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.