Infinitary combinatorics withouth the axiom of choice

Infinitary combinatorics
withouth the axiom of choice
Dimitriou, Ioanna Matilde
advisor : Prof. Dr. Peter Koepke
Introduction and motivation for an investigation without choice.
The area of my work is mathematical logic and in particular set theory.
Set theory as axiomatised by the Zermelo-Fraenkel axiomatic system ZF serves as a powerful foundation for
mathematics. The axioms are strong enough so that common mathematical constructions can be carried out
in familiar ways and in great generality. Thus the “working mathematician” will only rarely have to deal
with the set theoretical status of assumptions and arguments.
Techniques, past and present work
To create models of set theory without the axiom of choice and with certain other properties, there is a certain technique called taking symmetric submodels of generic forcing extensions1 . One of the most intriguing
symmetric model construction still is Solovay’s model in which every set of reals is Lebesgue-measurable and
the axiom of choice fails. Such models are made from the elements of a generic forcing extension that satisfy
certain symmetry properties.
Axiomatic set theory examines the consistency of the Zermelo-Fraenkel system and its variants - a task not
only motivated intrinsically but in particular by the foundational role of set theory. By the second G¨odel
incompleteness theorem (which is presented in the poster of Jip Veldman), the consistency of set theory
cannot be proved absolutely, and one can only try to gather positive evidence for consistency.
If there were contradictions in ZF then the study of strong, or nearly “paradoxical” assumptions should be a
means of exposing the weaknesses of the system. Conversely, the theories of large cardinals (for an explanation of the large cardinal axioms see the poster of Jip Veldman) or of descriptive set theory and determinacy
(for an explanation of descriptive set theory and the axiom of determinacy, see poster of Stefan Bold) which
have been developed during the last decades can be interpreted as strong indications for the consistency of ZF.
My project envisages investigations of the relative consistencies (for the notion of consistency strengths, see
poster of Jip Veldman), without the axiom of choice (AC), for a range of combinatorial properties. Omitting
the axiom of choice has various motivations:
• The axiom of choice differs from the other set theoretical axioms by its non-constructive nature. Choice
sets - or equivalently maximal elements in the sense of Zorn’s lemma - exist but cannot in general be
defined explicitly. Since the early years of set theory, the axiom of choice has been discussed critically.
• The axiom of determinacy (AD) contradicts the axiom of choice but has rich and attractive consequences in descriptive set theory and infinitary combinatorics: Solovay and Martin proved that accessible cardinals like ℵ1 or ℵ2 are measurable showed that ℵω is a Rowbottom cardinal, etc. Measurable
and Rowbottom cardinals are certain large cardinals, measurables will be discussed in the third page
of this poster.
• Some unusual combinatorial consequences of the axiom AD which contradict the axiom of choice, e.g.,
partition properties with infinite exponents, have been studied in their own right and lead to fascinating
new structures. Since the hypothesis AD is rather modest by present-day standards, such combinatorial
properties are not as exotic as they originally seemed to be.
• A technical motivation for the project is that there are now sufficient forcing and inner model techniques
available which will lead to equiconsistency results for a range of well-known combinatorial principles
without AC. These principles have been considered in the context of the axiom of choice and, in that
context, are often too strong for equiconsistency results with present-day methods.
As the picture suggests and as described in Jip Veldman’s poster, we can view the generic forcing construction as taking the closure of the generic object under the set theoretic operations. The symmetric construction
is a certain modification of this technique that leaves out it’s wellorderings. Since the statement “all sets
can be wellordered” is equivalent to AC, one can see how a symmetric model may not satisfy the axiom of
choice.
As seen in the picture, the ordinals are the wellordered spine of all standard set theoretic models. When we
talk about cardinals, we mean here initial ordinal (i.e., the smallest ordinal of its size). Since without AC
not all sets are wellorderable, i.e., in bijection with an ordinal, not all sets will have a corresponding cardinal
and so for these sets size comparison becomes non trivial.
In this field of choiceless models of set theory, I am interested in certain large cardinal axioms. For my
master’s thesis at the Universiteit van Amsterdam, I worked with my supervisor Benedikt L¨owe on the
smallest of the large cardinal axioms, inaccessible cardinals without the axiom of choice. There we had the
problem of even defining what inaccessibility means without choice, since the definition with choice involves
size comparison. We ended up with three definitions we could show were really not equivalent and this project was then extended to a joint paper with Andreas Blass with one more interesting notion for inaccessibility.
In my current PhD project I look at several stronger large cardinal axioms. Some of the large cardinal axioms
talk about the existence of sets with certain combinatorial properties or are very connected to such. As the
title of this poster suggests, I am looking at these large cardinals, their properties and their implications for
the set theoretic world (model) they exist in, if we drop the assumption of choice.
Infinitary combinatorics and model theory
Measurability and consistency strengths
To give an example of a cardinal defined by a combinatorial property, I’ll give the definition of an Erd˝os
cardinal.
Finally I want to talk about measurable cardinals. Some consider these large cardinals as the first “really
large” cardinals; the first referring to their consistency strength. A cardinal κ is measurable if there exists an
ultrafilter U over κ (a subset of the powerset of κ) that is κ-complete, i.e., closed under taking intersections
of κ many sets in U . Such U is called a measure on κ and we think of U as containing the “large” subsets
of κ since elements of U have size κ.
For a cardinal α, the cardinal κ is called α-Erd˝os if for every
partition F of the set of all finite subsets of κ in two colours, there
is a subset H ⊆ κ of size α (i.e., H is in bijection with α), which
is homogeneous for the partition F , i.e., all the finite subsets of H
are assigned to the same colour by F .
For example in the picture on the left, the homogeneous set H
would have blue colour via F and it would be κ \ {x, z}. That is
because there are sets that contain x and y that are assigned grey
colour via F .
A very intriguing and long standing open question is whether we can have three or more successive measurable cardinals; the case with two holds under AD for ω1 and ω2 . The axiom AD has very exotic large
cardinal patterns and it has inspired many papers from researchers like Arthur Apter. This is also an area
of interest to me, recreating large cardinal patterns and combinatorial situations found under AD but with
weaker assumptions (since as mentioned in Stefan Bold’s poster, AD is quite strong consistency-wise).
I end this poster with two diagrams of some implications between consistency strengths with and without
the axiom of choice. An arrow below stands for weakening consistency strength.
In this case, the homogeneous set has size κ. If for all such partitions there are always κ-sized homogeneous
sets then κ is called a Ramsey cardinal.
Other principles I want to study can be characterised by statements about structures. A structure is a set
(called the underlying set) with some relations and/or functions, denoted usually as A = hA, f, R, . . . i. A
substructure of A is a subset of A with the functions and/or relations of A restricted to the subset. A
substructure of A is elementary if everything we can say formally about it, is also true for A. This field of
mathematical logic is called model theory and it studies general structures and their properties.
As an example of a model theoretic property for cardinals, here is the generalised
Chang conjecture. For cardinals κ, λ, κ0 , λ0 we write (κ, λ) (κ0 , λ0 ) for the statement that every structure hκ, ˚
λ, . . .i with underlying set κ and unary relation ˚
λ for
˚
˚
membership in λ (i.e., λ(x) iff x ∈ λ) has an elementary substructure hA, B, . . .i such
that the size of A is κ0 and the size of B is λ0 . This would look as in the picture on the right.
With the axiom of choice, several versions of the generalised Chang conjecture have very
high consistency strength or are even inconsistent. With Peter Koepke we found that without AC, many such relations between structures are possible, i.e., not inconsistent any
more. Also for the ones that are compatible with AC, their consistency strengths drop to
the existence of just one Erd˝os cardinal which is considered pretty low nowadays.
This result is going to be presented in the coming Logic Colloquium of the Association for Symbolic Logic
(ASL) this July in Wroclaw, Poland.
References
[1] Andreas Blass, Ioanna Dimitriou and Benedikt L¨owe, Inaccessible cardinals without the axiom
of choice, Fundamenta Mathematicae, vol.194, pp 179–189
[2] Akihiro Kanamori, The higher infinite, Large cardinals in set theory from their beginnings, Springer,
2003
[3] Ioanna Dimitriou and Peter Koepke, Equiconsistency of choiceless higher Chang conjectures
with one Erd˝
os cardinal, Abstract to appear in the Bulletin of Symbolic Logic
The reason why such a result was possible is that without AC several large cardinals can become quite
accessible; as small as ω1 , the smallest uncountable ordinal. Another recent observation is that without AC,
ω1 and other such small cardinals can satisfy very strong large cardinal properties, like being Ramsey or even
stronger.
Mathematisches Institut
[email protected]

Download Report