Games in Logic, Language and Computation 14½

GLLC 14½

The Fourteenth Workshop on Games in Logic, Language and Computation

Amsterdam, The Netherlands, 29 September 2007, 10:00-19:00


Ioanna Dimitriou
Topological regularities in second order arithmetic

In the '60s, Robert Solovay showed the consistency of ZF plus 'all sets of reals are Lebesgue measurable, have the Baire property and the perfect set property', from the consistency of ZFC plus an inaccessible cardinal. He did this by Levy-collapsing everything below the inaccessible and then looking at the sets that are definable from countable sequences of ordinals. If one cuts the universe at an inaccessible, one gets a model of ZFC (i.e., if κ is an inaccessible then Vκ is a model of ZFC). Moreover, in models of second order arithmetic (SOA) sets of reals are definable classes of reals. We show that if we only care for ending up with a model of SOA instead of ZFC, then Solovay's technique works without the inaccessible. That is, we show that if we Levy-collapse entirely a model of ZFC then we get a model of SOA where all sets of reals are Lebesgue measurable, have the Baire property and the perfect set property. This is joint work with Peter Koepke and is building on work by Peter Koepke with Michael Möllerfeld, who gave a talk on initial steps of this in the Logic Colloquium 2003 in Helsinki.

Tapio Eerola
On singular cardinal arithmetic

I discuss problems and results in singular cardinal arithmetic.

Daisuke Ikegami
Forcing absolutenes and regularity properties

There is a close connection between forcing absolutenss and regularity properties, e.g., Σ13 Cohen forcing absoluteness holds if and only if every Δ12 set of reals has the Baire property. It is known that the same kind of phenomena occurs for random forcing and Lebesgue measurability, Mathias forcing and completely Ramseyness, Sacks forcing and Bernstein property etc. In this talk, I will introduce a class of forcing notions from which we can define the corresponding regularity properties and prove the equivalence as above for each forcing in the class. This class contains all practical forcing notions connected to regularity properties and this result implies the unknown equivalence for some forcings (e.g. Silver forcing and Miller forcing).

Jokke Hasa
Proper Forcing Axiom implies 2aleph-0=aleph-2

My intention is to give a quick overview of the proof by Velickovic. There is a lot involved, but I will only give the basic ideas, and refer to other sources for details. The proof consists mainly of three parts. First part is to show that Todorcevic's Open Colouring Axiom implies that the so-called bounding number b (cardinal invariant) equals aleph-2. In the second part it is demonstrated that PFA actually implies OCA. Third part, on the other hand, involves showing that PFA implies that the cardinality of the continuum equals b. The first part consists only of combinatorics of the Baire space (omega-sequences of natural numbers), the last two include some two-step iterated forcing.

Lauri Keskinen
Isomorphism and second order equivalence

It is independent of ZFC whether all second order equivalent countable models in a finite vocabulary are isomorphic. In the talk we will present this old result of Ajtai. We will also present a generalization of this result to bigger cardinals: It is independent of ZFC whether all L equivalent models of cardinality κ+ in a finite vocabulary are isomorphic, when L is second order strengthening of the infinitary language Lκ+,ω.

Yurii Khomskii
Regularity Properties and Determinacy

As is well-known, the Axiom of Determinacy (AD) implies that all sets of reals have the regularity properties. Without AD, this implication still holds in the following 'classwise' sense: if all sets in a large collection Gamma are determined, then all sets in Gamma are regular. On the other hand, we can look at `pointwise' consequences of determinacy: if a set A is determined, can we say anything about its regularity? In this talk I will discuss these `pointwise' consequences of determinacy. Mostly, the results will be negative (i.e. we can give counter-examples to pointwise implications) but in some cases there are also surprisingly interesting results.

Vadim Kulikov
Weak Ehrenfeucht-Fraïssé-game

Here we investigate a weak form of the Ehrenfeucht-Fraïssé-game. Given structures A and B, players I and II choose one by one elements from each structure as long as defined and II wins if the resulting substructures are isomorphic. The difference to ordinary Ehrenfeucht-Fraïssé-game is that the isomorphism need not depend on the proceeding of the game. The main result is that if structure A and B are given and the length of the game is κ, where κ is a cardinal such that κ = κ, then player I wins the weak game if and only if he wins the ordinary Ehrenfeucht-Fraïssé-game. It follows that if the ordinary EF game of length κ is determined, then the weak one is also. In particular, if κ = ω, the games EFω and EF*ω (weak) are in this sense equivalent and the structures are back-and-forth equivalent if and only if II has a winning strategy in the weak EF-game. This fails for games of finite length and for games of length ω+n where 1 < n < ω.

Brian Semmes
The tree game

In this talk, I will review the tree game and show that it characterizes the Borel functions on the Baire space.

Laura Sutinen
Suslin trees and Kurepa trees on ω1

I will discuss killing a Suslin tree using Suslin tree as a forcing notion and the fact that PFA implies that all Suslin trees are killed. I will also discuss the consistency of Kurepa's conjecture.

Jakub Szymanik
Complexity of natural language quantifiers

I will present some new results on computational complexity of everyday language quantifiers. Recently descriptive complexity perspective on natural language quantifiers has been taken in literature (see e.g. Mostowski & Wojtyniak 2004, Sevenster 2006). Among others it was observed that some natural language quantifiers when assuming their branching interpretation define NP-complete classes of finite models. Unfortunately, all these NP-complete natural language constructions are ambiguous. Their reading varies between easy and difficult interpretations. Moreover, such sentences can hardly be found in the corpus of English language. One of the goals of this paper is to present NP-complete natural language quantifiers which not only occur frequently in everyday English but also are one of the sources of its complexity. To achieve that we will analyse semantics of reciprocal expressions, like "each other", "one another" (see Dalrymple et al. 1998) by defining appropriate lifts on monadic quantifiers. Main result shows that there is computational dichotomy between different interpretation of reciprocal quantification. Strong reciprocal sentences with proportional or counting quantifiers in antecedents are NP-complete. However, PTIME quantifiers are closed on intermediate and strong reciprocal lifts.


  1. M. Dalrymple, M. Kanazawa, Y. Kim, S. Mchombo, S. Peters, Reciprocal expressions and the concept of reciprocity, Linguistic and Philosophy 21(1998), pp. 159-210.
  2. M. Mostowski and D. Wojtyniak, Computational complexity of the semantics of some natural language constructions, Annals of Pure and Applied Logic 127(2004), pp. 219-227.
  3. M. Sevenster, Branches of imperfect information: logic, games, and computation, PhD Thesis, ILLC UvA.

Lauri Tuomi
On the κ-cub game

When κ is a regular cardinal, there is a game that quite intuitively seems to characterize the κ-cub filter on κ+, though this is not exactly the case if large cardinal assumptions are made. However, with additional assumptions the characterization holds, especially the weak square for κ is such an assumption.

Last changed: September 18th, 2007