Sets and Classes: On the Work by Paul Bernays

.rr,"(p) = { ( & y , 6 , e ) ;(6 = Na A ? = (YAPE s A(P,y,G,e - 1) E p > v v ((6 # Na V Y # a V P $ S ) A ( P , Y , ~E , ~PI}* ) r S a ( is @the ) 2'-formula which results from

a

(7T: (tl),7T:

(t2),7Tc ( t 3 ) )

If T is a class of

E'xx.rr," (T(x)).

++

-

(7T:

(ti)

E S A 7T: ( h )

(Y

A Tf/ ( t 3 )

I%).

a,then .rr,"(T)= T, and in addition ~ ~ ~ f , E ' x T ( x=) )

232

ULRICH FELGNER

Here, for limited quantifiers VS,AS,the ordinal .$ is called the degree of is )given by an induction on the quantifier. Thus, the definition of T ~ ~ ( @ (see EASTON[1970], p. 149 for a definition of the order ord(@) of ord (a))for limited 2'-formulas a, and by induction on the length of Q, for unlimited 2-formulas. It is clear from this definition that if ord(@)= w 2 . q 1+ w . q 2 + 7 3 , then ord (rrs"(@)) = w 2 . q 1+ w * q 2 + qT, with q3s qT. This follows since s has degree 6 ( s ) s X , (s C_ X , and 6(s) is the set-theoretical rank of s in ,272). Thus, rrsa takes comprehension terms E'x @(x) into comprehension terms E'xrrs" (@(x)), and preserves the degree of any term of 2'. Let ]I denote * the weak-forcing relation

l k * @ e P 11-(7@). decides @ (in symbols, p 11 a) iff either p 1 1 P

We say that p

or p

1 1

@.

,

SYMMETRY LEMMA. Let CD be an 2'-sentence, p a condition and s a subset of the regular cardinal K, of ,272, where s is a set of ,272. Then: p

I t * @ e rr,,

