Date: Fri, 21 Apr 2000 23:46:54 -0700 (PDT)
Subject: NFU*: Letter1

Randall,

	Here starts my series of letters about my results on NFU*. I
will follow the same conventions as I did in my presentation about the
proofs concerning NFUA. That is, it will take me a series of
letters. How much I gewt to in a particular letter will depend  on
when my time and energy runs out.

	There is also the usual problem of saying too little [or too
much]. If I say something is obvious or well-known and and it's not
for you, **please** let me know. 

	At some point, I may start transmitting these letters as some
incarnation of TeX file (e.g. dvi files or ps files). I'm in the
process of changing the detailed way I produce TeX files and I need to
experiment with various macro packages. If I try them on this series
of letters, I can kill two birds with one stone. Of course, if it
turns out to be too much hassle for you to print up the TeX stuff, I
can revert to ascii letters.

	Let's start by being sure we are talking about the same
things:

	1) By NFU* I mean the theory NFU [including choice and
infinity] together with the following additional axioms:

	(a) The axiom of counting: omega is strongly cantorian.

	(b) Selection for strongly cantorian sets: If x is strongly
cantorian, and phi is a formula [no stratification restrictions
imposed and parameters allowed], then the set of all y in x such that
phi(y) exists. [Of course, this is a scheme of axioms.]

	2) Next I want to describe the ZFish theory which will be
proved to have the same consistency strength:

	(a) First we will have ZC. This is all the axioms of ZFC
except the replacement axiom. In particular, it has the selection
scheme for arbitrary formulas.

	(b) Then we will have replacement for formulas that are
Sigma_2 in the Levy hierarchy. Since we have full selection, we don't
have to worry about the issue of the domain of the function under
consideration. We get an equivalent version of the axiom if we require
that the domain of the function in question is an ordinal. [To get
things started if we do this, we should throw in an axiom giving
Mostowski collapse, so that we have the usual theory of Von Neumann
ordinals at hand.]

	It is true that Sigma_2 replacement can be expressed as a
finite set of axioms. This isn't important for us, however.

	What is important is that the theory described in 2) holds in
L if it holds in V.  I view this result as
"well-known". It is not, however, completely trivial.

	So the main theorem is that NFU* is consistent iff ZC +
Sigma_2 replacement is consistent. The proof can be formalized in PRA
[primitive recursive arithmetic]. But I won't insist on this, and all
I am officially claiming is that the equiconsistency proof can be
carried out in second order aritmetic [or what comes to the same
thing, ZF-].

	As seems to be the custom in this sort of thing, the two
directions of the equiconsistency are by totally different
arguments. The direction getting Con(ZC + Sigma_2 replacement) from
Con(NFU*) is quite a bit easier, and I will start [and probably
finish] that proof in the next letter.

	One final remark. I expected the consistency strength of NFU*
to be much stronger than it turned out to be. On first glance, it
looks rather similar to NFUB.

	This ends letter #1.

	To be continued ...

	--Bob

Date: Sat, 22 Apr 2000 19:25:39 -0700 (PDT)
Subject: NFU*: Letter 2

	We are given a model of NFU*. Our goal is to construct a model
of ZC + Sigma_2 replacement.

	Let the given model of NFU* be M, with epsilon relation
epsilon_M.

	Let Z be as usual the set of isomorphism classes of
extensionial topped well-founded relations. We write epsilon_Z for the
epsilon relation on Z.

	We define a subclass of Z, W as follows: An equivalence class
z in Z will lie in W, if the underlying set of any representative is
strongly cantorian. W is, in the obvious sense, a transitive subclass
of Z. 

	We equip W with the epsilon relation which is the restriction
of epsilon_Z to W. We shall show that W is a model of ZC + Sigma_2
Replacement. 

	Because of the many epsilon relations floating around, I am
taking a little license in describing things. Thus, really, epsilon_W
is an ordinary binary relation on W. And W is really a subset [in the
sense of the metatheory] of the [ordinary] set whose members are those
things that M thinks are members of Z. But I shall ignore such fine
points for the most part.

	It is quite straightforward to see that W is a model of
ZC. The axiom of infinity holds in W since the axiom of counting holds
in M. And the selection schema holds in W since "selection for
strongly Cantorian sets" holds in M.


	We know that for any ordinal alpha of W, Beth_alpha exists in
