This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!
F
satisfying
(1.6).
Next the propositional connectives: (4) If F
satisfies (1.6) then there is F . satisfying
(1.6).
Proof:
F . ( a , . . . a )= ( a , x . . . x a ) \ F . ( a 1 . . . a ) a(4) - c p l n 1 n 9 l n (5) If <|>(x1...x ) and ij; (*-.• • - x n ) each have F.,F, satisfying
(1.6)
then, letting X ( X T » - - X )H>(x,...x ) AIJJ (x-.. • » x ) there is F satisfying Proof:
(1.6).
F x (a r ..a n )=F ( ) ) (a 1 ...a n )nF^(a 1 ...a n ) =F(j)(a1...an)MF(f(a1...an)^ya1...an))
D(5)
The next two claims use F^ and F g to manipulate ordered sequences. (6) If i|;(x, ...x ) has F. satisfying (1.6) and (p (x, . . « x n + 1 ) results from \p by replacing each free occurrence is F
satisfying
of x
by x + . then there
(1.6).
Proof: If n=l then (p (x 1 ,x 2 ) «*i|; (x 2 ) so F . (a 1 ,a 2 ) =a 1 xF . (a 2 ) . Otherwise (7) If ij;(x, ,x 2 ) has F, satisfying (1.6) and
2 f by (3). Proof:F is F q . D(8) (9) There is F satisfying (1.6). n n+1 Proof: By (8) and (7) o(9) Ivpw an induction starting from (9) and using (6) yields: (10) For all m,n there is F such that —S coot is c -sound. Proof: Let m be the least for which this fails. m>0, of course. Now there is A€Em-./such thatvA *xna)pm, all x€Scoot , where pPdenotes #p pmo . Say A€E,(S " ^l*" m-l) in parameter pm, say, with pm minimal ± —coot in the canonical well-order (which really i_s a well-order in this m case). Let X=h_m-10(a)p Up m) . Then by lemma 4.4 let~~ M be transitive, o p so M i s m-sound, and i n p a r t i c u l a r a c o r e mouse. Let t h e mouse i t e r a t i o n s of M,N be < < Ma > a£On ,< ^ i denote
_ satisfying (1.6) . m~Xn Proof: If m
X
If n=m then F
x —x
n
(a,...a )=a,x...xa . m
-L
n
J.
n
a(10)
_ n"xm
Using F._ we can establish by similar arguments (11) For m
(13) F o r i > 0 , i
satisfying
(1.6).
i
Proof: Suppose <j>(x,...x )<=>A.(x.). Then F
Ai(al---an)=alX---Xaj-lXF17+i(aj'aj)xaj+lx---xan-
D
<13>
Hence (14) If <(>(x1...x ) is atomic then there is F. satisfying (1.6) It remains only to consider bounded quantifiers. We may of course restrict ourselves to the existential quantifier. (15) If I|J(X-I . . .x, ) n
a sF
i satisfying (1.6) and <j>(xn...x )
3x, €x . ip (x, . . .x, ) , where k>n,then there is F^ satisfying
is (1.6).
Note: The assumption that k>n is justified by the fact that <j> is orderly. Proof: Let 0(x....x, ) be x,€x.. So there is F Q , satisfying 1
K.
K.
"2
(1.6);
v Alp
and F~ , ( a , . . . a , , , U a . ) = { ( x 1 . . . X i >:x, € x . , x . £ a . 0Aip 1 k-l j 1 K k j i i
(l
ty ( X , . . . X, ) } .
Then l e t F. (an . . . a )=dom " n ( F Q . (a, . . . a ,a,...a,,Ua (pi n oAip 1 n 1 1 Lemma 1.5 i s p r o v e d . Lemma 1 . 6 . if
then there
.)) j
is F, a composition
a (15) • of F . I
F ( a , x , . . , x . _ w X . + , . . . x ) ={x . €a:cp ( x , . . . x ) }
(1.7)
Proof: Let F, be as in lemma 1.5. Then n-i * dom11 X ( F , ( { X j } . . . { x . _ 1 } / a , { x i + 1 } . . .{x n >) =
Applying r n g ( r n g ( x ) = F 2 ( F g ( x , d o m ( x ) ) , x ) ) Lemma 1 . 7 .
gives the required s e t . n
If l
of basis functions
F* which is a composition
such that F*(u,v)=F ."u>
Proof: Suppose there were a function G. such that G. (u,v)={<<x,y)/t ):x€uAy€vAt€F . (x,y) } . Then F*(u,v)=F c (G.(u,v),uxv). So it suffices to show that G.is a
composition of basis functions. (1){< < x,y>,t>:x£uAyevAt€{x,y}}=((uxv)x u )U((ux v )x v ) (2){<<x,y>,t >:xGuAy€vAtGUx} = {< <x,y >,t >€ (uxv) xuUu: t€Ux} Since t€Ux is I Q the result follows from lemma 1.6.We shall not repeat this remark with the other clauses. (3)
{<< x , y > , t > : x € u A y € V A t € x \ y } = {< < x , y > , t >€ ( u x v ) x u u : t € x ^ y }
(4)
{< < x , y > , t > : x £ u A y € v A t € x x y } = {< < x , y > , t >€ ( u x v ) x ( UuxUv) : t £ x x y }
(5)
{< < x , y > , t > : x € u A y e v A t € d o m ( x ) } = {< < x , y > , t >€ ( u x v ) xiJUUu: t € d o m ( x ) }
(6)
{< < x , y > , t > : x € u A y € v A t e x " { z } } = {< < x , y > , t >€ ( u x v ) x u u U x : t € x u { z } }
(7)
{< < x , y > , t > : x € u A y € v A 3 < s , z > 6 y 3 w e x
t=<w,s,z>} =
= {< < x , y >, t >€ ( u x v ) x ( U u x U U U v x l l U U v ) : 3< s , z > € y 3 w £ x t = < w , s , z f t The
It
remainder
follows
Lemma
1.8.
are easily
by induction
then
Lemma 1 . 9 .
R'=R.
of basis
F * is a composition
We saw t h a t
it
D
that:
If F is a composition
=F"u x . . . x u
Proof:
deduced.
is
functions
of basis
sufficient
Given $ l e t F be a s i n lemma 1.6
and F* (u . . . u ) =
functions.
t o prove
(v),€R'
for a l l
£
$.
with
F ( u , t , x 1 . . . x m ) = { s € u : ( | ) ( s / t f x 1 . . .x m ) } Then F* ( {u} ,w, { x ^ . . . {x m }) ={F(u, t ^ .
(1.9)
. .x m ) : t€w}
:<|) (s,t,x]L. . ,xm) }:t€w}
D
It follows that R may be axiomatised by a single 11^ axiom. Definition
1.10. A function F is rudimentary provided F is a composition of
basis functions.
We have asserted that for each i greater than 0 with i<17+N there is a E_ formula (j>. such that z=F i (x,y)H> i (x,y,z)
(1.10)
If N=0 we can prove (1.10) for all rudimentary functions. So assume N=0 until further notice. We actually prove a stronger assertion. Definition x ...x
1.11.
,u) is t
A function F is substitutable
provided that whenever
there is a E formula ty such that (1.11)
Lemma 1 . 1 2 .
All rudimentary functions
Proof:It will suffice
are
substitutable.
to consider only EQ formulae of the form
Vt€yx(t,x 1 ...x n ) where x is ?.Q. For from this the result follows by induction on Z Q structure. Also substitutable functions are closed under composition. So we need only consider the basis functions. Note that x i €F(z 1 . . .z m ) <* -(Vt€F(z 1 . . •z m ))-( x i = t ) • We shall only consider a few cases. (1) Vt€{z 1 ,z 2 }x(t,x 1 . . .x n )**x( z 1 /X 1 . . .xn) A X ( Z 2 , X 1 . . .x n )
(2) Vt€Uz 1 x(t,x 1 . . .xn)**(Vs€z1) (Vt€s) x (t,x1. . .xn> (3) Vt€z 1 ^z 2 x(t,x 1 ...x n )«(Vt€z 1 )(t€z 2 vx(t,x x ...x n )) (4) V t € z 1 x z 2 x ( t , x 1 . . .x n )**Vt 1 €z 1 Vt 2 €z 2 x« t±,t2 ),x1. . . X R ) using (5) Vt€< z i ; z 2 >x ( t , x 1 . . . x ^ ^ x ^ z ^ } f X ^ . . x n ) A X ( { Z 1 , Z 2 > , x 1 . . . x n ) which i n t u r n u s e s ( 1 ) . The r e a d e r may check t h e o t h e r s . o C o r o l l a r y 1 . 1 3 . If F is rudimentary then there is a 1 formula $ such that z=F (x 1 .. .xn)«<J) (X 1 . . ,x n , z) If N*0 then corollary 1.13 may f a i l . For example, {x,y}€A i s not necessarily 2L in L1"n . For t h i s reason we need to consider a broader class of relations. D e f i n i t i o n 1.14 A relation R is rudimentary provided that for some rudimentary function F R(x 1 ...x n )**'(x 1 ...x n )* 0 Lemma 1.15 Every Z relation is rudimentary. Proof: Let <J) be a ZQ formula. Then by lemma 1.6 there i s a rudimentary function F' such t h a t F'(a,x1...xn)={xn+16a:(D(x1...xn)AXn+1=xn+1}. Let F ( x 1 . . . x n ) = F l ( { O } , x 1 . . . x n ) The function in (1.12) can, informally "effectively"
(1.13) D
speaking, be obtained
from cf>. To formalise this idea we introduce a coding
of the rudimentary
functions.
L e t Q={q: q is a finite function A q*tf> A dom(q)c2 A (s=t|dom(s),t€dom(q) A
•* s€dom(q))
A
A rng(q)cl7+N+l A
(q(s)*O => s/s0,s"l€dom(q) ) A (q(s)=O =» s"0, s"l^dom(q) )}
Let a ={f: f is a function A dom(f) ={s€dom(q) :q(s) -
(1.12)
be a function defined by
F (f)=z ** f€a
A (3g) (dom(g) =dom(q) A
A(Vs€dom(g) ) (q(s)=0 => g(s)=f (s) A A A g(O)=z)
q(s) *0 => 9( s ) = F ,Wc^ (^(s^O) /
The clause with F , . must, of course, be written out as a finite disjunction. For all q in Q F
is rudimentary; and F (f)=z is a A, formula.
Now let T be some function from (s6dom(q):q(s)=0} to n. Let F where f ( s ) = x a 1 1S in dom(T) q T ( X 1 " -Xn)=Fq(f) • T ( s ) ' Then every rudimentary function is of the form F n . And q n 'T F (x,...x ) =z is a A, property of x, . • .x ,z,q,x. For any cj) we can therefore find <3L/T, such that 4>(xn...x ) « F " (x ...x )*0 . (1.14) 1 n q <j>' < J > Fix such q^/T. for all E Q <J> (informally, do so "effectively").
D e f i n i t i o n 1.16.
The E
satisfaction relation, |=" $(x . ..x ) is the relation
This is a A, relation. Definition
1.17
The E^ satisfaction relation, (==£ ( j ) ^ . . . ^
is the relatio
We identify E Q formulae <J> with <0,>. If (J) is 3y 1 Vy 2 . . .Qyin\p(y1. . ,y m ,x 1 . . .xn) then we identify (f) with <m,
>. The E satisfaction relation is itself E . We shall never have to m m refer to this representation explicitly: and later on we shall code the formulae by natural numbers. The superscript n may usually be omitted. Note that we have shown that every rudimentary relation is This is perhaps the moment to mention the role of classes in this theory. As we do not have a E, comprehension axiom there may be E^ definable bounded subsets of the ordinals - which, by the way, are defined in the usual way in R - that are not sets. They may even be like ordinals themselves: they may be initial segments of On. Such segments cannot have a largest element, of course. Definition {(X:
In
1.18. ) } , for
A E limit segment (v\) is a n some
E
n
d) and some
x,...x
In
E class of ordinals (i.e.
n ) such
that
(i) a<3€n =* a€n (ii) a€n => a+l€n. Every E
limit segment i s either On or an ordinal.
I t i s not even precluded that OJ might have a E segment properly included in i t . be disallowed, however.
limit
In our applications t h i s will
Exercises 1. X is rudimentarily closed provided x,y€X =• F ± (x,y)€X for all i with 0 f=R? 2. For which a does L
|=R?
3. Show that F Q is definable from F,..,FO and Fn . y
1
o
10
4. If X is a set, can it be proved in R that there is a smallest set Y=>X such that Y is rudimentarily closed? 5. <M,A> i s amenable provided t h a t f o r a l l x€M AflxGM. Show t h a t <M,A>}=R i f and only i f M f=R and <M,A> i s amenable. 6. Show t h a t i f u i s t r a n s i t i v e and 0
10 2: RELATIVE CONSTRUCTIBILITY
The theory R is not very strong. Although it is possible to define ordinal numbers in it there is practically no ordinal arithmetic. One way to strengthen R would be to add axioms making R closer to ZFC; for example, KP set theory. We want a theory that works in all levels of the constructible hierarchy, however, and not merely at admissible levels. We shall add to R axioms that say V=L[A1...AN] . 17+N
Definition 2.1. s(u)=uU U F ."u i=l By lemma 1.7 S is rudimentary, so R[- VU3ZZ=S(U) Lemma 2.2. If u is transitive then so is S(u). Proof: This is where the apparently redundant F ^
to F.. _ are used.
We check each F.. (1) x , y € u •» { x , y } c u c S (u) . (2)
x€u •» UxcucS(u)
(as u i s
transitive).
(3) x , y€u =• x ^ y c u c S (u) (4) x , y € u , s € x , t E y + < s , t >=F1]L ( s , t ) £S (u) . (5) x , y € u => d o m ( x ) c uc=S(u). (6)
x,y€u,
z € y , t = x " { z } =* t = F 1 7 ( x , z ) .
(7) x ^ e u ^ ' e x ^ v (8) x , y € u ,
1
, w ' >€y => < u 1 , v ' , w ' >=F 12 (u 1 ,< v ' w 1 » w1 €y =* < u 1 , w ' , v 1 > « F 1 3 (< u ' , v 1 >,w')
(u',v'>6x,
•i(9) F g ( x , y ) c F 4 ( x , y ) ;
(10) F 1 Q ( x , y ) c F 4 ( x , y ) .
(11)
x , y € u , s € < x , y > => s = { x } = F 1 ( x , x )
(12)
x,y€u,
y=
=» s = { ( x , v ' > } = F 1 6 ( x , v ' ) (13)
or
s={x,y}=F1(x,y).
s€< x , v f , w ' ) =* o r s={( x , v ' > , w ' } = F 1 4 ( x , y ) .
1
x , y € u , x = < u ' , v ' >, s€< u , y , v ' >=* =* s={< u 1 , y >}=F, 6 (u 1 , y ) o r s={< u 1 , y >, v 1 } = F , 5 ( x , y ) .
(14)
x,y€u,
y=
s€{< x , v ' >,w' } => s=w' o r s = ( x , v ' ) = F 1 1 ( x , v l ) .
(15)
x,y€u,
x=,
s€{< u 1 , y > , v ' } => s = v ' o r s=< u 1 , y >=F1;L (u 1 , y ) .
(16)
x,y€u,
s € { < x , y > } =* s = F 1 1 ( x , y ) .
(17)
x,y€u,
s € { t : < y , t >€x}=*< y , s >€x=*seu;
Definition
2.3.
(17+i)
(i) f=s\x ** xEOn A f is a function
x , y € u => ^^ A dom(f)=x A
A (0€x "*• f(0)=
A
11 A (VX£x) (lim(X) => f(X)= U (ii)
y=Sv ** (3f)(f=S\dom(f) A
Definition
2 . 4 . R is R together with the axioms
(i) W3f f=Slv (ii)
Vx3v3y (y=Sv A
For later use we also define Definition
2 . 5 . rud(u)= USn (u), where Sn (u) is defined inductively
by
S0(u)=uV{u] Sn+1(u)=S(Sn(u)U{Sn(u)}) Clearly rud(u) is rudimentarily closed. But it need not be a set even if u is; and it may not be the smallest rudimentarily closed X3uU{u} (unless we restrict X to be a set). From now on we work in R . Lemma 2 . 6 . Each S is
transitive.
Proof: (This is a model for various subsequent inductions) Suppose not. Then letting E={v :S is not transitive}, E*0. Claim
E has a least member.
Proof: Take y€E. If Efly=0 y is the least member. Otherwise let f=S|y. Then Efly={v
(2.1) n(Claim)
Let y be least, then.y+O, of course, nor is y a successor by lemma 2.2. but if y is a limit then S = U S and each S is Y v
Similarly Lemma 2 . 7 .
y
Lemma 2 . 8 .
If X is a limit
ordinal then S, is rudimentarily
closed.
A
Proof: If x,y€S A then x,y€S
, some y
Let S_x =< S x ,€nS^,A i ns x , . . . /^flS^ >. Clearly SX)=R (A a limit)
Lemma 2.9. lim(X) =* X=Onf\s, .
12 Proof: If not then we could use the technique of lemma 2.6 to obtain a least X for which the lemma failed. Case 1
A is a limit of limit ordinals
Then 0nDS^=0nn U{SX,:X'<X and X 1 a limit} =U{Onns^,: X'<X and X1 a limit} =U{X':X'<X} =X. Case 2 There is a maximal X'<X which is a limit ordinal. Suppose Xc{:S, . Then there is a least v<X such that V ^ S , . Since X'=OnnS,,ES x ,v>X'. But X'=Onns x , and S^,€S X so X'€S X . Thus v>X'; so v is not a limit ordinal; say v=y+l. Then y£S,; but then yll{y}€Sx as §XJ=R. Contradiction! Suppose, then, that OnflS^i X. Then there is y£ (OnDS, )^X; since OnflS, is transitive, X€S,nOn. By the usual argument there is a least v<X with XcS nOn. And since S, ,DOn=X',v>X'. Say v=y+l. So XcfcS . Now — v A y by exercise 6 in chapter 1 UUUUS cS . But since X is a limit ordinal XcUUUUS v ; contradiction!
D
Lemma 2.10. lim(X) => S,\=R+ Proof: Again we may assume that X is the least where this fails and derive a contradiction. Case 1 X is a limit of limit ordinals. R
is axiomatised by a single IT2 axiom, so this is impossible.
Case 2 There is a maximal X'<X which is a limit ordinal. Suppose there is v<X such that s|v$S, . We may take v least such. u>X', since otherwise SIvES^.cS^. And S|X'=U{fesx, : Sx, |=f=S |dom(f) }so S|X'€S X . So v is a successor.
Say v=y+l. Then s|y€S,. But
S | v=S |yU{< y,S >} and S €S <=s, . So s|v€S,. Contradiction! y y v~~ A A But given x€S, there is v<Xwith x€S so S,f=3v3y(y=S Ax€y) . I
A
V
Thus §, f=R .
~~A
V
D
In ordinary set theory it would now be straightforward to call S S x, JJ\ howevei in R we must f i r s t x ;; however, a)X X ordinal a r i t h m e t i c . Definition 2 . 1 1 .
develop the necessary
T=v+n <=» x,v€0n A n€w A
A 3f (dom(f)chi A f(O)=V A Cii+l£dom(f))
(f (i+l)=f (i)+l)
A T=f(n)
This i s a E, formula. Generally we cannot prove that v+n e x i s t s . Suppose for some v i t did not; then {n:v+n exists} i s a E, limit segment of u). Definition stating
2.12.
The theory R+ is R* together with the axiom schema
that every definable
limit
segment of 0) is either
0 or 0).
13 From now on we work in R . Note t h a t the theory i s no longer n~ axiomatisable. Now we g e t : Lemma 2 . 1 3 . For all v and all nQjd \>+n
exists.
Proof: {n:v+n exists} i s co. R
strengthens R
•
by a strong form of induction on GO .
Lemma 2 . 1 4 . Suppose
(Vn&ti) (v+n
X= sup V+n ) n£(jo
Proof: L e t E = { £ < T :
f o r a l l n€u) v+n<£}.
Claim n=v+n ** £5 (=ri=v+n Proof: (=*) Suppose ri=v+n. Let f be as in lemma 2.11. Then f€S by an easy induction on n. (*=) Obvious.
•(Claim)
Thus E={£
If there is a largest
a limit
ordinal X then On={\+n:n€a)}UX.
Proof: Otherwise t h e r e i s x€On^{ A+n:n€oj} UX. So X+OJ e x i s t s , butA+a)>X, X+OJ i s a l i m i t o r d i n a l . Definition (ii)
2.16.
•
(i) f=D\v *=» f is a function
A v€On A dom(f)=v A
K K rvx
This is a T.^ formula. [ V/OJ] is the unique T such that v=o)T+k, some k€oj.
Lemma 2.17.
VV/"V/OJ; exists.
Proof: It suffices to show VvD|v exists. Claim If X=0 or lim(X) then (Vv<X)D|v€S x . Proof: Suppose not. As usual we may get a least X where the claim fails. X*0, then; and if X is a limit of limit ordinals then the claim holds. So there is a maximal X'<X,X' a limit ordinal. Thus by lemma 2.14 X = { X'+n:n€o)}UX' . Now D|v£S, , for all v<X', and D|X'={< v,x>:Sx,f=x=[ V/OJ] }
(2.2)
so D|X'€S X I . Then if n is least such that DlX'+n^S^,, n=m+l, sayc But then D|X'+m€S A , and D | X ' +n= (D | X ' +m) U{< m, [ X '/a)] >} so DlX'+nES^; contradiction 1
•(Claim)
Now if On is a limit of limit ordinals the lemma follows by the claim. Otherwise there is a largest limit ordinal X and 0n= = {X+n:n€a)}UX by lemma 2.15, and the result is proved just as in the claim.
•
14 Definition
(ii)
2.18.
(i)
X=OJV ** (T=OAV=O)V(T is
dh denotes {y.-ojy
(Hi)
J =S
a limit
and
V=[T/U])
exists]
(provided OJV
exists)
I t i s immediate from lemma 2.10 that J f=R . Clearly every limit ordinal x i s of the form OJV . In R
the structure of limit
segments i s simplified by
Lemma 2 . 1 9 . If r\cpn is a bounded E limit then T] has no largest Proof:
limit
segment which is not an ordinal
ordinal.
Suppose i t did and c a l l
i t X.
Claim X+n€n for a l l n€oj. Proof: Let k={n: X+n€n}. k i s a E
limit
segment of OJ SO k=oj D( claim)
Hence X+OJCT) . So X+OJ e x i s t s and i s a l i m i t o r d i n a l ; So n i s an o r d i n a l .
Lemma 2 . 2 0 .
If there is a largest
dh is a limit
segment.
limit
ordinal OJV then dh=\)+l. Otherwise
Proof: Clear
If
o
n is a limit
limit
segment we l e t OJH denote {y:3v€n y
segment. By lemma 2.19 every E
but not an o r d i n a l
Lemma 2.21.
thus X+oj=n.
a
limit
segment t h a t
i s bounded
i s of the form ojri.
S \=R* (ojr)c: On) -OJTV —
Proof: If can is an ordinal then this is lemma 2.10. If ojri is On V=S . Otherwise S is a union of models of R by lemma 2.19 and V=S . Otherwise S is a union of model lemma 2.10.
D
We can extend definition 2.18 to limit segments by allowing J =S p r o v i d e d nsCfri. So
v=
J0n-
A l s o J =S
THE AXIOM OF CHOICE Just
a s i n ZFC V=L [A] =• AC, s o R+|-AC. The e s s e n t i a l
technical
lemma i s
Lemma 2 . 2 2 . Suppose u is a set with a well-order ordered. Indeed there is a rudimentary function
r. Then S(u) can be well-
W such that W(u,r)
well-orders
S(u). P r o o f : W ( u , r ) = { < x , y >€(S(u))
:
(x,y€uAxry)v(x€uAy€u) v
v(x$UAy$UA(3s€u)(3t€u)(3i£l7+N)(x=Fi(s,t) A
A ( V S ' € U ) (Vt'€u) (s'rs «* (Vj£l7+N) y*F.(s',t')A A ( s ' = S A t ' r t =» (Vj£l7+N)
y*F. ( s 1 , t ' ) )") )")A
(2.3)
15
Since the defining clause is E Q W is rudimentary by 1.6. • Note that W(u,r) is an end-extension of r. We let f=w|v be the formula f is a function A dom(f)=v A v€On A
(2.4)
pU{Sp} f f (?) U{< t,S >:t€S }) ) A )=
U f(£')) A (v*0 =* f(O)=0)
And r=W v means 3f(v€dom(f) A f=w|dom(f) A r=f(v)) Lemma 2.23.
(i) For all v W exists
(ii) For all v W is a well-order of S . Proof: Very like lemma 2.17. First of all establish that if X is a limit ordinal then for v<X W v €S^. If this failed there would be a least limit X where it failed. X cannot be 0 or a limit of limits; hence there is a largest limit X'<X. W £S,, for v<X' and W., is V
S x ,-definable
A
so W,,€S.. If X'+n+l i s least with
w
A s w e Xi+n+1$ x
derive a contradiction by rudimentary closure of S,. Then the result i s proved unless On=XU{X+n:n€a)}, some limit X, in which case i t i s proved by rudimentary closure. (ii)
i s then a t r i v i a l induction.
•
C o r o l l a r y 2 . 2 4 . Every set can be well-ordered. ordering of the universe that is a £
Indeed there is a well-
class.
The well-ordering we have constructed is called the canonical wellordering. Lemma 2 . 2 5 . Suppose R is a Z relation.
Then there is a I, function r such
that 3yR(x 1 . . . x n , y )
=» R(x x . . . x n , r ( x 1 . . . X R ) )
(2.5)
for all x , . . . x . 1 n Proof:
Suppose
at t h e l e a s t ordering.
R(x.....x
Then,
A(Vy So r
1
/
z eSY)(((y',z
Let r'(x,...x
R ' ( x . . . x ,y,z) in t h e canonical
) =* well-
R1 i s £ Q ,
« R'(x1...x
l
1
n /
y/z)
>,
A ( 3y) « y ,z >eSy
=> - R ' ( X ] _ . . . x
n
A
(2.6)
, y , z) )
i s E, . S a y r(xx...xn)=y
(2.7)
that
provided
r1 (x1...xn)=
, y ) <=> 3 z R ' ( x . . . . x , y , z ) .
such
« 3zr'(xx...xn)=
i s a T.1 d e f i n i t i o n
and r
satisfies
C o r o l l a r y 2 . 2 6 . If f is a E- function fog=id\rng(f)
.
(2.7) (2.5)
•
then there is a E function g such that
16 Proof: R(y,x) «=> f (x)=y
is a £.. relation. So there is g 1 such that
3xR(y,x) •» R(y,g(y)) =* f(g(y))=y. Let g=g'|rng(f).
D
SKOLEM FUNCTIONS The Kuratowski pair that we have used up to now is usually satisfactory, but sometimes we require a pairing function under which the ordinals are closed. The Godel pairing function is such; but generally if we are working in R we cannot assert that every pair of ordinals has a Godel pair. Our official pairing function will nevertheless be an adaptation of the Gftdel pairing function. Definition 2.27.
(i) < is the well-ordering of On determined by
< a, 3 >
(2.8) v
v (max (a, 3) =max(a' ,3 ') Aa=a ' A 3 < 3 ') (ii) f=p\y «=> dom(f)=^f A f is a function A Va,3
A Va
p i s a £, function
~ (3f) (f=p\dom(f)
that
A f (y)=< a,3 >;
enumerates t h e GdJdel p a i r s .
Lemma 2 . 2 8 . Va3f f=p\a.
Proof: Observe that< a, 3 >=p(y) =* max (a, 3)£p (y) . From this the technique of lemma 2.17 enables us to deduce that if X is a limit ordinal then Vv£A3f€S, f=p|v, and hence to obtain the result by the A usual adaptation. D 2 p|a:a-*-a , but is not, generally, surjective. D e f i n i t i o n 2 . 2 9 . (i) Q={oi:p(a)=( 0,a)} . (ii) a is G-closed if and only if a is a limit point of Q. Lemma 2 . 3 0 .
There is a E map of On onto On .
Proof: Although the strategy i s quite standard we give the proof
in
detail.
Claim
If A is a limit ordinal then there is a Z_ (S^) map of X onto
Proof: Suppose not. Let E = { A : A is a limit ordinal and there is no Z 1 (S X ) map of A onto X 2 } . So E*tf>. Take some X€E; if XflE=0 then X was minimal. Otherwise since ^ ( S ^ J c S ^ when X1 is an ordinal less than X, we may use definition 1.17 to set
17 EnA={A'
f:A'-A |2 onto}
so that EnA is a set. So there is a least A where the claim fails. Clearly A$Q. Case 1
A is a limit of limit ordinals.
Suppose p(A)=
A
onto {z:z< < V , T > } . Let y={z: z< < v, T >}; suppose A ' is a limit and V,T
—
A
«
By inductive hypothesis there is g€E,(S,,) mapping A1 onto A1 ; l A 2 so g€S,. So by corollary 2.26 there is g'€E,(S,,) mapping A1 A
J. —A
one-one into A 1 . So g'€S,. Let f « y , y ' » = g ' (
one-one into A'.Let v=rng(f); then v = g i n ( g I M y ) , so v€S,
Let h(y)=f" 1 (y) =<0,0> Then h:A-*A Case 2
if yev
(2.9)
otherwise
maps A onto A . Contradiction!
There is a maximal limit A'
Note that this is the only other case because a>€Q. There is a E, (S..,) map g:A'-*(A') i. —A
onto, and so by corollary 2.26
*y
a E1(S x ,) map g':(A') +A' one-one. So g'CS^. Since A={ A '+n:n€a)} UA' there is a bijection j: A«-*A ' I (S, ) . Let f (y ,y ') =g ' (< j (y) , j (y •) » . 2 1 —A So f:A -»-A' is one-one. Let v=rng(f); then v=rng(g'), so v€S, . h is then defined as in (2.9). Contradiction! a(Claim) As usual the lemma follows from the claim by applying the relevant case to On.
n
It is important to notice that the proof of lemma 2.30 was not uniform. In the definition (2.9), furthermore, we had to use a parameter v,and there is no way in general of making the map parameter free and keeping it E,. At times when we are being sensitive about parameters we shall use the Go'del pairing function. Definition 2.31. n is a Z -cardinal provided •
n
(i) T) is a limit segment of On; (ii) there is no E map F with v€r| such that X]C{F(i) :i
If r\ is a E cardinal
then r\ is closed
i€dom(F)}.
under p (so if T) is an
T\$.Q) .
Proof: Note t h a t n must be a l i m i t of l i m i t o r d i n a l s . But i f t h e lemma f a i l e d t h e r e would be A' €n with A1 a l i m i t and p"n<=(Al) . But then p " " 1 | ( A 1 ) 2 i s a E, f u n c t i o n with n E r n 9 ( P " 1 I ( A ') 2 ) • A n d t h e r e 2 i s a map of A'-^A 1 . C o n t r a d i c t i o n ! •
18 Let s be a map of u) one-one onto {:q€Q A A T:{3£dom(q):q(§)=O}+n,n<w}. Then the relation R m (i,<x 1 ...x <=> s (i) =< q , T . ,n > A kj} <j>(xn...x ) is E an
s
<> j q> ' Z 1 f i x e d f o r m n o w o n . $.
is
n is
provided s is picked £,; such
m
such
that
s(i)=
sometimes c a l l e d
Definition
2.33.
h(i,( x))=y
uniformises
R' (i,( x),y)
h is called
the Z Skolem
Lemma
2.34.
h" fup<x
s(i);
;^
n;
"*"
R denotes R . is the I
*• R (i,(x,y))
co
1 ,n),some
, T. •*"
1
cj). i s
>) ~
given
parameter
free
function
by the proof of lemma
that 2.25.
function.
h\
v.
Proof: (V denotes
> of course)
Let Y=h"(ooxx
Say
Y;L=h
( j±/< x±1. . . x ± k
»
where j.€o),0 (z,y, . . .y ) where 4> is E Q . Let
r(x 1 1 ...x n l ...x n k ,z) «< M z,h(J 1 ,<x 11 ...x lk »...
(2.10)
and suppose
(2.11)
3zR' (i,< x^., . . .x
>,z), so by definition k n R (i,< x i;L . . . x n k > r h(i,<x i;L ...x nk » ) . (2.12) n n Let z l = h ( i , ( x n . . . x n k >) ; so z ' £Y and by (2.12) R ' (i ,< x±1. . . x R k >, z ') n n 1
Definition 2.35.
ii(Xj denotes h" (wxx
Strictly speaking this is ambiguous, but in practice we always recognise functional applications of h by the natural number argument. Lemma 2.36 . v*h(On) . Proof: The usual strategy. Claim
If A is a limit ordinal and xGS^ then there are i€o> and
a, . . .a <X such that S, hx=h (i ,< a, . . .a >) . ~~A J. n -L n Proof: Suppose the claim failed. There will be a least X where it fails. Case 1 X is a limit of limit ordinals. Suppose xeS-,,A'<X, X1 a limit. Say i€(jo ,ot, < . . . ) . Then S>x=h(i,(a, ...a )) . A j. n ~~A i. n Case 2 There is a largest limit X'<X.
19 Then A=A'U{X'+n:nEw}. Suppose n is least such that there is xes
X « + +i
an
x
^
violates the claim. Say x=F.(y,z) with 0
y,z€S,,, U{S,,, }. It suffices to show that x is £, definable A
> n
A
•+• n
-L
from ordinals in S,. But x=F.(y,z) is E», so it suffices to show y,z ~~A
E, definable. If y,z€S,,, .L
A
"i~n
1
U
this follows by the minimality assumption.
But -A^ y = S A'+n ** 3f (f=S|dom(f) A f (XI+n)=y) (2.13) is a £, definition of S,,, from ordinals. This establishes the 1 A +n claim. D(Claim) The lemma follows from the claim as usual.
n
So there is a parameter free map of a subset of wxOn
w
onto V.
Lemma 2 . 3 7 . There is a I, (with parameters) map of On onto UJXOn 2
Proof: By lemma 2.30 there is a £, map F of On onto On . Define by induction on n
F 1 (a)=a F n + l ( a ) = < a i - " 3 n - l ' Y ' y l > w h e r e F n (a)=<3 1 ...3 n > and
(2.15)
(Vm
•
If F was the Gfldel pairing function then G is parameter free. In this case G is by abuse of notation called the G6"del pairing function. Often we write G(-ia,...a ^ ^ a ^ . - . a In
Corollary
2.38.
Lemma 2 . 3 9 . Proof:
>.
in
There is a I, map of a subset
of On onto V.
There is a I. map of On onto V.
L e t h * ( T ,< i , x >) = h ( i , x )
if
BzGS H ( i , < x > , y , z )
=0 o t h e r w i s e ,
where h(i,<x>)=y *> 3zH (i ,< x >,y, z) is some E, parameter free definition of h with H E Q . h* is l-^ and total. Furthermore h*:0nx(u)x0n w)->V onto. But using F and the map of lemma 2.37 there is a map of On onto Onx(cox0n w ) .
•
20 MISCELLANEOUS Lemma 2 . 4 0 .
RESULTS IN R*
TC(x) exists
for all x.
Proof: Let f=TC|y be the formula f is a function A
A dom(f)=y A y i s t r a n s i t i v e A
(Vz€y)f(z)=zU t y z f(t)
Then y=TC(x) « 3f(f=TC|dom(f) W3f
(2.16)
A f(x)=y). So it suffices to show
f=TC|S .
Claim W < X 3 f € S x
f=TC| S v when X is a limit.
Proof: If not there is a least X where the claim fails and X=X'U{X'+n:n€o)}
for some limit X'<X. Since
(2.16) is a 2^ definition
and TC|s€S,, Let n be least such that TC| s x»+ n +l , , ffor o r v<X', v < X , TC|s,,€S,. TC|s,,€S, V V
A A
X
A
L e t fQ = T C | S x , + n . L e t fi+1={<x,y>:x€Sx,+n+1
A xcdom(f ± )
A y=xUz^xf±(z)}
(2.17)
Then f o r x€S, , , , , we have x€dom(f, , , ) and f, , , (x)=TC(x) , where k A +n+J-
i s such t h a t
K + J.
K + J.
U x<=S, l + . But by e x e r c i s e 6 i n c h a p t e r 1 i f xGS, , +
t h e n UUUUxcS,,,
. So T C | s , , ,
-— A + n
, 1 =f c -, which i s i n S, .
A +n+j_
D
+ 1
• (Claim)
A
As usual the lemma follows from the claim Lemma 2 . 4 1 . Suppose X is the maximal limit ordinal
D and that A .<=S, for 0
^————^—^——
2
A
Then every y x<^S, is definable over S, . —X X Proof: Suppose x=F(y,...y ) for y,...y €S,U{S,} with f rudimentary: x n x n A A this is possible because each S , + is rudimentary in S,U{S,}. Now there is a function F 1 which is a composition of F i ' ' * F i 7
such
that x=F (y, . . . y ) *» x=F' (y, . . .y ,A, . . .A ) . By lemma 1.12 there is a E o formula $ such that t€F(y^...y ) <=> <J> (t, y^. . . Y n /A 1 . . . A N ) and we may assume t€F(y, ...y ) «* 4> (t,yn . . . y^ , ,S, ,A, . . .A ) (yn . . .y -,eSy) L n L n—x A J. IN x n"~x A By induction on E Q structure of (J) we may produce \p such that •
X
H(t^^ . .y ^ ) .
For *(t,y 1 ...y n _ 1 ,S x ,A 1 ...A N ) « <S X U{S X }U{A 1 ...A N },€,A 1 ...A N >H N(t,y1...yn_1,sx,A1...AN) since S^UlS^JuCA,...A
} is transitive: the construction of \p by
induction is left to the reader: the only non-trivial clause replaces (3y€S.) by 3y. A Lemma 2 . 4 2 . X onto
If X is a limit
o ordinal
then for all 7c€o3 there
is f mapping
Sx+k.
Proof: By induction on k. k=0 is corollary 2.38. Otherwise let
21 3, , be o n t o .
Define
g(a,Y,Y')=f(Y)
i f a=0
(2.18)
=F ( f ( Y ) f f ( Y 1 ) )
i f 0
=0 o t h e r w i s e s
T n e n
:X ^" x+v+i* onto.
u s i n g F_ of (2.14) a
d e f i n e d over S» ,
Lemma 2 . 4 3 . Suppose X is the maximal limit ordinal and xcP(SJ, and for 0
A .cs
—
l— A
There is p such that xc£ (S, ) . — p —A
P r o o f : T h i s i s a u n i f o r m f o r m o f lemma 2 . 4 1 . S u p p o s e x € S ^ + , , k € w . So x c S , ,, a s S A j l i s t r a n s i t i v e . — A+K A+K
S a y f:X->S,^, o n t o b y lemma 2 . 4 2 . A+K
We may assume x*0. So letting X={< Y,t>:t€f (Y) A f(Y)€x}
(2.19)
XcS and so by lemma 2.41 XGS (S,) say. Then for y£x there is Y < X — A p —A such t h a t y=f(y); then y={t:
map of On
onto V provably in R ? 4. A limit segment n is £
regular provided there is no E map
F such that for some v€n VY€TI3Y '
E, regular imply that n is a E-. cardinal? Vice-versa? If
22 3 : ACCEPTABILITY AND THE PROJECTUM
Not a l l models of R have nice fine structure. The possibility of fine structure depends on our being able to code a l l the bounded subsets of y which are £, by a single one, provided that y is the least ordinal for which the E, comprehension axiom fails.This is assured by the following Definition which
definition.
3 . 1 . RA is the theory R* together with the axiom of
acceptability
states: Suppose X is a limit
suppose u£S,
ordinal and 6<X such that for some ac6 ,
. Then there is f=K fy :6<E><\ >€S,
f.:^{Uu(P(^)nu)
such that
onto
(3.1)
In this chapter we work in RA. Lemma
3 . 2 . If X is a limit
then
Sy\=RA. —A
Proof: This i s immediate. • The axiom of acceptability can be thought of as the best form of GCH we can get without assuming the power set axiom. Lemma 3 . 3 . Suppose w i s a set. Let v denote the least
cardinal >v, or On if
V is the largest
class
cardinal.
Then there is v'
such
and a I
that
(a) {a^ .: i
isa
^
property.
x = ^y «•» 3f( f is a function A dom(f)=i A rng(f)=rvflST A
(3.2)
A f is strictly increasing ) A T € F This is £.. as V PIS is uniformly I. in T. The technique of chapter 2 establishes <^Y:j€S r v ^ for all i
23 dealt with s i n c e v_>0). L e t g be t h e l e a s t such map. L e t a
gg ( n, i) ), j j= jf j, n ( i ) ' S o P W - U ^^: i
T
Set v'=oov*. ^ Suppose o)V*>v . Then v €On,so i s a c a r d i n a l . Let $=[ v /GO] ; then there i s a map of 3 onto v ; so 3=v . That i s , v =o)V . Hence v*>v+. For i
and ?(V) -V or for all
Proof: I f P(v) i s n o t a s e t then given ucp(v) t h e r e i s a l i m i t X with u € S , + and P ( v ) n s , + ^ S , * 0 . By t h e axiom of a c c e p t a b i l i t y u£v. If P(v) i s a s e t t h e n P ( v ) £ v + by lemma 3 . 3 . But then P(v)=v + by C a n t o r ' s theorem. n Definition 3 . 5 . The projecturn p is defined by wp={v: f o r a l l £, AcOn ADv i s a s e t } 1
(3.3)
—
To justify this definition we need Lemma 3 . 6 .
{v: for all £ Acpn Af)V is a set] is a limit
Proof: If Aflv i s a set then Af1(v+1) i s a s e t .
segment
D
p is either an ordinal or a limit segment of Oh or Oh i t s e l f . As far as we are concerned the use of wp rather than p in (3.3) i s a nuisance, but i t s use keeps our r e s u l t s in line with the l i t e r a t u r e . The smallest possible value of p i s 1. Definition 3 . 7 . RA is the theory RA together with the axiom stating there is a I, AcVn such that for all x AnoJp+xflOJp. 1 If p is an ordinal then RA and RA
Lemma 3 . 8 . ujp is a Z
cardinal.
that
coincide. From now on we work in
24 Proof: Suppose F i s
E , y€cop , dom(F)cy and copcrng(f) . Suppose
_i_
i
$€y ^cop. So t h e r e
i s a function
from y whose range includes ojp, g. x. Say 6€A' « g(6)€A. Then A1
Take A 2^ such t h a t AHcop+xflcop, a l l is
1
E.^, A'cyEcop so A
is a set.
But Aflcop= (g"A') Do)p and g"A'
is a
set.
Contradiction! So y ^oap=0; t h a t lemma 3.3 t h e r e A is
a E,
is,
y -cop or y €cop.Hence y £rng(F)
subset of y, hence A i s a s e t .
Say A=G(£). Then
contradiction. 1 Corollary
3.9.
Corollary
3.10.
if
n
p*On then cop=p or p=2.
wp i s closed under the G&del pairing function.
Proof: By lemma 3.8 and lemma 2 . 3 2 .
Hence we could have defined Ac(0n)
and by
i s a E1 map G of y onto P ( y ) . Let A={£:C^G(^)};
2^, AfMvf" fine
a
wp as the s e t of is
structure,
v for which given
a set. in L for
of projectum by looking a t
example, we i t e r a t e
t h e s t r u c t u r e <J
the
,A> where
A codes up the E, s u b s e t s of cop; A i s c a l l e d the E, master code. In our p r e s e n t circumstances we could not be assured t h a t < J was amenable. We have to r e p l a c e J contains
all
by a s t r u c t u r e
that at
,A >
least
bounded subsets of cop.
Definition
3 . 1 1 . tf~ denotes {x:TC(x)€&} (This is well-defined
Definition
3.12.
P denotes {p€[ On]
:for some A
by lemma 2.40)
E in parameter p
there is no x such that AOb}p=AC\x] .
Lemma 3 . 1 3 . p*0 Proof: There is some p 1 with the property ascribed to members of P, since we are working in RA . But there is a parameter free map G say of
(0n) < a ) onto V. If p 1 =G (< o^. . . a n >) then let p={a 1 ...a n >.
a
On is not necessarily closed under the GOdel pairing function so p may not be reducible to a single ordinal. On the other hand o>p is closed by corollary corollc 3.10 so cop may be replaced by (wp) w in Definition 3.12.
Definition 3.14. r^fti,*): i€oo A X€H
So A P , T P are 2^.
A \=?, s(i)(xfp)};
25 Definition
3.15.
Let B ...B
be given.
Ik
0<j
_
(u) denotes 7 * * *
1 /r/V-f-J
J
^~
S_ 1" ' k =< S,£0S denotes
.(x,y)=B .Ox where
UUU{F."U :0
\r
k is defined from S_ B . . .B B 2 I k
J8!. '"Bk
Define F
as S was defined in definition 2.3. V B B
,A OS,. . . ,A OS,B OS,. . . ,B Os) where S=S 1" ' k S^l"'Bk
and J^l '"Bk
S^l '"Bk.
denotes
We make no existence claims in general. However: AP
Lemma 3 . 1 6 .
For all v€oop s
exists.
P r o o f : 6 = X+y m e a n s 3f ( f i s a f u n c t i o n A (Vv+l€dom(f)) (f (v+l)=f ( v ) + l )
A dom(f)<=On A f (0) =X A
A (VyGdom(f) ) ( l i m ( y ) =*
=> f ( y ) = s u p f ( v ) ) ) v
and S, ,(=X"--X+Y~~A
Then there is a least X"+n+l such that (Vy<X') S^,^X"+n+l=X+n. Suppose S, ,|=X"+n+l=X+'y+l and Y + l < A I (we are using the associativity —A
,
of addition, which may be seen to hold in R ) . Contradiction.1 So E=0 . The claim follows by the usual adaptation.
D(Claim 1)
Now suppose a€S, + \S, and acy€a)p . Suppose On={X+y ' :y' €n }UX. Claim 2 y€n. Proof:Suppose n^y. We are going to deduce that there is a E, map of y onto P(y). This is done by establishing that if X' is a limit and X'>X then there is a E, (S,,) map of y onto P(y)ns,,. Otherwise J- — A
A
take a least X1 where this fails. If there were a largest limit X"<X' then P(y) PIS, , *P (y) DS, „; if X" = X this is given, and if X M >X A A there is a E,(SAII) map of y onto P(y)ns, n . But by acceptability we deduce
i —A t h ee x i s t e n c e
o f a E,(S,,) -L ~~ A
A map o f y onto
P(y)ns,,. A
So suppose X1 is a limit of limits. If X
denote the
in the canonical well-order (y a limit).
So
(v2) if X+v 1 <X' and g(v)=
=0 otnerwise. Then F is a E^^ map, and since n£y, X '<={ X+y' :y'
F: y>P(y) ns^ , onto.
The usual argument now gives a E^ map F of y onto P(y). Let }. A is a set as y£o)p. But £€A ** ^$A. Contradiction!
26 _ Claim 3
D(Claim 2)
S a exists for all a€ S, , . y X+0)
Proof: Suppose A.1 is a limit ordinal, X'>X and X + Y ' < X ' . Then S^ , f=3f (f=S a | y 1 ) . To see this suppose it failed at some least X 1 . X 1 cannot be a limit of limits_; so X '=X" U{X"+n:n£u)} where X" is a Limit. If X + Y ' < X " then S a |y'€S,,.Since aes,, it follows that S a |Y'€S,, where X J - Y I = X " . So there is least: y' +n+l, where \+y'=\",
such that
S a | Y 1 +n+l^S.. , . But then S a ,€S,, and an e a s ^ induction gives S a , , € S , , , so S a |Y'+n+l = S a | Y ' +nU{< Y ' + n , S a , _ S
a
>}£S. ,; contradiction.1
Now it follows as usual that if X + Y exists then S a |y and hence exists. But Y ^ I by claim 2.
•(Claim 3)
suppose y is a limit and letS,^ a=A™riY. X be the least Now limit ordinal with a€S,^ordinal . If y=X then flP(y)Let *S, flP(y) . A +0J
1 Ajr OJ
A
^ ^ f:Y^(Y) Th Otherwise let f C S • Then let a=f "a, so a€P(y) O S .++ Hence by claim 3 S exists. So S exists for all y£uiQ, •
w
^
Claim 2 of the preceding lemma is often of independant interest: it implies, for example, that if X is the largest limit ordinal and the projectum of S, is 1 then the projectum p
must also be 1.
—A Lemma 3.17. Suppose that for all acry
Let e={p
(< £,T » :f (£)€f (T) }. v€Q so ecv.
We claim x€S e . For rank|TC(x):TC(x) +rank(x) onto so rank(x)€x. (Here we are using the result of exercise 1 in chapter 2.) Define g=coll|Y « y is an ordinal A g is a function A dom(g)=Y A A g(O)=0 A ( V X € Y ) ( A a limit =» g(X)= U g(C)) A B,<\
A ( W + 1 € Y ) (g(v+l)={< C,g(v) "{6:p x ( < 6 , O ) €e} >: C
A
A
P n (a>x (Y)< w )
is a
D
Setp
then for all Y ^ ^ P S a €J A .
then 6+y exists and 6+y€.bip because cop is a £, cardinal.
By claim 3 in lemma 3.16 S a €J
. So it suffices to prove that
27 _AP => a £ j . W e l l ,
+ y coop s o by lemma 3 . 3 t h e r e a r e i€u>, £€a)p
such t h a t a = h ( i , £ ) . S a y <J>(z,y,p) «• y € h ( i , z )
(3.4)
and s u p p o s e <> j i s <J> . ( a s a E, So
£ a e ^£ .<
j< > >
P
}
formula).
Then
(3.5)
D
p C o r o l l a r y 3 . 1 9 . H = . / ;H chfwpltfp};. *
cap p
Definition
oop—
+
3.20.
+
KA is R together with the axiom of strong
acceptability:
For all limit X and 6<X such that P(6)C\S^*P(&)n It i s easily seen,
u s i n g lemma 2 . 4 2 , t h a t RA 3RA.
p Lemma 3 . 2 1 . j_A \=RA + Proof: C l e a r l y J
Ap
~~P
+ Ap Ap |=R . Suppose aCS^ ^ S ^ , ac6,X a l i m i t . '
UJ
A "t"CO
A
~~
Say
a=h(i,^) where ^€6 . Let (J) be the formula 4>(x,y,p) •* y€h(i,x)
(3.6)
Suppose
(3.7)
So if 4> is $ . =5 ~p< j,<6,X, But then f€S^ +a) . n
Definition 3.22. v*W* . _p VP(=RA, so within V p we can define a projectum. But we cannot assume that VP|=RA .
Definition
3 . 2 3 . p =on; ip
np
np
A0=T°=P&Q=
n
Suppose lf ,T ,A ,p
and PA^ are defined for
pn+1=(){projecta of V^P,
(which is contained in
(v"p')p")
28 CODING V I N V P
Lemma 3 . 2 4 .
(i) (^,1?)
1
is amenable;
I
x=y(\TP is Z^ (V1*) .
(Hi)
x = y f l T p *> ( 3 f ) ( d o m ( f ) € O n
Proof:
a function"€Ap
is
A ( 3 i ) ( 3 ^ . . . T k € O n ) ( " h ( i , < T1 . . . T R f p»
A "dom(f) =dom(h (i/
( f ( £ ) = { f ( ? ) € T C ( y ) : " h ( i , < T±...TR,p» (C) € ,< T 1 . . . T k , p » (C)"€A P ) A ( 3 y ) ( y = f ( Y ) AX={fU)€y: A i€o) A ^ i ( j ) i ( z / p ) " e A P } ) ) )
"f(C)= P
P
i n
Before
where
t h e next
"<|>. (YrP) " d e n o t e s
definition
<J> i s a E_ f o r m u l a x obtained
variable
>.
we n e e d a l i t t l e
D
temporary
notation.
with
r n g ( T . ) c m - l a n d s ( i ) i s t h e E, f o r m u l a (p — J. by r e p l a c i n g e a c h o c c u r r e n c e o f v, by
h ( ( ( v
t h e n d 0)k)0'< ( ^ k h ' V ^ "*(
(3y) s ( j ) ( < x , p > , y ) ; t h e n D ( j , x )
Definition predicate
denotes
3 . 2 5 . The theory MC is formulated
in L
e n o t e s
€T.
as follows
(calling
the
••$«i0,Xo)..Mm_1,Xm_1)>»-D(i0,Xo)...D(im_1,Xm_1)!
(ii)
if rng(T,)cm-l and n>m then "(j>f< i n , x . >.. .< i .,x (p — — 0 u m—1 0 o n-1 n-1 (Hi) D(i,x) •* "
(V) "<
> =
(vi)k
i 0 / x o »•
(vii) rnfffT
x
m-
nd"x(i
_>;"*» m—l
* "
A »
-( j^X^" A "< V V * W " " A "( i
I A
(viii) i f 4> is xpy m—1
o f one
symbols B ...B ,A,T) :
(i)
(i
If
then "
1
^i>"
* "B Jt r; w
(0
If... ) . . .< i J I | . 1 / X J | | - 1 »" **
,*0>..
where ^ ^ . . . v ^ ^ ^ o m.y Let s(k ) denote the formula y=v. (xi) let Vy<|)Cy; Jbe a single II axiom for R together with the axiom; then D(i,x) =* "(j>C< i,x)) "; (xii)
D(kQ,xo);
(xiii)
"
(xiv)
" < k
o
"Bk({k0,x))"
,
o o l
« B^x/
acceptability
29 (xvi)
"€< *0/y>" =*• (3&y) ("
Let s(k ) be the formula (xvii) (xviii) (xix) (xx)
i,x>");
y=v ;
D(iklf0)); D(iirx))
«> "< i,x)=h(i,(
< kn,x),( 0 t i , x ) € T « * "
kn fO) )) " ; 1
).
The reader should check t h a t < VP,B . . .B N ,A P ,T P >|=MC. We s h a l l prove the following converse. Lemma 3 . 2 6 . Suppose MC holds. there is an isomorphism O'zCV9 )N^(vfB - 1 - 1 TTC7
Then there
O:( (V^)M, (Tp)M^V
is a class
t^RA and p€M such
and $=V=h(upUip}) / furthermore
. . . B ,A) and rif=V=h(up[){p'}) then there Ik
that if
is i!:M=N_with Tt(p) = (p') and
= 0 ' .
Proof: L e t M f = { < j , x > : D ( j , x ) } .
Define a r e l a t i o n I on M1 by
« "
By ( i i i ) and ( i v ) I i s an e q u i v a l e n c e r e l a t i o n . L e t M=M'/I and l e t [ j , x ] d e n o t e some member of t h e e q u i v a l e n c e c l a s s of < j , x > . Say [i()fx0]E[iirx1]
~
"
B^([i/X]) « " B k « i , x » " . Then E, B^. are well-defined by (v) , (vi)k- Let M=< MfE,B^, . . .B^. >. where <$> is E,. Proof: By induction on structure. Atomic formulae are immediate from the definitions and (ii) . - follows by (vii) and A by (vi'ii) . If #3y<M[i o ,x o ]...[i m _ 1 ,x m __ 1 ],y) say ^
([ ±QrxQ] .. . [ i ^ x j ) . Then by
(ix) "3y<M...,y)". Conversely if "3y<|> « i Q ,x 0 >.. . • • • ^ m - l ^ m - l " " t h e n s u p P ° s e "•«io'xo>---
•(Claim 1)
By (ix) M|=R. Define a map a:V->M by a(x)=[k , x ] . By (xii) a is well-defined and by (xiii)-(xv) a:V=M|rng(a). By (xvi) rng(a) is an E-initial segment of M. Hence M is a model of R^ and by (ix) M(=RA.
Let e=(p) M , p = [ k l f 0 ] .
Claim 2 a"On=u)£. Proof: Suppose (x)^ca(y). Let ACE-^M) be such that Ana(y)^M. Suppose A « (J)(^f [i,x]) . Let a={ C
~ "(t)«ko,a
So Afla (y)-o (a) . Contradiction!
(claim 1)
30 Suppose t h e n t h a t Observe
a"OnczcoY€cop. By ( x v i i i )
M)=V=h ( r n g ( a ) U{ [k^O]]) .
that
< i,<$>>€A ~ < i,<£>>€T
(by (xx) )
"c()i(
~
~ M(=cj)i(a(?) ,£)
(by (xix)) (claim 1)
~ < ±,o(t) >€T^ A
AP
~ a(Ci,oȣAP. A P
So M(=rng(a)cJA
A
A P
(J* is a set in M as y€p) . But there is f E E ^ J )cM
mapping coy onto
j
so M}=V=h (coylKp}) . HencG there is a £-,(M)
map,
g say, of a subset of coy onto M. Let A={£
seen t h a t
< i , x > € T => a (< i , x » £ (T p ) M
S i n c e M|=V=h (oopu{j5}) , Mf=RA left
(as in claim
to the reader.
Note t h a t
Definition
s d a : V=< M p , (T^) M >.
2 ) . The u n i q u e n e s s
claim i s
o
a l t h o u g h MC i s t e d i o u s
to state
i t has a single
II, a x i o m .
3 . 2 7 . MC is the theory MC;
Given MC , ri>0, define MC , as follows: Given a structure ( M,B_.. .B, fA) n n+1 — 1 k define a set T from A by the definition of lemma 3.24. Let Vyij;fyJ be the II sentence
asserting
that
MC+"MC "+ Vi,x(D(i,x) n
(M? > is amenable =• "\l)(
.
(where I|J is T..). Then MC _ is 1 n+1
Exercises 1.
Suppose t h a t in definition
3.15 F.. g . . .F, 7
Show t h a t corollary 3.19 would s t i l l
+ N
had been omitted.
hold.
2. Show t h a t lemma 3.16 i s not a theorem of R . CO
3. S u p p o s e TT:M-*£ N c o f i n a l l y a n d < M , T > is a m e n a b l e . L e t T' = = U Tr(xflT). S h o w t h a t TT:<M,T>-* < N , T ' > a n d < N , T * > i s a m e n a b l e . x€M Lo 4.
R e p e a t e x e r c i s e 3 f o r TT:M-*-V N . 2J2
5. Use MC to formulate an iterated version of lemma 3.26. n 6.
Suppose P ( 5 ) n J x * P ( 6 ) n J x + 1 ,
also that either
6€cop. Show t h a t coA+6 e x i s t s . Show
sup{coX+6: 6€cop} i s bounded in On or 06P.
31 4: MODELS OF R
I t i s more c o n v e n i e n t i f we use ZFC a s our b a s i c t h e o r y i n t h i s chapter. D e f i n i t i o n 4 . 1 A model M=(M,E,A . . .A > of R is standard provided (i) if M' is an initial segment of M (that is, x€M' and yEx => y€M') and EO(M')2 is well-founded then M' is transitive and Ef)(M')2=e0(M')2; (ii) U3+1 is an initial segment of M (or On =U) ; . Lemma 4 . 2 . if $=R is standard then M^=R . Proof: Suppose Mf= n i s a non-empty l i m i t segment of a>. Then n i s a non-empty l i m i t segment of u . So n=w . So M(=n=u>. D By c o n s i d e r i n g o n l y s t a n d a r d models we s h a l l n o t be embarrassed by the l o g i c a l l y complex axioms of d e f i n i t i o n 2 . 1 2 . The n e x t lemma i s a form of t h e Mostowski c o l l a p s i n g lemma: Lemma 4 . 3 .
Suppose t£=R and let
Jf is isomorphic
to a standard
z={n.-M^n6u)}. If Eftz
is well-founded
then
model of R.
Proof: Set T(x)={z:zEy , some n} where Mf=y =Unx. Set Z= ={x€M:T(x)2nE i s well-founded.} Z i s an i n i t i a l segment of M. For if x€Z and yEx then M^ycUx so for n€oa MJ=UnycUn+1x, hence T(y)cT(x), so T(y)2flE i s well-founded, i . e . y€Z. Z PIE i s well-founded. Suppose AcZ,A:t:0. Take some x€A. Let A'=T(x)nA. If A'=0 then yEx -» y€T(x) -» y$A so x i s E-minimal in A. If A'*0 l e t y be E-minimal in A 1 . If t€A,tEy then since y€T(x), t€T(x); so t€A'; c o n t r a d i c t i o n ! Hence y i s E-minimal in A.
ir:< z 1 , e n z | 2 >=< z,Enz 2 >. If (M^Z)nz'*0
(4.1)
replace M^Z by an isomorphic
copy disjoint from Z 1 .
Set M'=Z'U(M^Z). Let TT'(x)=7r(x) if x€Z', x otherwise. Say xE'y <=» (x,y€Z ' Ax€y) v (x€Z ' Ay^Z ') v (xryf Z ' AxEy) . We complete the proof by showing that <M',E' > is standard. N is an initial segment of Mf and N
is well-founded.
Suppose
Let N ^ T T " ^ .
32 N 1 is a well-founded initial segment of M': for if x€N, zEir1 (x) and z=7Tl(zl) then z'E'x so z'€N; hence z€N. Suppose x€N* . Then zET(x) => z£N'; so T(x)2flE is well-founded, so x€Z. Thus N'cZ, so NcZ', giving the desired result. Finally we are told that EDz
is well-founded, so ir:o)=z. If
Mf= " OJ exists" then M'|="u) exists". But E'n(a)U{oj})
is well-founded
1
so a) is a) in the sense of M . Thus OJ+1 is an initial segment of M 1 .• Next some terminology. Generally speaking t M(y,...y ) denotes that y such that M)=y=t (y. . . . y ) . The M may be a subscript or a superscript as convenient. For classes there is a small problem. Suppose n is a class of M defined by <$>. The natural choice for n
would be {x:M^=<j) (x) } .
Admittedly inside M we have written x€n - which should be read xE TJand now we are writing x€n in the real world. But x€n is only a convention with classes, whereas classes of M are sets in the real world, so that there is no ambiguity. Ambiguity does arise, though, when a class of M happens to be a set of M. In M we identified n with a set; in the universe the corresponding set is {x:xEr|}. Really this causes no trouble and we only mention it to account for some apparently bizarre uses later on. Three conventions: firstly the use of €., is restricted to cases where M is standard. This is handy when both a collapsed and an uncollapsed model are around together. If M is not standard we must explicitly give a name to its membership relation: it will usually be E. Secondly, we do not write vJJ^ but simply N n ^. If n=0 this is unambiguous as V =N. Finally, to avoid cumbersome expressions we do not underline structures that occur as subscripts and superscripts so that, for example, p N denotes p.,. Lemma 4.4. (The condensation lemma)
Suppose x-
—^——————
LT~
model of R. There is a standard
model M_ of R and a map TT with
r
n:M=NJX. If X is
a Em substructure of — N then in addition if:M+ — vL N.— P r o o f : R h a s a s i n g l e n 2 a x i o m s o N|x|=k. A l s o OJCX; s o t h e lemma may be p r o v e d by a p p l y i n g lemma 4 . 3 t o N | X . Lemma 4 . 5 . (resp.
If $=R
(resp.
RA) then f£=R
RA).
Proof: R 4.2,
Suppose TT:M+yN with M_,N_ standard.
•
i s IU a x i o m a t i s a b l e
s o Mj=R . S u p p o s e N(=RA. M^=R
and t h e a x i o m o f a c c e p t a b i l i t y
i s TI2 s o M^=RA.
There i s a l s o an upward form o f lemma 4 . 5 .
•
by lemma
33 Definition
4 . 6 . TT.-JV-^ cofinally
Lemma 4 . 7 . J f TT;JV-VV cofinally
provided
ir.-tf-^tf and Vx€w3y€tf tf[=xe7r(t/; .
then ir.-iv^N.
P r o o f : S u p p o s e N^=3x<J> ( x , TT ( Z . . ) . . . TT (Z ) ) w i t h 4> E Q . S u p p o s e N^4)(X,TT(Z1) . . .Tr(zn))
a n d NJ=x€ir(y) . T h e n N^3X€TT (y) <J) ( X , T T ( Z ; L ) . . . 7 r ( z n ) )
so N|=3x€y<J> (*r z ± . • . z n > • T h u s H=3x
4.8.
If v.-M+^N cofinally
and t£=R then
a
$=R.
Proof:Use t h e f i n i t e axiomatisation of chapter 1. E x t e n s i o n a l i t y and foundation a r e IL, so they hold in N by lemma 4 . 7 . Suppose u,v are in N; we have t o show t h a t N^F^UjV) e x i s t s
for 0
R i s RK. Suppose NJ=U€TT (U 1 ) ,V€TT (v 1 ) . Then J^=F i "u l x v t e x i s t s lemma 1.7.
Say
M(=w=FiIIul
f
by
1
x v ' . Then M(=Vx€u VyEv 3t6w t = F ± ( x , y ) . So
Nf=VxeTr(uf) Vy£Tr(v') 3t€7r(w)t=F i (x,y) . In p a r t i c u l a r NJ=3t t = F ± ( u / v ) . a Lemma 4 . 9 . If TT;#-* tf cofinally
and irro) -HO T onto then if d=R there is a
standard Nff=i? with a.-N'=iV_ and a l - f J '
cofinally.
Proof: By lemmas 4.3 and 4.8. Lemma 4 . 1 0 . If M_,N_ are standard then NJf=R
(resp.
Proof: N(=S
a models of R,^:M^^N cofinally
RA) .
e x i s t s for c o f i n a l v in On.,, hence for a l l v€0n
x in N, if Nj=x€7r(y) and M|=y€Sv then N^TT (y) ES^ , * Nf=R
and $=R+ (resp. RA) Given
(this i s Z^
so
as N is standard. For N(=RA observe that the axiom of
acceptability restricted to X+a)€On is IL: so let A be the largest limit ordinal. Let 6n be least such that for some ac6,a€S,, , ais,. ~~ A"i~n A 6 =7r B u t if f Then 6n€rng(iT); say n (\)satisfies the acceptability axiom for U=S,JT-1 ,^* + n , 6=6"n in M then ir(f) satisfies it for u = S ^ + n , 6=6n in N. This suffices. Lemma $=R+
4.11.
a and ^=R+ (resp. RA) then
If M_,N_ are standard models of R^M^^N
(resp.RA) .
Proof: All axioms are IU.
n
EXTENSION OF EMBEDDINGS Lemma
4.12.
isomorphism) Proof: are
If r(:Mh^ylr and N^=RA is
with
< N P , T P >f=RA+MC.
unique
standard
then
there
M,p' with
L e t T = { x € M : T P ( ir ( x ) ) } ; Mp'=Mf
s o <M,T>|=RA+MC
Tp =T. T i s unique
Note: E, was only needed to ensure <M,T>(=R .
x
are M_,p' (unique
up to
Mr =M_ and Mf=V=h(u>pUp') .
by
a
and
3.24(iii).
there
34 T h e M in lemma 4.12 m a y b e taken a s standard. It will b e a m o d e l of RA . P Lemma
4.13.
Suppose M_,N_ are standard models of RA . Suppose Tt:l£**v, f£ and
f^=V-h(UiQ\Jp') . Then there is a unique T? such that TT.-tf+ E
and
^(P')=P' Also
.-^-J, W. P
Proof: By lemma 3.24 TT:< M P * ,TP'> -*
..(4.2)
...h(in,))«hN(if
f
p ».
This is well-defined since M=vf=h(a)pUpf) ; and by (4.2) TT:M->£ N. We must show TOTT. Let s(j o ) be the formula y=x; then h (j <x,p* >)=x, h N (j Q ,
TT (p')=p. Take y€M and suppose ^=y=h(i,< x,pf >) with x€M p . Then N^TT 1 ( y ) = h ( i , < TT1 ( x ) , 7 r ' ( p 1 ) » = h ( i , < TT(X) , p » = i f ( y ) .
D
In fact we can improve this result if TT is a stronger map.
Lemma
4.14.
Suppose
TT.-VP •*•-. N^ where
P^v=h(up\Jp'),
and N^=V=h(up\Jp) .
Suppose
h
Ihm,
7 r : ^ v N and Hfp')=p. Zo
Then 7T;/f>v
N.
~ h+i
Proof: Suppose <J> is a E. + , formula. For def initeness take h odd: so say (\> •• 3x 1 Vx 2 . . . Bx^
where ^ is II- . Let
D={t j,y >:MhJ€o) A y€ M P '
A
h(j f
D={< j,y >:N|=j€a) A y€ N P
A
h(j,
Say R(x",z) •» ^=x±=< j ± ,x^ >€D A z ^ k ^ z M C D
exists}
(4.3)
>) exists} A
A ^ ( h ( J 1 , < x ^ p t »...h(j h ,<x i ; / p' » / ^
...h(k n ,
Define R s i m i l a r l y from N,D,p. Then M|=(j)(h(k1/
M
p l
so there is a A, formula x such that
|(z) .
(4.4)
And there is a A, formula 6 such that M(=xeD *» MP'(=<5(x) . Let x'( z ) ^ e
tne
formula
(4.5)
35 (4.6)
3xi(6(x1) A Vx2(<5(x2) => ...3xh(6(xh) A X ( X , Z ) ) (4.6) is is Z h and ^(h(kir<2^p' ». Similarly for N. Hence n
n
<* N P j= X <7T(z|) , p » . . . h ( k But
if(h(kir< z^,p» »)=h(k
Lemma 4 . 1 5 . Then there
Suppose
±
M, iv are standard
are JV, p, unique
n
,
, p » .
< TT(Z|) , p » .
D
models of R and TT;^ +V iv
up to isomorphism,
such that
cofinally.
N^^£ and N^V=h(wp\Jp) .
Proof: By lemmas 4.10 , 3 . 2 6 and c h a p t e r 3 e x e r c i s e 3 . n Lemma 4 . 1 6 . conclusion
Suppose M, If are standard
of Lemma 4.15
models of R and TT.-i^ ->-v N. Then the
holds.
Proof: By lemmas 4 . 1 1 , 3.26 and c h a p t e r 3 e x e r c i s e 4 . o Lemmas 4 . 1 2 - 4 . 1 6 a r e c a l l e d t h e e x t e n s i o n of embeddings lemmas. SOUNDNESS In order to iterate the extension of embeddings lemmas we must first look at the notion of soundness. Definition 4 . 1 7 . M is p-sound means $=v=h(u>p\Jp) . M M Suppose p-sound is defined for all p€.PA . Let (p....p _ )€PA ,._ Then n i n+i n+x . M is p-sound provided M is (p^-**p )-sound and M l " n is p .-sound. ~ — I n — n+1 Lemma 4 . 1 8
Suppose
lk=RA is p-sound.
Then t&=RA and
p€Pu-
Proof: L e t f€E,(M) with p a r a m e t e r p be such t h a t rng (f "up^) =P(On ) PIM Let A={^: £$f (£) }; A€£,(M) with parameter p . Suppose APloop =xntop w i t h x€M. Assume xcOn . Then i f x = f ( c ) , C€u)pM we have
Contradiction!
n
A similar proof shows t h a t if V=h(yU{p}), any p, then o)pcy. This was used in lemma 3.26. Lemma 4 . 1 9 . only if there
Suppose # is p-sound. is AS2h+1(M)
Suppose B£(wp)<(A). Then B isZ^Np)
with parameters
from pllfa)p;
if and
B^AOf^ (h>0) .
Proof: (in RA) F i r s t l y suppose A€E h+1 and B=Afl (cop)
36 x , p » ) «> V p (= X (
Z1(VP).
There is a E, map of some y€iop cofinally into On.
Call the map g. Suppose x€A P «=* 3y\|j(y,x,p) where i> is E Q . Say (f>(v,x) ~ (3y€Sv)i|;(y,x,p) . Obviously it suffices to prove the result if B is E Q ( V P ) . Furthermore, letting A'={< v,x ):\\) (v,x) } , since A p is rudimentary in
,A' >we may assume B is rudimentary in
is a rudimentary function F such that
(4.7)
Hence it suffices to prove that the function a(u)=A'nu is E 2 In fact it is IIlf for y=a(u) <* Vz(z€y «* A 1 (z) A Z € U ) Case 2
(4.8)
There is no E, map of y€iop cofinally into On.
Claim If H is E_ and u€V p then ——^— (_) Vx€u3yHxy => 3vVx€u3y6vHxy. (4.9) VP Proof: Suppose Vx€u3yHxy. Suppose u€S , y a limit, and suppose yP yP Y f:y+S
is E.(S
) and onto. Define g:y-K)n by
g(v)= the least y such that 3yGS Hf(v)y if f(v)€u = 0 otherwise. Then g is £,. So rng(g) is bounded in On;say g"ycy'€On. Then v=S , satisfies the claim.
•(Claim)
Now as in case 1 we must show y=a(u) ~ Vz(z€y « A P ( z ) A Z € U )
(4.10)
to be E 2 . (Vz€u) (Ap(z) => z€y) is certainly 1^. As for (Vz€y) (Ap(z) A Z € U ) , suppose A p (z) ** 3tip(t,z,p). By the claim (Vz€y) (3t) (i|;(t,z,p) A Z € U ) « (3v) (Vz^y) (3t€v) (^(t,z,p) A Z C U ) ; and this last is 2^. So y=a(u) is E 2 . Now an easy induction gives L e m m a 4.20. if
and only
if
D
Suppose M is p-sound, p£PAM. Suppose Bcru)p";
that
M
B=AOffp. (h>0) . Corollary 4.21. definable
Suppose M_ is
from parameters
in flop ) M
p-sound Up.
with p€.PA . Then every x in M_ is E
37 Now we a r e i n a p o s i t i o n t o i t e r a t e t h e e x t e n s i o n of embeddings lemmas. Lemma 4 . 2 2 , Suppose N_ is a standard MjP* unique up to isomorphism
model of R and TT.'AHy N_ . Then there are
with M==M_
and Af
Proof: I t e r a t e lemma 4 . 1 2 . Lemma 4 . 2 3 . Suppose M,N are standard Then there
is a uniqueitti
p'-sound.
D
such that
models of R and Tf:My ->•_ N_ , M
Lemma 4 . 2 4 . Suppose i\,M_,N_,"n,p,p' are as in lemra 4.23 and in addition p-sound.
Then TT-^Y ^ ' Provided n+h
that
f
Then there are N_,p unique up to isomorphism that M_ is p'-sound)
np
U:M
Lemma 4 . 2 5 . Suppose M_,N_ are standard (provided
N_ is
ip
•+•_ lf . h
models of R and if:tf*P •+•„ N_ co such that N=i^
and N_ is
finally.
p-sound
.
Proof: Use lemma 4.15 to get the f i r s t thereafter. Definition
p'-sound.
Tf(p')=p and T[\M m:M^Pm+y /r^Pm for all m
step and lemma 4.16
o 4 . 2 6 . Suppose TT.-M -> N cofinally
and M_ is p-sound.
TT:/f*v, N_ is the unique map of lemma 4.23. TT is called
the n-completion
Suppose of TT to M_.
In fact the n-completion depends only on M and TT. For suppose is the n-completion of Tr:Mnp->v N" and suppose M is p'-sound
TT:M-»V N p
and TT:M
^
N 1 where N^N 1 . Then it suffices to show that N is
7r(p')- sound and N ' = N n
p
. We may restrict ourselves to n=l. Then
since M is p'-sound we may assume p=h..(i,< £,p' >) (iCa),^€a)p ) so 7r(p)=h._ (i,< TT(^) ,TT(P' ) >) , TT(^) €a)p.T . But N is if(p)-sound so N is r c ^ r N N — — 7r(p') -sound. ^ 1 p To show that N ^ ^ ' ^ it suffices to show that TT:< M ' ,A P ' >->„ — — M Zo Let y=A p fix. Then V i , z ( < i , z > € y •• V^
A€x)
«• N ' p ( j ) . ( z , 7 r ( p ' ) ) A < i , z >€TT ( x ) ) , a s 7 r : M + E N ' . T h u s
Tr(y)=AjJ (pl) mr(x) . In fact 7r:M->N
is the unique TT ' :M-> N * such that n (a) every y in N* is E definable with parameters from (b) TT' "wp
THE CONSTRUCTIBLE UNIVERSE J i s t h e unique t r a n s i t i v e model M=(M,€> of R w i t h OnM=a. We may deduce a l l t h e u s u a l f i n e - s t r u c t u r a l p r o p e r t i e s of J from
38 our previous work; the following is the main result: Lemma 4.27. For all a jJ=RA+. Proof: By induction on a. Suppose it true for all $
have t o show
Since ac60. If u)p >6 for all m then for some p a€E, (Sa)a p ) and ajp cn-lp>6 S 1 S toa1 ~ coa so a^S^ icS . Thus a)pg_<6 for some m. So it suffices to show Claim For all m there is
TT:M=S
with M=M by lemma 4.22. Then V J wa ^ |'x . Let TT:M-> —E * m —a A€I (M). But M=J O some 3<wa and a^S so 3=wa. M is-rr (p )-sound; TT (p )
. / P >-sound.
Corollary 4.28.
a(Claim)
i\=GCH
P r o o f : L^=the power s e t a x i o m . T a k e a s u c h t h a t Ja|=P(Y)=Y+ b y c o r o l l a r y theorem.
3 . 4 . S o i n L P(y)
P(y)€J
. Then
s o P(y)=Y+ by C a n t o r ' s
D
Definition transitive S
n
4.29.
J^ denotes the unique model <«,€,!'> of R* which is
and has On =taa , A!=Aj)M (0
These definitions
are unambiguous provided i t i s clear that we
are working in ZFC and not in some model of R. In a model with predicates, M=<M,€M,A> —
J
denotes a model with the same predicates.
—^
M
If there is any danger of confusion the l a t t e r must be indexed J . Definition
4.30.
Models of RA are called acceptable; of RA
strongly
acceptable.
Exercises
1. Suppose 7r:N-*£ M where N,M are standard models of RA. Do either of (a) p€P N *1TT(p)€PM; (b) 7r(p)€PM => p€P N
39 necessarily hold? 2.Show that there is a non-standard model of R. 3. Suppose M,M' are standard models of R. Suppose 7r:M+ and <M,A> is amenable. Show that there is a unique A TT:<M,A>+
1
M 1 cofinally
such that
<M' ,A* >.
4. Show that if N=J
then N n p = J n for all n€u>. PN
5. Say rud+(M)= the closure of MU{M} under
F
i'"Fi5+N«
Show that if <M,A>|=R+ and M is transitive then if M'=rud+(M) and M'=<M',e,A>, then M'f=R+ and M=s5?' .
40 PART TWO: NORMAL MEASURES
In this part we examine Kunen's theory of iterated ultrapowers. Most of the non-fine-structural apparatus is developed here; many important applications are deferred to part three, where finestructure is reintroduced. Much of our subsequent work could be done using the iterable premice developed in chapters 5 and 6. Indeed the core model will be seen to be the union of those iterable premice whose projectum lies at or below their measurable cardinal; and the existence of 0 # is equivalent to the existence of an iterable premouse. Nevertheless we shall prefer to use "mice", which are indeed iterable premice, but which satisfy a weaker condition on the projectum than that stated above. Reasons will be given at the appropriate point. Generally speaking the message of this part - especially of chapter 7 - is that if N is a premouse with critical point K then nothing that affects P ( K ) is altered by iterating N. The reason why we might nevertheless want to iterate N is supplied by lemma 8.18; iterating restores to premice the L-like simplicity of levels of construction where a<$ **> J =J 8 . In part three we shall see that we are still living in a reasonably L-like universe.
41 5: NORMAL MEASURES AND ULTRAPOWERS
The dominant theme of studies of large cardinals has been the existence of embeddings of the universe into itself. Large cardinal axioms originally formulated in other terms have been translated into statements about embeddings; and these have revealed their connection with other axioms. Measurability is one of the best examples. The original definition was motivated by classical measure theory. Early results proving measurables inaccesssible were purely set theoretic, with no "model theoretic" methods used. Scott used an embedding equivalent to obtain far stronger results - including the absence of measurables in L. From our point of view, as in recent applications of forcing in large cardinal theory, the embeddings are central. Definition
5.1
Suppose j:#*v. N where M, N are standard models of R. — Lo—
Suppose that € 0(j"K)
is an initial
If wj=£<jfK; , then K is called then K i s the smallest Definition
5.2.
— —
the critical
K such that
^
segment of 6^ and £=sup (j"K)
exists.
point of j . (If M_,N_ are
transitive
j(K)>K).
K is measurable provided K is
the critical
point of some
j:V+ M, where M is an inner model.
Note t h a t d e f i n i t i o n
5.2 i s made in ZFC; o t h e r w i s e "measurable"
not d e f i n e d . Also note t h a t d e f i n i t i o n
5.2 i s i l l e g a l a s
q u a n t i f i e s over proper c l a s s e s . A l e g a l e q u i v a l e n t i s provided Until further
is
it later.
n o t i c e K i s a fixed measurable c a r d i n a l and
j:V^ M with K c r i t i c a l , e Lemma 5 . 3 . K>W Proof: j(co)=o) and j ( n ) = n , a l l n€u). Lemma 5 . 4 .
o
K i s a strong limit
Proof: Suppose y
acy then j ( a ) e j ( y ) = y ;
3€a «
j(3)€j(a)
~ B€j(a)
and for 3
onto.
42 so
j(a)=a.
Suppose
of
course.
So j ( K ' ) = j ( f ) ( j ( a ) ) ,
Corollary
Lemma
5.5.
5.6.
Proof: Suppose
K is a
Kis
Suppose
K=j(f)(a)
with
a€PM(y).
i . e . K'=j(f)(a).
Kf=f(a); K'
Contradiction! D
cardinal.
regular.
y
cofinally.
j ( f ) ("3) > K , 3"
3'=j(3I)=j(f)
Suppose
Then
j (f) : y * j (K)
cofinally.
Then
(j("3))
=j(f)(3)
>K
>3'. Contradiction!
•
Corollary 5.7. K is strongly inaccessible. For a long time it was an open problem whether K might be the least such. The following lemma shows that it may not. Lemma 5.8. K is not the smallest strong inaccessible. Proof: Since K is strongly inaccessible it is strongly inaccessible in M. If K were the smallest strong inaccessible then M(="J(K) is the smallest strong inaccessible". But K<j(K) . Contradiction!
D
There is a direct proof that V*M (see corollary 24.4); but we will come upon a form of this result as we proceed with our alternative characterisation. NORMAL MEASURES Definition 5.9. Suppose f^=R. U is a normal measure on K in M_ provided (ii) xEu A XOY, ye? (K) => YEu (Hi) (i)'(iii)
XEU A YEU + characterise
a
filter.
(iv) XEU v KNK€[7, for all
xEPtK)
M (i)-(iv) characterise an ultrafilter. (v)
43 Such an ultrafilter
is called
K-additive
- the influence
of classical
theory shows through in the terminology - and a K-additive ultrafilter
is called
(viii)
measure
non-principal
a measure, or a two-valued measure.
Suppose (X :y
(in M) a sequence with X €.U for all Y
then {6:(VY<6)6ex }£u. {5; CVy<&)<S€x } is called
the diagonal intersection
of (x ;6
There are redundancies in t h i s l i s t , of course. Some clauses are inserted merely for the intermediate d e f i n i t i o n s . Note t h a t there is a II, formula < > j such t h a t whenever <M,U>f=R we have: U i s a normal measure on K in M «* < M,U )\=<$> (K) . (5.1) We do not i n s i s t on <M,U>j=R as p a r t of the d e f i n i t i o n of normal measure, however. Note t h a t K€U (sincetf>$U); t h a t Y
6
Let
(i)
Suppose K is measurable. Then there is a normal measure on K (in V) U={X€P(K):K€J(X)}.
Immediate.
(ii) (iii) (iv)
K€j (X)
A
XcY => K€j (Y) .
j(XflY)=j(X)nj(Y) J(K)=J(X)UJ(K^X)
(v) K^j(0) . (vi)
(vii)
K { J ( { Y } ) = { Y > (Y
Suppose K^j (X ) , a l l Y<<$. Then j ( D X ) = n j (X ) a s <5
so K € J ( n x ) .
Y
^<5
Y
^
"
Y<6 Y (viii) Suppose KGJ (X ) , all y
But (VY
D
The converse to lemma 5.10 is one of our essential tools. That is, we shall obtain from U an embedding j:V-*eM. A word of warning, though: this procedure is not an inverse to that of lemma 5.10; if we start with j and let U={X€P(K):K€J(X)}, and then obtain an embedding from U we shall not necessarily return to j. Cases where this fails are encountered in part six. D e f i n i t i o n 5 . 1 1 . Suppose f^=R+AC is standard. Suppose j:M^y W with K Suppose U is a normal measure on K in M_. Then j ••#""*"# means (i) For all x€N, there is fOi, f:K+M such that $=x=j(f)(&) where
critical.
44 For all x£?M(K) M N_ is called the ultrapower (ii)
Suppose
x£u ** of M_ by U.
jrM-^N.
Lemma 5 . 1 2 .
j:H+v N
cofinally.
— Lo —
Proof: Suppose x€N. Say x=j (f) (£) with f€M, f:K+M. Suppose MJ=y=rng(f). Then so in p a r t i c u l a r N(=x€j (y) .
Corollary
5.13.
j--^v N_r f^ t->\
Proof: By lemmas 4.7 and 4 . 8 .
a
Suppose from now on t h a t N i s s t a n d a r d . This we may s a f e l y do a s M N i s standard/
and K>CO ( s i n c e £ cannot be w ) .
Lemma 5 . 1 4 . Suppose j':M+ N_'. Then there is an isomorphism O:N=N_' such
that
Oj=j' ,0(&)=&', where ^'\=&'=sup j " K . Proof: F i r s t of a l l o b s e r v e
that
Nt=JU) ( f c ) = j ( f ' ) (fc) ~ N ' h j 1 ( f ) ( f c ' ) = j ' (f ' ) (l^ 1 ) .
For
and
f
(5.2)
^
s i m i l a r l y f o r N 1 . B y t h e same
argument
N(=j(f) (f5)€j(f ') (g) <=» Nf|=j f (f) (($ f ) €j f (f f ) (^f) N|=A k (j(f) (£)) ** ^ ' ^ ( j
1
(5.3)
(f) (£')) .
Definea:N-vN' b y a (j (f) (£) ) = j ' (f) (£ ') . B y (5.2)-(5.4)
(5.4) this is a n
i s o m o r p h i s m . G i v e n x € M l e t c : K-»-M b e defined b y c (£)=x, a l l ^ < K . T h e n j ( x ) = j (c x ) (1^) . S o a(j(x))=a(j(cx)(«)) = j ' (c x ) (l^1)
Half of the above argument shows Lemma
5 . 1 5 . If j':n+ir with K critical and x£u «* (^'€j' (x) then there is
a;tf-ȣ N' such that Oj=j'.
T h i s g i v e s a " u n i v e r s a l " p r o p e r t y of j:M+ N . T h e a b o v e r e s u l t s w e r e u n i q u e n e s s a s s e r t i o n s : w e a l s o need a n existence
theorem.
45 Lemma 5 . 1 6 .
Suppose U is a normal measure on K in f^=R+AC, Then there
are
W,j such that jiMP-yfl.
Proof: Let oMf£M: f:K-*M}. Suppose f,g€T. We say f~g ~ {£:f (C)=g(^)}€U fEg « U :
(5.5)
Then ~ is an equivalence relation on T and a congruence with respect to E and A, . Let T=T/~ and define [fjE[g] « fEG (5.6) A R [f] ~ A k f where [f] is the equivalence class of f. Claim 1 For any £ Q formula <j> < T,E,A >f=cf> ( [f^] ... [f^]) «* {^:<|)(f1(5) . . .f n (?) ) }€U. Proof: By induction on E Q structure. Case 1 <j> is atomic. This is immediate. Case 2 $ is -ij;. Then < T / E / A H ( [ f 1 ] . . . [ f n ] ) «* < T , E , A ^ ( [ f 1 ] . . . [ f n l )
Case 3 (|) i s
I|^AX.
Then
** < T,E,A >H ([ f ±] . . . [ f R ] ) ,X (
Case 4 <j> is (3v.€v.)if> If < T f E , A ^ ( [ g ] , [ f 1 ] . . . [ f n l ) A [glCEfjlthen
j
Conversely suppose {^: 3v ± €f ^ (^)i|;(vif f x (?) . . .f n (5)) >6U. Let g(^)={x€f j (^):^(x / f 1 (^)...f n (C))>. Then g is a set in M. Since M^AC there is h in M such that Mt=h(S)€g(S) whenever g(^)*0. h:K^M. But U:g(£)*0}€U so {^:h(5)€g(5)}€U. Thus A i|;(h(5),f1(5)...fn(C))}€U so j A ^([h],[f1]...[fn]) o(Claim 1) Note 1: If M[=ZFC then g would e x i s t even without the bound on x. Hence claim 1 would hold for a l l cj>. Note 2: Claim 1 only u s e s the f a c t t h a t U i s an u l t r a f i l t e r . Recall the d e f i n i t i o n of c from lemma 5 . 1 4 . Let j ( x ) = [ c ] . Let N=< T,E,A>. So j:M+
H
N. For i f <J> i s EQ then
46 ^ ..xn) }€U
(by claim 1)
« M|=c|)(x1...xn) If M|=ZFC then j:M+ N. Claim 2 K is the critical point of j . Proof: First we must show that J"K is an initial segment of On.,. That is, if N|=x<j(3) and MJ=3
fiIUftXft,€U;
p
hence for some 3'<3
Xft(€U. That
p
P
is, N)=[f] = [ c 6 , ] , i.e. x=j(B'). We shall now show that if \ is id|K then [i]=£=sup J " K . Clearly if 3 < K then {£:3
X€U «* Nf=[ i ] €[c x ] .
Proof: X€U «* {^:^€X}€U. Claim 4
D (Claim 3)
N|=[f] = [c f ]([i]).
Proof: {^:f(C)=f(?)}€U.
a(Claim 4)
Hence j:M-> N.
D
Note that we can always replace N by an isomorphic copy in which 7r|K=id|K and [id|i<]=K. Unless we specify otherwise this is assumed from now on. Lemma 5 .17 . Suppose U is a normal measure on K. Then K is measurable. Proof: Note first that Ooo; OJ cannot carry a normal measure. Let j:V-*M. Then j:V-> M and K is critical. Take M standard. By the Mostowski collapsing lemma it is sufficient to show that M is well-founded (clearly for all y€M {x:x€ y} is a set). Suppose M were not well-founded and <x :n€a)>a sequence with x
€
n+l Mxn'
a11
n€a)
"
Then
su
PP°se
x
= n
J
Let X= n X ; then X6U, as K>O>. Take n€w n f n + 1 ( ^ ) € f n ( ^ ) ; contradiction!
^£X. Then for all n •
Now we give some computations in ZFC that are needed later. Suppose J V M (2K)M<j(K)<(2K)~h.
Lemma 5.18. K
M
Proof: ( 2 ) < J ( K ) as MJ=j (K) is a strong limit. But j (K) ={ j (f) (K) :
47 :
f:K-><} so J T K T £ K K = 2 K . Hence J ( K ) < ( 2 K ) + .
D
Corollary 5.19. V*M
Corollary 5 . 2 0 . v+L Proof: The only inner model o f L i s L. Lemma 5 . 2 1 .
D
if cf(\)*K then j(\)=sup j(a).
Proof: Suppose j(f)(K)<j(X). Then {£:f(£)<X}€U. Assume without loss of generality f:K-»-X and let y=sup f"K. If cf(X)>K then y<X and j(f)(K)<j(y) so j(X)=sup j(a). a<X Suppose cf(X)
If X>K and X is a strong limit cardinal with cf(X)*K then j(X)=X.
Proof: By lemma 5.21 it suffices to show j(y)<X whenever y<X. But JTyTlif: f:K+y}=yK and y K £ 2 Y # K < X , as X is a strong limit cardinal. Hence j(y)<X.
•
In particular if X > K is strongly inaccessible then j(X)=X. Lemma 5.23.
if cf(\)=K then j(\)>\.
Proof: Say X=supX ( X strictly increasing). Then j(X)=sup j(X).
^ But
X=sup
a
a
X<sup
a
a
"a
^a
j ( X) < j ( X ) ^ < j ( X ) . a
~
These r e s u l t s make e s s e n t i a l 5.3-5.7
a
K
use of
ZFC; on the other hand lemmas
can be proved in R, giving
Lemma 5 . 2 4 . inaccessible.
Suppose u is a normal measure on K in M_. Then ^ K is strongly
See exercise 7.
Lemma
5.25. •
Suppose
j:M+ N with — U—
U normal
on K in M. Then —
V ,(K)czP (K) . M — N
Proof: This is loosely formulated, and involves an assumption about the relation €.,; the reader should make the formulation N precise. From now on we shall be less careful about these statements because they can become very cumbersome. Suppose M[=acK. Then for y
•
48 If M^=ZFC then equality holds. In general Lemma 5 . 2 6 . Suppose j:tf+ N_ with U normal on K in M_ and <M_,U^=R. Then Proof:
Say a=j(f)(ic).
Then
3€a ~ B€j(f) (K) «
U:B€f(5)}€U.
A s <M,U>|=R { 3 : { £ : B € f ( £ ) } € U }
Definition
i s a s e t o f M.
If #=<#,€ ,uJi)\=R+ is standard and U is normal on K
5.27.
in M_ then M_ is called
a premouse. K is called
If M_=<Mfe^yu>then M_
is called
Lemma 5 . 2 8 .
D
the critical
point
of M_,
pure.
There is a IT sentence
0 such that for all
standard $=R+
M(=a *» M_ is a premouse. "troof:
Use t h e f o r m u l a
C o r o l l a r y* 5 . 2 9 .
If
of
(5.1).
-n:M+_ 2, 0 —N cofinally,
D
M is a premouse and — —N is
standard
then N is a premouse.
C o r o l l a r y 5.30.
If j:M+ N_ and M_ is a premouse then N_ is a premouse.
Therefore we can take an ultrapower of N. This is explained in the next chapter. Exercises 1. Suppose jrV-^M. Show that U^M. 2. Show that if K is uncountable and carries a measure then K carries a normal measure. 3. Suppose jrV+yM with K critical. Show K + = ( K + ) M . 4. Show that if K is measurable then K is the Kth strongly inaccessible cardinal. 5. Suppose K is measurable. What large cardinal properties will K have in L?
(In 1-5 assume ZFC).
6. Suppose U is normal on K . Suppose f:K-M< and {£:f(£)
49 6: ITERATED ULTRAPOWERS
We have just observed that if M is a premouse and j:M+ N then N is a premouse, so that if N=
and maps j :N -> N n + 1 n
where N n = < N n 'u n * • T n e maps may be composed to give 3mn:Mm-**£o N n cofinally whenever m
6 . 1 .
A c o m m u t a t i v e s y s t e m i s a p a i r ( ( A ) . . > , ( IT
"
~ 0 t Ot
o
)
CXp
where A \=R, \>0 and
(iii)
iraa -id|Aa
Definition is a pair
6.2.
(i)
a€A there
Suppose
commutative system that
of a commutative
system
< < - ,< IT g>
for all
Lemma 6 . 3 .
limit that
(X CX^A
————————
such
A direct
> ., > s u c h
^a-Vjii
(iii)
(a<\)
is a<\ and a€A
such
^ , > and —
(X Ot
Ot
that
a=TT (a) .
. > are direct
limits
Ot^A
< , « . , ) . Then t h e r e i s an isomorphism —a ot
of
the ^
O:A=A'
a a _ _ Proof: L e t a(ir (a))=7r ' ( a ) . Claim a i s w e l l - d e f i n e d . Proof: Suppose TT ( a , ) =Ttg (a 2 ) , a£ 3 . Then ir B(iraB(al))"iro(al) =TT 6 (a 2 ) so
ir
a =a ag( 1) 2-
Hence ir^ (Trog (aj^J^iTg ' (a2) , so TTa'(a^^) =iTg ' (a2)
a (Claim)
The claim in reverse shows that a one-one; it is clearly surjective. If h={A,E,A1.. .A N> and A'=< A,E' f^' . . .AN" > then a )E a
V i V 2> - V ^ i ^ ' V ^
just as in the claim, and similarly for A, ,A, ' . So a i s an isomorphism, air =TT ' by d e f i n i t i o n . D
50 Suppose < < ^/^ 1T o^
Lemma 6 . 4 . it has a direct Proof:
If
a commutat
^-ve
system.
Then
limit.
A = Y + 1 t h e n l e t A=A , IT =TT . S O s u p p o s e X i s a
limit
ordinal. A function
f:X+ U A i s c a l l e d c o n v e r g e n t p r o v i d e d t h e r e a<X i s y<X s u c h t h a t f o r a l l 6 w i t h y£6<X f ( 6 ) = i r g ( f ( y ) ) . L e t A* = { f : f:X-> U A A f i s c o n v e r g e n t } . F o r f , g € A * s a y a<X a f~g i f a n d o n l y i f t h e r e i s y<\ s u c h t h a t y<_6<\ => f ( 6 ) = g ( 6 ) . Then
~ i s an e q u i v a l e n c e r e l a t i o n .
Let
A=A*/~.
Suppose A = . Let *^ —a a' a a a fE*g ~ (3y<X) (V6) (y±6<\ => f (6)Egg(6))
(6.1)
A*g « (3y<X) (V6) (Yl6<X => A^g(6)) Then f~f',g~g',fE*g =» f'E*g'; similarly for A*. Let [f] denote the ~
equivalence class of f. Then define [f]E[g] <* fE*g
(6.2)
A k [f] o A * f . Let A=< A ^ ^ j ^ . . -A N >. Define t a :X+ U A X
^<X t^(Y)=O if Y
by
Y
t (y)=7T x aY(x) Y-a where Y<^-/ X ^ A . Define IT :A ->A by TT (x)=[t a ]. We shall show that
<
^'<7rct> < x } If
=wa6(x)
is a direct 6>3 t h e n t ^ (6)=TTa6 (x) a n d t £ ( x ) ( 6 ) =7T36 (7Ta3 ( x a ft ft ^ t»(«)-t^(xj«)8O ^ ~ t ^ ( x ) , i.e. irp(iraB(x))-ira(x).
a£3<X so
Given
and
f€A*
suppose
6>;Y/<S<X =» f ( 6 ) = 7 T
g
(f(y)).
Let
x=f(y)-
) )
Then
Y f-t^ so [f]=-n (x) . x y It remains to show TT :A -*-V A for a<X. This is done by J a -a Eo-
induction on Z
structure.
Case 1 <j> is x=y. Aa|=x=y <» AHr a (x)=TT a (y). =7r
ay(y)/
some y>a.
Case 2 $ i s
But i f
TTa (x) =TTa (y)
then t^~t^
so TT^X) =
So x=y.
x€y.
Aaf=x€y -> AY(=TTay(x)€TTaY(y) a l l
y>a,y<\
If t a E*t a , conversely, then there is y>ct with A (=TTa (x) €TT so x€y. Case 3
*=> A|=cf>.
=
(y)
51 £ a N ~ Z^H
a n d
Aa|=X ~ A ^ and |
f
Case 6 <J> i s If A a H ( y , x 1 . . . x n )
A y € z t h e n A^i|;(7r a (y) / TT a (x 1 ) . . . 7 r a ( x n ) )
A 7ra(y)€
€iro(z).
C o n v e r s e l y s u p p o s e Aj=i|i(iro (y) . i r ^ x ^ . . . i r a ( x n ) ) a n d iTg(y)e i r a ( z ) , <x
X )
^* W l "-
7r
(x
cxe n
a n d Trg (y) C i ^ g (z) s o
) ) SO
A |-*(x 1 ...x n )
a
The proof of case 6 also shows Lemma 6 . 5 . If TT O:A ->V A^ f o r ot<$<X then TT :A ->•„ A for all ot<X. a$ - a Ei-3 a - a Zx Lemma 6 . 6 . If ir O:A ->V A O cofinally 1
for a<$
Otp ~ 0 t Lo —P
• ••
for
01 "~0t 2JO —
—
a<X. Proof: Suppose y€A. y=TTg (y) f o r some $
J f TT O:A ->•„ Ao cofinally ap ~ct Lo ~~P
for a<8<X then A\=R. ~~
Lemma 6 . 8 . If TT O.-A •>- A f o r a l l a<3<X then TT :A ->« A. Otp ~0l 2J — — CX "~0l L — n n Proof: By induction on n. n=O is known. Suppose n=m+l. Then
"~~~~~~~~~~~"^
T T ^ A ^ J , A. Suppose A^=3xip (x,TTa(y1) . . .TTa(yn) ) with \p U^. Say m ^ ( T T (x) ,TTa(y1) .. ,TTa(yn) ) ,3>.a. I ^ A Q + J . A so A>i(; (x.^g (yx) . . . m •••^aP^n^ *
Hence
^ l = 3 x ^ ( X / 7 r a 3 ( Y l ) # •* 7T a3 (y n ) }
so
^ H 3 x ^ (x '^l * • • y n )
#D
ITERATED ULTRAPOWERS 6 . 9 . Suppose
Definition
A pair < < 2 V > - . ^ / < T T O > . O >-^ ) i s an i t e r a t e d ultrapower of N by U provided ~~QL Otton otp ot^ptc/n — are U such that (i) << V £7 a > a€Dn'
i s a
(v) << V V ' ^ a x W Lemma 6 . 1 0 . exists
coirmutative
for all a€0n
Vl* whenever X is a limit
there
i s a direct
for aU
limit
°f
ordinal.
Suppose (N_,u)^=R+AC where U is a normal measure on K in N_. There
an iterated
ultrapower
of N_ by U.
Proof: Induction based on lemma 5.16 at successors and lemma 6.4 at limits; each U
is a normal measure on ir. (K) by lemma 5.28. a
52 Lemma
6 . 1 1 . S u p p o s e < < A^ > a £ o n , < ^
^
^
>and<(^
>a£On,< i r ^ ^
^
>
are
iterated ultrapowers of N_ by U. Then there are isomorphisms Oa:Na=Na such that (i) OQ=id\N (ii) O n ; (iii)
CJgfTT^
Proof: Induction based on lemma 5.14 at successors and lemma 6.3 at limits. n D e f i n i t i o n 6 . 1 2 . Suppose < < N > c
,< TT O ) ^ o - > is an iterated
—Ot OLfcOn
of N_ by U. Each N is called an iterate of N_ by U. D e f i n i t i o n 6 . 1 3 . tf i s iterable founded .
ultrapower
Otp Ot^ptOil
of N_ by U; N is called an ath iterate
by U provided each iterate
of iV by U is well-
D e f i n i t i o n 6 . 1 4 . Suppose N=
< (N >
,< TT g > < g £
> is an iterated
ultrapower
of N_ by U.
(K) where U is a normal measure on K in N.Then
a oa (i) K is the critical
point of 7T o
Ot
Otp
(ii) tfJ=K (iii) Nj\=K,=sup K (\£0n a limit) a<X
Proof: ( i )
o On t h e
But K =7ra (K )>^K f o r a l l y with a
hand
other
W^a'^I >K
.
— a (ii) Immediate from (i). (iii) Suppose N ^ p 1 ^ . Then 3=^(3*) then $ > K , ; so —
A
f o r some
ct<X,F. If ^>
3"
OtA
(iv) From lemma 5.26.
Qi
o
In the above, and generally, we write, for example, ot<3 to mean N [=a<3 if there is no danger of ambiguity.
53 We should refer here to a s i t u a t i o n t h a t sometimes a r i s e s . I t may be the case t h a t M|=ZFC+RTPM (K) cj^ 1 and <J^,U>f=R but U$M; thus <M,U>^R. Let N=J^; then we can define an i t e r a t e d ultrapower of N but not, apparently, of M. But actually we can cobble something up: D e f i n i t i o n 6 . 1 6 . Suppose N=J^ , ?M(K)<=J*^ , f^=cf(\)>K A H^=Jy- and suppose that (
% > a C O n ' < 1 [ a 3 W o n > i s an iterated ultrapower of^by U. ((Mo, >OitOn _ ,< TT'otp>a
< Vir'a>a<X>
(iv) a limit (V)
i s a d i r e c t
1±mit
as
H^ =JX (K -IT (K)) a a in definition 6.9) °f
<<M >
a a<X'
when
X l s
MQ=M.
Lemma 6 . 1 7 . Suppose N=J\, P (K)GJ and U is a normal measure on K in N. Suppose f^=cf(X)>K A H,=J, . Then M has a weak iterated
ultrapower
by U.
~ M' Proof: Suppose IT ': M-»-TTM' and T M N + N ' . We claim N'=J. , for someX' . U - JJ- -A Let X'=TT'(X). Suppose TT1 (f) (K) 6J, , . Then without loss of generality f:K+J^, so f:K+J^, some 6<X, so f€N. Let a (IT1 (f) (K) ) =TT (f) (K) . a is the required isomorphism. Clearly cf (X') >TT(K) in M 1 and M'^J^^H^,. Thus we may iterate at successor ordinals. Now suppose y is a limit ordinal, and suppose M ,irR are defined for a£3
and x=7r-«- (x) with X € J ^ Y and yy A^
J^yN ) . The reader i s l e f t t o check t h a t A ^N-y l e t a(x)=ir-yy (a-(x) y
this
works. Lemma 6 . 1 8 . Lemma 6.11 applies
to weak iterated
ultra
powers.
Exercises 1. Suppose < < M a > a € O n , < i T a 3 > a < e e O n > is an iterated ultrapower of V by U, a normal measure on K , and each N transitive. Find a bound on the size of K^. 2. Let < < N a > a € O n , < ^ a 3 > a l 3 e O n > be the iterated ultrapower of an iterable premouse N. Suppose N =
X€U w *» 3nVk>nKk€X where X€P N (K^) and K a is the critical point of 1^. CO
54 7:
INDISCERNIBLES
Our aim in t h i s chapter i s to show that {KiBxeN- In other words given a E, formula $ and x€N and any two increasing sequences
N f=
ix
in
Oa
(7.1)
D n Oa
D l
An argument of Solovay is then used to extract E from these {K O :3
indiscernibles
p
For the time being fix a premouse N with iterated ultrapower <
,( TT o )
Lemma 7 . 1 .
Q
); let K
For all
x€No there p where a
be the critical point of N .
n is f€N , N \=f:K -+V,and a —a1
there
are
y....y 1
n
,
Proof: Assume a=0 without loss of generality. The result is proved by induction on 3. Suppose 3=Y+lf Say TT=TT
an
^t
n e
result is known for y.
o.
Take some x€N o . Then No(=x=iT(f) (K ) for some f€N , YP P ~P Y Y N [= f:< ->V. By the induction hypothesis N (=f=TT (g) (K . . . K ),say. Define a function g • €N with g ' : Km+1->V by g'(a1...am+1)=g(a1...am)(ain+1).
NOW
(7.2)
^03(gl)(KY...KY,Ky)=TT03(g)(KY...KYJ(KY)
=ir(f) ( K y )
=x
(in N^)
Suppose X is a limit ordinal and the result is known for y<\. Given x€N, , X=TT
A
(X) for some y<\; say N NX=TT_ (f) (K^ . . . K ^ ) . Then -Y OY y1 Ym
YA
Lemma 7 . 2 . Suppose (J> is a E formula.
Then there
is a £ formula
$* such
for all a
i
Proof:
in<...
(|>* i s c o n s t r u c t e d b y i n d u c t i o n o n n . I f n=0 l e t <{>* b e
S u p p o s e n=m+l. S u p p o s e <|>(y-,...y
/ x ) i s ^0«
Sa
Y
that
55 iMyi...ym,x)
~ U:4>(y1...ym,S.x)}€u
and l e tty*be such
(7.3)
that x)
(7.4)
for all a, i,<...
. . . K
±
,*
< X > ) <* N
± + 1
I n
N ( ^ i
- . . K
±
,TToi
+ ]
_(X))
( 7 . 5 )
n •• N ± h U : * ( K ± n i
1 n n . . . K ± ,C/TToi ( x ) ) } € U i 1 m n n
...K
i
n
,7T oi
±
1
(x))
m n
<* N |=i/;* ( x )
for a l l a, i.<...* b e ij;*. S u p p o s e , t h e n , that 4>(y-i---y /X) ** 3y^(y y n . - - y « / X ) w h e r e ip ± n , ± n is E . Let x k e the formula 3y€x'ip (y,y, . . .y ,x) and let x* be such that Na(=X(K± - . . K ± ,7rOa(x),TrOa(x')) <^#=X*(x,x') 1 n Then
. . . K
i
±
(7.6)
** 3 x ' GN N ^ B y e i T ^ ( x 1 ) ip ( K ± . . .
,irOa(x))
I n
(7.7)
1 •••Kin'7TOa(x)) «
S o we m a y l e t
<J>* b e
Corollary 7 . 3 .
3x'€N NaHx(Ki
3x'x*(x,x').
{K i ;i
Proof: Suppose i . < . . . < i Na|=4)(Ki...Ki 1
.
•
indiscernibles
,7TOa(x)) n
for < ^ / ^ ^ ^ g ^ -
< a , w i t h c> j E, a n d x € N . Then
«*N|=(j)*(x)
(7.8)
-N^K.^.K.^U)).
a
Corollary 7.4. Z C ^ ; O P C K ; -Z CN
Proof: Suppose X€I, (N) , X C K . Suppose 4> is E, and ^€X «* N)=(J) (^ ,p) . Then let X = U < K : N J = <j) (^ ,TTQa(p) ) } . Clearly X=X; and X is Z 1 ( N a ) . Conversely suppose X€S, (N ) .Suppose £€X <* N [=(})(C,p) . By lemma 7.1 there is f€N such that N |=p=ir .--yn))a
N
a
i
(f) ( K ± . . . K . ) . Say 1 n Then (J)1 i s Z 1 . And
. . . K ± ,irOa(f))
(7.9)
** N ^<J)'*(C f f) . Hence X=(C
a
O c c a s i o n a l l y a s h a r p e r form of lemma 7.2 i s Definition defined
7.5.
Suppose U is a normal measure on K in Af. Then un<=P(Kn) is
by: U *U
X€un+1
needed.
<* « ^ 7 . . . £ :
In
>:{£:<£...£ ,
In
56 7 . 6 . x€un is a Z, property of X,n (over M, where U is a normal measure on
Lemma
_ K in M) . X€Un «* 3f(dom(f)=n
Proof:
A f(O)=X A (Vm+l€n) (f (m+l) =
= { < £ - _ . . . £ n _ m > : U : < £-_...S n _ m ,C>€f (m)}€U}) Lemma 7 . 7 .
Suppose (j> i s a I
NJ=4>(
formula.
Then there
. . . K . > ,TT (x)) mrirf*(n,x) 1 n
A f(n-l)€U)
is a Z
(i <...
formula
D $* such
that
Proof: I f <> f i s Z then
(7.10)
GENERALISED INDISCERNIBLES S o l o v a y ' s g e n e r a l i s e d i n d i s c e r n i b l e s employ a combinatorial nent t o o b t a i n £ iinnddi s c e r n i bbllee s . The c e n t r a l notion i s t h a t of argument a f u l l sequence of i n d i s c e r n i b l e s . Definition
7.8.
Every ordinal is 0-good.
a is n+l-good provided a is a limit itself)
of n-good points
(and hence n-good
.
Note: a i s n-good i f and only if a i s a multiple of w , of course. (We count 0 as n-good). Solovay's proof was formulated in ordinal arithmetic: but we feel that the present approach gives more idea what i s going on, and, more importantly, may be generalised to models with many measurables, where the ordinal arithmetic becomes hopelessly confused. Definition
7 . 9 . Every
increasing
sequence
————————————
a ...a
with
IK
)is n+l-full
a -0 is
0-full.
J.
provided
(i) is n-full (ii) if a,<3
7.10.
ch (a)=max(m
_____________________
JJ
__
Lemma 7 . 1 1 . Suppose —————— ft
a <$
Then ch (&)< n
Proof: Suppose ch (B)_Lcn ( a n + i ^ ~ m ' s a v # T ^en m
Suppose is an increasing
sequence
<
3 I » . . 3 h > with
Suppose n o t .
some < a 1 . . . a , >
sequence of ordinals.
l ^ . . . a ^ ^ B ^ . . .3^}
L e t k be minimal such t h a t
and let< $-_.. . 3 , , >be n - f u l l
There
is
and <*k=$h-
where
the r e s u l t
fails
{$1...Bh,}2
for
57 ,} and Gu'^k-l (P r o v ^^ e ( ^ k>l) . So there are no
2{a, ...ou
{3 h , +1 ...3 h } with 3 n =a k and <3 1 -..3 h > n-full. Assume that a^ is minimal for the previous sentence. Then a^ is not n-good, otherwise < 3-^.. .3J-I rOt, > is n-full. Let a=sup{3 are n-full as a
D
A few examples may help clarify this. A sequence is 1-full provided that whenever i, is a successor ordinal i, , =i,-l. Hence • 2 2 12 2 2 <0,u)2+l,a) +3 > is not 1-full, but < O,o)2,o)2+l,o) ,0) +1,0) +2,0) +3 > is. The latter is not 2-full, but would be if 0) were added. The essential fact about n+l-full sequences is that from their ch ,, values we may determine the ch values of their n-full n+1
•*
n
extensions. D e f i n i t i o n 7 . 1 3 . Suppose
Then
> means (m....m )+ (n....n. i p nfx i K (i) X={u^...u^} / 0
m =max(n.,n) uh h (Hi) uh<j
Definition
7 . 1 4 . A?X
•" • Lemma 7 . 1 5 . Suppose {aJ...ajt>c{3
(0
s={<
mn.. .m >.-<jn....m H
\ n . . .n /
1
< 3,...3
> is n-full
. . . B } and 3 ^ a ^ . Then,
< Chn (^),. .P.,chn (*J*BJ
C
p
1
1
k
and < a . . . a > is n+l-full.
letting
V j
p
a h = 3 u (0
(CLJ
Suppose
and X = { u J . . . u J t }
Ch^ («k) >
Proof: Immediate from lemma 7 . 1 1 .
n
Conversely Lemma
7.16.
Suppose
———-————————
J.
a n d <m . . . m
K
1
>+ p
'TlfX
^ . ( a j . . . n+J. JL
,,.ch . 7 (OL,)>. Suppose X={u .. .u,} ,u <.. .
K
1
K
JL
K
< 3I, . . . 3 p > with 3u,=a,(0
h' =u, .
Then l e t 3 h ,=a h .
Case_^
ch n (3 h ,)=max(n,ch n + 1 (a h )) =m h"
Vhf
Let h " = h ' - l .
L e t m=m, , . T h e n m
+
i(av1+i)-
Hence
^+1
i s
58 So sup{$3nii. Then ch (3)^m. Suppose ch (3)>m; then sup{3'<3:3' is m-good}=3/ contradicting the minimal choice of 3. So ch n (3)=m. Let B h ,=3. It remains to check that <3-,...3 > is n-full. So suppose B^i is not n-good and 3n,,<3<3n, (h'=h"+l) Case 1
h' =u.
Then a, ,<3
Vhl
52=ii
Since 3_, i s not n-good ch (3, ,)
a
That concludes the disguised ordinal a r i t h m e t i c . We are a t l a s t in a position to prove a r e s u l t about i n d i s c e r n i b l e s . Lemma 7 .17 .
Suppose <J) is a E
formula. Then there is a I,
such that whenever is n-full
formula (j)*
then
NJ=<$>(< < a . . ,Ka >^0QL(x)) ** AH*C< chn(a2)..
-chn(ak) ),chn«x) ,x).
Note: As in lemmas 7.2 and 7.7 (J>* depends only on (j) and not on W. P r o o f : By i n d u c t i o n on n . n=0 i s lemma 7 . 7 . So suppose < > j is fX) and ty i s II . Then t h e formula 1
«Y 1 ...Y p >rX,x,f) «* 4>(f (Y1..-Yp)/< Y u ..-Y u >/X) A
(7.11)
is n n . By induction hypothesisthere is IIn i^1* such that NaH'«K3i...K3
>.XfirOa(x)firOa(f)) -
(7.12)
« N^i|;'*«chn_1(31) ...ch n _ 1 (3 p ) >,chn_1(a) ,X,x,f) provided 3,...3 ,a is n-l-full. Set: >
)
f
First of all, suppose N |=<j>(
<
. .mp+]j«in1. . .m p+ ^€
(7.13)
...K >/7U (x) ) . That is, there is y
...K >f^n (x)) . By lemma 7.1 there are f€N and
and < Kg, . . .K^, > such that M a Hy = 7 T O a ( f ) (K^, . . .K^,) . By lemma 7.12 there are (3-j^. . . 3 ,a>3{3|. . . 3 p u { a 1 . . .ak,a} such that
L e t a,=3 1 1 n
'^'i~
(0
p
and X={u, . . . u w p + l } . Then JL
K.
NaH'«K3...K3>,X^Oa(x),uOa(f))
(7.15)
so N(=V; l *«ch n _ 1 (B 1 ) • • • c h n _ 1 ( 3 p ) > / C h n - 1 ( a ) , X , x , f ' ) . L e t ni h =ch n _ 1 (Bh) (0
m
p+1=chn_1(a).
59
By lemma 7.15 <m 1 ...m
+1
>-*n-1
x
< c h n ( a 1 ) . . . c h n ( a k ) , c h n ( a ) >. So
N H > * ( < c h n ( a 1 ) . . . c h n ( a k ) >, ch n '(a) ,x) . Conversely suppose N^=<j>*(
(7.16)
>be s u c h tnat Let n h s s c h n ^ a h^ (0
x
pt-j.
I• •
V+l
7.16 there is an n-l-full sequence < 3-j_ - - - B
> with a n = 3 u
where
X = { u 1 . . . u k + 1 } / u 1 < . . . < u k + 1 and chn__1 ( $ h , ) =m h ,, 0
1
(7.17)
so
k
Lemma 7 . 1 7 i s one o f t h e major t e c h n i c a l r e s u l t s we n e e d . We can immediately d e r i v e some c o r o l l a r i e s . Corollary 7 . 1 8 . PCKjOZ ,(N )C P(K)C\1 , (N) * n+l —a. — n+l — Proof: J u s t l i k e h a l f o f c o r o l l a r y 7 . 4 . Corollary
7 . 1 9 . Suppose
<j> is a E
, formula
n and
n+l
sequences such that: (i) < a , . . . a / a > , < 3 , . . . 6 ,a> are 1 P 1 p Xii) chn(o.h)=chn($h) (0
...K a ,*0(x(x)) p
a^
. . . K >,< K Q . . . K Q > are #^ p a p
p
n-full
«d)rK3 ...K 3 1 p
^^M).
Corollary 7 . 2 0 . Suppose a is n-good and C={Kg.-$
for <
V
W
W
Exercises 1. Suppose 0
ft
i s an
elementary embedding. 2. Show t h a t {K o :$
c u < . . . < a < 8 n < . . •<3V,
UCX
60 8: ITERABILITY
This chapter begins with an embedding theorem which yields relative criteria of iterability; continues to some absolute criteria; and concludes with some important consequences of iterability. Review the proof of lemma 5.17. We used the fact that M=V together with K-additivity to obtain well-foundedness of the ultrapower. The reason that we needed M=V was that otherwise <X.:i€(o> might not have been a member of M, even if each X. were. Observe that we only used the o^-additivity of U (i.e. X ^ U for all i€a) => .^Q X.€U). We may formulate a weaker condition: Definition
8.1.
U is countably complete provided that whenever X.£[/ for all
j^x^'
i€o) then
In the case that M=V this is actually equivalent to o^-additivity. Lemma
8.2.
Suppose U is an ultrafilter on K. Then if U is countably complete
then U is 0)-additive.
Proof: Suppose Xi€U,i€a), but ^ X ^ U . Let Let
Y
i+l
=X
i'
i€a);
SO
Y =K ^i^a)xi' 0
so
Y
€U 0
*
l^V*'
Looking at the proof of lemma 5.17 it is only the fact that the intersection of X. is non-empty that is used to prove well1 U foundedness; so it might be hoped that if N=J
is a premouse and
U is countably complete then, letting j:N-*M, M is well-founded. But we want to go further and prove that N is iterable. Unfortunately the obvious inductive proof fails. Let ^ M a \x€On'* u 8* <8G0 * ^ e a n i t e r a t e < ^ ultrapower of N; suppose K is the critical point of N. Let K=TT (K) , for a€0n. We know (lemma 6.15(iii)) that Ka)=sup{Ki:i€o)}; let Xi=Ka)^KjLr for i€u>. M ^ N ^ ^ ^ ^ ,U) 0)
Then X. €U 1
0)
for i€a) but . Q X.=0; so U ltO)
1
0
could not possibly be c
)
countably complete. This also shows that countable completeness cannot be necessary for iterability, for N
is iterable if N is.
The proof of iterability from countable completeness uses the following very versatile embedding lemma.
61 Lemma 8.3. 111
order-preserving.
Suppose artf-* M where N and M are premice. Suppose f:0n+0n is — Lo— — —
Suppose
A M # , £ . [ / , A . . . . A ) and M=4 M,eM,U'
, A ' . . .A')
. Let
>,<
are unique maps O such that
(Hi) oa« then a d if If o,ff-&J[ then " cofinally. Proof: By induction on a . Let a o = 7 r of fO) " Suppose a a i s d e f i n e d . Define < V l ^ a + l ^ o ^ f ( a + 1 ) b y ClaJjnJ, a a + 1 i s well-defined, o Proof: Suppose
Mf ( a + 1 ) (8 2)
-
•••ltf(a)f(a)+l«Ja(fn))(Kf(a)))
where
Proof:
a(Claim 1)
°a+1*Oa+1=
f ( a ) f (a+l) a a 7 r 0a f (a)f (a+D^Of ( a ) 0 = *0f(a+l)a =K (6 a+1) Claim 3 g a + 1 ( K e > f ( e ) ^ Proof: Suppose B
o(Claim 2)
f {a+1)
Hence a a + 1 ( K B ) - O ? + 1 ( i r a a + 1 ( =ir
f (a)f (a+D'
7T
Claim 4 a
f(a+l)
a(K)
o(Claim 3)
=
Proof: Suppose (3£a) . Given x€N
«»o a + l = i r 6 f + 1
there are f'
. . . KK
<
1
a a n ((a+1) such t h a t
d 8 (ie
B B) )==<< f (6) B N a + 1 |=x=
62 =TT
+ . (f
') (K
K 1
o n =a. Then
T
) (a 1 <. . .
f(a)f(a+l)7r6f(a)a(fl)(Kf(a1)---Kf«xn))
=a . a+l(x)' where f ( y ^ . - Y ^ - ^
Claim 5 If
Wr*f
then
Q(Claim4)
V
Proof: Suppose <J> i s L , <> j <=» 3yip where I/J i s E Q . Then (x 55f ( a f l ) ^ (*'aa+l l> •' • •••^l^n" * Mf(a+1)Nyew'(a)f(a+1)(Z)*(y,aa+:L(x1)...aa+1(xn))/say/ZeMf(a)
^f(a+l)N * -
(a
a+l
(x
l> • • - a a + l
(x
n»}
w
^f(a+l)^y^f(a)f(a+l)(z)^y'Tf(a)f(a+l ••• • • •77rrr(a)f( r(a)f(a+l)(aa(fn))(l
where x k = i r a a + i (fk> (Ka) (0
cofinally. Proof:
^fCaJfCa+D^^a+l^aa+l'
SO rng(a
a + l ^ r n ^ U f (a) f (a+l) a a ) ' D(Claim 6)
This concludes the successor case. In the limit case, where a is defined for a<X, we may define o x ( H a X ( x ) ) = ^ ( o ) f a ) a a ( x ) . For if \^x) =* BX (y) , a<6, then *a y). But V aVB < x ) - * £ { o ) f (f»,aa<x) so a e 7T a B (x)=a e (y). ; hence =7r
S
'f
f(a)f(X)acc(x)s i n c e a :N ->_ a
A 7 r OA = 7 T f ( 0 ) f (A) a 0 = 7 r f ( 0 ) f ( A) " o f (O) ° =7r
(iii)
Of ( A ) a #
a , ( K)=a,iTrv,1,(K ) A a A a+lA a =7T
f(
=7T
f ( a + l ) f (A) I* a)
=K'
a
.
+l)f(A)a
(a
°a 6 ( y )=
63
(iv) < V K A ) = a A ( l T O X ( K ) ) =ir
Of(X)(K<) f (X) •
(v) a, is the unique map with properties (i)-(iii). For suppose a':N.+M-,,. satisfies (i)-(iii); given x€N, suppose f€N and a,<...
7T
...K
DC.
UA
))
CX
6f(X)a(f)(Kf(a1)"-Kf(anr
=a x (x). (vi) If each oa:Ea^Mf{a) then a , : ^ Mf ( X ) . (vii) If V N a + I o M f ( a ) cofinally for a<X then o ^ N ^ cofinally. For rng(a.) 3rng(ir' f ,, , a) . a The lemma was expressed for premice but i t i s easy to see that i t works too for weak i t e r a t e d ultrapowers. Lemma 8.3 i s very useful: see exercise 1, for example. I t immediately proves: Lemma 8 . 4 . Then N_ is
Suppose M is an iterable
premouse and N is a premouse,
0:N+ M.
iterable.
Proof: Suppose < < V a € O n ' < *«($ W o i ^ ' ' ^ ^ O n ' ^ ' a B W e o n 1 i t e r a t e d u l t r a p o w e r s of N,M r e s p e c t i v e l y . Suppose N i s n o t well-founded;
l e t f:On-K)n b e t h e i d e n t i t y a n d l e t a :N •*•_ M b e a s
g i v e n b y lemma 8 . 3 . S u p p o s e < x . : i € u ) > i s s u c h t h a t x
then a ( - + i )
a r e
e
x
-+i
e
x N
- / a l l i€co;
x
M
° ( - ) / a l l i € w . So M i s n o t w e l l - f o u n d e d .
Contradiction!
•
Corollary 8 . 5 . If J^ is an iterable premouse with critical K<$
point K and if
~~p
Like lemma 8 . 3 , lemma 8.4 i s t r u e f o r weak i t e r a t e d u l t r a p o w e r s . L e m m a 8 . 6 . i f N i s a p r e m o u s e and <<W > c
,< IT Q > ^ o _ > i s a n i t e r a t e d
ultrapower of N, and N is well-founded for a<0). then N is ~~CL
1
iterable.
—
Proof: Suppose N i s n o t w e l l - f o u n d e d . Suppose <x.:i€a)> i s a
64 sequence
such
X.=TT
that
(f.)(K
x.+,€
N
i...K i
x . , a l l i€a). Suppose )
(8.3)
where K is the critical point of N
,a?"<...
S={cu:i€a> AO<j£p i >. Let 3 be the order-type of <S,€>; so 3 is countable. Let f':3-*-S be order preserving and surjective. Define f:On-K)n by f(Y)=f'(Y) (Y<3) (8.4) f(3+6)=a+6 (all 6) Then f is monotone. Apply lemma 8.3 with M=N and a=id|N. Then a PQ :N + N . Let ou=f " 1 (aj2:) (i
Then a^ (x\) =7rQa (f±) (Ka±. . .Ka± )=x ± . So for i€w x i + 1 € N x\; hence
1 p^ No i s not well-founded. But 3<w,. —p
3 a
l
We may modify this proof slightly to get Lemma 8 . 7 . N is iterable if and only if whenever 0:M+ N and M is countable then Wis iterable. Proof: Suppose n o t and l e t f . , x . be a s i n t h e p r e v i o u s lemma. L e t X-J N w i t h {f.:i€a)}cX. L e t a:M=N|x where X i s c o u n t a b l e and
M i s standard. Let f ^ a ' ^ f ^ .
Let 7< Ma >a€Qn,< TT^ ^
^ > be an
iterated ultrapower of M with K ' the critical point of M . We may now repeat the previous proof, getting countable 3 and x.€MD such _
t h a t aot (x.) =x I. , i€u).So — Mpo i s not well-founded. I
!
o
Lemma 8 . 8 . Suppose N=
-* premouse Proof: j
and j:M+ ,M' then suppose
< X . >.
Then X±eu.
enumerate Hence
i
there
U i s countably
are as in the statement
Let
K. U is
countable
~°
(M,E,U',A') Firstly
point
P
a1 ( j ( f ) (lc))=a(f) ( T ) . Then Ml^(|)(j(f1) (K) . . . j ( f n )
N such that Suppose
and l e t K be t h e c r i t i c a l
t h e X€PM(ic)
Qa)Xi*0.
is 0':M'+ complete.
Say
such
T € i
Qa)xi-
that
0'j=0. a , M,M* a n d
point
o f M.
X6U 1 . L e t X . = a ( X . )
Define
(i<w) .
a':M'+N by
f o r EQ $ ( K ) ) -» ( C : ( J ) ( f 1 ( ^ ) . . . f n ( £ ) ) } e u ' =* { ^ : ( ( ) ( a ( f 1 )
(5) . . . a ( f n )
(C))>€U
*+ T € { ^ : ( j ) ( a ( f 1 ) (C) . . . a ( f n ) =* N ( = ( j ) ( a ( f 1 ) ( T ) . . . a ( f n )
(8.6)
(?) ) }
( T ) ).
Conversely suppose the stated condition holds. Let <X.:i€o)> be a sequence with X.€U, all K w . Let X^Liv N with {X.:i€o)}cX, X countable. 1 — 1 —
65 Let a:M=N|x, M standard. Let X^=a" ( X i ) . Then M is a premouse; say M=<M,€ M ,U' ,A' >, K" the critical point of M. Let j:M+ ,M' and let a':M'->
N where a'j=a. Let T=a' (K") . Then i=a'(K)
And x=a' U ) €a' (j (X±) )
(as X ^ U )
=a(X ± ) =X.. So Lemma 8 . 9 .
If N is a premouse, N*
——— — countably complete then N_ is
— iterable.
ft
—
P r o o f : By lemmas 8 . 6 a n d 8 . 7 we n e e d o n l y show t h a t is countable with iterated
i f a:M-* N a n d M
u l t r a p o w e r <<M > cr. ,< ir Q) .ocr. >then M c —a atOn a (3 a£p£On —a
is well-founded for all a
•*_ N; in fact by induction we define a :M -*•„ N such that
—10 •, L o — 0
CX —CX L o —
^o ~°o (all 3
U
is defined a ,1 is given by
CX
CX"rX
lemma 8.8. If a is defined for all a<X and X is a limit ordinal a (y) (a<3) , then define a, (TT , (x) ) =a^ (x) . Then if TT (X)=TT A
CX A
(X
CXA
PA
—
IT g(x)=y so cTg(y)=agTr g (x)=a (x) ; so a, i s well-defined. Let
a%
-°U} • 1 I t i s necessary to check that M i s countable when a
Suppose
N is a premouse —
§ is a T. formula. with
iterated
There ultrapower
is a £
formula
(f) s u c h
((N ) c , < T T O > . O -._ > ~~cx cxtO/i cxp cx
that then
66 the relation R={(x,y):N \=$(x,y)} is well-founded if and only if R = ={< x,y >;/v(=(j) (x,yfQ.)} is, provided aU{a} is an initial segment of On . P r o o f : L e t T = {
...Yi ) (8-7) 1 m where v={a 1 a n >, a 1 <...,f,g) ~ 4>
(8.8)
- - - ^ >'\,a
(8
a
'9)
(8.10)
where w=uUv. Suppose R is well-founded. Suppose
and R"" ff« f«i +fl f u i +>1 >< , < f f ii , u i »
(i€w) . I f uu={aj; (i€w) If a* }} aaj ;j<;. .<. <
NaN«Kyi...KYi)^Oa(fUitlWi)^Oa(fUiWi))
so
a
O
a
i
+1
o
0
a
i
o
x p p±+l i so N a (=4)(x i + 1 ,x i ) (all i with R ( x . + , , x . ) , a l l i<0). Let X
1
i-0a(fi)(^--V<)
X
X ( a
l<"-
Let u i = { a ^ . . . a 1 } . Then R (< f i + 1 # u i + 1 >,< f ± , u i » a l l iCco.
( 8
-
U )
o
C o r o l l a r y 8 . 1 2 . There is a relation R uniformly T. (N_) , where N_ is a premouse and to U{w } is an initial segment of N_, such that N_ is iterable if and only if R is well-founded. Proof:
B y lemma
Corollary 8.13.
8.6, letting
<J>(x,y)
<=» x € y i n lemma 8 . 1 1 . •
If $=ZF~ and u^Of then
flf="iV is an iterable
premouse" <=» N_ is an iterable
premouse.
ITERABLE PREMICE
Two important results on iterable premice follow. The first i s
67 the c o m p a r a b i l i t y property.Although two i t e r a b l e premice J Ua , JU' a r e Q 1 "~" => J"U €U not n e c e s s a r i l y d i r e c t l y comparable, i n t h e sense t h a t a<$ J^, a yet they may be i t e r a t e d t o premice with t h i s p r o p e r t y . Lemma 8 . 1 4 . Suppose N_ is an iterable <<JV > c
,< IT
n
>
If X is a limit
premouse with iterated
ultrapower
>.Suppose N =
nc
ordinal
point
Proof: Suppose x€U,; say X=TT . (x) , so x€U . Hence K €TT K €7T
a
x
aX^~ *
A
Tha : i s
t
'
x€rn
Tr
OtA
K €x
^^ aX^ "* a "
If x$Ux then K ^ X € U .
n (x) CX CXCX"rx
Ot
Let Ybe least
SO 3y<XV6 (y<6<\ -> K^^X) .
Lemma 8 . 1 5 . Suppose
0 is a cardinal
premouse with critical
point
such
of N then 9 is the critical —
point
Q
>
Q
, so
that
•
and Q>P(K)C\N, where N_ is an
K. If < < N > c^ ,< IT —OL ottc/n
ultrapower
of N .
then for all
> i s t/ie
iterable
iterated
otp d^pton
of N~. —0
Proof: L e t K^ be t h e c r i t i c a l p o i n t of N^.An easy i n d u c t i o n on y ^ ' 6 regular. Then for all X€P(Q)0NQ x€.Ua •• x contains a closed unbounded set where i^=< N A , € / f / A / A A >. ~~0
0
0
0
Proof: By lemma 8.14 if
x€UQ then x contains a closed unbounded
set
{K :Y
a
Definition 8 . 1 7 . Iterable premice M_,N_ are comparable if and only if there is a such that either M=J^a or N-J^'. a Lemma with
8 . 1 8 . Suppose
iterated
respectively.
ultrapowers
M_,N_ are
iterable
<<M > _
,< TT
pure O
> ^oc
premice >, <
,< I T '
Suppose 9 i s regular, Q>M,N. Then MafNa are comparable. — 0 ~~o
Proof:
9 is the critical point of both ML and N n by lemma 8.15. —o —o So the result follows immediately from lemma 8.16. a
Of course, lemma 8.18 does not hold if M,N have
additional
predicates A.. Does it follow from the fact that M =N Q that JL
either
—0 —0
M=N or M is an i t e r a t e of N or N is an i t e r a t e of M? Not in general: but we shall show in the next part that i t does in the cases that interest us.
68 The second p r o p e r t y of i t e r a b l e premice t h a t we need i s of obvious
significance.
Lemma 8 . 1 9 . Suppose N is an iterable Suppose a.-N-* M; suppose <
r/,
~~o> u t c / n
Suppose
So
5
tne
cxp o t ^ p t o n
n o t . Say a(^)
such t h a t
premouse and that M_ is an iterate
,< TT o ) w><-« ^s
say M=N . Then for all £€On , O(E,)>^ Proof:
less
iterated
ultrapower
of N_. of N;
—
(B,) . ( £ ) . By lemma
V,.B,O+Y<»|J«VBY'
8.3 t h e r e
a r e
a l l B
n£Na.n- L e t V ^ a . n ^ . o o ^ n * • We claim C n > C n + 1 - For C 0 >C 1 . because a(^)
n+2 =7r a(n+2) ,a.03(^n+2) =Tr
a(n+2) ,a.w (a a(n+l) ( ^n+l } }
=a
a.a)7Ta(n+l) ,a.a)(^n+l)
=a
a.w ( W (c )
(induction hypothesis)
=CiSo N
i s not well-founded; c o n t r a d i c t i o n !
Corollary 8.20.
Suppose M_ is an iterate
•
of N_, an iterable
premouse.
Suppose
7T.-W-* M_. Then Tf:N+y M_ cofinally.
Exercises 1. Derive corollary 7.3 from lemma 8.3.
2. Suppose U is a normal measure on K and <<M a ^ a e O n'^^aB^a<8€0n^ is the iterated ultrapower of V by U. Suppose 9 > K is a strong limit cardinal with cf(9)>K. Show that for all a<6
VOGL(Q)=Q.
3. Suppose M,M' are comparable iterable premice, N,N' iterates of M,M' respectively and N,N' comparable. Show that M€M' •• N6N 1 . 4. Suppose N ,M ,T\ QIT\X Q,O ,£ are as in lemma 8.3. Show that for all —(x —ot
otp
otp
ot
3
69 PART THREE: MICE
Part three brings together fine-structure and the theory of iterated ultrapowers. Chapter 9 will introduce mice, the main technical device of this study. The development here is rather different from that in [10 ] . We are concerned to show the parallel with the results of part two more closely because this is important for generalisations. To eliminate the operator -*jj makes the proof of the covering lemma harder. Chapter 10 reveals a simple structure theorem for mice: every mouse is an iterate of its core. So given two mice with a common mouse iterate one is a mouse iterate of the other. This fails to generalise even to mice with two measurable cardinals. Chapter 11 proves acceptability for iterable premice. This would seem to make the specification of acceptability in the definition of mouse redundant; but actually it is much simpler to put it in. Mice are used essentially in the proof of corollary 11.29. Chapter 11 uses many techniques that will be needed for the construction of the core model. Chapters 12 and 13 stand a little aside from the main development, relating to class models of ZFC rather than to mice. None of the results in these chapters require mice for their proofs, but the results are essential for the statement of later theorems, which is why they are included here. Chapter 12 gives a first example of a mouse and chapter 13 a very weak generalisation of mice. This is, moreover, only sketched; but the theory of double mice is not very different from the theory of single mice presented in this book. The descriptive set theory at the end of chapter 13 is included to show how mice may be used to prove results that predated their invention. It is not necessary for anything that comes later in the book.
70 9 : MICE
Consider an iterable premouse N. Let us assume for the moment that the critical point of N is K and that wp < K . Then it is clear that if < < N > e O n f< IT g > a
is
the
iterated
ultrapower of N then
= p N , since ?(K) flZ1 (N^) = P ( K ) nZ^ (N) by lemma 7.4, and
P ( K ) D N =P(K)P(N. In fact we shall show that A^=A^N and " ^ a ^ N ^ N ' a ot where p N is a standard member of P to be defined. Not so, however, if o)pN>K. Suppose oopJ*
have 7TQ :N-*-~ N
and we cannot conclude that pjj = pn. or that AJJ =A JJ«
For reasons we explained in the introduction we are not interested in premice with o)p^>K. But we shall need to consider the cases where alp. >K but o)p5J
n
M 1 , and M ' n p ' will be M. In n+1 will be bigger than the usual iterate of N.
completion of IT, Tr':N+
general M 1
Fine structural preliminaries precede the main definition. Definition 9.1. Lemma 9 . 2 .
Suppose p,g€[On]
<^ is a well-order
.
of [On]
Proof: I f p<*q and q<*r, w i t h Y/Y1 r e p e c t i v e l y as i n t h e l e t Y = m a x ( Y / Y ' ) . Then p^Y=r\Y- rnY'*0 so rflY+0. Case 1 Y=Y-
definition,
Then either pD7=0 / in which case p<*r, or max(pn"y) <max(qn-y) . If max(qriY) =max(rnY) then p<*r. Otherwise qnY=qnY', rn-y^rriY1 so max(qflY) <max(rnY) . Hence p<*r. Case 2
"y=y ' .
If pny=0 P < * r - Otherwise qflY+0 so qfiY*0 . Hence rnax(qfl Y ) < m a x ( r n Y ) « The proof goes as in case 1. So <^ is transitive. Given p,q€[On]
71 q<*p otherwise. Finally, <* is a well-order. For suppose p. + ^<*p./ all i<w. Suppose y. is such that p. +1 ^Y•=P-^Y•i P-
ny.*0 and max(p^ + ^ny^)<
< max (p. fly. )or p.+-.ny=0.We may assume i£j «* y.
is infinite. Contradiction!
Lemma 9 . 3 . Suppose a;itf->v N, M,N transitive. ———————
— 2JO —
n Then o(p)>p,
all p€[On]
— —
w
.
"
Proof: Let p={a 1 ...a n >, a 1 < — < a n . T h e n a(p)={a(a 1 )...a(a n )}. Suppose for i>k a.=a(a.) If k>0 a,* a (a,)
(0
so a,
where a=a(a, )+1.
a
We can use <* to simplify definition 3.23. Definition
9.4.
Suppose N is a transitive
model of RA (hence a model of RA ) .
—
Then we define by
p
induction:
p
= the
9 . 5 . N is n-sound if and only if N_ is < p . .
Lemma 9 . 6 . Suppose N_ is p-sound, +1
Proof: a)fp
p=< p .. .p >. Then
.p")-sound.
pn = QNnP'
=n{o)pNnq:q€PA^}. A simple induction shows t h a t A m q l " # q m
i s rudimentary in N 1 1 1 1 ^ " ' ' ^ for m
D
Suppose N_ is a transitive
>K, where K is the critical
acceptable
premouse of the form J and
point of N_. Then N_ is n+1-sound.
P r o o f : By i n d u c t i o n on n . Suppose t h e r e s u l t h o l d s f o r a l l m
. Hence letting B have the
same Z. definition over M from a " 1 ( p ^ + 1 ) , Bna3p^+1=Ana)p^+1. But by lemma 4.20 Bflcop
B is Z1(Nn)
is definable over N. Thus
a=a , N=N. But then
so a"" 1 (p^ + 1 )€P^n=P N n. a " 1 (pJJ+1) 1 * P N + 1
b v l e m m a9
-3
72 so a " 1 ( p ^ + 1 ) = p J J + 1 .
But t h e n a i s t h e i d e n t i t y map so X=M=Nn.
Compare t h e proof of lemma 4.27 . A s i m i l a r argument Lemma
9.8.
top^fK,
Suppose
where
Definition
K is
N_ is a transitive the critical
point
acceptable
premouse
of N_. Then
l f
i
^ *
yields and cop >K but
+ 1
9.9. Suppose $=RA. N_ is strongly acceptable above y provided that
whenever X is a limit ordinal >y and aa5, a€S, NS, then S.
Lemma
a
9 .10.
\=\<max(y,S) .
Suppose N_ is strongly acceptable above y. Then whenever
£ *A, N N N N Proof: We have to show H n=J n. We know that J ncH n. Suppose
N a€H
"PN PN n N V "PN n n. We may assume that acy<(op , for H n=L){j n: a€N A acy<(opN} XT
ra X7
"NT
r"»
IN
IN
and a€J n =» J n<=J n since cop.T i s closed under addition p
N
P
N-
P
( unless n=0
N
N
when the r e s u l t i s t r i v i a l ) . N Suppose X i s l e a s t such t h a t X i s a l i m i t ordinal and a€S, . Then S,+ \=\<max (y, \i) . Since a)pN i s a E, cardinal in N and Y,y€topN, therefore X€a3p^. Thus a€J n. a N PN Lemma 9 . 1 1 . Suppose iV is a transitive acceptable premousef with K the critical point.
Then N_ is strongly
acceptable above K. (N_ must be of the form J ) .
P r o o f : S u p p o s e a<=6, a € S ^ , ^ S ? , X a l i m i t . C a s e 1 PCKJOSV 1 ^ W = P ( K ) n s , . N N n Then by lemma 2.41 a€E (S ) . Say a€S (S ) ; then cop^N<max(K /6) . But & a) — A n —x TL"~ N N we may apply lemmas 9.7 and 9.8 to S, to get an S, definable map of max(6,K) onto X. Case 2 Z (S^) ^ Suppose nP(K)cS\\ ^ L e t M be rud T . n e N(SH . Then by lemma 2 . 4 1 CO ~~A
—
A
Ullo^
A
P(K)nM=P(K)nEaj(S^)cS^. Hence <M,€,U>|=R+. But then S^+a)eM. Contradiction! So E (S,)nP(K)is,, so for some m wp m N
CO ~~A
o ^ ~~
case 1.
a
A
THE OPERATION n : N - ^ N ' u D e f i n i t i o n 9 . 1 2 . A premouse N_ is n-suitable provided: (i) N_ is acceptable. (ii) N_ is strongly acceptable above K , where K is the critical (Hi) (iv)
K€copJJ. W is p-sound
for some p€PA
point of N_.
73 (ii) is not necessary but may always be assumed in the cases we are considering. Of course, ( i v ) means that ltfpRA for m
(ii) and (iv) are redundant. 9 . 1 3 . Suppose N_ is an n-suitable
Definition
Then r\:N+nNj means that is the n-completion
of T) \ N
P
So n : N ^ 7 N '
n:N-> N
1
means
Lemma 9 . 1 4 .
N=
n \tinp:iJnp-*' N_'nT](p' and r\
to N. .
Suppose N_ is an n-suitable
there is an isomorphism
premouse,
for some p£PAN N is p-sound,
premouse.
If T):N+*\N_' ,T\' :J£*JV' then
a:tf'=W" such that (3T\±r\'.
Proof: By the remark after definition 4.26 we may assume that each o f n | N n p , n I | N n p : N n p - > u N ' n n ( p ) , N " n n ' (p). So by lemma 5.14 there c*n | N n p = n • | N n p .
is a such that d:N' n n ( p ) =N" n n ' ( p ) and
By lemma 4.25, then, there is o^6 such that a:N'=N". But then an satisfies the definition of the n-completion of n ' | N n P N, so by lemma 4.2 3 an=n'.
to
°
Lemma 9 . 1 5 . Suppose N is an n-suitable premouse. Then if N=(N,€ ,U,A) there ————— pj are r|/W' such that r):N+nN_'. Proof: By lemmas 5.16, 4.25 and 4.23. Note that n:N-> N'. D
" n
Lemma 9 . 1 6 . If r\:N+ N_' then N_' is
E
n+1~
n-suitable.
Proof: N 1 is acceptable by lemma 4.10 or 4.11. By the same argument N1
is strongly acceptable above n(K). N 1 is n(p)-sound, provided
N is p-sound, by definition, and clearly n (K) €a)pjj, .
D
Lemma 9.16 gives us a basis for iterating the operation n:N+yN'. But first we need a couple of general results about n-completions. Lemma 9 . 1 7 . n-completion
of f\* :N_'
nV[(p)
nV[ lT](p)
-*iV'
—
(N,(-n —
((N > . ,< IT O > . o , > ) is —$ ot^A d p Ot^p
> ., > a direct
(X CX^A
limit
of~the
of
N", n ' n ^ ' f i .
— Lo~
L e m m a 9 . 1 8 . Suppose —————————-
n ' is
then T)'T) is the n-completion
P r o o f : N" i s n ' n ( p ) - s o u n d a n d n ' n : N - >
ordinal,
of f\:f^P^N_'nT[(p)and
if r\:N+N_' is the n-completion
the
fi'fi.
°
~ a commutative
system,
Xa
limit
system and for each a<$<X —
TT r,:N ->NQ is the n-completion of TT' =TT o l ^ OOL (some fixed p such that A^0, N is p-sound). psound). Let TT '=11^ =11^||rf™0o.'p) ; then < ^0(p) ,< ^ > a < x >is a direct p€PA^0,
p; limit of < <£W j £ W p ; >a<x,< iriB > a l 3 < A > and TT is the n-completion of 7T. Proof: Suppose f i r s t of a l l t h a t x€N 0 ( p . Then x=7r a (x) f o r some a<X, x6N ( ^
74 It suffices to prove the result for n=l. Let Y={v€N:N£=v€Tr (6) , some a) . So a)pNcy. Hence NJ=TC(X)€Y, so N f=TC(x)€a)pN , without loss of generality. So X E N W ^ . For t h e second p a r t i t s u f f i c e s t o show t h a t N i s p-sound. If i t i s n o t then OJP N*Y: say TT^ (6) ey^o)pN, 6€u)pN . Let A be E-^N) in parameter q such t h a t AOTT (6)$N. We may assume q=7r (q) . L e t t i n g A have t h e same E 1 d e f i n i t i o n <> ( over N^ from q API 6 6 1 ^ . But then a
which i s ITO; and TT O : N ->> N o , a s IT o i s t h e 1-completion of IT ' o , so 2 a p —ot L 2 —P ap _ by lemma 6.8 TT :N •*• N. So APITT (6)=TT (AH6) ; c o n t r a d i c t i o n !
ap •
MICE
D e f i n i t i o n 9 . 1 9 . Suppose N_ is an n-suitable premouse. Then <<# > r / , ,( TT o > ^oe~ } is an n-iterated ultrapower of N provided ~0t
OtfcO/3
(*)
(ii)
Otp Ot^-ptC'72
<<
—
^a > a€O7i' <7r aB > a<3€On )
each N is n-suitable,
i s
a conanutati e
^
system,
N=t N ,€ / y a / A ^ • a
(Hi) .
jv «iv. m
^n
QLQL+ - a
U
a 1 a~ ' "
(v) < N, ,< TT , > ^ > Lemma 9 . 2 0 .
i s a direct
If N_ is an n-suitable
limit
of (( N >
premouse then N_ has an n-iterated
ultrapower.
Proof: Construct N by induction on a, proving t h a t N i s n-suitable. Let NQ=N. in the successor case we use lemma 9.15 to get N + , . N + ^ i s n - s u i t a b l e by lemma 9.16. In the l i m i t case N.. e x i s t s by lemma 6.4. To show t h a t N, i s ~~A
—~A
n - s u i t a b l e we observe that by an inductive argument a<3<X «• => TT g i s the n-completion of TT g|Nn7TOa ^ for some fixed p in PAn such t h a t N i s p-sound. The induction uses lemmas 9.17 and 9.18. Hence by lemma 9.18 TTQ^ i s the n-completion of TTQ^|Nnp so N^ i s TTQ, (p) -sound. The other clauses are e a s i l y checked. D Lemma
9 . 2 1 . S u p p o s e <
n-iterated (i)
,< IT O > ^oc
> and < < # ' >
c
/< TT' > ^oc^ > a r e
ultrapowers of W. Then there are isomorphisms a :N =N' such that a 7T
3 aB=7Ta$aa
(ii) °^(Ka)ssK^
for
(K K a' a
a
-3* the
critical
points of ^ / ^ respectively) .
D e f i n i t i o n 9 . 2 2 . An n-suitable premouse N is called critical where K is the critical point of N. This n is written n(N) .
if K$a>pn+1 fT
75 Definition 9.23.
If N_ is a critical
of tf is called a mouse iteration
premouse then an n(N)-iterated
ultrapower
of N.
Definition 9.24.
Suppose < < N > c ,( T\ o) ^oc > i s an n-iterated ultrapower of yt ^ -a a€on a$ a<$€on N. Then each N is called an n-iterate of N, or a mouse iterate if n=n(N) . — —& — D e f i n i t i o n 9 . 2 5 . N_ is n-iterable provided each n^iterate of N_ is well-founded. If W is critical
and n(N)-iterable
then N_ is called a mouse (provided N_ is pure) .
The reason for introducing mice is quickly seen if we try to apply the ordinary iteration operation to critical premice with n(N)>0. Say n:N-> N 1 . Suppose n(N)=l; we do not know that a)pX7l
and N is a
mouse.) But there are good reasons for excluding such premice; if they are admitted to the core model indiscriminately then we shall end up with measurable cardinals in the core model, and we saw in the introduction that this would be a bad thing. We saw that if N is a mouse r^N+j^N1 and n ' rN-^N" then N" is an initial segment of N 1 ; and
P (K) nN"=P(K) PIN1 where K is the critical
point of N. N 1 adds enough levels to N" to get a construction stage where ojp^,
)+
<: n d O . Of course it could be the case that N was an
iterable premouse but not a mouse, and then these levels might not exist. By the results of chapter 7 there will often be a,3 such that 7T Q :N -> N o when TT O is the ordinary iteration map. In this case ap — a ^ n ~ p
otp
the maps may or may not coincide. Exercises 1. Suppose V=L['U] . Assuming that L[U]is acceptable and U is a normal measure on K construct a premouse N with n(N)=l. 2. Is there a sentence a such that N(=a <* N is a critical premouse? Such that N^=a «=» N is a critical premouse and n(N)=0? 3. Suppose nsN^j^N1, n=n(N)>0. Do we necessarily have n(p^)=p{J,? 4. Prove the equivalent of Los theorem for n:N+yN'.
76 10: PROPERTIES OF MICE
In this chapter we shall prove the basic structure theorem about mice. Roughly speaking this says that if M and N have a common mouse iterate then either M is a mouse iterate of N or N is a mouse iterate of M. Indeed there is a smallest mouse N of which N is a mouse iterate, called the core of N; this mouse will be n(N)+l sound (indeed, as it turns out it will be m-sound for all m ) . All manner of corollaries are proved as we go along. PRESERVATION OF PARAMETERS Suppose until further notice that N is a mouse, n=n(N), and that < <
,(N )0P(K)=1 n+1 (—ex
_(N)0?(K). n+1
n
—
n
Proof: E 1 (N )nP(K)=E 1 (N )nP(K) .
•
Lemma 10. 2 . Each N is n-sound. Proof: By lemma 9.7.
n
Lemma 10.3. tf*\=v=h(K Up12 ) Proof: By lemma 9.8.
•
Lemma 10.4. TT (pm)=pm UO. N
(m
N
—
Proof: By induction on m. Suppose ¥ +1
i€o), ye(a)p^ ) a
(p™. ) >*pJJ
• Then there are
such that Y,r))).
(10.1)
Hence
N"V(3r<,pg+1)(p^+1=h(i,r)). This is because r<^TTn (p
) => rUy<^Trn (p N
(10.2) ) . It follows that
N^ is r-sound, so r€P m. Contradiction! Suppose, then, that TT (p™. ) < *P^ • T n e n a s ^Q i s a n n-completion of TT- |Nn:Nn->N N p is TT (pJJ )-sound, where p= =< TT
(p )...TT 0 (pJJ) >. But by the induction hypothesis p=< p N ...pN> +1
so TTQ (pJJ )eP m. a a
Contradiction!
D
r
77 Note that the above is a general property of n-completions.
10.5. pj"^,
V
J
O<
-
a a Proof: The first claim is immediate from lemma 10.1. TJ T4 TJ Let q=p" -nK, r=p" -vK. Let r=p" -vaK . (K=K.) N N N O a a Claim 1 TrOa(r)=r. Proof: Suppose TT. (r) >*r". Then suppose i)) . So Nn i s fUq-sound. But fUq<*rUq; and rUq€P N n. C o n t r a d i c t i o n ! and A1 has t h e same d e f i n i t i o n
If A i s E,(N ) with parameter pJJ n
over N with parameter -nQ (p^ ) then A'nK=AflK; suppose AflK^Nn, .
+
So 7T
(Pvt
) ^P n ,
s o IT
(p
a _ Ta- (r)> A r. N a , that i s , To C l a i m 2 q=P^ + 1 HK.
a
Proof: As T r Q J P n + 1 ) €PNn and \
^
n+1
a
W O ^ r V
) >JLP
a
a D (Claim 1) + 1
)^
a
^
+
then
• T h u s TT
K
we know
K ( x
OaSaOaSOa
+1
t h e r e f o r e p[J nKaEK. Thus P N ^ V ^ O C X a a
(p
N+lnica) a
;
S O P
N+lnKa-*q* a a ( c l a
i m
2 )
a
Corollary 10.6 .
/1+1=Nn+1.
CORE MICE Let X=hNn(o)p^+1Up^+:L) . Let a:M'=N n |x where M 1 is transitive; so a:M'->
N n . Let M, p be unique such that M'=M n p , M is p-sound and
a:M+ N with oz>o and a(p)=
Su
PP°se
A i s
^x^N11) in parameter pjj+1 and
JJ +1 ^N n . Let A 1 have the same E., definition over M 1 from a" 1 Then for Y€U>PJ}+1 Y^A «* y€A' since o (y)-y.
Now A'nwpJJ^1 €M. Let
B=a(A'na)pJJ +1 ) ; so Bn(A)p^+1=Ana)pJJ+1€N; c o n t r a d i c t i o n ! Hence
PJJ+11PN+1
so o)p^+1
i t s
""iterated ultrapower.
M is n-sound
78 because i t i s t r a n s i t i v e . So each M^ i s TT' {< p M . . .pJJ >)-sound. And < < ^ ' a e o n ' * \ i e W o n >' where M;=M™6a (< % • • • ? £ > > , n
n
i s an i t e r a t e d
n
u l t r a p o w e r of M . By lemma 1 0 . 4 a:M -+y N ; so by lemma 8 . 3 t h e r e a r e maps
a : a M^->
n N £ such t h a t
a 7T g (Jte
lMl=7ra8aa'
when
a
l^
; a n d a
o=a#
Let a :M -*_, N be t h e n-completion of a . N i s well-founded, so n+1
Lemma 1 0 . 8 . Suppose Q_ and 0 ' are mice.
Suppose n=n(Q) and n'=n(Q_') . Let
^a€anaeaQ,Q'; let Q =J^a, Q'=J ,. Then Q^, QL. are -a - n - - n 8 6 comparable and Q Q' Qn*J~cfi
(some
U)$€£>IJ ** Qn^Za®
(some
0)3€£';.
Q
P r o o f : Q o =H 0n , s o P (0) 0 0 = P ( 0 ) flQQ ; s i m i l a r l y P (0) n Q ' = P ( 0 ) flQ' By lemma 8 . 1 8 Q 0 , Q ' a r e c o m p a r a b l e . So Q 0 , Q 0 a r e c o m p a r a b l e . — o ' — —— o S u p p o s e Q —J%Qf o)$€QA. QQ*QA s o Qft^OA» B u t i f Q ! = J Q 0 , t h e n P ( 0 ) n Q £ * P ( 0 ) n Q e a sa ) p ^ i + 1 < 0 . H e n c e P(0) OQ|P (0) nQ e . ~0 Contradiction! QI
a)p€O o
Q
Suppose Q =j;:0, o)3€Q'. Then by the last paragraph QA+JifQ* all —U —p
o)"p r €Q e .
Suppose
U
Q0=Q0.
Contradiction! Lemma
10. 9.
Then
U —p
P ( 8 ) flQ * P ( 6 ) flQJ
b u t P ( 0 ) n Q Q = P ( 0 ) fiQ^ .
D
For some
0^=2^.
M ^J — Proof: Let M'=J a, N'=J a . Let 0 be regular, 0>N.JBy lemma 10.8 —a — n' —a — n ^ either M O € N Q or M Q = N Q or N Q €M Q . If N Q =J^0, a)3€MQ, then N I = J ^ , say; ~~o —~u
~~u ~~u
~~o —*u
—"D ~~p
y
~~y ~ ~ P
but then TT0 a:Ml-^« M 1 is not cofinal, contradicting corollary 8.20. N Suppose M 0 =Jg0, then we saw in the proof of lemma 10.7 that there is A € E n + 1 (M)
such that Ana)pJ|+1 $N. But then AOa" 1 (K) £ E n + 1 (MQ)
so Ana"1(K)€N. But a"1 (K)2wpJJ +1. Fix 0 f o r a while. Corollary 10.10. pJJ Proof:
P^-PS^P
Lemma 1 0 . 1 1 .
a (p1?1) ^p"*
Contradiction!
79 ( p ^ x ) €PMn so
Proof: By t h e argument of lemma 1 0 . 7 a
' . But by lemma 8.19
But ^ogfPM^^PM* 1
b y leTma
10
-5
s o
Hence n+1
Corollary 10.12.
=An+1.
A M
N
C o r o l l a r y 1 0 . 1 3 . if1~f'1=tf1+1. Lemma 1 0 . 1 4 .
M_ is
n+1-sound.
+1
+1
Proof: We have t o show MnJ=V=h (u)p^ p^ +1UpJJ +1) . Suppose x€Mn; t h e n a(x)€X / N n h a ( x ) = h ( i , < Y / P ^ + 1 » , s a y . So Mnh=x=h
Lemma 1 0 . 1 5 . 1
JJ +1
TT^SW ' A.
•
0\J
0\J
Proof: M i s n+1-sound and (PJJ) = PN (m<_n+l) . Lemma 1 0 . 1 6 . N=M , for some a. a K l = a ~ 1 ( K ) . Let <^,
Proof:Let
respectively;
so K ' = K ^ . Let a be least such that K^>_K . Suppose
K'>K.
Suppose Mn(= =7T' ( f ) ( K ' . . . K 1 ) —ar K Oa a, a n In where fCM , f : K * V 1 and a 1 < . . . < a n < a M^K=^e(f)(K- . . . < ; ) 1 n so by lemma 1 0 . 1 5 $
o
e
K
;
K'
. . . K
1
. Then (10.7)
. . . K ; ). 1
But
(10.6)
(io.8)
n
j so K€rng(iT oe ). If K = T T O Q ( 6 ) and 6 < K then K = 6 < K . But if K = T T O 0 ( 6 )
and 6 > K then K=TT, . TT_, (6) >TT^, (6) >TT^, (K) >K . Contradiction! — xy ui — ui — ui Hence K ^ = K . Define T:M^->-Nn by +1 T(h Ma n(i,
+
where i€a), y€<. Since
(10.10)
80 (10.11)
where <> j i s E ^ t h e r e f o r e T i s w e l l - d e f i n e d and irM^-^N 11 . But NJ=V=h(KUp?J+1) so T i s s u r j e c t i v e . Hence T:M^=Nn, so M*=Nn, so Ma=N.D Lemma 1 0 . 1 7 .
a=Tr' .
—————————
OQL
Proof: ir£o
Suppose W is a mouse with core M_. Let << M > _ ,< IT g > < g e O n ^
be the mouse iteration point
of M_ and suppose N^=M . Let n=n(M) . Let K be the
critical
of M . Then Y
Proof: By lemma 7 . 1 Nn=hNn(irOa"MnU{ic :y
D e f i n i t i o n 1 0 . 2 0 . Suppose iV is a mouse with core M_, and suppose the mouse iteration
of M_ is << ^ ^ ^ Z ^ g > a
where K is the critical
{Ky.-Y
point of M .
C are E. indiscernibles for < if1 fp1**1 ,y > - % n+1 where n=n(N) . N 1 — N ytu)pp U U P )E^PN P r o o f : I m m e d i a t e b y lemma 7 . 3 and t h e f a c t t h a t rng(irir )E^P P N N •D N
Lemma 1 0 . 2 1 .
c are Z ,. indiscernibles for < N,p* . .pf//Y> or!1*1' n=n(N).
Corollary 10.22.
N
Lemma 1 0 . 2 3 .
nTJ.
K€CN «
~~ N
>
K>(JL)
P^ J
N
ytCup
Proof: Suppose M i s t h e core of N with mouse i t e r a t i o n ^
K
y
t h e c r i t i c a l
i f N=M . Suppose K=Ky. I f K Y =h N n(i, / P ^ + : L » TT
(hMn(i,< ?,pJJ +1 YUpJ5 )
+
>) ) so K €rng(ir
P°int
o f
V
(i€w,J€K Y )
So
CN
then
) , which i s impossible; so
. Obviously K Y >U) P JJ +1 .
81 Conversely suppose K^C... Let y be least such that K > K . Suppose K>a)pjJ+ . Then there are t«
such that
M^K=h(i,<£,pJj +1 >)
(10.13)
N n hc=h(i,,p£ + 1 » .
(10.14)
so
Thus K€h N n(KUp^
+1
).
D
Corollary 10.24. c €11, (Nn). •* •
•
fj
1
—
This fact will be of importance in chapter 11. The fact that the core of a mouse is itself a mouse may seem strange. We are accustomed to measurability being a large cardinal property; yet if M is a core mouse with K critical, n=n(M) and oopJJ
< K then Mf="K is inaccessible"; but there is a S +-, (M) map
of o)p^ onto K . This is not a contradiction, of course; although n+1 a)p = K implies that M is a core mouse, the converse is not true. Indeed, we shall later on give an example of a core mouse with p =1. This implies that M cannot be "continued", i.e. there is no premouse N with M=J
for some a)a€N. This does not only apply to core
mice: by lemma 10.19 there must be a lot of K
for w not to be
collapsed definably. In fact, continuability is a very strong N property: we shall see that if M=J , u3a€N, N a premouse with measure U, then C €U. This topic is taken up again in the next chapter. THE STRUCTURES N™, m>n To conclude the fine-structural analysis of mice we must look at the projectum below K . Let N be a mouse with mouse iteration
Lemma 10.25. For m>0
^
p
j
Proof: If m=0 this is trivial. p^ + m + 2 =n{p N n+m+lp: P ^ P A ^ + m + 1 ) . Now P N n+m+lp=p, n.m+lp' where p 1 are the last m+1 members of p. This follows from lemma 9.6. So pjj+m+2=n{p ^iijin+lp' : p ' C P A ^ } . But p?Jn+l=n{p ,.,n+l. mp": p"€PA :
p, n+lvmp"= p,Nn.m+lp
f
}. Hence it suffices to show
, where p" are the last m members of p 1 .
This would clearly be true if A^n N
n+1
n
for all p€N .
were rudimentary in
But A=A^n
is an iterate of M n , so A is l±(Mn)
f
is ^(N 1 1 ) , and N n
and therefore E 1 (M n ) with
82 parameters from p?. Ucop^
, and hence £, (N )with parameters from
-n+1Ua)p?i+1; but then i t i s rudimentary in N n + 1 . M
—
Corollary 10.26.
Let N_ be a mouse with n=n(N) and mouse
iteration
<
(iv) £*£. Proof: By corollary 10.13 N n+1 =N n+1 . Lemma 1 0 . 2 7 .
a
If N_ is a mouse and n=n(N) then W
is k-sound for all k,
and P^* + 2 =P K ^ • Proof: By induction on k. If k=0 i t i s t r i v i a l . Suppose m=n+k+l and suppose Nn i s k-sound. Then PNm=pNn+k+l=p^nll
(lemma 9.6)
= pJJ + k + 2
(10.15)
(lemma 1 0 . 2 5 ) . m
I t i s s u f f i c i e n t t o show N 1-sound. So l e t X=h N m(cop m+1 Up m+1 ). Let aiM'^N^Ix where M1 i s t r a n s i t i v e . So arM 1 -^ N™. L e t M be such t h a t M^M11^, M i s p-sound,
N, oz>o and a (p) =< p?.. . , p m >. 1 m
a:M-^v
Then j u s t a s i n lemma 1 0 . 7 , M i s a mouse. Furthermore p=
e
> a l 6 e O n >,< < NQ > a€On ,<
^
respectively. Just as in lemma 10.9 there is 9 such that M Q = N Q . So M=core(M Q )=core(N n )=core(N). Say N=M . Then by corollary 10.26 — —y —y — — —ex
N^M 1 .
But M1 i s 1-sound by the argument of lemma 10.14 so N® i s
1-sound. Corollary 10.28.
D If N_ is a core mouse then N_ is n-sound for all n.
n-ITERABILITY We concluse t h i s chapter with some c r i t e r i a for n - i t e r a b i l i t y . Definition 10.29. E is defined inductively on Nnpl'"Pn
as follows
n
EQ(x,y) « x€y Em+1 (x,y) * x, where s(k) is the formula "x=^i,x) A y=(j,y) A E (h(i,(x,p , )) ,h(j,( y,p m m+i m+i
n
83 is rudimentary in N n p . Clearly
Then E
Lemma 1 0 . 3 0 .
Suppose N is p-sound,
only if (E ) np
p€.PA . Then N_ is well-founded
if and
is.
Most of the results of chapter 8 can now bw reproduced with E in place of 6. Lemma 8.3 presents a problem though; the natural approach is to build the maps a , as there, and take n-completions. However we do not know that a :N -»•_ M f . * cofinally. We do have the following, a special case of which was used in lemma 10.7. The proof is the same as the proof of n-iterability in lemma 10.7. Lemma 1 0 . 3 1 .
Suppose O:M+N is the n-completion
If N_ is n-iterable More useful,
though,
Lemma 1 0 . 3 2 . =JQ
to M_ and M_ is
p-sound.
is
Suppose N_ is an iterable
0:M+N'is the n-completion
provided
of O\M
then M_ is.
Af is n-suitable
(that
premouse and for some uxx€.N, letting
of O\M
to M_ (M_ p'-sound)
is, provided
A£ i s acceptable
. Then M_ is and the
N' =
n-iterable
critical
of AT is in cop21; .
point
Proof: L e t <
>a€On'< * i 0 W o n >
critical point of M 1
U , U
1
b e t h e i t e r a t e d
b e a n
and let K
u l t r a p o w e r of N
n-iteration of M. Let K ^ be the
be the critical point of N_a. Let
be the measures of M ,N respectively. We shall define maps o^: {^Pa-»-j. N^ P a such that
^
(ii) oQ=o where P ^ i r ^ t p 1 ) , Pa=*0(x° (P1) • a
is to be ^Q a (3) so N^=TTOa (N1) . The maps are defined by
induction. oQ is a. Suppose a a is defined. Then define
Claim 1
a
a+i
:M
^+} + 1 "*" N a + i b Y
a . - :M^a+l->H a + 1 , where p=ojp", . a+1 a+T p Na+1
Proof: Since a (f)€NlPa
7T
aa+1
:N
'"* e N ( J t + 1 '
N
^ + 1i
s
by i n d u c t i o n h y p o t h e s i s ,
a c c e p t a b l e . Given so f o r a l l £
f€M^pct,
a ( ( f ) ( £ ) € N ' and
N^f=TC(aa(f) (£) )
84 and
(ir
^ + 1 ^ the claim. o(Claim 1) np Claim 2 aa+1 ^, :M a+l-> Eo—a+1 N' n p a+1. —a+I
(a
aa+l a
( f ) } (K
a
5 }< p
'
which
prOveS
Proof: Suppose $ is a I. formula; for simplicity, of one argument. ) (K
But
a ) } ~ M^Pa|=U:<J>(f ( S M K t T
^aa+l^^^Si+l 0 * 1 -
(10.16)
o (Claim 2)
' s o (i) h o l d s ' In the limit case l e t a, (TT' (x) ) =TT .a (x) . Details are left to A
(X A
Ot A Ot
i s rudimentary in N np
the reader. Since E
Mnpa f=En(x,y) «N^npa|=En(a a (x) , a a (y) ) .
(10.17)
But N' i s well-founded so M i s . C o r o l l a r y 1 0 . 3 3.
If N is an iterable
a premouse, O)B€N, W=J^, M acceptable,
_
K the critical oop M
point
p
of N_ and 0)p> >K then V_is n-iterable.
—
If in
addition
then M is a mouse.
~0t
Lemma 10. 34. If N_ is a transitive n-suitable premouse and its measure is countably complete then AT is n-iterable. Proof: As lemma 8 . 9 ; apply t h e argument t o E r a t h e r than € . • D e f i n i t i o n 10.3 5. E* denotes the uniformly Z relation of lemma 8.11 such that whenever < <—
a p a
{<x,y):N^ \=En(x,y)} is well-founded if and only if {< x ,y ):N$=E^(x,y) } is (WjQi) Lemma 10. 3 6. Suppose N_ is an n-suitable N_ is n-iterable if and only if (E ) np is
p-sound premouse, p€.PA ,0) €.N . Then well-founded.
D e f i n i t i o n 10.3 7. Em is defined by induction on m>n by A < * ' ^ / ^ > € A m + I p l * * 'pm+l where s(k') formula
"x=
Lemma 1 0 . 3 3 . ———————————
A y^j/y)
Suppose
m
AE (h(i,<~x,p n
,)) m+l
N is (p,...p )-sound — 1 m
,h(j
,{~y ,p
is the
.)))". m+l
and
n-suitable,
m>n/Ud.€.N — 1
.
Then
85 # is n-iterable
if
and only if
(E ) nip) is well -founded.
Exercises 1. Show that if N is a mouse then the following are equivalent: (i) for some M,N=core(M). (ii) N=core(N) (iii) N is n(N)+l-sound (iv) C N =0. 2. Show that if M is a mouse with K critical and mouse iteration
then
VS ) n P ( l °£V
3. Suppose M+=J^+1 i s a premouse and M=Ja i s a mouse with n(J a )=O. Let
Show that in general N' + ru'M). Do N 1 , n (M) have a common iterate? 4. Suppose N is a mouse. Show that if A€£n(N)flP(p) arid A^N then
86 11: ACCEPTABILITY REVISITED
This chapter will prove that iterable premice are acceptable. The proof will be inductive; the reader can check immediately that the limit case is trivial: that is, if J, is an iterable premouse and X is a limit, and if JU is acceptable for all a<X a U then J, is acceptable. + U We shall be assuming that N = J a + 1 is an iterable premouse with K critical. We shall be able to assume that N=J is acceptable. This implies by corollary 10.33 that either w p S x for all n - and this case will present few difficulties - or N is a mouse. The two cases cop = K and cop < K are handled separately; there seems to be an overlap between them, but there is not. THE CASE iup^+1
of N ; so C N = { K :y<*}a n d
K=K
x*
Let
K=K
o*
CL Reca11 tnat c en i(N N
) , so
C £ N
Lemma 11.1. c Eu. Proof: By lemma 10.23 C N ={K'
(11.1)
=0 if there is none. Clearly {£:£€hNn(f(£)UpJJ+1)}€U; and f€N + . By chapter 5 exercise 6 there is 3 such that {£: f (£) =3>€U. Hence Y = U : C€hNn(3UpjjJ+1) }6U. But then Y€N + , Y ^ in N + and Y is cofinal in K . Contradiction! D This makes precise our remark in chapter 10 about continuability. Let C N = { K :y<X A y is m-good}. Then cJj€N . Lemma 11.2. For each m€co N
Proof: By induction on m. If m=0 use lemma 11.1. Suppose C N €U; CM IN
= { K ' € C M : K'=sup(K'flc!J)}. Let f:K->K be defined by IN
JN
87 so f€N + . £(£)<_£,, for all £.Suppose {£:f(£)<£}€U. Then by chapter 5 exercise 6 there is 3 such that {£:f (?) =3>€U. So U : 3=sup(£flCm.) }€U; hence C™ is bounded in K . But C™EVl So {£:f(£)=£}€U; that is, c"
€U.
D
N
Corollary 11.3.
A is m-good for all zn
So by c o r o l l a r y
7.20
Corollary 11.4. *
d"1 are E _ indiscernibles N m+1
for < i/^/ir., (x) > ^-n. — 0\ x€N
Corollary 11.5. *
C7" are I , indiscernibles N m+1
for
C o r o l l a r y 1 1 . 6 . d° are E Lemma 1 1 . 7 . ————————
Proof:
J f x€PCK;nw
indiscernibles and x£E _ CN; n+m+l —
n+
for
,-)
then
If C ^ y e X then X€U by lemma 11.2.
Conversely suppose cJJ^y^X for all y
s
n+m+1-
1
Then for some £ n + 1 term t p=t (K^^ ...K i ,P N »..
. . . P ^ 1 ^ ! - - - Y q ) where iK ± , or y>u)p^+1 if p=0. Pick j such that K .>y and K.€CJJ. By lemma 7.12 we may assume that
K
=ch m (a')=m. Hence by corollary 7.19 K a €X **K a i e x follows that C^ycK^X, i.e. K ^ X C U . S O X^U.
Since C ^ y ^ X it
D
Lemma 11.7 says that we can predict whether a definable set will be in U just by looking at UDN. From this we deduce Lemma 1 1 . 8 . Let M=ruduf]N(N) . Then (M,u)is
amenable.
Proof: Suppose X€M, X C P ( K ) . By lemma 2.43 there is p such that X c E n + p + 1 ( N ) . Then xnU={Y€X:3y
But C €Z
P
(N) , s o C €M. Hence XflU€M.
(11.2) n
Lemma 11.9. N+=rudu(] (N). Proof: Every x in N
is definable from parameters in NU{N} by a
88 function rudimentary in N + . But <M,€,U>^=R so the same function has a value in M, and this value must be x by absoluteness. So x€M. Corollary 11.10. P(K)fli/=P(K)nz^(N). Proof: This follows from lemma 11.9 by lemma 2.41.
•
•
This result is important in many places. It does require the n+1 assumption cop < K ; after all, the measure must be unpredictable somewhere. Now put this case aside for a bit. THE KeepCASE the (notation introduced for the previous case. This time we shall show that H^=H^ , and therefore that ojp^=K for all m>n(N). Thus in this case the previous case cannot arise. A small change of convention is needed. Consider the case where N =J _, so N=J . The reader may easily check that J =J , so by U K U lemma 4.27 J is strongly acceptable. Also E (J )cj + _; hence since J +-,f=K ^ s a cardinal, cop =K . We want to apply the argument of the K
+1
- < , ^=
Lemma 11.11.
+1
Let H^ .
be the critical point of N . T ^
1
;
H;=<S a ,T a >.
ir O\H :H •+ HQ.
a3' a -a e ^ Proof: TT ft(H )=Hft. So otp — a
—p
^ ( x ^ . - . ^ t x ^ ) «N;HigH(^6(x1)...1raB(xm))»
(11.3)
Corollary 11.12. H -
—ot — p
Proof: IT O |H =id|H . For H =U{j a :acv
•
Lemma 11.13. H \=ZFC. Proof: H f=R , so we need only check separation, collection and power set. Note that H GH Q . For HQ(=VyJBBexists, where B Q = A £ + 1 . But ot
p
p
y
p
N«
89 \x6
(B
)=B
a
3
so B
a
=B
8
na)X(K
a
)
Hence
^ H ^
exists
-
(a) Separation. Suppose <{> is a formula and * € H a . Since H o h R there is y£H R such that (P €H a >
H3|="t€y ~ t€x A Hj=
(11.4)
so
«* tex A <|>(t,p))
(11.5)
so the same statement holds in H . (It follows immediately that cop™ =K^ for all m>n.) s-
a,
A.
(b) Collection. Let x€H . Suppose u€x, a<3. If Hg^=3v(|> (u,v,p) A
/\
t h e n Haf=3v<j> ( u , v , p ) .
Say
A
A
/\
Haf=<j> ( u , v , p ) .
Then H ^ v € H a
A
<j)(u,v,p).
A
A.
Hence Hgf=3v(|) (u,v,p) «• OvGH^) <)> (u,v r p) . So for x€H a H3l=3yVuex(3v
(11.6)
So the same statement holds in H . —a (c) Power set. Let xGH a . Let 0 be a regular cardinal greater than 2 X . Then K Q = 0 and P(x) nH Q <6. So P(x)f1HQcJB , some Y < 6 . S O u w w— y H0|=3y y3P(x) .
(11.7)
So the same statement holds in H . —a
o
In case N + = J ^ + 1 , Haf=V=L. This result will be generalised in part four. Lemma 11.14. H = H V Proof: H a cHg, so H a £H^3. Suppose x€H g and H ^ T C (x) <
Ha^Ha
is a limit cardinal, so x€H 3r some y
The strategy for the proof of the result we are after is as follows. Suppose we could construct all of N +
~
A
in some H . Then
~~ A
H cH a=H cN,and the result would be proved. H hZFC, so we can certainly construct N in H if ot>0. If
with X C K for all y
Since X 6U « KETT X (X ) therefore {Y:X Y €U} = {y:K€7r01(XY) } (11.8) But also < T O 1 ( X ) :y
90 {y:X €U}€N + . As t h e r e i s a d e f i n a b l e map of K o n t o N i n N + working with K-sequences i s no hardship. Lemma 1 1 . 1 5 . ————————
N €#Q and is uniformly definable —<x p
over HQ from K provided a<$. —p a
Proof: H'€Hg and is uniformly definable from K . As H^f=MC
there
is M with McH a and p€PA^ + 1 such that M p = H a and M is p-sound, iterating lemma 3.26 n+1 times. And M is unique up to isomorphism; so M=N ; hence M is well-founded. But then N from M as its transitive collapse. Lemma 11.16.
is uniquely definable
o
{ K :a<3) are Z indiscernibles for Ho. a)
a
—p
,
Proof: They are £, indiscernibles for N g .
•
Let y^ b e the smallest elementary 1substructure of H , containing 3 a /s —a+m K U { K . . . K ^ , } . L e t IT :M m =H ^ 1IX^ where M is transitive; so a a a+m-1 a — a —a+m a —a ™rfn
L e t K m = H ^, where K ^ denotes the successor of < a in a
Lemma 11.17. fr^|/=id|/\
a
^
^
Proof: We have to ghow ^ O H ¥ + m transitive. Suppose x€X m , x€H H a a +m a K(X ~ H +^=x<j< there is f€H + m Then obviously xcH + . Since H +^=x<j< there is f€H + m mapping onto x. Let f be least such in the canonical well-order of H a
Then if y€x, y is definable from f and some y from x.
•
? but f is definable
D
M ^ R , for H a+m|=R. So K ^ R . X^=H a so M°=H a . By lemma 11.17 K m = X m n H H * + m ; and ^f H M are in X m + 1 . But H ^ ^ > Kr m = K so K m € K m + 1 . a a K a a+m a —a+m+l a a a a By lemma 11.15 N a €X^ ; and \=*a in H + 1 , since 0)pJJ+1=Ka. Thus N ^ K ^ . Let f™ be the least map of <^ onto
p
(Ka)nK^
in
t h e
canonical
well-order of j j ^ ^ . So f™ is definable over £ a + m + 1 in {<&. . and the definition is uniform for all a. Lemma 11.18. Proof: Let a:N , . n->r N O l ,, be the map of lemma 8.3 such that —a+m+1 Ei — p+m+1 (i)
aiT
aa+m+l=7Tap-+m+l
(ii) a ( K a + p ) = K 3 + p (p<m) So by the uniform definability of f™ f m (y)=a(f m (y)) for Y
91 (11.9)
Now Lemma 11.19.
^
^
Proof: U a nK™={f m (Y) ••y«a A K ^ " " + 1 ( Y ) } • But f m + 1 Sa+m+2
from
K
is definable over
a+l"-Ko+m+l •
Let K = U K m . K is transitive and rudimentarily closed. By m is amenable. Thus < K a , €,U a >|=R. But N a
Lemma 11.20. H <=H . + Ha Proof: N cK cH^+cH, where H=H a a K a w a Corollary 11.21.tf£«J£.
+ N
a~ . By lemma 11.14 H K cH . a a
THE CASE O)p^>K FOR ALL n<0) This is not very difficult. Lemma 1 1 . 2 2 .
Suppose upn>K, all n<0). Then N =rud
P r o o f : L e t M=rud
n
«W .
(N) . T h e n <M,U> i s a m e n a b l e . F o r g i v e n X6M, i f
X C K then X€N, since P (K) OM=P (K) fiE^ (N) by lemma 2.41. So given Y C P ( K ) Y6M we have Ynu=Y(1(unN) . But unN€M so YflU€M. Hence <M,€,U>(=R so N + cM. But clearly McN + . Corollary 11.23.
•
?(K)ONf=?(K)nZ (N_)=P(K)0N.
Proof: Like corollary 11.10.
o
So much for that. ACCEPTABILITY A lot of the difficulties that remain arise from the need to obtain a sequence of functions
rather than
individual functions. It is helpful to prove the simpler version first, though, as the strategy gets obscured by the details in the proof proper.
92 Lemma 1 1 . 2 4 . Suppose N_ is an iterable
premouse and N_ is acceptable.
Suppose
aoS, a € i / \ N . Suppose u€N* and u<=P(6) . Then tf*\=~u<&. (&€0nN) Proof: Case 1 For a l l n_K. Then by c o r o l l a r y 11.21 and c o r o l l a r y 11.2 3 6_>K. And t h e r e i s n such t h a t oopjj£6. By lemma 9.7 t h e r e i s a Z n o n t o N. I f u € S ^ + k , Case 2
(N) map of a s u b s e t of 6
OnN=0)X t h e n t h e r e s u l t f o l l o w s from lemma 2 . 4 2 .
For some n<w wpN
By c o r o l l a r y 1 1 . 2 1 l e t t i n g n=n(N), ojp^+ < K . Hence by c o r o l l a r y 11.10 a£E
(N). L e t M be t h e c o r e of N w i t h mouse i t e r a t i o n
<<M)
,( 7T
Q
)
Q
), l e t K be t h e c r i t i c a l p o i n t of M and
suppose N=M,. ~~ ""A
We may assume 6 < K . Let a be least such that 6
+ 1 (N)
by lemma 2.43. Then ucE + 1 (N n ) so by corollary 7.18
n
ucZ + . (M ) . For some m wp™ <_6 . We can get a subset of K that codes all the I + 1 (M n ) subsets of 6; call it A. Then A€N + by chapter 10 exercise 2. But then N~F=U
onto K_.
Now we must do it properly. Keep the terminology of the previous lemma. L e m m a 1 1 . 2 5 . AT is strongly acceptable above K (and hence the axiom of acceptability holds in i/ for all 6>K) .
Proof: Suppose ac6 , K_< 6 , and a€N ^N. 11.21 9.8.
By corollaries
and 11.23 wpJJ_<6 for some n so this follows from lemmas 9.7 and D
So the proof is complete if P(y)nN=P(y)ON assume that N is a mouse and that wpj^
for all y
Let M be the core of N and let <<M > cr, ,< IT O ) ^ocr. > be its — — -—ex otton otp ot^ptvjn mouse iteration. Suppose N=M, and let K be the critTcal point of ~~ — A
Ot
M . Suppose ac6
The axiom of acceptability
holds in N_ for 6
93 Proof:By lemma 11.25 we need only produce a sequence
<JZ,
(m>l) . Since for only finitely many m is p n + m + 1 < p n + m this
will suffice. Take uGN
. We may assume ucP(K)flN . So by lemma 2.4 3
u£Z n + p + 1
The sequence f . 1 The relation R ( K ,£>,i) is defined by R(Ka,p,i) «,^=TTaX(p) A M ^ . © where (f>± is the Z Up
N
+1)
+1
^±
(11.10)
formula s(i). Since ^ " M ^ h ^ K ^ U p ^ " 1 " 1 ) , letting (
P>
" Nn|3H±<e)
(^=^aX(P)); and the
sequence
such that K >JE,. k is definable over N. Let Y,7,PN +1 >' i )>-
(11.11) +1
So g is definable over N. Since k(^)chNn(^UpJJ ) , H | 7 +1
^ . Let ( t p ) . < K be such that t : £+u)x (k (£) )
N
onto, or
Let f*(y)=gU,Y,i) if t^(y)= and =^
otherwise.
We must show f ^: ^(ur\?(E,) ) U ( U onto. Suppose a€unP(^), ^ < K . Then a € £ n + + 1 ( N ) , so a€Z lary 7.18 a€E
+1 (MjJ(r))-
\=$. (y,y ,p™+1
y€a ~ M ^
Sa
nn + 1 ( NN )).
By
Y Y€(k(^)) < a ) such that
).
(11.12)
y€a «* R(k(^) ^ Y , ^ , ? ^ 1 ) , ! ) .
(11.13)
So Hence ,i) Suppose < i , Y > = t £ ( ? ) . Then a = f ^ ( ^ ) . Case 2 The sequences f m + i
(m>_l)
Let u'=unP(o)p^ +m ) . So by corollary 7.18 u'cE u'cE
+1_m(M
the Z
+1_m
n+m
)
(11.14)
+1
(M n ) . Hence
(without loss of generality m
formula s ( i ) . Let A={< i, y, r, >: i
A Mn+m|=(()i(C,Y,pJJ+m+1)>- Then A € Z p + 1 ^ m ( M n ) ; hence A € Z p + 1 (N n | X Q ) , so A € N + . Let t€N + , t:o) P £ +m+1 +u)x ( a 3 P ^ + m + 1 ) < a ) onto. Let
94 f m + 1 ( y ) = { C : < i,Y/C>€A} i f t h i s i s i n u =£
Proof:
(11.15)
otherwise. •
This suffices. C o r o l l a r y 11.27.
(t(y)=)
If N_ is an iterable premouse then N is acceptable.
I n d u c t i o n b a s e d o n lemma 4 . 2 7 , lemma 1 1 . 2 5 a n d lemma 1 1 . 2 6 . D
Corollary 11.28.
If N_ is an iterable
n top^
premouse with K critical
and for some
premouse.
If N is an iterable
premouse with K critical
and for some
uatN, Ka M=J with u>pn
a
ff—
—
Proof: By corollary 10.33 and corollary 11.27.
•
Exercises 1. Is every core mouse strongly acceptable? 2. Show that
such that if aey
minimally? 5. Find a,A,B such that J
is strongly acceptable, J
is not, but
95 12: O
At last we are in a position to construct a mouse. The existence of a mouse turns out to be equivalent to a well-known large cardinal axiom, that 0
exists. Each is equivalent to
the existence of a non-trivial map j:L-> L. We are going to prove u
(i) if there is an iterable premouse then 0 exists; (ii) if 0 # exists there is a non-trivial j:L+ L; e (iii)
if there is a non-trivial j:L+eL then there is a mouse.
D e f i n i t i o n 1 2 . 1 . A sharp is an iterable premouse N_ with K critical
and On--
Lemma 1 2 . 2 . If there is an iterable premouse then there is a sharp. Proof: Trivial.
o
Lemma 1 2 . 3 . If N_ is a sharp with K critical
then H <=L.
Proof: cop =K. SO by corollary 11.21 H c j cL.
•
Note t h a t in addition P(K)nLcN. Lemma 1 2 . 4 . If N_ is a sharp then JV is a mouse with
n(N)=O.
Proof: There i s a £, (N) map of K onto K+OO SO ojp
L e t6>N,N';
l e t <<^
then N_, tf' have a common
>a£On,< iraB >
a l B € O n
iterate.
>,< < N ^ > a £ O n , < i r ^ >
a l B e O n
be the iterated ultrapowers of N,N' respectively. So N Q ,N' are comparable. But 0n.T =On.7,=9+co. So N Q =N' .
N6
N
o
-e -e
0
Let M be the core of some, and hence of all, sharps. This is fixed from now on - obviously M is the unique core sharp - and K is its critical point. Lemma 12 . 6 . p =1; p =0 . 1 MM Proof: Let X=h M (K) . Then X ^ =a
__ E
M. Say a:N=M|x. S O a:N-*E M. Let K =
( K ) . Then N is an iterable premouse at K; so N is a sharp.
!
96 Hence N is an iterate of M. But
K £ K S O N=M. But then there is a
parameter free map of u) onto M; so P M = 1 / P M =0 -
D
Corollary 1 2 . 7 . If N_ is a sharp then p =2, p =
W
could be coded as a real and would be a reasonable u u u definition of 0 . In fact 0 is a different real, but 0 €L[A M ] and M
A €L[(T ] , as we shall see. << ^a > a€On' < 7 T a3 > a<3€On > b e t h e i t e r a t e d ultrapower of M; let K be the critical point of M ; let C = { K :a€On}. We now apply the apparatus of the previous chapter. Let N =J a, so M =N . Note that H =N in this case. Hence by corollary 11.12 J -< J , a a a S when a£$, and J^ ^=ZFC by lemma 11.13. By lemma 11.16 {i
. The structures K m are defined as
indiscernibles for J
before; K m c K m + 1 , Km-<:J + and K = U K m . Also M cK and