Date: Tue, 6 Mar 2001 16:27:03 -0800 (PST)
Subject: Phase C: first letter
Randall,
1. Here starts the series of letters in which I present the
proof that Con(ZC + Sigma_2 Replacement) entails Con(NFU*).
We are given a model N of ZC + Sigma_2 Replacement, N. We can
and do assume that V=L holds in N. Moreover, we can and do
assume that for no limit cardinal lambda of N is L_lambda a
model of Sigma_2 replacement.
It follows, as I discussed in the first letter of phase B,
that there is a definable map from omega to OR, in N, whose
range is cofinal in OR. We can and do assume that this map is
strictly increasing, and that its range consists of lbfp's.
2. There is much in common between the proof in phase C and
the earlier proof in phase B, and I shall begin by reviewing
these common elements. Before doing that, I make the
following remark:
There is a clear lineage to this proof that runs as follows:
Jensen's proof that for every ordinal alpha, there is an alpha
model of NFU.
Phase A.
Phase B.
Phase C.
Each phase has a lot in common with its immediate
predecessor. But there is very little commonality [though
there is some-- for example, the use of Erdos-Rado] between
Jensen's original proof, and phase C. Thus had I chosen to
present phase C without indicating its origins, it would look
much more original than it actually is.
2. Here is a very high level outline of the proof. Again, we
will be constructing a certain theory T [that plays the role
of the "term model" M of phase B.]. The construction will take
place in N, and proceed in omega stages. Roughly speaking,
this has the effect that we are dealing with only a "set's
worth" of problems at any stage. Because there is a definable
cofinal map of omega into OR, we will succeed in "handling
everything" by the end of our construction.
We remark that the theory T will be a proper class of the
model N. Indeed, even the approximations to T [call them T_n]
will be proper classes of N. The T_n's will be Sigma_2, but we
will lose that in the limit, though T will be of course,
definable in N.
[I haven't bothered to compute what its complexity is. My
guess is that it is either Sigma_3 or Sigma_4.]
The theory T will have a canonical term-model M*. M* will be a
model of a significant amount of set-theory: roughly, MacLane
set-theory + KP + V=L + "There are arbitrarily large lbfps."
The model M* will have an obvious automorphism and so yield,
in the usual way, a model Q of NFU.
We will take steps during our construction to ensure that the
W [strongly cantorian initial segment of Z] of the model Q is
canonically identified with the model N. This together with
the fact that Q is a definable class of N will ensure, in the
usual way, that Q is a model of NFU*.
3. Next let me emphasize what is different in the proof.
Rather than working with a term language as I did in phases A
and B I will be working in a certain infinitary language,
rather like, but not exactly like, the ones that figure in the
Barwise compactness theorem.
It turns out that if V_kappa is a model of ZC + Sigma_2
replacement and kappa has cofinality omega, then the
infinitary logic based on V_kappa has strong compactness
properties. [I will review this material in a subsequent
letter.] One can apply these results "inside N". The "proofs"
are sets of N, while the models constructed are proper classes
of N. By using this machinery, we are able to carry out an
analogue of the proof given in phase B for the weaker theory
T_2.
This ends letter 1 of phase C. My next task is to present my
version of the results about V_kappa. [Although it is all in
Barwise's book "Admissible sets and structures", it took me a
while to decode what he was saying. And when I did, I realized
that I would present the material quite differently than he
did.]
Date: Tue, 6 Mar 2001 22:35:15 -0800 (PST)
Subject: Letter 2 of phase C
This letter is devoted to my exposition of the theory of
compactness for uncountable structures V_kappa where kappa has
cofinality omega.
My source for all this is Barwise's book Admissible Sets and
Structures". Particularly relevant is section 7 of Chapter
VIII of Barwise. Especially Theorems 7.2 and 7.4.
That said, I found Barwise's exposition of this needlessly
long-winded and obscure. I hope to do a better job.
1. We will be working in ZFC. Our main focus is the following
situation:
(a) kappa is a cardinal of cofinality omega;
(b) V_kappa is a model of ZC + Sigma_2-Replacement + V = L.
(Presumably, the use of V = L here can be avoided.)
As Barwise remarks, the arguments will go through in the
following more general situation:
(a) kappa is a cardinal of cofinality omega;
(b) S is a subset of V_kappa;
(c) P(x,y) is the relation : y is the power set of x;
(d) define the notion of Delta_0 formula in the usual way
except we allow atomic formulas of the form Sx and P(x,y) as
well as those of the form x=y and x epsilon y.
(e) The structure is admissible,
Our special case corresponds to taking S to be the empty
set. To get the general case, replace Sigma_2 by "Sigma_1 in
the predicates P and S".
2. Our next task is to describe a certain family of infinitary
languages. The finiteness condition we impose is non-standard
and is needed for our particular application. The general
results I review in this letter would go through just as well
if the finiteness condition were not imposed.
There will be one language L_n for each n \leq omega.
Basic predicates of the language L_n:
Exactly as in set-theory, there are two: = and \epsilon.
Variables:
There will be a variable v_alpha for each ordinal alpha.
Constants:
These come in four flavors:
1) For each ordinal alpha [less than kappa-- we are working
within V_kappa!] there will be a constant \bar{alpha}. The
intended interpretation of \bar{alpha} is alpha.
2) For each ordinal alpha, there will be a constant
xi_alpha. These play a somewhat analogous role to the xi_i's
in the previous phases of the proof. And at a later point, I
will need also xi_i's for negative integers i. But they won't
appear in the current language definition.
3) For each m < n, and lambda < kappa there will be a term
h_{m, lambda}. Intuitively, this corresponds to
h_m(xi_lambda) in the phase B proof.
The definition of the language is inductive. In particular,
there will be Henkin constants introduced by the following
rule;
4) If psi(x) is a formula having only the variable x free, then
\iota x psi(x) is a constant of the language.
Subsequently, I will need the notion of, for example, a
xi_alpha appearing in some term or formula. One gives the
obvious inductive definition. But in particular, if xi_alpha
appears in the formula psi(x), it appears in the Henkin
constant \iota x psi (x).
Also xi_alpha appears in the constant h_{m,alpha}.
Some comments: Barwise works with Skolem functions rather than
Henkin constants. Normally that would be the right thing to
do. But for our purposes, the use of Henkin constants proves
more convenient.
We define the xi-support of a term or formula to be the set of
alpha such that xi_alpha appears in the term or formula.
The notion of the h-support of a term or formula is
analogous. It is the set of m such that h_m appears in the
term or formula.
The definition of term is evident as is that of atomic
formula. [Though note well, that because of our use of Henkin
constants, the notion of term and formula must really be given
a simultaneous inductive definition.]
The other clauses of the definition are:
(a) if psi is a formula and x is a variable, then \exists x
psi is a formula.
(b) if psi is a formula, so is \neg psi.
(c) The final clause is a little more involved. We give first
the usual version that is found in Barwise, and then the
amendment that we will actually use.
Imagine that \bigvee is the kind of "big V" used to denote a
possibly infinite disjunction.
And imagine that \bigand is a large upside down V of the sort
used to denote a possibly infinite conjunction.
The approximate version of clause (c) is: If S is a set of
formulas, then <\bigvee, S> is a formula [and denotes the
infinite disjunction of the formulas in S];
CAUTION: When we say "set" here we really mean element of
V_kappa.
To get our precise definition, we need to impose three
finiteness conditions on S. [The first is imposed by Barwise
as well.]
Finiteness conditions:
1) The set of alpha such that v_alpha occurs free in some
formula of S is finite.
2) The set of alpha such that xi_alpha appears in some
formula of S is finite.
3) The set of m such that h_m appears in some formula of S is
finite.
Note well; We do not require that the set of alpha such that
\bar{alpha} appears in some formula of S is finite.
This completes our description of the syntax of our infinitary
language L_n.
We have chosen not to have \forall and infinite conjunctions
to be an official part of our infinitary languages. However,
they can be introduced by abbreviations [inspired by de
Morgan's laws] in the usual way. We will feel free to use them
when informally describing formulas.
I hope the semantics of L_n is evident. In particular, given a
sentence of L_n [formula with no free variables] and an
L_n-structure [a structure where all the constants and functions
as well as the epsilon predicate are given interpretations],
then the sentence has a truth-value relative to this structure
which is defined in the evident way.
In what follows, we frequently use "L" to stand for one of the
L_n's just introduced.
Notice that the way we have set things up, the sentences,
formulas, terms, etc, are elements of V_kappa. However, it
will be important to allow structures which are not elements
of V_kappa. [We could get by considering just structures whose
underlying sets are subsets of V_kappa.]
I am next going to explicitly spell out what set corresponds
to each term or formula. The definition is inductive; we let
<~~> be the set corresponding to the term or formula s.
The definition that follows is totally routine. There is
nothing tricky going on.
As usual, is the Kuratowski ordered pair: {{x,y}, {x}}
Our ordered triple is just >
<> = <0,alpha>;
<> = <1,alpha>;
<<\bar{alpha}>> = <2, alpha>;
<< \iota x psi >> = <3, <>, <> >;
<< h_{n,alpha} >> = <4, n, alpha >;
<< \exists x psi >> = <5, <>, <> >;
<< \neg psi >> = <6, <> > ;
Now let S be a set of formulas. Let S* be {<~~~~> | s \in S}.
<< \bigvee S >> = <7, S* > ;
<< s \in t >> = <8, <~~~~>, <> >
<< s = t >> = <9, <~~~~>, <> >
I don't think I will ever use explicitly the definition just
given. But it is already being implicitly used in the
immediately following paragraph.
It is fairly easy to see that the notions of formula, term,
etc. are Delta_2(V_kappa). (In fact, I believe these notions
are Delta_1(V_kappa).)
We Godel number the Sigma_2 subsets of V_kappa in an evident
way. [I had to do essentially this when I Godel numbered
Sigma_2 partial functions in letter 3 of phase B.]
Let S be the set of sentences of L. [S is a "proper class'
from the standpoint of V_kappa.] We get a Godel numbering of
the Sigma_2 subsets of S as follows. The subset of S with
Godel number e is obtained by intersecting S with the subset
of V_kappa with Godel number e. [e here is some element of
V_kappa.]
Theorem: Sigma_2 completeness. The set of e such that the collection
of sentences with Godel number e has a model [not necessarily
in V_kappa!] is Pi_2.
Theorem: Sigma_2 compactness. Let A be a Sigma_2 set of
sentences of L. Then the following are equivalent:
1) A has a model.
2) For every a \subseteq A such that a \in V_kappa, a has a
model.
3) For every a \subseteq A such that a \in V_kappa, a has a
model which is an element of V_kappa.
This completes this letter. These theorems are not at all
evident. I will prove them in the next letter [or two].
Date: Wed, 7 Mar 2001 12:50:06 -0800 (PST)
Subject: C: letter 3
Randall,
Our current order of business is to prove the facts concerning
infinitary logic that I asserted at the end of letter C2. Our
approach will be as follows.
1) We shall see that a version of Konig's lemma holds in our
current context [with "the usual proof"].
2) It is well-known that the usual form of Konig's lemma is
closely related to the Godel completeness theorem. A similar
situation will obtain here and we shall prove the theorems on
completeness and compactness asserted at the end of letter C2
from the current version of Konig's lemma.
2. Let's rehearse some well-known definitions. A tree T is a
set |T| together with a partial-ordering, \leq_T such that the
predecessors of any x in T are well-ordered by \leq_T.
To avoid any ambiguity: \leq_T is reflexive.
Let T be a tree. Each x in |T| has an ordinal attached, its
level, which is the order-type of the set of y which are
strictly less than x in the tree.
I write level(alpha,T) for the set of points of T which appear
at level alpha.
3. Next I have to explain when a tree T is "a Delta_2 tree".
We require:
1) The underlying set of T is a Delta_2 subset of V_kappa. [So
from the standpoint of V_kappa, T may be a proper class.
2) The partial-ordering of T is Delta_2.
3) The height of T is at most kappa. For each alpha < kappa,
level(alpha, T) is an element of V_kappa. And the map which
sends alpha to level(alpha, T) is Delta_2.
(Remark: It follows that the map that sends alpha to the
tree consisting of the levels level(beta,T) for beta < alpha
is Delta_2(V_kappa).)
4. We can now formulate the version of Konig's lemma we will
be proving. But first, I should probably recall our standing
assumptions on kappa.
1) kappa is a limit cardinal of cofinality omega;
2) V_kappa is a model of ZC + Sigma_2-replacement + V = L.
Here is the version of Konig's lemma we will be proving.
Lemma 4. Let T be a Delta_2 tree. Suppose that for every alpha
< kappa, level(alpha, T) is non-empty. Then T has a branch of
order-type kappa.
[A branch is a maximal linearly ordered subset of T.]
Cf. Barwise op. cit. Chapter VIII, Theorem 7.2.
Lemma 4 will follow immediately from the fact that kappa has
cofinality omega and the following two claims;
Claim 1. Let alpha < kappa. Then there is an x at level alpha
in T such that for every beta > alpha, [with beta < kappa, of
course] x has a descendent at level beta in T.
Claim 2. Let x in T. We suppose that x has level alpha and
that for every beta with alpha < beta < kappa, x has a
descendent at level beta of the tree. Let beta_0 be given with
alpha < beta_0 < kappa. Then x has a descendent y at level
beta_0 with the following property:
For every gamma with beta_0 < gamma < kappa, y has a
descendent at level gamma in T.
[When I say, e,g,. that x has a descendent y at level beta in
T, I mean there is a y at level beta such that x \leq_T y.]
The proofs of 1 and 2 are quite similar and I shall content
myself with a proof of 2.
We are given x satisfying the hypotheses of claim 2. Towards a
contradiction, assume that the conclusion of the lemma fails
for some beta_0 > alpha.
Let Y be the set of descendants of x at level beta_0. By
assumption Y is non-empty.
Introduce a Sigma_2 relation S(a,b) thus;
a is in Y, b is an ordinal greater than beta_0 and a has no
descendants at level b.
Our assumptions imply that for every a in Y, there is a b such
that S(a,b).
Uniformize S to a Sigma_2 function F with domain Y.
Let gamma be an ordinal greater than every ordinal in the
range of F.
By assumption, x has a descendant at level gamma, say z. Let y
be the ancestor of z at level beta_0. Then y in Y, and gamma >
F(y). But this contradicts the definition of F since y has the
descendant z at level gamma.
This completes our proof of the variant of Konig's Lemma and
with it letter C3.
Date: Wed, 7 Mar 2001 18:01:01 -0800 (PST)
Subject: Letter C4
The goal of this letter is to use the variant of Konig's Lemma
proved in letter C3 to establish the theorems asserted at the
end of letter C2.
1.
Let L be one of the languages L_alpha introduced in letter
C2. Let S be the set of sentences of L. [From the standpoint
of V_kappa, S is a proper class.] Let X be a Sigma_2 subset of
S. We are going to associate to X a certain tree T(X). Roughly
speaking, models of X will correspond to branches of T(X).
T(X) will be a subtree of a certain universal tree, T*, which
we build first.
Work in V_kappa. We define a Delta_2 function, F, mapping
kappa to kappa as follows:
F(0) = 0.
The ordinals F(1), F(2), ... enumerate in increasing order the
lbfps less than kappa. [Implicit in this definition is the
fact that there are kappa lbfps less than kappa.]
We now describe the tree T*. The tree order will be inclusion.
Level 0 of the tree will consist of one member, the empty set.
Let alpha > 0. Let S_alpha consist of those sentences of L
which lie in V(F(alpha)). Then the alpha^{th} level of T*
consists of all maps of S_alpha into {0,1}.
This completes the definition of T*.
2.
We follow the usual conventions of thinking of 1 as "truth"
and 0 as "falsehood".
Very roughly, level alpha of T(X) will consist of those
elements of level alpha of T* which "respect the logical
connectives" and require those elements known to be in X at
stage F(alpha) to get truth value 1.
We turn to the precise requirements. So let alpha be given and
let f be in level alpha of T*. We describe precisely the
requirements that f must satisfy to be in level alpha of T(X).
If alpha = 0, then the empty set will be in the bottom level
of T(X). So assume from now on, that alpha > 0.
Let the Sigma^2 definition of X have the form (exists x)A(x,s)
where A is Pi_1.
Requirement 1: Suppose that s \in V(F(alpha), s is a sentence,
and for some x in V(F(alpha)) A(x,s).
Then f(s) = 1.
Requirement 2: [f behaves right on disjunctions.]
Suppose that s is the disjunction of the set of sentences A.
Suppose also that s \in S and s \in V(F(alpha)). Notice
that this entails that each member of A is in S \cap
V(F(alpha)),
(a) If f(s) = 1, then for some a in A, f(a) = 1.
(b) If f(s) = 0, then for all a in A, f(a) = 0.
Requirement 3: [f behaves right on negations.]
Let s be a sentence in S \cap V(F(alpha) and let t be the
negation of s. Then f(t) = 1 - f(s).
Requirement 4: [f behaves right on existential quantifiers.]
(a) Let s be a sentence in the domain of f of the form
"exists x psi(x)"
Let t be a closed term of L lying in V(F(alpha)).
Let s_1 be the sentence psi(t).
Then if f(s_1) = 1, f(s) = 1.
(b) Let s be a sentence in the domain of f of the form
"exists x psi(x)".
Let t_1 be the closed term \iota x psi(x) and let s_2 be the
sentence
"psi(t_1)".
Then if f(s) = 1, then f(s_2) = 1.
Requirement 5: [f behaves right on "=".]
(a). If s is a sentence of the form "t = t" where t is a closed
term, and s is in the domain of f, then f(s) = 1.
(b) Suppose that t_1 and t_2 are closed terms in V(F(alpha)).
If f("t_1 = t_2") = 1, then f("t_2 = t_1") = 1.
(c) Suppose that t_1, t_2, and t_3 are closed terms in
V(F(alpha)). Then if f("t_1 = t_2") = 1, and f("t_2 = t_3") = 1,
then f("t_1 = t_3") = 1.
(d) Suppose that t_1, t_2, t_3, t_4 are closed terms in
V(F(alpha)).
If f("t_1 = t_2") = 1, f("t_3 = t_4") = 1, and f("t_1 \in t_3") =
1, then f("t_2 \in t_4") = 1.
This completes our description of the tree T(X). Of course, we
have just "done the obvious thing".
It is evident that T(X) is a Delta_2 tree in the sense of letter C3.
3.
Recall that a branch through a tree such as T(X) is a maximal
linearly ordered subset that has order type kappa. So it has
elements on every level.
So if b is a branch through T(X), the union of b is a function
mapping S to {0,1} that gives each s in X the value 1 and respects
the various logical connectives.
If M is a model of X, then M determines a function h:S --> {0,1}
["compute the truth value of the sentence s in M"]. The
restriction of h to the various S_alpha's gives a branch through
T(X).
Conversely, if b is a branch through T(X), b determines a model of
X as follows.
First, we put an equivalence relation on the closed terms by
saying t_1 == t_2 iff the union of b gives "t_1 = t_2" value
1. The underlying set of M is the set of equivalence classes. We
define the other elements of the structure of M "according to b"
in an evident way. Because of the requirements imposed on T(X), it
is routine to check that a sentence is true in M iff the union of
b gives it the value 1. [The fact that L is Henkenized is key
here, of course.]
The various claims at the end of letter C2 are now pretty
evident. First, X has a model iff T(X) has a branch iff every
level of T(X) is non-empty. But this last formulation is clearly
Pi_2.
As for compactness, obviously, if X has a model, then so does
every bounded subset x of X which is in V_kappa.
In fact, such a bounded subset will be in the domain of some
member of the branch b that corresponds to the model [and
which has rank some bfp > 0. Moreover, by taking this rank
gamma sufficiently large, we can assume that the members of x
are witnessed to be in X by stage gamma. (This uses Sigma_2
replacement + Sigma_2 uniformization.) But this
member easily yields a model for x which is an element of
V_kappa.
Conversely, if every bounded subset of X has a model,
level(alpha,T(X)) is non-empty for every alpha < kappa. Hence by
Konig, T(X) has a branch, so X has a model.
The various claims made at the end of letter C2 have been
proved. This ends letter C4.
Date: Wed, 7 Mar 2001 22:54:39 -0800 (PST)
Subject: Letter C5
The main purpose of this [hopefully brief] letter is to
discuss what the compactness and completeness results proved
in the last two letters look like when formulated "internal to
our model N".
We have a model N of T_2 + "For no limit cardinal lambda is
L_lambda a model of T_2". As I have remarked previously, it
follows that there is a definable map from omega to OR, in N,
whose range is cofinal in the ordinals of N. We let the map
send i to gamma_i; we shall assume that the gamma_i's are
lbfps and that the map i --> gamma_i is strictly increasing.
There is no difficulty carrying out the definition of our
language L internal to N. Where we previously had, for
example, a constant \bar{alpha} for each alpha < kappa, we now
have such a constant for each ordinal alpha.
The collections of terms, sentences, etc. are proper classes
which are Delta_2.
If X is a Sigma_2 set of sentences of L, we can form the tree
T(X) much as before. It will once again be a Delta_2 tree.
Konig's lemma now takes the following form: If every level of
T(X) is non-empty then there is a definable branch through
T. The old proof goes through, mutatis mutandis, using in a
crucial way that there is a definable map that shows that OR
has cofinality omega.
Such a branch through T(X) yields a canonical model M of X. I
will make one small change in the definition of M. Each
equivalence class of closed terms has a least member with
respect to the canonical well-ordering of N. [Recall that N is
a model of V=L.] I will take these least members rather than
the equivalence classes themselves as the elements of the
underlying class of M. [In general, M will be given as a
proper class of the model N.]
If one is being truly pedantic, there are proper classes which
give;
(a) the underlying class of M;
(b) The map from the class of closed terms of L onto M;
(c) The class of sentences of L which are true.
This gives us a quite satisfactory grip on M.
The completeness theorem holds in the form that the class of
Godel numbers [as Sigma_2 subsets of the class of sentences S]
of X's that have models [in the sense that T(X) has a branch]
is Pi^2. All that really matters is that this is a definable
class in N. The precise hierarchy calculation is unimportant.
The compactness theorem goes through as before: X "has a
model" [in the sense that T(X) has a branch] iff every subset x
of X has a set-model.
There is one small point in the proof of this that I slurred
over in the last letter. Let x be a subset of X. Then using
Sigma_2-replacement one sees that there is some stage alpha
[which is an lbfp] at which all the Sigma_2 facts that show
each member of x actually is in X have witnesses in
V(alpha). This is needed to get a model of x from an
appropriate node of the tree T(X).
This completes my discussion of the problem of internalizing
the results of Letters C3 and C4.
End of letter C5.
Date: Thu, 8 Mar 2001 12:38:42 -0800 (PST)
Subject: Letter C6
This letter starts the main thrust of the argument. Let me
outline how it will go.
We have our model N of T_2 whose properties I have just
recalled in letter C5. Our construction will take place
"inside N".
The main work is a length omega construction. One of the
things that we will be building, step by step, is a series of
Sigma_2 theories T_0, T_1, ... [There is a slight conflict
here with our previous use of T_2. I trust the context will
disambiguate things.]
T_i will be in the language L_i.
This series of theories is increasing. Its union T* need not
be Sigma_2, but it will certainly be a class of N. It will be
evident from our construction that T* is complete. Moreover,
it will be true for the limit theory that the xi_alpha's are
indiscernibles. [T* will be in the language L_omega.]
We will build the model M* according to the blueprint given by
T* but using as generating indiscernibles the xi_n for n in Z
[Here Z is the set of all integers both positive and negative
as computed in N.] M* has an evident automorphism which sends
xi_i to xi_{i+1} for any i. M* will be a model of a moderately
strong set-theory and the xi_n's will be lbfps in that model,
so we will get a model Q of NFU in the usual way.
It will be evident from our construction that the strongly
cantorian ordinals of Q are canonically identified with the
ordinals of N. In the usual way, this plus the fact that Q is
given by a class of N will ensure that the crucial axioms of
counting and strongly Cantorian full selection hold in Q so
that Q is indeed a model of NFU*.
2. The next order of business is to describe the theory T_0
and prove it has a model. [I always mean by this that the
relevant tree T(T_0) has a branch.] Most of the axioms of T_0
are routine, but there is at least one tricky one that I will
call attention to when we get to it.
Axiom group 1: Axioms of set-theory
We can find finitely many axioms in the usual language of
set-theory [first-order logic is a subset of L!] that express:
(a) Maclane set-theory;
(b) KP;
(c) V=L;
(d) There are arbitrarily large bfps.
Axiom group 2: Axioms on the \bar{alpha}'s.
For each alpha in OR, there is an axiom that says:
For all x [x is in \bar{alpha} iff
\bigvee {x = \bar{beta} | beta < alpha}
[This is the usual way one pins down the meaning of \bar{alpha}
in infinitary logic.]
Axiom group 3: Axioms on the xi_alpha's.
For each ordinal alpha, there is an axiom:
xi_alpha is an lbfp.
For each pair of ordinals, alpha, beta with alpha < beta,
there is an axiom:
xi_alpha \in xi_beta
Axiom group 4: Axioms on the h_{i,alpha}'s.
(a) h_{i,alpha} is an ordinal.
(b) h_{i,alpha} <= xi_alpha.
There are no instances of group 4 axioms in T_0. But if 0 < n,
there will be the appropriate axioms of this type for each i < n.
Axiom group 5: The least ordinal principle
The purpose of these axioms is to enforce, to the extent that
we can, that the models of T_0 are well-founded.
Let X be a set of closed terms of L. There will be one
instance of the axiom for each such X that meets the following
finiteness constraint:
There is a finite subset of omega, A, and a
finite subset of OR, B such that:
(a) The h-support of any x in X is a subset of A.
(b) The xi-support of any x in X is a subset of B.
Our axiom will have the form "If H(X) then C(X)". We describe
these two components in turn:
H(X) will express that all the members of X are ordinals:
\bigand {x is an ordinal | x \in X}
C(X) will express that some member of X is least:
To start, let [for x in X], D(x,X) express that x is least in
X:
\bigand { x <= y | y in X}
Then C(X) is just the obvious infinite disjunction:
\bigvee {D(x,X) | x \in X}
This completes our description of the theory T_0.
It is obviously Sigma^2. In fact, it is obviously Delta_2.
I say that T_0 is consistent [in the usual meaning we have
been giving to such phrases that the corresponding tree T(T_0)
has a branch through it].
For this, its enough, by compactness, to check that every set
of axioms of T_0 has a model. But this is easy. For any set,
a, of axioms of T_0, it is easy to whip up a model whose
underlying set is L_lambda, where lambda = F(gamma^+). Here F
is the function from letter C4 that enumerates the lbfps;
gamma^+ is the least cardinal greater than gamma; and gamma
\in OR is chosen sufficiently large compared to a.
This is a good place to pause and I will end letter C6 here.
Date: Thu, 8 Mar 2001 14:37:42 -0800 (PST)
Subject: Letter C7
Randall,
This letter handles a number of minor points that have come
up. I will return to the main thrust of the argument for Phase
C in the next letter.
1. I've been somewhat sloppy about the formal details of our
length omega constructions. [One occurred in phase B, and one
will be about to be presented in phase C.]
What's going on is the following: There is some inductive
condition I(x,n). There is some next-step condition S(x,y,n).
We have the following holding in our model N:
1) There is an x such that I(x,0).
2) For every n in omega, for every x:
If I(x,n) there is a y such that S(x,y,n) and I(y, n+1).
In that case there is a class of N which is a function f with
domain omega such that:
1) For all n, I(f(n),n);
2) For all n, S(f(n), f(n+1), n).
Roughly, one takes f(0) to be the L-least x such that
I(x,0). One takes f(n+1) to be the L-least y such that
S(f(n),y,n) and I(y, n+1).
I haven't been too explicit about spelling out I and S
precisely, but they are there in the background and would need
to be fully spelled out in a completely formal proof.
This ends my series of brief remarks and with it letter C7.
Date: Tue, 13 Mar 2001 22:08:46 -0800 (PST)
Subject: Letter C8
So lets start the inductive construction:
For each stage n in omega, we are going to define, by
induction on n:
(a) A consistent Sigma_2-theory T_n in the language L_n.
We will have T_n extends T_{n-1} if n > 0.
Really, we are inductively choosing the Godel number of T_n,
which is a set. T_n itself, of course, is a proper class.
(b) An ordinal alpha_n.
alpha_0 will be 0. If n > 0, then alpha_n will be a lbfp which
is greater than alpha_{n-1} and gamma_n. [The gamma's are our
standard sequence for cofinalizing OR.]
(c) A function f_n whose domain is the set of all sentences s
of the language L_n such that:
(1) s \in V(alpha_n);
(2) If xi_alpha appears in s, then alpha < n.
The range of f_n will be included in {0,1}.
Thus f_0 will be the empty function. If f_n(s) = 1, s will be
an axiom of T_n; if f_n(s) = 0, \neg s will be an axiom of T_n
We will require that T_n contains the following
indiscernibility axioms:
Let s be in the domain of f_n. Let
be an increasing n-tuple of ordinals.
Let s' be obtained from s by replacing xi_i by xi_{alpha_i}
uniformly throughout s. [This has to be explicated by a
straighforward inductive definition.] Then
"s iff s' "
is an axiom of T_n.
In order to keep things rolling we need to inductively
maintain the following property of the T_n's:
Let lambda_1 and lambda_2 be lbfps with alpha_n < lambda_1 <
lambda_2.
Let t_i be the intersection of T_n with V(lambda_i) for i =
1,2.
(Here we are construing a theory as a collection of sentences:
its axioms.)
Let M be a set model of t_2. Let f: lambda_1 --> lambda_2 be
order preserving.
f determines a map f* of the terms and formulas of L_n \cap
V(lambda_1) into the terms and formulas of L_n \cap
V(lambda_2) as follows:
The map is defined inductively. For most clauses in the
inductive definition of terms and formulas we "do the obvious
thing". f*( xi_alpha) = xi_{f(alpha)}.
f*(h_{n,alpha}) = h_{n,f(alpha)}.
We convert the model M into a premodel M^\star for the
language L_n \cap V(lambda_1) as follows:
The meanings of \in and = do not change. Nor do the meanings
of the \bar{alpha}'s. For a general closed term t, the meaning
of t in M^\star is the meaning of f*(t) in M.
Our key assumption [the thinning assumption] is that M^\star
is a model of t_1.
We will also have to maintain inductively that T_n "is
consistent". [That is, T(T_n) has a branch of order type
OR. By Konig this is equivalent to all the levels of T(T_n)
being non-empty which can be expressed "inside N".]
Here is a rough outline of the passage from T_n to T_{n+1}.
1) We will examine the "Cantorian terms of rank at most
(alpha_{n}, n)". [The phrase in quotes will be defined
presently.]
We will separate these into convergent and potentially
divergent terms. We will take action to make the potentially
divergent terms divergent. The result of our actions will be a
consistent theory, T_{n,1} in the language L_n.
2) We will add some new axioms concerning the
h_{n,alpha}'s. This will require the transition from the
language L_n to L_{n+1}. The axioms will ensure that the
divergent Cantorian terms will not be strongly Cantorian in
the final model. The resulting theory is T_{n,2}.
3) At this stage, we will be able to choose alpha_{n+1}. It
will be evident that all the convergent Cantorian terms will
have denotations below alpha_{n+1}.
4) We next add indiscernibility sentences for n+1-tuples of
xi_alpha's. The resulting theory is T_{n,3}. In checking that
T_{n,3} is consistent, use will be made of our "thinning
assumption" and Erdos-Rado.
5) Finally, we will decide the truth or falsity of any
sentence of rank at most (alpha_{n+1}, n+1).
Adding the sentences which reflect our decisions will give us
T_{n+1}. Of course, we must be sure that T_{n+1} is consistent
and satisfies our "thinning assumption".
This is a good place to end letter C8. In the next letter[s]
we will carry out our inductive construction in detail.
Date: Wed, 14 Mar 2001 17:38:12 -0800 (PST)
Subject: Letter C9
[There is no letter C9 in the current version of this series
of letters.]
Date: Wed, 14 Mar 2001 17:39:24 -0800 (PST)
Subject: Letter C10
Randall,
Before I start discussing the transition from T_n to T_{n+1},
I wanted to record another claim that we have to inductively
maintain.
As we increase the language, new instances of axiom
groups 4 and 5 will arise. They are assumed to be added to the
language.
So we are given [a Godel number for] the theory T_n, and we
have to define T_{n+1}.
We first describe a certain set of terms of the language L_n,
W_0.
W_0 will consist of all closed terms in V(alpha_n) whose
xi-support is included in {0, ... , n-2}. [If n <= 1, construe
{0, ..., n-2} as the empty set.].
If t \in W_0, let t* be the term obtained by replacing xi_i by
xi_{i+1} throughout t [for 0 \leq i < n-1]. [And similarly for
the h terms that are subterms of t: i.e, replace h_{j,i} by
h_{j,i+1}.]
This whole phase is pretty vacuous for n=0. W_0 is then the
empty set.
T_n will decide the truth value of the sentence t=t*. If it
decides that it is true, we say that t is "Cantorian". Let W_1
be the set of Cantorian terms t from W_0 such that T_n
believes that "t is an ordinal".
We put an equivalence relation == on W_1 as follows: t_1 ==
t_2 iff T_n decides "t_1 = t_2". Let W_2 be the set of
equivalence classes of W_1 under this equivalence relation.
We linearly order W_2 as follows: The equivalence class of t_1
is <* the equivalence class of t_2 if T_n decides t_1 < t_2
[using the usual ordering of ordinals]. It is indeed clear
that this gives a linear ordering of equivalence classes.
In fact, this gives a well-ordering of equivalence classes. We
leave the detailed proof of this to the reader. The essential
point is the "least ordinal principle" which is part of the
axioms of T_n.
We say that a t \in W_1 is divergent if the following theory
is consistent:
(a) The axioms of T_n;
(b) For each ordinal gamma, an axiom asserting
"t > \bar{gamma}.
It is evident that the theory just described is Sigma_2, since
T_n is.
So working within N, we can tell which terms are divergent.
For all we know there could be no divergent terms. But at
least the following claims are clear:
(a) Whether or not a term t is divergent depends only on the
equivalence class of t.
(b) If t_1 and t_2 are elements of W_1 and t_1 is divergent,
and the equivalence class of t_1 is <* the equivalence class
of t_2, then t_2 is divergent.
If there are no divergent terms, we set T_{n,1} = T_n. If
there are divergent terms, we pick an equivalence class of
such divergent terms which is <* minimal. We then pick a t in
this equivalence class [using the canonical well-ordering that
exists in the model N of V=L]. We then get T_{n,1} from T_n by
adjoining the following list of axioms:
If gamma is an ordinal, we have the axiom "t > \bar{gamma}".
Since t is divergent, the theory T_{n,1} is consistent.
We need to check that T_{n,1} has the thinning property. When
I introduced T_0, I should have assigned the reader the
following easy exercise:
T_0 has the thinning property. The proof is not difficult. The
only axiom groups that need any thought are axiom groups 3, 4
and 5.
We shall suppose that [as part of our inductive hypothesis] we
know that T_n has the thinning property. We also will have an
indiscernibility property that says [roughly] that all
increasing n-tuples of xi's look alike. Using this, it is easy
to see that T_{n,1} has the thinning property.
We next take steps to insure that the term t [our minimal
divergent term] is not strongly Cantorian. In doing this we
will define a new theory T_{n,2} in the language L_{n+1}.
The axioms of T_{n,2} consist of the following:
(a) The axioms of T_{n,1}.
(b) The new axioms of axiom group 4 [cf. letter C6] that apply
to terms of the form h_{n,alpha}.
(c) The new instances of Axiom group 5 ["the least ordinal
principle"] that occur since we have enlarged the language.
(d) For each pair of ordinals alpha and beta with alpha <
beta, an axiom that asserts that
h_{n,_alpha} < h_{n,beta}.
(e) Axioms of the following group will only be added if there
is a divergent term in W_1 [so that t is defined].
Let delta_0 < delta_1 < ... < delta_{n-1} be ordinals. Let
t[\vec{delta}] be the closed term obtained from t by replacing
xi_i by xi_{delta_i} throughout [and similarly for any subterm
of t which is an h term.]. Then there will be an axiom
h_{n,delta_0}) < t[\vec{delta}].
Claim: T_{n,2} is consistent.
Proof: Fix a lbfp beta > alpha_n. It suffices to show that
T_{n,2} \cap V(beta) has a model M* [for any such beta].
Let M be a model of T_{n,1} \cap V(beta). We are going to
enrich M so as to make it a model of T_{n,2} \cap V(beta).
The first thing is to give the meaning of the terns
h_{n,delta} (for delta < beta). It will denote the same
element of M that \bar{delta} does.
Many new closed terms of L_{n+1} will be elements of
V(beta). We have to assign a meaning to each such closed
term t. We will do this by induction on the rank of t. What we
will do is assign a closed term of L_n \cap V(beta) for it to
shadow. At the same time, we will be associating to each
formula of L_{n+1} a formula of L_n. It is our intention that
for the model M*, the formula of L_{n+1} and its shadow in L_n
will have the same meaning.
Let \sh{s} be the shadow of s. Here is the inductive
definition:
\sh{\bar{alpha} = \bar{alpha};
\sh{v_alpha} = v_alpha;
\sh{xi_alpha} = {xi_alpha};
If i < n,
\sh{h_{i,alpha}} = h_{i,alpha};
\sh{h_{n,alpha}} = \bar{alpha};
\sh{ \iota x psi(x)} = \iota x \sh{psi(x)};
\sh{ \neg psi} = \neg \sh{psi};
\sh{t_1 = t_2} =
\sh{t_1} = \sh{t_2};
\sh{t_1 \in t_2} =
\sh{t_1} \in \sh{t_2;
\sh{\exists x psi} =
\exists x \sh{psi};
Finally we have to handle infinitary disjunctions.
\sh{ \bigvee S} = \bigvee S*
where S* = {\sh{s} | s \in S}.
This completes our description of M*. Note that for every
closed term of M* there is a closed term of M with the same
denotation.
Note that by the key new axiom of T_{n,1} the value of t is
greater than the values of the h_{n,alpha}'s.
It remains to see that M* is a model of T_{n,2} \cap
V(beta). But this is straightforward to check.
[Our first comment is helpful in verifying the axioms of group
(c) and our second in verifying the axioms of group (e).
It is easy to check that T_{n,2} has the thinning property.
Our next task is to define alpha_{n+1}.
Let t be a term in W_1 that is not divergent. Let T_n[t] be
the theory in the language L_n obtained from T_n by adding the
axioms t > \bar{alpha} for each alpha in OR. By assumption,
T_n[t] is inconsistent. Using Sigma_2-replacement, it is easy
to see:
There is a single ordinal delta_n which is a lbfp such that
for any term t in W_1 which is not divergent,
T_n[t] \cap V(delta_n) is inconsistent.
We take alpha_{n+1} to be the least lbfp which is greater than
alpha_n, delta_n, and gamma_n. [The gamma_n's are our standard
sequence that cofinalizes OR in N.]
Our next theory will make sure that all the n+1-tuples of xi's
look alike.
T_{n,3} is obtained from T_{n,2} by adding the following
axioms:
For each sentence s whose xi-support is included in {0,...,n}
and each order preserving map f:{0,...,n} --> OR, there will
be an axiom A(s,f) defined as follows:
Let f* be the map on terms and formulas induced by f. [Recall
that f* acts on h terms in a non-trivial fashion.]
Then A(s,f) is the sentence
s iff f*(s).
Claim: T_{n,3} is consistent.
Let beta be a lbfp greater than alpha_{n+1}. It's enough to
construct a model of T_{n,3} \cap V(beta).
Let gamma be a lbfp greater than beta, and let M be a model of
T_{n,2} \cap V(gamma).
By Erdos-Rado, we can find a subset Y of gamma of order-type
beta such that for any s in V(beta) with xi-support included
in {0, ..., n} and any order preserving map f: {0, ..., n} -->
Y, the truth value of f*(s) has the same value.
Let g: beta --> Y be the obvious order isomorphism. We define
a model M* by giving the value of the closed term t in L_{n+1}
\cap V(beta) in M* to be the value of g*(t) in M.
Since T_{n,2} has the thinning property, M* is a model of
T_{n,2}. But by choice of Y, it is evident that M* satisfies
the additional axioms we added to T_{n,2} to make T_{n,3}. {At
least those instances lying in V(beta).}
The proof of the claim is complete.
Claim: T_{n,3} has the thinning property.
Proof: Exercise. Left to the reader.
We finally are in a position to define T_{n+1}. First let's
introduce a set of sentences S_{n+1}:
S_{n+1} consists of all sentences of L_{n+1} which lie in
V(alpha_{n+1}) and have xi-support included in {0, ..., n}.
To each f: S_{n+1} --> {0,1} we introduce a sentence A(f) as
follows:
A(f) is the infinite conjunction
\bigand {s^{f(s)} | s \in S_{n+1}}
Here if s is a sentence s^0 is \neg s, and s^1 is s.
Claim: For some f, T_{n,3) + A(f) is consistent.
Proof: Take a branch through T(T_{n,3}) and use the f it
defines.
Let f be least such that the claim is true.
T_{n+1} = T_n together with the axioms s^{f(s)} for s \in
S_{n+1}.
Claim: T_{n+1} has the thinning property.
Proof: Easy and left to the reader. The axioms we added to
make T_{n,3} play a crucial role here.
This completes our length omega construction, and with it
letter C10.
Date: Wed, 14 Mar 2001 17:40:11 -0800 (PST)
Subject: Letter C11
We are almost done.
Let T_omega be the union of the T_n's. Our construction
ensures that T_omega is a complete theory. That is, for any
sentence s of L_omega, there is a sentence s' such that:
1) s iff s' is an axiom of T_omega;
2) One of s', \neg s' is an axiom of T_omega.
[Let the xi-support of s, listed in increasing order, be
{alpha_0, ..., alpha_{n-1}}. Then roughly speaking, s' is
obtained from s by replacing xi_{alpha_i} by xi_i.]
In the obvious sense, the xi_alphas are fully indiscernible in
T_omega.
We use T_omega as an EM-blueprint, and construct a model M*
generated by indiscernibles xi_i (for i in Z) [Here Z is the
full ring of integers (both positive, negative, and zero) as
computed in our model N.]
There is an obvious automorphism of M [that moves xi_i to
xi_{i+1}].
The actions that we have taken during the course of the
construction ensure that the ordinals of M* such that they and
their predecessors are fixed by j are just those denoted by
\bar{alpha} for some ordinal alpha in N.
So M* yields a model of NFU* in the usual way.
~~