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.
I discuss problems and results in singular cardinal arithmetic.
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).
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.
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κ+,ω.
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.
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 < ω.
In this talk, I will review the tree game and show that it characterizes the Borel functions on the Baire space.
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.
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.
References:
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.