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.