(p

It-* ma(@I.

PROOF. By induction along the inductive definition of forcing. There are only two critical cases to check, namely the cases where @ is A ( t l , t 2 , t 3or) V,P*(x).

Case I . a is A(t,,t2,t3). Since CP is a sentence, t l , t z , t 3 are constant terms of 2.Let p ' be an extension of p , p ' 2 p , such that p ' decides 1@ or p ' 1 1 a),and let p * be an extension of p ' such that (i.e. either p ' 1 rrsP ( p *) decides nu (a).We claim that p * 1 1@ errSa( p *) 1 1rrs"(@). Suppose first that there is an extension q of p * and ordinals p, y, 6 in ,272 such that

(t)

q

1 1t , = p

1 1t z =

&q

y &q

1 1

t3

8.

We consider two subcases:

Subcase l ( a ) . p E s, y (*)

=a

and 6 = X , (in ,272). In this case,

ord ( A ( t l , t z , t 3= ) )w 2 . [max{6(t,),6(t2),S(t3)}+11 + w

+ 1,

but

(**I

o r d ( r r , , ( t , ) E s ~ r r ~ ~ ( at ~~) = r r ~ ~ ( Xt m~ )= ) = = w 2 . [max{6(t1),6(t2),8(t3)}+ 11 + n,

where n is the W-finite length of that formula. (Note that 6 ( t i ) = 6(rrs"( t i ) ) and that q 1 1ti = x (for some set x of ,272) implies 6 ( t i )2 6(x) = rank of x.) Thus, the formula A(tl,tz,t3) in (*) has a greater order than the formula in

CHOICE FUNCTIONS ON SETS AND CLASSES

233

234

ULRICH FELGNER

which in turn is r s " ( q ) l F * I T , " ( A ( t i , t z , t 3 ) )This . implies that p*

IF A ( t I , t Z , t 3 ) e n , " ( p * ) I l

n:(A(tl,tZ,t3))

by the choice of p * . Assume now that (T) does not hold. This implies by the definition of forcing that p * IF A ( t , , t Z , t 3 ) . Using the induction hypothesis it follows that there cannot be any extension q of p * such that rSa (4) IF r: (tl) = p, r s a ( q )IF y = 7r:(t2), and rr,"(q)It- S .rr,"(t3)for some ordinals p, y, 6 of 22.Thus, 7 r ~ " ( p * ) I ~ - ~ ( ? ~ ~ ( t I ) , . r r s " ( t Z )also , ? ~ ~holds. ( t 3 ) )In particular, 21

r s " ( p *) IF

It is now obvious that p ?Tsa(

p *) IF (A (IT:

(t1),57:

7(

ti

*1 1A(t,,t,,t,)

(tz),?T:

&).

C S A t z = (Y At3

(t3))

is equivalent to (T:

7

(ti)

ES A

fz,)).

A ?T,"(~Z)=ICYA?T~"(~~)~

Thus, we have shown that in all cases, p * I ) - A ( t l , t z , t 3 ) iff 1 1vSu(A( t l,tZ,t3)). This is true for any extension p * of p such that p * 11 A ( t l , t z , t 3 ) and r s " ( p * ) 11 r:(A(tl,tz,t3)). But "not p \I* @" is equivalent to " 3 p ' s p : p ' 1 1- @" (see FELGNER (1971a), p. 83, Lemma A(i)). Therefore, our claim rsu (pA*)

p

IF* A ( t l , t Z , t 3 ) @

'7f,"(p)Ik* n:(A(ti,tZ,t3))

follows .

Case 2. @ is V,' V(x). Let p * be an extension of p such that p * 11 @ and 7 ~ (~ p"*) 11 S ry (@). As in Case 1, it is sufficient to prove that p * IF Q, iff lTsu ( p *) IF ?Tsa(@I. 1W t ) . For some term t of degree 6 ( t )< T, p * IF V,' W x ) p * 1 Hence, if p * IF V,' T(x), then there is a constant term t of degree 8 ( t ) < T such that IT," ( p *) IF* rrsa(T(t))(by the induction hypothesis). If we can show that

($1

7rsa(

p *) IF* rsa ( W t ) ) e ITs" (P *) IF*

?TS"

(WX)"

/ITS"

(t)l,

where ?T,"(~(x))[x/?T,"(~)] is the result of substituting .rr,"(t) for x in the 9-formula mS" (q(x)), it will follow that 7," ( p *) IF* V,' rsa (T(x)), i.e. ( p *) T s " (@I. (@), then by a similar argument, it follows Conversely, if 7~,"( p *) IF rSu from ($) and the induction hypothesis that p * IF* a. Thus, all we have to do is prove ($). If the formulas rsa (Wt))and T,"(V(x))[x /rS" (t 11 are at all different, then vsa(T(X))[X/?T~~ ( t ) ] can be obtained from raa ( W t ) ) by finitely many ITS"

It*

235

CHOICE FUNCTIONS ON SETS AND CLASSES

replacements of a subformula of the form A(ti,t:,t) by the formula A( ti,t;,n,"(t))tt-((t:c

SAt:'(YATsa(t)'

&).

It suffices to show that if r*is obtained from r by a single replacement of this kind, then p IF* r*c* r. We prove this by induction on the length of the formula r. There are two cases to consider. . that by the definition of n:(@), Case 2(a). r is a ( t : , t ; , ~ : ( t ) )Note the constant term t must have degree less than X , since otherwise the and n3a( T ( x ) ) [ x / n a a ( t ) ]would not be different. But formulas rS"(T(t)) then p * I k 7 n,"(t) X a (see EASTON[1970],Lemma 13). Hence 2:

p

-

*It

( t :E S A t i --- (Y A Ts"( t )

2:

X-).

Then, obviously, p * I t * r t , ( r t t - ( t : E s ~ \ t : = ( ~ ~ n ~ ~ (X,)), t ) - - -i.e.

* lk* r -r*.

Case 2(b). r is not of the form a(tI,,t:,n:(t)). Here the claim follows by a straightforward computation. The Symmetry Lemma is thus proved. LEMMA3.2. %!* is a model of ,E.

PROOF. Suppose that the global form of the axiom of choice E holds in %*. Let R be the %!*-classof all unordered pairs. By our assumption there is a choice function G on R in %*. Define in %!*:

Q = {(x,Y>;{X,Y 1 E

8z G ({x,Y1) = x 1.

By the definition of %* there is an unlimited 9-formula T(x,y) which contains no subformula A ( u , v , w )in which one of the terms u, v, w is a variable which is not in the scope of a limited quantifier, such that Q = K x (V, V,x = (Y,,Z)AT(Y,Z)). Here, x = (y,z) stands for the unlimited 9 - f ormula A [a Ex

(A ( b E a

t ,

b

a

f-,

b

= y)

v A ( bEa b

(b = y v b

t ,

= z)))].

Since G is a choice function, we conclude in particular that for each y in Reg.={(; X , is regular} either

or holds. Let X , be (in 9R)the least-regular cardinal which is strictly greater than the degree (= rank) of any constant term or limited quantifier which occurs in T.The degree of a limited quantifier V p is defined to be p. We claim that %* T(6,,&)t,T(t,,&) holds. Let p be any condition. Clauses (i) and (ii) of the definition of a

t=

236

ULRICH FELGNER

condition imply that there is an ordinal A in 92, A < X,, such that (y,a,q) is in the domain of p only if y < A. Put s = X a - A (set theoretic Then, by the choice of A, ~ ( p=)p and hence by difference) and T = rSa. the symmetry lemma: p

It-* T(6,,ta)e p IF* T(T(6a,ta)).

By the assumption on the degrees of constant terms and limited quantifiers occurring in q ,the formula ~(T(6,,2,))is simply T ( T ( ~ , ) , T ( ~ , ) ) . Hence, p IF* T(6,,&)e p IF* T ( T ( ~ , ) , T ( ~ ,Next ) ) . we show that p IF* ~ ( 6 , = ) 2,. In fact let % be any complete sequence of conditions which contains p and let 92(%) be the resulting NB-model. Then in the sense of n(%):

K x (x C z- (6, )) = {(x

+

n A ) u (s - x ): x CK y ( y E

6, )} = K x ( x E 2,

).

Thus 92(%) n ( b , ) = c,. Since this holds for all complete sequences % containing p , it follows that p IF* ~ ( 6 , =) c,. A similar argument shows that p IF* ~ ( 2 , ) = 6,. It now follows that p IF* T(6,,&)( J p IF* T(L6,) holds for every condition p . Thus %* T(6,,2,) c* T(2,,6a), a contradiction. This shows that E does not hold in the model %*. Thus, we have completed the proof of Theorem 3.1.

+

Digression. For a class X and a set s, define

X'"' = {Y ;(S,Y) E X I , Pr, ( X ) = {y ;32:(y,z) E X } . Let V be the class of all sets and On the class of all ordinals. MAREKand ZBIERSKI[ 19721 considered the following two strong forms of the axiom of choice, Cv (choice on the universe V) and C, (choice on the ordinals):

cv Con

vx3~ @(x,x) + 3 Y V x (pr, ( Y )= V ~ @ ( x , y ' " ' ) ) , ~a 3~ @(a,x) + 3~ V a E On[Prl ( Y )= 0n~@(a,Y'"')1.

It is obvious that in NB-set theory Cv implies E (take in Cv the formula x = OvX E x ) and Cv implies Con.Furthermore, the conjunction of Con and AC implies E (to see this, consider in Conthe formula, " X is a well ordering of P(a) = { x ; x G ay' and use the Proof of Theorem 7.22 in RUBIN-RUBIN[1963], p. 77, or consider the formula " X is a well ordering of V,", where the V, = { x ; p ( x ) < a } are the von Neumann-Stufen). On the other hand, Cv follows from E since E implies that there is a class G which maps V in a one-to-one fashion onto On. Thus: (in NB): Cvc* (Co.~AC)+ E + AC. Theorem 3.1 shows that the last arrow cannot be reversed in NB. Marek

CHOICE FUNCTIONS ON SETS AND CLASSES

237

proved in MAREK(1973),p. 36 that Cvis independent from E. Hence (in NB) Cv+ E + AC while none of the converse implications are provable. 4. Conservative extensions

In the preceding section we have seen that the global axiom of choice E is not implied by the local axiom of choice AC. Thus, NB + E is a strictly stronger theory than NB AC. We shall see in this section that, on the other hand, NB E is not so much stronger than NB + AC: we shall prove that in NB + E one can prove nothing more about sets than one can prove already in NB AC. More precisely, we shall prove the following result: "NB + E is a conservative extension of NB + AC with respect to ZF-sentences ".

+

+

+

(See SHOENFIELD [1967], p. 41 for terminology, and notice that 2 '- is a [1971]. sublanguage of 2?--see 91.) This result appeared in FELGNER Here we present a slightly simplified and modified version of that proof. It is convenient to have the following version of the axiom of dependent choices at hand. Let a be a cardinal number: DCC": Axiom of dependent choices o n classes of length a

If R is a binary relation between subsets and elements of a class S such that V y G S[card ( y ) < a 3 3 2 E S : (y,z) E R l , then there is a function f : a + S such that

WY); Y E p ) , f(PN E R

for every p < a.

This axiom is a generalization of the axiom DC introduced by BERNAYS (1942), p. 86: DC: Axiom of dependent choices

If r is a binary relation o n the set s such that for every x E s there is an element y E s such that ( x , y ) E r, then there is a sequence (x,; n E w ) of elements x, E s such that (xn,xn+,) E r for all n E w. This axiom DC was rediscovered independently six years later by TARSKI[1948], p. 96. Denote by DC" the axiom which results from DCC" by requiring that R and S are sets. These axioms DC" have been introduced by LCvy in [19641. Clearly NC and DC" are equivalent. LCvy showed in L E V Y [1964] that (in NB'):

AC e ( V a : DC").

238

ULRICH FELGNER

The reader is referred to FELGNER[1971a], p. 146-166 for further results concerning the axioms DC". The DCC" will be discussed in §5. Here, we confine ourselves to the following result. LEMMA4.1. (for every cardinal a). In the axiom system NB (which includes the axiom of foundation), the axioms DC" and DCC" are equivalent. PROOF. Since DCC" +DC" is obvious, we have only to prove the converse. Let R and S be given such that the hypothesis of DCC" is true. Let p ( x ) = min {y ;x E V,,,} be the usual rank of the set x. By the axiom of foundation every set x has a rank p ( x ) . Let p be an arbitrary element of S and put G o = { p } . We shall define sets G, by induction:

GI = { X E S ;({P >,x ) E R AVY E S (({P 1,Y ) E R

+

P ( X ) =S P ( Y 1)).

Suppose G, # 0 is defined for all u < A where A < a. Call a sequence d = ( u u ;v < A ) of elements u, E S a regular A-chain iff u, E G, and ({u, ; y < v},u,) E R for all v < A. Let DAbe the set of all regular A-chains. For d E DAdefine

HA( d ) = { x E S ; ( 0E)R AVY E S ( ( ~ , YE )R

+P(X)

P(Y))},

and finally GA = U { H A ( d )d; E DA}. The set t = U { G , ; Y < a} equipped with the restriction of R to t, satisfies the hypothesis of DC". Hence, by DC", there is a function f defined on a such that (Cf(y); y < P},f ( p ) )E R for all p < a. Thus DCC" holds, Q.E.D. COROLLARY.In NB the local axiom of choice AC is equivalent to V a : DCC". The result that NB +E is a conservative extension of NB + AC with respect to ZF-sentences, will be a corollary to the following more general theorem. THEOREM4.1 (FELGNER[1971]). Every countable model % of NB+ AC can be extended to a countable model 92 of NB + E such that % and %

have precisely the same "sets".

PROOF(outline). Let 'iD2 be given, 'iD2+NB+AC, and let En be the membership relation of %. We shall extend 'iD2 to a model % in such a way that % has no new sets but only new classes. In particular, we shall add a universal choice function F to %. We shall apply Cohen's method of forcing in order to obtain a generic universal choice function F. The genericity of F guarantees that the structure % = m [ F ] generated by 'iD2 and F is a model of NB-set theory. We define a language C F which has set variables vi (for each integer i of

CHOICE FUNCTIONS ON SETS AND CLASSES

239

a,notice that may contain non-standard integers), constants S for each class S of a,a unary predicate symbol F, a binary predicate symbol C,

the sentential connectives -, v (“not”, “or”), a quantifier V (“there exists”), and brackets. If s is a set in the sense of 2%then the constant s will be called a set constant. The formulas of 2” are defined in the metalanguage, so that the length of a formula will be finite in the usual sense: (i) If a and b are variables or set constants, then F ( a ) and a E b are formulas of U“, (ii) If a is a variable or a set constant, and if S is any constant, then a ES is a formula of ZF, (iii) If @ and are formulas of QF, and if x is a variable, then -@, @ v Y , and V, @ are formulas of UF. We introduce the other logical symbols A , +, -, and A (conjunction, implication, equivalence, and universal quantification) into 2” as usual by definition. Their use can be eliminated.

DEFINITION (in n). A condition is a set p such that p is a function and p (x) E x for all x in the domain of p . Let cond be in 22 the class of all conditions. By a simple induction on the length of the i?”-formula @ we define in the metalanguage the forcing relation p IF@( p forces @) as follows:

IF t E s e t Ems, P IF F ( s ) s Empp,

(1)

p

(2) (3)

p l k 7 @ e V q Emcond[p G m q

(4)

p II-@vure(p IF@or P IF p V, @(x) e 3 s [s is a set of

w,

+ notq IF@],

92 and p IF @(s)]. Here c* denotes inclusion in the sense of fxn, i.e. (5)

xcmyevz(ZEmx jzErny),

and V, 3, 3 , 8z are the logical symbols of our metalanguage. A sequence % = (p‘”); n E w ) of conditions is called complete, if % is well ordered by

a,

Cm and of order type w and, if for every class C of conditions, C in which is cofinal in cond, there is some p‘k’ in % such that p ‘ k ’ E m C . Let 9’ be a complete sequence of conditions. The model Y2 can now be defined: (i) If @(x) is a formula of U”, then the collection of all set constants s such that 9’1 1@(s) is called a class of Y2, and will be denoted by K x @(x). (ii) Sets of 8 are classes of the form K x (x C s), where s is a set constant of 2“.

240

ULRICH FELGNER

(iii) The membership relation

€%

is defined as follows:

K x @(x) E n K y W(y) holds iff there is some set s in W such that s E Ky W(y) and Kx @(x) = Kx (x C s ) (equality of these collections in

the sense of the metatheory!). (iv) A class K x @(x) of % satisfies the predicate F in 8 iff K x @(x) EzK y F ( y ) .

(v) A constant S (where S is a class of W ) is interpreted in % by the class Kx (x C s). Thus, we have defined how the language Q F is interpreted in % = (Kx @(x); @(x) is a formula of Q F which has x as its only free variable}. The mapping T : W + % which is given by T(S)= K x (x E S), is an isomorphism from W into % such that S1EmS2e T(SJ E2T(&). This follows immediately from the fact Kx (x € S1)= Ky (y € S,) f* S ( ~ S =I S2.In particular T maps the class of all sets of W onto the class of all sets of %. Thus, if we identify W with its isomorphic image in %, then W and % have precisely the same sets. It can now be easily shown that % satisfies all the axioms of groups I (extensionality), I1 (direct construction of sets), I11 (construction of classes), VI (infinity), VII (foundation), and axioms a, b, d of group V (subclass, sum and power set). We refer to FELGNER [ 19711 where all necessary details are given.

LEMMA4.2. The global axiom of choice E'holds in %. PROOF. It is clear that F = K x F ( x ) is a function in 8 such that F ( a ) €% a for all non-empty sets a of %. We have to show that F is defined for all non-empty sets of %. In fact let a be a given non-empty set of 8.By the definition of %, there is a set s in W such that a = K x (x E s). But T is an €-isomorphism from W into 3, ~ ( s = ) a, and hence, s must be non-empty in W . Therefore

D=(p;pE*~ond&3t(t€~s&(s,t)€*p)}* is a class (defined in D!) which is cofinal in cond. Since 9 is a complete say p ( " ) ,such that sequence of conditions, there must be a member of 9, p'" €m D. Hence p'k' It F ( ( s , t ) )by the definition of forcing. This gives us (Kx ( x € s ) , K y ( Y € ~ ) ) € ~ and F

Ky ( y € t ) E " K x (xEs).

It follows that F is defined for every non-empty set of '3, Q.E.D. Let @(xo,xI,.. .,x,) be a formula of g F with no free variables other than xo,...,x,, let s be a set constant and y a variable not occurring in @. Define Res (@,s,y) (restriction of @ to s and y ) as the following formula: / \ . * . A [ ( x l ~ s / \ . . . r \ x n € s ) - , ( V @ ( X,..., o Xn)* XI

x.

xo

v

*OEY

@(Xo

,..., X"))].

CHOICE FUNCTIONS ON SETS AND CLASSES

24 1

The next lemma will show that for every set constant s, the class {q E”cond; q V, Res (@,s,y)} is cofinal in cond.

LEMMA4.3. Let s be a set of 1Dz, p a condition and @(xo,...,x,) a formula of g F with no free variable other than xo,. ..,x,. There exists an extension q of p such that 4 It v Res (@AY 1. PROOF. Let S” be in 2J2 the set of all n-tuples of elements of s. Since 1Dz satisfies the local axiom of choice AC there is a well ordering of s in 1Dz. Hence, we can index the elements of s by ordinals a, s = {u, ; a < A}m, where A is a cardinal of 1Dz. If u, is the n-tuple (zl,..., z,) in 1Dz, then we shall write @(y,u,) instead of @(y, z,, ..., 2,). Now define in 1Dz:

K

C q & q E cond & a < A & e E {0,1}& 6% [(e = 1 82 4 It- @(v,u,)) or ( e = 0 & - 3 q ’ 2 q 3 w : q’ It @(w,u,))l}.

= {(q,u,,e,v);p

A partial ordering

< can

be defined on K as follows:

( ql,ua,el,vl)<( q 2 , u p , e 2 , v 24, )e

q 2

& a < P.

If a E K , then put cp(a) = P e 3 q 3 e 3 v : a = (q,u,,e,v).We call cp(a)the order of a. A subset t of K is called a thread, if t is totally ordered by < and V a E t V y [ y < cp(a) 3 b E t : cp(b) = yl

+

holds. As usual Prl ((q,u,,e,v))= q is the projection to the first coordinate. We are now in a position to define a relation R between subsets and elements of K as follows:

( t , a )E R

i

t is a thread & a E K & c p ( ~ ) = SUP {y + 1; 3 b E t : cp ( b ) = y} & Pr, ( a )2 U {Prl ( b ) ;b E t } .

By the Corollary of Lemma 4.1, the axiom DCC” holds in 2J2. Hence, there is a function f from A into K such that

(Cf(r);Y < a } , f ( a )E) R Put p * = U{Prl ( f ( a ) ) a; < A}

all a < A. and r = {v ;3a < A 3 4 3 e :f ( a )= (q,u,,e,v)} (notice that cpCf(a))= a always holds). It

for

follows that p *

It Res ( @ , s , r ) ,and hence p * 1 1V,

Res (@,s,y), Q.E.D.

It follows from Lemma 4.3 that for every 2’-formula @(xo,. ..,x,) and every set s of 1Dz there is a set r in 12n such that % Res ( @ , s , r )holds.

+

242

ULRICH FELGNER

It is now a routine matter to show that this implies that the axiom of [1971] for all details). Theorem 4.1 is replacement holds in % (see FELGNER thus proved. REMARK. In contrast to the result of Morris, which says that not every countable model XJl of NB-set theory can be extended to a countable model % of NB + AC without adding ordinals (see §2), Theorem 4.1 says that every countable model 2Jl of NB +AC can be extended to a countable model of NB +E without adding ordinals! One reason for the extendibility of models XJl satisfying AC is that the axioms DCC" provide choices from "sets of classes". The importance of DCC" in this context will become clearer as soon as the question of extendibility is discussed in the absence of the axiom of foundation. The axiom of choice AC is sometimes considered as an axiom which enlarges the universe of sets, since it provides to every collection of non-empty sets a further set, namely a choice function. I think that AC has more the character of an axiom which restricts the universe of sets: only those collections are sets which have choice functions. It follows from Godel's work that the minimal model of constructible sets satisfies AC. The result of Morris shows that models of NB + AC are not arbitrarily large (if one fixes the ordinals). However, Theorem 4.1 shows that E restricts the universe of sets no more than AC. By results of Cohen and Jensen (see 02) the same is true for the general continuum hypothesis GCH. In contrast to this, Godel's axiom of constructibility V = L is definitely a restrictive axiom. Let .& be the class of models of NB + AC + E and let 93 be the class of models of NB+E. Theorems 3.1 and 4.1 show that there is a chain of E SQ countable models 2Jlo 2Jl, . - . 92" nn+, such that Dzn and Y.RZn+,E 93 for all n E w. The existence of this alternating chain shows that the disjoint classes d and 93 cannot be separated by an V,O n &"-class (see ADDISON[1965]). However, not much more is known about such separability questions. The following theorem was obtained independently by several people, [1971], GRISIN[1972], Jensen, Kripke, and COHEN[1966], p. 77, FELGNER Solovay. A forcing-free proof was obtained by GAIFMAN[ 19681.

c

c

c---

THEOREM4.2. If @ is a sentence of the ZF-language 9 ~ then,@ is provable in NB + E if Q, is provable in NB + AC.

PROOF. If NB + AC Q, then clearly also NB + E @, since AC follows from E.' Conversely, suppose that NB E Q,, where is a sentence in

+

I

T.

The symbol

k denotes provability. Thus T 1CP means that @ is provable in the theory

CHOICE FUNCTIONS ON SETS AND CLASSES

the ZF-language, i.e. @ contains no class variables. Assume that @ is not provable in NB+AC. Then NB+AC+(-CP) is consistent and has a model a. By the Lowenheim-Skolem theorem N B + A C + - @ has a countable model 2Jl. By theorem 4.1,m can be extended to a model % of NB + E such that both 2Jl and % have the same sets. Since @ speaks only about sets, it thus follows that % must also satisfy @. Hence % NB + E + CP. But by our assumption, @ is provable in NB + E, thus % @, a contradiction. This shows that @ must be a theorem of the theory NB + AC, Q.E.D.

+ +

COROLLARY4.1'. If @ is a sentence of the ZF-language. Then @ is provable in ZF + AC i$ CP i s provable in NB +E. It is well known that ZF @ iff NB I- @ for every ZF-sentence @ (see COHEN[ 19661, p. 77, FRAENKEL-BAR-HILLEL-LEVY-VAN DALEN [1973], pp. 131-132). Hence, if N B + E F @ , then N B + A C F @ by Theorem 4.2, and therefore NB (AC j @). We conclude that ZF (AC a), and hence ZF +AC @, Q.E.D.

PROOF.

+

F

Let 23'5F be the first-order language which results from Z e Z Fby adding the unary function symbol a. The terms of 2'SF are defined inductively: the variables x, y, z, xo, xl, ... are terms, and if t is a term, then a ( t ) is a term. The formulas of 2':F are also defined inductively: if t l and tZ are terms, then t l E t z and t l = tZare formulas, and if CP and P are formulas, then -@, @AT, @ v T , @+P,@-T, V x @, and 3 x @ are also formulas (where x is a variable). The system ZF,O consists of the axioms of extensionality, empty set, pairs, unions, power set, infinity, replacement (where all formulas @(x,y ) from 2% are allowed to appear in the schema of replacement), and the axiom A,

v x (xf

0 j C(X)

€ x).

It follows from the axioms of the predicate calculus that v x v y [x = y -+ a ( x ) = (r(y)l;

ZF, = ZF,O + Axiom of foundation. The language PzF is defined similarly: 6p;F results from 23'zF by adding Hilbert's esymbol. The formulas and terms of YzFare defined by a simultaneous induction: all variables x, y, 2 , . . . are terms; if t l and tl are terms than t l € t2 and t l = t S are formulas. If @ is a formula which contains at least one free variable x, then ex@ is a term; if @ and v' are formulas, then @ ,, @ ~ v@ ' ,v T , @+T, @-P, VxCP and 3 x @ are formulas.

244

ULRICH FELGNER

The system ZFP consists of the axioms of extensionality, empty set, pairs, unions, power set, infinity, and replacement (where all formulas @ ( x , y ) from Yz are allowed to appear in the schema of replacement). Besides the usual logical axioms the system ZFP also contains Hilbert’s axiom 3 x @ ( x ) + @(& @)

and Ackermann’s axiom v x (@(x)

c,* ( x ) )

-+

€,

4) = E x ‘I’

as logical axioms. The system which is obtained from ZFP by adding the axiom of foundation is called ZF.. It is obvious that the axiom of choice AC is provable in both systems ZF: and ZF;. As a corollary to Theorem 4.2 we now obtain: COROLLARY 4.2. Let CP be a sentence of the ordinary ZF-language (CP E YZF).Then the following three conditions are equivalent : (i) ZF +AC 1 @, (ii) ZF, 1@, (iii) ZF, CP. PROOF. Since ZF, AC, it is obvious that (i) implies (ii). Since the symbol (T can be interpreted in YZF by the stipulation u ( x ) = E,(Y E x ) so that Hilbert’s axiom gives u ( x ) E x for all x such that 3 y ( y E x), we see immediately that (ii) implies (iii). Now suppose that (iii) holds: ZF, 1 @. Let p be the ordinary rank function: p ( z ) = min {a;z E Ve+l}. The €-terms have an interpretation in ZF, by defining for an arbitrary formula *(x)7

p = (+({X ;* ( X ) A VY (*(Y)

EX

+P

(X)

P(Y )))).

Thus (iii) implies (ii). It follows easily from Theorem 4.1 that (ii) implies (i): if !N is any model of ZF + AC, then !E can be extended to a model n* of NB + AC just by adding predicative classes (see FRAENKEL-BARHILLEL-LEVY-VANDALEN[1973], pp. 131-132 for all details). Znz and Znz* have the same “sets”. Thus, Theorem 4.1 gives an extension %! of n* such that % NB + E and such that %! and !N have the same “sets”. If we interpret u by the global choice function which exists in 8,it then follows, that every model !N of ZF + AC can be expanded to a model of ZF, (without adding new sets). Thus (i) follows from (ii) in the same way as we proved Theorem 4.2, Q.E.D.

+

Theorem 4.2 and its two corollaries follow almost immediately from Theorem 4.1 which was proved by means of forcing. Gaifman obtained a

245

CHOICE FUNCTIONS ON SETS AND CLASSES

f orcing-free proof of Theorem 4.1 and obtained thereby an even stronger result. Gaifman’s result is as follows:

(9

Let W be a model of ZF +AC such that the ordinals of are cofinal with o. Then W can be expanded to a model %=(W,F) of ZF,.

W

In fact, let W be a given model of ZF + AC such that there is a countable increasing sequence of ordinals a, (of W)with the property that every ordinal in the sense of 9J2 is less than some a,. Notice that 9J2 need not be countable! Denote the m-set of those sets of W whose ranks are less than y by V,”. Construct a tree T such that the nth level of T consists of all linear orderings of some V,” for y 3 a, which are in W and which are inside W well orderings of Vanw.Put W, e W , 8 W , is an initial segment of Wz.Thus (T,s) is a tree. Let 2% be the language which results from LfZ by adding a binary predicate w (,). In a structure (V,, W), where W E T, the predicate w is interpreted by the ordering relation W. Let (V,”, WJ <, (V,”, W2)mean that (V,“, W , ) is an n-elementary substructure of (V,”,Wz>, i.e. ( v,“,W , ) Q, iff ( V,”,Wz) Q, for all sentences Q, E 2; in prenex form containing names for elements of V,” such that Q, contains at most n alternating blocks of quantifiers. Using reflection inside %! one can prove the existence of a branch Wo< W ,a * * a W, a * in the tree ( T , a ) such that inside W,W, is a well ordering of V,,“ and (V,,“, W , ) in(V:,,, W,,,) for all n E o.Since (a,;n E o)is cofinal in the W-class of all ordinals, the union over all these V z is equal to the universe of W and W = U { W, ; n E w } is a well ordering of the universe of W.Thus 2% can be interpreted in (B, W). Using the relation <, one can show that (W, W ) is a model of ZF,, Q.E.D.

+

-

An open problem. Mostowski has shown that ZF Q, iff NB Q, for all ZF-sentences Q,. SHOENFIELD [1954] showed that there is a primitive recursive function f such that, if p is the Godel number of a proof of Q, in NB then f(p) is the Godel number of a proof of Q, in ZF (see also DOETS [1969] and FLANNAGAN [1975]). It is not known whether a similar result holds for NB + E and ZF + AC. In closing this section we mention that Theorems 4.1 and 4.2 also hold for the impredicative theory of classes M of Wang and Morse (sometimes also called Morse-Kelley set theory). The language S,.,has E and only one sort of variables: capital letters X, Y,2,... which range over classes. The axioms of M are extensionality, empty set, pairs, union, power set, replacement, infinity, foundation, and the class-existence schema (i.e. Axioms I-VII and VIII, in MAREK[1973]). In 1970, the author proved the

246

ULRICH FELGNER

following result (see MAREK[1973], p. 10):

(0)

Every countable model % of M +AC can be extended to a countable model % of M +E such that 9.X and 8 have the same “sels”.

As a corollary we obtain: (00)

If @ is any ZF-sentence, then M + AC

@ iff M +E

@.

This can be proved in a quite similar way as we have proved Theorems 4.1 and 4.2. In order to prove (0),define the class of conditions to consist of all local choice functions f which are in 9.X and obtain a generic filter G. Using techniques developed by CHUAQUI[1972], one shows that G is strongly generic and that hence the resulting extension is a model of M +E. We refer to MAREK-ZBIERSKI [1972] for a discussion of further axioms of choice in M. 5. Axioms of choice in set theory with atoms It is the aim of this section to discuss the question of whether the results obtained in 44 remain true if we drop the axiom of foundation. We shall discuss for example whether ZF,O is a conservative extension of Z F o + AC or not. The axiom of extensionality excludes the existence of urelements, i.e. objects u such that u # 0 and V x ( x e u ) . The axiom of foundation V x [ x # 0 + 3 y E x ( x n y = 0)] excludes the existence of ungrounded sets like reflexive sets x = { x } . If 011 is a set of urelements, then define by induction R (a,%)= u P( U R (P,%)), P (a

where a is an ordinal number. The assumption that U {R (a,%);a is an ordinal) is equal to the universe V of all sets, corresponds to our intuitive understanding of the notion of set: the universe of sets is built up in stages R(a,%) and every set is well founded relative to the given class % of urelements. The urelements correspond to what Cantor called “Objekte der Anschauung”. Urelements appear as soon as we use our settheoretical formalism in connection with the axioms of some other field of science, e.g. in connection with the axioms for euclidean geometry. In the latter case the “points” are to be considered as urelements since their set-theoretical nature is not specified. In the case of the theories ZF” and NBo the situation is different. The existence of urelements is excluded but it is consistent with Z F o and NBo to assume the existence of ungrounded sets, e.g. sets x such that

CHOICE FUNCTIONS ON SETS A N D CLASSES

247

-

x 3 x 13 x2 3 . .3x, 3 * (for all n E w ) . The theories ZFo and NB" became important in connection with the Fraenkel-Mostowski-Specker method for obtaining independence results (see e.g. FELGNER [1971a],pp. 46-75). Even after the appearance of Cohen's forcing method, the method of Fraenkel-Mostowski-Specker remained of interest, since (i) the permutation models constructed b y that method are much easier to handle than generic extensions, and (ii) independence results obtained by means of permutation models can be carried over in many cases to independence results for set theories including the axiom of foundation. This is accomplished by the Jech-Sochor-Pincus theorem (see JECH[ 19731, pp. 85-117). If we now try to generalize the results of 04 to set theories not containing the axiom of foundation, then this is done, not only to see whether these results depend on the axiom of foundation or not, but also to overcome some fascinating combinatorial problems which arise in this connection. In doing so we hope to throw some more light on the results of 04. Further, the axiom of foundation has also the flavour of choice, since by the axiom of foundation there is a function which selects subsets from classes. Hence the combinatorial power of various axioms of choice is best seen in the absence of foundation.

First observation. Statements which are equivalent to AC or to E on the basis of the axioms of ZF or NB need not be equivalent to AC respectively to E on the basis of the weaker systems ZF" and NB". As an example consider: Inj

(The injection principle): Every set can be injected into every proper class.

PW

The power set of every well-orderable set is well orderable.

It is proved in FELGNER-JECH [1973] that in NBO: Inj + AC + PW, while none of the converse implications is provable. In NB, however, all these three statements are equivalent. Consider also: N

(Von Neumann's axiom): If X is a proper class, then there is a one-to-one mapping from X onto the class V of all sets.

Obviously in NBO: N + " V is well orderable" + E. We shall see below that in NBonone of the converse implications are provable. However, in NB all these statements N, E, and "V is well orderable" are equivalent. This suggests that if we drop the axiom of foundation in Theorem 4.2, we must choose carefully between certain forms of local and global choice in order to obtain a true theorem.

248

ULRICH FELGNER

LEMMA5.1. In NB', (VaDCC") =$ Inj holds. The converse implication is not provable in NB'.

PROOF. First, we show that V a : DCC" implies Inj. Let s be a set and T a proper class. Since DCC" =$ DC",it follows that s can be well ordered. Let A be a cardinal such that s = {r, ;p < A}, where the p are ordinals. Define a tree D such that the pth-levelof D consists of all injections from {rr ;y < p } into T. Since the elements f of D are defined on initial segments of s, it is obvious that D is a tree with respect to the inclusion relation G. By DCCAthere is a chain (fv ;v < A ) of length A in (D,C).Then U cfy ;v < A} is the required injection from s into T. In order to show that Inj does not imply V a :DCC" in NB",we construct a Fraenkel-Mostowski-Specker model W in which Inj holds, but DCC" will fail in W.Let On be the class of all ordinals and let On" be the class of all functions from m into On. Let A be a proper class of atoms (reflexive sets a = {a}) which are indexed by the elements of U {Onm;1 s m E m } , A ={af;3m ( I s m & f €On")}. Define af d a , e f Cg, then (A,$) is a tree. If B C_ A, then B is called a small subtree, if B is a set such that B contains no branch of length w and Vx E B Vy [y u x =$ y E B] holds. Consider

G

={T; 7

is a permutation of a subset of A which preserves a}.

Let dom ( T ) be the domain of the permutation T. For 7 E G let .i be the mapping' defined by .i(x)= ~ ( x )for x E d o m ( ~ )and .i(x)= x for x $Z dom (T),x E A. A subgroup H of G is called nice if there is a small subtree T of (A,+ such that

H

= {T E G ; T

leaves T pointwise fixed}.

For groups HI and H,,let HIs H , mean that HI is a subgroup of H,. Define 9 = {H;H

G

G & 3 K [ K s H & K is a nice subgroup of GI}.

If s is a subset of the class A, then define by transfinite induction R o ( s )= s, R , ( s ) = U Q ( R P ( s ) )p; < a}. Since af E A implies af = {af}, it is obvious that p < a implies R,(s)C R , ( s ) . Finally, we put W(A) = {x; 3 s C_ A 3a E On[s is a set & x E R"(s)]}.For x E W(A) let T C ( x )= {x} u x u U x u U ( U x ) u . . * be the transitive closure of x. Following Mirimanoff, we call ker (x) = T C ( x )n A the kernel of the set x E W(A). We are now in the position to define the model 2J2. Define I Every . i extends uniquely to an E-automorphism of W(A). This extension will be denoted again by .i.

CHOICE FUNCTIONS ON SETS AND CLASSES

249

M = {x E W(A); ker (x) is a small subtree of (A,a)}. We say that x is a set of 9R iff x EM.We say that X is a class of 9 2 iff X T M andthereisagroupHE8suchthat . i ( y ) E X e y E X f o r a l l 7 E H. The membership relation of is the actual E-relation. It is a matter of routine to show that 9R is a model of NBO-set theory. The local axiom of choice AC holds in 272, since for every set x of 9R the kernel ker (x) is a small subtree and all small subtrees T have a well ordering in 2Q (see e.g. FELGNER [1971a], p. 75). Moreover, 2R is a model of the injection principle Inj. (A,<) is in 9R,but (A,e) has no branch of length o in 2Q. Thus DCC" fails in %. Lemma 5.1 is thus proved.

COROLLARY.NB"b (Va DCCP)j Inj j AC, NB AC j (Va DCC"), but neither AC j Inj nor Inj j (VaDCC-) are provable in NBO. LEMMA 5.2. The implication E j "V is well orderable" is provable in NB but not in NBO. PROOF. In NB every set x has a unique rank p ( x ) . By E there is a function F such that for each ordinal a, F ( a ) is a well ordering of V, = {x ;p ( x ) < a}. By the axiom of foundation U { V, ;a E On} = V = {x; x is a set} holds. It follows that x
or [P(x)=p(Y)A(X,Y)EF(P(X))I

is a well ordering on V. We now prove that E does not imply on the basis of the axioms of NBo that the universe of sets can be well ordered. Let A be a countably infinite set of reflexive sets, A = { a , ; r E Q}, indexed by the set Q of all rational numbers. If s denotes the usual linear ordering of Q, then put a, a a, e r < s (for r,s E Q). Define and

%(A) = A, R ( A ) = U(P(R,(A)); P < a } W(A) = U {R,(A); a E On}.

Let G be the group of all permutations of A (i.e. one-to-onemappings from A onto A ) which preserve the linear ordering S . If H is a subgroup of G, then H is called a finite-support subgroup, if there is a finite subset e of A such that H = (7 E G ; 7 leaves e pointwise fixed}. Let 9 be the filter of subgroups such that the set of all finite-support subgroups is a filter base of 9.Again let TC(x) be the transitive closure of x and ker (x) = A n TC(x) be the kernel of x. Put M = {x E W(A); ker (x) is finite}.The elements of M are the "sets" of %. A class X is called a "class of 9R" iff X C M and 3 H E s V y EXv7EH[yEXeT(Y)EH].

The epsilon relation is interpreted in 9 2 by the usual E-relation. The

250

ULRICH FELGNER

standard arguments show that 1171 is a model of NB". Since A is a proper class in 1171 and there is no well ordering of A in 1171, it follows that the universe of sets has no well ordering in 1171. It remains to show that 1171 is a model of the global axiom of choice. Let Q = {r, ;n E w } be the standard enumeration of Q and define:

M, = {x E M ; ker (x) = {aw,a ,,,..., a,"-,}}, MZ = {x E M ; ker (x) has cardinality n } .

M,, and Mz are both classes of 2.R and Mt = { ~ ( x ) ;x E M,, T E G}. Since we assume that the model P2 is constructed within a universe of sets which is well ordered, it follows that for each particular n there is a well ordering r,,of M,, in 1171. Since Q is preserved by all T E G, it follows that zsis in 1171. Let S(A) be the class of all finite subsets of A and let L be the lexicographic linear ordering on S(A). Both S(A) and L are classes of 1171. For x E MZ,y E MX, x # y define ker (x) # ker ( y ) & (ker (x), ker ( y ) ) E L, or x < y a ( ker (x) = ker ( y ) & 37 E G [T(x)E M, & ( T ( x ) , T ( Y ) ) E rnl. It follows that

YX. Let < be

<,, is a linear ordering on M z and that <,, is in the model the union of the relations <,, (for n E w ) . Since < is

$-symmetric, it is in 1171. A global choice function F can now be defined in 1171 by the stipulation

F ( x ) = min { y ; y E x}, where the minimum is meant in the sense of Q . Note that if x is a set of 1171, y Ex, then ker ( y ) C ker (x) and Q induces a well ordering on {z E M ; ker (z) C ker (x)}. Thus F ( x ) is well defined and Lemma 5.2 is thus proved. LEMMA5.3. The implication "V is well orderable" j N is provable in NB but not in NB".

PROOF. Let W be a well ordering of V and define a new ordering V by the stipulation X

S

on

< Y a [P (X) < P ( Y ) V ( P ( X I = P ( Y ) A ( X , Y ) 5 ' w)],

where p ( x ) is the rank of x. Thus in the presence of the axiom of foundation, V has a well ordering which is isomorphic with the class of &ll ordinals. From this von Neumann's axiom N readily follows. In order to see that N is not implied by the statement that V is well orderable in NB', one simply produces a model 1171 of NBowhose universe of sets is well ordered such that 1171 contains a class A of reflexive sets

25 1

CHOICE FUNCTIONS ON SETS AND CLASSES

such that in the metalanguage card (On") < card ( A ) , where Onm is the 2Jl-class of all ordinals of 2Jl, Q.E.D. We now return to our question of whether we can find a theorem like Theorem 4.2 which concerns set theories not containing the axiom of foundation. The proof of Theorem 4.1, as it is given in 04, immediately gives the following result: Every countable model 2Jl of NB" + V a :DCC" can be extended to a model 8 of NB" + E such that both W and 8 have the same sets. In fact it was for the sake of this result that we have introduced the axioms DCC" and have presented the proof of Theorem 4.1 using these axioms DCC". Hence NB" + E @ implies NB" + V a : DCC" @ for every ZF-sentence @. But NB"+E is not an extension of the theory NB" + V a : DCC" (in fact the model constructed in the proof of Lemma 5.2 satisfies E but not lnj and in particular not DCCY).Flannagan suggested that if one uses well orderings instead of choice functions as conditions in the proof of Theorem 4.1, one would get models of NB"+N. Hence THEOREM5.1. NB" + N is a conservative extension of NB" + V a :DCC" with respect to ZF-sentences.

-

PROOF. Let @ be a ZF-sentence such that NB" + N @ and suppose that @ is not provable in NB" V a : DCC". Then NBo+ V a : DCC" + @ is consistent and has a countable model 22. Use a forcing language ,Vw which is the same as the language ,VF used in the proof of Theorem 4.1 but contains a binary predicate W ( - , - ) instead of the unary predicate F(-). If R is a set of ordered pairs, then Pr, ( R )= {x ;3 y : ( x , y ) E R } , Prl ( R ) = { y ;3 x : ( x , y ) E R } , and Fd ( R ) = Prl ( R ) u Prz ( R ) is called the field of R. We say that p is a condition if p is, in 2Jl, a well-ordering relation on its field. If p and q are conditions, then we say that 4 extends p iff the well ordering p is an initial segment of the well ordering q. Now obtain a complete sequence of conditions and define the extension 8 similarly as in the proof of Theorem 4.1. It turns out that 8 is a model of NBo+ "the universe of all sets has a well ordering such that all initial segments are sets". Thus 8 satisfies von Neumann's axiom N. Since @ follows from N in NB', 8 is a model of @. But 2Jl satisfies -,@. Since @ speaks only about sets and 22 and 8 have the same sets, also 8 must satisfy 7@,a contradiction, Q.E.D.

+

REMARK. The proof of Theorem 5.1 shows that in some cases it is possible to apply Cohen's forcing method to models which do not satisfy the axiom of foundation. We do not know whether this is always possible. In the proof of Theorem 5.1, we succeeded in applying Cohen's forcing method, since no new sets had been added to the ground model 9J2. We could thus define the extension 8 without any €-induction.

252

ULRICH FELGNER

It is not known whether NB"+E is a conservative extension of NBo+AC with respect to ZF-sentences, or similarly, whether ZF: is a conservative extension of ZF" + AC. This question was raised independently by Flannagan in his thesis and by GRISHIN"721. However, it was proved independently by GRISHIN[ 19721 and simultaneously by us that ZFP is not a conservative extension of ZFo+AC. LEMMA5.4. There is a ZF-sentence @ such that @ is provable in ZFP, but @ is not provable in ZF" + AC.

PROOF. We call a set x an n-cycle if there are sets yl, yz,. ..,yn such that x = y l E yz E y3 E - - E Y,-~ E yn E x and yi is the only element of yi+l (for all 1d i < n) and yn is the only element of x. Now let @ be the following sentence: "If for every n E w, 1 s n, there is an n-cyclic set, then there is a set C such that C contains precisely one n-cyclic set for each 1d n E w".

If we apply the axiom schema of replacement Vx 3!y 1Ir(x,y)+ Va 3 b Vy [y E b -ax

(x E a h*(x,y))I

to the formula y = ~ ( isz an x-cyclic set), then for a = w we obtain the choice set b = C as required. Thus ZFPF @. It can be shown by means of permutation models that @ is not provable in ZF"+AC. The consistency of the existence of n-cyclic sets with NB" was shown by H ~ E [1965], K p. 109 and BOFFA[1968], [1968a]. Let A, be a countably infinite set of n-cyclic sets for each 1 d n E w, and put A = U { A , ; l c n E w } . Define Ro(A)=A, W(A) = U { R , (A 1; a E On} R, (A) = U (p (R, (A )); p < a}, and finally M = {x E W(A); ker (x) = A n TC(x) is finite}. Let G be the group of those permutations T of A which map A, onto A, (for all 1 d n E w ) . A subgroup H of G is called a finite-support subgroup if there is a finite set e C A such that H = {T E G ;T leaves e pointwise fixed}. Let 9 be the filter of subgroups generated by the finite-support subgroups. A class X is in the model % if X G M and 3 H E % v y E X v T E H [ y EXt*T(Y)EX]. The elements of M are called the sets of %. It is easily seen that % is a model of ZF"+AC such that %[email protected] Lemma 5.4 is proved.

CHOICE FUNCTIONS ON SETS AND CLASSES

253

References ADDISON,J. W., HENKIN,L., and TARSKI,A. (Eds.) (1965) The theory of models. Proc. of the 1963 international symposium at Berkeley. North-Holland, Amsterdam. 494 pp. (2nd printing (1972), 509 pp.) ADDISON,J. W. (1965a) The methodofalternatingchains, pp. 1-16. In ADDISONet al. (1%5). BARWISE,J. (1971) lnfinitary methods in the model theory ofset theory, pp. 53-56. In GANDY and YATES (1971). BELL, J. L. and SLOMSON,A. (1969) Models and ultraproducts: A n introduction. North-Holland, Amsterdam. 322 pp. (1st revised reprint (1971)). BERNAYS,P. (1937-1954) A system of axiomatic set theory; I-VII. J.S.L. I: 2,65-77 (1937); 11: 6, 1-17 (1941); 111: 7,65-89 (1942); IV: 7, 133-145 (1942); V: 8, 89-106 (1943); VI: 13, 65-79 (1948); VII: 19,81-96 (1954). This volume. BERNAYS,P. (1958) Axiomatic set theory (with a historical introduction by A. A. Fraenkel). North-Holland, Amsterdam. 226 pp. (2nd ed. (1968), 235 pp.). BOFFA, M. (1968) Les ensembles extraordinaire. Bull. SOC.Math. Belgique 20, 3-15. BOFFA, M. (1968a) Elimination de cycles d’appartenance par permutation de l’univers. C.R. Acad. Sci. Paris 266, 545-546. BOFFA, M. (1971) Forcing and reflection. Bull. Acad. Polon. Sc. 19, 181-183. CHANG, C. C. and KEISLER, H. J. (1973) Model theory. North-Holland, Amsterdam, 550 pp. CHUAQUI, R. (1972) Forcing for the impredicative theory of classes. J.S.L. 37, 1-18. C O H E N , ~J.. (1966) Set theoryandthecontinuum hypothesis.Benjamin,NewYork, 16Opp. COHEN,P. J. (1974). Models of set theory with more real numbers than ordinals. J.S.L. 39, 579-583. DOETS, H. C. (1969) Novak’s result by Henkin’s method. Fund. Math. 64, 329-333.

EASTON,W. B. (1970) Powers of regular cardinals. Ann. of Math. Logic 1, 139-178. FEFERMAN, S. (1965) Some applications of the notions of forcing and generic sets. Fund. Math. 56, 325-345. (Summary in ADDISON et al. (1965), pp. 89-95.) FELGNER, U. (1971) Comparison of the axioms of local and universal choice. Fund. Math. 71, 43-62. FELGNER,U. (1971a) Models of ZF-set theory. Springer Lecture Notes in Mathematics, Vol. 223. Springer, Berlin, 173 pp. FELGNER, U. and JECH, Th. J. (1973) Variants of the axiom of choice in set theory with atoms. Fund. Math. 79, 79-85.

FLANNAGAN, T. B. (1976)A new finitary proof of a theorem of Mostowski. This volume. FRAENKEL, A. A. (1922) Uber den Begriff “definit” und die Unabhangigkeit des Auswahlaxioms. Sitzungsberichte der Preuss. Akademie d. Wiss.,Phys.-Math. Klasse, pp. 253-257. FRAENKEL,A. A. (1937) Uber eine abgeschwachte Fassung des Auswahlaxioms. J.S.L. 2, 1-25.

254

ULRICH FELGNER

FRAENKEL,A. A., BAR-HILLEL,Y., LEVY,A. and DALEN,D. VAN (1973) Foundations of set theory. North-Holland, Amsterdam, 404 pp. FRIEDMAN,H.

(m).

Large models with countable height. J.S.L., to appear.

GAIFMAN,H. (1968) Two results concerning extensions of models of set theory (abstract). Notices A.M.S. 15, 947 pp. GANDY,R. 0. and YATES, C. E. M. (Eds.) (1971) Logic colloquium '69. Proceedings of the summer school and colloquium in mathematical logic, Manchester, August 1969. NorthHolland, Amsterdam. 451 pp. GODEL, K. (1938) The consistency of the axiom of choice and of the generalized continuum hypothesis. Acad. U.S.A. 24, 556567. GODEL, K. (1939) Consistency proof for the generalized continuum hypothesis. Ibid. 25, 220-224. GODEL, K. (1940) The consistency of the axiom of choice and of the generalized continuum hypothesis with the axioms of set theory. Annals of Math. Studies, Vol. 3. Princeton University Press, Princeton, N.J., 66 pp. (7th printing (1966).) GRISIN,V. N. (1972) The theory of Zermelo-Fraenkel sets with Hilbert €-terms. Math. Notes Acad. Sci. U.S.S.R. 12, 779-783. HAJEK, P. (1965) Modelle der Mengenlehre in denen Mengen gegebener Gestalt existieren. Zeitschr. f. math. Logik 11, 103-115. JECH, TH. J. (1973) The axiom of choice. North-Holland, Amsterdam. 203 pp. LEVY, A. (1964) The interdependence of certain consequences of the axiom of choice. Fund. Math. 54, 135-157. MAREK, W. (1973) On the metamathematics of impredicative set theory. Dissertationes Math. Vol. 98. Warszaw. MAREK,W. and ZBIERSKI,P. (1972) Axioms of choice in impredicative set theory. Bull. Acad. Polon. Sci. 20, 255-258. MENDELSON,E. (1956) The independence of a weak axiom of choice. J.S.L. 21,350-366. MORRIS, D. B. (1970) Adding total indiscernibles to models of set theory. Dissertation, Wisconsin. MOSTOWSKI, A. (1939) Uber die Unabhangigkeit des Wohlordnungssatzes vom Ordnungsprinzip. Fund. Math. 32, 201-252. NEUMANN,J. VON (1928) Die Axiomatisierung der Mengenlehre. Math. Zeitschr. 27, 669-752. Also in VON NEUMANN(1961), pp. 339-422. NEUMANN,.I. VON (1961) Collected Works. Vol. I. Pergamon, New York, 654 pp. RUBIN, H. and RUBIN, J. E. (1963) Equiualents of the axiom of choice. North-Holland, Amsterdam, 134 pp. (2nd ed. (1970).) SACKS,G . E. (1972) Saturated model theory. Benjamin, New York, 335 pp. SHOENFIELD,J. R. (1954) A relative consistency proof. J.S.L. 19, 21-28.

CHOICE FUNCTIONS ON SETS AND CLASSES

255

SHOENFIELD,J. R. (1967) Mathematical logic. Addison-Wesley, Reading, Mass. 344 pp. SPECKER,E. (1957) Zur Axiomatik der Mengenlehre (Fundierungs- und Auswahlaxiom). Zeitschr. f. math. Logik 3 , 173-210. TAKEUTI,G. and ZARING,W. M. (1973) Axiomatic set theory. Springer, Berlin. 238 pp. TARSKI,A. (1948) Axiomatic and algebraic aspects of two theorems on sums of cardinals. Fund. Math. 35, 79-104.

SETS AND CLASSES; On the work by Paul Bernays @ North-Holland Publishing Company (1976) pp. 257-275.

A NEW FINITARY PROOF OF A THEOREM OF MOSTOWSKI Timothy B. FLANNAGAN’ Heidelberg, West Germany 0. Historical introduction

In NOVAK[1948], [1951], it was shown that if ‘5 is a consistent theory formalized in the first-order predicate calculus, and if CY is a theory related to 0: in much the same way as von Neumann-Bernays-Godel set theory is related to Zermelo-Fraenkel set theory ZF, then CY is also consistent. Novak’s method was to construct a model of Ef within the formal syntax of &. In 1949 in a talk at Princeton, Mostowski showed by an elementary argument that Novak’s proof could be adapted to prove the stronger result that Ef is a conservative extension of &. The argument is given in outline at the bottom of p. 112 of MOSTOWSKI [1951]. Later, ROSSERand WANG[I9501 gave another proof of the same result using Mostowski’s method. More recently, DOETS[ 19691 gave another proof by constructing a Henkin-type canonical model of 0:’.All these proofs have the property of being non-finitary, where “finitary” is taken in the sense of HILBERTand BERNAYS[1934], [1968], p. 32; but SHOENFIELD [1954], gave a finitary proof. In § 1 of this paper we give another finitary proof of this result. In fact, by slightly relaxing the usual definition of normality in the class comprehension schema (see A3, p. 259 below) we obtain a correspondingly stronger result than Mostowski’s. The central idea in the proof is due to Shoenfield, viz, replacing abstraction terms by their definitions; but for the following reasons, our proof is slightly more natural and direct: (1) We do not avoid bound-class variables in the manner of SHOENFIELD [1954] and we use €-terms of the form EXA for abstraction terms ( X being a class variable) since these are available anyway. (2) Shoenfield’s use of Hilbert and Bernays’ method of proof of the first €-theorem results in the unnecessary removal of bound individual (set) variables, and these must be restored.

’ The author is grateful to the Alexander von Humboldt Stiftung for financial support. 257

258

TIMOTHY B. FLANNAGAN

(3) We do not introduce Hilbert’s full ecalculus where the “subordination” of €-terms to other expressions may occur in logical axioms. In 92 we give some applications of the metatheorem proved in 91, and in 03 we ask some questions and make some remarks. 1. The theories % and @‘

Let 2 be a first-order language determined by: (i) a vocabulary “1’ consisting of sets of function and predicate symbols of finite order, (ii) a denumerably infinite set of individual variables x l , x2,. . . , denoted syntactically by the letters u, v, w , x , y, z with or without subscripts, and (iii) logical constants -, v , A , +, 3, V and = (identity).

% is a theory formalized in 2 and @‘ is a theory formalized in the language 2”which is obtained from 2 by adding the two-place predicate q (which must not be contained in 2) and a denumerably infinite set of class variables X I ,X 2 ,. . . The letters U, V, W, X , Y, 2, with or without subscripts, will be used syntactically to denote arbitrary class variables or individual variables. The letters Q , Q’ will denote either of the quantifiers 3 or V . Before defining @‘, we define a slightly less restrictive notion of a “normal” formula than the one used in WANG[1949], GODEL[1940], and consequently in SHOENFIELD [1954]. We say that a formula Q X A of @‘ is immediately subordinate to a formula Q ’ Y B of W if it occurs in B and a free occurrence of Y in B occurs within an occurrence of Q X A . We also say that Q X A is subordinate to Q’YB, if there is a finite sequence of formulas FI,F 2 , .. . , F,, with n > 1, such that F, is Q’Y B, F, is Q X A and for each i = 2,. ..,n, E is immediately subordinate to K1. The expression F ,,..., F, is called a subordination chain. A formula Qx A of W is called a (*)-formula,if there is a formula Q’ Y B and a subordination chain F1,. . .,F, ( n > 1) such that F , is Qx A and F. is Q’ Y B. An 9”-formula(i.e. a formula of 9”) is called a (**)-formula,if it is either a (*)-formula or a formula of the form Q X A . An 3”’-formula Q x A is called normal if it is not a (*)-formula. The non-logical axioms of W are those of % together with those Y-formulas of the form: A1 A2

vu,v(vx(xqU-xqv)+u=v) V U , V ( U qv+3x (x = U ) )

-

A FINITARY PROOF OF A THEOREM OF MOSTOWSKI

A3

259

VX,~~~X,3XVz(z~Xt,F I , . (. . z , ,X X” ) ) , where Vz ( z q X F(z, Xi,.... X , ) ) is normal in the sense above.

Showing that W is a conservative extension of 6 clearly involves, inter alia, the elimination of class variables and instances of Al-A3 from deductions from W of an 9-formula 8. The way in which it is done is [1973] of Hilbert’s first similar to the method of proof in FLANNAGAN €-theorem in HILBERTand BERNAYS[1939]. The calculus used is a weakened form of the €-calculus of Hilbert and Bernays, called the [1969]. Its axioms are the €*-calculus. This is described in LEISENRING proper axioms of the €-calculus (see below). The effect of this is that our method is more discriminating than the method in SHOENFIELD [1954] in that it necessitates only the elimination of (**)-formulas from deductions from W of 2-formulas and does not involve the elimination of all bound variables. 2. The €*-calculus

Let 2=and 9:be the €-languages obtained from 9 and 2”’ respectively by adjoining Hibert’s €-symbol. The well-formed expressions of 9:(see [1969]) include €-terms EXA,which we call ASSER[1957] or LEISENRING individual €-terms, and EYB (called class €-terms), where A and B are Of course the only €-terms in are individual eterms. formulas of 9:. The lowercase letters r, s, and t denote arbitrary individual terms of 9: (i.e. individual variables or €-terms) and R , S , and T denote arbitrary terms of 9:. Before defining the notion of a proper formula, we define the skeleton of a formula. Let A be a formula of 9:and t (resp. T ) have maximal length amongst the individual €-terms (resp. the class eterms) in A which do not have a free variable bound by a quantifier in A. Replace t (resp. T ) by the first individual variable x (resp. class variable X ) which does not already appear in A. Repeating this procedure, we find after finitely many steps that no more €-terms can be replaced. The resulting formula A’ is called the skeleton of A. If A’ is €-free (i.e. does not contain the €-symbol) we say that A is proper. Otherwise we say it is improper. For example, if A is the formula

3x ( xT l Y A € Z ( Z ? Y) l q €u(u 7l Y V u ll €v(Y‘f) v)))),

then A’ has the form

3x(XqYAXqZ),

260

TIMOTHY B . FLANNAGAN

so A is proper. If A is the Q3,-axiom (see below) -3X(X=YAX=EZ(Z'f) Y V Z = X ) ) + ( U = Y A U = E Z ( 2 q Y V 2 = U)),

7

then A' has the form -3X

(X =

Y

A X =EZ(Z

Tl

Y

V 2 =X))+-

(U = Y ) A U = V ) ) ,

so A is improper. We now define the calculus for 2: (which we abbreviate as E*") as [1969], p. 66): its only rule of inference is Modus follows (see LEISENRING Ponens and its axioms are all the proper 9;-formulas which are instances of the following schemata: (1) A certain list of tautologies called P-axioms: (2) The quantification axioms: Q1

Q2 Q3 I 432 Q4

VXA+-3X-A, VXA + 3 X A, 73~A+-A(t), 7 3 X A +7A(T), 3 X A +A(eXA). 7

7

(3) The identity axioms:

El E2

S = TA[AI$+[AI?, T = T.

As usual, [A]$ denotes the result of replacing every free occurrence of X in A by S.

In axiom schema E l , A is required to be an atom (i.e. a formula of the form S1q TI or S1= TI)in which X does not appear free within the scope of an e-symbol. A deduction in the calculus is defined in the obvious way and is called an E *-deduction.

-

REMARKS. (1) Instances of Ackermann's schema VZ([A]Z

[BIZ) + EXA = EYB

are not included in E*". (2) The axioms of the E *-calculus for S 'e (which we call E %) are just the axioms of E *r' which contain no class variables. For example, it is only Q3- and QCaxioms are proper axioms of the form 3x A + A ( t ) and 3x A + A (ExA)respectively. (3) In view of axiom A1 of f&", it is clear that in a deduction in E * ~of~ a

A FINITARY PROOF O F A THEOREM OF MOSTOWSKI

26 1

formula A from W, E3-axioms are redundant, but this fact is not used in the sequel. (which we call PC”) are just The axioms of the predicate calculus for 2’’ the €-free axioms of E*” and its rules of inference are: (i) Modus Ponens, (ii) the 3-rule: from A ( x ) + B infer 3 x A + B provided x does not occur free in B ; and from A (X) + B infer 3 X A + B provided X does not occur free in B. The axioms and rules of the predicate calculus for 9 (which we call PC,) are defined in the obvious way. We write MkpC,A, MkPc-A, M be.,, A, M ke*# A to denote that there is a deduction of A from M in PCo, PC”, E *,, E *” respectively. As usual, 0 kpc0 A, 0 bpcA etc. mean that A is derivable just from the logical axioms and rules of PC,, PC” etc. Our aim in this section is to prove the following metatheorem: METATHEOREM 2.1. There is a Jinitary proof that C?‘ is a conservative extension of Q. That is, if 8 is an 9-formula andW kpv 8, then B kpc, 8. ( E *,r,T,)-deductions

3.

As a measure of the degree of subordination of formulas to other formulas, we need the following notion of the rank of an 2”-formula QXA, rk (QXA): 1 if there is no formula Q ’Y B subordinate to it. rk ( Q X A ) = 1 +the maximal rank of the formulas Q’YB which are subordinate to it if there is such a formula.

-

i

Let 9 be a deduction in € * ” . I If the axiom 3 X A +A(EXA) or 3 X A + -,A (T) for some term T is used as a logical axiom in 9, then 3 X A will be called a class-Q-formula in 9. Similarly, if a (*)-formula 3 y B is the specified existential formula in the antecedent of a Q3- or then it will be called a (*)-Q-formula in 9. Of course, a QCaxiom in 9, (**)-Q-formula in 9 is either a class-Q-formula or a (*)-Q-formula. (See p. 258 above for the definition of a (**)-formula.) If all the (**)-Q-formulas in 9 have rank s r, then 9 will be called an (~*,r)-deduction.If in addition, all the (**)-Q-formulas in 9 are in some finite set T, of (**)-formulas of rank r, then 9 will be called an (E *, r, T,)-deduction. We write ’% k rA and ’% t--‘.TrAto denote respectively that there is an (E*,r)-deduction and an (E*,r,T,)-deduction of A from M. Since every class-Q-formula has rank 3 1 and every (*)-Q-formula has

‘ Note that

a deduction in

E * ~is

trivially a deduction in

E*”

262

TIMOTHY B . FLANNAGAN

rank 2 2, it is clear that an ( E *,l)-deduction contains no (*)-Q-formulasthat its only (**)-Q-formulas are class-Q-formulas. It is also clear that an ( E *,l$)-deduction is an ( E *,O)-deduction which in turn contains no (**)-Q-formulas, although it might well contain Q3- or Q4-axioms of the form 7 3 x A + - A ( t ) or 3 x A +A(ExA), where 3 x A is normal in the sense of p. 258 above. The proof of Metatheorem 2.1 involves the replacement of certain formulas by other formulas and E-terms by other terms, so we rely heavily on the following lemmata: LEMMA3.1. The following properties of the rank function are all trivial consequences of its definition and the notion of subordination:

R1. If Q X A is subordinate to Q’YB, then r k ( Q X A ) < r k ( Q ’ Y B ) . R2. If Q X A ’ is obtained from Q X A by replacing every occurrence of some €-term T by some other term, then rk (QXA‘) = rk (QXA). R3. If X is any variable which appears free in Q Y B and T is any term, then rk (Q Y [BITX)= rk (Q Y B ) . R4. rk ( Q X A ) = rk (QX -A). R5. If r k ( Q X A ) a r k ( Q ’ Y B ) and if Q X A is not Q’YB,and if * denotes the operation of replacing every occurrence of Q X A in Q’YBby rk (Q’ Y B ) . This apparently motiveless statement is used in Lemma 3.7 below. LEMMA 3.2 (cf. LEISENRING [1969], Theorem 111.1). If A is an axiom of E *” other than a Q4-axiom and if A is obtained from A by replacing every occurrence of some individual E-term (resp. class €-term) by some other individual term (resp. term), then A’ is an axiom of E*” of the same form as A. PROOF. The lemma is trivial if A is a P-, Q1-, Q2-, E l - or E3-axiom. Notice that the restriction on El-axioms is used here. Suppose that A is a Q3,-axiom. Clearly, the only way in which A can be damaged by the replacement of an €-term T by another term S , i.e. converted into a formula which is no longer a Q3,-axiom, is if it has the form

3x

7

( a *

*

EYB(Y,X) * *

a)+-

(

-

0

.

EYB(Y,t).. *)

where T is either EYB(Y,x) or EYB( Y , t ) . However, in this case an E-term will appear in the antecedent of the skeleton of A, contrary to the assumption that A is proper. A similar argument holds if A is a Q3*- or QCaxiom, Q.E.D.

A FINITARY PROOF OF A THEOREM OF MOSTOWSKI

263

LEMMA3.3 (cf. LEISENRING [1969], Theorem 111.3). Let '21 u {A} be any collection of 2.'-formulas. If there is a deduction o f A from i?I in E * ~ ,then there is a deduction of A from % in PCo. PROOF. Let 9 be a deduction of A from % in E * ~ .The proof is by induction on the number n of €-terms in 9, all of which are individual eterms. If n = 0, then 9 is already a deduction in PCo.Suppose n > 0. Let eyB have minimal length amongst the €-terms in 9. Then no eterms . x be some individual variable which does not occur in B occur in E ~ BLet or A and let 9'be the sequence of formulas obtained from 9 by replacing every occurrence of eyB by x. If the axiom (1)

3 y B +B(€yB)

is not used in 9,then by Lemma 3.2 and since A and i?I are €-free, 9' is a ~ which only n - 1 eterms are used. Hence, deduction of A from '21 in E * in A. by the induction hypothesis, '21 kpco If (1) is used in 9,then 9' is a deduction of A from 3 y B +. B ( x )in E *o in which only n - 1 €-terms are used. Since the deduction theorem holds in full generality in the E *-calculus,' we can therefore find a deduction 9'l of (2)

( 3 Y B +B(x))-,A

from % in E * ~which contains only n - 1 E-terms. Since (2) is €-free it follows from the induction hypothesis that '21 kpco ( 3 y B + B ( x ) )+ A. Now B (x) + A follows tautologically from ( 3 y B -j B ( x ) )+ A, so '21 kpco B (x) + A and hence % kpco 3 y B + A by an application of the 3-rule. Now A is a tautological consequence of ( ( 3 y B + B ( x ) ) + A ) A ( 3 y B + A ) , so '21 kPco A, Q.E.D. LEMMA3.4. Let '21 u { A } be any collection of 2."'-formulas and '21' be the collection of 2.'e:'-formulaswhich are substitution instances of the members of '21 formed by allowing E-terms of 2; in place of free variables. I f '21 kpc A, then '21' k....A . In particular, if the members of % contain no free variables and if '21 kpcA, then '21 k-..,, A. PROOF. Let ( A , ,...,An), denoted by 9, be a deduction of A from '21 in PC". One shows by an elementary induction on i that %' k....Ai.

LEMMA 3.5. Let r 2 1 and 3 Y B be a (**)-formula of rank r. Let A be an axiom of E*" and ' denote the operation of replacing every occurrence of 3 Y B by B ( E Y B )and i f B has the form C, by simultaneously replacing

-

' That is, if there is an E *-deduction of B from % u {A}, then there is an E *-deduction of A - + B from '?[.

264

T I M O T H Y B . FLANNAGAN

every occurrence of Q Y C by C ( E Y B ) .Then: (i) If A is a P-, E l - or E3-axiom, then A ’ is an axiom of the same form. (ii) If A is a Q1- or Q2-axiom other than V Y C + 7 3 Y C or V Y C +3 Y C, then A ’ is an axiom o f the same form. (iii) If A is a Q31-axiom 3 x D +7 D ( t ) or a QCaxiom 3 x D + D ( € x D ) ,where 3 x D is normal, then A’ is an axiom of the same form. (iv) I f A is a Q31-axiom 7 3 x D D ( t ) or a QCaxiom 3 x D + D(exD), where 3 x D has rank s r and 3 x D is not 3 Y B , then A’ is an axiom of the same form. Furthermore, by rank property R5, rk ( 3 x D ) = rk (3x 0’). (v) If A is a Q32-axiorn 7 3 X D + -D,( T ) or a Q4-axiom 3 X D + D ( E X D ) ,where 3 X D has rank 6 r and 3 X D is not 3 Y B , then A’ is an axiom o f the same form and rk ( 3 X D )= rk ( 3 X D ’ ) .

-

PROOF. Cases (i) and (ii) are trivial and the proofs of (iii)-(v) are similar to the proof of Lemma 3.2. We give only one example: Let A be the Q3,-axiom 3 X D + --r D ( T ) and suppose that A ’ is not the Q3*-axiom - 3 X D ’ + D’(T’). Clearly, one of the following cases must hold:

( 1 ) 3 Y B is 3 X D , but this is ruled out by the hypothesis of (v). (2) 3 Y B or V Y C is immediately subordinate to 3 X D, in which case, e.g. A has the form (1)

3 X ( ** ‘3Y H ( Y , X )* * *)

7

+

where 3 Y H ( Y , X ) is 3 Y B , and A’ is

3X

7

( . a

-

* H ( E Y HY( , X ) , X . .*)+-

(*

*3Y H ( Y , T ) * .),

*

9

(

0

.

‘ 3 YH ( Y , T )* *

a),

which is not a Q3,-axiom. ( 3 ) 3 Y B or V Y C has the form Q Y H ( Y , T ) , where Q Y H ( Y , X ) is immediately subordinate to 3 X D . In this case, A has the form ( 1 ) for example, and A ’ has the form

7 3 x (.

*3Y H ( Y , X )* * .) + (. * * H ( E Y HY( , T ) , T ) *.). . *

7

It follows immediately from the rank properties R1 and R3 that if either (2) or ( 3 ) holds, then rk ( 3 X D ) > r, contrary to assumption, Q.E.D. LEMMA3.6. If Q X , .. .Q’X,A is any proper %formula, then there are €-terms T I , .. ., T, such that

6) for each i = 1 * * * n, Ti is an individual €-term if X i is an individual variable and a class €-term if X i is a class variable, (ii) ~ ) - . * ~ , Q X , . * * Q ’ X ++[A]:;:::$. ,A

A FINITARY PROOF OF A THEOREM OF MOSTOWSKI

-

265

PROOF. The proof is by repeated application of the well-known and easily-established facts that if 3 Y B and V Y C are proper, then

0 be*.. 3Y B

(1) and

0 be*,, VYc

(2)

-

B (EYB)

C(€Y

-

C).

COROLLARY (Immediate). If A is any 2e:'-forinula and G"ke*<,A, then %* Fee,, A, where 6* is 0" with axioms Al-A3 replaced by

Al* A2* A3*

Vx ( x q s e x q T ) + S = T, S q T + 3 x (x = S ) , Vz ( z q T* ++ F ( z , TI,.. . , T,,)), where T* is E X V Z( z q X - F ( z , TI,..., T,))forsomevariableX.

We are now ready to prove the main lemmas in support of Metatheorem 2.1, but at this point we break off to briefly discuss the problems in proving it and to sketch the plan of the proof. Henceforth, 0 will denote a fixed 2-formula with no free variables. Consider an €*-deduction 3 of 6 from %*. If 9 contains no instances of axiom A3*, then the problem is fairly trivial (see Lemma 3.9). Suppose 9 does contain instances of A3*. One's first inclination would probably be to replace every expression s q T* by F ( s )(see the definition of A3* above). This would be a perfectly safe procedure were it not for the fact that (and this is the central problem in the proof) 9 must be assumed to contain Q3z-axioms 3 X A + A (T").

(1)

7

To replace the formulas s q T* would clearly damage Q3z-axioms of the form - 3 X ( . * * S q X . . * ) + - ( * * * sq T * . . - .) Now, this in itself is not a problem, for a manoeuvre similar to one used in the following lemma could overcome this difficulty if the only Q32axioms in 3 of the form (1) are those in which A is not of the form " ' S , q x . . . s 2 qx * * . s q ,x . . . , (2) where n > 1. Broadly speaking, the reason for this is as follows: Suppose that A has the form (2) and 3 X A has low rank. Replacing all formulas s q T* by F ( s ) converts (1) into

(3)

-

3XA

( * F ( s ~ .) . F ( s , ) .*

+7

*

a

a).

In the course of Lemma 3.7 we then want to replace some formula of the

266

TIMOTHY B . F L A N N A G A N

form 3 Y B by B ( E Y B ) ,where 3 Y B might have greater rank than 3 X A but might nevertheless appear in one of the formulas F ( s i ) ,i = 1 .* n, say F(sl),and contain sI.In this case, let us write B as B ’ ( Y , s l ) In . order to avoid damaging (3) beyond repair, we then need to replace not only 3 Y B ’ ( Y , s l )by B ’ ( E Y B ’ ( Y , ~ , but ) , ~ for ~ ) ,each i = 2 . - . n ,3 Y B ’ ( Y , s i )by B ’ ( E Y B ’Y( , s i ) , s i )However, . this leads to complications which we are unable to overcome. Hence, in order to replace all formulas s -q T* by F ( s ) we first need to eliminate all Q3,-axioms from 9. The first step in this elimination is the . this procereplacement of certain formulas 3 X A by A ( E x A )However, dure could damage Q3 ,-axioms 9

(4)

73yB-+-B(t),

for example, if 3 X A is immediately subordinate to 3 y B or if 3 X A has , 3 X H ( X , y )is immediately subordinate to the form 3 X [ H ( X , y ) l t Ywhere 3 y B. But in this case, 3 y B is a (*)-Q-formula. Hence, we must not only eliminate all Q3z-axioms, but all Q3l-axioms (4) where 3 y B is a (*)-formula. We do this in fact by eliminating all (**)Q-formulas from 9. We start with those of maximal rank. Once the above eliminations have been carried out, we replace s q T* by F ( s ) etc. The rest is easy. LEMMA 3.7. For any r 2 1 and any finite set T, of (**)-formulas of rank r, if &* 1”’. 8, then &* Fr.’ 8.

PROOF. Let ( A,,. . . , A ” ) ,denoted by 9, be an (E*,r,T,)-deduction of 8 from 6”. The proof is by induction on the number of (**)-formulas in T,. If n = 0, 9 is already an (~*,r,O)-deduction.Suppose n > 0. Let 3 Y B have maximal length amongst the (**)-formulas in T,. Put S, = T, - { 3 Y B } . We show that &* kr.’r8 and then apply the induction hypothesis. The proof is exactly the same as if we had chosen a formula 3 y B of maximal length amongst the (**)-formulas in T,. We may suppose that 3 Y B is a (**)-Q-formula in 9, for otherwise 9 is already an ( E *,r,S,)-deduction. Let ’ denote the operation of replacing every occurrence of 3 Y B by B ( E Y B ) ,and if B has the form C , by simultaneously replacing every occurrence of V Y C by C ( E Y B ) . The formula 8’ is clearly 8 since 8 is an 9-formula and 3 Y B and V Y C contain class variables. Since no member of E* I is a (**)-formula, and here we make essential use of the normality of instances of axiom schema A3*, it is trivial to see that if Ai is a member of &*, then so is A:.

’ By

a member of &* we mean a non-logical axiom of &*

A FINITARY PROOF OF A THEOREM OF MOSTOWSKI

-

267

If A, is the Q1-axiom V Y C +73Y C or the Q2-axiom 7 V Y C + C or the Q6axiom 3 Y B + B ( E Y B ) then , A, is clearly one of the 3Y tautologies

!

-

(1)

C(EYB)’B(EYB), C(EYB)+B(EYB), B ( E Y B )+ B ( E Y B ) .

If A, is a Q32-axiom 7 3 Y B +-, B ( T ) for some term T, then A: is

-B(EYB)+~B(T‘). Since there are no (**)-Q-formulas in 9 of rank > r , it now follows from Lemma 3.5 by our choice of 3 Y B with maximal rank that if A, is any other logical axiom in 9, then A: is an axiom of the same form. If A, is a 4 3 - or QCaxiom, then the rank of the specified existential formula 3 X D in its antecedent is unaltered-in particular, if rk ( 3 X D )= r (i.e. 3 X D is in S , ) , then 3 X D ’ is 3 X D - and we say that members of S, remain members of S,. Modus Ponens is clearly preserved under the operation I , that is, if A, follows by modus ponens from A, and A, + A, for some j < i, then A : follows by modus ponens from A: and A’,+A:. Hence, by augmenting ( A ; , .. . ,A;), call it 9‘, with proofs of the tautologies (I), we find that for some terms T I T,,, (2) 6*u {- B ( E Y B ) - +B~( T , ) ,. . . ,

B(eYB)+-

B(T,)}

k.”“,8.

We now have two cases to consider.

) a member of a*. In this case, it is not an instance Case (i). C ( E Y B is of A3* since such formulas have the form D ( E X D ) Hence, . C ( E Y B )must be an instance of Al* or A2*, in which case, the formulas C ( T , ) ,for i = 1 ... rn are also instances of Al* or A2*; so by virtue of the tautologies C(T,)+~B(EYB)+~B(T,) it follows from (1) that B*

l r . ’ 7

8.

Case (ii). C ( E Y B )is not a member of a*. In this case 9 must be allowed to contain Q3-axioms 3 Y B +7 B ( T ) ;that is, rn in (2) must be assumed to be 3 1. We therefore proceed as follows: by (2) and the tautologies B ( € Y B ) + 7 B ( E Y B ) + B~( T , ) B(T,)+B(EYB)+B ~(T,) we obtain (3)

i-

B* u { B ( E Y B )Fr”, } 8

268

TIMOTHY B. FLANNACAN

and Q* u {- B ( T , ) , . . ,

(4)

-

B ( T , ) } Fr*’,8.

Let ‘& be an (E*,r,S,)-deduction of 8 from Q* u { B ( E Y B ) }and , for each 1 * * rn, let qi be obtained from ’& by replacing every occurrence of EYB by Ti.Let ” denote this operation. By Lemma 3.2 every logical axiom in ’G: becomes under ” an axiom of the same form. Moreover, by rank property R2, the ranks of the (**)-Q-formulas are unaltered. In particular, by our choice of 3 Y B with maximal length, EYBcannot appear in any (**)Q-formula in ‘G: of rank r. Hence, members of S, remain members of S,. If E Y B is a specified term in an instance I of Al* or A2*, then clearly I” is a formula of the same form. We suppose that E Y B is not the specified class term T* in an instance of A3* in %, for otherwise B ( E Y B )is an instance of A3* and by (3) the required result, namely, &* F r , ’ r 8, would follow. Modus ponens is clearly preserved under ”, so for each i = 1 . * m we obtain B* u { B (Ti)} Fr,’r 8, i

=

-

Fr”,8, Q.E.D. If &* ko8, then Q*-A3* ko13. (A ,,... ,A”), called 9, be an (c*,O)-deduction of

and finally, Q* LEMMA3.8. PROOF, Let

6* and suppose that for i

Mi

= 1.. . rn,

VZi (Zi

q T:

-

the formulas

8 from

E (Zi)),

where is €XiVzi (ziq Xi c* F i ( z i ) )are the instances of A3* used in 9. We systematically eliminate these formulas in a manner similar to the elimination of abstracts in SHOENFIELD [ 19541. We may clearly suppose that TT is at least as long as any other TT, i = 2 * . * m. For each j = 1 * n, let A: be obtained from Aj by performing the following three operations in the order r 1-r3:

--

rl. Replacing all formulas TT q S by 3 u ( u q S A Vv (v q u f-, F l ( v ) ) , where u and ‘u are new individual variables. r2. Replacing all formulas S = TT and TT = S by Vv (v q S t,Fl(v)). r3. Replacing all formulas S q TT by 3 w (w = S) A F , ( S ) ,where w is a new individual variable distinct from u and 21. REMARK. The order rl-r3 is not the only order which ensures that formulas eliminated by one replacement are not restored by another. For example, the order r3, r2, r l would do. However, the order r2, r3, r l would not do because r2 eliminates formulas of the form x = TT, but these are restored by the application of r3 to the formula TT = TT. Clearly under rl-r3 the formula MI becomes

A FINITARY PROOF O F A THEOREM O F MOSTOWSKI

269

Vzl Q w (w = zl) A Fl(zl)f,Fl(zl))

(1)

and by our choice of TT with maximal length, every other M,, i = 2 . . . m, is unaffected; that is, if A, is M, for i = 2 . . m, then A: is A,. If A, is an instance of Al*, then either TT is neither of the specified terms in A,, in which case, A: has the same form as A, ; or TT is one of the specified terms in A,. In this case, A: can only be a formula of the form

s)+vV

s t*Fi(U)),

(2)

VZ Q W (W = Z )

(3)

V Z ( Z Y S C * ~ (WW = z ) A F I ( Z ) ) + V V( v ~ S ~ * F I ( V ) ) ,

A Fi(Z)t*Z

T)

(0 r)

or (4)

Vz Q w (w = 2) A FI(z)*3w (w = 2) A Ft(z))+ + V V (3w (w = V ) A F l ( v ) t * F l ( v ) ) .

If A, is an instance of A2*, then A: can either be a formula of the same form or a formula of the form (5)

(6)

3~ (U

S

A

V V( V q

*Fi(V)))+3X VV

3 u (3w (w = u ) A F l ( u ) A +3x

or (7)

U

Vv ( V

vv (v -q x *

qu

(V

qX

c* F l ( V ) ) ,

* Fl(u)))

F1(v)),

3 w (w = s ) A FI(S)+3x (x

=

s).

If A, is 8 or a member of 6,then A: is A, since A, contains no class variables and TT does. If A, is a P-, Q1- or Q2-axiom, then A: is obviously a formula of the same form. then TT cannot be the specified term in If A, is a Q3- or QCaxiom in 9, A, since, 9 being an (E*,O)-deduction,the only Q3- and QCaxioms in 9 are those whose specified existential formula is normal and hence whose specified term is an individual term. Hence, A: is an axiom of the same form. For example, suppose A, is 32 B +7 B ( t ) and that " denotes the operation r3-of replacing every formula S q TT by 3 w (w = S) A FI(S). Since B is proper (9 being an €*-deduction), t can appear in neither S nor TT. Hence, either S is not t, in which case, A:' clearly has the form 7 3 2 B " + - B " ( t " ) , or S is t and B has the form - - - z r )T T - . .. In this latter case, A': clearly has the form -32 ( * * * 3 W (=W2 )

A

F,(Z)*.*)-t -(*.'3W(W = t ) A F,(t)".),

so it is a Q3-axiom, and moreover, -32 .-3w(w= z ) A Fl(z).. -1 is normal. An easy check shows that if A, is any other logical axiom in 9, then (a

270

TIMOTHY B . FLANNAGAN

0 1"A :. We give one

example: if Ai is an El-axiom

TT = S

A

S q R + TTq R ,

where neither S nor R is TT, then A: is (8)

where

-

VV ( V q

s

t*Fi(U))

A

s q R +'3U

(U

'fl

RAv U

(U r( U t * F i ( V ) ) ) ,

denotes the result of performing r l then r2.

Since (1)-(8) are formulas G such that

01' G, it follows that

& u A l * u A2* u {A&,. . . ,M,,,}k"8. Hence, repeating the above procedure m - 1 more times, we finally see 8, Q.E.D. that &*-A3* 1" LEMMA3.9. If &*-A3*k0 8, then

&kpco 8.

PROOF. First, note that &*-A3* is & u A l * uA2*. Let (A1,..., A,,), called 9, be an (E*,O)-deduction of 8 from 6*-A3*. Let 9'be obtained from 9 by replacing all class variables by suitable new individual variables. It is trivial to verify that 9'is a deduction in E*" of 8 from & u Al*', where Al*' is the schema vz

(2

qs

-2

q t)+s

= t.

If there is a two-place predicate P in the vocabulary 'If such that vz (Pzs t* P z t ) + s = t

holds in 6,then by replacing every formula s q t in 9' by Pst, one easily 8, and hence by Lemma 3.3 that (5 Fpc0 8. If there is no shows that (5 le*o such predicate P in 'If, then P may be taken to be the identity, Q.E.D. REMARK In the above proof, we made essential use of the requirement that q is not a predicate in the vocabulary 'If. THE PROOF OF METATHEOREM 2.1. By Lemma 3.4, if 6'' kpcra 8, then G" k....8. Hence by Lemma 3.6 we have &* k-.... 8, so for some Y and T,, &* kr,Tr 0. Hence by Lemma 3.7, B* kr,O 8. But an (E*,r,O)-deduction is an ( E *,r-l,S,.I)-deduction for some &,. Hence, by repeated applications of Lemma 3.7, we obtain &* 8. By Lemmas 3.8 and 3.9, it follows that 6 ~ P C , 8, , Q.E.D. 4. Applications of Metatheorem 2.1

In view of the replacement operations in Lemma 3.7, it is clear that if G(T,,. . . ,T,) is a normal 2"'-formula in the sense of p. 258 above, then in Lemma 3.7 all formulas of the form G may be added to &* as axioms.

A FINITARY PROOF OF A THEOREM OF MOSTOWSKI

27 1

However, unless we further stipulate that G contains no class terms, it seems impossible to ensure that it survives the replacement operations in Lemma 3.8; but certainly, any such 2"-formula without class terms which is valid in 6,when 77 is replaced by either = or some two-place predicate P of 6, will survive all the replacement operations of Lemmas 3.7-3.9. Hence all such formulas may be added to 6 in the statement of the metatheorem. It seems that we cannot generalize any further, and unfortunately, the requirement that G contains no class terms is so severe as to be of no apparent value. However, it is easily seen that certain normal 9formulas which contain class variables do, in a sense, survive the replacement operations of Lemmas 3.8 and 3.9. We give three examples. 4.1. Let Q be Peano Arithmetic N (see SHOENFIELD [1967], p. 204). Let N" be obtained from N as (5" is obtained from 0 and by allowing the quantified formulas specified in the induction schema

A ( 0 ) A Vx (A(x)+A(x'))+VxA(x),

Ind

where x' is the successor of x, and is to be normal in the sense of p. 258. In N", Ind is then equivalent to the single axiom VX(OqXAVX(XqX~Xx'1X)~Vx(XqX)).

Now consider the schema Ind*

oqT

A

vx(x q T + x ' q T)+Vx

(X

q T),

where T is an arbitrary term, and let N* be 6 u Al* u A2* u A3* u Ind*. Since the formulas Vx (x q T + x ' q T ) and Vx (x q T ) are normal, Ind* survives the operations of Lemma 3.7; i.e. if N" kr,Tr 8, then N" k"' 8. Now under the replacement operations rl-r3 in Lemma 3.8, any instance of Ind* either becomes a formula of the same form or a normal formula of the form Fi(0) A 3 W (W

= 0) A

Vx (3W (W = X )

A Fi(X)+aW

+VX (3W (W

=X)

A

(W = X ' ) A F i ( X ' ) )

FB(x)),

which is an instance of Ind. The proof of Lemma 3.8 therefore shows that if N"ko8, then N*-A3* k"0 ; and the proof of Lemma 3.9 shows that N kPc, 8. Hence, N " is a conservative extension of N. The proof that NBG is a conservative extension of ZF is similar to the proof above. As axioms of NBG we may take the group of axioms A u C together with the schema M4 (see GODEL[1940]). However, the specified formula cp in M4 is required to contain no bound-class variables. We relax this condition by considering instead the system NBG", namely, 4.2.

272

TIMOTHY B. FLANNAGAN

A u C u A3,, where the subscript n is used both to emphasize the fact that instances of A3* are normal and to distinguish the schema A3, from the axiom A3 in the group of axioms A. We show that NBG”is a conservative extension of ZF. By interpreting Gls ( X ) as X = X and % ( X ) as 3 x (x = X ) , it is trivial to verify that the axioms A1-4, C1-3 of NBG”hold in B* when B is ZF. The proofs are purely finitary. Thus, we only need to show that the Ersetzungsaxiom C4 “survives” the various replacement operations in Lemmas 3.7-3.9. Let C4* be the following schema:

lln(T)+gy Vz (zq y - 3 u

(u q t

A

(u,z)q T))’

and B** be B* u C4*. Since every quantified formula which is specified in C4* is normal, C4* survives Lemma 3.7 intact. Furthermore, under the operations rl-r3 of Lemma 3.8 an instance of C4* either becomes another formula of the same form or a normal formula of the form (1)

Vu,z,z‘(A(u,z) A A(u,z’)+ z

= z’) +

+ 3 y vz ( z q y - 3 u ( u

A(u,z)),

qt

A

and further applications of rl-r3 do not damage these. Let us denote by Rep, the collection of formulas of the form (1) in which the quantified formulas which are specified are normal, and let us denote by Rep the collection of %’-formulasof the form (1). Then Lemmas 3.7 and 3.8 show 8, then (&**-A3*) u Rep, 1 ’8. Now the operations in that if B** kr,Tr Lemma 3.9 convert instances of C4* and Rep, into instances of Rep. Hence, Lemma 3.9 shows that if (a**-A3*) u Rep,, ko8, then 6 kpc0 8. Hence, NBG” is a conservative extension of ZF. An immediate corollary to the above is that NBG and NBG” are equivalent in the sense that they have the same theorems in the language of ZF, but we get a stronger result than this in 43. 4.3. Finally, let 6 be the theory of New Foundations (NF) in QUINE119571 and ML”be obtained from the Wang-Quine system ML in QUINE[ 1951J by allowing the comprehension axiom “202 to be normal in the sense that A3 is normal. Note that ML can equivalently be written in a two-sorted language. Thus, ML”is 6” and Metatheorem 2.1 applies as it stands to show that ML”is a conservative extension of NF. I Here, llIl(T) and (u,z)qT are abbreviations of the usual set-theoretic formulas, but written with q instead of E (the usual two-place predicate of Zermelo’s set theory).

A FINITARY PROOF OF A THEOREM OF MOSTOWSKI

273

5. Other definitions of a normal formula Throughout the proofs of Lemmas 3.7-3.9 we emphasized that instances of A3* were normal in the sense of p. 258. Since this requirement is weaker than the usual one, it might seem that the results in 92 are stronger than [1954]. Indeed, since we did not the corresponding results in SHOENFIELD require that instances of Ind contain no bound-class variables, our result that N " is a conservative extension of N certainly appears to be stronger than the corresponding result in SHOENFIELD [1954]. However, this is not so for the cases NBG" and ML", for if ML' is like ML" except that it only contains instances of A3 whose specified formula F ( z ) contains no bound-class variables, then since the ordered pair (x,y ) is definable in NBG and ML', one can easily show by induction on the length of formulas that NBG A3Z and ML'I- A3:. Now, it is natural to ask if it is possible to obtain stronger results than those already obtained, by weakening still further the requirements of the normality of the schema A3*-for example, by N1.

N2.

only requiring that there is no formula Q X B ( X , z ) in F ( z ) which is immediately subordinate to Vz ( z q T* f* F ( z ) ) , X being a class variable, not an individual variable; or allowing instances of A3 to be impredicative, that is, allowing F ( z ) to be any Y'-formula with one free individual variable.

Let 6';and &; be the theories obtained from 6'' by replacing our notion of normality by N1 and N2 respectively. @is what QUINE[1951], p. 316, calls an impredicative enlargement of 6. Quine pointed out that WANG[I9491 showed that Ky (and hence (5';) is a conservative extension of 6, but the proof is non-finitary and we can or &; can see no way of adapting the proof of Metatheorem 2.1 so that 6'; be inserted in place of K" in the statement of the Metatheorem. The reason for this is that the methods we used insist upon the elimination of (**)-formulas, and there seems to be no way of doing this when instances of A3* are permitted to be (*)-formulas. In fact, we suspect that if there is one, a finitary proof of Wang's theorem would use different methods altogether from those used here, but it would also use the result of Metatheorem 2.1. We conclude with a question and some remarks. Let NBG, be like NBG except that instances of the class comprehension schema are only required to be normal in the sense of N1 above.

+

QUESTION. Is there a finitary proof that NBG E (resp. NBG, + E) is a conservative extension of NBG AC (resp. NBG, + AC) with respect to

+

274

TIMOTHY B. F L A N N A G A N

ZF-formulas, where E is Godel's axiom of choice and AC is the ZF-form of the axiom of choice? [1971], FLANNAGAN It is well known (see for example, FELCNER [1973], and GRISIN [1972]) that NBG+E is a conservative extension of NBG AC with respect to ZF-formulas, but since a choice function in the sense of E only makes selections from sets, there is no strong reason known to us as to why the axiom of foundation should be necessary in the statement of the theorem. Moreover, there is no known recursive proof of the result, let alone a primitive-recursive proof. If a primitive-recursive proof could be found, it might well make no use of the axiom of foundation in NBG and hence might yield a proof that NBG'+E is a conservative extension of NBG"+AC with respect to ZF-formulas, where ' denotes the absence of the axiom of foundation. The question of whether this result is true was raised in FLANNAGAN [ 19731 and independently in GRISEN[1972], but the question is still open. The nearest solution is the following (given by the author in a talk in Oberwolfach, April, 1974). If Q is a ZF-type set theory, and Q, is obtained from it by adjoining the one-place function symbol u,adding the axiom x # O-. u ( x ) E x and allowing u to figure in the schemata of Q, then every cr-free theorem of S;+CR: (and hence of ZF:) is a theorem of So + CRS+ AC; and for A 1, every u-free theorem of ZF2 (N& (and hence of (ZM,'),) is a theorem of ZF'+N,+AC. For notation, see FLANNAGAN [1974] or LEVY[1960].

+

*

+

References ASSER, G. (1957) Theorie der logischen Auswahlfunktionen. Zeitschr. f. Math. Logik 3 , 30-68. DOETS, H. C. (1969) Novak's result by Henkin's method. Fund. Math. 64, 329-333. FELGNER, U. (1971) Comparison of the axioms of local and universal choice. Fund. Math. 71, 43-62. FLANNAGAN, T. B. (1973) Ph.D. thesis. London. FLANNAGAN, T. B. (1974) Set theories incorporating Hilbert's E-symbol. Dissertationes Math. 154. Warszawa. GODEL, K. (1940) The consistency of the axiom of choice and of the generalized continuum hypothesis with the axioms of set theory. Annals of Math. Studies, Vol. 3. Princeton. 66 pp. (2nd printing (1951), 74pp.) GRISIN,V. N. (1972) The theory of Zermelo-Fraenkel sets with Hilbert €-terms. Math. Notes Acad. Sci. U.S.S.R. 12, 779-783. HILBERT,D. and BERNAYS,P. (1934-1939) Grundlagen der Mathematik I(1934); I1 (1939). Springer, Berlin. 471; 498 pp. (2nd edition (1968); (1970), 488; 575 pp.)

A FINITARY PROOF O F A THEOREM O F MOSTOWSKI

275

LEISENRING,A. C. (1969) Mathematical Logic and Hilbert’s symbol. Gordon and Breach, New York, 142 pp. LEVY, A. (1960) Axiom schemata of strong infinity in axiomatic set theory. Pacific J. Math. 10, 223-238. MOSTOWSKI,A. (1951) Some impredicative definitions in the axiomatic set theory. Fund. Math. 37, 11 1-124. (Corrections, ibid. (1952) 38, 238.) NOVAK, I. L. (1948) A construction for models of consistent systems. Ph.D. thesis, Harvard. NOVAK,I. L. (1951) A construction for models of consistent systems. Fund. Math. 37, 87-1 10. QUINE,W. V. (1937)New foundations for mathematical logic. Am. Math. Monthly 44,70-80. (A revised and expanded version is in QUINE (1953), pp. 80-101.) QUINE, W. V. (1951) Mathematical Logic (revised edition) Harvard University Press, Cambridge, Mass., 346 pp. (First edition (1940).) QUINE,W. V. (1953) From a logical point of view. Harvard University Press, Cambridge, Mass, 184 pp. QUINE, W. V. (1963) Set theory and its logic. Belknap Press, Cambridge, Mass., 359 pp. (Revised ed. (1%9), 361 pp.) ROSSER, J. B. and WANG, H. (1950) Non-standard models for formal logics. J.S.L. 15, 113-129. (Errata, ibid. p. iv.). SHOENFIELD,J. R. (1954) A relative consistency proof. J.S.L. 19, 21-28. SHOENFIELD,J. R. (1967) Mathematical logic. Addison-Wesley, Reading, Mass. 344 pp. WANG, H. (1949) On Zermelo’s and von Neumann’s axioms for set theory. Acad. Sci. U.S.A. 35, 150-155. WANG, H. (1950) A formal system of logic. J.S.L. 15, 25-32.

SETS AND CLASSES; On the work by Paul Bernays

@ North-Holland Publishing Company (1976) pp. 277-323.

REFLECTION PRINCIPLES AND INDESCRIBABILITY Klaus GLOEDE Heidelberg, West Germany 0. Introduction

The aim of this paper is to present some results supplementary to P. Bernays' investigation of a second-order reflection principle (BERNAYS [ 19611). This schema is classified within the hierarchy of reflection principles for various classes of formulas, beginning with the first-order language of Zermelo-Fraenkel set theory, which leads to the principles first introduced and studied by LCvy, and ending with the language of finite (or even transfinite) type theory, which is related to the notion of indescribability in the sense of Hanf and Scott. Taking this view, one is led in a natural way to take into account two aspects in the investigation of various set theories: (i) the distinction between class terms (in the sense of ZermeloFraenkel set theory) and class variables (in the sense of Bernays and von Neumann-Bernays set theory) and (ii) the classification of set-theoretical formulas according to their logical complexity. Montague-Vaught's theorem is the most illuminating and striking illustration of (i), and we shall encounter a similar phenomenon at a higher level of type. (ii) Leads us to consider some subtheories of the BernaysLCvy theory BL, in particular the theory EL, which corresponds to II,'-indescribability. A comprehensive treatment of the subject as indicated would require a whole monograph. Therefore, we restrict ourselves primarily to those results which have not yet been published in detail (although they seem to be well known to a large extent). 1. Reflection principles in set theory without class variables 1.1. Reflection principles in the language of ZF set theory 1.1.1. The language of ZF set theory, denoted by YZF,is the usual first-order language with (set) variables vo, v , , ...,atomic formulas v, = v,

277

278

KLAUS GLOEDE

and v,,E v,, and the logical symbols 7 , A , v, +,t*,V and 3.We also use lowercase letters a, b, c ,... for free, and u, v , x ,... for bound variables (possibly with indices). Formulas of this language are denoted by cp, $, . . . . Some of the notation is self-explanatory. 1.1.2. Relativization. If cp is a formula of LEzF, the relativization of cp to a, denoted by Re1 (a,cp)or simply cpa, is the formula obtained from cp by replacing any quantifier Vx or 3 x occurring in cp by Vx E a and 3x E a respectively. Here, Vx E a $ and 3 x E a t,b are regarded as abbreviations of the formulas Vx (x E a + $) and 3 x (x E a A $) resp. Though the operation of relativizing is a purely syntactical notion (to be defined by recursion on the subformula relation), it has an obvious model-theoretic interpretation: Let T be a sufficiently strong set theory, e.g. Zermelo-Fraenkel set theory ZF or the Kripke-Platek theory KP of admissible sets (which we usually assume to include the axiom of infinity). One can define in T a set Fml,, which intuitively represents the set of all formulas of the language of ZF. Every formula cp of ~ Z corresponds to a suitably chosen term ’cp7 of T (the “Godel number of cp” which may be a natural number or, more generally, a hereditarily finite set) such that T rcpl E FmlzF. Moreover, in the usual recursive manner one can define in T a formalized notion of satisfaction in a structure ( a ,E ) by a formula $o(vo,v1,v2) of 2 z F such that

(a) in T +ho(a,e,b)intuitively expresses the statement

“ e is the Godel number of a formula cp of LEzF with free variables among v,, . .., v,,for some natural number n, b is a sequence of n + 1 elements of a and cp is true in the structure (a,E ) if b ( i ) is assigned to vifor i = 0,. . . , n”, (b) one can prove in T the following schema:

for any formula cp with Godel number e and any assignment b as in (a). (For more details see, e.g. JENSEN-KARP[1971],p. 147, or LEVY119651, 05, for formulas of rank sj, it is rather obvious how to remove this restriction.) In order to remind the reader of the intuitive interpretation of the formula we write for $,,(a,e,b),

F

REFLECTION P R I N C P L E S A N D INDESCRIBABILITY

or-somewhat

,279

imprecise-

( a , E ) F e [b(O),...,b(n)I (if n is suitably chosen). Thus, we may read cp a (an,. ..,a,) as “cp holds in a ” (under the obvious assignment and with the obvious interpretation of the membership relation). However, it should be kept in mind that cpa(an,..., a,) is a formula of TZF (in contradistinction to the metamathematical statement “cp holds in a”) and hence corresponds to a formalized notion of satisfaction. 1.1.3. Reflection principles (introduced into set theory by LBVY[ 19581). These are schemata of the following form: PR, (9)

cp(ao,..., an)+3u [$(U)Aao,..., a, E u Acp’(ao ,..., a,)] (partial reflection)

or

C R, ( 2 )

3~ [ a E u A t , h ( u ) v V x o * * -Eu(cp(Xn, x. ...,X n ) (py(xn,...,xn)>l (complete reflection )

where in both cases cp is any formula of 9 with free variables among v,, ..., v, and $ is some fixed formula (containing possibly free variables in addition to the indicated variable). If 9 contains formulas which are not in the basic language ZzF,the notion of relativization has to be extended in a suitable way to apply to all formulas of 2;examples of such extensions are discussed later. In view of the model-theoretic interpretation of the notion of relativization (1.1.2) one can interpret these principles roughly as follows:

any property (not necessarily in the one-place sense) which is expressible by a formula of 2 and which is true in the universe (under some given assignment) is true (under the same assignment) in some set satisfying $ (PR,(9)); or in the case of complete reflection (CR$(9)):

for any property expressible by a formula cp of 6p and any set a there is a set b which contains a as an element, satisfies $ and is a complete “reflection” ofthe universe with respect to the property expressed by cp. It is shown in the sequel that reflection principles can conveniently be applied to yield the existence of sets satisfying certain closure properties.

280

KLAUS GLOEDE

In standard axiomatizations of set theory, the existence of such sets is proved by means of the axiom schema of replacement and certain types of the axiom of infinity. Conversely, the latter axioms, together with some basic axioms of set theory, imply certain types of reflection principles. (This fact should be rather obvious to anyone familiar with the Lowenheim-Skolem theorem.) Axiomatizing set theory by means of reflection principles has several advantages. First, from the model-theoretic interpretation of these principles, one can easily deduce metamathematical properties of the corresponding systems (e.g. in the case of CRTrans(ZzF): Z F is not finitely axiomatizable).’ Second, the principles of partial and complete reflection €or the language of ZF set theory admit straightforward generalization to richer languages (higher order, infinitary languages, etc.), thus yielding stronger axiom systems, or else can be weakened by restricting Z to suitable classes of formulas. 1.1.4. For the sake of completeness and later reference, we indicate main steps for a proof of the well-known fact that the axioms of ZF can be derived from a principle of complete reflection together with some basic axioms. The axioms of ZF are the following:’ Ext Pair

Sum Pow Inf RePIS Fund

-

V x ( x E a ++ x E b ) + a = b (Extensionality) 3 x V y ( y E x t,y = a v y = b ) (Pairing) 3x Vy(y E x (3z E a ) y E z ) (Sum set) 3 x V y ( y E X t,y a ) (Power set)

3 x @ Y ( Y E x ) A V Y E x ({y)Vx)l (Infinity) VX,Y,Z (cp(X,Y,...)A(X,Z,...)--, Y = z ) + (Axiom schema 3 z V y ( y E t t,3 x E a ~ ( xy , . . .) of replacement) (Axiom of foundation, 3 y ( y E a ) - + 3 y E a Vz E yz$Z a Fundieru ng )

Here and in the following we use the common set-theoretical notations: ( a } = {a,a}, ( a & ) = {(a},(a,b}} (ordered pair), C (inclusion), P ( a ) (power set of a ) . A Ao-formulacp is a formula of TEZF in which all quantifiers are restricted to sets, i.e. of the form Vv, E v,,, or 3v, E urn (LEVY [1965]).For example Rel(rp,a) is a Ao-formula in which all quantifiers are restricted to the same set a ; in

0 (empty set), {a,b) (unordered pair),

I A proof of this statement (due to R. Montague) can be found e.g. in FELGNER [1971al, p. 20 and KRIVINE(1971), p. 54. For a generalization, cf. LEVY[1%0]. ’The symbol “=” is regarded as a logical symbol.

28 1

REFLECTION PRINCIPLES AND INDESCRIBABILITY

general, quantifiers may be restricted in A,-formulas to different set variables. Thus, the definition of a transitive (or complete) set may begiven by the following A,-formula: Trans ( a ) : f* Vx E a Vy E x (y E a). We also need the following definition: Strans ( a ) :-Trans (a) A Vx E a V y (y C x + y E a ) ( “ a is supertransitive (supercomplete)”; cf. BERNAYS [1961] and SHEPHERDSON [19521).

We frequently make use of the fact that Ao-formulas are “absolute” with respect to transitive sets, i.e. if cp(ao,...,a,) is a A,-formula with free variables as indicated then

-

Trans (a ) -+ Vxo. x. E a

(cp (x,,

. ..,x, )

-

Re1 (a,cp (x,, .. . ,x,)).

The Aussonderungsschema (schema of subsets)

AusS

3XVy(yEXt*yEU

A

cp(y, ...))

is provable in ZF. For our purposes, it is often sufficient to consider the weaker

AO-AUSS

3X

v y (y

E

E X f*y

where cp is any Ao-formula. We now turn to the principles PR,

U A

cp(y, ...))

= PR,(LF’zF)

and CR, = CR,(LF’ZF):

1.1. PROPOSITION

(a) (b)

Ext + A,-AusS Ext + A,-AusS

+ PR, Pair (for any formula + PRTrans Pair + S u m + Inf.

+),

PROOF. Applying PR, to the formula Uo

= UoA

Ul

= Ul

we obtain the formula 3X

(UoEX

A

UlEX)

and hence Pair by means of A,-AusS. This proves (a). The proof of (b) is similar and is given in BERNAYS[1961], pp. 127-128. REMARK1.1. Let PRJ be the schema cp(ao,..., & ) + 3 u

($(u) A ( P U(ao,...,an))

282

KLAUS GLOEDE

(cp any formula of LZZF),as considered in BERNAYS [1961], p. 126. Though this is a weakening of PR,, both schemata are in fact equivalent. (To deduce an instance of PR, from PRI, apply P R I to the formula cp(ao,..., an)A 3 x (x = ao)A . . - A3 x (x = a n ) . )

+ PRs,,

PROPOSITION 1.2. Ext + A,,-AusS

Pow.

PROOF(cf. BERNAYS[1961], p. 139). By PRs,,,,, there is, for any set a a set b such that a Eb

A

Strans ( b ) ,

hence a Eb

A

Vx E b Vy (y C x + y E b),

p(a)Cb.

Hence 9 ( a ) is a set by A,-AusS. Using the axiom of pairing, if $(a)+Trans(a), CR, implies PR,. However, whereas the derivation of the axiom of pairing from PRJ, is obvious, we first need the axiom schema of replacement to derive Pair from CR* Without using Pair one can prove as in Propositions 1.1 and 1.2: PROPOSITION 1.3. (a) (b)

+ + AO-AUSS+ CRStransk POW.

Ext + Ao-AusS CRTrans Vx 3 y (y = {x}) + Sum + Inf, EXt

Before proving the axiom schema of replacement we need a lemma in which the iterated application of CRTranscan be replaced by a single one: LEMMA1.1 (LCvy). Ext

+ Ao-AusS+ CRTrans 3 u [Trans ( u ) A Vxo. 'x,

for any finite sequence of formulas among vo,..., v,.

ql,. . . , cpm of

rn

E u A (pi * cpi")] i=l

LfzF with free variables

PROOF(cf. Levy [1960], Theorem 2). A proof can be found in FELGNER [1971a], pp. 18f and KRIVINE[1971]. It should be noted that having derived the axiom of pairing (Corollary 1.l), one can easily get Lemma 1.1 with the additional clause a E u. THEOREM1.1 (LCvy).

+

Ext + Ao-AusS CRTrans ReplS.

k

PROOF(outline). Since we refer later to the proof of this theorem, we

REFLECTION PRINCIPLES AND INDESCRIBABILITY

283

indicate the main steps of the proof which uses an argument taken from the proof of Theorem 3 of LEVY [1960]: Let a,, . . ., a,, a, b be all the free variables occurring in cp(a,b) and let + ( d ) be the formula we wish to prove: $(d):=Vx,Y,z

(cP(x,Y)A q(&z)+y = Z ) + 3 u V v (v E u - 3 x E dcp(x,v).).

Put

1

qJ dX,Y = q (X,Y

1,

( o ~ ( x= ) $(x),

) = 3 w cp (x, w 1, q ~= 4 V x l * * *xnx +(x). cpI(X,Y

Applying Lemma 1.1 to these four formulas we obtain the existence of a transitive set c such that (i) (ii) (iii) (iv)

Vxl.*.xnx,y E c VXl

* *

'Xn,X

(P(X,.Y)-CP"(X,Y))

Ec

(3wcp(x,w) t-* (3 w cp(x,w))")

VX1***Xn,XE c

V X ~. ., . X,,X +(x)

(+(x)t-* +'(x))

-.

c-* ( V X ~ , .

9

XnJ

+(x))~*

The idea of the proof is as follows: Because of (iv), we need only show that the axiom of replacement (for cp as above) holds when relativized to c . Hence we assume that d and the parameters occurring in cp are elements of c. Because of (iii), we need only show $ ( d ) (instead of + ' ( d ) ) . So we may assume Vx,y,z (p(x,y) A cp(x,z)+ y = z ) , i.e. cp defines a function in the obvious sense. Since c is transitive, d c . (i) implies that cp is absolute with respect to c, and together with (ii) we see that c is closed under the function defined by cp. So we obtain: Vy ( 3 X E d cp(X,y) f* y E C

-

A 3X

E d cp (X,y)).

Hence by Ao-AusS there is a set d' such that V Y (Y E d '

3 x E d cp (X,Y 11,

and this establishes our claim $ ( d ) .

COROLLARY 1.1. Ext + Ao-AusS + CRTrans Pair.

PROOF. By Proposition 1.3(a) there is a set containing 0 and (0) as elements. By A,-AusS, {0,{0}} is a set. Now apply the axiom of replacement to the formula cp(c,d):=(c = 0 A d = u ) v ( c = { 0 }

d=b).

The range of the function defined by this formula on the set {0,{0}} is just {a,b}.

284

KLAUS GLOEDE

COROLLARY 1.2. Ext + A0-AusS + CR, that $(a)+Trans ( a ) .

PR$ for any formula 1(1 such

We have not yet made any use of the axiom of foundation. As in BERNAYS[1961], p. 143 we can easily derive the axiom schema of foundation Funds

cp(a)+3x (cp(x)

VY E x

A

7

cp(Y))

from the axiom of foundation, Fund, by using PRTrans. This is accomplished by a modification of Bernays' proof (note that we are not yet allowed to use class variables): PROPOSITION 1.4. Ext + A,-AusS

+ Fund + PRTrans

Funds.

PROOF. Let i,b denote the negation of the formula we wish to prove, i.e. cp(a)A VX [cp(X)+3Y (cp(Y) A Y E XI19

and let a, a l ,..., a, be a11 the free variables occurring in 1(1. Applying PRTrans, we obtain (i)

i,b(a)+3u [Trans ( u )A a, a l,..., a, E u

A

$"(a)].

By the recursive definition of relativization, we have: $ ' ( u ) t * c p b ( a ) ~Vx E b [cpb(x)+3y E b ( c p ' ( y ) ~y Ex)].

Using A,-AusS, there is a set c such that VX

Then

a Eb (ii)

3u (a E u

A

A

(X

EC

Eb

f*X

~ , ! ~ ' ( a ) +Eac

A

cpb(X)).

A

VX E c 3~ E c y E X ,

$ ( a ) )+3 u [ a E u

A

VX E u 3 y E u y E XI.

But the conclusion of (ii) contradicts the axiom of foundation, hence by contraposition and using (ii), we obtain $.

-

1.1.5. We summarize these results as follows, considering the following theories:

T:=EXt+ AO-AUSS+ PRTrans, T:=Ext+ AO-AUSS+ PRstrans, T;=EXt+AO-AusS+ CRTrans, Tb=EXt+ Ao-AUSS+ CRstrans, T,=TI+Fund

for i

=

1,...,4.

REFLECTION PRINCIPLES AND INDESCRIBABILITY

285

Then we have the following results:

T: Pair +Sum + Inf, T;

TI + RepiS,

.

T i F Ti + Pow, T i F T: + Pow + ReplS,

in particular, T4F ZF. (We shall see later that ZF T4,too.) The relationship between these theories may be illustrated by the following diagram (Ti +Ti means: Ti is an extension of Ti):

It can be shown that all these extensions are proper (assuming consistency, of course): LEVY-VAUGHT[1961] proved that T4(= ZF) is “essentially reflexive” over T2, in particular T4 is properly stronger than T,. Moreover, it can be proved (in ZFC or ZF + “The countable union of countable sets is countable”) that H ( o , ) ,the set of hereditarily-countable sets, is a model of T, (cf. GLOEDE[1970], p. 31), but obviously it does not satisfy the axiom of power set. From these results it is immediate that all the extensions depicted in the above diagram are proper (and neither T, is an extension of T3 nor conversely). In particular, the full axiom schema of replacement is not derivable in T, (assuming consistency). On the other hand, in TIwith PRTrans restricted to 2-formulas one obtains the axiom of replacement for 2-functions.’ Similarly, in Tz (possibly with a restricted PRs,,,.,) one can prove the 21(9)-replacement schema of KUNEN[ 19721, and hence Tz is quite a strong set theory (KUNEN [1972], pp. 589ff and LEVY-VAUGHT[ 19611, 02) provided the A,-Aussonderungsaxiom of T2is being replaced by a stronger schema (possibly the full schema of subsets). This suggests that the systems TI and T,, with reflection restricted to suitable classes of formulas, may be more reasonable theories than TI and Tz .

Reflection principles in Ackermann’s set theory have been investigated [1961], and REINHARDT by LEVY [1965] (Appendix C), L~vY-VAUGHT [1967], [1970]. 1.2. Introducing class terms The language .2zF of set theory has been introduced as the usual first-order language with two binary-relation symbols denoting equality

‘See, e.g. BARWISE [1969], Lemma 2.2. The Kripke-Platek theory KP of admissible sets is the theory obtained from T, by restricting the reflection schema to Sformulas and adding the axiom schema of foundation. The above mentioned result, however, does not require the latter schema.

286

KLAUS GLOEDE

and membership relation respectively. This is a particularly simple language as far as the metamathematics of set theory is concerned. On the other hand, for the development of set theory within this language, it is often more convenient to extend the basic language by introducing class terms (e.g. in the proof of Theorem 1 . 1 we already spoke of the “function” defined by a particular formula). This can be done in such a way that every formula of the extended language, possibly containing class terms, is equivalent to a formula of the basic language. As usual we proceed as follows: The basic language ZezF is extended by adding class terms of the form {x I...} and adding the following formation rules for formulas: If cp(a,...) is a formula of the extended language then so is the formula a E { x I qk...)}. Moreover, we add to the usual axioms and rules of the predicate calculus with equality the following schema: CH

a E{XIc

pk.

..) ) t * q ( a , . . . )

(Church)

by means of which class terms can be eliminated in an obvious way.’ Following QUINE[1963] (cf. also JENSEN [1967]), we may even extend the logical frame further by introducing syntactical variables for class terms. In order to distinguish notationally from the class variables A, B, ... to be introduced in the next chapter, we use A, B, . .. to denote class terms in the above sense. Note that a formula containing such a syntactical variable A denotes a schema of formulas of the extended language, in contradistinction to a formula containing a (formal) class variable A. With respect to these class terms, it is convenient to define equality and membership relation between class terms and (set) terms by the following schema of definitions:

tl=tz:f,VX(XEt,t*XEt2),

t l E t z : f ; , 3 X ( X = t l AX E t 2 )

if t l and t 2 are class terms or set variables, but not both set variables. It is now possible to rewrite the axiom schema of replacement in the following form (assuming the axiom of pairing): Ft ( F ) A 3 x ( x = dom ( F ) )- + 3 y ( y

= rng

(F))

where we have made use of the following definitions: Ft ( F ) :f;,Vz ( z E F + 3 x , y ( z = ( x , y ) ) )A Vx,y,z ( ( x , y )E F A ( x , z )E F + y

=z

) “ F is a function”,

’ As long as we have not introduced class variables, we use the word “class term” for class abstracts of the form {x I cp(x,. . .)} whereas BERNAYS[1961] uses the word “class term” to denote either a class variable or a class term of the form {x I cp(x,. . .)} (in a somewhat extended sense insofar as cp may contain class variables).

REFLECTION PRINCIPLES AND INDESCRIBABILITY

287

dom ( F ) := {x 13y ( ( x , y ) E F ) } "domain of F", rng ( F ) := {y I 3 x ( ( x , y ) E F ) } "range of F". For the following discussion let us assume the following convention: By

cp(ao,.. . , a,, A,,.. .,A,,) we denote the formula of the extended language

obtained from the formula cp(a,,..., a,, bo,..., b.) of the basic language 2ZzFby substituting Ai for bi for i = 0,. .. , n. We now extend the notion of relativization to formulas of the extended language by requiring that for any formula q(a, ,..., a,, b, ,...,b,,) of the basic language and any class terms Ao,. . .,A, Rel(a,cp(ao,..., amrAo,-..,An))

or

($(a,,..., am,Ao,*..,An)")

to be the formula Re1 (a,$) where $ is a formula of $PzF obtained from cp(ao,.. . , a,, Ao,. . . ,A,,) by eliminating the class terms occurring in this formula in some canonical way. Alternatively, we may proceed as follows: We define by recursion the relativization of formulas and class terms of the extended language as follows:

-

Re1 (a,cp)= cp if cp is atomic, Re1 ( a , cp) = Re1 (a,cp),similarly for the propositional connectives A , v ,+, and c*, Re1 ( a ,Vx cp) = Vx E a Re1 (a,cp), Re1 ( a , 3x cp) = 3 x E a Re1 (a,cp), Re1 (a,b E {x I cp}) = b E {x I Re1 (a,q)}, Re1 (a,{x 9)) = {x I cp)" = {x I Re1 (a,cp)).

I

Thus Re1 (a,cp(a,,..., a, A,,. .., A,,)) may also be defined by the formula cpa(ao,.. . , a,, A o a ,.. .,A:) which is obtained from q ( a o , .. .,a,, A,, . . . ,A,,) by relativizing the quantifiers occurring in this formula to a and substituting Ai" for Ai. Now suppose again that p(ao,..., a,,Ao ,..., A,) is a formula of the extended language. Then the partial reflection principle PR, applied to such a formula and particular class terms (or, more exactly, to the equivalent formula of the basic language) yields (+>

p(ao ,..., a,,,,Ao,..., A,,) + 3 u [ $ ( u ) A u,..., ~ am E U A

cpU(ao,.. . , a,,Ao",...,A,")].

(We assume that the free variables of cp(ao,.. ., a,, Ao,. ..,A,) are among a,, ..., a,-note that the class terms may contain free variables.) If $(a)+Trans ( a ) ,we may replace A: by A: n u in (+) (here we need

288

KLAUS GLOEDE

the assumption on the free variables).' However, in general A n a need not be equal to A n a (even if a is transitive); in fact, the principle 3 u (I,!J(U)AA" n u =A n u)

is a principle of complete reflection. Thus, in order to obtain the axiom of replacement, we either have to use a schema of complete reflection (cf. the proof of Theorem 1.1: we have made essential use of the fact that the formula defining a function is absolute with respect to some appropriate set c), or as in BERNAYS[1961], use a schema of partial reflection for formulas containing class variables which remain unchanged under the process of relativization. (It follows from Theorem 1.2 below that the latter principle implies the schema of complete reflection C RTrans.)However, even without introducing free class variables, within the logical frame of ZF set theory, modified by the use of syntactical variables for class terms, we can treat these variables like the free class variables in Bernays' schema and consider the following principle: PRII,O

p(ao,..., a,,Ao ,..., A , ) + 3 u [Trans(u) A

p"(ao,..., %,Ao n u ,..., A, n u ) ]

(where p(ao,.. ., a,, Ao,.. . , A,) is a formula of the extended language in the sense explained above). Using an argument from Remark 1.1 it can easily be seen that we may add the clause a o E u A . . . A a, E u as a conjunctive member within the scope of 3 u in the principle above, and in this form A in u may be replaced by Ai. LEMMA1.2.

Ext

+ Ao-AusS+ PRII,OFPair.

PROOF. Apply PRII," to the formula 3 x (x

= ao) A

3 x (x

= a').

One can now use the method of BERNAYS[1961], pp. 133ff. to show that PRII," (together with the axioms mentioned in Lemma 1.10) implies the axiom schema of replacement (using a class term F instead of a free class variable F as in Bernays' paper). Alternatively, we can prove the following THEOREM1.2. Ext +Ao-AusS

+ PRII,OF CRTrans.

PROOF. Let p(ao,..., a,) to be a formula of ZZF with free variables as 'Thus, we could also define the relativization of a class term Re1 (a,{x I cp}) to be E a A Re1 (a,cp)},provided a is transitive and a,, . ..,a, E a where ao,...,a, are the free variables of cp.

{x I x

REFLECTION PRINCIPLES A N D INDESCRIBABILITY

289

indicated and define A : = { y ) 3 X o . * . X n ( y = ( X o ,..., X n ) A ~p(Xo,..., X"))}, I,!J(A,u):= IX ( a = X ) A V X , 32 ~ ( 2 = (x,y)) A V & . . . x , ( 3 y (y =(Xo, ..., X n ) h Y E A ) (p(x0,. ..,Xn)).

-

By Lemma 1.2, + ( A , a ) is provable in the theory considered, hence by PRII," there is a transitive set b such that

aEb

V x o - . . x nE b (3y E b (y =(xO,..., xn)

A

Vx,y E b ( x , y ) E b

A

y € A n b)-pb(Xo ,..., L)),

therefore,

a f b

A

A

V x O * * * x , E b ( q ( ~,..., o x,)-~~(xO

,..., X n ) ) .

Let T, denote the theory Ext + Ao-AusS + Fund + Pow + PRII,". Then we have the following

COROLLARY1.3. T,

1 T4 and

T,

1 ZF

We shall see later that ZF T, and, moreover, PRII,O can be further strengthened to yield a principle of complete reflection which is related to PRII," like CRTransto PRTrans.

1.3. Derivation of reflection principles in ZF set theory

In this section we shall make further use of class terms in deriving principles of reflection in ZF set theory. For this purpose it is convenient to use the concept of normal functions: Ordinals are defined as usual in such a way that they are well'ordered by the €-relation: ord ( a ) :-Trans

( a ) A Vx,y E a (x E Y v x A

V.2 ( 2

c U +

=Y v Y E X )

2 =oV3X E Z

Vy

E X (YeZ))

a is an ordinal

On := {x I ord (x)} is the class of ordinals, a + 1 := a u {a},lim(a) :-ord(a) A a # O A Vx E a 3 y E a (x ~ y ) . Assuming the axiom of foundation, the last conjunctive member in the definition of an ordinal is redundant, and in this case ord (Q)is defined by a 8,-formula. We use lowercase greek letters to denote ordinals. A normal function is one defined on the class of all ordinals, with range included in the class of ordinals and which is strictly increasing and

290

KLAUS GLOEDE

continuous: Ft ( F ) A dom ( F ) = On A rng ( F ) g On Nft ( F ) :o A Vx,y E On (x E y + F ( x ) E F ( y ) ) A V X( L i m ( x ) + F ( x ) = U { F ( y ) l y E x } ) . For the remaining part of this section we assume the usual axioms of ZF. It is easy to see that the composition of normal functions is again a normal function and that every normal function F has arbitrary large critical points (i.e. ordinals a such that a = F(a)). Using transfinite induction one can prove that there is a sequence of sets (V, I x E On) satisfying the recursive conditions v,,=@,

v,+,=~(V,),

Lim(a)+V,=~{v, I x ~ a } ,

and V = U{V,Ix €On} by the axiom of foundation. (V, is $(a) in BERNAYS[1961], p. 146.) METATHEOREM 1.1 (Scott-Scarpellini). For every formula cp (vo,. . . ,v,) of gZF with free variables as indicated there is a normal function F (depending on cp) such that F ( a ) = a + V x o . . . x , E V, (cp(xo,..., xn)f*Rel(V,,cp(xo,..., x,))). [1969], p. 23 where the PROOF. A proof can be found e.g. in MOSTOWSKI proof is given in Quine-Morse set theory. The above version, however, which uses the concept of relativization rather than a formalized version of satisfaction for classes (which is not definable in ZF) can be proved in ZF along the lines of Mostowski’s proof. (See also KRIVINE[1971], Ch. IV.) Since the V,’s are supertransitive, we obtain:

COROLLARY 1.4. ZF 1 CRStrans,and hence ZF 1 T4. Metatheorem 1.1 has a further corollary for class terms: COROLLR1.5. For every class term A with free variables among vo,. . ., v, there is a normal function F such that F ( a ) = a +Vxo**.x,E V, (A n V,

= Rel(V,,A) n

V,).

Combining Metatheorem 1.1 and Corollary 1.4, and using the fact that the composition of finitely many normal functions F , , ... ,Fk is again a normal function whose critical points are critical points of each Fi we obtain: COROLLARY1.6. For every formula q ( a o,..., a,,,, bo,..., b , ) of ~ Z and every class terms Ao, ...,A, such that the free variables of

F

REFLECTION PRINCIPLES AND INDESCRIBABILITY

29 1

q ( a o,..., a,,Ao,. . ., A , ) are among ao,..., a,,, there is a normal function F such that

F ( ( Y )= (Y + V X ~ * * E *X V a~[ ~ ( x o. ., ,. x,, Ao,. .. , An) n V,, . . .,A, n Va)]. COROLLARY1.7. ZF

PRII;,

and hence ZF

q V a ( X ~.,.,. X m A o

Ts.

As a further consequence of Corollary 1.6, the principle PRII," of partial reflection can be strengthened in ZF to the following principle of complete reflection: CRK,"

3 u [Trans(u) A V x o . . ~ x ,Eu(rp(xo,. ,, f* rp"(xo,..., x m , A on u ,..., A, n u))]

where rp and A o . .. .,A,, are as in Corollary .6. (In addition, Trans ( u ) may be replaced by Strans ( u ) . ) This possibility of strengthening a principle of partial reflection to the corresponding principle of complete reflection is a peculiar feature of PRII," (possibly with Strans ( u ) in place of Trans ( u ) ) and the schema PRIIo' to be introduced later, since in general the principle of complete reflection C R(2) is stronger than the corresponding principle of partial reflection PR(2) for the same set of formulas 2. For example cf. the end of §1.1, 42.1, and remark (2), p. 305. 2 . From class terms to class variables

2.1. Bernays' set theory B In the preceding chapter we introduced a version of ZF set theory which allows for the use of class terms and even has syntactical variables A , B, ... for arbitrary class terms. Replacing these syntactical variables by formal class variables A, B,. . . we obtain Bernays' set theory B (as in his 1958 monograph). The language .%of B is an extension of the basic language LfZFof ZF which has in addition free-class variables A, B, ..., but no bound-class variables. The formulas of this language will be denoted by capital greek letters @, Y,.... For simplicity, we assume that the language of B has atomic formulas only of the form u E v, u = v, and u E A. We use the same symbol of equality "=" in formulas of the form t = s where t and s are set or class variables; in case at least one of t, s is a class variable, t = s is defined according to the principle of extensionality (cf. 91.2). Thus, we write a = A for Rep(A,a) (BERNAYS [1958]) and a = A (BERNAYS [1961]). Similarly we define A E t : - 3 x ( x = A A x E t ) if t is a

292

KLAUS GLOEDE

class or a set variable (cf. 4 1.2). We further assume that formulas of B do not contain any class terms (apart from class variables); formulas of the form a E {x I @(x,...)} are regarded as “abbreviations” of @(a,.. .). (Alternatively we may assume that class terms of the above kind are eliminated from formulas of B by means of the (extended) Church schema.) We assume a suitable system of logical axioms and rules including the schema of equality u = b. + .4,(u,. . .) +@ ( b , ...). (In particular, we have a = b.+.a E A + b E A . ) Axioms for B are Al-A8 of BERNAYS[1958]; we may also use the following axioms for B: Ext, Pair, Sum, Pow, Inf, and Fund (as in the case of ZF),

and finally Repl’

Ft (F)A 3 x ( x = dom ( F ) ) + 3 y ( y

= rng

(F)),

which is obtained from the axiom schema of replacement of ZF (as defined in 41.2) by replacing the syntactical variable F by a free-class variable F. We might call a formula of 2, a A,-formula iff it is equivalent to a formula in which all quantifiers are restricted to set variables (as in the sense of § 1.1) and consider the following schema:

8 o - A sS’ ~

3 X v y ( y EX e y E a

A

@ ( y , ...))

where @ is any Ao-formulaof ZB.However, since a E A is a A,-formula, this schema immediately gives the full Aussonderungsaxiom (axiom of subsets) of B:

Au s‘

3 x Vy ( y E x + + y E a

A

y€A)

We have excluded class terms from our formal language in order to simplify the notion of relativization for formulas of B: If 4, is such a formula then @a (or Rel(a,@)) is the formula obtained from @ by restricting any quantifiers occurring in @ (note that there are only quantifiers on set variables) to a (as in the case of a formula of 5fzF). Again, if @ contains any defined symbol or class terms then Re1 (a,@)is defined to be Re1 (a,W) where is obtained from @, by eliminating the defined symbols and the class terms occurring in CD. Let us now consider the schema of partial reflection for formulas of the language of B: @(a,,.. . , a,, Ao,...,A,) + 3 u [Trans ( u ) A CDU(ao,. .., a,, A, n u,... , A, n u ) ]

P RHO’

where

4,

is any formula of ZBwith free variables as indicated.

REFLECTION PRINCIPLES AND INDESCRIBABILITY

293

REMARK. As in the case of PRII,", one may add in PRIIo' the clause a . E u A . .* A a , E u as a conjunctive member within the scope of 3u and replace Ai n u by Ai. THEOREM2.1.

Ext

+ Aus' + PRII,'t-Pair + Sum + Inf + Repl'.

The axiom of pairing is proved as in Lemma 1.2. The proof of the remaining axioms is given in Bernays [1961], pp. 127, 128, and 133ff. REMARK. Thiele's version of the axiom of replacement (Formula (191, p. 133 of BERNAYS [1961]) is in fact equivalent to (18) in B using the von Neumann rank of a set in a manner due to SCOTT[19551. COROLLARY 2.1.

Ext + Aus' + Pow + Fund + PRIIo' 1 B.

Conversely, one can prove by the method of 0 1.3 (Metatheorem 1.1): METATHEOREM 2.1. For every formula @(ao,..., a,, A. ,..., A,) o f LtB with free variables as indicated, there is a normal function F (more precisely, a class term F defined by a formula of LfB which depends on @ such that B Nft ( F ) ) such that one can prove in B:

+

F(cx)=cx+~/x~ E *V*, *(@(x, x , ,..., X ~ , A ~ , . . . , A , ) @ @"a(x0,...,x,, A. n V,,. .. , A, n V , ) ) .

Thus again PRIIo' can be strengthened in B to give a schema of complete reflection CRII,' as in the case of PRII2; similarly, if in PRIIo' and CRIIo', we replace Trans ( u ) by Strans ( u ) , in this case the stronger principles imply the axiom of power set (cf. Proposition 1.2). Note that the proof of Metatheorem 2.1 is similar to the proof of Metatheorem 1.1 rather than Corollary 1.6, since a € A is now an atomic formula (whereas a € A need not be equivalent to an atomic formula in ZF). In fact, Corollary 1.6 can be proved along the lines of the proof of Metatheorem 1.1 by treating a E A as an atomic formula. Thus we have the following results (as usual we write TI = T, to mean that TI and T, have the same theorems):

+ +

Z F = Ext + Ao-AusS Pow + Fund + PRII,", B = Ext Ao-AusS' Pow Fund + PRIIol,

+

+

and we can delete the axioms of power set on the right-hand sides if the respective schemata of partial reflection assert the existence of a "reflecting" set a such that Strans ( a ) rather than Trans ( a ) . 2.2. Montague- Vaught 's theorem Before

presenting

various

results

from

MONTAGUE-VAUGHT

[ 19591, we recall some definitions (throughout this section we assume the

294

KLAUS GLOEDE

axioms of ZF): w is the least infinite ordinal (and the set of natural numbers), Osq cf) :- Ft cf) A dom ( f ) E On A rng ( f ) C On “ f is a sequence of ordinals”,

AOsq (f) :* Osq ( f 1A VX,Y( x E Y

A

Y E dom ( f 1-+f ( x )E f ( y ))

“f is an ascending sequence of ordinals”. If f is a function such that a dom ( f ) , then sup+f ( x ):= u { f ( x )+ 1 I x E a}.

sup f ( x ):= u c f ( x ) I x E a } ,

x E”

X E O

Nf t (f,a):t,AOsq ( f ) A dom c f ) = a

A

rng c f ) C a

A

V x E a (lim ( x)

a

= supt s(x)),

--j

f ( x )= SUP f (Y 1) YE*

“f is a normal function on a”, conf ( a $ ) :-3s

(AOsq (s)

A

dom (s)

=p A

cf ( Q ) := p x conf ( a , x )

xe@

( p x q ( x ) denotes the least ordinal x such that cp ( x ) if there is such an x, 0 otherwise), reg(a):t,cf(a)=a “ a is regular”,

sing ( a ):++

reg ( a )

“a is singular”,

in ( a ) :c*a > w

A

Vf (Ft cf) A dom (f) E V,

A

rng cf) C V, +rng (f) E V,)

“ a is (strongly) inaccessible”. Any infinite regular ordinal is a limit number, an inaccessible ordinal is regular. Assuming the axiom of choice AC, inaccessibles can also be characterized as follows (MONTAGUE-VAUGHT[ 19591, Lemma 6.4): (ZFC)

in ( a )c,a > w

A

reg ( a ) A V x E a

(I P ( x ) 1 E a ) ,

where la1 denotes the cardinal number of a (assuming AC). The formal notion of satisfaction for first-order formulas in a structure which is a set can be extended for second-order formulas of set theory (which are obtained from the language of B by admitting even bound-

REFLECTION PRINCIPLES AND INDESCRIBABILITY

295

class variables VXi and 3Xi) in several ways. Here we decide to reduce the notion of satisfaction for the latter class of formulas in a structure of the form (a, E ) to the satisfaction of first-order formulas in the structure (P(u),E)as follows: As in 91.1.2 one can assign to each secondorder set-theoretical formula @ a term r@l (the Godel number of @) and define in ZF a set Fml’ which intuitively represents the set of all such Godel numbers such that ZF r@l E Fml’ for each second-order formula @. Moreover, one can define in ZF a function * which assigns in a suitable way to each e E Fm1’ a set e* E FmlZF. Instead of giving a formal definition of * (this would presuppose an explicit definition of FmlzFand Fml’ as well as several syntactical concepts) we describe it informally. If @(vo,. .., urn,A o , .. ., A,,)is a second-order formula of set theory, @* is the formula of YZFobtained as follows: replace the second-order variables Ao,...,A, by the first-order variables urn+’,..., urn+,+2(renaming bound variables in @, if there are any among urntI,..., urn+,,+2),replace any first-order quantifier Vx (3x) occurring in @ by Vx E urn+1(3x E urn+1 resp.) and any second-order quantifier V X (3X) by a first-order quantifier Vx (3x resp.) for some suitably chosen set variable x. We then define (a,€) I= @‘[a$]

for a formula @ as above, and a sequence a of m sequence b of n + 1 elements of ??(a) by ( P ( a ) Z )I=

where c is the sequence of n

+ 1 elements of a, and a

@*[Cl

+ m + 3 elements

a(O>,...,a(m), a, Wh..., b(n)

This means that we interpret class variables in a structure (a,€) as ranging over the set of subsets of a. We denote by (a,€) I=’ e[a;bI, or (though notationally not quite correct),

if n and m are suitably chosen, the satisfaction predicate for secondorder formulas of set theory formalized within ZF set theory in a manner described above informally. (For more details the reader may consult [ 19691 or BOWEN[1972]. In Mostowski’s book, however, MOSTOWSKI this notion of satisfaction is defined for structures ( A , € )(where A may be a proper class) in Quine-Morse set theory; the same definition, restricted to structures which are sets, can be defined in ZF set theory).

296

KLAUS GLOEDE

As usual, we write (a,E)+=2r@Tf o r ( a , E ) p ‘ V x , - - - x ,V X , . - - X ,

@I,

or, equivalently, VX~**E *X a ,V y o * * . y L n a ((a,E)t=zr@-[xo ,..., x m ; y o ,..., y n l )

if @ is a second-order formula with free first-order variables among vo,..., v, and free second-order (class) variables among Ao,.. . ,A,. Also (a,€) kZ E

and

(a,€)

‘@,

+

Q2’

for a schema or a set of second-order formulas E and formulas @,, Q2 is assumed to be defined as usual. Finally, ( a , € )< (b,E) is a formal version (definable in ZF) of the predicate “(a,€) is an elementary subsystem (with respect to first-order formulas, i.e. with respect to formulas of ZZF) of (b,€)” in the sense of TARSKI-VAUGHT [1957]. In order to simplify notation, we often identify a formula with its Godel number (similarly in the case of a set of formulas) and write e.g. ( a , € ) Ext or ( a , € ) B, since in these cases the use of the symbols or indicates that we are dealing with the formal counterparts of the respective (metamathematical) satisfaction relations. Using these definitions it can be shown (cf. MONTAGUE-VAUGHT [1959], p. 234):

v

LEMMA2.1. If a # 0 and a # 0 , then

6) (ii) (iii) (iv) (v) ( 4

Trans ( a ) + ( a , E ) Ext + Fund, l i m ( a ) + ( V a , € ) k Pair+Sum+Pow, w Ea+(Vu,E)~lnf,

( V U , GFB f,in ( a 1, V,,E) B + ( V,,E) in (a)+reg (a).

v

+ ZF,

The converse of (v) is not true. This is a consequence of the following: THEOREM2.2 (Montague-Vaught). ( V,,E)

vB

+

36 < a (V.,E)< ( Vu,E).

PROOF. We indicate a proof of the informal version of this theorem using the method of MOSTOWSKI [1969], pp. 25f. Let (cp,ln < w ) be an such that the free variables of (P, are enumeration of the formulas of TZF among vo,..., v,. Since V, is a model of ZF, by Scott-Scarpellini’s Metatheorem 1.1 there exists for each n a function f n (definable in V,)

REFLECTION PRINCIPLES AND INDESCRIBABILITY

such that Nft (f.,a) and

V.$< a Lf,,(()

297

-

= .$ +

V X ~ * - -EXV,E (Re1 (Va,cpn(Xo,..., x , ) ) Re1 (Vt,Pn(xO,...,xn)))l.

Define a function f on a by recursion on P < a such that f ( 0 )= 1, f ( P + l ) = m a x c f ( P ) , supf.(P))+l, n ( 0

Lim ( A )

A

h < a +f(h)

= sup f(.$). ,
(Note that f and the sequence (f. In < w ) are definable in ZF but not in V,.) Obviously, f is strictly increasing and continuous. Any critical point of f is a critical point of each f,,, hence if f(P) = p then for all n < o:

V X O..,. ,X n E V p (Re1 (V,,cp, ( X O , ... ,xn1) t-,Re1 ( Vp,cp,,( X O , ...,X . ))I. Finally, it remains to show that f has a critical point. In fact, if reg ( a )A a > w (in particular, if V , is a model of B by Lemma 2.1 (iv)), then we have Nftcf,a) and even Nft(g,a) where g is the function enumerating the critical points of f in increasing order. A subset a a is called closed unbounded in a iff it is the range of a normal function on a :

c

clo unb ( a , a ) :e 3f (Nft cf,a) A a = rng cf)). Incidentally, we have thus proved the following stronger result:

COROLLARY2.2. reg ( a ) ~ ( V , , € ) k Z F + 3 x a(clounb(x,a) A x c (5 < I ( V,,E)< ( vU*aH, in particular (Montague-Vaught): i n ( a ) + 3 . $ < a ( ( V E , E ) < ( V , , E ) ~ c f ( . $ )w=) . COROLLARY 2.3. (V,,E)

k26 +35 < a ( V . , E )

ZF.

The same result can be expressed as follows:

COROLLARY 2.4. (V,,E)

PRIlo’+35 < a( V,,E)

PRn2.

We have seen in 02.1 (Metatheorem 2.1) that the principle PRII,’ can be strengthened in the theory B, in fact, if (V,,E) is a model of B then for each formula @(aO ,..., a,,,, Ao,..., A,) of 5!?Bwith free variables as indicated and any bo,..., b. C V,, the set {(
-

~Vxo-~~xmEV,(Rel(V,,@(xo ,..., xm,bo,..., 6 , )

Re1 ( V , , @ ( X .~.,,.x m , bo,. . ., bn1)))

298

KLAUS GLOEDE

contains a set which is closed unbounded in a. Combining this result with Corollary 2.2 and the fact that for any regular a > w the closedunbounded subsets of a generate a filter in the power set of a, we obtain the following result:

-

If ( V,,E) is a model of B then ( V,,E) satisfies the following principles: (+)

36 [ ( V , , E ) F Z F AV X ~ ’ * * XE, V~(@(XO, ...,x,,Ao,..., A,) Re1 ( V6,@(xo,. . . , x,, Ao,...,A,,)))I,

in particular, (++)

@(ao ,..., a,,Ao ,...,A , ) + 3 u [Strans(u)A ( u , E ) k Z F A A

Re1 (u,@(ao,. . . , a,, Ao,.. . , A,))]

(where in both cases, @ is any formula of 2ZB with free variables as indicated). This result should be compared with schema (llg) of BERNAYS [1961], p. 141 and LCvy’s principle ((I) of BERNAYS [1961], p. 122, cf. LEVY[1960]). These latter principles have in place of the formula Strans ( u ) A ( u , E )F ZF the formula Strans ( u ) A Mod ( u ) (Bernays), and ScmzF( u ) (Levy), respectively. In ZF, S t r a n s ( a ) ~M o d ( a ) t * S t r a n s ( a ) ~( a , E ) p B c* Strans ( a )A ScmZF( a ) , and Montague-Vaught’s theorem shows that ScmzF( a ) and Trans ( a )A Mod ( a ) both are stronger than Trans ( a )A ( a , € ) ZF (even if we add “strans (a)” in both cases), and in fact the latter principles are stronger than (++) and even (+) (assuming consistency). On the other hand, (+ +) is a schema which is derivable in Quine-Morse set theory (cf. p. 306) and can be used as a motivation for LCvy’s principle. Finally, as it is known that the theories 6 and ZF are equiconsistent, (++) cannot be proved in B (again assuming that B is consistent). 3. Reflection principles for second-order languages

3.1. Second-order set theory The language 2Z* of second-order set theory is obtained from the first-order language 2’zF of ZF set theory by introducing second-order (class) variables Xi(i < w ) (as in the case of set variables, we often use capital letters from the beginning of the alphabet for free variables and letters from the end for bound variables). Again, as in the case of Bernays’ set theory 6, we assume that we have only atomic formulas of

REFLECTION PRINCIPLES AND INDESCRIBABILITY

299

the form u = v, ; E and u E X and that our formal language does not contain class terms (apart from class variables). t = s :-Vx (x E t - x E s) (if t and s are variables, but not both set variables) and X E t :-3x (x = X A x E t ) (for a set or class variable t ) is defined as in $4. In a suitably extended language, {x I Q,(x)}denotes the class of all sets x such that @(x). The axioms of von Neumann-Bernays' set theory VNB consist of the axioms of Bernays' set theory B: Ext, Pair, Sum, Pow, Inf, Fund and Repl', and the following schema of (predicative) class formation : II,'-Comp

3 X V y (y E X - @ ( y , a o , . . . , am,Ao, ..., A,,)),

where Q, is any formula of 9 'containing no bound-class variables (i.e. ' of VNB will also be denoted by any formula of Lf6). The language 2 =%'VN~.

If we replace in VNB the IIo'-comprehension schema by the (impredicative) schema of comprehension

3x v y ( y E x WY,. . .I>,

IIo2-Comp

where

Q,

f,

is any second-order formula, we obtain Quine-Morse set theory

QM.

LEMMA3.1 (ZF).

(a,€)

+*IT,'-Comp

for any set a # 0.

PROOF. This fact is due to the particular definition of satisfaction+' which interprets classes in (a,€) as subsets of a, and the fact that ( a , € )k' e [x,. . .] is a formula of ZF set theory. COROLLARY 3.1 (ZF).

+' B

( Va,E)

-

( V A k*VNB * ( V a , E ) QM in (a). f ,

From the results of the previous chapter, we obtain:

+ +

VNB = Ext + AUS' + Pow + Fund + IIo'-Comp PRII,', QM = Ext AUS' + Pow Fund II2-Comp PRIIo'. LCvy's classification of the formulas of ZF set theory (LEVY[1965]) can be extended to formulas of VNB and QM set theory as follows: A II,'-formula @ is a formula of ZVNB which does not contain any boundclass variable (i.e. a formula of ZB), Xo' = no'.A II!,+l(Z!,+I)-formulaQ, is a formula of LZvNeof the form VXW (or 3XW resp.) for a %'(IT,')-formula W. Formulas of =%'vNaare also called IIoZ-formulas. Let Q, be any formula of LZvN6. Then Q, has a prenex normal form

+

(1)

+

Q I t 1 - * - Q,t,

+

$ ''

300

KLAUS GLOEDE

where each ti is a set or a class variable, Qi is V or 3 and W does not contain any quantifier. Q l t l .=.Q,t, is called the prefix of the formula (1). Clearly, (1) is equivalent to a ll,l-formula for some rn. We can obtain another classification of the second-order formulas by “ignoring” the bounded-set variables even in front of bounded-class variables: The reduced form of (1) is obtained from (1) by deleting any set quantifier in the prefix of (1). A fi,’-formula ($,‘-formula) is a formula in prenex normal form such that the reduced form of it is a II,’-formula (2,’-formula). A A,’-formula is a formula which is equivalent to both a n,’- and a 2,’-formula, similarly €or A,,’. We sometimes use the symbol Q to denote any of the symbols ll, 2, A, fi, 2, 6. We show that under suitable assumptions the ll,,’- and the fin’classifications agree and hence obtain a simple method for classifying a according to its bound variables. For the remaining part formula of ZvNB of this section, if not mentioned otherwise, we assume the axioms of VNB. First, note that any two (and hence any finite number of) adjacent quantifiers of the same kind can be reduced to a single one using ordered pairs; in the case of class quantifiers, one may use a coding of finitely many classes into a single class (cf. ROBINSON[1945]).For example we may define the ordered pair of two classes A, B by ((0)x A ) u ({ l} X B ) , hence we have in VNB:

v x V Y Q,(X,Y , ...) vz W Z , ...), f-*

where W(Z,...) is obtained from Q,(X,Y,...) by replacing any occurrence of X and Y of the form u E X by (0,u) E 2 and u E Y by (1,u) E 2 resp. (where Z is assumed to be a variable which does not occur in a). Now, let Q, again be any formula of ZvNB written in prenex normal form (1)-with alternating quantifiers. Obviously, if Q, is a IT,,’-formula, then it is a II,’-formula. In order to prove the converse, we have to show that any set quantifier occurring in the prefix of (1) can be moved over a class quantifier from left to right without introducing new bound-class variables. We generalize the ordered pair of classes by introducing the following coding for sequences of classes:

DEFINITION.A, := A ” { a }= {xI(a,x)

E A}.

(Though this notation might conflict with the metamathematical use of indices for class variables (e.g. in the notation @(ao,..., a,, A. ,..., A,)) we hope that the reader will always discover the right meaning from this context.)

REFLECTION PRINCIPLES AND INDESCRIBABILITY

30 1

In order to advance a set quantifier over a class quantifier in a suitable way, it seems necessary to assume some kind of axiom of choice. We consider the following forms:

V x E a ( x # 0)+3f [Ft cf) A dom (f) = a A V X E a f ( x )E x ] (set form of the axiom of choice)

AC SAC

3 F [Ft ( F ) A dom ( F ) = v

A

v x ( x # o+F(X) E X ) ] (strong axiom o f choice)

v x 3Y @(x,Y , ...)+3Y v x @(x,Yx,.. .),

Qn'-AC

where @ is any Q,'-formula.

LEMMA 3.2.

(a) VNB + IIol-AC SAC.

(b) In VNB, the II,'-AC is equivalent to each of the following schemata : (9

2;+i-AC,

vx 3~ @(x,Y,...I - 3 V~x @(x,Y,,...), @ a 2L+1-forrnula, (ii) 3 x V Y @(x,Y,.. .) -VY 3 x @(x,Y,,...), @a II!,+l-formula. (iii) PROOF. (a) Let @ ( a , A )be the IIo'-formula a = O V A € a , i.e. -3x (x E a ) v 3 x (x E a A V y ( y E x - y E A ) ) . Applying the IIol-ACto the formula V x 3 Y @(x,Y ) which is derivable in

VNB, we obtain the existence of a class A such that

V x (x#O+A, E x ) . Then F := {x,z Ix # 0 A z = A,} u {(0,0)}is a function as required. In order to prove (b) we have to show that II,'-AC implies Z;+l-AC. Thus, assume the former and let

@(a,A,...) = 3 X * ( a , A , X,...) be a 2!,+1-formula,i.e. 9 a II,,'-formula. Assume

v x 3Y 3X*(x, Y , X ,...). We have to show, 3 Y V x 3 X T ( x , Y,,X,. ..). Contracting the existential quantifiers, we have

v x 13Y 3x *(x, Y,x,...) cf 32 *(x, ZO,Zl,.. .)I

where Z,, Z 1are defined as on p. 300, and from V x 32 *(x,Zo,Z1,...), we obtain by applying II,,'-AC: 32 v x V x , (ZO),, (Zl),,. ..) 3 Y v x 3x *(x, Y,, x,...). 3 Y 3x v x *(x, Y,,x,,...),

302

KLAUS GLOEDE

[1971] shows that in several REMARK. Theorem 3c of MOSCHOVAKIS cases the application of IIo'-AC can be eliminated.

With respect to structures which are sets we have the following

LEMMA 3.3 (ZF + AC). (a,€) k2II,'-AC for each n < w and any set a # 0 which is transitive and closed under pairs. PROOF. Let @(ao,..., ak, a, A. ,..., A,, A ) be any III,'-formula with free variables as indicated and assume ( a , E ) ~ 2 V ~ k + 1 3 Y m + l,..., @ [ aa ko; bo,..., b m l

for any ao,.. ., a k E a, bo,.. ., bm C a. Then v x E a 3 y C a (a,€) kza[&,.. . , ak, X; bo,. . ., b m , y].

Since this is a formula of ZF, by A C there is a function f such that dom (f) = a, rng cf) C P ( a ) and Vx E a (a,€) 'F' @[ao,..., ak, x ; bo,. . . , b m , f(x>I.

Define B := {x,y I x E a a class as required.

A

y Ef(x)}. Then Vx E a B ,

= f(x)

and B C a is

THEOREM 3.1. For any l?L+l-forrnula CP there is a II;+,-forrnula@' with the same free variables such that VNB

+ III,'-AC

@

f-,

a'.

REMARK. a' can be obtained from @ in a simple and uniform manner, e.g. there is a primitive recursive set function (in the sense of JENSEN-KARP [1971]) F such that Fro' = '@I1. In fact, @' can be defined by recursion as follows: @' = @ if @ is a n,'-formula for some n,

Y,. . .)I' = 3 Y v x *'(x, Yx,...), [3x V Y *(x, Y,. ..)I' = V Y 3x *'(x, Yx,...). COROLLARY3.2 (ZF +AC). If @ is a fi,,'-formula, then there is a [VX 3 Y *(x,

II,'-fomufa @ with the same free variables such that for any transitive set a # 0 which i s closed under pairs : (a,€)

+*@

f*

@'.

Finally, we extend the operation of relativizing a second-order formula to a set a by defining Re1 (a,@)(or W ) to be the formula obtained of 5?veN from @ by replacing any quantifier of the form Vx (3x) by Vx E a(3x E a resp.) (as in the case of a first-order formula) and any quantifier of the

303

REFLECTION PRINCIPLES AND INDESCRIBABILITY

form V X ( 3 X )by Vx a (3x C a resp.) for a suitably chosen variable x. Again it is tacitly understood that defined symbols (and possibly class terms other than class variables) have been eliminated from @ before performing the process of relativizing. This definition is in agreement with in fact our definition of satisfaction in a structure ( a , € )by the predicate one can prove in ZF:

+*;

(a,€)~'e[a;b]t,Rel(a,@(a(O),..., a ( m ) , b ( O,..., ) b(n))) for any formula @ of LfVw with Godel number e such that the free variables of @ are among vo,. .., v,, Ao,.. ., A, and any sequences a of rn + 1 elements from a and any sequence b of n + 1 subsets of a (cf. (b) of 0 1.1.2). 3.2. Second-order reflection principles We now consider generalizations of the partial-reflection principles for second-order formulas: PRQn'

@(a0,..., ak, AO,..., Am)+3u(Trans ( u ) A @"(ao,. ,ak, A. n u,. ..,A, n u ) )

..

where @ is any (2,'-formula with free variables as indicated. Similarly, PRII; is the full second-order reflection principle of BERNAYS[ 19611. REMARK3.1. Using ordered k-tupels and a suitable coding of finite sequences of classes as in 93.1, and assuming some basic axioms (e.g. the axioms of pairing, union, AUS' and IIo'-Comp), the schema PRQ,' can be replaced by the following schema: @(A)+3u (Trans ( u ) A @."(An u ) ) where @(A)is any Q.'-formula with only A as its free variable. Similarly, as in Ch. 11, one may add in PRQn' the formula a. E u A * A , E u as a conjunction within the scope of " 3 u ", and Ai n u may be replaced by Ai. LEMMA3.4. PRII,'

1 PR z!,,

and hence both schemata are equivalent.

PROOF. Let 3 X * ( X , . ..) be a 2i+,-formula, i.e. *(A,. ..) a II,'-forrnula, and assume 3 X * ( X ,...). Then there is a class A such that T(A,...). Applying PRII"', there is a transitive set a such that *"(A n a,. ..), hence

( 3 X T(X, ...))".

Let BL, be the theory Ext + Fund + AUS' + PRII,' From 92.1 we recall that BL,

Pair+ Sum + Inf + Repl'.

(Bernays-LCvy).

304

KLAUS GLOEDE

BERNAYS[1961], pp. 138ff proves: B L I k P o w , hence B L 1 k B , since B = BLo + POW. PROPOSITION 3.1.

BL,,,

+ AC k II,'-AC.

PROOF. Let Q, be a III,'-formula and suppose that the instance of II,'-AC for such a Q, does not hold, i.e. v X 3 Y @ ( X , Y,...) A v Y 3 X - @ ( X , Y x

,...).

Obviously this formula is equivalent to a Ili+z-formulaq.(For simplicity, we assume that Q,(a,A) has no free variables other than a and A.) Applying PRIIA+zto q A Vx, y 32 (z = (x,y)) we obtain the existence of a transitive set b which is closed under pairs such that '$'.

However, this contradicts Lemma 3.3. COROLLARY 3.3.

BLntZ+ AC k SAC.

PROOF. Use Lemma 3.2(a). In fact, Corollary 3.3 can be improved to THEOREM 3.2. BL, +AC 1 SAC. PROOF. A proof is given in BERNAYS[1961], pp. 141ff. Taking a closer look at the proofs given in BERNAYS[1961], one easily sees that all his results only require BLI rather than BL = BLo+ PRII; = VNB + PRII: with one exception: Specker's result that the full impredicative schema of comprehension, IIo2-Cornp, holds in BL. If we introduce the following schemata: Q "'-Co m p

3 Y v x (x E Y -Q,(x,...)),

where Q, is any Q,'-formula (such that Y is not bound in method shows:

k

a), Specker's

k

THEOREM 3.3. (i) BL1 IIo'-Comp, hence BL1 VNB, (ii) (iii) (iv) (v)

BL,,, II,'-Comp, X,'-Comp, BL,+I k A,'-Comp, B L + PRfiA+l fi,'-Cornp, z:-Cornp, BLo+ PRfi,,' 6,I-Comp.

PROOF. Suppose QnL-Compdoes not hold for some Q,'-formula - 3 Y v x (x E Y -a.(x, ...)).

Q,, i.e.

REFLECTION PRINCIPLES AND INDESCRIBABILITY

305

Now, one only has to verify that in each of the cases (i)-(v) this formula is equivalent to a formula q to which the reflection principle of the respective theories applies. Hence there is a transitive set a # 0 such that T holds in (a,€) (under some appropriate assignment of the free variables of in (a) which contradicts the fact that (a,€) k2II$-Comp (cf. Lemma 3.1). Parts (iv) and (v) are from BOWEN[1972], Lemma 2.1.5. COROLLARY 3.4 (Specker). BL k II:-Comp,

and hence BL k QM.

Remarks and additions. (1) BOWEN[1972] denotes by BLntl the theory (which by Theorem 3.3 (i) and the Remark following below is equivalent to) VNB + PRII:?+l,let us denote it by BE,+1; B"L0= VNB + PRfIo'. Then (in our notation) BL,, 1BL,, and by Theorem 3.2: BL,+' +II,'-AC 1BL,,+'. (Here II,'-AC can also be replaced by IIt+,-Comp + AC.) Therefore, assuming II,'-AC, both theories are equivalent. Note that BL,+z + AC k II,,'-AC%y Proposition 3.1. We do not know whether BL,,+' and BL,+, are equivalent without assuming some kind of axiom of choice. Of course, assuming ZF +AC (for the metatheory) by Lemma 3.3 and Theorem 3.1, both have the same transitive standard models (with respect to the satisfaction relation k').In particular, (V,,E)

k2PRfI"'

-

(V,,E)

k' PRII,'.

In any case, even without the AC, we clearly have BL 1BLn for each n. Finally, it should be noted that BL is consistent iff the theories BL, are consistent for each n. (2) In BERNAYS[1961], pp. 138ff it is shown that in the theory BL,, the reflection principle PRIIk+I can be strengthened to a schema which asserts the existence of a "reflecting" set of the form V, for some inaccessible a (cf. Theorem 3.4). We cannot use this method in order to strengthen PRIIo', "since by Lemma 2.1 (iv), and the fact that B = Ext + AUS' + Fund + Pow + PRII,,' (§2.1), we have:

-

in (a) (V&)

kzB

f-,

(V,,E)

k2PRIIo',

and therefore one cannot prove in B (nor in VNB) the existence of inaccessible cardinals (assuming consistency). So one has to use the method of 02.1, and in fact Metatheorem 2.1 shows that PRIIo', too, can be strengthened to assert the existence of a "reflecting" set of the form V, (though a need not be inaccessible). One can also use the method of 02.2 (which is an extension of the methods yielding Metatheorem 2.1) to obtain a strengthening of PRrIo' (and similarly for PRIIA,,) as follows: Let T be the theory

VNB

+ All-Comp, i.e. BLo+Pow + Fund + A,'-Comp.

306

KLAUSGLOEDE

In T one can define a satisfaction relation Sat, ( A , a )for the class V of all sets with respect to formulas of TBsuch that Sat, is a Al'-formula and one can prove in T: Sat, ( A x { j } , r @ ( A j )t7,)@ ( A ) for any class A and any II,'-formula @(ai)with Ai as its free variable (cf. MOSTOWSKI [1969], BOWEN[1972], Lemma 2.1.14). This allows us to use the method of proof for Theorem 2.2 and Corollaries 2.2-2.4 replacing V, B (which becomes by V and deleting the assumption that (V,,E) redundant since V is a "model" of T and B C T). Thus in T one can prove, e.g. 35(V,,E) < (V,E), and in T the schema PRII,' can be strengthened to yield the schemata (+) and (++) of 02.2. Similarly, though by a somewhat different method, it is shown in BOWEN [1972], Corollary 2.1.19 that the following schema of complete reflection is provable in BL,,,,,: CRfi,,'

35 [a E V,

A

Vx E V,(@(x,A)

-

Re1 (V,,@(x,A n V*)>>I

where @ ( a , A )is any fi,'-formula with free variables as indicated (and similarly for formulas with finitely many free variables, cf. Remark 3.1). By the same method one can prove: BL,, + A;+,-Cornp CRII,' (cf. also Theorem 4.6). This is the best possible result insofar as in BL, + A i ' Comp (BL,) one cannot prove CRII,' (CRfI,' resp.) (assuming consistency; cf. GLOEDE[1970], p. 75). For a different situation in the case of P R I I 2 and PRII,' cf. the end of 01.3 and Metatheorem 2.1. (3) One can easily prove that the theory BL is consistent with Godel's axiom of constructibility V = L (Godel [1940]), (see BOWEN[1972], Theorem 3.1.2). This result has been extended to systems containing reflection principles of any finite or even transfinite-type theory by TAKEUTI[1965]. Let Ref' (BOWEN[ 19721) be the (weak) second-order complete reflection principle 35 Vx E V, [@(x) Re1 (V,,@(x))]

-

where @ ( a )is any IIo2-formula with a as its only free variable (thus @ may not contain any second-order free variable) and BL' = BL + Ref'. THARP [1967] has shown that BL' + (V = L)

BL

(cf. BOWEN[1972], Theorem 3.2.2),

and by Bowen's result mentioned above, B L I BL'. Therefore BL is consistent iff BL' is consistent.

REFLECTION PRINCIPLES AND INDESCRIBABILITY

307

(4) Finally, BOWEN[1972], Ch. 111, has shown that the consistency of BL or even BLI implies the consistency of VNB with various axioms which imply V # L (e.g.: for almost all regular cardinals a,( L a , € )is an elementary submodel of ( L , E ) ) and which originally have only been obtained from axioms asserting the existence of certain large cardinals, the existence of which cannot be proved in BL. 3.3. Mahlo’s Principle In his 1961 paper, Bernays emphasizes the fact that the schemata of reflection for second-order languages are “self-strengthening” in a very strong way (the corresponding schemata of partial reflection for firstorder formulas only partly partake of this property). In particular, the schema PRII,’ can be strengthened to yield the existence of “reflecting” sets of the form Vn,where a is a cardinal which is very large in the Mahlo hierarchy. In this section, we only discuss some of the results which are related to Mahlo’s principle and to the problems which are relevant to the class terms and class variables distinction, as expressed by MontagueVaught’s theorem. For further results, we refer to GAIFMAN[1967] and GLOEDE[19711. THEOREM3.4. In the theory BL,,, = Ext + AUS’ + Fund + PRX,,, the schema PRIIA., can be strengthened to the following schema o f partial reflection : @(Ao,... . A,,,)+35 [in (5)A @“c(A0n Vc,.. . ,A,,, n Vc)], where @ is any IIA+,-formulawith free variables as indicated.

PROOF. BERNAYS[1961], p. 141 shows that PRJI!,,, can be strengthened to a schema which has in place of “Trans ( u ) ” the stronger property Strans ( u ) A Mod ( u ) . As mentioned at the end of 92.2, one can prove in ZF:

-

Strans(a) A Mod(a)t,(a,E)+’B

+’ VNB.

(a,€)

By a result of SHEPHERDSON [1952] (03.14) (cf. MONTAGUE-VAUGHT [1959], p. 228), any super-complete model ( a , € ) of VNB is of the form V, for some a : this follows from the absoluteness of the rank function and the axiom of Fundierung. Clearly, any such CY must be inaccessible by Lemma 2.1(iv). Note that we have a corresponding result for PRIIo’, provided we drop the requirement “in (t)”,cf. §3.2(2).

308

KLAUS GLOEDE

In particular, one can prove in BL, that there is a “large” class of inaccessibles. There are several ways of interpreting the concept of a “large” class of ordinals, e.g. we might call a class A of ordinals large, if it is unbounded or even closed unbounded (i.e. the range of a normal function defined for all the ordinals). Unfortunately, the class of inaccessibles is not closed, since the limit of an ascending sequence of inaccessibles need not be inaccessible (since it may be cofinal with 0 ) . A more suitable notion of a “large” class of ordinals is provided by the following definition: DEFINITION3.1. stationary (A) :-VF [Nft (F)+,3[ E A F(S)= 51, stationary (A,&):- V f [Nft (fp)+3[ E A f ( 5 ) = 51. Thus a class A is stationary (sometimes also called dense) iff it intersects each closed unbounded class of ordinals; “ A is stationary in a” is the corresponding concept relativized to V,. LEMMA3.5. lim (a)A A C a. + .( V,,E)

stationary ( X , ) [ A ]t* stationary ( A , a ) .

A further strengthening of PRIIA,, is provided by the following THEOREM3.5. BL,,,

((5 I in (5) A

@(Ao,.. . ,A,)+stationary

Qv6(A, n Vc,. . . ,A,,, n V.)})

f o r any II!,+,-formula @ with free variables as indicated. PROOF. Let F be any normal function. Applying Theorem 3.15 to the n!,+,-formula Nft ( F ) A @(An,.. .,A m ) ,

we obtain the existence of some ordinal a such that in(a)A N f t ( F n V,)”-

A

@‘-(Ann Va,..., A,,, n V a ) .

Clearly, lim ( a ) + [Nft ( F n V,)”-

t* a

= F(a)l,

and this proves the theorem. Let us define the following versions of Mahlo’s operation: DEFINITION 3.2.

H ( A ) := (5 I in (5) A stationary (A,()}, Ho(A) := (5 I reg (5) A stationary (A,[)}.

REFLECTION PRINCIPLES AND INDESCRIBABILITY

309

(These operations are roughly the duals of the operation M of KEISLERTARSKI[ 19641.) In BERNAYS[1961], p. 41 it is shown that one can define in ZF a predicate Ma (a,?) ("a is a Mahlo number of order y " ) by a formula of TeZF satisfying the following recursive conditions: Ma (a,O)f* a E H(On) (i.e. in ( a ) ) ,

Ma (a,? + 1) f* a E H({5 I Ma (5,~)}), Ma ( a , A ) f* VTJ< A Ma (a,q) for A alimit number. (This definition agrees with the notion of a hyper-inaccessible number o f type y as defined in LEVY[ 19601.) Replacing H by Hn, we obtain Mahlo's original definition of the T o u numbers ( T a n y is the a th ordinal among the rOr numbers, cf. MAHLO[1911-19131). COROLLARY 3.5. B L I E M , where M is the following formula (which might be called Mahlo 's Principle):

stationary ( A ) + stationary (H(A)).

M

PROOF. Apply Theorem 3.5 to the H,'-formula stationary (A) and use Lemma 3.5. Although the intersection of two stationary classes may be empty, one can prove in BLI the following stronger Mahlo diagonalization principle : M*

VTJ(stationary (A,,)) + stationary ({Elin (6) A VTJ <[ stationary (A,,,()}):

COROLLARY 3.6.

BL,

M*.

PROOF. Let YP(A,TJ) be the H,'-formula stationary (A,,) (where A,, = {x ( ( T J ,E ~ A}). ) Applying Theorem 3.5 to the formula VTJV(A,r)) which clearly is equivalent to a H,'-formula, we have:

B = (5 1 in (5)

A

VTJ< ( Y"<(A n V<,TJ)} is stationary.

COROLLARY 3.7. BL, 1 stationary ((6 1 Ma (&y)}). PROOF. By induction on y using Corollary 3.5 for the case y = 0 (On is stationary) and the successor stages, Corollary 3.6 for the limit stages. We note that the result obtained in Corollary 3.7 can already be derived from the principle M* rather than PRnl1, and in fact even from the principle M * obtained from M* by replacing the class variable A by a syntactical variable A ranging over class terms (of the language of ZF) only. While (the universal closure of) M* is a Hzl-statement,each instance BL1.Then of M * is a Z2'-formula. Let a be an ordinal such that (V,,E)

+*

310

KLAUS GLOEDE

(V,,E) kzPR C2' by Lemma 3.4. Therefore, each instance of M * being satisfied in V, is already satisfied in some V, for some /3 < a.Moreover, since there are only countably, many formulas of 2?= (and hence countably many instances of M * ) , an argument due to LEVY[1971] (Corollary 10b) shows that there is an inaccessible /3 < (Y such that V, satisfies each instance of M * . On the other hand, JENSEN[1972] (Theorem 6.1) has shown that (V,,E)

kzPRIL'

reg (a)A Vx C a [stationary (x,a) +35 < a stationary (x,t)l f*

assuming Godel's axiom V = L. In particular (in ZF + (V = L)): ( v,,E)

kzP

R ~++' ( v,,E)

k2B + M*,

whereas hence

(V,,E)k2 PRlIl'+3(


(V,,E)+zB+bl*-+3t < a ( V c , E ) k 2 Z F + M * as mentioned above. This result might be compared with MontagueVaught's theorem, since B and ZF are related to each other like M * is related to M". Some applications of the concept of Mahlo numbers can be found in SCHMERL [ 19721 and SCHMERL-SHELAH [ 19723. For recursive analogues of Mahlo numbers cf. ACZEL-RICHTER[ 19701. 4. Indescribable cardinals 4.1. Higher-order languages

Having introduced class variables, which are called variables of type 2, whereas set variables are regarded as variables of type 1, it is natural to extend the language of 2fVNBfurther by adding variables of any finite (and possibly even transfinite) type. Variables of type n will also be denoted by X", Y " ... , . For formulas of this language (with atomic formulas of the form s = t and s E t for any kind of variables s, t ) we extend Lkvy's classification of first-order formulas as follows (cf. HANF-SCOTT[ 19611):'

' The definition that follows does not completely agree with the notation introduced in the which are not previous sections since we have used I,' to denote the set of formulas of 2vNs allowed to contain free variables of type 3, but only set and class variables. In most cases we consider only formulas which contain free variables of type at most 2 (i.e. class variables). Thus, if there is any risk of confusion, we give additional information on the free variables which are allowed to occur in the formulas under consideration.

REFLECTION PRINCIPLES AND INDESCRIBABILITY

311

A IIom-formula is a formula in which every bounded variable is of type rn and every free variable is of type G rn + 1, Zom= nom. A K+Iformula (Z~+,-formula)is a formula of the form VX"'"-v ( 3 X m + ' * resp.) where !P is a Cn"-fomula (II," -formula resp.). A A,"-fomula is a formula which (in some appropriate type theory) is equivalent to both a n,,"- and a 2,"'-formula. Thus the IIol-formulasare just those of Bernays' set theory B (as in the 1958 monograph), and the IIt-formulas containing free variables of type at most 2 are the formulas of VNB set theory (disregarding the fact that for some technical reasons, we have taken u = v, u E v and u E A as the only atomic formulas of these languages). It is debatable whether the language of finite- or transfinite-type theory is more adequate for set theory than the languages considered in the previous chapter (for a discussion, cf. TAKEUTI[1965] and [19691), in any case the idea of investigating the type-theoretical classification of various definitions and propositions with respect to a particular structure has turned out to be fundamental for a large number of results (cf. 01.3 for applications within the scope of this paper). Therefore, we do not introduce a logical system for type theory (this could be done along the lines sketched in 003.1 and 3.2 for the second-order language), but consider only particular models for certain axioms in the language of type theory (like the reflection principles for this language). Taking this approach we avoid taking into account logical axioms for type theory like comprehension axioms and various kinds of choice principles (like those introduced in 03.1) since these are satisfied in any model under consideration (cf. Lemmas 3.1, 3.3 and Corollary 3.2 for the case of second-order language). Throughout this chapter we assume the axioms of ZF + A C for our metatheory (the use of the axiom of choice could be avoided in most cases by some simple modifications). For the following we again require a suitable formalization of satisfaction in a structure of the form (a,€) for formulas of finite-type theory. In particular, we assume that a set is assigned in a suitable manner to each formula @ of finite-type theory. Then a formal satisfaction predicate for IIom+'-formulascan be defined in ZF set theory (e.g. by reduction to the case of satisfaction of a IIol-formula in the structure ( P ' " ( a ) , E ) (where P " ( a ) is the result of applying the power set operation to a m-times, Po"()= a ) in a manner indicated in 02.2 for the case m = 1). We let G

r@7

( a , € ) +"'+I

e [ b , . . . , ak);(bO,...,b n ) I ,

(though somewhat imprecise we also use the notation

(a,€>I="'+'e[ao,.. . , ak ;h,... b,l)

312

KLAUS GLOEDE

be a suitable formalization in ZF set theory of the corresponding metamathematical statement " e is the Godel number of a IIom+l-formula@ with free set variables vo,.. . , vr, free class variables A o , .. . , A,, ao,.. . , a, E a, bo,..., b,, c a , and @ is true in ( a , € ) if ai(bi) is assigned to v, (Ai resp.) for i s k, j s n, and bound variables X'" are interpreted to range over P ' ( a ) " . is of 91.1.2, kzis the same relation as defined in 92.2.) A formal definition of satisfaction as required can also be given without referring to satisfaction for IIo'-formulas, details are given in BOWEN [1972], pp. 42ff, for the case m = 1 (and this definition can easily be generalized for any finite m ) . The requirements on the formal definition of satisfaction which we need in the sequel are the following: (+I

4.1.1. Uniform definability. For each m > O , n 2 0 there is a A l m formula v',,,( v o ,Xom+l,. ..,X,"'+l) with free variables as indicated such that for every IIo"-formula @(XOmfl,. . . , X,,"+') with free variables as indicated, for any inaccessible a and all bo,.. . , b, E 8"(V,): (V,,E)+"+l

'O.'[bo,..., b , ] * ( V , , € ) ~ = " + r'Pm7[r@7;bo,..., ' b,].

(v',,, is just the formula defining satisfaction in (V,E): ( V , E ) ~ " ''@."Al*q,n('@.',A), where A is a class coding finitely many classes Ao,.. . , A,,.) As a consequence (cf. LEVY [19711, Theorem 8): 4.1.2. Absoluteness. For each n,m > O there is a n,"-formula W(vo,Ao) with the only free variables uo and A , which is universal for the set of IInm-formulas @(Ao)which contain only the free class variable Ao, i.e. for any such formula @(Ao),every inaccessible a and every A c V, : (V,

E)

km+' '07[A]

(V,,E) +"+I

t ,

T[T,A].

(To obtain v' from the A,"-formula v'" of 34.1.1 consider the formula

QXnmYrma(v0, A , , X , ",..., X,") where qma is the HI"' (2,")-formula which is equivalent to v', if Q is V (or 3 resp.). Now, contract the quantifiers QX,," and the first quantifier Q Y" of PmQinto a single quantifier QXnm(as described in §3.1 for the case m = 1) and substitute g ( v o )for v o where g('VXlm QX," @?) = -@- for any II,,"-formula VXI"* . * QX," @(Ao,X I m ,..., X,"), g ( v o )= 0 other-

wise.) (The requirement that a be inaccessible can be weakened in §§4.1.1 and 4.1.2.)

REFLECTION PRINCIPLES A N D INDESCRIBABILITY

313

4.1.3. Adequacy. We extend the process of relativization to nnmformulas as follows: W’ is the formula obtained from @ by replacing any quantifier of the form Vx by V x E a , VX by Vx E P ( a ) , VX“’ by Vx EP‘(a), and similarly for existential quantifiers (where in the last two cases x is a suitably chosen first-order variable). Then we have, as in the case of a first-order formula, the following schema which expresses the material adequacy of the satisfaction relation:

For any nmm-forrnula@(vo ,..., vk, A. ,..., A t ) with free variables as indicated and any elements a, ,..., ak E a, b, ,..., b, E p ( a ) : ( a , E ) F ” ” ‘O,”U~ ,..., a r ; b , ,..., b,]*@’”(ao,..., U k , bo ,..., bL). Since we shall consider only structures of the form ( a , € ) for transitive sets a, any free variable of type i may also be considered as a variable of any higher type. Therefore, it is sufficient to define satisfaction for formulas which contain only free variables of the same (highest) type. We have separated the first-order free variables from the higher-order free variables only for technical reasons, in connection with the reflection principles which are considered later.

REMARK.

4.2. Indescribable cardinals

By P W we denote the partidreflection principle for formulas in which contain free variables of type at most 2: DEFINITION.Let

r

r be either II,’”, X n m , or An’”. Then:

P R r @(u,,..., U k , A, ,..., A i ) + 3 ~[Trans ( U ) A

(PU(ao,. . . , a,, A , n u,. .., A, n u)l,

where @ is any r-formula with free variables as indicated.

I’-indesc ( a ):t,a > 0 A (V,,E) +’”+’PRT “ a is I?-indescribable”, r-desc ( a ):o-r-indesc ( a ) “a is r-describable”.

REMARK4.1. (1) Note that for each set of formulas l‘ as considered above the predicate “ a is r-indescribable” is defined by a formula of ZZF. (2) If m > 0 , we may also replace the principle PRII,”’ by the same principle restricted to llnm-formulas @ ( A )with the free-class variable A only (cf. Remark 3.1). (3) Intuitively, “CY is rInm-indescribable” means that for each K‘“-

3 14

KLAUS GLOEDE

formula @(uo,... , uk,A",.. . , A1)(with free variables as indicated) and any sets a. ,..., ak E V,, bo,..., b, C V,, if ( V,,E)

+"'+I

@[a,, . .. , ak ; bo,. . ., bil,

then there is a transitive set a E V, such that ao,.. . , ak E a (if m > 0 or n > 1) and ( v , , E ) ~ m + ' R e l ( ~ ~ + l,..., , ~ )Uk,a; [ u o b o n a , ...bl n u ] , i.e. by §4.1.3 Re1 (V,,Rel (a,@(a,.. . , ak,bo n a,. .. , b , n a ) ) ) which again is equivalent to

, bl n )) Re1 (a,@(&,. .., a,, bon a,. _. (since a n V,

= a),

and again by 4.1.3 this is equivalent to

( a , E ) ~ ' " + ' @ ,..., [ a o a k ; b o n a,..., b l n a l .

Moreover, if n > 0 or m > 0 then, by Theorem 3.4 (and the remark at the end of the proof for the case of PRII,') a can be assumed to be of the form V, for some p < a, and /3 can be assumed to be inaccessible if n > 0 and m > O . (Note that we not only identify a formula with its Godel number, but also use the same letters to denote numerals (in the metamathematical sense) and natural numbers (in the formal sense). We hope that the reader will discover the right meaning from the context as a correct distinction will render the notation unnecessarily complicated.) (4) Some authors define the notion of r-indescribability by using instead of I?-formulas which contain free second-order variables A,,, . .. ,Ak, the corresponding formulas which have unary relation constants Aiin place of A iand replacing the structures (V,,E) by structures ( V,, E, bo,..., b k ) where the bi's are subsets of V, interpreting Ai (whereas b, is assigned to Aiin our notation), and similarly for structures (a,€) for arbitrary sets a (cf. LEVY [1971]). In this chapter we are only concerned with the case m > O which implies that every indescribable ordinal is a cardinal, in fact inaccessible:

-

PROPOSITION 4.1. &'-indesc (a) in ( a )t,(V,,€) V B . PROOF. Immediate from the fact that Pow + PRIIoi (§2.1), (94) and Lemma 2.1(iv).

Similarly:

-

PROPOSITION 4.2. rIIa-indesc (a) { V,,E)

B = Ext + Fund + AuS'

BL.

+

REFLECTION PRINCIPLES A N D JNDESCRIBABILITY

315

PROPOSITION 4.3. n,'-indesc (a)t-,C!,+,-index(a). PROOF. Lemma 3.4. DEFINITION4.1. rrnm:= px(II,"-indesc (x)), cnm := px(X,,"-indesc 7,"

(x)),

:= px(IInm-index (x) A

2,"'-index (x)).

Since the universal closure of each instance of PRII,' is (equivalent to) a II!,+'-sentence, it follows from 4.1.2 and the fact that the clause "for all II,'-formulas " can be expressed by a universal quantifier ranging over the set of Godel numbers of II"' formulas that for n > O there is a II!,+'sentence W such that ( VwE) I='PRJJn' t-,(Vm,E)

'I?,

and hence n-,' is II!,+l-describable(if it exists).' The last statement is true even for the case n = 0, for ( V,,E)

PR&'

(V,,E)

t-,

kzVNB

by Proposition 4.1, and the universal closure of the conjunction of the finitely many axioms, by means of which VNB is axiomatizable, is a 1111-sentence.Alternatively, one may use the fact that there is a 111'sentence 9 such that in (a)f* (V,,E) kzT.Therefore, we obtain: 4.1 (HANF-SCOTT[1961], LEVY [1971], Corollary 17). THEOREM (i) (ii)

n-,,I

= v!,+' = rn',

7,'

< n-!,+' < n-:.

(With the understanding that pxcp(x) < px+(x) is read as follows: if 35+(5>,then Xcp(5) and pxcp(x)< pxlCl(x).) We now turn to the case m > 1. The situation is completely different for this case for the following reason: In our definition of rInmindescribability, we have restricted the II," -formulas to those containing free variables of type at most 2, and for the case m > 1, this is a true restriction which, however, is necessary: REMARK4.2. If in our definition of K"-indescribability, we allow any IInm-formula@ (containing variables of type m + 1) to occur in PRII,", then we obtain (for m > 0) the following wider notion of indescribability: a is II,"-indescribable in the wider sense iff for each II,"'-formula

' BY " / L x ( P ( xexists" ) we mean "3[cp([)and / L X ( P ( X ) is the least ordinal x such that ( ~ ( x ) " .

316

KLAUS GLOEDE

@(AO"+', .. .,Akm+')with free variables as indicated and any bo,...,bk E 8"(V,): if (V,,E) +"+I @ [ b o ,..., b , ] , then there is a transitive set a E V, such that ( a , € )+"+I @[bon P m - ' ( U ) , . . . ,bk n g m - * ( U ) ] .

If m = 1, this agrees with our previous definition, however, if rn > 1 then there are no n,"'-indescribable cardinals in the wider sense: Consider the III,z-formula3X (X= Ad). Then clearly for each a:

3 X (X= Ad)[ V, 1.

( V,,E)

So, if there is a transitive a E V,, such that (a,€)

3 X ( X = Ad)[V,

n9(a)l,

then there exists some b C a such that

b

=

V,

n9(a).

On the other hand, V, n 9 ( a ) = 9 ( a ) (since a C V,), hence 9 ( a )C a, a contradiction. Now returning to our original definition of H," -indescribability, let us assume m > 1 and let us consider some instance of PRII," (corresponding to some n,"-formula @ with the free variable A only). This is, in some suitable type theory, equivalent to a &,"-formula *(A), and its universal closure is of the form VXW(X).By the standard arguments of type theory the quantifier VX can be moved across the quantifiers of higher type in the Z,"-formula V, and hence VXT(X) is equivalent to a C,"-formula. Now, as in the case rn = 1, the statement (V,,E)k"+' PRII," introduces only an additional set quantifier ("for all n,"formulas"), and therefore we have a X,"-sentence Tosuch that (V,,E) +'"+'PRII,"

t*

(V,,E)

+"'+I

'Pa,

is C,"-describable, if it exists. Similarly, anmis also and hence rnm II,"-describable, (if it exists). Thus we obtain: THEOREM 4.2 (HANF-SCOTT[1961], LEVY [1971], Corollary 17). rn", ~

Therefore

n

"

< 7," < r;+i <

rnm+' # anm+' for mtl

r,

< ~ ; + i < n om + l

(m> O ) .

each m,n, but it is unknown whether or


anm+' < rnm+*.

However, Moschovakis has recently shown that the second alternative holds if one assumes V = L. The inequalities of Theorems 4.l(ii) and 4.2 are very strong, e.g. one can prove:

REFLECTION PRINCIPLES AND INDESCRIBABILITY

317

THEOREM4.3 (cf. BOWEN[1972], 02.1.15, THARP[1967], LEVY [19711, Theorem 19h). HA+,-indesc( a )-+ stationary ((6 1 HI,'-indesc ( ( ) } , a ) . PROOF. Let a be IIk+l-indescribable, and let T be the IIi+l-sentence (described in the proof of Theorem 4.1)such that for any inaccessible p : { V&)

t*

II,,'-index (p).

In particular we have: (V,,E)pU, since a is II,'-indescribable and inaccessible. Hence by Theorem 3.5 and Lemma 3.5

(6 I in (5)A ( V& f=' U}is stationary in a, whence the result follows. Similarly: THEOREM4.4 (cf. LEVY [1971], Theorem 19i). For rn > 0 : if indesc ( a ) or C.,",l-indesc ( a ) ,then stationary ((8 1 IT,"' -indesc (()},a), and

stationary ((6 1 Z."-indesc ( ( ) } , a ) .

Additions. (1) LEVY [I9711 investigates the following weaker form of indescribability (where r again denotes IInmor S,,"'): w-r-indesc ( a ):- a > 0 A (a,<) km+l PRT, " a is weakly r-indescribable". The main difference between both notions of indescribability results from a technical problem: If a is a limit ordinal, then V, is closed under ordered pairs and these can be used, e.g. for contracting quantifiers of the same kind. In case of the structure (a,<),however, one has to use an ordinal-pairing function (like Godel's function P : On X On -+ On which is one-to-one and onto). If a is closed under P, e.g. if a is regular, P can be used instead of the operation of ordered pairs. Second, whereas for limit ordinals a, V, is closed under the power-set operation this is not true for a. Thus, one can only prove:

w-IIo'-indesc ( a )++reg( a )A a > o (compare with Proposition 4.1), and any weakly H,'-indescribable cardinal is weakly inaccessible, but need not be (strongly) inaccessible. On the other hand, if a is strongly inaccessible then I V, 1 = la I (by the AC). This implies that for inaccessible

318

KLAUS GLOEDE

a and any rn, n such that m > 1 or m

=

1 and n > 1:

w-II,"-indesc ( a )t,nnm-indesc( a ) (LEVY[1971] Theorem 2.1). Indescribability in the weak sense has also been investigated by KUNEN [1968], 016. (2) Whereas LCvy's definition of r-indescribable ordinals is obtained from our definition by replacing the structures (V,,E) by (a,<),there is a recursive analogue of the r-indescribable cardinals which results from the former (roughly) by considering the structures ( L , , E ) in place of (V,,E). For more details we refer to ACZEL-RICHTER [1970]. 4.3. Large cardinals and indescribability In this section we review some indescribability results for large cardinals. We do not include proofs since in almost all cases a particular method of proof is required. DEFINITION 4.2. A cardinal K > o is called measurable iff there is a K-complete (which means closure under < K members) non-principal prime ideal P(K);it is called w-measurable iff there is a non-principal R,-complete prime ideal in P(K).The least w-measurable cardinal is measurable, and hence the least-measurable cardinal is %'-describable, since it is the least o-measurable cardinal and is > XI).On the other hand: If K is measurable then K is II1'-indescribable (HANF-SCOTT[1961]). (The proof uses an ultrapower construction and an extension of Los' Theorem, cf. SILVER[1971], Theorem 1.10.) VAUGHT[1963] has shown that the converse of the above is not true, this also follows from Silver's results described below. DEFINITION 4.3. (ERDOS-HAJNAL[1958]). If f is a function and the domain of f is K < " ' ( K ( ~ ) ) ,the set of finite (n-element resp.) subsets of K , then a set a K is called homogeneous for f iff f ( x ) = f ( y ) for all finite subsets x , y a of the same cardinality (of cardinality n resp.).

c c

K

K

c

[Ft (f) A dom (f) = K<" A rng (f) 2 + 3 x ( X a A x has order type a A x is homogeneous for f)], +(a)" : e V f [Ft (f) A dom (f) = K ( " ) A rng c f ) c2 + 3 x ( x C a A x has order type a A x is homogeneous for f)]. +(a)<@:-Vf

If K is measurable, then K + ( K ) < ~ (Erdos-Hajnal), and the least K such that K + ( K ) < * is obviously II,'-describable, hence by Hanf-Scott it is less than the first measurable cardinal (providing such a cardinal exists). STATEMENT 4.1.

K

+( K ) '

II,'-indesc ( K ) .

t ,

REFLECTION PRINCIPLES AND INDESCRIBABILITY

319

A proof of this statement and other properties equivalent to II,'indescribability can be found in SILVER[1971], Theorem 1.13 (cf. also BOWEN[1972], 42.2).

STATEMENT 4.2. p x ( x + (x)*) < p x ( x + (0)'"') < p x ( x + (x)'"); in fact, if K + (o)'", then there is a A < K such that A is II,,"'-indescribable for each n, m < w (SILVER [1966],Corollary 4.4; see also REINHARDT-SILVER [1965] and 04.16 below). On the other hand, if K = p x ( x +(a)'"') and a < K , then K is clearly IIl'-describable (assuming that a is a limit ordinal). STATEMENT 4.3. The notion of indescribability can be extended by using the language of transfinite type theory, viz. the partial-reflection principle PRII,' where I,' is a straightforward generalization of IInmto transfinite-type theory. (Having gone so far, one could also allow n to take transfinite values, i.e. introducing infinitary languages.) In order to define indescribability for transfinite-type theory in ZF set theory there are two approaches which are not equivalent since they are based on different formalizations of satisfaction for transfinite-type theory. For the case of finite m one can reduce satisfaction of IIom"-statements in (V,,E) to satisfaction of IIoi-formulas containing additional unary relation constants in the structure (V,+,, €, V,, V,+l,.... Va+m-l), and since V,, . . ., V,+,-, are (first-order) definable in (V,+,,E), again, this can be reduced to satisfaction of II,'-statements in (V,+,,E) (cf. 04.1). However, for transfinite y, V,+, need no longer be first-order definable in V,+, for 6 < y, so the latter reduction is not possible in the case of transfinite-type theory. Of course, one could still generalize the first reduction for transfinite type theory; however, we shall take the following approach due to REINHARDT[1970], Definition 4.7 and JENSEN [1967a], DEFINITION.a is K-indescribable iff for each IIo'-formula cp ( X o , . . , X , ) with free variables as indicated and all A,, ..., A, C V,: if (V,+,,E) k cp [A,, . . ., A,] then there is a p < a such that,

( V o + , , E ) k ~ [ A o nVfiy*.*,An

Val.

We let K-indesc ( a )be the corresponding formal statement (expressible by a formula $ ( ~ , aof) 9zF using the formalized notion of satisfaction). Clearly we have (by the result of 44.1 to which we referred above):

-

IIom+l-indesc ( a )++ m-indesc (a) for each finite m, in particular: 0-indesc ( a ) IIo'-indesc ( a )f* in (a)f, (V,,E) BL. 1-indesc ( a )t* II2-indesc (a)f* (V,,E)

k*B,

320

KLAUS GLOEDE

Then Silver's result mentioned in 84.2 can be strengthened as follows: If K is the least y such that y - + ( o ) ' ~then {( < K I K-indesc (6)) is stationary in K.

(Cf. JENSEN[1967a], Satz 4, p. 110, and GLOEDE[1972], Theorem 10.7.) If Y < a s p then we define (REINHARDT [1970], Definition 4.6) in ZF ( V A < (VB,E) to mean (informally) ( V,+,,E)

I=

q [ a o , ... , a,]

c*

(vB+,,€) t= q [ a o , .. . , G I

for every a. ,..., a, E V, and every 6Pz,-formula q ( v o,..., v,) with free variables as indicated. Similarly, we define (V&,A

n Va) < (VB,€,A> (forA G V p ) .

Thus (VwE)

3 (VB,E)c*(Va,E)<(Vp,E),

and ( V,,E) < (V,,E) means that (V,,E) is a second-order elementary extension of (V,,E). THEOREM4.5 (REINHARDT[1970], Theorem 4.8). If K is indescribable for some y < K , then there is some (Y < K such that

y

+ 1-

(V&) < (V&. (Unfortunately, for y = 0 this does not imply Montague-Vaught's Theorem 2.2.) In particular, if K is no""*-indescribable, i.e. ( m + 1)indescribable, then ( V,,E) satisfies the principle of complete reflection CRIIo"'+' (which is defined in analogy to CRn,' in 83.2. Using Reinhardt's method, this latter result can be improved as follows: THEOREM4.6 (GLOEDE [1970], Theorem 12.8). Assuming PRIIl"+' + Alm+'-Comp,there is some (Y such that

B+

(Va,E,A n Va) i m (V,E,A),

in particular, if IIlm+l-indesc( K ) , then (V,,E)

+"'+I

PRII,,"+'.

PROOF. By 4.1.1 there is a Alm+'-formulaT(vo,Xo)such that for any given class A :

(i) Vx (( V,E) +"'+' @[x ;A 1 .++ W ( @ , x ) , A 11, for each Ilom+'-formulacD(v,,Xo)with free variables as indicated, and by

REFLECTION PRINCIPLES AND INDESCRIBABILITY

32 1

-

4.1.2, v' is absolute with respect to V , if p is inaccessible:

W v o , A o ) [ ( @ , x )n; AV,l (ii) V x E VB((V,,E)Fm+* (V,,E) +"'+I @ [ x ; A n V , ] ) for each IIom+~-formula @(vo,Ao). By AI""-Comp there is some class B such that V y ( y E B t t v ' ( y , A ) ) ,i.e. B

= {@,x

-

1 @ is a IIom+'-formulaA ( V , E )

+"'+I

@[x ;A]}.

Define Qo(Ao,A1) := Vx (x E A . 'P(x,Ao)).Obviously, a0 is a I l l m + ' formula. Hence by PRI1,"'" there is some inaccessible cr such that QOV-(B n V,,A n V , ) , i.e. by (ii) (iii) V x ( x E B n V, - ( V , , E ) F " + " P [ X ; A n V , ] ) .

-

Now let @(uo,Ao)be any IIom+'-formulaand a E V,. Then we obtain, using (i) and (iii): (V,E) Fm+' @ [ a: A ]

hence

(V,,E) +"'+I

";A

n

Val,

References ACZEL, P. and RICHTER, W. (1970) Inductive definitions and analogues of large cardinals. In Conference in Math. Logic, London, '70, W. Hodges (Ed.), pp. 1-9. Springer Lecture Notes in Mathematics, Vol. 255. Springer, Berlin. 351 pp. BAR-HILLEL, Y.,POZNANSKI,E. I. J., RABIN, M. O., and ROBINSON,A. (Eds.) (1961) Essays on the foundations of mathematics. (Dedicated to A. A. Fraenkel.) Magnes Press, Jerusalem. 351 pp. BARWISE,J. (1969) Infinitary logic and admissible sets. J.S.L. 34, 226-252. BERNAYS,P. (1958) Axiomatic set theory (with a historical introduction by A. A. Fraenkel). North-Holland, Amsterdam. 226 pp. (2nd ed. (1968), 235 pp.) BERNAYS,P. (1961) Zur Frage der Unendlichkeitsschemata in der axiomatischen Mengenlehre. In BAR-HILLEL et al. (1961), pp. 3-49. This volume. (English translation-revised version.) BOWEN,K. A. (1972) The relative consistency of some consequences of the existence of measurable cardinal numbers. Dissertationes Math. Warszawa. 63 pp. BULOFF, J. J., HOLYOKE, T. C., and HAHN, S. W. (Eds.). (1969) Foundations of mathematics. (Symposium papers commemorating the sixtieth birthday of Kurt Godel.) Springer, Berlin. 195 p. ERDOS,P. and HAJNAL,A. (1958) On the structure of set mappings. Acta Math. Acad. Sci. Hung. 9, 111-131.

322

KLAUS GLOEDE

ERDOS,P. and HAJNAL,A. (1962) Some remarks concerning our paper “On the structure of set mappings”. Ibid. 13, 223-226.

FELGNER, U. (197la) Models of ZF-set theory. Springer Lecture Notes in Mathematics, Vol. 223. Springer, Berlin. 173 pp. GAIFMAN, H. (1967) A generalization of Mahlo’s method for obtaining large cardinal numbers. Israel J. Math. 5 , 188-201. GLOEDE,K. (1970) Reflection principles and large cardinals. Ph.D. thesis. Heidelberg. 129 PP. GLOEDE,K. (1971) Filters closed under Mahlo’s and Gaifman’s operation. In Proceedings of the Cambridge Summer School in Mathematical Logic, August ’71. A. R. D. Mathias and H. Rogers (Eds.), pp. 495-530. Springer Lecture Notes in Mathematics. Vol. 337. Springer, Berlin. 660 pp. GLOEDE, K. (1972) Ordinals with partition properties and the constructible hierarchy. Zeitschr. f . math. Logik 18, 135-164. GODEL, K. (1940) The consistency of the axiom of choice and of the generalized continuum hypothesis with the axioms of set theory. Annals of Math. Studies, Vol. 3. Princeton University Press, Princeton, N.J., 66 pp. (7th printing (1966).) HANF, W. and SCOTT,D. (1961) Classifying inaccessible cardinals (abstract). Notices A.M.S. 8, 445. JENSEN, R. B. (1967) Modelk der Mengenlehre. Springer Lecture Notes in Mathematics. Vol. 37. Berlin. 176 pp. JENSEN, R. B. (1967a) GroBe Kardinalzahlen. Notes of lectures given at Oberwolfach (Germany). 121 pp. JENSEN, R. B. (1972) The fine structure of the constructible hierarchy. AnnaLs o f Math. Logic 4, 229-308. JENSEN,R. B. and KARP, C. (1971) Primitive recursive set functions. In SCOTT(1971), pp. 143-1 76. KEISLER, H. J. and ROWBOTTOM,F. (1965) Constructible sets and weakly compact cardinals (abstract). Notices A.M.S. 12, 373-374. KEISLER, H. J. and TARSKI,A. (1964) From accessible to inaccessible cardinals. Fund. Math. 53, 225-308. (Corrections, ibid. 57, 119 (1965).) KRIVINE,J . L. (1971) Introduction to axiomatic set theory. Reidel, Dordrecht. 98 pp. KUNEN,K. (1968) Inaccessibility properties of cardinals. Doctoral Dissertation. Stanford. 117 pp. KUNEN,K. (1972) The Hanf number of second-order logic. J.S.L. 37, 588-594. LEVY, A. (1958) Contributions to the metamathematics of set theory. Ph.D. thesis. Jerusalem. LEVY, A. (1960) Axiom schemata of strong infinity in axiomatic set theory. Pacific J. Math. 10, 223-238. LEVY, A. (1965) A hierarchy of formulas in set theory. Memoirs A.M.S. 57, 76 pp. LEVY, A. (1971) The size of the indescribable cardinals. In SCOTT(1971), pp. 205-218.

REFLECTION PRINCIPLES AND INDESCRIBABILITY

323

LEVY, A. and VAUGHT,R. L. (1961) Principles of partial reflection in the set theories of Zermelo and Ackermann. Pacific J. Math. 11, 1045-1062. MAHLO,P. (191I ) Uber lineare transfinite Mengen. Berichte iiber die Verhundlungen der Koniglich Siichsischen Akademie der Wissenschaften zu Leipzig, Math.-Phys. Klasse 63, 187-225. MAHLO, P. (1912-1913) Zur Theorie und Anwendung der p,-Zahlen, ibid., I: 64, 108-112 (1912); 11: 65, 268-282 (1913). MONTAGUE,R. and VAUGHT,R. L. (1959) Natural models of set theories. Fund. Math. 47, 219-242. MOSCHOVAKIS,Y. N. (1971) Predicative classes. In SCOTT(1971), pp. 247-264. MOSTOWSKI,A. (1969) Constructible sets with applications. North-Holland, Amsterdam. 269 PP. QUINE, W. V. (1963) Set theory and its logic. Belknap Press, Cambridge, Mass. 359 pp. (Revised ed., 361 pp.). REINHARDT, W. N. (1967) Topics in the metamathematics of set theory, Doctoral Dissertation, 85 pp. W. N. (1970) Ackermann’s set theory equals ZF. Ann. Math. Logic 2,189-249 REINHARDT, REINHARDT, W. N. and SILVER, J. (1965) On some problems of Erdos and Hajnal (abstract). Notices A.M.S. 12, 723. ROBINSON,R. M. (1945) On finite sequences of classes. J.S.L. 10, 125-126. SCHMERL,J. H. (1972) An elementary sentence which has ordered models. J.S.L. 37, 521-530. SCHMERL,J. H. and SHELAH, S. (1972) On power-like models for hyperinaccessible cardinals. J.S.L. 37, 531-537. SCOrT,

D. (1955) Definitions by abstraction in axiomatic set theory (abstract), Bull. A.M.S.

61, 442.

SCOTT,D. (Ed.) (1971) Axiomatic set theory. Proceedings of symposia in pure mathematics 13. Am. Math. SOC.,Providence, R.I.

SHEPHERDSON, J. C. (1952) Inner models for set theory-11.

J.S.L. 17, 225-237.

SILVER,J. (1966) Some applications of model theory in set theory. Doctoral Dissertation, Berkeley, 110 pp. (Published (with the deletion of 04) in SILVER (1971)). SILVER,J. (1971) Some applications of model theory in set theory. Ann. of Math. Logic 3 , 45-1 10. TAKEUTI,G . (1965) On the axiom of constructibility. Proceedings of Symposia of Logic, Computability and Automata at Rome. Mimeographed Notes, New York. TAKEUTI, G. (1969) The universe of set theory, pp. 74128. In BULOFF et al. (1969). TARSKI, A. and VAUGHT, R. L. (1957) Arithmetical extensions of relational systems. Cornpositio Math. 18, 81-102. THARP,L. (1967) On a set theory of Bernays. J.S.L. 32, 319-321. VAUGHT, R. L. (1963) Indescribable cardinals (abstract). Notices A.M.S. 10, 126.

SETS AND CLASSES; On the work by Paul Bernays

@ North-Holland Publishing Company (1976) pp. 325-340.

A REMARK ON MODELS OF THE GODEL-BERNAYS AXIOMS FOR SET THEORY Andrzej MOSTOWSKIT Warzaw ,Poland

1. Notation

We denote the sets of axioms of Zermelo-Fraenkel and Godel-Bernays by ZF and GB respectively. Both these systems are formulated in a first-order language L with identity (denoted by =) and with one binary predicate E. Unlike GODEL[1940], we admit in GB only one primitive notion, viz. the binary relation E and define the predicates Cls(x) (x is a class), M(x) (x is a set) by formulas x = x, ( E y ) ( x E y ) respectively. Axioms A1 and A2 of Godel can then be omitted. A formula cp is called predicative if all its quantifiers are limited to M. A system obtained from ZF by addition of the axiom of choice is called ZFC; similarly GBC denotes a system obtained from GB by adding to it the (set-form of the) axiom of choice. All models for ZF or GB which we consider below have the form (&I,€ where M i s a transitive set of sets. We write simply M instead of ( M , € ) . The extension of the predicate M in a model M is denoted by VM.Thus, V, = M if M ZF but VMC M if M GB. If MI,M 2are two families of sets such that MIC M , and V M= , V,, then we call M , a C-extension of M I and write M , & M , . A language obtained from L by adding to it constants c, for each element m of a set M is denoted by L, We identify cm with a suitable element of M which allows us to consider L, as a subset of M. All models for axioms formulated in LMalways contain M, and c, is always interpreted as m. L(A) or L,(A) denotes a language obtained from L or L, by adding to it a new one-place predicate A. Models for axioms formulated in L(A) or in L,(A) have the form ( N , X ) ,where N is a transitive family of sets and X C N ; the interpretation of the new predicate A is X and the interpretation of E is the relation € of “being an element of”.

+

325

326

ANDRZEJ MOSTOWSKI

For each family M of sets we denote by Def, the family of sets of the form {x E V,: M cp(c,)} where cp is a predicative formula of L, with exactly one free variable and cp(cx)arises from q by replacing the free variable by c, wherever it occurs. Sets which belong to Def, are said to be definable in M. A slightly more general notion of definability is as follows: let M be a transitive family of sets, X C V., A set S is definable in M with respect to X if there is a predicative formula cp of L,(A) with exactly one free variable such that S = { x E V,: ( M , X ) cp(c,)}. We denote the family of all such sets by Def,(X). It is easy to prove that if M is transitive, then so is Def,(X) for any X C V,. We intend to prove below the following theorem:

+

+

For a given countable transitive model M of ZFC there are 2-1 models L of GB such that VL = M. Moreover these models form a full binary tree of height w 1 when ordered by inclusion ; if two models L,, L1do not lie on the same branch of the tree, then there is no transitive model L of GB such that VL = M and L > L, u LZ. A similar theorem is also valid for the “predicative extension” of Peano’s arithmetic; an exact formulation of this theorem is given in §5. 2. Auxiliary theorems LEMMA2.1 (Marek). If M is a transitive model of GB and C is the family of all transitive sets K which satisfy the conditions

MCKCP(V,),

VK = V,,

KFGB,

then the union o f any chain L C C is an element of C. The proof of this lemma is very easy and we omit it. Marek deduced from this lemma the existence of maximal elements of C, and asked about their number. A partial answer to this question is given in Corollary 4.1 below. LEMMA2.2. If M is a transitive model of G B and X C V,, then all the axioms of groups A and B of GB as well as the axioms Cl-C3 and D are valid in the model Def, ( X ) .Moreover Def, ( X )is a C-extension of M.

PROOF. The verification of Axioms A and B are left to the reader. In order to prove that Def, ( X ) is a C-extension of M , let us assume that x C VD,, (x),i.e. that there is a set S such that x E S CDef, ( X ) .Hence, S is a set definable in M with respect to X and therefore S consists of

MODELS OF THE GODEL-BERNAYS

327

AXIOMS

elements of V, which proves that x C V., Conversely, if x f V, then the unit set (x) is definable in M with respect to X whence x f(x)fDef, (X) which proves that x C VDef,(x). Since Axioms C1-C3 deal exclusively with sets, it follows from their validity in M that they are also valid in Def, (X) since in both these models the interpretations of sets are identical. Lemma 2.2 is thus proved. In connection with Lemma 2.2 it is necessary to point out that the statement “a sub-class of a set is a set” may (and generally does) fail in the family Def, (X). Thus, if we agree to call elements of V, “sets of M”, then Def, (X) may, and generally does, contain “semi-sets”, i.e. classes (elements of Def, (X)) which are contained in sets of M (see V O P ~ N Kand A HAJEK(1972)).The existence of semi-sets is due to the fact that the axiom of comprehension is, in general, false in Def, (X). In the case when X is definable in M, the axiom of replacement and the axiom of comprehension are valid in Def, (X) and thus, no semi-sets exist. We shall see below an example of X when not definable in M and yet no semi-sets exist because the axiom of comprehension is valid in Def, (X). The crux of the whole construction is a determination of a set X M such that Def, (X) is a model for the axiom C4 of replacement. Unfortunately I do not know of any workable, necessary, and sufficient conditions for this to be the case and have to rely on results established by FELGNER [1971] in a special case of a denumerable model. In what follows, M is a transitive denumerable model of GB. Let P E Def, and R € Def, be a binary relation which partially orders P. Elements of P are called conditions. We write p s q instead of pRq and read this formula: p is an extension of q. We define by induction a binary relation (forcing), whose left domain is P and right domain consists of all predicative sentences of L,(A):

It

Whenever cp is a formula, we denote by Fr(cp) the set of its free variables. For y € MFr(C), we denote by cp ( y ) the sentence obtained from cp by substituting cY(”)for 0 throughout cp for each vEFr(cp). With this , notation we have :9

328

ANDRZEJ MOSTOWSKI

LEMMA2.3. For each predicative formula cp of LM(A) the set { ( P , Y ) C P x MFr(C): P I/- cp(Y)l

belongs to Def,. A set G C P is generic (more exactly: generic in P over M ) if it has the properties: (i) If pCG and p s q , then q f G ; (ii) If p , q C G, then ( E r ) [ ( rC G ) & ( r S p ) & ( r 6 q ) ] ; (iii) If S CDef, and S is dense in P, then G n S # 0. LEMMA2.4. Each condition belongs to at least one generic set. LEMMA2.5. If G is generic then ( M , G ) cp = ( E P ) ~ (1 1 P cp) for each predicative sentence cp of LM(A). In order to prove the next two lemmas we make the following assumption about P : ASSUMPTION (A) Whenever x C VM,O# x C P and x is a chain with respect to S , then there is a condition p such that p S q for each 4 in x. LEMMA2.6. If M GBC, G is generic, rn C V, and cp is a predicative formula of L,(A) with exactly one free variable v, then there is a set n C VM such that

( M , G )I= {8~cpl).

PROOF. It is sufficient to show that the set

Q = (P CP: ( X ) r n [ P It- c p ( c x N 7 cp(c*)l) is dense in P. Once this is shown the rest is easy: by Lemma 2.3 the set Q belongs to Def,, hence there is a p in Q which belongs to G and it is sufficient to take n = { x C m : p cp(c,)}. The proof that Q is dense closely follows the construction used by FELGNER [1971]; it is therefore sufficient to indicate only the main steps of this proof. We can assume that rn is infinite. Let qoCP. For arbitrary ( x , p ) in V, x P we denote by Z ( x , p ) the set of elements q in P which have the following properties: (9 4 S P and 4 It- cp(cx)v-7 cp(cx); (ii) whenever r has the property (i), then rk (4) s rk ( r ) . We easily see that Z(x,p)E V., If 0 # a Con n V, and g C V, n P" then we denote by W ( g )the set of conditions q which have the properties: (iii) q s qo and q s r for each r CRg ( 8 ) ; (iv) whenever s has the property (iii), then rk (4) S rk (s).

It

MODELS OF THE GODEL-BERNAYS AXIOMS

329

For LY = 0 we define additionally W ( g ) = 0 . We can show easily that W(g)C VMfor each g C V, n P a and each (Y COn n VM. Let p be a cardinal of VMand let f be a function such that f E VMand f is an injection of p onto m. The existence of p and f follows from the assumption that M GBC and m C VM.Using transfinite induction we define two sequences {Pz},{Qz} of type p which are elements of VMand which satisfy the following equations for each 6 < p :

+

Qz= { g c( U pa u {so})"' : (g(0) = 40)tk ( a ) t ( g ( l + a)Epa 1 tk l+*(6>l+,[y < 6 + g ( y ) g(6)11, f't= U { Z ( f ( S ) , y ) Y: CU{W(g): gCQt1)-

Using the axiom of choice in M we can select functions g, h in VMof type P such that g ~ ( 1 + 0 ~ C &h (, 5 ) c W ( g f . ( 1 + 5 ) ) and g ( 1 + 5 ) E Z ( f ( t ) ,h ( 6 ) )for w c h 6 < p. Thus g is a decreasing function and by (A) the set W(g) is non-void. For an arbitrary p in W(g) we have then p C Q and p s q,, which proves the density of Q.

LEMMA2.7. If M is a transitive model of GBC, G is generic and y is a predicative formula of L,(A) with exactly two free variables u, w, then f o r each m in VMthere is a set n in VMsuch that (*1

( M , G ) + ( v ) ( w ) { [ ( vEc,)&cpI+

( E w ) [ ( wEcn)&cpl).

PROOF. This is again a repetition of the construction of Felgner and it is sufficient to indicate only its main steps. We put R =(PEP: (En),(X),(Y),(Ez)"P

It

[ 7 cP

(~x,~,)VcPO~x,~*)I~

and claim that R is dense in P. To show this we choose qoin P and denote by p and f a cardinal and a bijection as in the previous proof. We can assume that p is infinite. Let Z ( x , p ) be a set defined as follows: if there are q s p such that (i) q It- (EW)MP(C,,W)then Z ( x , p ) consists of all the conditions 4 s p which have the property (i) and the following property: (ii) whenever r s p and r has the property (i), then rk (4) s rk ( r ) . If there are no q with the property (i) then ( q ) s p(Er)sqrIt ( E w ) ~ ~ ( c ~ , w ) and hence there are q s p such that (iii) q I / - ( E ~ ) ~ c p ( c ~ ,In w ) this . case we let Z ( x , p ) be the set of all conditions q s p which have the property (iii) and are such that whenever r s p has the property (iii), then r k ( q ) s r k ( r ) . It is easily seen that Z k p 1E V M . We define S ( x , q )as follows: if q non Ik ( E w ) ~ ~ ( c ~then , w )S, ( x , q ) = 0. Otherwise, let S ( x , q ) be the set consisting of all the elements y E VMwith

330

ANDRZEJ MOSTOWSKI

the following properties: (v) 4 cp(cx,c,); (vi) whenever q It cp(c,,c,) then rk ( y ) G rk (2). It is again easy to show that S(x,q)C V,. Finally, let W(g), P6, QE,g, h be defined as in the proof of Lemma 2.6. Using once more the axiom of choice, we obtain a function k € VMwith domain V, such that k ( c ) C S ( f ( ( ) ,g(1+ 6 ) )for each 6 < p. Then rg(k) is a set n C VMsuch that for any p in W(g) and arbitrary x in m, y in VM there is a z in n satisfying p -,cp(c,,c,)v cp(c,,c,);moreover p s qo.The density of R is thus proved. If now, p CR n G and n is a set whose existence is secured by the fact that p C R, then formula (*) holds for this set n. This proves Lemma 2.7.

It

It

For the benefit of readers not acquainted with Felgner’s paper [1971] we add below some comments about the intuitive meaning of constructions carried out in two proofs sketched above. In order to prove the density of sets Q and R we have to show that each q o € P has an extension which belongs to both Q and R. These extensions are obtained by constructing successive extensions of qo and repeating this process transfinitely many times. In both proofs we represent the given set m as the range of a one-to-one function f whose domain is a cardinal p and assume that p is infinite. The sequence of successive extensions of qo is denoted in both proofs by g. Thus g is a decreasing function with domain p whose values are conditions. The initial term of g is g(0) = qo. If 6 < p and g ( a ) is already defined for (Y < 1 + 6, then g(1+ 6 ) is an extension of all the g(a)’s which satisfies an additional requirement. In Lemma 2.6 this additional requirement is: g ( l + 6) decides ( P ( C ~ ( ~ , ) ,i.e. g(1+ 6 ) either forces this formula or its negation. In Lemma 2.7 the additional requirement is: g(1+ 6 ) forces ( E W ) , ~ ~ ( C ~if( there ~ ) , Ware ) conditions which have this property and extend all the g(a)’s; otherwise g(l + 6) should force (Ew)Mcp(cf(E),w)To explain the notation previously used, we note that g(l+[) is constructed in two stages: first, we construct h ( 6 ) which is an extension of all the g(a)’s, a < 1 + 6 and then g ( l + 6 ) is selected from among such extensions of h ( 5 ) as satisfy the additional requirements. The first fact is expressed by the formula h(6)C W(g 1 (1 + 6 ) ) and the second by the formula g(1+ [ ) E Z ( f ( ( ) , h ( ( ) ) In . case of Lemma 2.7 we construct still one additional function k such that if g(1+ 6 ) ( E W ) M ~ ( C ~ ( Cthen ),W) k ( 6 ) is an element of VMsatisfying g(1+ 6 ) I t ( P ( C ~ ~ ~ , , C ~ ( ~ , ) . Once we have the functions g and k we can take as p any condition which extends all the g ( l ) ’ s , 6 < p , and as n the set rg ( k ) . The existence

-

+

MODELS OF THE GODEL-BERNAYS

AXIOMS

331

of p is secured by assumption (A). In case of Lemma 2.6 we see immediately that p decides cp(c,) for all x in m because each x can be represented as f(5) and p is an extension of g(1+[) which decides c p ( ~ ~ ( ~ )Hence ). p C Q. In case of Lemma 2.7 we see from the definitions of g ( 1 + 5 ) and k ( 5 ) that if p IF ( E w ) ~ ~ ( c , ,then w ) ,p 1 1p(c,,c,) for a z in n. Hence p ER. The essential point is that functions g and k are elements of V,; otherwise we can neither claim that nCV, nor that assumption (A) is applicable for obtaining p . In order to obtain g and k in V,, we cannot proceed in a simple-minded way and for instance define g as any extension of qo which decides cp(cfo,).The reason why this procedure is faulty, follows: the extensions of the g ( a ) ’ s , a < 1 + 6, do not form, in general, a set which belongs to V,; rather they form a “class”, i.e. a definable subset of V,. Thus we cannot use the set-form of the axiom of choice to select a particular extension. Yet we have only this form of the axiom at our disposal if we want to obtain in the end a function which belongs to V,. To overcome this difficulty we consider not all the extensions of the g ( a ) ’ s ,but only those which possibly have a smail rank. These extensions form a set W(g r ( 1 + 5)) which is an element of V,. Also we select g(1+ 5) not from among all the conditions which satisfy the additional requirements because this would involve a choice from a “class”, but from among those conditions which have possibly small ranks and which therefore form a set which belongs to V,. Also k ( 6 ) and h ( 5 ) are selected from sets S(f((),g(l+ 6)) or W(g (1 + 6)) which both belong to V,. In this way we can obtain the required functions by applying the set-form of the axiom of choice which, according to our assumption, is valid in M and so yields functions which belong to V,. Let us note that it is an open question whether Lemmas 2.6 and 2.7 remain valid if we replace the assumption M GBC by the weaker assumption M GB. From Lemmas 2.2 and 2.7 we obtain the following theorem which allows us to construct models of GB:

r

t=

+

THEOREM2.1. If M is a denumerable transitive model of GBC, P, R EDef, and R is a partial ordering of P such that P satisfies (A), then Def,(G) /=GBC for every set G which is generic in P over M. Moreover, V0,, ( G , = V, i.e. Def, (G) is a C-extension of M. PROOF. If x C y E Def, (GI, then y C VMand hence x c VM.Conversely, if x € VM, then there are y €Def, ( G ) such that x c y . Hence, the last

equation stated in the theorem is proved. It follows in particular that the set-form of the axiom of choice is valid in Def, (G). In view of Lemma 2.2 it remains for us to verify the validity of the axiom of substitution.

332

ANDRZEJ MOSTOWSKI

Thus, let m C VMand XEDef, (G) and assume that X is a function. Let cp be a predicative formula with two free variables such that for all u, v in VM ( u , v > € X= (M,G) k 40(cu,c,). In view of Lemma 2.7 there is n , C V, such that whenever u C m and there is y in VMsatisfying (M,G) q(cu,cr),then there is a y in n , satisfying the same formula. In view of our assumption y is determined uniquely by u. Hence, all the values which the function X takes for arguments in m belong to n,. Applying Lemma 2.6 we obtain a set n t V, whose elements are exactly these values which proves the theorem.

+

3. A finite tree of C-extensions

Let M GBC be a transitive denumerable model and N an integer. We consider subsets S o , Si,.. .,S k - i , To, TI,. . ., TI-i

of (0, 1,. , . , N - 1) satisfying the conditions:

l T h 1 3 2 , T h - S , # O for j < k ,

h
LEMMA3.1. There are N transitive denumerable C-extensions M, of M such that M, GBC for i < N with the following properties :

+

(* 1

for each j < k there is a transitive denumerable model + M i k GBC which is a C-extension of all the models M, with iCS,;

(**)

for no h < 1 and no transitive model Mf'kGBC, M " is a C-extension of all the models M, with iCTh.

PROOF. Let On, = On n M, P = { 2 * x Nt M : [Con,),

where N

,..., N

= (0, 1

- l}.

We call elements of P conditions and order them by inverse inclusion: p G q = p > q . F o r p i n P weputdom(p)=Dom(Dom(p));thusdomp is the ordinal [ such that p E25xN.For each non-void set X N and each p in P we put p [XI = p (dom ( p ) X X ) and denote by P [ X ]the set of all p [ X ]where p C P . For each O f X r N and p C P [ X ] we put

r

6 = {(cu,i>Cdom(p)x X : p ( ( a , i ) )= 1); and G C P [ X I ,then & denotes the set U{6 : p C G}. Let 0, be a

if X N sequence of all dense subsets of P which are definable in M. Similarly

MODELS OF THE GODEL-BERNAYS

AXIOMS

333

D, [XI is a sequence of all dense subsets of P [XI which are definable in M , the ordering of P [ X ] being also the relation of inverse inclusion. If p S q ED. then we say that D,, covers p . To simplify formulas we assume once and for all that the letter i with or without subscripts denotes an integer s N , and the letters j and h denote integers less than k and I respectively. Let {a,} be a sequence (without repetitions) consisting of all the elements of On,. We construct a sequence p , of elements of P such that p n for each n and a function p : w --z w such that the following conditions are satisfied: (1)

(2) (3) (4)

D n [ { i } ]covers pn[{i}3for each i; 0, [Sj]covers p n[ S , ] for each j ; am < p(rn)< p(m + 1) for each r n ; r l Dom ( f i n [{ill) = {ap(o), .. . , a,oz-l)l. i C Th

Before proving the existence of the sequences p , and p ( n ) we show that lemma 3.1 can be derived from (1)-(4). Let Gi = {x E P [{i}l: (En)(x 2 p n [{i}l)}, H , ~ = { EP[Sj]: x ( E ~ ) (>xp n [ S , ] ) } . In view of (1) and (2) these sets are generic respectively in P [ { i } ]or P [ S j ] over M. By Theorem 2.1, the families Def, (Gi) and Def, (Hi) are transitive denumerable models of GBC and are C-extensions of M. Let Mi = Def, (G,), M i = Def, ( H j ) . We show that M i is a C-extension of Mi whenever i E Si. To prove this, it is sufficient to show that Gi EDef, (Hi) whenever i C Sj and this follows from the equivalence x E Gi = ( E y ){(YE H,1 &L [x = Y 1 (dom (y x { i } ) l } .

To prove it we note that each x E Gi is obtained from a function pn [ { i } ] by restricting its arguments to a x {i}, where a is an ordinal s dom (p"). If we restrict pn to a x Si, we obtain a function y EHi such that x = y (dom ( y ) x {i}). Similarly restricting the arguments of a function y EHj to dom ( y ) X {i}, we obtain a function x in Gi. Now we prove (**). Let us assume that M','kGBC and M" is a transitive C-extension of M ifor each i E T,. It follows that Gi E M " ; hence, if we abbreviate nicTh Dom (Gi) by X we obtain XCMr'.Each Gi consists of pairs ( a $ )such that x ( ( a , i ) )= 1 for some x EGi. Hence

r

(4)EGi

(En)bn[{i}l((a,i))

=

(En)((ai)Efin[{i}l).

334

ANDRZEJ MOSTOWSKI

It follows that a CDom (Gi) = ( E n ) a CDom (Ij,,[{i}]), a CX= (i)Th(En)(a CDom I j n [{i}]).

If a satisfies this condition then for each i C T h there is an n = n, such that a CDom (fin [{i}]). Selecting the largest of the n, and denoting it with n we obtain (in view of the inclusions Ijn [{i}] 2 f i n , [{i}]) the result a C n,cTh Dom (9"[{i}]). Conversely, if a belongs to this intersection, then for each i C Th.Thus it obviously belongs to Dom (Gi) X

=U n

n Dom ( f i n [{i)l>= U

t€T,

..

ayp(l), . ,a q ( n - l , }

c

= {a,(,):i w } .

Since X C M" and the theorem on inductive definitions is valid in M", we infer that there is a function f in M" with domain w such that f(0) = a,(o), f ( k + 1) = min {tC X : 5 > f(k)}. Hence f(k) = a,(!+ Since a,(,,)> an,we obtain the result ( E k ) , ( f ( k )> 5) which clearly contradicts the assumption MkGGBC. Thus, (**) is proved. We now indicate the construction of sequences {p,,}, {p(n)}. We start with the void function pa and assume that p,,, satisfying (1)-(4), has already been constructed. We first extend pn[{O}]to a condition ijoCDn+J{O}]and add to pn all the pairs ((S,O),E) which belong to ijo- pn as well as pairs (([,i),O) for i # 0, 5 Edom (Go) - dom ( p " ) . The resulting condition pan has the properties:

(c)on,

PO"

ss pn,

pan

[{O}I = qoEDn+l[{O}I

n Dom (fion[{i)l) = {a,(O),. ..,a,
lCTh

The first two properties are obvious. To prove the third we note that if a CDom (Ijon[{i}])then pon((a,i))= 1 and this is possible only if either a CDom (fin[{i}]) or i = 0. Since I T h I a 2, the desired equation follows. In the next step we extend pan. We start by selecting a ijl S ponisuch that ijlCDn+l[{l}]and then extend pOnto pln by adding to panu Ljl all the pairs ((t,i),O) where i # 1 and dom (po,) G 5 < dom (ijl). Again, we have

The condition p l n is extended next to pZnby adding to pIna condition

q26 pln[{2}1 which belongs to 0,,+,[{2}]as well as pairs ((&i),O)where i f 2 and dom (pin) S 5 < dom (q2).Continuing in this way we finally obtain a condition p N - l , n= qn satisfying the formulas:

MODELS OF T H E GODEL-BERNAYS AXIOMS

qn

pn,

135

qn[{ill is covered by Dn+l[{i)l,

n Dom (6,[{ill) = {aq(o), aq(l), . . . ,a q ( n - l ) l .

iCTh

In the next k-steps we extend qn so as to obtain conditions qJnsuch that Dn+,[SJ] covers qJn[S,]for each j < k. We start by extending qn[So]to Fa in Dn+,[S,],then add Fn to qn and also add to qn all the pairs ((t7i),0)where i f s o and dom(q,)
r,[SJ1is covered by Dn+,[SJ] for each j < k.

3 rn,

We show that

r l Dom (?n [{ill) = {aq(o), a q ~ l.). , a . q(,-~)}.

lETh

Assume that a belongs to the left-hand side, i.e. r,,((a,i))= 1 for each i E Th.If a 3 dom ( p " ) ,then there exists a j < k such that q,,,((a,i))= 1 and dom ( q l - l , ns) (Y < dom ( q J n(in ) case j = 0 we replace ql-I by qn).This equation is possible only if i E S,. Hence if a belongs to the left-hand side of the above equation, then for each i in Th there is a j , such that i f S,, and dom (qlt-l,n) =sa < dom (q,,,,). From these inequalities it follows that j , is independent of i and can be denoted by j . But then i C SJ for each i in Th which contradicts our assumption that 1 ThI 3 2 and Th - S, # 0. In the last step of our construction we define p ( n ) . Let Pn = dom (r,,). Hence Pn 3 (Y~(,-~). Let p ( n ) be the least integer such that ap(,,)> Pn and aV(") > an.We extend r,, to pn+lby adding all the pairs ((&i),O), where i < N , Pn s < aq(n) and also the pairs ((c~~(,,),i),l)~ where i < N. Formulas (1)-(4) are then clearly satisfied with n replaced by n + 1. Lemma 3.1 is thus proved. 4. Models for the Godel-Bernays set theory In order to express the main results we now describe some special trees. Let N C w, and let the family of all non-void subsets of (0, 1,. . . , N - l} be partitioned into two families A u B such that (1) A contains with any set X all the non-void subsets of X , and B contains with any set Y all the non-void super-sets of Y ; ( 2 ) if XEA and Y € B ,then Y - X f O ; (3) if YCB, then ) Y l 3 2 ; (4) U A ={O, 1 7 . . . , N - 1).

336

ANDRZEJ MOSTOWSKI

We denote by So, S1,.. . , Sk-lthe maximal elements of A with more than 1 element. Let A,(A,B) be a tree with N + k + 1 nodes: {W,

0, I,. .., N

-

1, g o , . . ., ak-1).

The initial node w is connected with the N nodes 0, 1,. . . ,N - 1 which are said to lie below w : i 6 0. The node aj is connected with the nodes i such that i C Sj and Iies below these nodes (i.e. uj6 i iff i C S j ) . Moreover, we assume that w 3 uifor each j . No other pairs of nodes are connected. Nodes which lie below no other nodes are called the terminal nodes of AN(A,B). We also consider infinite trees of height w1 which arise in the following way: there is just one node w of height 0. If nodes of height < 5 and edges connecting them are already defined then we correlate a tree Ag = ANg(AR,Bg) to each branch g consisting of nodes already defined and place this tree below all nodes on the branch g. Thus, the initial node wg of Ag has height 5 and nodes of A8 lying below w, have heights 6 + 1 or 5 + 2. Trees of this kind are called A,,-trees.

4.1. For every denumerable transitive model M GBC and THEOREM every tree h = AN(A,13) with the initial node w there is a mapping 4 of nodes of A into a family of transitive denumerable C-extensions of M satisfying the following conditions : (1) 4 ( w ) = M ; (2) + ( w ) F G B C for each node w ; ( 3 ) if w 1=z w z , then +(wl)> +(wz); (4) 4 (wI ) and C#J ( w2)have no joint C-extension M ' G B C unless there is a w such that w s w 1 and w =z w 2 .

+

THEOREM4.2. For every M a s in Theorem 4.1 and every A,,-tree A there is a mapping 4 of nodes of A into a family of transitive denumerable C-extensions of M satisfying the same conditions (1)-(4) as in Theorem

4.1. Theorem 4.2 results immediately from Theorem 4.1 and Lemma 2.1. To prove Theorem 4.1 we denote by So,. .., the maximal elements of A, and by To,... , T,-l, the minimal elements of B, construct models Mo, MI,.. . ,MN-,,M & ... ,M;-, as in Lemma 3.1 and put 4(0) = M , 4 ( i ) = Mi, +(q)= M:. Conditions (l), (2), (3) of Theorem 4.1 are obviously satisfied. To prove (4)we note that if w l= i l , w 2= iz and there is a w such that w s w l ,w < w2 then i l , i,CSi for some j and thus a common extension +(w) exists. Otherwise i , , iz must belong to a set Y in B and thus il, iz is one of the Th and therefore no common extension of 4(wl), exists. Now consider the case when one of the nodes w l ,w 2is of C#J(w,)

337

MODELS OF THE GODELBERNAYS AXIOMS

the form ui,e.g. w I = q.If w z = i and w I non s w z then i f Si and therefore Si u {i} contains one of the sets Th.Thus no common extension of M i and M iexists because otherwise there would exist an extension of all the Mi,, i l € Th.Similarly if w z = ui, there cannot be a joint extension of Miand Mi, because sju sir contains one of the sets Th. EXAMPLE. Let N

=6

So = {(),I},

and A consist of the four sets

SI= {1,2,3}, Sz = {2,3,4}, S , = (5)

and of their non-void subsets. The family A has 14 sets. Let B consist of the remaining 49 non-void subsets of 0, 1 , 2 , 3 , 4 , 5 . The tree A,(A,B) has the following form: w

Theorems 4.1 and 4.2 show how complicated the family of transitive C-extensions M GBC of a given transitive denumerable model M of GBC is. From Theorem 4.2, we obtain

COROLLARY4.1. Given a transitive denumerable model M exists 2"' transitive C-extensions M bGBC of power wl.

+ GBC, there

PROOF. To prove this we consider the full binary tree of height w Iand a function C#J as described in Theorem 4.2 by Lemma 2.1 the union U C#J(w) taken over nodes w lying on a branch g gives us a C-extension M, of M of power w 1 such that M, F G B C and for different branches g , , g,, we obtain different models. Observing that models M,,, M, corresponding to two different branches do not have a common transitive C-extension, we obtain furthermore COROLLARY 4.2. There are at least 29 maximal-transitive models M +GBC with a given denumerable VM. Under the assumption of the continuum hypothesis, this estimate of the number of maximal-transitive models with a given denumerable VM is sharp. Without this assumption, no such sharp estimate exists but it seems probable that Martin's axiom implies that their number is 2*"1).

338

ANDRZEJ MOSTOWSKI

5. Models for the predicative arithmetic of second order

A Godel-Bernays-type extension of a theory is possible not only for the theory ZF but for arbitrary first-order theories. Let us consider briefly the Godel-Bernays-type extension of Peano’s arithmetic 9.A detailed description of 9 can be found, e.g. in KLEENE[1952], p. 82. We extend 9 by adding to it a new sort of variable X , Y, Z,. .. called set variables and a binary predicate E. Formulas with no bound-set variables are called predicative. As axioms of the extended theory we take axioms of Peano’s system (Kleene’s axioms 14-21) as well as the following ones: + [(x E X) = (y E Y ) l , ( X = Y )= (x)[(x E X ) = (X E Y ) ] , ( E X ) ( x ) [ ( xE X ) = c p ] (set existence scheme), (0 E X ) & (x)[x E X + (x’ E X)] + (x EX).

(x = Y )

(All (A2) (A3) (A4)

In the set-existence scheme, cp can be any predicative formula in which X does not occur. The resulting system will be called predicative arithmetic of second order and denoted by Apr.It is possible to replace the predicative set-existence scheme by a finite number of axioms as it is done in the case of set theory. Models of A,, can be assumed to have the form (0,S, 0, I , +, C ) where (0,0, ’, +, *) is a model of Peano arithmetic and S C P ( 0 ) . Moreover, 0 can be assumed to have as its initial segment the set 0, of ordinary integers. The operations I , +, * restricted to 0, coincide with the usual arithmetical operations and 0 is the integer zero. If 0 = 0, then the model (0,S, 0, ’, +, *, C ) is an w-model. If Mi = (0,Si, O , ’ , +, *, C ) for i = l , 2 and S , C S2,then we say that M 2 is a C-extension of MI. Later, we shall abbreviate our notation for models and write (0,s) instead of (a,S, 0, *,

I ,

+,

-9

C).

LEMMA5.1 Lemma 2.1 (mutatis mutandis) holds for models of Apr. We define the family Def, and Def, (X) similarly as on p. 326. If Apr. Similarly, if M = (0,s)k A,,, then (n,Def,) Apr.Instead of Lemma 2.2, we have the following result: If (0,s) A,, and X C IR, then all the axioms of A,, with the possible exception of (A4) hold in (O,DefM(X)). The notion of a generic set is defined similarly as on p. 4 (cf. SIMPSON [ m ] ) .We can prove easily (cf. SIMPSON [a])that if (In,M) A,, u M is denumerable and P C Def, is a set partially ordered by a relation R C DefM then generic sets G C P exist. Moreover, (Cl,DefM(G)) ‘pA,. Our main results are as follows:

nk 9 , then (n,Def,)

+

+

+

+

MODELS O F THE GODEL-BERNAYS AXIOMS

339

THEOREM5.1. Given an integer N , a tree A=A,(A,B) and a model M = (R,S) A,, such that 0 u S = o and, R # Ro, then there exists a mapping C$ of the nodes o f A into denumerable C-extensions of M such that (1) the initial node of A is mapped onte M, ( 2 ) if w I , w z are nodes of A, then C $ ( w l ) > & ( w 2 )is equivalent to w1 c w,; ( 3 ) if w I , wz are nodes of A, then C$(w,),C$(wz)have a joint C-extension which is a model of A,, i f f there exists a w such that w =sw I and w S w2.

+

THEOREM5.2. tree.

Theorem 5.1 holds if one replaces A,(A,B) by a Am,-

These theorems are proved essentially as Theorems’4.1 and 4.2. The crucial lemma corresponding to Lemma 3.1 is proved by considering conditions which are finite two-valued functions with domains of the form {x : x =sn } x N , where n E R and s is the “less-than’’ relation of the model R. The word “finite” is meant here in the sense of R and the whole function has to be coded by a single element of 0. We fix an increasing sequence {a”}, n €Ro of elements of R which is cofinal with R. This sequence does not belong to the model. We arrange the construction of generic sets Gi,i < N , in such a way that the intersections ni,,,Dom(Gi) be equal to a set X consisting of infinitely many an’s. This is possible because for each condition p only finitely many an’scan belong to dom(p). We show that there is no model (R,S*) of A,, such that S * > U {Si: i E Th}.Otherwise, the set X would be an element of S * . Using the theorem on inductive definitions we could then find in S * a functional set f whose domain is a segment of R such that f(0) = ao, f ( x + 1) = the least element of X greater than f (x). Thus, the domain of f would be the set of standard integers which is a contradiction because this set belongs to no model (a$*) of Apr. It is rather remarkable that we have here a complete analogy between models of GBC and models of A,, with non-standard integers. For models of A,, with standard integers Theorems 5.1 and 5.2 are false because any two such models have a joint C-extension. References FELGNER,U. (1971) Comparison of the axioms of local and universal choice. Fundamenta Mathematicae 71, 43-62. GODEL,K. (1940) The consistency of the axiom of choice and of the generalized continuum hypothesis with the axioms of set theory. Annals of Math. Studies. Vol. 3 . Princeton University Press, Princeton, N.J.,66 pp. (7th printing (1966))

340

ANDRZEJ MOSTOWSKI

KLEENE,S. C. (1952) Introduction to metamathematics. North-Holland, Amsterdam, 550 pp. (2nd printing (1957).) SIMPSON,S. G. (m) Forcing and models for arithmetic. Proceedings of the American Mathematical Society. (To appear.) VOPENKA,P. and HAJEK,P. (1972) The Theory of Semisets. North-Holland, Amsterdam, 332 PP.

SETS AND CLASSES; On the work by Paul Bernays @ North-Holland Publishing Company (1976) pp. 341-352.

BIBLIOGRAPHY ACKERMANN,W. (1937) Die Widerspruchsfreiheit der allgemeinen Mengenlehre. Math. Annalen 114, 305-315. ACKERMANN, W. (1956) Zur Axiomatik der Mengenlehre. Math. Annalen 131, 336-345. ACZEL,P. and RICHTER, W. (1970) Inductive definitions and analogues of large cardinals. In Conference in Math. Logic, London '70,W. Hodges (Ed.), pp. 1-9. Springer Lecture Notes in Mathematics, Vol. 255. Springer, Berlin. 351 pp. ADDISON,J. W., HENKIN,L., and TARSKI, A. (Eds.) (1965) The theory of models. Proceedings of the 1963 international Symposium at Berkeley. North-Holland, Amsterdam. 494 pp. (2nd printing (1972), 509 pp.) ASSER,G. (1957) Theorie der logischen Auswahlfunktionen. Zeitschr. f. Math. Logik 3, 30-68. BAR-HILLEL,Y., POZNANSKI, E. I. J., RABIN,M. O., and ROBINSON,A. (Eds.) (1961) Essays on the foundations of mathematics. (Dedicated to A. A. Fraenkel.) Magnes Press, Jerusalem. 351 pp. BARWISE,J. (1969) Infinitary logic and admissible sets. J.S.L . 34,226-252. BARWISE,J. (1971) Infinitary methods in the model theory of set theory, pp. 53-56. In GANDYand YATES(1971). BELL, J. L. and SLOMSON,A. (1969) Models and ultraproducts: An introduction. North-Holland, Amsterdam, 322 pp. (1 st revised reprint ( 197 1) .) BERNAYS,P. (1937-1954) A system of axiomatic set theory; I-VII. J.S.L. I: 2,65-77 (1937); 11: 6, 1-17 (1941); 111: 7,65-89 (1942); IV: 7, 133-145 (1942); V: 8, 89-106 (1943); VI: 13, 65-79 (1948); VII: 19, 81-96 (1954). This volume. BERNAYS,P. (1958) Axiomatic set theory (with a historical introduction by A. A. Fraenkel). North-Holland, Amsterdam. 226 pp. (2nd ed. (1%8), 235 PP.). 34 1

342

BIBLIOGRAPHY

BERNAYS,P. (1961) Zur Frage der Unendlichkeitsschemata in der axiomatischen Mengenlehre. In BAR-HILLELet al. (1961), pp. 3-49. This volume (English translation-revised version). BOFFA,M. (1968) Les ensembles extraordinaire. Bull. Soc. Math. Belgique 20, 3-15. BOFFA,M. (1968a) Elimination de cycles d’appartenance par permutation de I’univers. C.R. Acad. Sci. Paris 266, 545-546.

BOFFA, M. (1971) Forcing and reflection. Bull. Acad. Polon. Sc. 19, 181-183. BOREL,E. (1898) Lecons sur la the‘orie des fonctions. Gauthiers Villars, Paris (1898). 2nded. (1914),260pp.; 3rd [4th] ed. (1928) [1950]. (Cf. Math. Annalen 60, 194-195 (1905), and Rev. du Mois 1, 248-250 (1906).) BOWEN,K. A. (1972) The relative consistency of some consequences of the existence of measurable cardinal numbers. Dissertationes Math. Warszawa. 63 pp. BULOFF,J. J., HOLYOKE,T. C., and HAHN,S. W. (Eds.) (1969) Foundations of mathematics. (Symposium papers commemorating the sixtieth birthday of Kurt Godel.) Springer, Berlin. 195 pp. CHANG,C. C. and KEISLER,H. J. (1973) Model theory. North-Holland, Amsterdam, 550 pp. CHUAQUI,R. (1972) Forcing for the impredicative theory of classes. J.S.L. 37, 1-18. CHURCH,A. (1927) Alternatives to Zermelo’s assumption. Trans. A.M.S. 29, 178-208. CHURCH,A. (1956) Introduction to mathematical logic-I. University Press, Princeton, N.J., 376 pp.

Princeton

COHEN,P. J. (1966) Set theory and the continuum hypothesis. Benjamin, New York, 160 pp. COHEN,P. J. (1974). Models of set theory with more real numbers than ordinals. J.S.L. 39, 579-583. DEDEKIND, R. (1888) Was sind und was sollen die Zahlen? 6th ed.: F. Vieweg & Sohn, Braunschweig (1930), 58 pp.; also in DEDEKIND (1930-1932) 111. English ed. by W. W. Beman, in: Essays on the theory of numbers by R. Dedekind. Chicago and London (1901). R. (1930-1932) Gesammelte mathematische Werke. R. Fricke, DEDEKIND, E. Noether and 0.Ore (Eds.). 3 vols. F. Vieweg & Sohn, Braunschweig.

BIBLIOGRAPHY

343

DOETS,H. C. (1969) Novak‘s result by Henkin’s method. Fund. Math. 64, 329-333. EASTON,W. B. (1964) Powers of regular cardinals. Ph.D. thesis. Princeton University. 66 pp. EASTON,W. B. (1970) Powers of regular cardinals. Ann. of Math. Logic 1, 139-178. ERDOS,P. and HAJNAL,A. (1958) On the structure of set mappings. Acta Math. Acad. Sci. Hung. 9, 111-131. ERDOS,P. and HAJNAL,A. (1962) Some remarks concerning our paper “On the structure of set mappings”. Ibid. 13, 223-226.

S. (1965) Some applications of the notions of forcing and FEFERMAN, generic sets. Fund. Math. 56, 325-345. (Summary in ADDISONet al. (1965), pp. 89-95.) FELGNER, U. (1971) Comparison of the axioms of local and universal choice. Fund. Math. 71, 43-62. FELGNER, U. (1971a) Models of ZF-set theory. Springer Lecture Notes in Mathematics, Vol. 223. Springer, Berlin. 173 pp. FELGNER,U. and JECH, Th. J. (1973) Variants of the axiom of choice in set theory with atoms. Fund. Math. 79, 79-85.

FEYS,R. (1944) Logistiek. Philosophische Biblotheek N.V., Antwerpen and Nijmegen. FINSLER,P. (1926) Uber die Grundlegung der Mengenlehre-I. Mengen und ihre Axiome. Math. Zeitschr. 25, 683-713.

Teil. Die

FIRESTONE, C. D. (1948) Review of Bernays’ article: A system of axiomatic set theory-Part VI. J.S.L. 13, 220-221. FLANNAGAN, T. B. (1973) Ph.D. thesis, London. FLANNAGAN, T. B. (1974) Set theories incorporating Hilbert’s €-symbol. Dissertationes Math. 154. Warszawa.

FLANNAGAN, T. B. (1976) A new finitary proof of a theorem of Mostowski. This volume. FRAENKEL, A. A. (1922) Zu den Grundlagen der Cantor-Zermeloschen Mengenlehre. Math. Annulen 86, 230-237. (Cf. already Jahresber. D.M.V. 30 p. 97 ital. (1921).) FRAENKEL, A. A. (1922a) Uber den Begriff “definit” und die Unabhangigkeit des Auswahlaxioms. Sitzungsberichte der Preuss.

344

BIBLIOGRAPHY

Akademie d. Wiss., Phys.-Math. Klasse, pp. 253-257. (English translation in VAN HEIJENOORD (1%7), pp. 284-289.)

FRAENKEL, A. A. (1925) Untersuchungen iiber die Grundlagen der Mengenlehre. Math. Zeitschr. 22, 250-273. FRAENKEL,A. A. (1927) Zehn Vorlesungen iiber die Grundlegung der Mengenlehre. Springer, Berlin, 182 pp. FRAENKEL, A. A. (1927a) Uber die Gleichheitsbeziehung in der Mengenlehre. J. f. Math. 157, 79-81.

FRAENKEL, A A. (1928) Einfeitung in die Mengenlehre, 3rd ed. Springer, Berlin, 424 pp. Reprinted (1964). FRAENKEL, A. A. (1937) h e r eine abgeschwachte Fassung des Auswahlaxioms. J.S.L. 2, 1-25. FRAENKEL, A. A , BAR-HILLEL,Y., LEVY,A. and DALEN,D. VAN (1973) Foundations of set theory. North-Holland, Amsterdam, 404 pp. FFUEDMAN, H. (a)Large models with countable height. J.S.L., to appear.

H. (1967) A generalization of Mahlo’s method for obtaining GAIFMAN, large cardinal numbers. Israel J. Math. 5, 188-201. GAIFMAN, H. (1968) Two results concerning extensions of models of set theory (abstract). Notices A.M.S. 15, 947 pp. GANDY,R. 0. and YATES,C. E. M. (Eds.) (1971) Logic colloquium ’69. Proceedings of the summer school and colloquium in mathematical logic, Manchester, August 1969. North-Holland, Amsterdam. 451 pp. GLOEDE,K. (1970) Reflection principles and large cardinals. Ph.D. thesis. Heidelberg. 129 pp. GLOEDE,K. (1971) Filters closed under Mahlo’s and Gaifman’s operation. In Proceedings of the Cambridge Summer School in Mathematical Logic, August 1971. pp. 495-530. A. R. D. Mathias and H. Rogers (Eds.) Springer Lecture Notes in Mathematics, Vol. 337. Springer, Berlin. 660 pp. GLOEDE,K. (1972) Ordinals with partition properties and the constructible hierarchy. Zeitschr. f. math. Logik 18, 135-164. GODEL,K. (1938) The consistency of the axiom of choice and of the generalized continuum hypothesis. Acad. U.S.A. 24, 556-567. GODEL, K. (1939) Consistency proof for the generalized continuum hypothesis. Ibid. 25, 220-224.

BIBLIOGRAPHY

345

GODEL, K. (1940) The consistency of the axiom of choice and of the generalized continuum hypothesis with the axioms of set theory. Annals of Math. Studies, Vol. 3. Princeton University Press, Princeton, N.J., 66 pp. (7th printing (1966).) GRELLING,K. (1910) Die Axiome der Arithmetik. (Dissertation, Gottingen.) GRISIN,V. N. (1972) The theory of Zermelo-Fraenkel sets with Hilbert €-terms. Math. Notes Acad. Sci. U.S.S.R. 12, 779-783. H ~ E KP., (1965) Modelle der Mengenlehre in denen Mengen gegebener Gestalt existieren. Zeitschr. f, math. Logik 11, 103-115. HARTOGS,F. (1915) Uber das Problem der Wohlordnung. Math. Annalen 76, 438443. HASENJAEGER, G. (1953) Eine Bemerkung zu Henkin’s Beweis fur die Vollstandigkeit des Pradikatenkalkiils der ersten Stufe. J.S.L. 18, 42-48. HANF, W. and S c o r r , D. (1961) Classifying inaccessible cardinals (abstract). Notices A.M.S. 8, 445. J. VAN (Ed.) (1967) From Frege to Godel-a source book in HEIJENOORT, mathematical logic, 1879-1931. Harvard University Press, Cambridge, Mass., 660 pp.

HENKIN,L. (1949) The completeness of the first-order functional calculus. J.S.L. 14, 159-166. HESSENBERG,G. (1906) Grundbegriffe der Mengenlehre. (Abh. der Friesschen Schule, N.S. [l] Heft 4.) Gottingen, 220 pp. P. (1934-1939) Grundlagen der Mathematik I HILBERT,D. and BERNAYS, (1934); I1 (1939). Springer, Berlin. 471; 498 pp. (2nd edition (1%8; 1970), 488; 575 pp.) ISBELL,J. R. (1963) Two set-theoretical theorems in categories. Fund. Math. 53, 43-49. ISBELL,J. R. and WRIGHT,F. B. (1966) Another equivalent form of the axiom of choice. Proc. A.M.S. 17, 174. JECH,Th. J. (1973) The axiom of choice. North-Holland, Amsterdam. 203 PP. JENSEN,R. B. (1967) Modelle der Mengenlehre. Springer Lecture Notes in Mathematics, Vol. 37. Springer, Berlin. 176 pp.

346

BIBLIOGRAPHY

JENSEN,R. B. (1967a) GroSe Kardinalzahlen. (Notes of lectures given at Oberwolfach (Germany).) 121 pp. JENSEN,R. B. (1972) The fine structure of the constructible hierarchy. Annals of Math. Logic, vol. 4, 229-308. JENSEN,R. B. and KARP,C. (1971) Primitive recursive set functions, pp. 143-176. In SCOTT(1971). KEISLER,H. J. and TARSKI,A. (1964) From accessible to inaccessible cardinals. Fund. Math. 53, 225-308. Corrections, ibid. (1965) 57, 119. KEISLER,H. J. and ROWBOTTOM, F. (1965) Constructible sets and weakly compact cardinals (abstract). Notices A.M.S. 12, 373-374. KELLEY,J. L. (1955) General topology. Van Nostrand, New York. 298 pp. KLEENE,S. C. (1935) A theory of positive integers in formal logic. American J. of Math. 57, pp. 153-173 and pp. 219-244 (especially the passage from theorem 15-IV to 15-V, pp. 220-221). KLEENE,S. C. (1952) Introduction to metamathematics. Amsterdam. 550 pp. (2nd printing (1957).) KONIG,J. (1905) Zum Kontinuum-Problem, Math. Annalen 60. KORSELT,A. (1911) Uber einen Beweis des Aquivalenzsatzes. Math. Annalen 70, 294-296. KREISEL,G. and LEVY,A. (1968) Reflection principles and their use for establishing the complexity of axiomatic systems. Zeitschr. f. math. Logik 14, 97-191. KRIVINE,J. L. (1971) Introduction to axiomatic set theory. Reidel, Dordrecht. 98 pp. KRUSE,A. H. (1963) A method of modelling the formalism of set theory in axiomatic set theory. J.S.L. 28, 20-34. KRUSE,A. H. (1966) Grothendieck universes and the super-complete models of Sheperdson. Compositio Math. 17, 96-101. KUHNRICH, M. (1966) Uber den Begriff des Universums. Zeitschr. f. math. Logik 12, 37-50. KUNEN,K. (1968) Inaccessibility properties of cardinals. Doctoral Dissertation. Stanford. 117 pp. KUNEN,K. (1972) The Hanf number of second-order logic. J.S.L. 37, 588-594.

BIBLIOGRAPHY

347

KURATA,R. (1964) On the existence of a proper complete model of set theory. Comm. Math. Univ. Sancti PauQ 13, 35-43. KURATOWSKI, K. (1921) Sur la notion d’ordre dans la thkorie des ensembles. Fund. Math. 2 , 161-171. LEISENRING, A. C. (1969) Mathematical Logic and Hilbert ’s €-symbol. Gordon and Breach, New York, 142 pp. LEVY, A. (1958) Contributions to the metamathematics of set theory. Ph.D. thesis. Jerusalem. LEVY,A. (1959) On Ackermann’s set theory. J.S.L. 24, 154-166. LEVY,A. (1960) Axiom schemata of strong infinity in axiomatic set theory. Pacific J. Math. 10, 223-238. LEVY,A. (1960a) Principles of reflection in axiomatic set theory. Fund. Math. 49, 1-10. LEVY, A. (1964) The interdependence of certain consequences of the axiom of choice. Fund. Math. 54, 135-157. LEVY,A. (1965) A hierarchy of formulas in set theory. Memoirs A.M.S. 57, 76 pp. LEVY,A. (1968) On von Neumann’s axiom systems for set theory. Am. Math. Monthly 75, 762-763. LEVY,A. (1971) The size of the indescribable cardinals. In SCOTT(1971), pp. 205-218.

LEVY,A. and VAUGHT,R. L. (1961) Principles of partial reflection in the set theories of Zermelo and Ackermann. PacificJ. Math. 11,1045-1062. MACLANE,S . (1961) Locally small categories and the foundations of set theory. Infinitistic methods, Warszaw, pp. 25-43. MAHLO,P. (191 1) Uber lineare transfinite Mengen. Berichte uber die Verhandlungen der Koniglich Sachsischen Akademie der Wissenschaften zu Leipzig. Math.-Phys. Klasse, 63, 187-225. MAHLO,P. (1912-1913) Zur Theory und Anwendung der p,-Zahlen, ibid., I: 64, 108-112 (1912); 11: 65, 268-282 (1913). MAREK,W. (1973) On the metamathematics of impredicative set theory. Dissertationes Math. 98, Warszaw. MAREK,W. and ZBIERSKI,P. (1972) Axioms of choice in impredicative set theory. Bull. Acad. Polon. Sci. 20, 255-258.

348

BIBLIOGRAPHY

MARKOV,A. A. (1948) On the dependence of axiom B6 on the other axioms of the Bernays-Godel system. Izvkstiyd Akadkmii Nauk. SSSR, ser. mat. Vol. 12, 569-570. MENDELSON,E. (1956) The independence of a weak axiom of choice. J.S.L. 21, 350-366. MENDELSON, E. (1964) Introduction to mathematicaf logic. Van Nostrand, New York, 300pp. MONTAGUE,R. (1961) Semantical closure and non-finite axiomatizability-I. Infinitistic methods. Warszaw, pp. 45-69. MONTAGUE,R. and VAUGHT,R. L. (1959) Natural models of set theories. Fund. Math. 47, 219-242. MORRIS, D. B. (1970) Adding total indiscernibles to models of set theory. Dissertation, Wisconsin. MORSE,A. P. (1965) A theory ofsets. Academic Press, New York, 130pp. MOSCHOVAKIS, Y. N. (1971) Predicative classes, pp. 247-264. In SCOTT (1971). MOSTOWSKI, A. (1939) Uber die Unabhangigkeit des Wohlordnungssatzes vom Ordnungsprinzip. Fund. Math. 32, 201-252.

MOSTOWSKI,A. (1949) An undecidable arithmetical statement. Fund. Math. 36, 143-164. MOSTOWSKI, A. (195 1) Some impredicative definitions in the axiomatic set theory. Fund. Math. 37,111-124. (Corrections, ibid. (1952) 38,238.) MOSTOWSKI,A. (1969) Constructible sets with applications. NorthHolland, Amsterdam. 269 pp. MYHILL,J. R. (1952) The hypothesis that all classes are nameable. Acad. U.S.A. 38, 979-981. MYHILL,J. R. (1963) Remark on a system of Bernays. J.S.L. 28,75-76. NEUMANN,J. VON (1925) Eine Axiomatisierung der Mengenlehre. J. f. Math. 154, 219-240. Corrections, ibid. 155, 128 (1926). Also in VON NEUMANN (1961) pp. 34-56. (English translation in VAN HEIJENOORT (1967) pp. 393-413.) NEUMANN, J. VON (1928) Die Axiomatisierung der Mengenlehre. Math. (1961) pp. 339-422. Zeitschr. 27, 669-752. Also in VON NEUMANN

BIBLIOGRAPHY

349

NEUMANN, J. VON (1928a) Uber die Definition durch transfinite Induktion und verwandte Fragen der allgemeinen Mengenlehre. Math. Annalen 99,373-391. Also in VONNEUMANN(1961) pp. 320-338. (Cf. FRAENKEL (1928) pp. 392-393.) NEUMANN,J. VON (1929) Uber eine Widerspruchsfreiheitsfrage in der axiomatischen Mengenlehre. J. f. Math. 160, 227-241; also in VON NEUMANN(1961) pp. 494-508. NEUMANN,J. VON (1929-1930) Allgemeine Eigenwerttheorie Hermitescher Funktionaloperatoren. Math. Annalen 102, 49-13 1, in particular Kap. I and Anhang I therein.

J. VON (1961) Collected works. Vol. I. Pergamon, New York. NEUMANN, 654 pp. NOVAK,I. L. (1948) A construction for models of consistent systems. Ph.D. thesis. Harvard. NOVAK,I. L. (1951) A construction for models of consistent systems. Fund. Math. 37, 87-110. OBERSCHELP,A. (1964) Eigentliche Klassen als Urelemente in der Mengenlehre. Math. Annalen 157, 234-260. PETER,R.(1941) Review Of T E I C H M U L L E R (J.S.L. ~ ~ ~ ~6(1941),65-66. ),

QUINE,W. V. (1937) New foundations for mathematical logic. Am. Math. Monthly 44,7680. (A revised and expanded version is in QUINE(l953), pp. 80-101). QUINE, W. V. (1951) Mathematical logic (revised edition). Harvard University Press, Cambridge, Mass., 346 pp. (First edition (1940).) QUINE,W. V. (1953) From a logical point of view. Harvard University Press, Cambridge, Mass., 184 pp. QUINE,W. V. (1963) Set theory and its logic. Belknap Press, Cambridge, Mass., 359 pp. (Revised ed. (1969), 361 pp.) REINHARDT, W. N. (1967) Topics in the metamathematics of set theory. Doctoral Dissertation, 85 pp. REINHARDT, W. N. (1970) Ackermann's set theory equals ZF. Ann. Math. Logic. 2 , 189-249. REINHARDT, W. N. and SILVER,J. (1965) On some problems of Erdos and Hajnal (abstract). Notices A.M.S. 12, 723.

350

BIBLIOGRAPHY

ROBINSON, R. M. (1937) The theory of classes-A modification of von Neumann’s system. J.S.L. 2, 69-72. ROBINSON,R. M. (1945) On finite sequences of classes. J.S.L. 10, 125-126. ROSSER,J. B. and WANG, H. (1950) Non-standard models for formal logics. J.S.L. 15, 113-129. (Errata, ibid. p. iv.) RUBIN,H. and RUBIN,J. E. (1963) Equivalents o f the axiom o f choice. North-Holland, Amsterdam, 134 pp. (2nd ed. (1970).) RUSSELL,B. (1906) On some difficulties in the theory of transfinite numbers and order types. Proc. o f t h e London Math. SOC.4 (2), 29-53. SACKS,G. E. (1972) Saturated model theory. Benjamin, New York, 335 pp. SCHMERL, J. H. (1972) An elementary sentence which has ordered models. J.S.L. 37, 521-530. SCHMERL,J. H. and SHELAH,S. (1972) On power-like models for hyperinaccessible cardinals. J.S.L. 37, 531-537. SCHUTTE,K. (1950) Schlussweisen-Kalkiile der Pradikatenlogik. Math. Annalen 122, 47-65. SCOTT, D. (1955) Definitions by abstraction in axiomatic set theory (abstract). Bull. A.M.S. 61, 442. SCOTT,D. (1961) Measurable cardinals and constructible sets. Bull. Acad. Polon. Sc. 9, 521-524. SCOTT,D. (Ed.) (197 1) Axiomatic set theory. Proceedings of symposia in pure math. 13, Am. Math. SOC., Providence, R.I. SHEPHERDSON, J. C. (1951-1953) Inner models for set theory. J.S.L. 16, 161-190 (1951); 17, 225-237 (1952); 18, 145-167 (1953). SHOENFIELD, J. R. (1954) A relative consistency proof. J.S.L. 19,21-28. SHOENFIELD, J. R. (1967) Mathematical logic. Addison-Wesley, Reading, Mass. 344 pp. SIERPINSKI, W. (1921) Une remarque sur la notion de l’ordre. Fund. Math. 2, 199-200. SILVER,J. (1966) Some applications of model theory in set theory. Doctoral Dissertation, Berkeley, 110 pp. Published (with the deletion of 04) in SILVER(1971). SILVER,J. (1971) Some applications of model theory in set theory. Ann. of Math. Logic 3, 45-1 10.

BIBLIOGRAPHY

35 1

SIMPSON, S. G. (03) Forcing and models for arithmetic. Proceedings of the A . M S . (To appear.) SKOLEM, TH. (1923) Einige Bemerkungen zur axiomatischen Begrundung der Mengenlehre. Wiss. Vortrage gehalten auf dem 5. Kongress der Skandinav. Mathematiker in Helsingfors, 1922, pp. 217-232. (English translation in VAN HEIJENOORT (1967), pp. 290-301.) SKOLEM,TH. (1929) Uber einige Grundlagenfragen der Mathematik. Skrifter utgit av det Norske Vid.-Akad. i Oslo I (4), 1-49. SOLOVAY, R. M. (1966) On the consistency of Takeuti's TT (abstract). J.S.L. 31, 691. SPECKER,E. (1952) Habilitationsschrift. SPECKER,E. (1957) Zur Axiomatik der Mengenlehre (Fundierungs- und Auxwahlaxiom). Zeitschr. f. math. Logik 3, 173-210. STEGMULLER, W. (1962) Eine Axiomatisierung der Mengenlehre beruhend auf den Systemem von Bernays und Quine. In Kasbauer et al. (Eds.) Logik und Logikkalkiil, pp. 57-103. K. Alber, Freiburg. STENIUS, E. (1952) Das Interpretationsproblem der formalisierten Zahlentheorie und ihre formale Widerspruchsfreiheit. Acta Academiae Aboensis (Math. et Phys.) 18 (3), Abo Akademi, Abo, 102 pp. TAKEUTI,G. (1961) Axioms of infinity of set theory. J. Math. SOC.Japan 13, 220-233. TAKEUTI,G. (1965) On the axiom of constructibility. Proceedings of Symposia of Logic, Computability, and Automata at Rome. Mimeographed Notes, New York. G. (1969) The universe of set theory, pp. 74-128. In BULOFFet al. TAKEUTI, (1969). TAKEUTI,G. and ZARING,W. M. (1973) Axiomatic set theory. Springer, Berlin. 238 pp. TARSKI,A. (1930) Fundamentale BegrifTe der Methodologie der deduktiven Wissenschaften I, Monatshefte fiir Mathematik und Physik 37, Satz I. 56, p. 394. TARSKI,A. (1938) Uber unerreichbare Kardinalzahlen. Fund. Math. 30, 68-89. TARSKI,A. (1948) Axiomatic and algebraic aspects of two theorems on sums of cardinals. Fund. Math. 35, 79-104.

352

BIBLIOGRAPHY

TARSKI,A. and VAUGHT,R. (1957) Arithmetical extensions of relational systems. Compositio Math. 18, 81-102. TEICHMULLER, 0. (1939) Braucht der Algebraiker das Auswahlaxiom? Deutsche Mathematik, 4, 567-577. THARP,L. (1966) Bernays’ set theory and the continuum hypothesis (abstract). Notices A.M.S. 13, 138. THARP,L. (1967) On a set theory of Bernays. J.S.L. 32, 319-321. THIELE,E. J. (1955) Ein axiomatisches System der Mengenlehre nach Zermelo und Fraenkel. Zeitschr. f. math. Log& 1, 173-195. VAUGHT,R. (1963) Indescribable cardinals (abstract). Notices A.M.S. 10, 126. VOPENKA,P. and HAJEK, P. (1972) The Theory of Semisets. NorthHolland, Amsterdam, 332 pp.

WANG,H. (1949) On Zermelo’s and von Neumann’s axioms for set theory. Acad. Sci. U.S.A. 35, 150-155. WANG,H. (1950) A formal system of logic. J.S.L. 15, 25-32. ZERMELO, E. (1904) Beweis dass jede Menge wohlgeordnet werden kann. Math. Annalen 59, 514-516. (English translation in VANHEIJENOORT (1967), pp. 139-141.) (Cf. A. Schoenflies, E. Borel, P. E. B. Jourdain (1905). Math. Annulen 60, 181-186, 194-195, 465-470.) ZERMELO, E. (1908) Neuer Beweis fur die Wohlordnung. Math. Annalen 65, 107-128. (English translation in VAN HEIJENOORT (1967), pp. 181-198.) ZERMELO, E. (1908a) Untersuchungen iiber die Grundlagen der Mengenlehre-I. Math. Annalen 65, 261-281. (English translation in VAN HEIJENOORT (1967), pp. 199-215.) ZERMELO,E. (1909) Sur les ensembles finis et le principe de I’induction complete. Acta Math. 32, 185-193. ZERMELO,E. (1909a) Uber die Grundlagen der Arithmetik. Atti del IV Congress0 Internationate del Maternatici (Roma, 6-1 1 aprile 1908). Vol. 2, pp. 8-11. ZERMELO,E. (1930) Uber Grenzzahlen und Mengenbereiche. Fund. Math. 16, 29-47. ZORN,M. (1935) A remark on methods in transfinite algebra. Bulletin of the A.M.S. 41, 667-670.

INDEX

CHAPTER 1. P. BERNAYS:A

SYSTEM OF AXIOMATIC SET THEORY

Axioms

I

(Axioms of extensionality) 3 I1 (Axioms of direct construction of sets) 4 111 (Axioms for construction of classes) 5 IV (Axiom of choice) 14 IV, (Special axiom of choice) 50 IV* (Weakened axiom of choice-class-form of the axiom of dependent choices) 52 V (Axioms concerning the representation of classes by sets) 15 V* (Axiom of replacement) 16 V** (Sum theorem) 16 VI (Axiom of infinity) 16 VI* (Generalized axiom of infinity) 33 VI,, VI, 98 VII (Restrictive axiom) 19 VII* (Set-form of the restrictive axiom) 19 Axiom of the enumerable 34 Pair class axiom 56

Theorems Cantor theorem 60 class theorem 8, 12, 13 composition lemma 11 enumerability, theorems on 35 finite classes and sets, theorems on- 29 induction, principle of complete 24 principle of generalized 54 iteration theorem 24 Konig theorem (generalized by Jourdain) 63 numeration, theorem of adapted 64 pair class theorem 77 recursion, theorem of finite 26 theorem of 54 restricted theorem on transfinite 82 strong theorem on transfinite 74

-

--

-

-

-

-

353

INDEX

Theorems (continued) replacement, theorem of 16 Schroder-Bernstein theorem 58 sum lemma 81 sum theorem 16 Teichmiiller’s principle 73 well-ordering theorem 66 Zorn maximum principle 71f

-

Definitions and special expressions (introduced at some place in the text and used in the same sense throughout) adapted 64,67, 70 iterator 25 argument 6 k-tuplet 7, normal 7 ascending sequence 53, 70 limit, limiting number 53, 70 assign 14 maximal element 72 assigned ( B is assigned to a set a by member 69 means of the class of pairs C) 60 member (first, second) 5 attributable 29 new sets 102 belongs to 2 null set 4 cardinal, -number 65 number class 52, 53 chain 71 numeration in the natural order 66 closed 71 order 65 comparable 61, 91 order, -associated with 66 complementary class 5 order, generated by an ordering 67 composition 12 order, natural- 66 converse class 5 ordering 21, 67 converse domain 6, 17, 36 ordinal 19, 22 correspond 8 pair class 35 correspondence, one-to-one 16 pair set 79 coupling 5 , 6 parameter 6 degree 7 power set 87 domain 5 , 16, 36 powers (Machtigkeiten) 59 domain, lowest 70 predicate 6 doublet 7 property (“definite Eigenschaft”) 1 enumerable 31 product (of ordinals) 80 expression, primary 6 rebracketing 7 constitutive 7 reflexive 3 field 6 represent 3 finite 24, 27, 29 residual 75, 76 function 14 schema of the k-tuplet 7 functional set 14 segment 69 identity 3, 4 sequence 89, n-sequence 69 infinite 31 set-sum 76 irreducible 70 singlet 7

-

-

-

-

-

Symbols ( a ) , (a, b ) 5 (a,b> 5 a b 26, 83 A“’ 57 A x B 35

c’

20 2 102

5 7)

i

n,n,,n2102, 104, 105 0, 105

355

INDEX

Symbols (continued) 53 o,o, 93 n 89 rI* 100 n,n, 93 88

n

* 9*

Y 96

c E

<

z

-

100

CHAPTER 2. P. BERNAYS: ON

2,33 3 59 59 28

THE PROBLEM OF SCHEMATA OF INFINITY IN

AXIOMATIC SET THEORY

Definitions and special expressions functional set 133 L-schema 124 y-schema 166 irreducible limit (= regular cardinal) 147 represented 13 1 selection-schema 163 Special symbols (which are not in common use) a ’ (= a + 1) (successor ordinal) 144 a * 131f Clf 141 Crs 147 dom, (domain) 133 dom, (co-domain = range) 133 Fu (function) 133 In 148 In* 157 Lu (regular ordinal) 147 Ma 151 Ma(m,k) 152f Mod 141 Mo& 130 Od (ordinal) 144 Pr (relation) 133 Re1 122, 136 Re1 16Of sq 145 Sqod 145 Strans 139 [a,b] (unordered pair) 125, 166 [a] (singleton) 125, 167 y (universal class) 160 r ( a ) (= P(a) = Y(a), power set) 139, 157 X ( a ) (= U a, union) 127, 168 4, $(a)= V. = R ( a ) (von Neumann’s function) s (equality between classes) 131

146

356

INDEX

CHAPTER 3. A. Lfivu: THE ROLE

OF CLASSES IN SET THEORY

Axioms (I) (11) (111) (IV) (V) (V) (VI) (VII) (VII') (VIII) (VIII,) (WE) (IX)

(extensionality) 174 (pairing) 174 (union) 174 (power set) 175 (schema of subsets) 175 (subsets) 184 (infinity) 175 (schema of replacement) 175 (replacement) 185 (local choice) 175 (global choice) 176 (global choice) 192 (schema of foundation) 175 (Ix') (foundation) 185 (IX*) 186 (X) (extensionality for classes) 179 (XI) (predicative comprehension for classes) 181 (XI 1) 187, (XI 2-8) 188f (XII) (impredicative comprehension) 197 ( a ) - ( [ )(axioms for Ackerrnann's set theory) 208-210

Theories A 207ff G 195 QM 197 ST, 201 VNB 176ff, 186f VNBC 192 VNBC, 192 ZF,ZFC 174 ZF' 200 ZF, 176 ZM 200 Definitions pure condition selector I75f

Symbols 0 175 A 182 V 182

178

P 202 R ( a ) 202 %, B r , Riel

185

357

INDEX

CHAPTER 4.

u. FELGNER:CHOICE FUNCTIONS ON SETS AND CLASSES

Axiom AC 217 Aa 243 DC, DCC" 237 E 218 GCH 227 lnj 247 N 247 NE 227 PW 247 Theories M (=QM) 245 NB (=VNB) 219 NBo 218f ZF,O 243 ZF.,ZF.O 244 ZFU 219

CHAPTER 5. T. B. FLANNAGAN: A MOSTOWSKI

NEW FINITARY PROOF OF A THEOREM OF

Axioms, special theorems and theories Al-A3 258ff Q , Q" 258 El, E2 260 Ind, Ind* 271 NBG (= VNB = NB) 271 Ql-Q4 260

CHAPTER 6. K. GLOEDE:REFLECTION PRINCIPLES Axioms AC 301 Aus' 292 AusS 281

n,'-Cornp

299

IIo2-Comp 299 Q.'-Comp 304 CR, 279 CR II," 291 Ext 280 Fund 280 FundS 284 Inf 280 Pair 280 Pow 280

AND INDESCRIBABILITY

INDEX

Axioms (continued) PR. 279 PR n," 288 PR no' 292 PR Q.' 303 Q.'-AC 301 Repl' 292 Repls 280 SAC 301 Sum 280

ThWrfeS B 292f KP 285 OM 299 Tl-T4 284

CHAPTER 7. A. MOSTOWSKI:A AXIOMS FOR SET THEORY

Theories GB (= VNB = NB) 325 GBC 325 ZF, ZFC 325 Definitions C-extension 325 DefM 326 VM 325

T5 289 VNB 299 ZF 280

REMARK ON MODELS OF THE GODEL-BERNAYS