Alternative Finestructural and Computational Approaches to Constructibility [Elektronische Ressource] / Merlin Carl

Sujets

• Mathematics

Informations

• Publié par: rheinische_friedrich-wilhelms-universitat_bonn
• Publié le: 01 janvier 2011
• Nombre de lectures: 20
• Langue: Deutsch
• Poids de l'ouvrage: 1 Mo

Extrait

Alternative Finestructural and Computational
Approaches to Constructibility
Dissertation
zur Erlangung des Doktorgrades (Dr. rer. nat.)
der
Mathematisch-Naturwissenschaftlichen Fakult at
der
Rheinischen Friedrich-Wilhelms-Universit at Bonn
vorgelegt von
Merlin Carl
aus
Dusseldorf
Bonn 2010Angefertigt mit Genehmigung
der
Mathematisch-Naturwissenschaftlichen Fakult at
der
Rheinischen Friedrich-Wilhelms-Universit at Bonn
1. Gutachter: Prof. Dr. Peter Koepke
2.hter: Prof. Dr. Stefan Geschke
Tag der Promotion: 10.06.2011
Erscheinungsjahr: 2011
2Fur Elisabeth Th olken,
Lux In Tenebris.
3Danksagungen
Mein Dank an dieser Stelle hat jenen zu gelten, ohne deren Unterstutzung
und Vorbild diese Arbeit nicht entstanden w are.
Ich danke meinem Betreuer Peter Koepke fur seinen engagierten, aber
niemals aufdringlichen Rat, seine Bereitschaft, seinen reichen
Erfahrungsschatz zu teilen, sein atigest Interesse an meinem akademischen
Fortkommen vor, w ahrend und nach dieser Arbeit - und nicht zuletzt dafur,
mich fur die Mengenlehre gewonnen zu haben; meiner Mutter Heike Carl,
die mich viel Wertvolles lehrte, zu viel fur eine Aufz ahlung im einzelnen;
meinem viel zu fruh verstorbenen Vater Wolfgang K onig-Carl dafur, dass er
mir sein Interesse am Grunds atzlichen, das sp ater ein mathematisches
werden sollte, hinterlie ; meiner Lehrerin Inge Hachtel, die es auf die
Mathematik, und meinem Lehrer Horst Frings, der es auf die Philosophie
hin lenkte - erst durch sie erhielt es sein heutiges Gepr age; meinen
Mitstudenten und Freunden Dominik Klein und Ulrike Endesfelder fur
Zuspruch und Aufmunterung in schwierigen Zeiten; Immanuel Kant,
Friedrich Nietzsche und Martin Heidegger, die mich die gro en und tiefen
Ziele klarer zu sehen und nie aus dem Blick zu verlieren lehren; und meiner
Gef ahrtin Elisabeth Th olken, mit der und durch die sie sich nicht blo
denken, sondern leben lassen.
41 Introduction
Axiomatic set theory serves as a foundation for pure mathematics. About
80 years after the formulation of the formal system for set theory by Zermelo
and Fraenkel,ZFC, it seems that any theorem of common mathematics can
be formulated as an-formula and that every argument acceptable as a proof
in any area of pure mathematics with the exception of set theory itself has
a formal counterpart within rst-order predicate calculus, starting from the
axioms of ZFC.
Apart from its intrinsic value and philosophical relevance, this has two con-
sequences that are particularly remarkable: First, through the use of deriva-
tions withinZFC, mathematicians have a tool at hand that can in principle
be used to reformulate proofs as syntactical objects that are mechanically
checkable. Second, by giving such a precise de nition of the notion of a
proof, proofs itself could become a subject of mathematical study. Deriva-
tions withinZFC are thus in a similar relationship to proofs in the intuitive
sense as Turing programs are to the informal idea of a ’method’ or an ’algo-
rithm’. Arguably, the most important advantage of this is the possibility of
independence proofs: Having transformed proofs from the metatheory into
objects of mathematical study, the statement that a certain mathematical
statement has no proof becomes itself a mathematical statement, and so
does the statement that is undecidable, i.e. that there are neither proofs
for nor for:.
The usual way to prove something like this is the construction of models:
Assuming that some modelM ofZFC is given, one describes how to turn it
into a model ofZFC + and into another model ofZFC +:. This implies
the independence of from ZFC, provided ZFC is consistent.
There are essentially two methods for such constructions. The one, forcing,
consists in adding extra objects toM in a controlled way, extending it to an
outer model ofZFC and was invented by Paul Cohen. The other, historically
rst, method, is due to G odel [39]: Here, one passes from a class-sized M to a
potentially-smaller, de nable, class-sized submodel of M, a so-called inner
model. The simplest inner model, the constructible hierarchyL, is generated
by the following ordinal recursion:
51. (1) L =;0
2. (2) L = Def(L )+1
S
3. (3) L = L <
Here, Def(x) is the set of sets de nable by an 2-formula over x, i.e. of sets
of the formfy2xjxj=(y;p~)g for some2-formula and some nite vector
S
p~ x. Then L is L . It is rather easy to check that L is a model2On
of ZFC containing all ordinals, and in fact the-smallest one. Because of
its very concrete and uniform de nition, L can be analyzed much easier and
deeper than a general model of ZFC. An important and probably the most
famous example is Cantor’s continuum hypothesis (CH). The trouble with
CH in ZFC seems to be that ZFC does not give a precise meaning to the
notion of a subset of!; hence, there are models where the size of the contin-
uum becomes arbitrarily large. On the other hand, the set of real numbers
in L is very clear. This allows one to demonstrate that all reals in L are
already elements of L L, which implies that Lj= CH. In this way, G odel!
1
demonstrated the relative consisteny of CH.
The research on L made a great step forwards through the invention of
Jensen’s ne structure theory. This studies in detail at which stages of the
recursion new subsets of ordinals arise and thereby helps to reveal the com-
nbinatorial content of L. Roughly, the -projectum of L is the smallestn
ordinal such that there is a -formula andp~ L with the propertyn fin
thatfx2 LjL j= (x;p~)g\2= L . The lexically minimal such param-
neter p~ is then the -standard parameter. If = , the structure L isn
closed under -comprehension, so the projectum can be seen as a measuren
for the closedness of a structure. Through the use of bounded truth predi-
cates, the so called master codes, and relativized structures, reducts, these
ne structural parameters become compatible with extension techniques for
embeddings and condensation arguments. The theory becomes smoother by
using theJ-hierarchy instead of theL ’s. With these tools, strong combina-
torial principles like the square principle or the existence of morasses could
be demonstrated to hold in L.
However, these techniques lead to very complicated proofs. Typically for a
nestructural construction, a lexically minimal triple h;n;p~i is considered
6such that some interesting object (like the collapse of an ordinal or a co nal
sequence) is de nable by a -formula over J in parameter p~ J . Itn fin
is then shown with considerable e ort that these triples are preserved by
su ciently well-behaved maps like Mostowski collapses. Usually, the combi-
natorial intuition is encoded in the case where is a limit ordinal andn = 1.
The nestructural apparatus is then used to reduce every other case to this
one. When one asks for simpli cations of nestructure, it is therefore natural
to try to set up a hierarchy in such a way that anything is -de nable over1
a level, so that the messy reduction procedure is avoided.
Several di erent ne structures based on this main idea have been proposed
since the publication of [6]. Most notably are Jensens own -theory, where
the mentioning of codes is almost completely avoided by a clever modi ca-
tion of the Levy hierarchy. In [28] this is used for a comparably short proof
of several combinatorial principles. Silver [19] used very slowly growing hier-
archies of hull operators, known as Silver machines, to eliminate large parts
of nestructural considerations from combinatorial proofs in L. A canonical
choice of a Silver machine based on G odels L -hierarchy lead to the hyper ne
structure of Friedman and Koepke [16].
The F -hierarchy is another approach in this spirit. Its levels are de ned by
iterating a very limited comprehension operator, restricted to quanti er-free
formulas in an extended set-theoretical language with build-in symbols for a
well-ordering, a comprehension operator and Skolem functions. It was rst
described van Eijmeren in [15], and later on used by Koepke for a simpli ed
proof of the covering lemma for L in [14].
In the rst section, we introduce the F -hierarchy. The purpose of this part
is two-fold: We give a complete account on results in the F -hierarchy and
extend the range of these results, thereby exploring the possibilities and bor-
ders of this approach. First, we introduce the F -hierarchy and the basic
related notions: We de ne hull operators, prove a condensation theorem for
the F -hierarchy and introduce structure-preserving maps between F -levels,
so called ’ ne maps’. Simple combinatorics like GCH and versions of diamond
are carried out. These proofs turn out to be rather stable between di erent
hierarchies. Then, we consider direct limits of F -structures and introduce a
technique for extending ne maps to larger domains. This is the basis for a
proof of the covering lemma for L and a proof of the approximation lemma,
claiming that any set of ordinals closed under the basic operations of the F -
]hierarchy is a union of countably many constructible sets, provided that 0
does not exist. Through the use of the new approach, there are considerable
7simpli cations in both proofs. In particular, due to the homogenity of the
comprehension operator, no case disti