Z. Using induction on alpha, we can see that in fact for any alpha in
W, Beth_alpha exists in W.

	Recall that an ordinal alpha is a Beth fixed point [we will
abreviate this bfp] if alpha = Beth_alpha. Using full induction on
omega [which is available in NFU*] and the result of the preceding
paragraph, it is easy to see that for any alpha in W, there is a bfp
beta in W which is greater than alpha.

	An ordinal alpha is a limit of Beth fixed points [we abreviate
this lbfp] if it is greater than 0 and for any eta < alpha, there is a
bfp beta with eta < beta < alpha. Clearly any lbfp is a bfp.

	Again, it is easy to see that if alpha is in W, there is a
lbfp beta in W with alpha < beta.

	Note that it is now clear [since W is an initial segment of Z
which is a model of ZFC-] that the Mostowski collapse theorem holds in
W. [In fact, it was clear at the instant that W was defined.]

	We next need to recall the Levy collapse lemma [which we view
as a theorem of ZFC-:

	Let kappa be an uncountable cardinal. Let H(kappa) be the
collection of all sets whose transitive closure has cardinality less
than kappa. Then if the parameters of a Sigma_1 formula phi(x) lie in
H(kappa) and there is an x such that phi(x). then there is an x in
H(kappa) such that phi(x) [and conversely]. We express this by saying
that H(kappa) is absolute for Sigma_1 formulas.

	Now an uncountable cardinal kappa is a bfp iff V_kappa =
H(kappa). It follows that if beta is a bfp, then V_beta is absolute
for Sigma_1 formulas.

	We now return to the task of proving that Sigma_2 replacement
holds in W. Let G be a Sigma_2 function with domain an ordinal delta
in W. We have to show that the range of G is a member of W.

	We introduce an auxilliary function H. H(alpha) is defined iff
alpha < delta. If so, H(alpha) is the least beta such that:
	(1) beta is a bfp
	(2) The Sigma_2 definition of G(alpha) works in V(beta) to
define G(alpha).
	(3) beta is the least ordinal satisfying (1) and (2).

	The following points should be clear:

	(1) In W, H is defined on all of delta.
	(2) The same definition works in Z to define a function on
delta.

	And it defines the same function in Z that it does in W.

	But Z is a model of ZFC-. So the sup of the range of H exists
in Z. But it is the sup of strongly cantorian ordinals, hence itself
strongly cantorian. That is, the range of H is bounded in W.

	It is now clear that the range of G is a set in W.

	This completes our verification that Sigma_2 Replacement holds
in W and with that our proof that Con(NFU*) entails Con(ZC + Sigma_2
Replacement). 

	This ends letter 2.

	--Bob


Date: Sun, 23 Apr 2000 20:40:15 -0700 (PDT)
Subject: NFU*: The hard direction--preliminary outline

We turn now to the reverse direction of our equiconsistency result. We
are going to present three results which will converge to the final
proof.

	A) Work in ZFC + V=L + "There is an inaccessible
cardinal". There is a model of NFU*.

	[In fact this proof is easily modified to get a model whose
strongly cantorian sets are a model of ZFC.]

   Question:  Is the strength of NFU + Choice + Counting +
   Replacement for s.c. sets the same as the strength of ZFC?

	The proof of A) is modeled on Jensen's proof that for any
ordinal alpha, there is a model of NFU whose standard part is alpha.
Like Jensen's proof the model is constructed in a length omega
construction. Unlike Jensen's proof, the value of alpha is not known
in advance. Instead it is dynamically generated by the construction.

	During the course of the construction we will consider terms
that denote Cantorian ordinals. We will take steps to insure that one
of the following alternatives happens:

	(a) The value of the term is less than alpha;

	(b) There is a non-Cantorian ordinal whose value is less than
the value of the term.

	We could easily arrange that the proof of part A takes place
in ZFC [rather than ZFC + "There is an inaccessible" + V=L].

	Part B is obtained by optimizing part A: We prove in ZF- that
if there is a model M of 

	ZC + Sigma_3 Replacement 

then there is a model of V=L.

	There are various technical complications involved in the
transition from part A to part B:

	1) The model M need not be an omega model. This causes no real
problems, but it requires all constructions to be done "internal to
M".

	2) What plays the role of alpha is now the class of ordinals
of M. The model of NFU* we construct is a proper class of M.

	In part C, we prove our final result [in ZF-]: If there is a
