Date: Mon, 5 Mar 2001 16:34:24 -0800 (PST)
Subject: Phase B:letter 1
Randall,
Here starts my presentation of phase B. As I mentioned
earlier, the proof of phase C [which is the final desired result]
builds on the work of phase B.
We are working in the metatheory ZF- [or what comes to the same
thing, second order number theory]. It would be fairly routine to carry
out the proof in IDelta_0 + Exp. Indeed the proof can be carried out
in "Polynomial Time Arithmetic" but one must then be careful to spell
out the details of the treatment of first order logic and how
precisely proofs are encoded as bit strings.
We are given a model of ZC + Sigma_3 Replacement. Our task
is to produce a model of NFU*. The first order of business is to
massage the model to one with certain extra properties. That task [and
some preliminary comments about what one can do in the theory ZC +
Sigma_n-replacement + V=L] will be the contents of the present letter.
Let's call the given model N_0. We apply Godel's construction
inside it getting a model of the theory "ZC + Sigma_3-replacement +
V=L". We use T_n as an abbreviation for "ZC + V=L +
Sigma_n-replacement". We let N_1 be the model of T_3 just constructed.
Work inside N_1. If there is a limit cardinal lambda such that
L_lambda is a model of T_3, choose the least such and let L_lambda be
the model N_2. If not, let N_2 be N_1.
I am being slightly sloppy here. Really, if the first case
arises, N_2 is the model whose underlying set is the set of all
elements of the underlying set of N_1 that N_1 thinks are in
L_lambda. [And the epsilon relation of N_2 is the restriction of the
epsilon relation of N_1.]
In what follows, we refer to N_2 as N. It is a model of T_3 +
"For no limit cardinal lambda is L_lambda a model of T_3".
Caution: There is absolutely no reason to think that the ordinals
of N are well-ordered [or even that all the integers of N are standard].
What we have gained by this manouvering is the following
property:
Lemma 1. N thinks: There is a definable map of omega cofinally into
the ordinals.
Remarks:
1) One can actually show that the map in question is Sigma_4. We
won't have need of this more precise result
2) An entirely analogous result holds for T_2: If "ZC +
Sigma_2-replacement" is consistent, then there is a model N of "T_2 +
'for no limit cardinal lambda is L_lambda a model of T_2' ". In this
model N, there is a definable map from omega cofinally into the
ordinals.
We shall have need of this analogous result when we tackle phase C.
Before beginning the proof of Lemma 1, we state the following
proposition whose proof will be left as an exercise to the reader.
Proposition: Let n be a positive integer. Then the following are
theorem schemes of T_n:
A) If R(x,y) is a Sigma_n-relation, then R can be
uniformized. That is there is a Sigma_n-relation S such that:
(a) S(x,y) implies R(x,y).
(b) If R(x,y), then for some z, S(x,z).
(c) If S(x,z_1) and S(x,z_2), then z_1 = z_2.
B) Suppose S(x) is a Sigma_n formula. [S might have free
variables other than x that we are not displaying.] Then the
formula
(for all x in y) S(x)
is equivalent to a Sigma_n formula. [We require, of course,
that the variables x and y are distinct.]
C) Definition of functions by transfinite induction: Let F be a
Sigma_n class which is functional. I.e., if F(x,y) and F(x,z)
then y = z.
We are concerned with functions G defined on initial segments of
OR [possibly all of OR] that satisfy the following equation:
G(alpha) = F(G restricted to alpha). [for every alpha in the
domain of G]
Then either (a) for every ordinal alpha there is such a G with
domain alpha or (b) there is a least ordinal gamma such that
no such G exists with domain gamma.
In the latter case, gamma must be a successor ordinal [say beta
+ 1] and F is not defined on the function on beta [call it
g_beta] that satisfies the above functional equation.
In case (a), the various g_beta's piece together to give a
class function mapping OR to V, say G, which satisfies the
functional equation. This G is Sigma_n. [Or if there is a
maximal set-sized g, it is Sigma_n in the same parameters as
F.]
Some comments on the proof of A through C:
These are closely analogous to results of Jensen about
transitive models of V=L. The fact that we have full
selection is a great help in the proofs. The proofs proceed by
induction on n. For a fixed n, one proceeds in the order A, B,
C in giving the proofs.
We return to the proof of Lemma 1.
First using C2, we see that T_2 proves that for every ordinal
alpha there is a lbfp [limit of Beth fixed points] greater
than alpha. {One first shows that for every alpha, Beth_alpha
exists; then one shows that there are arbitrarily large
Beth fixed points. Finally, one proves the stated result about
lbfp's.}
Next, as a piece of temporary notation, say that an ordinal
beta is n-good for alpha [alpha is also an ordinal] if:
1) beta is greater than alpha;
2) beta is a lbfp;
3) Every Sigma_n formula which is true of some x and which has
parameters in L_alpha is true of some x in L_beta.
Using full selection plus Sigma_3-uniformization and
replacement, one sees, in T_3, that for every alpha there is
an ordinal beta which is 3-good for alpha.
Next using the fact that we have full induction on omega, one
defines a class map H from omega into OR as follows:
H(0) = omega.
H(n+1) is the least ordinal which is 3-good for H(n).
If the range of H was not cofinal in OR, we could define kappa
= sup range H. [This uses full selection since I have not
estimated the logical complexity of H.]
But then L_kappa would easily be seen to be a model of T_3,
contrary to our choice of the model N.
This completes the proof of Lemma 1 and with it this letter.
Date: Mon, 5 Mar 2001 22:30:12 -0800 (PST)
Subject: Letter 2 of phase B.
Randall,
This letter covers a small but important point that could have
appeared in letter 1.
Let me start with a fact that I won't prove [or use in the
proof of phase B.] It explains why the naive proof requires
T_3 rather than T_2.
FACT: Work in T_2. Suppose that for no limit cardinal lambda
is L_lambda a model of T_2. Then there is a Sigma_2 map F from OR into
omega such that for any integer n, the class of alpha such that
F(alpha) = n is bounded in OR. [I.e., it is a *set*.]
Lemma 3. [T_3]. Let F be a Sigma_2 map from OR into some ordinal
gamma, Then for some ordinal eta less than gamma, the class of
alpha such that F(alpha) = eta is cofinal in OR
Remark: Of course, there is no contradiction between Lemma 3
and the FACT. Together, they do establish that T_3 proves that
there is a limit ordinal lambda such that L_lambda is a model
of T_2.
Proof of Lemma 3:
We work in T_3, and assume that F counterinstances the
lemma. We shall derive a contradiction.
Define a relation R(eta, theta) as follows:
R(eta, theta) holds if theta is an ordinal, eta is an ordinal
less than gamma, and for all ordinals delta >= theta F(delta)
is unequal to eta.
Claim 1: R is Pi_2:
Proof: R can be written:
1) eta is an ordinal;
2) theta is an ordinal;
3) eta is a member of gamma;
4) For all delta, xi:
If delta is an ordinal and xi is an ordinal and
delta >= theta and F(delta) = xi,
then xi is unequal to eta.
Clauses 1 through 3 are Delta_0. It suffices to see that the
last two lines of clause 4) are Pi_2. But these lines are an
implication whose hypothesis is Sigma_2 and whose conclusion
is Delta_0, so this is clear.
Our assumptions that F counterinstances the lemma imply that
for every eta < gamma, there is a theta such that
R(eta, theta).
Uniformize R by a Sigma_3 function H mapping gamma into OR. By
Sigma_3 replacement, there is an ordinal xi which is greater
than every element of range H. But then there is no possible
value for F(xi). [If F(xi) = delta, then this contradicts the
facts that:
(a) xi > H(delta);
hence (b) R(delta, H(delta)), so
(c) F(xi) is unequal to delta. ]
This completes the proof of the lemma and so ends letter 2 of
phase B.
Date: Tue, 6 Mar 2001 13:51:36 -0800 (PST)
Subject: Letter 3 of Phase B
This completes my discussion of Phase B of the proof.
1. Let's start this letter by reviewing the construction in
phase A:
1) We introduced a certain term language L.
2) By a length omega construction, we constructed a term model M.
3) From the model M, we easily derived a model of set-theory with an
automorphism. I think I used the same notation for this model as for
the term-model. But now I will call it M*.
4) From M*, we derived in the usual way a model Q of NFU. Steps we had
taken in the construction of M ensured that Q was in fact a model of
NFU*.
Recall from Letter 1, that we carefully prepared a model N of
T_2. The first key difference in our current construction will
be that everything is internal to N. Thus the language L will
be described by a certain class of N. And the models M, M*,
and Q will be proper classes of N.
Also, note that our construction in phase A was indexed by the
set omega of non-negative integers. Since our current
construction will be internal to N, it will be indexed by the
integers of N.
In phase A, our term language was determined by a certain
ordinal alpha. We didn't specify alpha in advance, but let it
be dynamically determined during the course of the
construction.
What plays the role of alpha in our current construction is
the class of all ordinals of the model N. With this as a
guide, it should be clear what the terms of our term language
are. Simply replace in the old definition the phrase "ordinal
less than alpha" by the word "ordinal" and carry out the
definition inside N.
2. We pause to indicate how the verification of the crucial
axiom of NFU* will be verified. [Selection from s. c. sets
using arbitrary formulas.]
Work in NFU for the moment. There is the model Z consisting of
isomorphism classes of topped well-founded extensional
structures. As a class of Z, we have W consisting of those
elements of Z whose transitive closures have strongly
Cantorian cardinalities.
We shall arrange the construction of Q, so that the analogue
of W is canonically isomorphic to our starting model N of T_3.
Since Q is coded by a class of N, any "definable in Q"
subcollection of a strongly Cantorian ordinal, will be
"definable in N". Hence it will lie in N, and be constructible
at some ordinal stage lying in the strongly Cantorian part of
Q. So it will lie in Q.
3.
One of the things achieved in letter 1 was that there was a
definable map of omega into the ordinals whose range was
cofinal with OR. It is easy to massage this map into one with
the stated property whose range consists of lbfp's and which
is strictly increasing. We let the map be n --> gamma_n.
Our construction of our final term-model will closely
approximate the one done in phase A. In particular, alpha will
be obtained as the limit of a strictly increasing sequence of
smaller ordinals alpha_n. To achieve that the limit of the
alpha_n's is indeed the class of all ordinals of N, we shall
require that alpha_n > gamma_n.
Recall that in phase A, a key role was played by instantiation
functions. In our current context, the corresponding functions
will all be proper classes of N. We will deal with this
difficulty as follows:
All the instantiation functions we use will be Sigma_2. We
will "Godel number" the Sigma_2 functions in a moment in a
straightforward way. The Godel-numbers will be certain sets in
N. The construction will refer to an instantiation function by
giving its Godel number.
So how do we Godel number Sigma_2 functions: By pairs
*. Here i is an integer which is the Godel number of A
Sigma_2 formula with three free variables, say x, y, z.
We uniformize phi_i in the variable y [getting a map from V^2
to V] which need not be total. We plug in p for the variable
z, getting the partial function from V to V with Godel number
**.
4. Our construction of the model M, will be by defining a
function f from omega to V^3 [all this is done inside N, of
course].
The function f will be a proper class of N, and
definitely not be given by a set of N.
Suppose that f(n) = . Then these will have the
following significance;
a_n will be an ordinal. In fact a_n is precisely what we have
previously referred to as alpha_n. We will arrange that the
sequence alpha_n is strictly increasing in n, that alpha_n is
an lbfp, and that alpha_n > gamma_n.
b_n is an equivalence relation on the terms of rank at most
(alpha_n,n). We require of course that b_n allows the various
relevant functions of our language that are available at stage
n to be well-defined on equivalence classes.
c_n is the Godel number of a Sigma_2 function with domain the
cardinals of N which shows that the equivalence relation b_n
is "very-well-instantiated".
Logically, to describe the construction, I should specify f(0)
and then show how to obtain f(n+1) from f(n). But I shall
leave the specification of f(0) "to the reader" and turn to
the specification of f(n+1) from f(n). This follow closely the
material in letter7.dvi that I sent you in my discussion of
part A of the proof, and I shall refer to that manuscript.
I shall assume that n > 0. If n = 0, we make no attempt to
control the strongly Cantorian ordinals, and the passage from
n to n+1 is slightly easier.
Following section 2.2 of letter 7, we define (a) the cantorian
terms of rank (alpha_{n-1}, n-1); (b) The set W_n of
such terms that are destined to denote
ordinals, and (c) the set W_n^\star of equivalence classes of
such terms.
It is again clear that W_n^\star is well-ordered [in the way
described in section 2.2]. We can define the notion of a
divergent equivalence class as before. To refine an
instantiation function to witness divergence merely uses
Sigma_2 uniformization. We can again introduce h_n to insure
that the divergent terms will not give strongly Cantorian
ordinals.
We now start using the fact that we have Sigma_3
replacement. Some of these uses are essential [as is shown by
the FACT in letter 2 of phase B]. I haven't checked that they
all are.
The relation that gamma is an upper bound for the values of a
convergent cantorian term [in W_n] is Pi_2. We can uniformize
this Pi_2 relation by a Sigma_3 function. Applying Sigma_3
replacement, we get a single ordinal delta_n that bounds the
values of all convergent terms in any instantiating model
given by our current instantiating function.
We can now define alpha_{n+1} it is the least lbfp which is
greater than all of the following: (a) alpha_n; (b)
gamma_{n+1}; (c) delta_n.
We now argue much as in section 2.9 of Lemma 7, invoking
Erdos-Rado, and getting an equivalence relation twiddle_eta [THAT
DEPENDS ON eta] and a Sigma_2 function [analogous to the F_3 of the
section cited] that gives for each eta, a model depending on
eta, such that Y has ordertype at least eta, and that increasing
tuples of the appropriate type instantiate the equivalence relation
twiddle_eta. This only uses Sigma_2 uniformization.
Here comes the crucial use of Sigma_3 replacement: We can
find some fixed equivalence relation on the terms of rank
at most (alpha_{n+1},n+1) that occurs as twiddle_eta for
unboundedly many eta. [This uses Lemma 3 from letter 2 of
phase B!]. Once we have this relation, we take it as
b_{n+1}. Another application of Sigma_2-uniformization
gets a Sigma_2 function defined on the infinite cardinals
that well-instantiates b_{n+1}.
This completes letter 3, and with it our discussion of
phase B of the proof.
*