From solovay@math.berkeley.edu Sat Apr 15 16:00 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA03546; Sat, 15 Apr 1995 15:59:59 -0600 Return-Path: Received: by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id OAA23185; Sat, 15 Apr 1995 14:55:33 -0700 Date: Sat, 15 Apr 1995 14:55:33 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Message-Id: <199504152155.OAA23185@math.berkeley.edu> To: holmes@catseye.idbsu.edu Subject: First of a series of letters Status: RO Randall, It is raining here in Oakland, and so I write on my Powerbook [whose connection with the internet is somewhat flaky.] Partly as a consequence of this flakiness, I will be composing a series of short letters rather than one jumbo letter. The first installment concerns the following question which arose during my musings recently about proving the consistency of NFU. Of course, thanks to Specker, we know that NF refutes the axiom of choice. But does it rule out the assertion that every well-founded set [one arising from a well-founded extensional relation] is constructible? I couldn't see that it does. More to come. --Bob From solovay@math.berkeley.edu Sat Apr 15 17:21 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA03577; Sat, 15 Apr 1995 17:21:13 -0600 Return-Path: Received: by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id QAA24218; Sat, 15 Apr 1995 16:16:47 -0700 Date: Sat, 15 Apr 1995 16:16:47 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Message-Id: <199504152316.QAA24218@math.berkeley.edu> To: holmes@catseye.idbsu.edu Subject: An example Status: RO I mentioned in a previous letter that I had an example of a set of sentences Sigma which satisfied your suggested conditions but such that the resulting term model did not satisfy the axiom of counting. My original example employed both an inaccessible cardinal and the fine structure technology of Jensen. I've since realized that the example can be simplified so as not to use the Jensen technology. The question under consideration is an arithmetic one, so we may wlog assume that V=L. {Though I'm not really using this assumption.] Let alpha be an inaccessible cardinal. We are going to choose an ultrafilter U on alpha. Using this U and its powers and the structure L_alpha will generate a set of sentences Sigma. We have to insure that there will be a definable function f from alpha to omega which is non-constant mod U. This will, as in the previous example, insure that the term model generated by U and the definable functions of the structure L_alpha will not satisfy counting. The function f may be described as follows. Let beta be an ordinal. Then beta can be written as a sum lambda + n, where lambda is 0 or a limit ordinal, and n is a non-negative integer. Then f(beta) will be this n. It is routine to construct a uniform ultrafilter U on alpha such that f is non-constant mod U. This completes the description of the revised construction. As ever, Bob From solovay@math.berkeley.edu Sat Apr 15 18:02 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA03606; Sat, 15 Apr 1995 18:02:48 -0600 Return-Path: Received: by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id QAA24836; Sat, 15 Apr 1995 16:58:22 -0700 Date: Sat, 15 Apr 1995 16:58:22 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Message-Id: <199504152358.QAA24836@math.berkeley.edu> To: holmes@catseye.idbsu.edu Subject: Some large cardinal properties Status: RO Randall, This letter just defines some concepts that I need to state the results in my following letter on upper bounds on the consistency strength of some variants of NFU. Here are some large cardinal properties arranged in order of strictly decreasing consistency strength. The ones that occur after 0# are all compatible with V=L. 1) strongly compact 2) measurable 3) 0# exists 4) Erdos 5) completely ineffable 6) ineffable 7) weakly compact 8) Mahlo 9) inaccessible The ones that I need for the next letter are 4) and 5). I should caution that I am not sure that I am using the term "completely ineffable" as it is used in the literature. In the letter that follows I am using it in the sense to be given below. The definition of an Erdos cardinal is somewhat delicate. Instead I describe a property such that the least cardinal with that property is the least Erdos cardinal. Here is the property in question. Whenever A is a structure [in a countable similarity type] with underlying set the cardinal kappa, then there is a set of indiscernibles for the structure A of order type omega. The definition of "completely ineffable" is in terms of a certain two person game. In this game, player II plays subsets of kappa, A_0, A_1, ... These are to be a decreasing sequence of subsets each of cardinality kappa. If ever player II cannot play a legal move, then he loses; if he never fails to play a legal move, he wins the game. To start things off, A_{-1} is the set of limit ordinals less than kappa. Player I has two sorts of moves he can play. 1) He can play an array of length kappa of subsets of kappa. To respond II plays a set which is [modulo sets of cardinality less than kappa] either contained in or disjoint from each set of the array. 2) I can play a regressive function f on A_{n-1}. That is, f(beta) < beta for any beta in A_{n-1}. II must play a set A_n on which f is constant. This completes the description of the game. If II wins, kappa is completely ineffable. As an instructive exercise show that if kappa is measurable, then kappa is completely ineffable. As ever, Bob From solovay@math.berkeley.edu Sat Apr 15 18:11 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA03620; Sat, 15 Apr 1995 18:11:53 -0600 Return-Path: Received: by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id RAA24929; Sat, 15 Apr 1995 17:07:26 -0700 Date: Sat, 15 Apr 1995 17:07:26 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Message-Id: <199504160007.RAA24929@math.berkeley.edu> To: holmes@catseye.idbsu.edu Subject: Some upper bounds on consistency strength Status: RO We will be considering two extensions of NFU: NFUA: NFU + Infinity + Choice plus Every Cantorian set is strongly cantorian. NFUB: NFUA + the axiom that seys every definable subset of the strongly cantorian well-founded sets is the intersection of the well-founded strongly cantorian sets with some set of the model. Result 1: The consistency of each of these theories is provable in Zermelo set theory plus "There is a completely ineffable cardinal". Result 2: Suppose there is an Erdos cardinal. Then there is an inaccessible cardinal gamma and a model N of NFUB such that the strongly Cantorian sets of this model are isomorphic to V_gamma. [gamma will in fact be completely ineffable and hence weakly compact]. It is interesting to note that I can't get a model of NFUA from any assumption that doesn't also yield a model of NFUB. The model of NFUA that I get in Result 1 is countable, but its strongly Cantorian ordinals are well-ordered. As ever, Bob From solovay@math.berkeley.edu Sun Apr 16 17:27 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA03928; Sun, 16 Apr 1995 17:27:20 -0600 Return-Path: Received: by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id QAA07568; Sun, 16 Apr 1995 16:22:53 -0700 Date: Sun, 16 Apr 1995 16:22:53 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Message-Id: <199504162322.QAA07568@math.berkeley.edu> To: holmes@catseye.idbsu.edu Subject: Lower bounds Status: RO Here is a theorem I am willing to claim: NFUA proves the consistency of "ZFC + There is an inaccessible limit of inaccessibles". It's not quite clear what the best I can get is. I definitely haven't yet gotten the consistency of "ZFC + There is a Mahlo cardinal". But I'm still trying. The results claimed contradict, of course, your claim that NFUA is equiconsistent with ZFC [unless ZFC is inconsistent]. I will continue to think about this but this is the last letter I will post until I get some reaction from you. --Bob From solovay@math.berkeley.edu Wed Apr 12 13:48 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA03920; Wed, 12 Apr 1995 13:48:05 -0600 Return-Path: Received: by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id MAA04011; Wed, 12 Apr 1995 12:44:03 -0700 Date: Wed, 12 Apr 1995 12:44:03 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Message-Id: <199504121944.MAA04011@math.berkeley.edu> To: holmes@catseye.idbsu.edu Cc: T.Forster@pmms.cam.ac.uk, holmes@catseye.idbsu.edu In-Reply-To: Randall Holmes's message of Wed, 12 Apr 1995 03:41:37 -0600 <199504120938.CAA21877@math.berkeley.edu> Subject: From Randall Holmes Status: RO Dear Randall, 1. You write: The requirement for a model of the axiom of counting is not that each ordinal be standard (sorry, I mean each natural number there) but that each natural number be fixed by the automorphism. Reply: I am **well** aware of this; I explicitly indicated a natural number moved by the automorphism. I will discuss this point again later in this letter. 2. I can now prove a bit more than I asserted in my previous letter. I asserted there that it seemed unlikely that the conditons you imposed on Sigma sufficed to get a model of the Counting axiom [much less the Cantorian axiom]. I can now [assuming an inaccessible cardinal] produce a specific example of a term-model constructed from a Sigma meeting your requirements that does not satisfy the axiom of counting. I will not include a proof of this latter result in this letter, since it involves ideas from Jensen's work on the fine structure of L with which you may not bew familiar. 3. You say that you are fairly certain that the model below an inaccessible with ultrafilters is correct. I **know for certain** that it is not. I will try to convey the proof once again in the hope that this time I will supply sufficient detail to convince you. Please read what I am writing. I am getting the feeling that I am wasting my time in writing to you since you don't read carefully and **think** about what I send. 4. So lets start the discussion of the model "below an inaccessible". alpha is a strongly inaccessible cardinal fixed once for all. We fix an ultrafilter U on alpha, that gives each bounded subset of alpha measure zero. [I am taking the von Neumann approach where each cardinal is an ordinal and each ordinal is the set of all smaller ordinals.] 5. I will sketch an alternate construction of the ultrafilters U_n [for n in omega]. It really is completely equivalent to what you do [though I shall not stop to prove this]. But the approach I will follow is much easier to compute with. So I need first the notion of the cartesian product of two ultrafilters. Suppose that F and G are ultrafilters on sets X and Y respectively. I am going to define an ultrafilter F \cross G which will live on the cartesian product set X \cross Y. Let then A be a subset of X \cross Y. Let f be the characteristic function of A. If we integrate f with respect to its second variable [using G], we get a 2-valued function on X, say f'. If we integrate f' [using F] we get a number in {0,1}. Put A in F \cross G iff the number is 1. This is a standard construction in the theory of ultrafilters. I note only that the order of integration is important. 3. We can now define the U_n's. U_1 is the isomorphic copy of U obtained using the obvious isomorphism of alpha with alpha^1. U_{n+1} is the isomorphic copy of U_n \cross U_1 using the obvious isomprphism [given by concatentation] of alpha^n \cross alpha with alpha^{n+1}. It is easy to see that these U_n's have the various desired properties. In particular, they satisfy the sentences imposed in Sigma. 4. We can form the limit ultraproduct construction [using all the functions from alpha^Z to V_alpha of finite support] as outlined in your paper. To show that the axiom of counting fails in the model, it suffices to find an integer of the model moved by the automorphism j. But this is easy to do. Let F be a map from alpha to omega that is non-constant mod U. Let F_0 be the map of alpha^Z to omega which sends a sequence s to F(s(0)). Similarly, let F_1 be the analgous map that sends the sequence s to F(s(1)). Then the automorphism j sends the equivalence class of F_0 to the equivalence class of F_1. It only remains to see that these equivalence classes are unequal. This amounts to seeing that the U_2 measure of the set of all pairs with F(gamma_0) <> F(gamma_1) is 1. But this is immediate from the way that U_2 was defined and the fact that F is unequal [mod U] to a constant function. As ever, Bob Solovay who has not forgotten **everything** that he learned in his former incarnation as logician. From solovay@math.berkeley.edu Mon Apr 17 12:20 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA04726; Mon, 17 Apr 1995 12:20:14 -0600 Return-Path: Received: by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id LAA23741; Mon, 17 Apr 1995 11:15:45 -0700 Date: Mon, 17 Apr 1995 11:15:45 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Message-Id: <199504171815.LAA23741@math.berkeley.edu> To: holmes@catseye.idbsu.edu Cc: holmes@catseye.idbsu.edu In-Reply-To: Randall Holmes's message of Mon, 17 Apr 1995 11:26:22 -0600 <199504171721.KAA21538@math.berkeley.edu> Subject: Lower bounds Status: RO Dear Randall, You write: I will say that it looks to me as if your claim that my model of NFUA using an inaccessible doesn't work springs from a misunderstanding of the way in which the model is constructed. What I would like to do (and will start doing unless you object) is to go through the construction of a model of NFUA given an inaccessible in detail in Reply: This sounds like a fine way to proceed. I don't have a reference for "there is a completely ineffable cardinal below a measurable, though I think its well-known. I proved it by reconstructing the proofs of the following results: Theorem(Silver?) There is an Erdos cardinal less than the first measurable. Theorem(Silver) The least Erdos cardinal, if it exists, is Erdos in L. Theorem(???) There are a stationary set of completely ineffable cardinals below the first Erdos cardinal. I know a reference for the second theorem [as well as its proof.] The first theorem is really easy. As for the third, I cooked up a proof, but I suspect that it's in whatever paper the concept is first introduced in. [I don't recall when or where this paper appeared or by whom the paper was done.] As ever, Bob From holmes Mon Apr 17 12:26:50 1995 To: solovay@math.berkeley.edu Subject: Various Status: RO Dear Bob: I must apologize! You are absolutely right in your objections to the Refinement of Construction 2 as a way to construct models of NFU with even the Axiom of Counting! It isn't that I haven't been reading what _you_ wrote carefully; I haven't been reading what _I_ wrote myself carefully! For I do not claim in the paper that the Refinement of Construction 2 gives models of the Axiom of Counting; all I claim is that (in the case \beth{\alpha} = \alpha, which I will assume from here on out) any ordinal greater than all standard ordinals is moved upward by the automorphism (in the model of NFU resulting, T{\alpha} < \alpha unless \alpha is bounded by a standard ordinal). This is a technically very useful but not very strong property. I knew perfectly well when I was writing this that this did not give models of Counting; to see how I get models of Counting (or \beta strongly cantorian for any fixed \beta < \alpha) see Construction 3 (which I will summarize in a following note, jut to get it completely clear in my head!). The construction of a model of NFUA using an inaccessible (which I still think is possible) is not found in this paper. I'm really sorry about this; I definitely must have appeared (and was being) pig-headed, because I was not remembering what I had done correctly! More stuff follows (an account of Construction 3) but I want to send this off now since we seem to be talking in real time and I want to clear the air of smoke a bit and get down to stating things correctly! I shouldn't have tried to discuss any of this while attending the conferences in Europe, I think; my mind was largely elsewhere :-( --Randall From holmes Mon Apr 17 14:11:48 1995 To: solovay@math.berkeley.edu Subject: Construction 3 Status: RO Dear Bob, Now, hopefully, you are talking to the real Randall Holmes with brain completely engaged :-) Topic 1: Modelling counting (not yet NFUA!) I am going to describe the basic construction of a model of NFU with a certain standard infinite cardinal \beta (you may think of it as \omega, so that this will be a model of Counting, but I will be general, since generality is cheap here) strongly cantorian. It is sufficient to build a model with automorphism in which each ordinal less than \beta (and \beta itself) is fixed by the automorphism. Choose a cardinal \alpha greater than each iterated exponential of \beta (so that the Erdos-Rado theorem can be used). Functions from \alpha to \beta can be coded by elements of \alpha; clearly, so can finite sets of such functions. Consider, for each function f from \alpha to \beta, the set C_f of all codes of finite sets of maps from \alpha to \beta which contain f. The collection of C_f's is a filter on \alpha which can be extended to an ultrafilter C. C "describes" the code of a "finite set" of maps \alpha -> \beta which contains all standard such maps, in the ultrafilter model constructed using C. This "finite set" of functions induces a partition of \alpha into \beta pieces, which has a "homogeneous set" H. We use this "homogeneous set" to define a sequence of ultrafilters U_i on [\alpha]^i in the real world: U_i will contain all standard finite sets of subsets of \alpha of size i whose analogues in the model built with C contain all subsets of H with i elements. The model can be defined in terms of the U_i's as in the earlier constructions. The model contains \beta_k's indexed by integers k: U_i tells us which sets contain each sequence of i successive \beta_k's; the model elements are exactly the images under standard functions of finite sequences of successive \beta_k's. Any ordinal less than \beta in this model is the image of a finite sequence of n successive \beta_k's under some standard function \alpha^n -> \beta. Now the set H in the model built using C was homogeneous with respect to the partition induced by this map (and every similar standard map), so the images of any sequence of n successive \beta_k's remains the same when the indexes of the \beta_k's are incremented; any ordinal less than \beta is fixed by the automorphism. If you have trouble seeing that this information is coded in the U_i's, consider that the information that f(beta_0...beta_{n-1}) = f(beta_1...beta_n) for any standard f and n is coded in U_{n+1}. (I assume that you will _not_ have trouble seeing this; I include it mostly to remind _myself_). This construction gives models of Counting and higher axioms of the form "Ordinal so-and-so is strongly Cantorian". It does not, of course, give us a basis for any assertion about _all_ Cantorian or s.c. sets. I seem not to have included an argument for a model of NFUA using an inaccessible in the paper as it stands; I'm going to have to reconstruct this! It was a refinement of this argument for models with s.c. sets, and I seem to have thought that it was redundant given the sharper result for ZFC which I have not communicated successfully! I will look at old drafts of the paper and see if I can find that construction; meanwhile, do you believe this construction? Topic 2: A possible description of the set of sentences needed to establish that Con(ZFC) = Con(NFUA) As in the argument in the paper, we work in a term model of ZFC. Add alpha_i's, nonstandard ordinals, indexed by integers (levels can be recovered as V_{\alpha_i's}) They satisfy the following sentences: G(\alpha_1...\alpha_n) < \alpha_{n+1}, G standard For each partition P of finite subsets of the ordinals of size n into set many compartments, definable using a finite sequence of \alpha_i's whose largest index is k, all \alpha_i's with index higher than k belong to the same cofinal homogeneous class for P. The question about the latter collection of sentences (in my mind) is again whether it is expressible without essential reference to classes. I'll take another stab at expressing it: Let F(\alpha_{k-m}...\alpha_k) be a class map from n-element subsets (represented as ascending sequences) of the ordinals onto some (von Neumann) ordinal (i.e., it has bounded values, and so is a partition of the kind indicated above). The part of the definition of this partition represented by the letter F is standard (in the term model). Then we have F(\alpha_{j_1}...\alpha_{j_n}) = F(\alpha_{k_1}...\alpha_{k_n}) whenever all j_m's, k_m's > k. I haven't directly provided that the homogeneous class is cofinal (which is essential for iteration; one doesn't want it to become small!), but this seems to be provided by the first set of sentences; any class which contains all the \alpha_i's seems to have to be cofinal. But this condition seems to be expressible as well (without essential reference to classes): to say that a given homogeneous class can be regarded as cofinal is to say that the corresponding value for F is found on homogeneous sets relative to this partition of arbitrarily large ordinals, I think? Do you agree that this set of sentences is describable and consistent (I do say something like this in the paper)? Existence of cofinal homogeneous classes does follow from Erdos-Rado, does it not? It appears that this set of sentences is sufficient for my purposes (the "standard-bounded" stuff is not needed). Compare any \alpha_i with a standard function image F(\alpha_{i+1}...\alpha_{i+n}). Consider the partition produced by mapping each sequence (a_1...a_n) to F(a_1...a_n) if this is less than \alpha_i and to \alpha_i otherwise. The larger \alpha_k's must be homogeneous with respect to this partition: thus, F(\alpha_{i+1}...\alpha_{i+n}) is either (i.) greater than or equal to \alpha_i or (ii.) lies below \alpha_i and is fixed under the automorphism induced by incrementing the indices of the \alpha_i's (that this operation is an automorphism follows from the homogeneity properties of the model). Thus, in the induced model of NFU (built from V_{\alpha_0) using the index incrementing automorphism), every ordinal will either be fixed under the automorphism or greater than some \alpha_i; this is sufficient for the Axiom of Cantorian Sets to hold. Final Remark: Now that I have what I think is the correct set of sentences for the Con(ZFC) -> Con(NFUA) proof, I think I see how to reconstruct the model of NFUA below an inaccessible. But I will get this part out before tackling the latter in the next message! I hope that I am being more coherent! --Randall From holmes Mon Apr 17 14:48:07 1995 To: holmes@catseye.idbsu.edu, solovay@math.berkeley.edu Subject: Re: Construction 3 Status: RO I'm not sure that I stated exactly how the "finite set" of partitions described by the ultrafilter C in the outline of Construction 3 is used to induce a single partition for which a homogeneous set can be found. If this is not clear, ask me. --Randall From solovay@math.berkeley.edu Tue Apr 18 23:39 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA07457; Tue, 18 Apr 1995 23:39:52 -0600 Return-Path: Received: by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id WAA09173; Tue, 18 Apr 1995 22:35:23 -0700 Date: Tue, 18 Apr 1995 22:35:23 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Message-Id: <199504190535.WAA09173@math.berkeley.edu> To: holmes@catseye.idbsu.edu Subject: Upper bounds on NFUB's consistency strength Status: RO For a certain new property Phi(kappa), I can prove ZFC + exists kappa Phi(kappa) proves Con(NFUB). Before giving the precise definition let me make some comments. 1) If kappa is completely ineffable, then there are a stationary set of alpha's less than kappa such that Phi(alpha). 2) It follows that there are alpha in L such that Phi(alpha) [say if 0# exists]. But I cannot prove yet that if Phi(alpha), then Phi(alpha) holds in L. Indeed, for all I know, "ZFC + V=L + exists alpha Phi(alpha)" has greater consistency strength than "ZFC + exists alpha Phi(alpha)". [I don't think this actually happens; I just can't yet rule it out.] 3) If Phi(alpha), then alpha is weakly compact, and there are a stationary set of beta less than alpha which are n-ineffable for all n in omega [and hence are weakly compact]. 4) The idea of Phi(alpha) is to give just as much of the normal measure coming from a measurable as is needed in [my version of] the usual proof that measurable cardinals give the consistency of NFUB. Here is the precise definition: A cardinal kappa is Phi provided there is a well-ordering of V_kappa of length kappa, <*, say, a non-empty collection of subsets of kappa, say W, and a finitely additive ultrafilter U on W such that: (a) To avoid any confusion I spell out what I mean by an ultrafilter U on W. It will follow from the closure conditions on W asserted below that W is a Boolean subalgebra of P(kappa). There is a Boolean homomorphism of W onto 2 such that U is the preimage of 1. Note well: we do not assume that U is countably additive. (b) Here are the explicit closure conditions on W. W contains every one element subset of kappa. If A and B are members of W and C is a subset of kappa which is definable in the structure then C is in W. (c) Suppose that is a kappa sequence of subsets of kappa that is coded by a member of W> Then the set of alpha such that A_alpha is in U is a member of W. [This says that U, in the terminology of Kunen, is a W-ultrafilter.] Finally, we need the following normality condition. (d) Suppose that A is in U, and that f is map from A to kappa, which is regressive in the sense that f(alpha) < alpha for every alpha in A. Then there is a subset B of A, also lying in U, such that the restriction of f to B is constant, That completes the definition of Phi and with it this letter. As ever, Bob From solovay@math.berkeley.edu Wed Apr 19 10:36 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA07895; Wed, 19 Apr 1995 10:36:36 -0600 Return-Path: Received: by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id JAA17901; Wed, 19 Apr 1995 09:32:05 -0700 Date: Wed, 19 Apr 1995 09:32:05 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Message-Id: <199504191632.JAA17901@math.berkeley.edu> To: holmes@catseye.idbsu.edu In-Reply-To: Randall Holmes's message of Wed, 19 Apr 1995 06:33:16 -0600 <199504191228.FAA13457@math.berkeley.edu> Subject: Net effect Status: RO Randall, This letter is being written in great haste early in the morning in response to your two most recent letters. 1) It is possible that my "quite erroneous" appelation of your first proof was "quite erroneous". I will have to think about this. What I am pretty sure is that your ultrafilter style arguments do not yield the Jensen-Morley result that for any standard beta, NFU has a beta model. When I read this proof, I thought this was what you were trying to prove. So I will have to read the proof again to see if it yields a proof of the consistency of NFU + Counting. 2) I will be glad to (a) discuss my objections to your proof [if they survive a second reading thereof] and your "proof" of Con(ZFC) implies Con(NFUA). But the next thing I want to tackle [in our correspondence] is the typing in of my proof that NFUA implies the consistency of ZFC {and a fair bit more!] I have no time right now to read and comment on the mathematics in your two latest letters. All in due time. As ever, BobB From solovay@math.berkeley.edu Wed Apr 19 13:38 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA08078; Wed, 19 Apr 1995 13:38:28 -0600 Return-Path: Received: from feynman.berkeley.edu by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id MAA23808; Wed, 19 Apr 1995 12:33:58 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Received: (solovay@localhost) by feynman.berkeley.edu (8.6.10/8.6.4) id MAA12316; Wed, 19 Apr 1995 12:33:57 -0700 Date: Wed, 19 Apr 1995 12:33:57 -0700 Message-Id: <199504191933.MAA12316@feynman.berkeley.edu> To: holmes@catseye.idbsu.edu Subject: On the consistency strength of NFU + Counting Status: RO Of course, ZFC simply proves NFU + Counting consistent. So we have to use weaker theories to calibrate its consistency strength. The following terminology is pretty standard: Z is Zermelo set theory. [So we drop the replacement axiom and the axiom of choice; we do have a comprehension schema. ZC is Zermelo plus the axiom of choice. ZF- is ZFC - the power set and choice axioms. ZFC- is ZFC minus the power set axiom. The weakest theory in which I can prove the consistency of NFU + "Counting" is ZFC- + "Aleph_{Aleph_{Aleph_1}} exists". If I weren't so lazy, I could almost certainly hack out a proof in ZC + "For all countable ordinals alpha, Aleph_{Aleph_alpha} exists". How about lower bounds. Well we certainly can get the consistency of ZC + V=L + "Aleph_alpha exists" for any explicit small countable ordinal alpha. [For example, alpha = omega^2.] I think with a little work, this could be greatly improved---to for example, ZC + V=L + Aleph_{Aleph_{omega^2}. The idea would be to exploit the examples showing the cardinal bounds for Erdos-Rado are optimal. As I indicate, I haven't thought this through. What is the relevance of all this. Well so far as I can see, your proof if it were correct could easily be formalized in ZC + V=L + Aleph_omega exists. [Your beta is omega; your alpha could be taken to be Aleph_omega.] In this way, we would easily contradict Godel's theorem. As ever, Bob From solovay@math.berkeley.edu Wed Apr 19 14:16 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA08116; Wed, 19 Apr 1995 14:16:18 -0600 Return-Path: Received: from feynman.berkeley.edu by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id NAA25005; Wed, 19 Apr 1995 13:11:48 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Received: (solovay@localhost) by feynman.berkeley.edu (8.6.10/8.6.4) id NAA12388; Wed, 19 Apr 1995 13:11:46 -0700 Date: Wed, 19 Apr 1995 13:11:46 -0700 Message-Id: <199504192011.NAA12388@feynman.berkeley.edu> To: holmes@catseye.idbsu.edu Subject: Lower bound for strength of NFUA: 1 Status: RO Just some organizational comments and caveats. I envision a series of five letters of which this is the first. Letter 2 will just state precisely what I am claiming. It is a tiny bit stronger than the off-hand claims I made in previous letters. The proof requires a fair amount of reasoning within NFUA. I prefer to present this as follows. I reformulate NFUA as a Specker theory and work within that. The advantage, for me, is that my usual set-theoretical intuitions are readily available. One could, no doubt, do the same argument within orthdox NFUA. Letter 3 gives the main construction, which involves defining two descending sequences of ordinals. The definition takes place internally to the Specker model, so at some point the construction must break down. Letter 4 gives a proof that the construction never breaks down. Although it now seems quite straightforward to me, this is the trickiest part of the argument. I suspect that if my proof is wrong [and I don't think it is] then here is where the error lies. Of course, Letters 3 and 4 together yield a contradiction but to what? Well before starting the argument in Letter 3 an "anti-large-cardinal" assumption was made, and that is what's refuted. A final caveat: This is the first time I've written up the proof in detail and I am doing it in real time. There is definitely a risk that when I come to write letter 4, say, I will just say "Whoops". Of course, I could avoid that by writing this all offline, but I choose not to do so. It's psychologically rewarding to send each letter off into the aether, and as a born again lazy person I need all the props and tricks I can muster to get myself to do anything at all. As ever, Bob From holmes@catseye.idbsu.edu Wed Apr 19 14:17 MDT 1995 Received: by catseye.idbsu.edu (1.38.193.4/16.2) id AA08119; Wed, 19 Apr 1995 14:17:04 -0600 Date: Wed, 19 Apr 1995 14:17:04 -0600 From: Randall Holmes Return-Path: To: holmes@catseye.idbsu.edu, solovay@math.berkeley.edu Subject: Re: On the consistency strength of NFU + Counting Status: RO Dear Bob, I have heard the assertion that the consistency strength of NFU + Counting is Z + < aleph-omega replacement; I don't know how to evaluate it. I think that the consistency strength of my construction is higher than you think. It is necessary to construct V_{alpha} for alpha nonstandard just less than aleph-omega (at least, that's where I _think_ the ordinals moved by the automorphism live) to build the model of NFU; so one certainly has aleph(aleph n) for each n, for example! A proof that aleph(aleph(omega)) exists under Counting would Godelize my construction to my satisfaction! One needs to be able to construct the ordinal ranks corresponding to the ordinals moved by the automorphism as well as those ordinals themselves! If you want to talk about this construction, I want to write it up carefully again from first principles; exact descriptions of the various ultrafilters are important! (and my comment that the U_i's are used in a way analogous to those in construction 2 might be misleading; this does not mean that the U_i's have the same properties as those in the earlier construction). The obstruction to the proof for ZFC is that I need a sharper form of the Erdos-Rado theorem, in the sense that the Paris-Harrington theorem is sharper than the Ramsey theorem: I need homogeneous sets which are larger in cardinality than their smallest element. I only realized that I needed something like this this morning, and I'm quite willing to believe that such a theorem would be either definitely false or would strengthen ZFC (by analogy with what the P-H theorem does). --Randall From holmes@catseye.idbsu.edu Wed Apr 19 14:19 MDT 1995 Received: by catseye.idbsu.edu (1.38.193.4/16.2) id AA08129; Wed, 19 Apr 1995 14:19:00 -0600 Date: Wed, 19 Apr 1995 14:19:00 -0600 From: Randall Holmes Return-Path: To: holmes@catseye.idbsu.edu, solovay@math.berkeley.edu Subject: Re: Lower bound for strength of NFUA: 1 Status: RO I'm fine with sending off "proofs in progress"; I'm guilty of this myself! (as witness the "proof" I started this morning; claim 1 foundered on close examination, or at least is nontrivial!) --Randall From solovay@math.berkeley.edu Wed Apr 19 15:41 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA08285; Wed, 19 Apr 1995 15:41:29 -0600 Return-Path: Received: from feynman.berkeley.edu by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id OAA27834; Wed, 19 Apr 1995 14:36:58 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Received: (solovay@localhost) by feynman.berkeley.edu (8.6.10/8.6.4) id OAA12461; Wed, 19 Apr 1995 14:36:57 -0700 Date: Wed, 19 Apr 1995 14:36:57 -0700 Message-Id: <199504192136.OAA12461@feynman.berkeley.edu> To: holmes@catseye.idbsu.edu Subject: Lower bound for strength of NFUA: 2 Status: RO Here I can state the precise result I am heading for fairly briefly. Work in NFUA. Among the well-orderings of V there is a shortest one. Fix a well-ordering of V of that order type. Call that order type Omega. There will be a binary relation on V which is a model of Z-- + V=L and whose ordinals have order type Omega. Here Z-- is either Z or ZF- depending on whether Omega is a limit cardinal in L or not. [This can be talked about since, in effect, we have type-theory with V as the base set.] Main Claim: There is an ordinal of this model which the model thinks is an inaccessible cardinal with an inaccessible limit of inaccessibles below it. >From the fact that NFUA proves the main claim, it follows readily, that NFUA proves the consistency of ZFC + "There is an inaccessible limit of inaccessible cardinals". It remains to prove the main claim in NFUA. We will work in the theory NFUA + "Main Claim is false" and in the letters that follow will derive a contradiction. From solovay@math.berkeley.edu Wed Apr 19 15:29 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA08267; Wed, 19 Apr 1995 15:29:13 -0600 Return-Path: Received: from feynman.berkeley.edu by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id OAA27409; Wed, 19 Apr 1995 14:24:43 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Received: (solovay@localhost) by feynman.berkeley.edu (8.6.10/8.6.4) id OAA12451; Wed, 19 Apr 1995 14:24:42 -0700 Date: Wed, 19 Apr 1995 14:24:42 -0700 Message-Id: <199504192124.OAA12451@feynman.berkeley.edu> To: holmes@catseye.idbsu.edu Cc: holmes@catseye.idbsu.edu In-Reply-To: Randall Holmes's message of Wed, 19 Apr 1995 14:17:04 -0600 <199504192012.NAA25020@math.berkeley.edu> Subject: On the consistency strength of NFU + Counting Status: RO Randall, I suspected you might reply that the issue is Aleph_{Aleph_omega}. I may look at the proposed strengthening of the lower bound; or I may simply confine myself to looking at your proof. One doesn't need Godel, though it can be a useful way of getting insight. To whom is this proof of the consistency strength of Counting attributed? Is it published? I find myself **rather** skeptical. I think it likely that your formulation of P-H variants of Erdos-Rado is somewhat strong. Not too strong, of course; they follow from weakly compact cardinals. But I've never really thought about such matters so my opinion isn't worth too much. As ever, Bob From holmes@catseye.idbsu.edu Wed Apr 19 16:37 MDT 1995 Received: by catseye.idbsu.edu (1.38.193.4/16.2) id AA08321; Wed, 19 Apr 1995 16:37:59 -0600 Date: Wed, 19 Apr 1995 16:37:59 -0600 From: Randall Holmes Return-Path: To: holmes@catseye.idbsu.edu, solovay@math.berkeley.edu Subject: Re: On the consistency strength of NFU + Counting Status: RO It's mine; it appears in an appendix to my Ph.D. thesis. --Randall Do you have references for P_H variants of Erdos-Rado? I don't need full strength! The construction I had in mind to prove Claim 1 works if I have a P-H variant of Erdos-Rado; of course, the strength needed is then not ZFC! --Randall P.S. I will send you the full write-up of Construction 3 that I am doing now shortly. From holmes@catseye.idbsu.edu Wed Apr 19 16:55 MDT 1995 Received: by catseye.idbsu.edu (1.38.193.4/16.2) id AA08351; Wed, 19 Apr 1995 16:55:38 -0600 Date: Wed, 19 Apr 1995 16:55:38 -0600 From: Randall Holmes Return-Path: To: holmes@catseye.idbsu.edu, solovay@math.berkeley.edu Subject: Re: Lower bound for strength of NFUA: 2 Status: RO I believe the assertions in this note, other than the Main Claim which remains to be established, of course! --Randall From solovay@math.berkeley.edu Thu Apr 20 02:15 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA08687; Thu, 20 Apr 1995 02:15:16 -0600 Return-Path: Received: by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id BAA11727; Thu, 20 Apr 1995 01:10:46 -0700 Date: Thu, 20 Apr 1995 01:10:46 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Message-Id: <199504200810.BAA11727@math.berkeley.edu> To: holmes@catseye.idbsu.edu Subject: Letter 3 on Lower Bounds Status: RO So we have our model of NFUA where the Main Claim is false. There is a relation eta on V such that V equipped with eta is isomorphic to L_Omega. We now do the Specker trick of unravelling the model. So V_i is the i^{th} copy of V. There is an epsilon relation between V_i and V_{i+1}, say epsilon_i. There is a copy of eta on V_i, which we dub eta_i. V_i equipped with this relation is isomorphic to L_{Omega_i}. There is a natural inclusion map of L_Omega{i} into L_{Omega{i+1}, which is the analogue in this approach of the T construction. This maps L_{Omega_i} onto an initial segment of L_{Omega_{i+1}}. It is a consequence of the Burali-Forti paradox that this inclusion map is not onto. It is important that these inclusion maps prolong to isomorphisms of finite type structures using the epsilon_i's. Moreover, it is legitimate to allow the various inclusion maps and the eta_i's as well as the epsilon_i's [and the notion of which elements of V_{i+1} correspond to subsets of V_i] to appear in the comprehension principles which define [epsilon type subsets of the various V_i's. There is of course an automorphism j which sends eta_i onto eta_{i+1} for any i, and sends V_i onto V_{i+1} and also carries epsilon_i} onto epsilon_{i+1}. It also maps canonical inclusion maps to one another in the obvious way. We treat the various inclusion maps as identifications for the most part. With these conventions, the ordinals Omega_j for j < i appear in V_i. Moreover, j(Omega_i) = Omega_{i+1}. All this is fairly straightforward. The only three caveats: 1) The comprehension axioms involve only variables ranging over the V-i's one at a time; there are no global variables ranging over the directed limit of the L_{Omega_i}'s. 2) There may well be non-constructible subsets of sets in the various L_{Omega_i}'s . 3) j cannot appear in the instances of the comprehension axiom. I trust all this is utterly clear to you. I will abuse notation by referring to all the different epsilon_i's and eta_i's as epsilon. This just eases the writing; it would be easy to get all the subscripts right if it were important. This ends letter 3. From holmes@catseye.idbsu.edu Thu Apr 20 07:32 MDT 1995 Received: by catseye.idbsu.edu (1.38.193.4/16.2) id AA08739; Thu, 20 Apr 1995 07:32:27 -0600 Date: Thu, 20 Apr 1995 07:32:27 -0600 From: Randall Holmes Return-Path: To: holmes@catseye.idbsu.edu, solovay@math.berkeley.edu Subject: Re: Letter 3 on Lower Bounds Status: RO All of this is clear to me as you expected. --Randall From T.Forster@pmms.cam.ac.uk Thu Apr 20 12:18 MDT 1995 Received: from emu.pmms.cam.ac.uk by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA09004; Thu, 20 Apr 1995 12:18:16 -0600 Return-Path: Received: by emu.pmms.cam.ac.uk (UK-Smail 3.1.25.1/1); Thu, 20 Apr 95 18:58 BST Message-Id: Date: Thu, 20 Apr 95 19:13 BST From: Thomas Forster To: holmes@catseye.idbsu.edu Subject: Re: Not fixed Status: RO I can't think of any reason why ``every cantorian is stcan" should give you anything like zf. From holmes@catseye.idbsu.edu Thu Apr 20 13:54 MDT 1995 Received: by catseye.idbsu.edu (1.38.193.4/16.2) id AA09119; Thu, 20 Apr 1995 13:54:03 -0600 Date: Thu, 20 Apr 1995 13:54:03 -0600 From: Randall Holmes Return-Path: To: T.Forster@pmms.cam.ac.uk, holmes@catseye.idbsu.edu Subject: Re: Not fixed Status: RO Dear Thomas, It seems established that it gives the strength of ZFC as a lower bound; I think that part of my paper is sound. What Solovay claims and I cannot see how to exclude is that it is in fact considerably stronger. The proposition he is now attempting to prove to me (we are not far enough along for me to express an opinion as to the validity of the argument) is that NFU + Infinity + AC + "every Cantorian set is strongly Cantorian" proves that there is an inaccessible limit of inaccessibles in L (as encoded suitably in Ord, not L in the usual unstratified sense). My attempt at a proof that Con(ZFC) implies Con(NFU + stuff above) works perfectly well to show that Con(ZFC + weakly compact cardinal) implies Con(NFU + stuff above). A variation I attempted turned out to need a refinement of the Erdos-Rado theorem which works -- in the presence of weakly compact cardinals! I find it very hard to believe that the Axiom of Cantorian Sets is that strong! Internal evidence seems to support strength of ZFC. The Axiom of Cantorian Sets is very useful for establishing that limit ordinals are strongly Cantorian; limit ordinals familiar from ZFC will generally be Cantorian, thus strongly Cantorian by the axiom. In my paper I proved that the Axiom of Cantorian Sets implies that "each class of strongly Cantorian isomorphism types of wfexts which is definable from equality and the "membership" relation natural for these objects with all quantifiers restricted to the class of strongly Cantorian isomorphism types of wfexts is the intersection of the class of strongly Cantorian isomorphisms of wfexts and some set". This principle is enough for the interpretation of Zermelo style set theory in s.c. isomorphism types of wfexts to satisfy Replacement. The idea of the proof of the preceding result I outlined during my visit. Let's call "ismorphism types of wfexts" "Z-pictures" (I have just created this term) (actually, we want only those types which belong to ranks all subsets of which are realized as types to be Z-pictures). Any class of Z-pictures defined as above has no problem with stratification except that quantifiers may be present which range over a non-set (the class of s.c. Z-pictures). Relativize all quantifiers to the lowest rank of Z-pictures which has the same theory as the class of all Z-pictures; this rank is Cantorian (obviously) and so strongly Cantorian. The rank to which one relativizes may be dependent on parameters in the definition of the class; as long as these parameters are s.c., everything works fine. When one carries out this process repeatedly, one needs to relativize to lowest sequences of ranks b1,...bn which have the same theory (considered as models of TTU_{n+1}) as Z (the last rank, the set of all Z-pictures), Tz,...,T^n{z}; again, this is a sequence of Cantorian, thus strongly Cantorian ranks. The reason that one needs iterated images under T is that the relativization process itself needs to be relativized, and the only way to do this is to reflect things downward using T (theories being preserved because Counting holds). In this way, all class definitions of this kind can be transformed into stratified definitions, as long as all parameters are restricted to s.c. objects; these stratified definitions define sets, which will have the same s.c. elements as the original classes. The class definition principle above is a weaker version of my Axiom of Small Ordinals. Showing that it implies Replacement is pretty easy. If NFU + Infinity + Choice + Axiom of Cantorian Sets _did_ turn out to be quite strong this would recommend it in some ways (the Axiom of Cantorian Sets is, after all, a very natural assumption). The strength of this axiom is in any event below that of a measurable cardinal, and probably below that of a Weakly compact cardinal by my busted argument. I will be surprised if Solovay can show that it is stronger than ZFC, but I must admit to being stymied in my efforts to show its exact strength is that of ZFC! My original argument does not seem to be possible to repair in any cheap way; all obvious variations seem to need that blasted weakly compact cardinal! --Randall From solovay@math.berkeley.edu Fri Apr 21 00:06 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA09504; Fri, 21 Apr 1995 00:06:43 -0600 Return-Path: Received: by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id XAA08437; Thu, 20 Apr 1995 23:02:12 -0700 Date: Thu, 20 Apr 1995 23:02:12 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Message-Id: <199504210602.XAA08437@math.berkeley.edu> To: holmes@catseye.idbsu.edu Subject: Addendum to letter 3 Lower Bounds On Consistency Strength Status: RO Randall, I clearly was rather tired when I wrote that letter since I forgot the main point. Work in NFUA. Recall that we have an ordering of V, <, which is "as short as possible". In terms of this we define an analogue of the T map as follows. Let x in V. Let S_x be the set of y such that y < x. We let S_x' be the set of singletons of members of S_x, and give it the isomorphic copy of the restriction of < to S_x as its ordering. So S_x' is order-isomorphic to S_y for a unique y, and we call that y TT(x). [I am using TT since this is not quite the T of your paper, though it is very closely related to it. Now go to the Specker framework described in my letter 3. The map TT has the following relationship to j. Let zeta be an ordinal of L_Omega. Then zeta has a copy in V_0, [which lies in Omega_0, in fact] and as described in that letter, there is a canonical injection of Omega_0 onto a proper initial segment of Omega_1 which is a subset of V_1. Say zeta* is the image of zeta under this map. Then j^{-1}(zeta*) = TT(zeta). This was difficult for me to prove, but I suspect that it is obvious to you, and so omit the proof. [I will, of course, supply my proof if need be.] What I need is the corollary. The L_Omega cardinal gamma is Cantorian iff j(gamma) = gamma. Hence gamma is strongly Cantorian iff the restriction of j to the ordinals less than gamma is the identity. From solovay@math.berkeley.edu Fri Apr 21 00:55 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA09509; Fri, 21 Apr 1995 00:55:46 -0600 Return-Path: Received: by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id XAA08937; Thu, 20 Apr 1995 23:51:16 -0700 Date: Thu, 20 Apr 1995 23:51:16 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Message-Id: <199504210651.XAA08937@math.berkeley.edu> To: holmes@catseye.idbsu.edu Subject: Letter 4: Lower bounds on consistency Status: RO We work in the Specker framework. The following definitions will take place within the model L_{Omega_2}. If I were formal, there would be a definition of the sequences I am constructing in L_Omega_2 from the parameters Omega_0 and Omega_1. Since L_Omega_2 is a model of either ZF- or Z, it has a perfectly good treatment of finite sequences of ordinals [the usual set-theoretic treatment!]. We are going to define, by induction on the integer i, ordinals alpha(i) and beta(i). It will be true that if alpha(i+1) is defined, then alpha(i+1) < alpha(i). Similarly, beta(i+1) < beta(i) if both are defined. It will always be true that if alpha(i) is defined and j is less than i, then alpha(j) is defined. So alpha is defined on a proper initial segment of the integers. Entirely analogous remarks apply to beta. It will also be true that alpha(i) is defined iff beta(i) is defined. To start the process off, alpha(0) = Omega_0; beta(0) = Omega_1. Now suppose that alpha(i) and beta(i) have been defined. Our task is to tell whether alpha(i+1) and beta(i+1) are defined and, if so, what they are. First, if alpha(i) = beta(i), then alpha(i+1) and beta(i+1) are undefined. Next, if alpha(i) and beta(i) have different "colors" [in a sense to be explained in a moment] then alpha(i+1) and beta(i+1) are undefined. Given an ordinal of Omega_2, we define its color as follows: 0) Ordinals <= omega get the color 0. 1) Ordinals that are not cardinals [in L_{Omega_2] get the color 1. [I won't keep repeating "in L_{Omega_2} in the remainder of this definition.] 2) Ordinals that are infinite sucessor cardinals get the color 2. 3) Singular limit cardinals get the color 3. 4) Inaccessible cardinals that are not limits of inaccessible cardinals get the color 4. 5) Inaccessible limits of inaccessible's get the color 5. The only remaining cases to consider are when alpha(i) and beta(i) have the same color, but are distinct ordinals. There are six subcases according to what the common color is. Case 0: alpha(i+1) and beta(i+1) are undefined in this case. Case 1: Set alpha(i+1) equal to the cardinal of alpha(i) in L_{Omega_2}. Set beta(i+1) equal to the cardinal of beta(i) in L_{Omega_2}. Case 2: Set alpha(i+1) equal to the largest cardinal less than alpha(i). Define beta(i+1) analogously from beta(i). Case 3: This is the most complicated case to handle. Let alpha* be the cofinality of alpha; let beta* be the cofinality of beta. If alpha* is unequal to beta*, set alpha(i+1) = alpha* and beta(i+1) = beta*. So suppose now that alpha* = beta* = gamma, say. Let f be the L-least order preserving map of gamma cofinally into alpha(i) and let g be the L-least order preserving map of gamma cofinally into beta(i). Let eta be the least ordinal less than gamma such that f(eta) is unequal to g(eta). [eta must exist since alpha(i) is unequal to beta(i).] Set alpha(i+1) = f(eta); set beta(i+1) = g(eta). Case 4: Let alpha(i+1) be the sup of the inaccessible cardinals less than alpha(i). [If there are none, alpha(i+1) = 0.] Let beta(i+1) be defined analogously from beta(i). Case 5: In this case, the construction stops and alpha(i+1) and beta(i+1) are undefined. This completes the construction and letter 4. From T.Forster@pmms.cam.ac.uk Fri Apr 21 02:20 MDT 1995 Received: from diamond.idbsu.edu by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA09516; Fri, 21 Apr 1995 02:20:44 -0600 Return-Path: Received: from emu.pmms.cam.ac.uk by diamond.idbsu.edu with SMTP (1.37.109.16/16.2) id AA069752366; Fri, 21 Apr 1995 02:19:26 -0600 Received: by emu.pmms.cam.ac.uk (UK-Smail 3.1.25.1/1); Fri, 21 Apr 95 08:50 BST Message-Id: Date: Fri, 21 Apr 95 09:15 BST From: Thomas Forster To: holmes@diamond.idbsu.edu Subject: every can is stcan Status: RO Thanks for bringing me up to date with your tho'rts on this. I haven't actually tho'rt about this myself for many years, and the of course in the context of NF not NFU. I think my view was that it was a very unsatisfactory axiom, having possibly rather strong consequences for big sets and not saying as much about little sets as one would like. It doesn't seem to imply that the Hcan sets are a model of ZF for example, which is something one might want. On the other hand i have the feeling that funny things happen to big ordinals if every can is stcan. I think i ended up feeling that one should steer clear of it. I suppose what i want to say is that i don't yet think i understand the genesis of the two concepts of can and stcan to know whther or not they should have the same extensions, and certainly *at the moment* i can see no motivation. But keep keeping me up to date! best wishes Thomas From T.Forster@pmms.cam.ac.uk Fri Apr 21 07:47 MDT 1995 Received: from emu.pmms.cam.ac.uk by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA09585; Fri, 21 Apr 1995 07:47:02 -0600 Return-Path: Received: by emu.pmms.cam.ac.uk (UK-Smail 3.1.25.1/1); Fri, 21 Apr 95 14:39 BST Message-Id: Date: Fri, 21 Apr 95 14:39 BST From: Thomas Forster To: holmes@catseye.idbsu.edu Subject: Re: every can is stcan Status: RO Really? How do you get all the comprehension? Don't you need a certain amount of choice? Oh yes, i forgot, you are doing all this in \nf U. Well, *that* does it! From holmes@catseye.idbsu.edu Fri Apr 21 09:08 MDT 1995 Received: by catseye.idbsu.edu (1.38.193.4/16.2) id AA09683; Fri, 21 Apr 1995 09:08:40 -0600 Date: Fri, 21 Apr 1995 09:08:40 -0600 From: Randall Holmes Return-Path: To: holmes@catseye.idbsu.edu, solovay@math.berkeley.edu Subject: Re: Addendum to letter 3 Lower Bounds On Consistency Strength Status: RO Dear Bob, I was too quick in confirming your statements about your map TT(x) (I didn't read the definition carefully enough!). I think that it may very well be correct, but I _do_ need to think about it and may request the proof! --Randall From holmes@catseye.idbsu.edu Fri Apr 21 09:15 MDT 1995 Received: by catseye.idbsu.edu (1.38.193.4/16.2) id AA09706; Fri, 21 Apr 1995 09:10:54 -0600 Date: Fri, 21 Apr 1995 09:10:54 -0600 From: Randall Holmes Return-Path: To: T.Forster@pmms.cam.ac.uk, holmes@catseye.idbsu.edu Subject: Re: every can is stcan Status: RO I don't think that choice is needed in the argument, actually, but if it were, it would be available. Remember that Z-pictures have structure on them which the whole universe doesn't. --Randall From solovay@math.berkeley.edu Fri Apr 21 00:55 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA09509; Fri, 21 Apr 1995 00:55:46 -0600 Return-Path: Received: by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id XAA08937; Thu, 20 Apr 1995 23:51:16 -0700 Date: Thu, 20 Apr 1995 23:51:16 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Message-Id: <199504210651.XAA08937@math.berkeley.edu> To: holmes@catseye.idbsu.edu Subject: Letter 4: Lower bounds on consistency Status: RO We work in the Specker framework. The following definitions will take place within the model L_{Omega_2}. If I were formal, there would be a definition of the sequences I am constructing in L_Omega_2 from the parameters Omega_0 and Omega_1. Since L_Omega_2 is a model of either ZF- or Z, it has a perfectly good treatment of finite sequences of ordinals [the usual set-theoretic treatment!]. We are going to define, by induction on the integer i, ordinals alpha(i) and beta(i). It will be true that if alpha(i+1) is defined, then alpha(i+1) < alpha(i). Similarly, beta(i+1) < beta(i) if both are defined. It will always be true that if alpha(i) is defined and j is less than i, then alpha(j) is defined. So alpha is defined on a proper initial segment of the integers. Entirely analogous remarks apply to beta. It will also be true that alpha(i) is defined iff beta(i) is defined. To start the process off, alpha(0) = Omega_0; beta(0) = Omega_1. Now suppose that alpha(i) and beta(i) have been defined. Our task is to tell whether alpha(i+1) and beta(i+1) are defined and, if so, what they are. First, if alpha(i) = beta(i), then alpha(i+1) and beta(i+1) are undefined. Next, if alpha(i) and beta(i) have different "colors" [in a sense to be explained in a moment] then alpha(i+1) and beta(i+1) are undefined. Given an ordinal of Omega_2, we define its color as follows: 0) Ordinals <= omega get the color 0. 1) Ordinals that are not cardinals [in L_{Omega_2] get the color 1. [I won't keep repeating "in L_{Omega_2} in the remainder of this definition.] 2) Ordinals that are infinite sucessor cardinals get the color 2. 3) Singular limit cardinals get the color 3. 4) Inaccessible cardinals that are not limits of inaccessible cardinals get the color 4. 5) Inaccessible limits of inaccessible's get the color 5. The only remaining cases to consider are when alpha(i) and beta(i) have the same color, but are distinct ordinals. There are six subcases according to what the common color is. Case 0: alpha(i+1) and beta(i+1) are undefined in this case. Case 1: Set alpha(i+1) equal to the cardinal of alpha(i) in L_{Omega_2}. Set beta(i+1) equal to the cardinal of beta(i) in L_{Omega_2}. Case 2: Set alpha(i+1) equal to the largest cardinal less than alpha(i). Define beta(i+1) analogously from beta(i). Case 3: This is the most complicated case to handle. Let alpha* be the cofinality of alpha; let beta* be the cofinality of beta. If alpha* is unequal to beta*, set alpha(i+1) = alpha* and beta(i+1) = beta*. So suppose now that alpha* = beta* = gamma, say. Let f be the L-least order preserving map of gamma cofinally into alpha(i) and let g be the L-least order preserving map of gamma cofinally into beta(i). Let eta be the least ordinal less than gamma such that f(eta) is unequal to g(eta). [eta must exist since alpha(i) is unequal to beta(i).] Set alpha(i+1) = f(eta); set beta(i+1) = g(eta). Case 4: Let alpha(i+1) be the sup of the inaccessible cardinals less than alpha(i). [If there are none, alpha(i+1) = 0.] Let beta(i+1) be defined analogously from beta(i). Case 5: In this case, the construction stops and alpha(i+1) and beta(i+1) are undefined. This completes the construction and letter 4. From holmes Mon Apr 17 14:11:48 1995 To: solovay@math.berkeley.edu Subject: Construction 3 Status: RO Dear Bob, Now, hopefully, you are talking to the real Randall Holmes with brain completely engaged :-) Topic 1: Modelling counting (not yet NFUA!) I am going to describe the basic construction of a model of NFU with a certain standard infinite cardinal \beta (you may think of it as \omega, so that this will be a model of Counting, but I will be general, since generality is cheap here) strongly cantorian. It is sufficient to build a model with automorphism in which each ordinal less than \beta (and \beta itself) is fixed by the automorphism. Choose a cardinal \alpha greater than each iterated exponential of \beta (so that the Erdos-Rado theorem can be used). Functions from \alpha to \beta can be coded by elements of \alpha; clearly, so can finite sets of such functions. Consider, for each function f from \alpha to \beta, the set C_f of all codes of finite sets of maps from \alpha to \beta which contain f. The collection of C_f's is a filter on \alpha which can be extended to an ultrafilter C. C "describes" the code of a "finite set" of maps \alpha -> \beta which contains all standard such maps, in the ultrafilter model constructed using C. This "finite set" of functions induces a partition of \alpha into \beta pieces, which has a "homogeneous set" H. We use this "homogeneous set" to define a sequence of ultrafilters U_i on [\alpha]^i in the real world: U_i will contain all standard finite sets of subsets of \alpha of size i whose analogues in the model built with C contain all subsets of H with i elements. The model can be defined in terms of the U_i's as in the earlier constructions. The model contains \beta_k's indexed by integers k: U_i tells us which sets contain each sequence of i successive \beta_k's; the model elements are exactly the images under standard functions of finite sequences of successive \beta_k's. Any ordinal less than \beta in this model is the image of a finite sequence of n successive \beta_k's under some standard function \alpha^n -> \beta. Now the set H in the model built using C was homogeneous with respect to the partition induced by this map (and every similar standard map), so the images of any sequence of n successive \beta_k's remains the same when the indexes of the \beta_k's are incremented; any ordinal less than \beta is fixed by the automorphism. If you have trouble seeing that this information is coded in the U_i's, consider that the information that f(beta_0...beta_{n-1}) = f(beta_1...beta_n) for any standard f and n is coded in U_{n+1}. (I assume that you will _not_ have trouble seeing this; I include it mostly to remind _myself_). This construction gives models of Counting and higher axioms of the form "Ordinal so-and-so is strongly Cantorian". It does not, of course, give us a basis for any assertion about _all_ Cantorian or s.c. sets. I seem not to have included an argument for a model of NFUA using an inaccessible in the paper as it stands; I'm going to have to reconstruct this! It was a refinement of this argument for models with s.c. sets, and I seem to have thought that it was redundant given the sharper result for ZFC which I have not communicated successfully! I will look at old drafts of the paper and see if I can find that construction; meanwhile, do you believe this construction? Topic 2: A possible description of the set of sentences needed to establish that Con(ZFC) = Con(NFUA) As in the argument in the paper, we work in a term model of ZFC. Add alpha_i's, nonstandard ordinals, indexed by integers (levels can be recovered as V_{\alpha_i's}) They satisfy the following sentences: G(\alpha_1...\alpha_n) < \alpha_{n+1}, G standard For each partition P of finite subsets of the ordinals of size n into set many compartments, definable using a finite sequence of \alpha_i's whose largest index is k, all \alpha_i's with index higher than k belong to the same cofinal homogeneous class for P. The question about the latter collection of sentences (in my mind) is again whether it is expressible without essential reference to classes. I'll take another stab at expressing it: Let F(\alpha_{k-m}...\alpha_k) be a class map from n-element subsets (represented as ascending sequences) of the ordinals onto some (von Neumann) ordinal (i.e., it has bounded values, and so is a partition of the kind indicated above). The part of the definition of this partition represented by the letter F is standard (in the term model). Then we have F(\alpha_{j_1}...\alpha_{j_n}) = F(\alpha_{k_1}...\alpha_{k_n}) whenever all j_m's, k_m's > k. I haven't directly provided that the homogeneous class is cofinal (which is essential for iteration; one doesn't want it to become small!), but this seems to be provided by the first set of sentences; any class which contains all the \alpha_i's seems to have to be cofinal. But this condition seems to be expressible as well (without essential reference to classes): to say that a given homogeneous class can be regarded as cofinal is to say that the corresponding value for F is found on homogeneous sets relative to this partition of arbitrarily large ordinals, I think? Do you agree that this set of sentences is describable and consistent (I do say something like this in the paper)? Existence of cofinal homogeneous classes does follow from Erdos-Rado, does it not? It appears that this set of sentences is sufficient for my purposes (the "standard-bounded" stuff is not needed). Compare any \alpha_i with a standard function image F(\alpha_{i+1}...\alpha_{i+n}). Consider the partition produced by mapping each sequence (a_1...a_n) to F(a_1...a_n) if this is less than \alpha_i and to \alpha_i otherwise. The larger \alpha_k's must be homogeneous with respect to this partition: thus, F(\alpha_{i+1}...\alpha_{i+n}) is either (i.) greater than or equal to \alpha_i or (ii.) lies below \alpha_i and is fixed under the automorphism induced by incrementing the indices of the \alpha_i's (that this operation is an automorphism follows from the homogeneity properties of the model). Thus, in the induced model of NFU (built from V_{\alpha_0) using the index incrementing automorphism), every ordinal will either be fixed under the automorphism or greater than some \alpha_i; this is sufficient for the Axiom of Cantorian Sets to hold. Final Remark: Now that I have what I think is the correct set of sentences for the Con(ZFC) -> Con(NFUA) proof, I think I see how to reconstruct the model of NFUA below an inaccessible. But I will get this part out before tackling the latter in the next message! I hope that I am being more coherent! --Randall From solovay@math.berkeley.edu Sat Apr 22 00:35 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA10923; Sat, 22 Apr 1995 00:35:01 -0600 Return-Path: Received: by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id XAA03663; Fri, 21 Apr 1995 23:30:29 -0700 Date: Fri, 21 Apr 1995 23:30:29 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Message-Id: <199504220630.XAA03663@math.berkeley.edu> To: holmes@catseye.idbsu.edu Subject: The final installment of the proof Status: RO Randall, I decided to send this, even though you seem to accept the proof after installments 1 through 4, since there are some delicate points I have not yet discussed which were not reflected in your comments. We have defined two elements of L_{Omega_2}, alpha and beta. They are finite decreasing sequences of ordinals of the same length. We wish to prove by induction on i in omega the following claims: (0) alpha(i) and beta(i) are defined; (1) alpha(i) is unequal to beta(i); (2) j(alpha(i)) = beta(i). The set of i satisfying (0) or (1) is clearly a set of our Specker model. For (2), this is less clear because of the appearance of j. We get around this as follows. Let gamma be the sequence j(alpha). Then gamma is a finite sequence on L_{Omega_3} which is strictly decreasing and starts with Omega_1. It follows that gamma is in L_{Omega_2}. Next, using the axiom of counting, we see that the length of gamma is j(m) = m, where m is the common length of alpha and beta. Moreover, gamma(i) = gamma(j(i)) = j(alpha(i)). Thus we can describe the set of i satisfying (2) alternatively as the set of i such that beta(i) = gamma(i). This alternative decription makes evident that the set of i satisfying (2) lies in our Specker model. [In fact, since its finite, it also lies in L_{Omega_2}, but this isn't terribly important.] Clearly 0 satisfies (0) through (2). Let i be maximal which satisfies (0) through (2). We show that i+1 satisfies (0) through (2) as well, which will give our desired contradiction. Since i satisfies (1), alpha(i) is unequal to beta(i). Since j(alpha(i) = beta(i), we conclude easily that alpha(i) and beta(i) have the same color. The remainder of the argument splits into cases according to the common color of alpha(i) and beta(i). Case 0. Then alpha(i) <= omega. So, by the axiom of counting, j(alpha(i)) = alpha(i). So alpha(i) = beta(i). This contradicts that i satisfies (1). So this case can't arise. Case 1. Then clearly alpha(i+1) and beta(i+1) are defined and j(alpha(i+1)) = beta(i+1). We have to rule out that alpha(i+1) = beta(i+1). But if this happens, alpha(i+1) is Cantorian. Hence the successor cardinal to alpha(i+1) is also Cantorian [say using the characterization of fixed points of j.} So it is strongly Cantorian. But alpha(i) is less than this successor, so it is cantorian. So beta(i) = j(alpha(i)) = alpha(i), which contradicts our inductive hypothesis. Case 2: Quite similar to Case 1. The details are omitted. Case 3: It is this case where we make the most crucial use of the axiom that every cantorian ordinal is strongly cantorian. There are two subcases. (A) Suppose alpha(i+1) = cf(alpha(i)) is unequal to cf(beta(i)). Then all our inductive claims are clear. (B) Suppose that the cofinalities of alpha(i) and beta(i) are both equal to gamma, say. Then j(gamma) = j(cf(alpha(i))= cf(j(alpha(i)))= cf(beta(i)) = gamma. [We are using constantly that j is an elementary embedding from L_{Omega_1} to L_{Omega_2} and that things like cardinality and cofinality are absolute from L_{Omega_1} to L_{Omega_2} since Omega_1 is a cardinal in L_{Omega_2}. The upshot is that j(gamma) = gamma. Let eta be least such that f(eta) is unequal to g(eta). [Definitions as in the treatment of this case in the prior letter. By the Cantorian axiom, j(eta) = eta. Clearly, j(f) = g. So j(alpha(i+1)) = j(f(eta)) = j(f)(j(eta)) = g(eta) = beta(i+1). So all inductive claims are clear. Case 4. This case is easy and similar to Cases 1 and 2. If alpha(i+1) = beta(i+1), then alpha(i) = beta (i) = least inaccessible greater than alpha(i+1), contradicting our inductive hypothesis. Case 5. By the assumption that the main claim is false, there is only one ordinal of color 5. So this case can't arise. That's all folks. From solovay@math.berkeley.edu Sat Apr 22 00:43 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA10928; Sat, 22 Apr 1995 00:43:56 -0600 Return-Path: Received: by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id XAA03815; Fri, 21 Apr 1995 23:39:24 -0700 Date: Fri, 21 Apr 1995 23:39:24 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Message-Id: <199504220639.XAA03815@math.berkeley.edu> To: holmes@catseye.idbsu.edu In-Reply-To: Randall Holmes's message of Fri, 21 Apr 1995 12:43:45 -0600 <199504211839.LAA19459@math.berkeley.edu> Subject: A question Status: RO Randall, You ask: Do you have any sense for exactly how strong NFUA should be? Now that I see what I was doing wrong, I think that I can show easily that the existence of a weakly compact cardinal implies Con(NFUA); the broken link in my best argument involves cofinal homogeneous sets for partitions, and below a weakly compact cardinal, these can be found. Reply: I have mentioned what I can do re this in previous letters. To sum up: The weakest large cardinal property from which I can get models of NFUA is what I dubbed Phi in a prior letter. This is much stronger than "weakly compact". For example, it implies the esistence of a weakly compact cardinal such that the set of smaller weakly compact cardinals is stationary in it. I can improve my argument in various trivial ways. But I can't deduce the consistency of a Mahlo cardinal from that of NFUA. The gap between these upper and lower bounds is enormous! I am rather sceptical you can get a model of NFUA from a weakly compact. I think you have still not understood all the bugs in your prior proofs. [But I could be wrong about this. I certainly don't know that Exists weakly compact implies Con(NFUA) is not a theorem of ZFC.] As ever, Bob From solovay@math.berkeley.edu Sun Apr 23 12:21 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA11716; Sun, 23 Apr 1995 12:20:59 -0600 Return-Path: Received: by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id LAA23547; Sun, 23 Apr 1995 11:16:27 -0700 Date: Sun, 23 Apr 1995 11:16:27 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Message-Id: <199504231816.LAA23547@math.berkeley.edu> To: holmes@catseye.idbsu.edu In-Reply-To: Randall Holmes's message of Sun, 23 Apr 1995 11:28:53 -0600 <199504231724.KAA23035@math.berkeley.edu> Subject: Further stuff Status: RO Dear Randall, I had been planning [and still am] to read your construction 3 and the proof of the consistency of NFUA given a weakly compact. I am even willing to read your proof of Con(NFUA) --> Con(ZFC). But this list may be "it". Weakly compact cardinals are just the Pi^1_1 indescribable cardinals. This suggests immediately what the analogue of ZFC should be [it will be in a language with both sets and classes sort of like Kelley-Morse set theory]. Today is committed to other tasks so I can't be more explicit at the instant. You may state and prove my theorem duly attributed. I would like it then to be in a self-contained appendix which I would then proofreand and approve. I have a real horror about having arguments of mine being first presented to the world with incorrect proofs [as has happened at least once] so I do insist on approving the presentation. I think the letters I sent go a long way to indicating how I would want it presented, but I would certainly rewrite more carefully Letter 3, and a proof of the claim in the appendix to Letter 3 should be provided. As ever, Bob From holmes Mon Apr 24 12:14:30 1995 To: solovay@math.berkeley.edu Subject: Construction 3 (proofread) Status: RO Dear Bob, This is the proofread version of the latest edition of construction 3. Definitely don't read the version in the paper; I started by misstating the domain of the first ultrafilter (it certainly cannot be alpha; it needs to be something like 2^{2^alpha}} as below (as I knew perfectly well on some level...) --Randall Detailed account of construction 3 Construction: Build a model of NFU in which a fixed ordinal beta is strongly Cantorian. Let alpha be the first strong limit cardinal greater than beta. Let A_m be the set of maps [alpha]^m -> beta for each natural number m. Let A = the union of the A_m's. Let U be an ultrafilter on the power set of A which contains {x|x is a finite subset of A} and contains {x|a \in x} for each a \in A. Build an ultrafilter model of set theory using U in the standard way; then the equivalence class of the identity function will be a nonstandard finite set F which contains all (nonstandard analogues of) standard partitions of [alpha]^n for standard n into beta pieces (in the sense of the model). In this model, we can build a single partition of [alpha]^M for a nonstandard natural number M using the set F which codes all of the partitions in F. Suppose that the elements of F are indexed: {F_1,...,F_N}. Each F_i has domain [alpha]^{m_i}; let M = max(m_i) and define F_i' as the map with domain [alpha]^M obtained by applying F_i to the initial segment of length m_i of elements of [alpha]^M. We can define a map P0: [alpha]^M -> beta^N (recall that N = card(F)): the ith projection of P0(a_1,...,a_m,...,a_M) is F_i'(a_1,...,a_m). Compose P0 with any injection from beta^N into beta to obtain the desired partition P: [alpha]^M -> beta. By the Erdos-Rado theorem, P has a homogeneous set H. It should be clear that this homogeneous set H will be homogeneous for the nonstandard analogue of each standard partition of an [alpha]^n into beta pieces. We now define a sequence of ultrafilters U_i indexed by positive integers in the real world (not in the nonstandard model!). U_i will be the set of all subsets of [alpha]^i whose analogues in the nonstandard model built with U above contain a tuple (a_1,...,a_i) of ascending distinct elements of H. Clearly, if (the analogue of) a standard set contains any one of these, it contains all of them! We use the sequence of ultrafilters U_i to build a second nonstandard model of set theory. An ultrafilter model built with a U_n will contain a sequence of n indiscernible nonstandard elements a_1...a_n of alpha (ordinals below alpha). Every object in this model will be of the form F(a_i,...,a_i+k) where F is a standard function [alpha]^k -> V_alpha and the arguments are a segment of the sequence of a_i's. The full nonstandard model is obtained as a direct limit of ultrafilter models U_{2n+1} with the identification of the indiscernibles in successive models indicated by calling each sequence of 2n+1 indiscernibles (a^{-n},...,a_n); the direct limit contains a collection of indiscernibles a_i indexed by the integers. It should be clear that the direct limit has an external automorphism induced by incrementing the indexes of the a_i's uniformly. Further, we observe that any element (standard or nonstandard) of the analogue of beta in this model is fixed under the automorphism. For any such element may be represented without loss of generality by a term F(a_i,...a_i+k), where F is a standard function from [alpha]^i to beta, and the model construction ensures that the set of all sequences b_1,...,b_k+1 such that F(b_1,...,b_k) = F(b_2,...,b_{k+1}) belongs to U_{k+1} for any standard F:[alpha_i] -> beta, which ensures in turn that the general element of beta that we have described is fixed by the automorphism. This is sufficient to guarantee that the analogue of beta in this model is strongly Cantorian in the natural model of NFU with domain V_{a_0} constructed inside the nonstandard model of V_alpha derived from the U_i's. Refinement of Construction 3 which yields a model of NFUA below a weakly compact cardinal: Let kappa be a weakly compact cardinal. We build an ultrafilter U on a suitable set which codes a finite set F containing all standard maps [kappa]^m -> kappa for standard n. We work in an ultrafilter model of set theory containing this object. For each alpha < kappa (including nonstandard ones!), define F_alpha as the set of maps obtained by composing elements of F with the map which is the identity on ordinals less than alpha and sends each ordinal >= alpha to alpha. F_alpha codes all standard partitions (relative to alpha, which may itself be nonstandard) of [kappa]^n into pieces indexed by the ordinals <= alpha. Just as above, we can define a partition P_alpha of a [kappa]^{M_alpha} which codes all partitions standard relative to alpha. We choose a sequence of ordinals alpha_i of the nonstandard model as follows: let alpha_{0} = 1. We define H_{0} as a homogeneous set of cardinality kappa for P_1. We choose each alpha_{i+1} from H_{i} and define H_{i+1} as a homogeneous set of cardinality kappa for the partition P_{alpha_{i+1}} restricted to H_{i} (which is large enough; this was the point of failure of my construction below an inaccessible!). The ultrafilters U_i are defined as the collections of standard subsets of [kappa]^i which contain the sequence of the first consecutive alpha_i's starting with a_1 (not a_0!). The second model is constructed exactly as above as a directed limit of models built using U_{2n+1}'s, in which there will be a collection of indiscernibles indexed by the integers. The objects described by the ultrafilters now have the property that if F(alpha_i+1,...alpha_i+j) < alpha_i, it is fixed by the automorphism (think about the partition induced by F_{alpha_i}; all a_k's above a_i belong to a homogeneous set with respect to this partition; in fact, F(alpha_i+1,...,a_i+j) is forced to lie below all a_k's!). Any object in the model of NFU based on V_{alpha_0} has rank either between successive alpha_i's (and so not Cantorian) or below all alpha_i's (and so, by the remarks above, strongly Cantorian, because fixed by the automorphism along with everything below it). There should be an analogous argument for Con(NFUA) from Con(the theory of the part of the universe below a weakly compact cardinal)? --Randall From solovay@math.berkeley.edu Wed Apr 26 09:41 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA15445; Wed, 26 Apr 1995 09:41:33 -0600 Return-Path: Received: by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id IAA25943; Wed, 26 Apr 1995 08:36:58 -0700 Date: Wed, 26 Apr 1995 08:36:58 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Message-Id: <199504261536.IAA25943@math.berkeley.edu> To: holmes@catseye.idbsu.edu Subject: I now believe Status: RO Randall, Thanks to your latest letter I now believe the proof of (a) construction of a model of the axiom of counting via Construction 3; (b) getting a model of NFUA from a weakly compact cardinal. My actual process of verification consisted of (a) reading your proofs, definitely without full comprehension and then (b) going off and hacking out proofs of my own. My proof of the "counting" result is virtually identical with yours, but my proof of the weakly compact result is somewhat different [and I think slightly simpler]. One result of this method of proceeding is that I can't vouch for your proofs line by line. Of course, I now see that various comments I made about the likeliness of these results and proofs being correct were flat out wrong. To paraphrase Judge Ito, "That's life in the big city.". The upper bound and lower bound on the consistency strength of NFUA are starting to get awfully close. I will probably take a shot again at getting a Mahlo in L from NFUA. What I think should be easier [but have not yet done] is find a large cardinal axiom [probably very ad-hoc] strictly weaker than weakly compact cardinals and which yields the consistency of NFUA. Another project which looks viable to me is to show now that one can get an inaccessible limit of weakly compacts from NFUB. [I certainly don't have a clear idea as to how to do this yet.] This would settle that the two theories are of strictly different consistency strengths. As ever, Bob From holmes@catseye.idbsu.edu Wed Apr 26 10:17 MDT 1995 Received: by catseye.idbsu.edu (1.38.193.4/16.2) id AA15458; Wed, 26 Apr 1995 10:17:24 -0600 Date: Wed, 26 Apr 1995 10:17:24 -0600 From: Randall Holmes Return-Path: To: holmes@catseye.idbsu.edu, solovay@math.berkeley.edu Subject: Re: I now believe Status: RO I was thinking about the definition of a property of cardinals: Let kappa be an "NFUA cardinal" if it has the following property: If f is a map from [kappa]^n -> alpha, alpha < kappa, then there is an increasing sequence {x_i} of elements of kappa, indexed by the natural numbers, such that the image of any set of n _consecutive_ terms of the sequence under f is the same. Is an "NFUA cardinal" weakly compact, or is this a weaker property? It is tailored exactly to prove the existence of models of NFUA, of course! --Randall From holmes@catseye.idbsu.edu Wed Apr 26 10:20 MDT 1995 Received: by catseye.idbsu.edu (1.38.193.4/16.2) id AA15466; Wed, 26 Apr 1995 10:20:58 -0600 Date: Wed, 26 Apr 1995 10:20:58 -0600 From: Randall Holmes Return-Path: To: holmes@catseye.idbsu.edu, solovay@math.berkeley.edu Subject: Re: I now believe Status: RO Another point: I think that the strength of Jensen's proof of the consistency of Counting is misleading, because he proved counting by producing an omega-model, and the (inexpressible in first-order terms) assertion "All natural numbers are standard" is _much_ stronger than the Axiom of Counting; it implies full unstratified math induction for example, which is stronger than Counting! I'm glad that I had _something_ right :-) --Randall From holmes@catseye.idbsu.edu Wed Apr 26 10:22 MDT 1995 Received: by catseye.idbsu.edu (1.38.193.4/16.2) id AA15469; Wed, 26 Apr 1995 10:22:49 -0600 Date: Wed, 26 Apr 1995 10:22:49 -0600 From: Randall Holmes Return-Path: To: holmes@catseye.idbsu.edu, solovay@math.berkeley.edu Subject: Re: I now believe Status: RO A third remark: If you go on to read the Con(NFUA) -> Con(ZFC) construction, I'd like to write it up again; the main feature of this paper is that I am now severely dissatisfied with the way almost everything in it is written! The way it is written in the paper is too telegraphic, and misses some important points that need to be made! --Randall From solovay@math.berkeley.edu Wed Apr 26 18:18 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA16111; Wed, 26 Apr 1995 18:18:49 -0600 Return-Path: Received: by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id RAA11719; Wed, 26 Apr 1995 17:14:14 -0700 Date: Wed, 26 Apr 1995 17:14:14 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Message-Id: <199504270014.RAA11719@math.berkeley.edu> To: holmes@catseye.idbsu.edu Subject: Closing in for the kill Status: RO Randall, I'm glad to wait and read a revised writeup of Con(NFUA) -> Con(ZFC). Heres a theorem I can prove. Suppose that for every n, ZFC + exists an n-Mahlo is consistent. Then so is NFUA. I conjecture that this is sharp. That is for every n, I conjecture NFUA proves there is an n-Mahlo in L. Of course, this latest result supercedes your result that it there is a weakly compact, then NFUA is consistent. As ever, Bob From solovay@math.berkeley.edu Wed Apr 26 18:25 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA16115; Wed, 26 Apr 1995 18:25:36 -0600 Return-Path: Received: by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id RAA11893; Wed, 26 Apr 1995 17:21:01 -0700 Date: Wed, 26 Apr 1995 17:21:01 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Message-Id: <199504270021.RAA11893@math.berkeley.edu> To: holmes@catseye.idbsu.edu In-Reply-To: Randall Holmes's message of Wed, 26 Apr 1995 17:02:38 -0600 <199504262258.PAA09605@math.berkeley.edu> Subject: Homogeneous sets Status: RO Randall, You may well be right. I want to think about getting n-Mahlos from NFUA [which would settle things completely] before thinking about your question. It is of course still possible that the consistency strength of NFUA is very weak [less than a Mahlo], though at the moment I'm guessing the other way. As ever, Bob From solovay@math.berkeley.edu Wed Apr 26 23:34 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA16312; Wed, 26 Apr 1995 23:34:04 -0600 Return-Path: Received: by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id WAA17945; Wed, 26 Apr 1995 22:29:29 -0700 Date: Wed, 26 Apr 1995 22:29:29 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Message-Id: <199504270529.WAA17945@math.berkeley.edu> To: holmes@catseye.idbsu.edu Subject: the relevant reference Status: RO Journal of Symbolic Logic v. 37 (1972) On power-like models for hyperinaccessible cardinals,by James H. Schmerl and Saharon Shelah, pp. 531-537 Read sections 0 and 1; after understanding them, my result should be an easy exercise. [Alternatively, when you know this material, I can concisely explain my proof.] As ever, Bob From solovay@math.berkeley.edu Sun Apr 30 10:49 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA18649; Sun, 30 Apr 1995 10:49:32 -0600 Return-Path: Received: by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id JAA12989; Sun, 30 Apr 1995 09:44:54 -0700 Date: Sun, 30 Apr 1995 09:44:54 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Message-Id: <199504301644.JAA12989@math.berkeley.edu> To: holmes@catseye.idbsu.edu Subject: Radio silence Status: RO Randall, I hope my comments re the Shelah-Schmerl paper did not offend in some way. It really is true that one has to understand that paper to understand my improved upper bounds on the strength of NFUA. Very roughly, they show how from the stated large cardinal assumptions to construct a model of ZFC with something like a measure on the class of all ordinals. One can play the usual games with this "measure" getting indiscernibles and models of NFUA. The astonishing thing for me is that one gets a "measure" from such weak assumptions. Their proof uses compactness and one definitely does not get omega models. There is a companion paper of Schmerl in the Transactions of the AMS [the preciese reference is not at hand as I type] where he gives a combinatorial equivalent to n-Mahlo; I suspect that this will eventually yield the lower bounds, but that it will not be easy. [Despite comments to the contrary that I think I wrote, the paper itself is not terribly difficult to read or understand.] As ever, Bob From solovay@math.berkeley.edu Sun Apr 30 11:08 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA18654; Sun, 30 Apr 1995 11:08:43 -0600 Return-Path: Received: by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id KAA13134; Sun, 30 Apr 1995 10:04:05 -0700 Date: Sun, 30 Apr 1995 10:04:05 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Message-Id: <199504301704.KAA13134@math.berkeley.edu> To: holmes@catseye.idbsu.edu Subject: Missing reference Status: RO The Schmerl paper is in vol. 188 of the Transactions of the AMS (1974) on pages 281-291. --Bob From solovay@math.berkeley.edu Tue May 2 10:00 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA20148; Tue, 2 May 1995 10:00:32 -0600 Return-Path: Received: by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id IAA27878; Tue, 2 May 1995 08:55:51 -0700 Date: Tue, 2 May 1995 08:55:51 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Message-Id: <199505021555.IAA27878@math.berkeley.edu> To: holmes@catseye.idbsu.edu Subject: Package sent Status: RO A first class envelope [largeish] was sent yesterday with the two papers of Schmerl and the joint paper of Schmerl and Shelah. The joint paper is definitely relevant to the upper bound on the consistency of NFUA; of the two papers by Schmerl, I read through the one in the Transactions. At one time, I had hopes it would be directly relevant to the proofs of the corresponding lower bounds, but now I'm not so sure. My current thoughts are along the lines of ramping up the proof I sent you that one can get an inaccessible limit of inaccessibles in L, from NFUA. Alas, I must give a talk this Friday on a totally unrelated topic ["Quantum Turing Machines"], so I won't be spending much time on improved lower bounds for the consistency strength of NFUA in the next few days. It does seem now that this is significantly harder than the upper bounds, but problems often seem harder to me before they are solved. As ever, Bob From solovay@math.berkeley.edu Tue May 2 12:58 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA20407; Tue, 2 May 1995 12:58:06 -0600 Return-Path: Received: by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id LAA03754; Tue, 2 May 1995 11:53:20 -0700 Date: Tue, 2 May 1995 11:53:20 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Message-Id: <199505021853.LAA03754@math.berkeley.edu> To: holmes@catseye.idbsu.edu In-Reply-To: Randall Holmes's message of Tue, 2 May 1995 10:53:43 -0600 <199505021649.JAA29925@math.berkeley.edu> Subject: My sketch Status: RO Randall, I will add your sketch to my list of things to think about; my offhand reaction is that the class of things that "commute with T" is a lot less than the class of definable clubs. I conjecture that you will not be able to prove that Sigma_3 definable properties "commute with T" for example. I have been working with a class of properties that *do* commute with T which can be characterized as follows. In deciding P(alpha) one is allowed to ask questions about alpha in L_beta where beta is the $n^{th}$ cardinal in L after alpha. This is not the most general class of properties that can be shown to commute with T, but I don't know a clean definition of a maximal class. Module this observation, your sketch looks right to me, but I have **not** thought it through carefully. The whole problem of truly getting Mahlo cardinals in L is that the classes one encounters provably do not commute with T. [Like all offhand remarks take this last with a grain of salt; there is always the possibility that by reconceptualizing this difficulty can be made to go away.] It's hard to characterize the approach I am trying to push through now in a few words. But roughly, it tries to meet the difficulty head on rather than sidestep it. [If it works and doesn't simplify itself it will be a *long* and complicated proof. Not that I don't prefer simple proofs when I can find them!] As ever, Bob From holmes@catseye.idbsu.edu Tue May 2 13:07 MDT 1995 Received: by catseye.idbsu.edu (1.38.193.4/16.2) id AA20448; Tue, 2 May 1995 13:07:06 -0600 Date: Tue, 2 May 1995 13:07:06 -0600 From: Randall Holmes Return-Path: To: holmes@catseye.idbsu.edu, solovay@math.berkeley.edu Subject: Re: My sketch Status: RO I'm well aware that the class of things which commute with T is difficult to capture! This is why the argument I outlined doesn't seem to give any hint of how to get an actual Mahlo cardinal. This week is the last week of the semester here; I'm giving a final exam on Monday and then I will be free to work on writing up the Con(NFUA) -> Con(ZFC) argument. I think that this argument may contain some ideas which are useful for thinking about large cardinals in NFUA; it uses a kind of reflection property of the isomorphism classes of well-founded extensional relations in NFUA, and one might hope that better understanding of reflection properties (there might be better ones in L) might help in looking for things like Mahlo cardinals. --Randall From solovay@math.berkeley.edu Thu May 4 23:49 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA24285; Thu, 4 May 1995 23:49:22 -0600 Return-Path: Received: by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id WAA17105; Thu, 4 May 1995 22:44:40 -0700 Date: Thu, 4 May 1995 22:44:40 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Message-Id: <199505050544.WAA17105@math.berkeley.edu> To: holmes@catseye.idbsu.edu In-Reply-To: Randall Holmes's message of Thu, 4 May 1995 10:40:32 -0600 <199505041635.JAA27250@math.berkeley.edu> Subject: But it is involved! Status: RO Randall, I thought some about how to get Con(NFUA) directly from Schmerl's partition property, and it's not clear to me. [I could go from the partition property back to the n Mahlo's and then give my original proof, but that clearly is cheating. Don't worry about this till Monday. I would like to see your proof then if I haven't figured it out by then. As ever, Bob From solovay@math.berkeley.edu Thu May 11 18:44 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA01857; Thu, 11 May 1995 18:44:21 -0600 Return-Path: Received: by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id RAA09366; Thu, 11 May 1995 17:39:34 -0700 Date: Thu, 11 May 1995 17:39:34 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Message-Id: <199505120039.RAA09366@math.berkeley.edu> To: holmes@catseye.idbsu.edu Subject: Yes and No Status: RO Randall, Yes, I now see how to get the consistency of NFUA via the Schmerl partition principle. No, I do not quite believe your proof [though obviously, in view of my prior "Yes", I see a repair]. You assert without proof that if f(a_1,...,a_n) = f(a_2,..., a_{n+1}), then it follows that f(a_1,...,a_n) < a_0. I can cook up systems of functions where this is not the case. As ever, Bob From holmes@catseye.idbsu.edu Fri May 12 07:54 MDT 1995 Received: by catseye.idbsu.edu (1.38.193.4/16.2) id AA02087; Fri, 12 May 1995 07:54:40 -0600 Date: Fri, 12 May 1995 07:54:40 -0600 From: Randall Holmes Return-Path: To: holmes@catseye.idbsu.edu, solovay@math.berkeley.edu Subject: Re: Yes and No Status: RO Dear Bob, That assertion (that elements fixed under the automorphism are less than a_i's) _is_ true for any element of V_{a_0} (the domain of the model of NFUA); sorry for not making this clear (obviously it was not clear in my mind that I needed to point this out!). I did already know that other, larger objects in the nonstandard model of set theory being constructed may be fixed under the automorphism (I think that this may be inevitable; I would be interested to see a fix that avoids this, but I don't need it for this proof). But any element of _the model of NFUA_ is either of a rank below any a_i (and so fixed under the automorphism) or is of a rank between a_i's, and so is moved by the automorphism. --Randall From solovay@math.berkeley.edu Fri May 12 10:35 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA02185; Fri, 12 May 1995 10:35:49 -0600 Return-Path: Received: by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id JAA22967; Fri, 12 May 1995 09:31:02 -0700 Date: Fri, 12 May 1995 09:31:02 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Message-Id: <199505121631.JAA22967@math.berkeley.edu> To: holmes@catseye.idbsu.edu Cc: holmes@catseye.idbsu.edu In-Reply-To: Randall Holmes's message of Fri, 12 May 1995 07:54:40 -0600 <199505121349.GAA19758@math.berkeley.edu> Subject: Yes and No Status: RO Randall, I'm still not quite convinced. We know that ordinals less than a_0 are fixed. But why does it follow that elements of rank less than a_0 are fixed. I had two repairs, but here is the simplest one. Examining the proof of Schmerl's combinatorial principle shows that we can assume that all the indiscernibles lie in some preassigned stationary subset of the n-Mahlo. Unfortunately, Schmerl doesn't record this fact, but after you have been through the proof of his combinatorial principle, I can explain this refinement. here is how we get the desired sentences: By choosing a suitable club, we can insure the sentences f(a_1,...,a_n) < a_{n+1}. If also f(a_1,...,a_n) = f(a_2,...,a_{n+1}), then it follows that f(a_1,..,a_n) = f(a_{n+2},...,a_{2n+1}). Hence f(a_{n+2},...,a_{2n+1}) < a_{n+1}). So f(a_1,...,a_n) < a_0 as desired. We also can impose that the a_n's are inaccessible cardinals, so that the point I raised in the first paragraph of this letter is also handled. As ever, Bob From holmes@catseye.idbsu.edu Fri May 12 10:53 MDT 1995 Received: by catseye.idbsu.edu (1.38.193.4/16.2) id AA02202; Fri, 12 May 1995 10:53:36 -0600 Date: Fri, 12 May 1995 10:53:36 -0600 From: Randall Holmes Return-Path: To: holmes@catseye.idbsu.edu, solovay@math.berkeley.edu Subject: Re: Yes and No Status: RO Dear Bob, It is definitely necessary to require explicitly that a_i = beth{a_i}, so that the fact about elements of ranks works out correctly! This is enough; the a_i's don't need to be inaccessible (though it is hardly lavish to require this!). At this point you are bringing out things which I "know" implicitly about the construction but am forgetting to state :-( --Randall From solovay@math.berkeley.edu Fri May 12 13:24 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA02308; Fri, 12 May 1995 13:24:08 -0600 Return-Path: Received: by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id MAA29107; Fri, 12 May 1995 12:19:20 -0700 Date: Fri, 12 May 1995 12:19:20 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Message-Id: <199505121919.MAA29107@math.berkeley.edu> To: holmes@catseye.idbsu.edu Subject: Re: Yes and No Cc: solovay@math.berkeley.edu Status: RO How do you insure from the statement of the Schmerl principle that a_i = Beth_{a_i}? I don't off hand see how to do this. --Bob From solovay@math.berkeley.edu Fri May 12 13:26 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA02345; Fri, 12 May 1995 13:26:11 -0600 Return-Path: Received: by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id MAA29156; Fri, 12 May 1995 12:21:22 -0700 Date: Fri, 12 May 1995 12:21:22 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Message-Id: <199505121921.MAA29156@math.berkeley.edu> To: holmes@catseye.idbsu.edu Subject: Re: Corrections Cc: solovay@math.berkeley.edu Status: RO Randall, I don't have time to look at the latest version of your argument at this instant. I'll try to look at it shortly and comment on it. --Bob From solovay@math.berkeley.edu Sat May 13 13:34 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA02948; Sat, 13 May 1995 13:34:46 -0600 Return-Path: Received: by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id MAA24191; Sat, 13 May 1995 12:29:57 -0700 Date: Sat, 13 May 1995 12:29:57 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Message-Id: <199505131929.MAA24191@math.berkeley.edu> To: holmes@catseye.idbsu.edu Cc: holmes@catseye.idbsu.edu In-Reply-To: Randall Holmes's message of Fri, 12 May 1995 13:38:05 -0600 <199505121933.MAA29623@math.berkeley.edu> Subject: Corrections Status: RO Dear Randall, You write: The partition determined by the set of sentences Sigma is set up to categorize a sequence of ordinals (x_1...x_n) not by plugging the x_i's into the formulas but by plugging in the x_i'th fixed point of the beth operator in each case. Thus, the sentences are talking about the fixed points of the beth operator indexed by the ordinals below kappa (which are exactly the fixed points below kappa, of course). The C_alpha's are redefined in the same way. Reply: Yes this does it. I think this way of doing things [via the Schmerl partition relations] is cleaner than my earlier proof via Shelah-Schmerl. [I had to construct a set of indiscernibles in the other approach but got them via "iterated ultraproducts".] I'm still thinking hard about the converse, still optimistic, but still with nothing definitive to report. As ever, Bob From solovay@math.berkeley.edu Mon May 15 23:31 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA04019; Mon, 15 May 1995 23:31:57 -0600 Return-Path: Received: by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id WAA18648; Mon, 15 May 1995 22:27:02 -0700 Date: Mon, 15 May 1995 22:27:02 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Message-Id: <199505160527.WAA18648@math.berkeley.edu> To: holmes@catseye.idbsu.edu Subject: finally... Status: RO Randall, Here's a theorem [provable, say, in Peano Arithmetic]: For each integer n, NFUA proves the obvious formalization of "there is a non-Cantorian n-Mahlo cardinal". Joined with my earlier result, this shows that the consistency strength of NFUA is **exactly** ZFC plus the following scheme: For each integer n, there is an axiom: "There is an n-Mahlo cardinal". The proof is somewhat more involved than my earlier result that NFUA proves the existence of inaccessibles in L. Unless I hear a declaration of non-interest, I will start drafting a series of letters communicating the proof. [The metatheory I will work in will be second-order number theory, but I could, if I chose, prove the theorem in the fragment "IDelta_0 + Exp" of Peano Arithmetic.] As ever, Bob From solovay@math.berkeley.edu Mon May 15 23:58 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA04024; Mon, 15 May 1995 23:58:22 -0600 Return-Path: Received: by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id WAA18993; Mon, 15 May 1995 22:53:32 -0700 Date: Mon, 15 May 1995 22:53:32 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Message-Id: <199505160553.WAA18993@math.berkeley.edu> To: holmes@catseye.idbsu.edu Subject: Outline of the proof Status: RO Usual disclaimer: I think this proof is right and I've "thought through all the details" in my head, but this is the first time I've committed it "to paper" and a bug may emerge at any point. For the following two definitions, [which I will not give precisely in this outline] the theory in which we work is ZFC + V=L. We will introduce a property of a limit cardinal, lambda, and an increasing n+1-tuple of ordinals xi_0,...,xi_n of the tuple being lambda-good. The intuition is that lambda is a supply of ordinals certified cantorian, and for some j [an elementary embedding] j(xi_i) = xi_{i+1}. [This is by no means the literal definition!] We will be able to prove in NFUA that there are natural ["well-founded, subset absolute"] models of V=L + ZFC + for some limit cardinal lambda, there is an n+1-tuple that is lambda good. [This is a theorem scheme.] By a process reminiscent of the construction of a normal measure on a measurable cardinal, we will be able to show that if there is a good n+1-tuple for lambda, there is a "superb" [definition omitted in this outline] n+1-tuple for lambda. Finally, in ZFC + V=L, we will be able to prove that if lambda is a limit cardinal and xi_0,...,xi_{n} is a superb tuple for lambda, then all the xi_i's are n-Mahlo. [This is a theorem scheme proved by induction on n in the metatheory.] That's the high level outline. Of course, many details must be added to convert it into a proof. As ever, Bob From solovay@math.berkeley.edu Tue May 16 02:09 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA04037; Tue, 16 May 1995 02:09:04 -0600 Return-Path: Received: by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id BAA21244; Tue, 16 May 1995 01:04:14 -0700 Date: Tue, 16 May 1995 01:04:14 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Message-Id: <199505160804.BAA21244@math.berkeley.edu> To: holmes@catseye.idbsu.edu Subject: The proof--part 1 Status: RO The goal of this and the next two letters is to define the notions of lambda good and lambda superb. In all these letters, we are working in the theory ZFC + V=L. For this letter, our goal is to introduce the class of local functions. There will be countably many local functions, one for each formula phi of the language of set theory whose free variables are an initial segment of the variables. So let phi be a formula such that the variables occuring free in phi are v_0,...,v_n. We will define a function f_phi:Or^n --> Or. The intuition is that to compute f_phi(alpha_1,...,alpha_n) one goes to L_beta where beta is the least cardinal greater than alpha_1,...,alpha_n and then uses the definition phi. Precisely, if there is exactly one ordinal eta such that L_beta thinks phi(eta,alpha_1,...,alpha_n) then f_phi(alpha_1,...,alpha_n) = eta; otherwise, it equals 0. There is also a notion of a local predicate. This has the normal form f(alpha_1,...,alpha_n) = 0. The crucial property of local functions and predicates is that they are absolute from L_gamma to L whenever gamma is a strong limit cardinal. Moreover, the predicates "is singular" or "is n-Mahlo" are local. Via the usual well-ordering of L, it makes sense to ask if a map from say Or--> L is local, and the following maps are local: The map which assigns to a singular limit ordinal a closed cofinal subset of order type its cofinality. The map which assigns to an inaccessible cardinal which is not n+1-Mahlo a closed cofinal subset which is disjoint from the n-Mahlo cardinals. [These maps should be viewed as 0 outside their natural domains. The local maps are closed under compositions and contain the projection functions. This ends letter 1. From solovay@math.berkeley.edu Tue May 16 10:27 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA04267; Tue, 16 May 1995 10:27:21 -0600 Return-Path: Received: by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id JAA27817; Tue, 16 May 1995 09:22:30 -0700 Date: Tue, 16 May 1995 09:22:30 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Message-Id: <199505161622.JAA27817@math.berkeley.edu> To: holmes@catseye.idbsu.edu Subject: The proof--part 2 Status: RO The goal of the present letter is to introduce the concept "lambda good". Here is the context. We are working in the theory ZFC + V=L. lambda is a limit cardinal greater than omega. xi_0,...,xi_n is a tuple of ordinals that is either strictly increasing or strictly decreasing. The tuple is lambda good if the following two conditions are met: (1) whenver (a) f is a local function which maps OR^{n+1} to OR; (b) eta is an ordinal less than lambda; and one of f(eta,xi_0,...,xi_{n-1}) and f(eta,xi_1,...,xi_n) is less than lambda, then they both are and they are equal. (2) whenever (a) f is a local function which maps OR^{n+1} to OR; (b) eta is an ordinal less than lambda; and f(eta,xi_0,...,xi_{n-1}) = f(eta,xi_1,...,xi_n) then the common value is less than lambda. This ends the notion of lambda good. Here are some easy consequences of the definition: 1) Let r be an integer with 1 <= r <= n. Let i_1,..., i_r be integers with 0 <= i_1 < ... < i_r < n. Let k be a positive integer and let j_s = i_s + k for all s with 1 <= s <= r. We suppose also that j_r <= n. [Thus the sequence of j's is just a shift of the sequence of i's.] Let f be a local function with domain OR^{r+1} and eta an ordinal less than lambda. Then the obvious analogues of (1) and (2) above for f(eta,xi_{i_1},...,xi_{i_r}) and f(eta,xi_{j_1},...,xi_{j_r}) obtain. 2) There is a "shift indiscernibility" property for local properties that follows from the way we have defined local properties from local functions. 3) We have lambda <= xi_j whenever 0 <= j <= n. It is easy to see that if kappa is say n+100-Mahlo, then there is a limit cardinal lambda < kappa, and ordinals xi_0,..., xi_n less than kappa such that the xi's are lambda good. We don't need this last observation for our proof, however. So ends part 2 of the proof. From solovay@math.berkeley.edu Tue May 16 10:55 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA04285; Tue, 16 May 1995 10:55:09 -0600 Return-Path: Received: by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id JAA28799; Tue, 16 May 1995 09:50:18 -0700 Date: Tue, 16 May 1995 09:50:18 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Message-Id: <199505161650.JAA28799@math.berkeley.edu> To: holmes@catseye.idbsu.edu Subject: The proof--part 3 Status: RO The goal of this letter is to give the definition of a tuple being lambda superb and prove that if there is an n+1-tuple that is lambda good, then there is one that is lambda superb. The context is that of our previous letter. Thus we work in the theory ZFC + V=L. lambda is a strong limit cardinal greater than omega. A tuple xi_0,...,xi_n is lambda superb iff: 1) the tuple is lambda good; 2) whenver eta is an ordinal less than lambda, and f is a local function with domain OR^2 such that f(eta,xi_0) < xi_0, then f(eta,xi_0) < lambda. This completes the definition. Suppose then that xi_0,...xi_n is lambda good. We show how to build a tuple gamma_0,..., gamma_n which is lambda superb. Choose a local function f and an eta < lambda such that (1) f(eta, xi_0) >= lambda; (2) subject to (1), f(eta,xi_0) is as small as possible. Now set gamma_i = f(eta,xi_i). A routine verification [which we leave to the reader] shows that gamma_0,..., gamma_n is a lambda superb n+1-tuple. This ends letter 3. Our next letter will show how to construc models of ZFC + "there is a good n+1-tuple" starting from models of NFUA. From solovay@math.berkeley.edu Tue May 16 12:12 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA04307; Tue, 16 May 1995 12:12:44 -0600 Return-Path: Received: by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id LAA01640; Tue, 16 May 1995 11:07:49 -0700 Date: Tue, 16 May 1995 11:07:49 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Message-Id: <199505161807.LAA01640@math.berkeley.edu> To: holmes@catseye.idbsu.edu Subject: The proof--part 4 Status: RO Here we show how to get good tuples starting from models of NFUA. The following is a theorem scheme [in the integer variable n] in NFUA: There is an L inaccessible, Omega, such that L_Omega thinks: There is a limit cardinal lambda, and ordinals xi_0,..., xi_n such that the tuple xi-vector is lambda good. In proving this, I will, as in my earlier argument, adopt the Specker formalism: So Omega is the order-type of the least well-ordering of V. There are analogues of Omega at each level: Omega_n is the analogue of Omega at level n. We may and do assume that Omega_n is an initial segment [proper!] of Omega_{n+1}, and that L_{Omega_n} is a transitive set in L_{Omega_{n+1}. THere is an automorphism j which carries L_{Omega_n} isomorphically onto L_{Omega_{n+1}. Care is needed in working with j, since it is not allowed to directly appear in comprehension axioms. The ordinal Omega need not be inaccessible. However, my earlier proof showed that there is a non-Cantorian ordinal theta < Omega such that theta **is** inaccessible in L. We let theta_i be the analogue of theta at level i. One annoying fact is that we cannot prove that j(theta) > theta. If in fact j(theta) < theta, we reinitialize the notaion, replacing theta_i by theta_{-i} and j by j^{-1}. So we have seen how to insure that [after reinitializing the notation] the Omega_i's are all inaccessible in L. Here ends the current letter. Of course, we are in the midst of the proof of the stated theorem scheme in NFUA. From solovay@math.berkeley.edu Wed May 17 23:08 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA05186; Wed, 17 May 1995 23:08:48 -0600 Return-Path: Received: by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id WAA01024; Wed, 17 May 1995 22:03:56 -0700 Date: Wed, 17 May 1995 22:03:56 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Message-Id: <199505180503.WAA01024@math.berkeley.edu> To: holmes@catseye.idbsu.edu Subject: The proof-part 6 Status: RO One minor point. Note that an ordinal alpha is fixed by j iff it is fixed by j^{-1}. So even after reinitializing notation, it is true that if alpha is fixed by j and beta is less than alpha, then beta is fixed by j. We will take as our model of ZFC + V= L the model M = L_{Omega_{n+1}}. The tuple which will eventually be shown to be lambda good for a suitable lambda will be Omega_0,...,Omega_n. The lambda which will actullay be shown to work eventually will be built in M by a certain construction which we now describe. We will define a certain strictly increasing sequence of ordinals . lambda will be the sup of this sequence of ordinals. To start things off, we set lambda_0 = omega. Suppose that lambda_n has been defined. We show how to define lambda_{n+1}. This will be the sup of various ordinals: (a) The least cardinal greater than lambda_i. [This clause will insure that lambda is indeed a limit cardinal and that the sequence of lambda_i's is strictly increasing.] (b) all ordinals of the form f(eta,Omega_0,...,Omega_{n-1}) where f is a local function of the appropriate number of variables, and eta is an ordinal less than lambda_i **and**: f(eta,Omega_0,...,Omega_{n-1}) = f(eta,Omega_1,...,Omega_n). Our construction makes trivial one of the two clauses for lambda-good. Towards the other, let s be the function with domain omega such that s(i) = lambda_i. Of course, s lies in M, since the whole construction has taken place in M. Let s' = j(s). Claim: s = s'. Suppose not toward an eventual contradiction. Clearly, s' is also an omega sequence of ordinals, and since, by the Cantorian axiom, j fixes all the non-negative integers, s'(n) = j(s(n)). So it suffices to prove that all the s(n)'s are fixed by j. Suppose not. Note that the set of integers m of the model M such that s(m) is unequal to s'(m) is a set of M. So if it is non-empty, it has a least member. This least member can't be 0 since s(0) = omega which is fixed by j. So it has the form k+1. Thus to prove our claim that s = s' it suffices to show the following: if lambda_k is fixed by j, then so is lambda_{k+1}. This a good place to end the current letter. From solovay@math.berkeley.edu Wed May 17 23:39 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA05191; Wed, 17 May 1995 23:39:38 -0600 Return-Path: Received: by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id WAA01532; Wed, 17 May 1995 22:34:46 -0700 Date: Wed, 17 May 1995 22:34:46 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Message-Id: <199505180534.WAA01532@math.berkeley.edu> To: holmes@catseye.idbsu.edu Subject: The proof--part 7 Status: RO Recall that lambda_k is fixed by j and that we are trying to show that lambda_{k+1} is also fixed by j. Now lambda_{k+1} is the sup of two things (a) the least cardinal greater than lambda_k and a set of ordinals which we will recall in a moment. It is obvious that the cardinal successor of lambda_k is fixed by j, so we turn our attention to the other term in the sup. Godel number the local functions of n+1 variables in some reasonable way. Let D be the set of all pairs such that i is the Godel number of a local function of n+1 variables, and eta is less than lambda_k. It is evident that j(D)= D and that D is pointwise fixed by j. Remark:It is a consequence of V=L and the Cantorian axiom that each set fixed by j is also pointwise fixed by j. But the current special case is particularly clear. Define a function F with domain D as follows. [We are working in the model M.] Let be an element of D. Let f be the local function with Godel number i. Then F() = f(eta,Omega_0,...,Omega_{n-1}). Note that the local function f is absolute to L_{Omega_n}, and hence the function F just described sits in L_{Omega_n}. Let F' = j(F). Clearly F' is a function with domain D. Moreover, using the absoluteness of local functions which we have just recalled, we see that F'() = f(eta,Omega_1,...,Omega_n). Working in M, let E be the subset of D consisting of those points of D at which F and F' take the same value. Then since E is a subset of D, j(E) = E. Let G be the restriction of F to E and let G' be the restriction of F' to E. Then clearly G = G' since they are functions with the same domain which take the same value at every point of their common domain. Moreover, it is evident that G' = j(G), since G' is the restriction of j(F) to j(E). The upshot is that j(G) = G. It then follows that the supremum of the range of G is fixed by j. But this is precisely the other term contributing to the definition of lambda_{k+1}. It is now evident that lambda_{k+1} is fixed by j. Our proof of our claim that s = s' is complete. An immediate corrolary of the claim just proved is that every ordinal less than lambda is fixed by j. Now suppose that f(eta,Omega_0,...,Omega_{n-1}) = theta, where f is a local function and theta and eta are both less than lambda [and hence fixed by j]. We have already seen that j commutes with local functions. Hence applying j to this equality, we get: f(eta, Omega_1,...,Omega_n) = theta. Similarly, if f(eta,Omega_1,...,Omega_n) = theta, [with f, theta, eta as above] then applying j^{-1} we conclude that f(eta,Omega_0,...,Omega_{n-1}) = theta. Our proof that Omega,0,...,Omega_n is lambda good in M is complete. So ends letter 7. From solovay@math.berkeley.edu Thu May 18 01:51 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA05207; Thu, 18 May 1995 01:51:48 -0600 Return-Path: Received: by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id AAA03152; Thu, 18 May 1995 00:46:35 -0700 Date: Thu, 18 May 1995 00:46:35 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Message-Id: <199505180746.AAA03152@math.berkeley.edu> To: holmes@catseye.idbsu.edu Subject: The proof--part 8 Status: RO Let me make explicit the definition of some terminology I've been using. A cardinal is 0-Mahlo iff it is inaccessible. A cardinal kappa is n+1-Mahlo iff it is inaccessible and the set of n-Mahlo's less than kappa is stationary in kappa. The following will be shown to be a theorem of ZFC + V=L: Let lambda be a limit cardinal. Let kappa_0,...kappa_{n+1} be lambda superb. Then each of the kappa_i's is n-Mahlo. Once we establish this result, the stated lower bound on the consistency strength of NFUA will be completely proved. Note that it is evident that either all the kappa_i's are n-Mahlo or none of them are. [This uses only that the kappa_i's are lambda good.] The proof is by induction on n and the current letter will consider only the case when n = 0. Without loss of generality, we assume that kappa_0 < kappa_1. We consider various cases [each of which will be shown to be absurd]: Case 1: kappa_0 <= omega. This case can't arise since omega < lambda <= kappa_0 Case 2: kappa_0 is not a cardinal. There is a local function f such that f(0,gamma) is the cardinal of gamma. So f(0,kappa_0) < kappa_0. Since the kappa's are lambda superb, we have f(0,kappa_0) < lambda. But lambda is a limit cardinal. So it follows that kappa_0 < lambda which is absurd. Case 3: kappa_0 is a sucessor cardinal. There is a local function f such that if kappa is a successor cardinal, then f(0,kappa) is the cardinal predecessor of kappa. So f(0, kappa_0) < kappa_0. Since the kappa's are lambda superb, f(0,kappa_0) < lambda. But lambda is a limit cardinal. It follows that kappa_0 < lambda which is absurd. Case 4: kappa_0 is a singular strong limit cardinal. There is a local function f such that f(0,kappa) = cf(kappa). Since the kappa's are lambda superb, it follows that cf(kappa_0) = cf(kappa_1) = gamma for some gamma < lambda. There is a local function g which does the following: Let kappa be singular and let eta < cf(kappa). Let h be the L-least map of cf(kappa) cofinally into kappa. Then g(eta,kappa) = h(eta). Now let h_0 and h_1 be the L-least maps of gamma cofinally into kappa. Since the kappa's are lambda superb, we have h_0(eta) = g(eta,kappa_0) = g(eta,kappa_1) = h_1(eta). The upshot is that h_0 = h_1. But then kappa_0 = kappa_1 which is absurd. Since each of these cases has led to a contradiction, we conclude that kappa_0 and kappa_1 are inaccessible cardinals. This completes the basis part of our inductive proof and with it letter 8. From solovay@math.berkeley.edu Thu May 18 02:27 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA05216; Thu, 18 May 1995 02:27:32 -0600 Return-Path: Received: by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id BAA03703; Thu, 18 May 1995 01:22:40 -0700 Date: Thu, 18 May 1995 01:22:40 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Message-Id: <199505180822.BAA03703@math.berkeley.edu> To: holmes@catseye.idbsu.edu Subject: The proof--part 9 Status: RO The situation is the following. We are working in the theory ZFC + V=L. We know that whenever lambda is a strong limit cardinal, and gamma_0,...,gamma_{n+1} is lambda superb, then the gamma_i's are n-Mahlo. We are given kappa_0,...kappa_{n+2} which are lambda superb. We have to show that they are all n+1-Mahlo. It is evident that kappa_0,..., kappa_{n+1} are lambda superb. Hence we know [using our inductive hypothesis] that all the kappa_i's are n-Mahlo. Suppose towards a contradiction that not all the kappa_i's are n+1-Mahlo. It follows that none of the kappa_i's are n+1-Mahlo. What does this mean. it means that for each i, there is a set C_i which is club in kappa_i and which contains no n-Mahlo cardinal. We take C_i to be, in fact, the L-least subset of kappa_i with this property. Without loss of generality, we assume that kappa_0 < kappa_1 < ... < kappa_{n+2}. Note that C_0 is unequal to C_1 intersected with kappa_0. For if not, C_1 would have kappa_0 as a limit point and hence kappa_0 would be a member of C_1. But kappa_0 is n-Mahlo, and C_1 contains no n-Mahlo cardinals, which gives a contradiction. There is a local function f:OR^3 --> OR with the following property: If kappa_0 and kappa_1 are not n+1-Mahlo but are n-Mahlo, and C_0 and C_1 are the L-least witnesses that kappa_0 and kappa_1 are not n+1-Mahlo, then f(0,kappa_0,kappa_1) is the least gamma which is in precisely one of C_0 and C_1. Our preceding discussion has shown that f(0,kappa_0,kappa_1) < kappa_0. We show next that f(0,kappa_0,kappa_1) is >= lambda. Suppose not. Then f(0,kappa_0,kappa_1) = f(0,kappa_1,kappa_2). We consider two cases. Case 1: f(0,kappa_0,kappa_1) is in C_0. Then by shift indiscernibility, f(0, kappa_1,kappa_2) is in C_1. But f(0,kappa_0,kappa_1) = f(0,kappa_1,kappa_2). So f(0,kappa_0,kappa_1) is in C_1. But the ordinal f(0,kappa_0,kappa_1) is in precisely one of C_0 and C_1. Contradiction. Case 2: f(0,kappa_0,kappa_1) is in C_1. This case can be handled exactly like case 1. Now define a local function g and an ordinal eta by the following requirements: g(eta,kappa_0,kappa_1) is >= lambda, and is as small as possible subject to that. eta is as small as possible subject to this constraint, and modulo the choice of eta, g has minimal Godel number. Let gamma_i = g(eta,kappa_i, kappa_{i+1}). Then it is easy to see that gamma_0,..., gamma_{n+1} are lambda superb. Hence by induction hypothesis, they are n-Mahlo. Notice that g(eta,kappa_0,kappa_1) <= f(0,kappa_0,kappa_1). It follows that gamma_0 < kappa_0. Since gamma_0 is n-Mahlo, it is not in C_0. Since C_0 is closed, we define an ordinal theta_0 as the sup of C_0 intersect gamma_0. Since theta_0 < gamma_0 and has the form h(eta', kappa_0, kappa_1) for some local h and some eta' < lambda, we have theta_0 < lambda. Now consider theta* which is the least member of C_0 greater than theta_0. Then theta* can be obtained from theta_0 and kappa_0 by applying a local function. Since the kappa_i's are lambda superb, and theta_0 is less than lambda, we conclude that theta* is less than lambda. But clearly, gamma_0 < theta*. So gamma_0 is less than lambda, which is contrary to the definition of the gamma's. Our assumption that the kappa's are not n+1-Mahlo has led to a contradiction. This completes the proof and with it letter 9. From solovay@math.berkeley.edu Thu May 18 02:57 MDT 1995 Received: from math.Berkeley.EDU by catseye.idbsu.edu with SMTP (1.38.193.4/16.2) id AA05221; Thu, 18 May 1995 02:57:01 -0600 Return-Path: Received: by math.berkeley.edu (8.6.10/1.33(math)Ow.1) id BAA03753; Thu, 18 May 1995 01:27:05 -0700 Date: Thu, 18 May 1995 01:27:05 -0700 From: solovay@math.berkeley.edu (Robert M. Solovay) Message-Id: <199505180827.BAA03753@math.berkeley.edu> To: holmes@catseye.idbsu.edu Subject: All done Status: RO I've sent you nine letters which contain my proof of the optimal lower bound on the cosistency strength