model of ZC + Sigma_2 Replacement, then there is a model of NFU*.

	The proof uses a variant (due to Barwise) of the Barwise
compactness theorem. The ideas of infinitary logic and infinitary
proofs play a crucial role in the the improvement from part B to
part C. In addition, while the use of L was mainly a convenience in
parts A and B, it seems to play an essential role in part C.

	This ends the high level outline of what we are going to do
and with it letter 3. In the next letter, I review term models
[essentially these are EM blueprints] and state sufficient conditions
on a term model to yield a model of NFU*.

Date: Tue, 25 Apr 2000 23:18:54 -0700 (PDT)
Subject: NFU*: Description of the term language


We begin phase A of the proof of the converse direction. We are
working in the metatheory ZFC + V=L + "There is an inaccessible
cardinal theta".

We start by defining the concepts of term language and term
model. [These concepts are really rather trivial.] Then we list
various conditions on a term model and show that if we can meet them
we can generate a model of NFU*. Finally, we will give a construction
of a term model meeting these requirements. This will complete phase A
of the proof.

A term language is just a language for first-order logic which has
only the predicate =. The following concepts make sense for such a
language: term; closed term.

A term-model is an equivalence relation on the closed terms so that
the resulting structure satisfies the equality axioms. More
explicitly, if == is the equivalence relation, f is an n-ary function
symbol of the term language, t_1, ..., t_n, and s_1, ..., s_n are
closed terms of the language such that for 1 <= i <= n we have s_i ==
t_i holding in the term model, then 

	f(s_1, ...,s_n) == f(t_1, ...,t_n) 

holds in the term model. 

	##########################################################

	Let us now spell out the particular term language which we
will employ in the proof. As I remarked previously, it will depend on
the choice of a certain cardinal alpha < theta. The precise value of
alpha will be determined in the course of the construction that
underlies our proof.

	Our language will have an infinite stock of variables x_i (for
i in omega).

	For each ordinal gamma < alpha, there will be a corresponding
constant gamma_bar. [The intended meaning of gamma_bar is gamma.]

	For each i in Z [Z is the set of integers, positive, negative
or zero] there will be a constant xi_i.

	The intuition is that the xi_i's are a generating set of
indiscernibles. It will turn out that our term-model converts
naturally to a model of a set-theory somewhat stronger than KP +
MacLane Set Theory plus V= L. In that "model of set-theory" the xi_i's
will be lbfp's and the map which sends i to xi_i will be order
preserving. [That map will not be a set of the "model of set theory"
arising from the term model, of course.]

	For each positive integer n, and each non-negative integer i,
there will be an n-ary function symbol f_{n,i}. We can explain the
intended meaning of these by telling what their canonical
interpretation is in a model of the form L_lambda [where lambda is a
lbfp].

	So let lambda be as stated. Let n, i meet the restrictions
just given. Let a_1, ..., a_n be elements of L_lambda.

	We fix a Godel numbering of the formulas of the language of
set-theory. [This is the first order language with no constant or
function symbols and with just two predicates [both binary] one for =
and one for epsilon.]

	To abbreviate, we write f for f_{n,i}.

	If i is not the Godel number of a formula of set-theory whose
free variables are a subset of {x_0, ..., x_n} then f(a_1, ..., a_n) =
0.

	Suppose we are not in this case. Let phi(x_0, ...,x_n) be the
formula with Godel number i.

	Let delta be the least bfp such that a_1, ..., a_n are members
of L_delta.

	delta < lambda since lambda is a lbfp.

	If, in L_delta, there exists an a such that L_delta thinks
that phi(a,a_1, ..., a_n), then f(a_1, ..., a_n) is the L-least such
a.

	If there is no such a, then f(a_1, ..., a_n) = 0.

	Finally, our term language will have for each i in omega,
a unary function h_i.

	The meaning of the h_i's will be decided in the course of our
construction. We shall employ this freedom to arrange that in the
final model of NFU* the strongly cantorian ordinals correspond
precisely to the ordinals less than alpha.

	We remark that the functions f_{n,i} play roughly the same
role that the local functions that I used in my construction of
n-Mahlos in NFUA did. [They form a slightly larger class of functions,
however.]

	This ends letter 4. The next topic to take up is how certain
term-models for our language yield models of KP + V=L + MacLane Set
Theory + "There are arbitrarily large lbfp's".