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.,
**Σ**^{1}_{3} Cohen forcing
absoluteness holds if and only if every
**Δ**^{1}_{2} 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:*

- 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.
- 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.
- M. Sevenster, Branches of imperfect information: logic, games, and computation, PhD Thesis, ILLC UvA.

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: