Foundations of Mathematics (Malestrom)

[ Pobierz całość w formacie PDF ]

�
A set X is said to be constructible if X " L� for some ordinal �. The class of
all constructible sets is denoted L.
Lemma 5.4.2. For all ordinals �, L� is a transitive, pure, well-founded set,
and L� �" R�.
Proof. For any transitive, pure, well-founded set T , we have T �" Def(T ) �" P(T )
and hence Def(T ) is again a transitive, pure, well-founded set. With these
observations, the lemma follows easily by transfinite induction on �.
Lemma 5.4.3. For all ordinals �, we have � = L� )" Ord.
Proof. If T is any transitive, pure, well-founded set, then for any a " T we
have that a is an ordinal (i.e., a von Neumann ordinal) if and only if T satisfies
a is transitive and (a, "|a) is a linear ordering . Thus T )" Ord " Def(T ).
With this observation, the lemma follows easily by transfinite induction on (von
Neumann) ordinals �.
103
We are going to show that the constructible sets form a model of ZFC.
Some of the axioms of ZFC are straightforwardly verified in L using Lemma 5.3.5.
For instance, the Union Axiom holds in L because x " L� implies x " L�.
The Pairing Axiom holds in L because x, y " L� implies {x, y} " L�+1. The
Empty Set Axiom holds in L because " " L1. The Axiom of Infinity holds in
L because � " L�+1. The Axioms of Extensionality and Foundation hold in L
because L is transitive and consists of pure, well-founded sets.
To show that the Power Set Axiom holds in L, let X be any constructible
set. For each Y " P(X) )" L put �(Y ) = the least � such that Y " L�. Put
� = sup{�(Y ) | Y " P(X) )" L}. Thus P(X) )" L �" L�. Hence P(X) )" L is
definable over L�; namely, it is the set of all Y " L� such that L� satisfies
Y �" X. Hence P(X) )" L " Def(L�) = L�+1. We have now shown that for all
X " L, P(X) )" L " L. From this it follows by Lemma 5.3.5 that the Power Set
Axiom holds in L.
To show that Comprehension and Replacement hold in L, we shall need the
following lemmas.
Lemma 5.4.4. Let f1, . . . , fk be functions from Ord to Ord. Then there exist
arbitrarily large ordinals � such that � is closed under f1, . . . , fk, i.e., fi(�)
for all �
Proof. Given an ordinal �, define an increasing sequence of ordinals �n, n " N
inductively by �0 = �, �n+1 = max(�n + 1, sup{fi(�) | �
k}). Putting � = sup{�n | n " N} we see that � > � and � is closed under
f1, . . . , fk.
Lemma 5.4.5 (reflection). Let F (x1, . . . , xn) be a formula of L" with free vari-
ables x1, . . . , xn. Then there exist arbitrarily large ordinals � such that, for all
a1, . . . , an " L�, L satisfies F (a1, . . . , an) if and only if L� satisfies F (a1, . . . , an).
Proof. Replacing " by � "� as necessary, we may safely assume that F contains
no occurrences of ". Now let "y Gi, i = 1, . . . , k be a list of the subformulas of F
of the form "y G. Write Gi a" Gi(y, xi1, . . . , xin ) where xi1, . . . , xin are the free
i i
variables of "y Gi. For a1, . . . , an " L, put gi(a1, . . . , an ) = the least ordinal
i i
� such that a1, . . . , an " L� and such that, if L satisfies "y Gi(y, a1, . . . , an ),
i i
then L satisfies Gi(b, a1, . . . , an ) for some b " L�. Define fi : Ord �! Ord by
i
fi(�) = sup{gi(a1, . . . , an ) | a1, . . . , an " L�}. By the previous lemma, there
i i
exist arbitrarily large ordinals � such that that � is closed under f1, . . . , fk. It
is straightforward to verify that such an � has the desired property.
Remark 5.4.6. The proof of the previous lemma used only the following prop-
erties of the constructible hierarchy: � d" � implies L� �" L�; and L� = L�
�
for limit ordinals �. Since the R� hierarchy also has these properties, the same
lemma holds for the R� hierarchy as well. This has the following interesting
consequence: If F1, . . . , Fk is a finite set of sentences that are true in the real
world, then there exist arbitrarily large ordinals � such that F1, . . . , Fk are true
in R�.
104
Lemma 5.4.7. L satisfies the Comprehension and Replacement Schemes.
Proof. To show that the Replacement Scheme holds in L, let f : L �! L be a
function which is definable over L. We must prove that, for all a " L, rng(f�!a) =
{f(u) | u " a} also belongs to L. Note first that, since f is definable over L,
we have parameters c1, . . . , cn " L and a formula F (u, v, z1, . . . , zn) with free
variables u, v, z1, . . . , zn such that, for all u " L, f(u) = the unique v " L such
that L satisfies F (u, v, c1, . . . , cn). Now given a " L, put b = rng(f�!a). We [ Pobierz całość w formacie PDF ]

Pokrewne