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!
: @(P, 4 , I) = > { and B = {y:(p, y ) V~> .Prove that if F i s a normal sequence of universal functions for the n-th projective class Pn(NN) orC,(V", thenthepair(U, V)where U = ((9,y ) : y ~ F ~ ( K * ( c p )and ) } V = {
" {
The set ( ( p , q ) : A @ ( p , q , r ) } is Gal), and finally the set r
') This follows from the remark that a projection of a closed and bounded set in the space 6. is a closed set, and consequently, a projection of any closed set is an F,-set. For other spaces (for example NN)this theorem - as we know from 5 4 -is false.
367
5. PROJECTIVE SETS
v Y ( P ,4)L
A = {P:
where
4
W P ,4)= ,AW P ,4, r),
is of the first projective class, as the projection of a Csset '). 2. Let a be a double sequence of natural numbers (i.e. a E N N x N ) such that the set {(m, n, p ) : a,,,,, = p } is arithmetically definable. Denote by A the set { m : lim inf am,,= m}. We shall show that n+ m
+
the set A is arithmetically definable. For
Writing
v [x+y = z] instead of x < y
we may rewrite the formula
Y
above as
mEAr/\VAV[(n+u=q)v(p+v=a,nn)l P
E
q
nu*
A Vq A V [(w + amn) v (n+u p n uvw
= 4)v @+o = w)I*
Since each of the propositional functions w # a,,,,,, q+u = n, p + v = w is projective with respect to D, the set A is also projective with respect to D. Using Theorem 4 it is easy to see that if the propositional function w = a,,,,, is of the class KOwith respect to D, then the set A belongs to the class K4 with respect to D .
8 6. Universal functions Let S be a set and KO a base, that is, a family contained in the union 2s4satisfying conditions (1)-(5) on p. 359. As on p. 359
u
q>o
we denote by K,, the nth projective class with respect to KO and we let K,,,4= 2" K,,. 1: For an arbitrary family R of subsets of DEFINITION
u S4,f is
qcN
l) The arguments above d o not imply that our estimate is sharp, i.e. that we cannot lower the class in this estimate. However, in our case the estimate is sharp, because there exists a closed set F c C3 for which the set A is non-Bore1 (this was proved by 0. Nikodym, Fundamenta Mathematicae 7 (1925) 250 and by P. Urysohn, Proceedings K. Akademie van Wetenschappen 28 (1925) 984).
X. ANALYTIC A N D PROJ'@CTWE SETS
368
a universalfunction for R if the domain off is S and the range o f f is R.
DEFINITION 2: A sequence F of functions is a normal sequence of universal functions for R if (1) Fq is a universal function for the family R n 2# (q E N, q > 0); (2) for q > 0 the set P, = { ( x , s ) : xeFq(s)} belongs to R n 239+1. THEOREM I: If F is a normal sequence of universal functions for the n-th projective class K,,, then the set Mq
= {<xo, * - - ,
xq-2,
s>: (XO,
xq-2,
.'.Y
belongs to Kn+l,q-Kn,qif n is odd and to
s> $w91
Kn-l,q-Kn,q
if n is even.
PROOF.If Mq E Kn,q, then for some soE S
...,xq-2, xq-l> E Mq <xo, ...,+ l > for arbitrary x,, ...,X,-~ES,By the definition of <xo,
3
0 0 , ".,xq-2,Xq-l)
$F&q-J
E iF,(so)
Mq we have
= (xo, ...,xq- 2,Xq-l>
EFq(S0).
Letting = so we obtain a contradiction. Thus Mq$&,q. The set M q arises from by identifying the qth and (q+ 1)st coordinates and then by complementation. The first operation leads from a set belonging to Kn,el to a set belonging to K,,q (see Theorem 1, p. 3601, the second operation leads from a set belonging to K,,,q to a set belonging Kn+l,qor to Kn-l,q depending upon whether n is odd or even (see p. 362). Thus Theorem 1 is proved.
rq
COROLLARY 2: r f for every n 2 1 there exists a normal sequence of universal functions for the class K,,,then all inclusions in the diagram (see p. 361) Ki -+K3 + ... -+ KZn-1-+KZn+1-+...
KO/"
I/I
are strict. Moreover,
\r
/I
6. UNIVERSAL FUNCTIONS
369
PROOF.From Theorem 1 it follows that Kzn+t-KZn+z # 0 # K2n+2-K2n+t (3) for every n 2 0. If KZnbl= K2n+l,then by the diagram above K2n+2
c Kzn-t = K 2 n + l
contradicting (3); similarly, if KZn= K2n+2,then Kzn+t
c Kzn = KZn+2
also contradicting (3). Moreover, K2n-1= K2n+2implies K2,,+*c K2n+l, and KZn= K2,+l implies KZnfl= KZn+2. Analogously we show that KO# Kt and KO# K2. Corollary 2 shows that if for every n 2 1 there is a normal sequence of universal Functions for K,, then for arbitrary n >, 1 there exist sets belonging exactly to the nth projective class. Thus in this case the classification of projective sets cannot be reduced to a smaller number of classes. We shall prove that the hypothesis of Corollary 2 is satisfied when S = NN, n > 0 and the base KO is the family B = B(NN)OF Bore1 sets. The construction of the desired sequence of universal functions proceeds in several steps. Firt we let Gq be the family of open sets of the space (NN)qand let G = Gq.
u
q>o
LEMMA 3: There exists a normal sequence of universal functions for the family G. PROOF.Every open set X E G , is the union of the neighborhoods it contains, that is, of the Cartesian products
where e is a finite sequence of natural numbers. Using the one-to-one function 0' introduced on page 98 to map N onto the set of finite sequences of natural numbers, we can represent every neighborhood in the form N0qaj)where ai E N f o r j < q. Let C4 = -c;-l (see p. 98) map N
n
j<4
onto N q . Then Cq(n) is a sequence of q terms C,(n,O), Cq(n, l), ...,
3 70
X. ANALYTIC AND PROJECTIVE SETS
[ J n , q - 1). Thus an arbitrary neighborhood in (NNJqcan be represented in the form where n E N . Let The function H a is universal for the family Ga. In fact, for every p the set Hq(v) is open because it is a union of neighborhoods. If X EGq and p is the sequence of all natural numbers m such that O ( m ) c X, then X = Hq(v). Thus the range of Hq is Gq. It remains to show that the set rq= {(x, v): x ~ H , ( p j }is open. r,,,, where Tq,,= ((x, 9): x E O(p(m))}; This set is the union
u
msN
it suffices to show that each set that (x, V) = (970, ..., pq-l, p) ~ r (yo,
rq,m is open. For this purpose assume q , m i.e-
...)~ q - i ) E o ( ~ ( m ) = ) Il~oCcq(P(m),i), j
or Let 0' =
vjENoc
1<4
(vo, ...,Q ) ~ v} - ~ in , the space (NN)q+'.We shall show that v') E 0', then p'i(m+ 1) = pj(mf1) In fact, if (v;, Sri; E Not cq(v(m),j)
for j
0' c rq,m. and
< 4-
It follows that p'(m) = q(m) and thus V; E N o c cq (v,(m),j) for j < This shows that (pi, ..., pi-^) E O(cp'(m)), whence Q.E.D. ( ~ i.,.., ~ i - 1 ,p') E rqm , LEMMA 4 : There exists a normal sequence of universal functions for the family PI(") of analytic sets. PROOF.Let 4q(v)
=:
("Y
= ("1'
v (x, Y > $ Hq+1(v)1 {x: v ((XY YY v)
n {x:
n
V,+l)I.
371
6. UNIVERSAL FUNCTIONS
Since the set P,,, is open, it follows that Flq(q)as the projection of a closed set is analytic. If X is an analytic subset of the space (NN)', then X is the projection (say with respect to the qth axis) of a closed set Y in the space (NN)qtl(p. 352). Thus, for some 9, Y = (NN)q+l -Hq+l(v) and it follows that X = Flq(q). Finally the set { ( x , q>: X E Flq(v)} is analytic, because
V
xEFiJ(P) = x E ( N N Y A
Y<.[
YY(P)
$rq+&
Y,
hence this set is the projection of a set closed in (NN)q+I. Lemma 4 shows that for the family of projective sets the hypothesis of Corollary 2 hoMs in the case n = 1. In order to extend this result to higher projective classes we shall make use of a mapping which will allow us to replace a finite number of projections by one projection. Let h be a fixed positive integer; for j < h, and for arbitrary v E N N , let (see p. 353) @ = P [ p ( h n + j ) ] . It is easy to check that if q > 0, nEN
then the function &,h:
<%Y
..'Y9 ) q - l ~ 9) *
vq-l,Q)(o), **.,Q)('-'))
maps the space (NN)'Jf'onto the space (NN)q+".
LEMMA 5: If n 2 1 and B belongs to one of theprqiective classes Pn(NN) or Cn(NN)and i f B c (NN)q+h,then the set &;\(B) belongs to the same projective class and is a subset of ( N N ) q f l .
PROOF.The invariance of the projective class follows from Corollary 7, p. 364 and from the remark that the set W = {(x,~): f,,,(x) = y ) is closed. In order to establish the validity of this remark we assume that (X,Y)+W
and
x=
Y
=
and
.yq-l'fio, .-.
Y
2qk-l>.
From the inequality y # fqr(x)it follows that either (Pi # yi or ( P ~ ./L) fij for at least one i < q1j < h. If for instance pi(n) # yi(n)then, taking as a neighborhood U of the point (x,y) all those points (X',Y') =
(74,...,Q);-1,p),yo, ...Yy;-l,%, ...,4-1) I
)
for which the equations qj(n) = P?;(n)and yj(n)= y;(n) hold f o r j < q,
372
X. ANALYTIC AND PROJECTIVE SETS
we infer that the sets U and W are disjoint. Similarly, one shows that if v(J)# 6,, then there exists a neighborhood of the point (x,r) which is disjoint from W.Thus the complement of W is open and W itself is closed.
n
6: For each of the projective classes P n ( N N )and C n ( N N ) , THEOREM 1, there exists a normal sequence F@),F'(") of universal functions.
PROOF. The existence of the sequence F ( ' ) was proved in Lemma 4. Thus it suffices to prove that (I) the existence of F(") implies the existence of F'(") and (11) the existence of F'(") implies the existence of F("+I). (I).Letting Fi(")(y)= (NN)4-F$')(y) we obtain, as can easily be checked, the desired sequence of universal functions. (19. For this case, let
{ V (x, y> E F;Y&~)}.
~F+l)(p1) = ( N N ) ~n X :
v
The set {{x, y ) : x E F $ + ' ) ( ~ ) }is the projection of a set of the class Cn(NN),because x E F t + l ) ( Y )= [(x, y) E F;y&)].
vv
Therefore this set belongs to the class Pn+l(NN). For every y , F p l ) ( y )E Pn+l(NN).It remains to show that every X of the class P,+l(NN) can be represented in the form F:+')(y) for some yo. If X c ( N N ) qthen X arises from a set B E C,,(NN)by finitely many projections. If h is the number of projections, then B c (NN)4+h. Since permutation of coordinates does not change the projective class of X we may assume that
This condition is equivalent to
that is,
373
6. UNIVERSAL FUNCTIONS
The set f,sk(B) belongs to Pn+l(NN)(Lemma 5); it follows that for some plo, f4;i(B) = Fiti(y0),which implies that
x EX= // [(x,q ) E Fiy](qO)] 3 x E F$"")(plo).
Q.E.D.
P
Theorem 6 implies, in particular, that in the space N N for every n there are sets which belong to the nth projective class but not to any lower class. We conclude this section by giving examples of families for which there exists no normal sequence of universal functions. THEOREM 7: There does not exist a normal sequence of universal functions either for the family B of Borel sets in the space N N or for the family K, of all projective subsets of NN. PROOF. Assume that @ is a universal function for the family Bn2"" (or for K m n 2"w). It suffices to show that the set {{y, pl): y ~ @ ( p ) } is not Bore1 (or projective). Supposing that it were Borel (projective) then the set {q: q E @(pl)}, and thus the set {T: q $ @(y)}, would also be Borel (projective), since the operations of identification of coordinates and of complementation do not lead outside of the classes B and K,. From the assumption of the existence of a normal sequence of universal functions it then follows that for some plo, { q : q $ @(q)}=@(ploj, that is, pl # sP(pl) = pl E @(plo). Substituting plo for p we obtain a contradiction. Q.E.D. In 0 11 we shall use the following theorem, which can be proved without difficulty by applying the methods obtained above. O
THEOREM 8: For arbitrary n and for k 2 I the classes B ( N ~ ) ~ ( N ~Pn(NN) } ~ , n (NNjk
and
c,(NN)
n
are a-additive and @-multiplicative.
PROOF.The theorem holds for the zero projective class, because this class coincides with the family of Borel sets. If the theorem holds for the (2n+ 1)st class (i.e. for Pn(NN)), then it holds for the (2n+2)nd class (i.e. for Cn(NN)), because sets belonging to this class are just complements of sets belonging to the (2n+l)st class. Thus it suffices to prove the theorem for the class Pn+l(NN)assuming that
3 74
X. ANALYTIC AND PROJECTIVE SETS
it holds for the class C,,(NN). (If n = 0 then we replace C,,(NN)by the class of Borel sets.) Therefore, we assume that &EP,,+~(") and X i c ( N N ) kfor i E N . By Lemma 5 it follows that there exists a set Yi c (NN)k+' such that YiE Cn(NN),and xeXis
v [ ( x , ~ ) E Y ~for]
iEN.
B
Thus XEUXi-V i
which implies that
[ ( x y 6 ) ~ Uyi], f
8
u Xi EP,,,,( N N ) ,because by the inductive assumpi
tion
UI YiECn(Nh)*
To prove that tain X E
ni X i E P " + ~ ( Nwe~ )apply (10) from p.
123 and ob-
n xi= p, v ((X,6)Ey i ) = v A ((x, w ) ) ~Y*), i
i t 9
B
m
where I?(~) is defined as on p. 99. It remains to show that the set {(x,6): ( X , ~ ( ~ ) ) E Y belongs , , , } to class C , , ( N N ) . But this set is equal to the set f - ' ( Y , x N N ) , where f is the function defined by the equation f ( x ,6) = ( x , O(m)). Because the graph of this function is Borel, applying Corollary 7, p. 364 we obtain the desired result. Exercises 1. Prove that the classes Pn(NN) are closed under the operation (A) for n > 1. 2. Prove that there exists a normal sequence of universal functions for the families F d , Ga, Fd,Gee, etc. in the spaces NN, (NN)Z,... and derive as a corollary a statement about the inclusion relations which hold between these families.
3. The pair (U,V), where U and V are subsets of the space (NN)Z,is a universal pair for a family K of subsets of NN if and only if for arbitrary sets A, B E K there exists V E N N such that A = {y:
375
7. SIEVES
57. Sieves In $9 7-11 we shall use the theory of ordinal numbers to investigate the projective sets of the space ( A V ~ )We ~ . shall denote this space by X , where k is an arbitrary fixed natural number (without loss of generality we may let k = 1; see p. 353). The applications which we have in mind make use of a special ordering of the set d = N"+l, that is, of the set of a11 non-empty
u n
finite sequences of natural numbers. 0 will denote the one-to-one mapping of d u (0) (the set'of all finite sequences of natural numbers) onto N which satisfies the condition a(0) = 0 (see p. 98). For arbitrary sequences e E N", f~ Nm(n > 0, m > O), let
e 42 f -
V (f=elk),
kim
e -5 f-[(e=f)v(e <1f)v(e<2f)l.
The relation e + 2 f holds exactly when f is a proper initial segment of e. The meaning of the relation 31is illustrated by the following examples: 41<3, lo>,
41<5>,
<4,1,5>41<4,2,8,2).
the set d into type q. 3 -is obvious. Antisymmetry. Assume that e 3 f and f 3 e. If neither e is a proper initial segment off nor f is a proper initialsegment of e, then either e =f, or there exists a least k < min(n, m) such that ek #&. In the latter case it follows by the assumption that e 3f and f 4 e; but e 3 f contradicts the inequality fk < ek and f 3 e contradicts fk > ek. Thus the only remaining possibility is e =f. Connectedness. Assume e # f and e non <J Iff is a proper initial segment of e, then e 4 2f and thus e 3 5 Otherwise there exists a least k < min(n, m) such that ek Zfk; and by the assumption that e non < A we have ek > h and thus f -3e. Transitivity. Clearly e S2f F Z g-+ e F2g.
THEOREM 1: The relation PROOF.The reflexivity of
3 orders -
376
X. ANALYTIC A N D PROJECTWE SETS
If e + l f ~ 2 and g k is the least number such that ek #A, then ek >fk and ek > gk because f is a proper initial segment of g. Moreover, ep =fp = gp for p < k . Thus e Flf F 2 g e >lg. If e g2f + l g and k is the least number such that # gk, then f k > gk and fp = gp for p < k. If the length of e is greater than k, then it follows that ek =fk > gk and ep = g p for p < k , and thus e + l g. On the other hand, if the length of e is less than k, then e F2g, because e j =J; = g j for all terms of the sequence e. Thus e F1f >2 g +e>g. Finally assume that e > f F g and let k and h satisfy the conditions
-,
ek>fk,
P
q
<
e >l(eO~ . . - 7 e k - 1 , f k 9 f k + l + 1 )
=
(hi * . - 7 f k - 1 7 f k , f k + 1 + 1 )
>If;
if, on the other hand, the length off is k+ 1 , then 7fR-17 ek, 0) >If* ek-1, ek7 0) = ( f 0 7 e > 2 (e07 The set J is, therefore, densely ordered without first or last element, thus the order type of d is '11 (see p. 219). # W e can prove Theorem 1 differently. Let Ro be the set of rational numbers (2m+ 1)/2" contained in the open interval (0,1). Y
n
2-ck,where
Every number r E Ro can be represented in the form k-1
377
7. SIEVES
n > 0 and 0 < c1 < c2 ... < c, . Associating the number r with the sequence e(r) = ( ~ ~ - 1c2-cl-1, , ..., C , - - C , - ~ - ~ ) we obtain a oneto-one mapping of Ro onto d such that rl > r2 =e(rl) -$ e(r2).# THEOREM 2 : I f g , e N N ,then ?In
> yl(n+l)
f o r n>O.
PROOF.The sequence cpln is a proper segment of the sequence ?In+ 1. THEOREM 3 : Let e(")E Nkn for n E N and k, > 0. Assume that e(") + e("+') for n E N . Then there exists an increasing sequence of natural numbers p , such that k , >, n+ 1 and such that the sequence e(P,)/(n+ 1) is a proper initial segment of the sequence e(Pn+l)/(n+2)for every n E N . PROOF.If e?) S1e("+'), then e$?, > ep+'); on the other hand, if e(")F2e("+'), then e p ) = e$"+').Thus the sequence e$') is non-increasing. Because there exists no infinite decreasing sequence of natural numbers, it follows that, from a value of n on all the terms e p ) are equal. Let po be the first number such that e p ) = e$'O)
for
n >po.
Then kpo>, 1 and e(")/l= e@o)ll for n > p o . Assume that s > 0 and that the numbers p j for j conditions PO < P I
n >pj
-+
< ...
(kn >,j+1)
A
< s satisfy the
k , >,j+L
(e(n'I(j+l) = e"j'l(j+l)).
We consider now the sequence of numbers el") for n >,P,-~. Since e(")ls= e(ps-l)Is, it follows that for n >ps-l the sequence e(") has length >, s and that the equations e:") = ejn+') hold for all j < s. If e(Ps-l) F2e(@,then the sequence e(") has at least s f l terms. If e(PS-')
F1e(") then there exists h < min(kPs-l, k,) such that e p - ' )
>
>
> ep). Thus h s and again k , s+ 1. It follows that all the sequences e(:) for n >,pS-' have length at least s+l and that the term e p ) is defined. the numbers el") form a non-increasing sequence. Thus For n there exists a least number p s > pS-' such that e?) = eLPS)for all
378
X. ANALYTIC AND PROJECTIVE SETS
n >p,. It follows that
k, >, s+ 1
and
n > ps -+ (kn2 s+ 1 ) A (e(")l(s+ 1 ) = e"S)/(s+ 1 ) ) .
The sequence of numbers pn defined in this way by induction satisfies the assertion of Theorem 3. COROLLARY 4: r f the hypotheses of Theorem 3 are satisfied, then there exists an infinite sequence q~ E N Nsuch that for some infinite increasing sequence of natural numbers p n pln = e("n)I(n+l)
for
nEN.
PROOF.We may take for q~ the sequence defined by the formula pn = e p ) , where p n is the nth term of the sequence defined in Theorem 3. We introduce the notion of sieve'). A function L ~ ( 2 ~ that ) ~ is, , a function with domain J such that L, is a subset of X for every e E d, is called a sieve. The sieve L is called open (closed, Borel, analytic, etc.) if for every e E J the set L, is open (closed, Borel, etc.). For any sieve L and for x EX we let IL(x) = {eE 6:X E I,,}.
Thus for every x the set IL(x) is a subset of 6. Denote by R ( L ) the set of x E X for which there exists an infinite sequence e(")of elements of I'(x) such that e(")> e("+')for n E N . Then x E R = {the set IL(x) is not well-ordered}. We say that the set R(L)is sifted through the sieve L. We can picture the function L as a subset of the plane, where J is the vertical axis, X the horizontal axis and L, as a horizontal segment with ordinate e. For el 3 e2 we can interpret e, as lying higher than el on the vertical axis. The set IL(x) then consists of those e that the vertical line through x intersects L,. The sifted set R(L) consists of points x such that the intersection of the vertical line through x and I) The notion of sieve is due to N. Lusin; see his paper, Sur les ensemblesanalytiques, Fundamenta Mathematicae 10 (1927) 1-95. In a particular case this notion was considered by Lebesgue in 1905. See H. Lebesgue, Sur les fonctions reprisentables analytiquement, Journal de Math., 1905, pp. 213-214.
3 79
7. SIEVES
the sets L, is not a well-ordered set (the intersection contains an infinite decreasing sequence). 'THEOREM5: The set sifted through an analytic sieve is analytic. PROOF.By definition, x e R ( L ) if and only if there exists an infinite sequence of elements of d such that e(")t e("+l)
Letting
vn= a(e(")) Fn # 07
and
x E Le(n) for all n E N .
we have 0'
(FnJ F be( P n + d
and
x E -b('pn)
for all n E N . Thus Clearly the set QL of those pairs (v, x ) for which P), # 0 is Borel. ( ~analytic. ~) The set QY of those pairs ( 9 1 , ~ ) for which X E L , C is In fact, (9, x> E
QL
E
'v v [ ( x E L , ) (vn A
q:N esJ
= ql A
( 4 4 =q)],
and thus
Q Y = U U [ ( ~ " X L e ) n ( { ~P ):n = q } X X ) n Z e q ] , qEN e c d
where Z,, = 0 or Z,, = N N X X depending on whether a(e) # q, or a(e) = q. Since the set N N x L, is analytic, it follows that the set Q; is analytic. Similarly one proves that the set Qr' which consists of those pairs (tp,x) for which uc(pn)> U~(P),,+~)is a Borel set. Thus x ER(L)= 'd [
n (Qh QYnQ3], n
and the set R(L) is therefore the projection of an analytic set and, as such, is itself analytic (see p. 355). THEOREM 6: Every analytic set can be obtained by applying the function R to a closed sieve. PROOF.Let M
=
u f-1 H,,,, where H is a regular defining system ~n
such that for every e E ~3 the set He is closed. For simplicity we may assume that H, = X .
X. ANALYTIC AND PROJECTIVE SETS
380
Let L , = He for e E d ; the function L is then a closed sieve, We shall show that M = R(L). First we suppose that x E M , i.e. that there exists a sequence 9 E N N such that x E (7 H,,, = L,,, . Then yln E IL(x) for all n > 0 and thus n
n n
the set IL(x) is not well-ordered, because for every n > 0, qln pl(n-t-1). Hence X E R ( L )and M c R(L). Next we suppose that x ER(L), i.e. that there exists a sequence of elements of d such that e(")E IL(x), x E Le(n)= H,(n) and e(")+ e("+') for all n E N . By Corollary 4, p. 378 there exists a sequence such that for some infinite sequence of natural numbers p n , we have e@n'[n= yln. From the regulariLy of H it follows that X E HJP,,)c HJP,,)~, = HPIn and thus X E H q I n .Q.E.D.
un (
~
n
Theorem 6 does not imply that there is a one-to-one correspondence between analytic sets and closed sieves: in fact different sieves can determine the same sets. Let V be a segment of d such that = 11 and let f be an order-preserving map of d onto V . For any sieve L, let L: = L,,,,, if eEV, if e$V. L: = 0
v
It follows from definition that (e E v) -+ [(e E 1,. ( X I )
= ( f WE I d x ) ) ] . Thus for arbitrary e E d we have f(e) E ILL.(")= e E ZL(x); that is, IL,(x) Clearly the sets IL(x) and I&) are similar, thus R(L) R(L') although the sieves L and L' are in general distinct. Now let ZI be an element of d greater than all'the elements of V and let L" differ from L' only in that L:' = X . Clearly ILt,(x)= IL,(x)u { v } , and thus R(L") = R(L'). We have proved the following theorem:
=f'(I,(x)). ==
7 : For every analytic set M there exists a closed sieve L THEOREM such that M = R(L) and such that the set IL(x), for every x , has a largest element. Similarly, replacing w by a sequence of type w all of whose terms are greater than those of V we obtain the following
7. SIEVES
381
THEOREM 8: Fof every analytic set M there exists a closed sieve such that M = R ( L ) and for no X E X the set IL(x) has a largest element.
5 8.
Constituents
We shall use sieves to analyze sets of the class C l , that is, sets which are complements of analytic sets. ! we let For a given sieve L and a given ordinal a < 2
CJL) = ( x : IL(x)= a}. We call this set the u-th constituent determined by the sieve L. THEOREM 1: X-R(L)
=
u C,(L).
a
For X E X - R ( L ) if and only if there exists an ordinal M which is the order type of the set IL(x);it follows that a < Q and thus XEC,(L). We shall show that under certain assumptions all constituents are Borel sets. For this purpose we need several auxiliary theorems. For arbitrary sieves L and L’, let T
= T ( L ,L’) =
{ ( x ,x’): the set IL(x)is similar to a part of IL.(x’)},
T* = T*(L,L’) = { ( x ,x‘): there is an e in I,, (x’) such that I&) is similar to a part of the segment O[e) of IL,(x’)}.
LEMMA 2: If the sieves L and L’ are Borel, then the sets T and T* are analytic. PROOF.The condition (1)
( x , x’) E T
is equivalent to the existence of a one-to-one order preserving function which maps the set IL(x) into IL.(x‘). Because the sets IL(x)and I,,[x’) are countable, we may restate the condition above in the following form: there exist two infinite sequences e(O),e(l),...,
f(O),f(l),...
of elements of d such that IL(x) is the set of terms of the first sequence, ZLt(x’)contains the set of terms of the second sequence and
382
X. ANALYTIC A N D PROJECTNE SETS
where A m , = { ( y , W ,X ,
XI):
vm
B m n = ((9,P, X , x'):
= n},
ym
= n}
and Z,,,, = 0
or
Zpq,,= N N xN N xX X X
depending on whether the sentence
(."(P)
3
= ( o C ( q ) .uC(s)) i
is false or true. Since the sets A,,, Bmn and ZPqrSare Borel, it follows that H5 is also Borel. The sets H3 and H4are Borel. We shall prove only that H3 is Borel, because the proof for H4 is similar. From the definition of the set IL( x ) we have (rp, y , XY x'> E H3
=A n
v{ q
(rpn
= 4)A ( x E LoC(q)) A C(X
@ J%(*))
"v P
(rpp
= 41
1
383
8. CONSTITUENTS
thus
and it follows that H3 is Borel since the class of Borel sets is closed with respect to the operations of union, intersection, complementation (see pp. 363-364) and Cartesian product. Condition (1) is thus equivalent to
v [(cp, PV
p, x , XI> E H2 n H3 n H4 n &I,
and thus the set T is the projection of a Borel set and as such is analytic. The proof that T* is analytic is similar except that we replace condition (4) by
The set H: of quadruples satisfying this condition is Borel. Since T* is a projection of the set H2n H3 n H: n H,, it is analytic. O THEOREM 3 : If L is a Borel sieve, then every constituent C,(L) belongs to the class PI n C,; that is, every constituent is analytic and has analytic complement.
PROOF.We may assume that the constituent C,(L) = C, is non-empty. Let x,EC, and let T = T ( L , L ) . Clearly, . (XEC,) ~((X,XO)fT)h(<XO,X)ET). Conversely, suppose that <x, xo)E T and (xo,x} E T. The first condition implies that the set IL(x) is similar to a subset of IL(xo). This set is of type a, thus Zr,(x) is well-ordered and its type is a. Similarly, the second condition implies that the type of ZL(x) is >a. Thus the type of I L ( x )is exactly a. In this way we have shown that
<
Ca = {X: ((X,xo)ET) A ((Xo, x > E T ) } ,
which proves that the constituent C, is analytic. The complement of C, consists of those x which satisfy one of the
384
X. ANALYTIC AND PROJECTIVE SETS
following conditions: the set IL(x) is not well-ordered; the set ZL(x) is well-ordered and its type is < a; the set I,(x) is well-ordered and its type is > a. The set of x satisfying the first condition is analytic because it is equal to R(L). The set OF x satisfying the second condition is equal to the set { x : ( x , x0) ET*},and the set of x satisfying the third condition is equal to [X--R(L)] n { x : (xo,X) E T* } .Thus X--C, = R ( L ) u {x: (x, x J E T * } u {x:
x )ET * ),
(~0,
and the set X-C, is analytic. COROLLARY 4: Every constituent is Borel. PROOF.The Family Pl n C,is identical with the family Bo (see p. 356). O COROLLARY 5: Every set M E C , is the union of K1 Borel sets. For every such set is equal to X--R(L), where L is a Borel sieve. Thus M is the union of K1 constituents, all of which are Borel. O
Exercises 1. Deduce from Corollary 4 that every set belonging t o Pz is the union of analytic sets and thus the union of N, Borel sets. 2. Let H be a defining system such that the sets He are Borel. Let H:
= He,
and
H," =
H,"" = H , " n
I,
u H& k
nH f for limit ordinals 3,
b
(the expression e ; k denotes the sequence obtained from e by adding k as the last term). Prove that
x- U nHVln = U E', 9
n
where
E'=
a
U H," e-N
(union indexed by sequences of one term)'). [Sierpihski] ') This statement shows that it is possible t o decompose an analytic complement into the union of X, Borel sets without using the notion of sieve. See W. Sierpihski, Sur une propriktk des ensembles (A), Fundamenta Mathematicae 8 (1926) 362.
3 85
9. UNIVERSAL SIEVE AND THE FUNCTION I
$9. Universal sieve and the function t With each point of the set
v
of the space N N we associate the order type t (v)
. {ac(vo),uc(vJ, *.*,aC(vn), --.l.-{O) ordered by the relation
c
J
5.
By Theorem 1, p. 375 and by the universality of the type q (p. 219), for every countable order type z there exists a such that t(p))= z. For if z is the order type of a non-empty set E c J and if eo,el ... is an infinite sequence (possibly with repetitions) whose terms constitute the set E, then it suffices to take for 9 the sequence 97, = a(e,). If E = 0, then it suffices to take for cp the sequence all of whose terms are 0. By Q we shall denote the set of all q~ for which t ( q ) is an ordinal number.
THEOREM 1: The set NN- Q is analytic; there exists a Bore1 sieve U (all of whose values are Fb-sets) such that N N - Q = R(U) and such that for every a < Q the constituent C,(U) consists of those q~ for which t ( v ) = a. PROOF.For e in d let U,= {v: // (aC(qn)= e)}. The set U, belongs n
to the class F,, because ~1 E ue
V
[(vn
= 4) A (4 #
0)A ( U c ( q )
= e)],
nq
and the set {v: v, = q} = A,, is closed. The set I u ( y ) consists of all non-empty sequences of the form ac(qn) and thus I,@) = t(v), which proves the theorem. We call the sieve U universal; this name is justified by the fact that among the sets I u ( v ) occur ordered sets of all possible countable order types. In particular, the constituents C,CU) are non-empty for all a < Q'). Using the set Q and the constituents C,(U)we can introduce a ge~
l) Neglecting non-essential differences, the set Q and the sieve U were defined already by Lebesgue. See his paper cited on p. 378.
386
X. ANALYTIC A N D PROJECFIVB SETS
ometrization of the cardinal numbers < 9 '). This geometrization relies upon the fact that every relation R ( q Byy, ...) among ordinal numbers < 9 can be replaced by a relation R' among elements of N N which holds for the points y , y , 8 , ... exactly when R ( t ( v ) , t ( y ) ,...). We shall not examine the details of this geometrization here and shall only define two operations which we shall use later in 0 11. For y E N N and q EN- (0)we denote by e ( y , q) the sequence defined by the following formulas: v n if oc(vn)-3 oC(q)or y n = 0, ~n = 0 if ac(yn>> oc(q); in addition we let E(Q),O)= v.
{
THEOREM 2: For every 91 E N N and q E N - { 0 } the set lv(e(yyq)) consists of those elements of the set Iv(y) which are + o"(q); moreover, for every 4 the set {(q, y>: y = ~ ( yq)} , is Borel. The first part of the theorem follows from the fact that I J v ) consists of all finite non-empty sequences of the form bC(yn)and that I U ( 4 y , q ) )consists of those UC(Q)n) which are jdo(@. The second part of the theorem follows from the formula
[Y
E(QI,
A (<(yn =
4)1
vn) A
[(qn = 0)v ( ~ c ( ~ n3 ) oC(q))])
v [ ( n = 0) A (0"(4) 5 8(qn))])
An V ((91. p
= P) A
({(Yn
= P> A
[(P ==0)v ( ~ Y P 3 ) OC(q))l>
v [(vn = 0)A (uc(q) F~o(P))J)).
THEOREM 3 : If q # 0, then the set { y : oo(q) is the last element of the set l u ( y ) } is Borel.
PROOF.This set is equal to (91 : V n
A { ( v n = 4 ) A [ ( v m = 0)v (aC(ym) 5aa(q))])1* m
I) This msthod of investigation of ordinal numbem is due to K. Kuratowski. Detailed information on geometrization of ordinal numbers can be found in his Topology, pp. 503-508.
9. UNIVERSAL SIEVE AND THE FUNCTION
t
387
We prove now two important theorems about C,-sets. The first of them (Theorem 4) will show that in a certain sense the set Q is universal. The second (Theorem 7) will give necessary and sufficient conditions for a set to be Borel. THEOREM 4: For every set M c X belonging to the class C, there exists a function f E: ( N N ) Xwhose graph { ( x , y ) : g~ =f ( x ) } is Borel and such that M =f - ' ( Q ) . In other words, every set of the class Cl is the Borel inverse image of the set Q. PROOF.Let eo, e l , ... be a sequence such that d is the set of ist terms. Assume that X - M = R ( L ) where L is a closed sieve and let f ( x ) be the sequence y defined by the formula =
Q I ~
{
0 a(e,)
if if
en $ ZL ( x ) (i.e. x $ Len), enEIL(x)(i.e. xELen).
The graph off is Borel, because
1
A { [ ( x L,JA (Vn = 011v [ ( x ~ ~ e ,A, )(yn = en))] ( f ( x )= and the sets Lenare Borel by assumption. Let x EX and let y =f ( x ) . By definition it follows that Iu ( y ) = ZL(x), and hence t ( y ) = IL(x).Thus t ( y ) is an ordinal number if and only if the set IL(x) is well-ordered. Hence @ E M )E ( x . X - R ( L ) )
e {t(p')is an ordinal number}
= ( y e Q>= ( f ( 4E Q), which implies that M = f - ' ( Q ) .
COROLLARY 5 : The set Q is not Borel I). PROOF.Let M EC, be a non-Bore1 set in the space N N (see p. 373). By Theorem 4, M =f - ' ( Q ) and thus
l) This is a theorem of Lusin and Sierpihki; see their paper: Sur un ensemble non mesurable (B), Journal de Mathdmatique, 1923, p. 68.
388
X. ANALYTIC AND PROJECTIVE SETS
If Q were Borel, then the formulas above would imply that M belongs to the class PI n C,,and would be Borel since in the space NN the intersection PIn C,coincides with the class of all Borel sets (P. 356). O COROLLARY 6: The notion of well-ordering for subsets of N is not definable in terms of the operations of the propositional calculus and quanti3cation limited to elements of N * ) ,
PROOF.Assume that {R is a well-ordering relation for a subset of N ) = @(R), where @ is a propositional function constructed from expressions of the form x R y , x= y , by means o f the operations of the propositional calculus and quantification over elements of N. For Q~E", let
R, = (<m, n> : (vm z 0)A (pin # 0)A (uWn) 4 .C<~m))}. The set {pl: mR,n} is Borel. It follows that, for every propositional function @ of the kind under consideration, the set {q: @(I?,)) is Borel. Thus the set (q: R, is a well-ordering} s Borel, which is impossible since
(R, is a well-ordering} = (the-set IU(q)is well ordered) EVPQ.
'THEOREM7: Let M be an arbitrary subset of the space X. The following three conditions are equivalent: (i) M EPIand for every Borel sieve L, M = R(L) implies that there exists a, < l2 such that all constituents C,(L)for u > a, are empty. (ii) There exist a Borel sieve L and and C,(L)= 0 for u > c10.
go
< 52 such that M = RCW
(iii) M EPIn C,. I) This is a theorem of A. Tarski, Grundzige des Systemenkalkiirs Il, Fundamenta Mathematicae 26 (1936) 301. The proof given here is due to K. Kuratowski, Les rypes d'ordres &$nissables et les ensembles boreliens, Fundamenta Mathematicae 29 (1937) 97-100.
9. UNIVERSAL SIEVE AND THE FUNCTION
t
389
PROOF.(i) --t (6). M EP1 implies that M = R(L) for some Borel sieve L. By (i) for every such L there exists a. < 9 such that all constituents with indices > a. are empty. (ii) * (iii). By (ii), X - M =
u C,(L) u C,(L). Every constit=
UCR
u
uent Ca(L)is Borel and thus the union of countably many C,(L)is also Borel. Thus the sets X--M and M belong to the class P, n Cl . (iii) + (i). Let M belong to P1n C, and let L be a Borel sieve such that M = R(L). Assume that there exist non-empty constituents C,(L) for arbitrarily large countable a. Let T = T ( U , L); we shall show that
For if x $ M and (pyx) E T ,then the set &(p) is similar to a subset of ZL(x) and thus is similar to a subset of a well-ordered set. Thus Iu(pl) is well ordered, that is, p E Q. Conversely, if ~ E and Q Iu(pl) = a, then by assumption - there exists an x which does not belong to M such that I,,@) > a, and thus x> E T . Formula-(l) has been proved. Since the complement of M is analytic and since the set T is also analytic (see Lemma 2, p. 381), it follows by (1) that Q is also analytic. Since Q E C ~we , have that Q E Pln Cl , which implies that Q is Borel. Thus the assumption that there exist non-empty constituents Ca(L) for a arbitrarily large leads to a contradiction. ( 9 9
O COROLLARY 8 I): A set M c X is Borel if and only if it satisfies one of the conditions (i), (ii) or (iii) of Theorem 7.
Exercises 1. Let M be Borel and a. an ordinal < 8.Construct a sieve L such that R(L) = M and C,,(L) # 0. 2. Prove chat if L is a Borel sieve in NN and E is an analytic set contained in l) This corollary is due to N. Lusin. See his paper Sur les ensembles anabtiques. Fundarnenta Mathematicae 10 (1927) 71.
390
X. ANALYTIC AND PROJECTIVE SETS
X--R(L), then there exists an ordinal a0 < sd such that E c
u
C&).
[Lusin]
=
Hint: Use an argument similar to that used in the proof of Corollary 8. 3. Prove that if L is aBorel sieve, then the sets ( x : IL(x) = 7)and ( x : ZL(X) = w*> are Borel l).
5 10. The reduction theorem and the second separation theorem Let K be an arbitrary family of sets. We say that K has the reduction property if for arbitrary hil and M2 belonging to K the union Ml u M , can be represented as the disjoint union Z1u 2, of two sets Z1 and 2, belonging to K and contained in Ml and Mz respectively: (1) Z l u Z , = M l u M z ,
ZlnZ,=O,
Z i c M i for i = 1 , 2 .
O THEOREM 1: The family Cl = Cl(NN)of complements of analytic sets has the reduction property ').
PROOF.Let X - M i = R(Li), i = 1,2, where the Borel sieves L1,Lz are chosen in such a way that for every XEXthe set I&) has a last has a last element element and such that for no X E Xthe set I&) [see p. 380-381). Let 2, = { x : <x, x> $ T(Lz,Li)} n MI9 2 2
= { x : (x, x> $ T ( d ,Lz)} n Mz-
The sets Zi belong to the class Cl (see Lemma 2, p. 381), and Zi c Mi for i = 1,2. Moreover, x E Z= ~ (x E Ml) A [the set IL2(x)is not similar to any part of Z"l(x)],
x E Z2= ( x E M,)
A
[the set IL1(x)is not similar to any part of I&)].
Clearly, the sets Z1 and Z, are disjoint. For XEZ,nZ, implies l ) See S . Hartman. Zur Geometrisierung der abzahlbaren Ordnungstypen, Fundamenta Mathematicae 29 (1937) 209-214. D. Scott has proved that for every order type T the set { x : Irr(x) = T > is Borel. See his paper Invariant Borel sets. Fund. Math. 56 (1964) 117-128. See also C. Ryll-Nardzewski, On Borel measurability of orbits, ibidem, 129-130. ,) See K. Kuratowski, Sur les thiorhes de se'paration duns la thiorie des ensembles, Fundamenta Mathernaticae 26 (1 936) 183-1 91.
391
10. THE REDUCITON THEOREM
that both of the sets ZLI(x) and I&) are well ordered and none is similar to any part of the other, which is a contradiction (see p. 231). It remains to be shown that Ml u Mz c Z1u 2,. Assume that x E M1 -Z1, then I&) is well ordered and IL,(x) is similar to a part of the set ZLI(x). It follows that x e M z and that the set IL,(x) is not similar to any part of the set I&), since by assumption the types of the sets ILI(x)and I&) are distinct. Thus x e Z z and Ml-Zl c 2,. Similarly, Mz-Zz c Z1 and hence Mi c Z1u Z 2 for i = 1,2. Q.E.D. The reduction property is closely associated with the second separation principle. We say that the second separation principle holds for the family K if for arbitrary sets Hl and H, belonging to K there exist sets D1 and Dz such that
Hi- HZ c Dz, Hz- Hi c D1, and X - D i e K , i = 1,2. DlnDz=O
'COROLLARY 2: The second separation principle holds for the family P1I). PROOF.Applying the reduction theorem to the sets X- Hi we obtain sets Di belonging to Cl such that (X- H l ) u ( X - Hz) = D1 u Dz and Di c X - Hi for i = 1,2. It follows that Hi n Di
Hz-Hl
=0
for i = 1,2, and thus
= Hz n [ ( X - H I ) u (X-H,)] = Hz n (Dl u
Dz) = Hz n D1 c D1
and similarly Hl-Hz c Dz. It was shown by Novikov that if X = N N (or, more generally, if X is a compleie separable space), then the reduction property holds for the family Pz and the second separation principle holds for Cz2).It is likely that the reduction property and the second separation principle for other projective classes are independent from the axioms of set theory. On the other hand, it has been shown that the reduction propI)
See N. Lusin, Lecons sur les ensembles analytiques (Paris 1930), p. 210. P. Novikov, Sur la sdparabilitd des ensembles projectifs de seconde classe, Eun-
damenta Mathematicae 25(1935) 459-466.
X. ANALYTIC AND PROJECTIVE SETS
392
erty for the classes P. (n 2 2) and the second separation principle for the classes C, (n 2 2) are not contradictory with the axioms '1. Exercises 1. Show that if the reduction property holds for the family K , then the second separation principle holds for the family C(K)consisting of all complements of sets belonging to K. 2. We say that the first separation principle holds for the family K. if for arbitrary disjoint sets M, and M2belonging to K there is a set E E K n C ( K )such that M, c E and E n M2 = 0. Show that if the family K has the reduction property, then the iirst separation principle holds for C(K). 3. Using Exercise 2 above and Theorem 1, p. 390 prove Theorem 6, p. 355. 4. Neither the first nor the second separation principle holds for the family C, in the space NN. Hint: Let be a universal pair for the family C,, where the sets U and V are complements of analytic sets (see Exercise 3, p. 374). By virtue of reduction property there exist sets U,c U and V, c V such that U u V = U,u V,. If the sets U,and V,could be separated by a Borel set W,then the function F(q) = { y :
0 11. The problem of projectivity for sets defined by transfinite induction Let H be a function which assigns to every set M c (NN)k= X a set H ( M ) c X. By the theorem on inductive definitions, for every Z c X there exists a sequence of type Q of subsets of X such that
Do = Z , Let E =
DE+'= H(D,),
DA=
u De for L a limit ordinal.
€
u D,. The problem which we shall deal with in this section
edl
concerns the projectivity of the set E2). Applying the general idea of geometrization of ordinal numbers, we let D' {
I) J. W . Addison, Separation principles in the hierarchies of classical and effective descriptive set theory, Fundamenta Mathematicae 46(1959) 123-135. 2, This problem (in a more general setting) was solved by K. Kuratowski, Les ensembles projectifs et l'induction transfinie, Fundamenta Mathematicae 27 (1 936)
269-276.
11. THE PROBLEM OF PROJECTIWIY
Clearly x E E =
393
v [(v, x ) ED'];thus, in order to evaluate the projec(P
tive class of the set E, it suffices to consider the same problem for the set D'. We shall use the following notation. If A c NNx Y where Y is an arbitrary space, then A'" will denote the set {y: (v,y> E A } we call it the crossection of A through q~.We shall denote the projective classes P n ( N Nn ) ( N N ) kand Cn(NN)n (NN)kby Pn,k and Cn,k, or by Pa and C,, if k is fixed and if no confusion can occur. DEFINITION: A function HE"')'' is projective of class P, (or C,,) if for every set A EPn,k+Z (or A e C n , k + 2 ) the set {(F, y, x } : x EA(')(*)} belongs to the class Pn,k+z (or to the class Cn,k+Z). In the sequel we shall restrict our attention to functions of class P,,, but all arguments can be shown to hold for functions of class C,,.
LEMMA1: If H is a function of class P,, (n 2 l), then
( M cX)n ( M E P,,) + H(M)EP,,. PROOF.If M E P,, then the set A class Pn,k+Z, and thus the set
= N Nx
N Nx M belongs to the
B = { ( ~ , Y , X ) : XEH(A(")(~))} = { ( ~ , , w , x )X: E H ( M ) } belongs to the class Pn,k+P. It follows that H ( M ) is the projection of the set B: xEH(M)=
v [(FYy,x>"q;
I ,
thus, H(M)€Pn since n 2 1. LEMMA 2: lTfZePn,kand H i s aprojective function of class P,,( n > l), then D , E P , ,for ~ all E < 9.
PROOF.Let K = (5 < 9:DcE p,,} and let W(a)c K; by the induction principle it suffices to show that ~ E KThis . is clear for a = 0 because Do= 2 E P,,. If a is a limit ordinal, then 0, is the countable union of sets belonging to the class P,, and thus D,EP,, (see p. 373). Finally, if a = p+ 1 then Ds E P,, by hypothesis and thus D, = H(Dp)E P,, by Lemma 1.
394
X. ANALYTIC AND PROJECTIVE SETS
LEMMA3: Under the same hypotheses as in Lemma 2, the union U(Ct(U)x 0 6 ) belongs to the class P n , k + l . €
PROOF.Each constituent Ce(U) is Borel and the class P. is closed with respect to the operations of countable union and of Cartesian product. In the following lemma we use the notation Kq = (p): #(q) is the last element of the set Iu(p))}. The set Kq is Borel as was proved in Theorem 3 on p. 386. We shall use T to denote the set T(U, V ) (see p. 381). For p), W EQ the condition t ( y )< t (y) is equivalent to (9, y ) E T . LEMMA4: If Z E P , , H is a function of class P,,(n >, 1) and if x)ED', then there exists a set A c N" x X having the following proper ties: (p),
(1)
(2) (3)
~ E C , ( U+ ) A(V)= Z ; ( Y E Q ) A ( ( ~ , ~ ) ) E T ) A ( ~ E K ~ ) A ( ~ # O+ ) (A(V)=H(A(e(V*Q))));
(4)
(YE
Q ) A ( ( Y , p)) E T ) A // (Y, #Kq) + (A(v)= 4#0
u A(%
4)));
4#0
(5)
A € P n , k+l * Conversely, if there exists a set A satisfying (1)-(5) where p) E Q, then (9,x>ED'. PROOF.The first part of the lemma follows from the fact that the set
satisfies conditions (1)-(5). To prove the second part we assume that A satisfies (1)-(5) and that Y E Q.Let CI = t(p)).We shall show by induction on ,B that if ,B a, then t ( Y ) = p +A@') = D 8. (6)
<
Let Y be the set consisting of all countable ordinals > a and of ordinals 6 a which satisfy (6). Assume that W ( p ) c Y. It suffices to show that BEY. Clearly we may also assume that ,B < a. If ,B = 0
395
11. THE PROBLEM OF PROJECTNITY
then p satisfies (6), since t ( y j = 0 implies that peC0(V) and thus by (2), A(') = 2 = Do: = y f l < a , and thus (y,p} If = y + l and t ( y ) = p then-) E T , y E Q and there exists a q # 0 such that @(q) is the last element From (3) it then follows that A(') = of the set Zu(y), that is, H(A(8(V*@)), and because (seep. 386) t(a(y, q)) = y E Y, we have A(t(v.4)) = D, and A(V)= H(D,) = D,+l = DB. If 4, is a limit ordinal and tcy) = ,4, then I,(y) < a, thus p E Q and (y, p>E T; moreover, y #Kq for all natural numbers q # 0. From (4) it follows that A(v) = On the other hand, for every
u
qfO
q, t(E(y,q)) < i ( y ) = j3, and every ordinal y < p can be represented in the form t(E(y, q)) where q is a natural number # 0. Since i ( c ( y , q)) E Y, we have
Thus formula (6) holds. Substituting in (6) /I= t(q) and y = q, we obtain A ( @ = Dt(cp), and thus by (1)
Dt(p)
c
D'.
Q.E.D.
Now let F be a universal function for the class the set = {<6, x): x E F@)j
P,J,k+l such
that
w
belongs to class P , , k + 2 . The existence of such a function was proved on p. 372. Notice that W(4)= F(6) according to the definition. Every set A E P,,,k+l can be represented in the form F(6), that is in the form W(')and W(')E P,,,k+l for every 6. Hence substituting A = W(')in Lemma 4 we obtain the following statement: 5 : If Z E Pn,kand H is a function of class P,, , then ihe formula LEMMA ( y , x) ED' is equivalent to the exisience of a point 6 E N N such ihat for all y:
(7) (8)
((6,Q1, X> E w)A (v E Q); y € C o ( V )+ (W(Q(V)= 2);
The lemma above allows us to solve the problem of projectivity of the set D'. Namely, by Lemma 5 we have the equivalence
are the propositional functions (7)-(10). where Let Hi = {(q, x, 8 , y ) : Qi} for i = 1,2,3,4. Then (1 1)
(v, x> ED' =
v A [(q, x,@,y> *
LEMMA 6: If n
Y
E H l n H 2 n f4nH41.
,
1 then the sets Hi belong to class C,,+l,if3 for
i = 1,2,3,4.
PROOF. The set HI can be obtained from the set [ W x N N ]n [NNx x NNx Q xx] by permutation and identification of coordinates. Therefore H1 belongs to class Pn,k+3 since W E P , , ~ and + ~ QEC,,,c P.,,. Thus HZE cn+lk+3 , * The set H2 can be defined by the equivalence
(9% x, 8,Y>E H2
= {(y 4 CO(u)) v
A, [(Y E W(')('))= (Y E z>) Y
=A {(Y 4 co cv>> v [ K @ Y Y u>E w >A (u E a 1 Y 9
v
Y,Y> f# W )A 0,$311
v
= 1 {[YE CO(v)l A [(<.a, Y,Y>4 m v (Y 4211 Y
A
I((@,
y , Y> E
w v (YEZII}.
The propositional function Q written inside the brackets { } defines a set which is the intersection of a Bore1 set (the first component of 8 in square brackets [ I), a set of class Cn(the second component in [ I), and a set of class Pn (the third component in [ 3). Thus 0 belongs
397
1I . THE PROBLEM OF PROJEECITVITY
to class
Prefixingwith the existential quantifier
v the propositional Y
function 0 we do not change the projective class of the set defined by 0, since the class P,+lis closed with respect to projections. Thus the propositional function 1 0 determines a set of class C,,, .
v Y
The argument for the sets H3 and H4 is similar. We can define H3 equivalently by (12)
(VY x, 6,Y> E H3 z5
A {@,@,y) v A [(yEW(9)(lp))~(yEH(W(9)(s(lP.,’))]} Y AY 4+0 A { @,(qyY) [((o,yyJJ> E w)A ( Y E H(W‘”‘(e‘v’4))))]
qzo E
V
V
[(@,y,y)$ w)A (y 4 H(W(’)(8(V,q)’))]},
where 0, is the propositional function
1[(Y E Qj A ((Y, V) E T )* (Y EK,)]. Clearly 0, determines a set of class Pzsince Q belongs to C,, T is analytic, and K, is Borel. The propositional function (6, y,y ) E W defines a set of class P,, since WEP,,. On the other hand, the propositional function Y E H( W(s)(e(cp*q))) also defines a set of class Pn by the assumption that H is a function of class P,,. Thus the propositional function ((6,y,u) E w)A (y E H( W((s)@(lp’q))))
determines a set of class P,,. It can be shown similarly that the propositional function written in the last square brackets on the right-hand side of equivalence (12) determines a set of class C,,. It follows, similarly as for the set H,, that H3E Cn+,,k+3. The proof that H4E Ckfl, kf3 follows in an analogous manner from the equivalence
398
where
X. ANALYTIC AND PROJECTIVE SETS
O* is the propositional function
Q)A ((Y, V )
(Y $ Q* From formula (11) and Lemma 6 we obtain the desired result: (YJ
E
A
THEOREM1: If Z E P , , , and ~ H is a projective function of class p,, (n 2 11, then the sets D' and E are projective of class Pn+z.
PROOF.From (11) it follows that
v 1v ( ( ~ , x Y s , Y ) ~ H l n H , n H 3 n H 4 ) . The complement of the set H I nHz H3 H4 belongs to Pn+l.Application of the quantifier v corresponds to the operation of projection (y,x)EDr=
6
I
n
n
P
and thus yields a set of the same class, Pn+l; application of negation yields a propositional function which determines a set of class C,,+l and the projection corresponding to the application of the quantifier
v 6
gives a set of class Pn+2. From the above it follows by the equivalence x E B =
v ((v, x )
E D')
Q
that the theorem holds for the set E. It can be shown by an analogous argument that if Z E C , , , ~ and if H is a projective function of class C,, ( n 2 11, then the sets D' and E both belong to Pn+2. In general, deciding whether the function H is projective and evaluating its class presents no difficulty if the formula x E H ( M ) is defined by an equivalence of the form XEH(M)
= q x ,M ) ,
where @ is a propositional function whose bound variables range over the sets N and NN.For example, if all quantifiers occurring in Q, bind only variables which range over the set of natural numbers, then H is a Bore1 function.
LIST OF IMPORTANT SYMBOLS conjunction (logical product) of the sentenm p and q 1 disjunction (logical sum) of p and q 1 implication “if p then q” 2 equivalence of p and q 2 negation of the sentencep 2 “xisaset”5 “ x is an element of y” 5 “x is not an element of y” 5 “ x is the relational type of y” 5 sumofthesetsAand3 6 difference of the sets A and B 6 intersection of the sets A and 3 7 symmetric difference of A and 3 7,14 inclusion relation 7 empty set 9 “the sets A and B are congruent modulo the ideal I” 17 space (universe) 18 complement of the set A 18 closure of the set A 26,28 interior of the set A 28 boundary of the set A 31 derivative of the set A 32 sum of elements of a Boolean algebra 33 difference of elements of a Boolean algebra 33 symmetric difference of elements of a Boolean algebra 33 product of elements of a Boolean algebra 33 zero element of a Boolean algebra 33
LIST OF IMPORTANT SYMBOLS
value of the Boolean polynomialf 34 “Boolean polynomial f is immediately transformable into the polynomial g” 35 order relation in a Boolean algebra 37 unit of a Boolean algebra 37 pseudo-difference of elements of a Brouwerian lattice 43 pseudo-complement of an element of a Brouwerian lattice 43 universal quantifier 45, 46 existential quantifier 45, 46 class of propositional functions of general set theory 50 class of propositional functions of general set theory extended by the primitive terms P,Q,... 51 union of sets belonging to the family A 52 power set of the set A 52 the set of x which belong to A and for which @(x) 54 image of the set A obtained by the transformation @ 55 infinite system of axioms of set theory 55 system of axioms which does not contain the axiom of choice 55 unordered pair of the elements a and b 59 ordered pair of the elements a and b 59 intersection of sets belonging to the family A 61 Cartesian product of the sets X and Y 63 the set of real number 63 “a is in the relation R to b” or: “the relation R holds between a and b” 64 left domain of a relation 64
RC
right domain (range, counter-domain) of a relation 64 domain of the functionf 69 range of the functionf 69 field of the relation R 64 inverse of the relation R 65
40 1
LIST OF IMPORTANT SYMBOLS
R oS x/R C/R Yx
composition of the relations R and S 65 equivalence class containing the element x 68 quotient class of the set C with respect to the relation R 68 set of all mappings of X into Y 70 ‘Yrnaps X into Y” 70 value of the function f at x 70 restriction f of g for which &Cf) = A 72 function defined by the propositional function ... x
... 73
image of the set X under the relation R 74 set of values of the function f on the set X 74 inverse image of the set Y under the relation R 75 inverse image of the set Y under the function f 75 factor Boolean algebra 79
Vh reT
least upper bound of a set 82
/\A
greatest lower bound of a set 82
f€T
0 OA
]
1l A ) ( A , R,, R 1 , ... ,Rk-l> < A ,R )
zero element of an ordered set 82 unit element of an ordered set 83 relational system of characteristic b0, p l , ...,pk-]) 84 relational system of characteristic (2) 84 isomorphism of the relational systems (A, R ) and ( B , S) 84
successor of the set X 88 nth iteration of the function a 93 “the set X has n elements” 100 complete graph with the field X 107 union of the sets Ft belonging to the family W being the range of F 1 11 intersection of the sets belonging to the family W being the range of F 111 limit superior of the sequence Fo, 4 , ... 121
402
LIST OF IMPORTANT SYMBOLS
Lim inf F,, n=m
Lim F,, n=
m
Rs Rd
R.3
limit inferior of the sequence Fa, F,,
... 121
limit of the sequence Fa, Fl , ... 122 least family of sets containing the family R and closed under the union of sets 127 least family containing the family R and closed under the intersection of sets 127 family of sets of the form
u Ha, where W ERN 129
family of sets of the form
nn W,,where H ERN
n
129
least u-additive and a-multiplicative family containing R 129 Cartesian product of sets 131 Cartesian power of the set Y 132 Cantor set 137 the generalized Cantor set 137 equivalence relation modulo the ideal I142 inverse limit of the inverse system U = (X,T,F, f) 147
cut in an ordered set 159 order relation between cuts 159 family of all cuts of an ordered set 159 “the set A is equipollent to the set B” 169 cardinal number or power of the set A 174 cardinal number of infinite countable sets 174 “the sets X and Yare equivalent by finite decomposition” 191 power of the continuum 193 order type of the relational system 206 the element x precedes y under the relation R 209 initial segment defined by the element x under the ordering relation R 209
403
LIST OF IMPORTANT SYMBOLS
order types of sets
I ;:: 217
inverse of the order type a 222 limit of the Rsequence ~ ( y for ) y
Lim {CJ} &
< t 235
“the propositional function @ defines an operation” 238 “the operation defined by the propositional function @ is increasing” 238 limit of the operation defined by the propositional function @ 238 “the operation defined by the propositional function @ is continuous” 238 “there exists exactly one y” 238 “the least ordinal number p which satisfies the condition ... p ...” 238 “ I is the inductive sequence for @ of type a + 1” 244 formalization of a definition by means of transfinite induction 244 family of sets of rank at most a 246 ath power of the ordinal number n 246 natural sum of the ordinal numbers a and p 260 natural product of the ordinal numbers a and p 260 ordinal number in the sense of von Neumann 269 cardinal number of the ordinal E 274 smallest uncountable ordinal number 274 power (cardinal number) of the ordinal number B 274 Hartog’s aleph function 278 initial ordinals of the powers a and Nt 279 set of all initial ordinals w < 91 280 index of the initial ordinal 280 initial ordinal whose index is equal to a 281 the least number E such that the limit ordinal with wc 282
a
is cofinal
power of an initial number whose index is equal to
a
282
tth term of the exponential hierarchy of cardinals 297
404
LIST OF IMPORTANT SYMBOLS
N, is strongly inaccessible 326
sequence whose first term is m and whose following terms are the terms of the sequence e 341 sequence of (n+m) terms whose first n terms coincide with the terms of the sequence e, and whose last m terms coincide with those o f f in their original order 342 family of A-sets with respect to the family R 344 family of analytic subsets of a topological space 351 free union of the sets X and Y 357 free intersection of the sets X and Y 357 the set which arises from the set X by permutation of coordinates 357 the set which arises from the set X by identification of the ith andjth coordinates 358 projection of the set X onto the set Sr 358 family of all projections of sets belonging to the family L 359 family of complements of sets belonging to the family L 359 set of all non-empty finite sequences of natural numbers 375 sieve 373 ath constituent determined by the sieve L 381
AUTHOR INDEX Addison, J. W. 392 Bachmann, H. 289, 331 Baire, R. 242,333 Banach, S. 188, 190, 315 Bar-Hillel, Y. 58 Bendixson, I. 277 Bernays, P. 57, 58, 89 Bernstein, F. 190, 191, 192,267,289 Birkhoff, G. 41,269 Bolzano,B. v, 169 BooIe, G. 10, 33 Bore], E. vi, 53, 130, 190, 241 Bourbaki,N. 80 Brouwer, L. E. J. 42 Bruns, G. 160 Burali-Forti, C. 234 Cantor, G. v, vi, 61, 68, 86, 169, 173, 179, 182, 188, 190, 191, 192, 195, 206, 219, 228, 229, 231, 232, 239, 246, 274, 308, 328 Cauchy, A. 67, 130 Cohen, P. J. vi Davis, A. 224 Davis, R. L. 87 Dedekind, R. v, 103, 160,212 Dirichlet, L. 102, 104 Du Bois Reymond, P. v Ehrenfeucht, A. 325 Erdos, P. 110,215,338
Fichtenholz, G. 303 Fraenkel, A. A. vi, 53, 57, 58, 89, 262 Fralssk, R. 219 Frayne, T. 142 Frege, G. 61 Frolik, A. 352 Gillman, L. 338 Godel, K. vi, 58 Gratzer, G. 167 Hajnal, A. 215 Halmos, R. 33 Hame1,G. 267 Hanf,W. 320 Hardy, G. H. 182 Hartman, S. 390 Hartogs, F. 278,292 Hausdorff, F. 13, 18, 53, 287, 303, 310, 334, 338, 339, 348 Henkin,L. 156 Henriksen, M. 338 Hessenberg, G. 229,259,283 Hoborski, A. 252 Huntington, E. V. 41 Iseki, K. 32 Jacobstahl, E. 261 Jhnsson, B. 167,219 Kantorovitch, L. 303,348
406
AUTHOR INDEX
Keisler, J. H. 320, 323, 325, 326 Kleene, S. C. 365 Kochen, S. 338, 339 Kolmogorov, A. N. 131,348 Konig, D. 104,107 Konig, J. 190, 203
Lebesgue, H. 53,340,378,385 LeSniewski, S. 297 Levi,B. 186 Levy, A. 187,326-328 Lindenbaum, A. 186,191,279,297,334 Livenson, B. 348 Lusin, N. 333, 335, 357, 374, 378, 389-391
LoS, J. 142, 325, 326
Mahlo, P. 314 Marczewski, E. 22, 122, 126 Mc Kinsey, J. C. C. 26,42,44 Mc Naughton, R. 58 Mc Neille, H. M. 160 Mirimanov, D. 57 Monk,D. 326 Morel, A. C. 142 de Morgan, A. 4, 12,47,113,152 Morley, M. 219 Mycielski, J. 325
Rado, R. 110 Ramsey, F. P. 107, 109, 110 Rubin, H. 269, 295 Rubin, J. 269,295 Russell, B. 61, 133, 246 Ryll-Nardzewski, C. 390 Schonflies, A. 215 Schroder, E. 190 Scott, D. 142,326, 390 Sierpidski, W. 53, 131, 187, 198, 224, 252,269,287, 313, 334, 338, 340, 346, 356, 357, 384,387 Sikorski, R. 33, 156, 287 Skolem, Th. 26, 57, 110 Specker, E. 295,296, 333, 334 Stone, A. H. 31 Stone, M. H. 13, 167 Suslin, M. 340, 356, Tarski, A. vi, 26, 42, 44, 115, 129, 153, 155, 167, 186, 188, 191, 193, 288, 293, 295, 297, 303, 311, 313, 319, 320, 323, 325, 326, 334, 357, 388 Teichmiiller, 0. 269 Tennenbaum, S. 220 Tychonoff, A. N. 135 Ulam, S. 318,319 Urysohn, P. 367
Oczan, Yu. S. 348
de la Vallk Poussin, Ch. 122 Vaught, R. L. 219,269 Vitali, G. 69 Wang, H. 58 Whitehead, A. N. 133,246 Wiener, N. 59
Peano, G. 69,89
Zermelo, E. v, vi, 56, 57, 186, 261, 311 Zorn, M. 263
von Neumann, J. 57,269 Nikodym, 0. 367 Novikov, P. 391
SUBJECT INDEX abscissa of a point 63 absorption of a cardinal number by another cardinal number 193 abstract measure theory 315 accumulation point 28, 32 additivity of the operation of forming images and inverse images 117 alephs 282 a-sequence 235,237 algebra, atomic Boolean 152 Boolean 33 Brouwerian 42 factor Boolean 79 algebras, cylindrical 156 analytic set 351 analytically representable function of class a 242 antecedent of an implication 1 anti-lexicographical ordering 226 antinomies 4, 61 antinomy of Russell 61 arithmetically definable set 365 A-sets 344 associative law 171 associative law for the addition of cardinal numbers 183 for the multiplication of cardinal numbers 184 for the product of cardinal numbers 202 associative laws for operations on sets 10
atom of Boolean algebra 152 atomic Boolean algebra 152 atomic formulas of the class R? 51 axiom, multiplicative 133 axiom of choice 53 of difference 6 of existence 6 of extensionality 5, 51 of infinity 52 of pairs 52 of power set 52 of regularity 56 of relational systems 86 of replacement for a propositional function 54 of subsets for a propositional function 54 of Tarski 326 of the empty set 51 of unions 6, 52 axioms of Boolean algebra 33 of lattice theory 41 axiom system of set theory of Godel-Bernays 58 of von Neumann 57 of Zermelo 57 of Zermelo-Fraenkel 57 Bake space 137 base, 359 closed, of a topological space 119 Hamel 268
open, of a topological space 120
408
SUBJECT INDEX
base for an ideal 307 of a Hausdorff operation 348 Bernstein formula 289 binary operation 64 Boolean algebra (ring), 33, 134 atomic 152 distributive 152 factor 79 Boolean polynomial 34 Boolean ring (algebra) 33, 134 Bore1 sets of type a 241 boundary of a set 31 boundary set 32 branch, 104 infinite 104 branch of length n 104 Brouwerian algebra 42 Brouwerian lattice 42 cancellation laws 187 canonical mapping 79 Cantor-Bernstein (Schroder-Bernstein) theorem 190 Cantor set 137 cardinal number 174 cardinal C 193 cardinal, hyper-inaccessible 314, 315 inaccessible 314 measurable 315 strongly inaccessible 311 weakly inaccessible 310 Cartesian power of a set 132 Cartesian product of sets 62, 131 of relations 133 of spaces 138 of operations 133 Cauchysequence 67 characteristic function of a set 122 characteristic of a relational system 84
choice function 74 class of projective sets with respect to a base 359 closed base of a topological space 119 closed ordered set 262 closed set 27, 119 closed subbase of a topological space 120 closure 26, 135 cofinal ordinals 235 cofinal sets 81 coinitial sets 81 commutative diagram 72 commutative law 171 for the addition of cardinal numbers 183 for the product of cardinal numbers 202 commutative laws for operations on sets 10 commutative ring 16 compact topological space 139 complement ofagraph 107 of an element of a Boolean algebra 37 of a set 18 complete graph 107 complete lattice 83 complete ordering 83 components of a conjunction 1 composition of relations 65 conjunction 1 consequent of an implication 1 constituent 20 constituent determined by a sieve 381 continuous a-sequence 237 continuous function 77, 125 continuous set 212 continuously ordered set 212 continuum hypothesis, 328 generalized 328 convergent sequence 122
SUBJECT I W E X
coordinate axes (as subsets of product) 63 coset of a function 75, 186 countable (denumerable) set 174 cover of a set 81 critical ordinal of an a-sequence 237 cross-section of a set 393 cut 159 cylindrical algebras 156 Dedekind infinite set 103 defining system 340 definition by induction 92 dense in itself set 32 densely ordered set 210,211 denumerable (countable set) 174 derivative of a set 32 derivatives of order a 241 descriptive set-theory 340 difference of elements of Boolean algebra 33 of ordinals 248 of sets 6 digits of an expansion of ordinal numbers 256 direct predecessor of an elements 209 direct product of Boolean algebras 134 of sets (functions, relations) reduced modulo an ideal 143 direct successor of an element 209 directed set 81 Dirichlet’s drawer principle 102 Dirichlet’s principle for infinite set 104 discrete topology 137 disjoint sets 9 disjunction 1 distributive Boolean algebra 152 distributive lattice 41 distributive laws for operations on sets 10 distributive law for the product of cardinal numbers 202
409
domain of a function 69 of a relation 64 drawer principle of Dirichlet 102 element, extendable, of a set 188 maximal (minimal), of ordered set 82 unit, of ordered set 83 zero, of ordered set 82 element lying in the cut of a set 212 of a set 5 effective proof 47 elementary propositional function 145 elementary set 365 embedding preserving suprema (infima) 158 empty set 9 epsilon-ordinal 254 equipollence 169 equivalence of sentences 2 equivalence classes of a relation 68 equivalence relation 66 qE-set 335 Euclidean algorithm for ordinal numbers 250 even ordinals 242 existential quantifier 46 expansion of an ordinal number for the base, 256 exponents of 256 exponentiation of alephs 287 exponential hierarchy of cardinal numbers 297 extendable element of a set 188 extension of an element 188 of a function 72 of a relational system 157 factor Boolean algebra 79
410
S
family of sets of rank at most a 246 family of sets, 51 closed under a function 126 independent 304 inductive 268 monotone 81 a-additive 128 a-multiplicative 128 field ofsets 34 of agraph 107 of a relation 64 of a relational system 84 filter 162 finalsegment 209 finite inteisection property 139 finite sequence 91 finite set 100 first distributive law 3 first element of linearly ordered set 207 first monotonic law for addition 247 for ordinal multiplication 248 first separation principle 392 firstseparation theorem 355 first term of an ordered pair 59 free intersection 357 freeunion 357 function 69 function, analytically representable, of class a 242 characteristic, of a set 122 choice 74 continuous 77,125 domain of 69 elementary propositional 145 extensionof 72 Hartogs’ aleph 278 increasing 230 monotone, of subsets 19i non-trivial 317
m INDEX
function, nth iteration of 93 one-to-one 70 open propositional 141 projective 393 propositional 45 propositional, projective with respect t o a base 362 propositional, of class n with respect to abase 362 propositional, with domain limited to aset 45 propositional, of general set theory extended by primitive terms 51 universal 367 function consistent with a relation 78 defined on a set 70 defined almost everywhere 317 induced by a relation 78 with the domain limited to a set 45 functions of two and more variables 48, 73
gap 212 generalized associative laws 114 generalized associative law (for cardinal numbers) 198 generalized Cantor set 137 generalized commutative laws 115 generalized commutative law (for cardinalnumbers) 198 generalized continuum hypothesis (H) 328 generalized distributive laws 115 generalized distributive law for multiplication with respect to addition 199 generalized Hausdorff formula 289 generalized logical conjunction and disjunction 46 geometrization of the theory of cardinal numbers 386
41 I
SUBJECT INDEX
Godel-Bemays axiom system of set theory 58 graph 107 of propositional function 362 greatest lower bound 82
Hamel basis 268 Hartogs’ aleph function 278 HausdorB operations 348 HausdoriT recursion formula 287 hereditary set 230 homeomorphism 78 hyper-inaccessible cardinals 314, 3 15 hypothesis (C) 329
ideal, 17 m-additive 317 prime 163 principal, generated by an element CI 163 ideal of a distributive lattice 163 identification of coordinates 358 image of a set 55 of a set under relation 74 immediate extension of a sequence 350 immediate transformability of polynomials 35 implication 1 inaccessible cardinal 3 14 inclusion relation 7 increasing function 230 independent sets 22, 267 index of an initial ordinal 280 induction, 89 transfinite 229 inductive definition 92 inductive family of sets 268 inductive set 89 inequalities between cardinal numbers 185
infimum of elements 150 infinite branch 104 infinite set 100 initial ordinal 279 281 initial ordinal initial segment 209 initial vertex of a branch 104 interior of a set 28 intersection of sets 7 of sets belonging to a family 61 interval 209 invariance under an isomorphism 84 inverse image of a set under relation 75 inverse limit of an inverse system 147 inverse of an order type 222 of a relation 65 inverse system 147 isolated point 178 isomorphic embedding of a relational system 157 isomorphic relational systems 84 w.1
Konig’s infinity lemma 104 Konig’s theorem 203 lattice, 41 complete 83 distributive 152 modular 43 lattice of sets generated by a family closed under operation 127 law, associative 171 associative, for the addition of cardinal numbers 183 associative, for the multiplication of cardinal numbers 184 associative, for the product of cardinal numbers 202 cancellation 187
412
SUBJECT INDEX
law, commutative 171 commutative, for addition of cardinal numbers 183 commutative, for multiplication of cardinal numbers 184 commutative, for the product of cardinal numbers 202 distributive for operations on sets 10 distributive for cardinal numbers 202 first distributive 3 first monotonic, for addition 247 first monotonic, for ordinal multiplication 248 generalized associative 114, 198 generalized commutative 115, 198 generalized distributive 11 5 generalized distributive, for multiplication with respect to addition 199 second monotonic, for addition 241 second monotonic, for ordinal multiplication 249 law of associativity of conjunction 3 of associativity of disjunction 3 of commutativity of conjunction 3 of commutativity of disjunction 3 of contradiction 4 of contraposition 4 of double complementation 18 of double negation 4 of excluded middle 4 of exponents for the Cartesian product 172 of hypothetical syllogism 4 of trichotomy 292 laws, associative, for operations on sets 10 commutative 10 distributive 10 logical (tautology) 2 monotonic, for ordinal subtraction 248 de Morgan’s 4, 12,47, 152
laws of absorption 3 of subtraction 11 of tautology 3 , l l least upper bound 82 left distributivity of ordinal multiplication with respect to ordinal subtraction 249 lexicographical ordering 224 left domain of a relation 64 Uvy’s scheme 327 limit of a sequence 122 of A-sequence 235 limit ordinal 235 limit inferior 121 limit superior 121 linear order relations 81 linear (total, complete, simple) ordering 206 linearly accessible point 366 logical conjunction, generalized 46 logical disjunction, generalized 46 logical law (tautology) 2 logical product 1 logical sum 1 lower section of a cut 159
m-additive ideal 317 Mahlo classification of inaccessible cardinals 314 maximal element o f a s e t 262 of aq ordered set 82 mapping (transformation) 70 maximum principle 262,269 m-compact topological space 323 mean-value theorem 191 measurable cardinal 315 method of transfinite induction 230 modular lattice 43 monotone family 81
SUBIII(=T
monotonic function on subsets 192 monotonic laws for ordinal subtraction 248 de Morgan’s laws 4, 12,47, 152 minimal element of an ordered set 82 minimal extension of an ordered set 160 multiplicative axiom 133 multiplicativity of the operation of forming inverse images 117
natural addition 259 natural interpretation of axioms 27 natural multiplication 259 natural numbers 88 natural product 260 natural sum 260 negation 2 neighborhood 135 von Neumann’s axiom system of set theory 57 von Neumann’s ordinals 262 non-trivial function 317 normal form of sets 20 normal sequence of universal functions 368 nowhere dense set 32 nth iteration of a function 93 nth projective class with respect to a base 359 numbers of the second class 274
odd ordinal 242 one-to-one function 70 one-to-one sequence with n terms 100 open base 120 open propositional function 141 openset 27 open (closed, Borel, analytic) sieve 378
INDEX
413
open subbase of a topological space 120 operation (A) 340 order relation 80 in Boolean algebra 37 in a lattice 41 order of a function 77 of a value of function 77 order type 206 vj 217 1 219 w 216 ordered pair 59 ordered union of linearly ordered sets 213 ordering, anti-lexicographical (by the principle of last differences) 226 lexicographical (by the principle of first differences) 224 ordinal exponentiation 252 ordinal number (ordinal) 232 ordinal, epsilon- 254 expansion of 256 exponent 253 even 242 initial 279 initial, ma 281 limit 235 odd 242 power of 253 regular initial 308 singular initial 308 ordinal number in the sense of von Neumann 269 ordinals, natural addition of 259 natural multiplication of 259 natural product of 260 natural sum of 260 quotient of 250 weakly inaccessible 309 ordinate of a point 63
414
SUBJECT INDEX
partial order relation 80 partition 81 pair, ordered 59 universal, for a family 374 unordered 59 partition of a set 67 permutation of a set 71 of coordinates 351 Peano axioms 89 perfect set 267 point, accumulation 32 isolated 178 linearly accessible 366 point of wtesian product 63 points of the space 26 polynomial immediately transformable into polynomial 35 power set 52 power ofaset 174 of an ordinal 253 of a cardinal number 184 of the continuum 193 prime ideal 144 prime ideal of a distributive lattice 163 principal ideal generated by a 163 principle, first separation 392 maximum 262,269 second separation 391 Zorn maximal 263 principle of duality 41 of induction for ordinals 275 of transfinite induction 229 principal ordinals of multiplication 261 problem of elimination 23 product, cartesian, see cartesian product direct, of Boolean algebras 134
product, direct, of groups, rings, etc. 134 logical, of sentences 1 natural 260 product of cardinal numbers 183,202 of order types 223 of ordinal numbers 246 projection of relation 64 projective classes 364 projective set 357 proof by induction 89 proof, effective 47 proper cut 212 proper extremum of a function 178 proper subset 8 property, finite intersection 139 reduction 390 property invariant under isomorphism 84 propositional functions 45 propositional function of two variables 48 with domain limited to set 45 projective with respect to a base 362 proto-order relation 80 projection 358 pseudo-complement 43 pseudo-difference 43 quantifiers 46 quasi-order relation 80 quotient class of sets with respect to a relation 68 quotient of ordinals 250 Ramsey’s theorem 107, 109 range of a relation 64 of a function 69 reduction property 390 refinement of a cover 81
SUBJECT INDEX
regular closed set 38 regular initial ordinal 308 regular system 341 relation 64 relation, binary 64 equivalence 66 inclusion 7 inverse 65 linear order 81 order 80 order, in a Boolean algebra 37 order, in a lattice 41 partial order 80 proto-order 80 quasi-order 80 transitive 8 relation of lying between, for elements of 209 of preceding, for elements of a set of preceding, for intervals of a set “less than”, for cardinal numbers relational system 84 relational system embedded into a tional system 157 relational type 5, 87 remainder of an ordinal number 250,259 o f a s e t 235 result of the operation (A) 341 right domain of a relation 64 ring 16 R-separable set 346 Russell’s antinomy 61
a set 209 210 185 rela-
scattered set 21 1 Schroder-Bernstein (Cantor-Bernstein) theorem 190 second distributive law 3 second monotonic law for addition 247
415
second monotonic law for ordinal multiplication 249 second separation principle 391 second term of an ordered pair 59 sequence, Cauchy 67 convergent 122 finite 91 immediate extension of 350 infinite 91 A- 135 normal, of universal functions 368 one-to-one, with n terms 100 transfinite, of type a (or: a-sequence) 235 a-sequence, 235 increasing 235 continuous 237 set, 4 A- 344 analytic 351 arithmetically definable 365 boundary 32 Cantor 137 closed 27, 119 closed ordered 262 continuous 212 continuously ordered 212 countable 174 Dedekind’infinite 103 dense in itself 32 densely ordered 210 densely ordered in linearly ordered set 21 1 directed 81 elementary 365 empty 9 rly- 335 finite 100 fmite, in the direction of the kth axis 286 generalized Cantor 137 hereditary 230
416
SUBJECT INDEX
set, infinite 100 independent 267 inductive 89 nowhere dense 32 open 27, 119 ordered 80 perfect 267 power 52 projective 357 quasi-ordered 80 regular closed 38 scattered 211 sifted through a sieve 378 successor of 88 well-ordered 228 set of representatives 69 sets, Borel 130 Borel, of type a 241 cofinal 81 coinitial 81 congruent modulo ideal 17 disjoint 9 disjoint modulo ideal 17 equipollent 169 equivalent by finite decomposition 191 independent 22 reduced modulo ideal 143 R-separable 340 similar 83 sets of the same cardinal number (of the same power) 173 sieve, 378 universal 385 sifted set 378 similar sets 83 similarity of relations 208 singular initial ordinal 308 u-additive family of sets 128 a-additive zero-one measure 317 a-multiplicative family of sets 128 space (universe) 18
space, 26 Baire 137 compact topological 139 ttt-compact topological 323 Stone 167 topological 26, 119 strongly inaccessible cardinal 311 subgraph 107 subset 7 subsystem of a relational system 157 successor of a set 88 sum, logical, of sentences 1 natural 260 sum of cardinal numbers 181,197 of elements of a Boolean algebra 33 of order types 222 of series of cardinal numbers 198 of sets 6, 52 supremum of elements 150 Suslin problem 220 symmetric difference 6 of sets 7 of elements of a Boolean algebra 33
Tarski recursion formula 288 tautology (logical law) 2, 11 theorem, Cantor-Bendixson 277 Cantor-Bernstein (Schroder-Bernstein) 190 first separation 355 Konig’s 203 mean-value 191 Ramsey’s 107, 109 Tychonoff’s 139 well-ordering (Zermelo’s) 261 theorem on definition by transfinite induction 239 on diagonalization 179
SUBJECT INDEX
theorem on the existence of pair 59 on the existence of union 59 on the existence of unordered triples, quadruples, etc. 59 topological space 26, 119 topology, 26 discrete 137 Tychonoff 135 transfinite sequence of type a 235 transformation (mapping) 70 transformability of Boolean polynomials 35 transitive relations 8 Tychonoff theorem 139 Tychonoff topology 135 type of a relational system 86
union of sets 52 unit element 83 of the ring 16 of Boolean algebra 37 universal function for a family 367 universal pair for a family 374
417
universal quantifier 46 universal sieve 385 universe (space) 18 unordered pair 59 upper section of a cut 159
value of a Boolean polynomial 34 of a function 70 vertices of a field of a graph 107 VN ordinal 269
weakly inaccessible cardinal 310 weakly inaccessible ordinal 309 well-ordered set 228 well-ordering theorem (Zermelo’s theorem) 261
Zorn maximal principle 263 zero element 82 Zermelo set theory 57 Zermelo-Fraenkel set theory 57