UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

On the foundations of the theory of ordinal numbers Dunik, Peter Anthony 1966

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-UBC_1966_A8 D8.pdf [ 2.84MB ]
Metadata
JSON: 831-1.0080598.json
JSON-LD: 831-1.0080598-ld.json
RDF/XML (Pretty): 831-1.0080598-rdf.xml
RDF/JSON: 831-1.0080598-rdf.json
Turtle: 831-1.0080598-turtle.txt
N-Triples: 831-1.0080598-rdf-ntriples.txt
Original Record: 831-1.0080598-source.json
Full Text
831-1.0080598-fulltext.txt
Citation
831-1.0080598.ris

Full Text

ON THE FOUNDATIONS OF THE THEORY" OF ORDINAL NUMBERS by PETER ANTHONY DUNIK, B.Sc. The U n i v e r s i t y of B r i t i s h Columbia 1964 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF ARTS -in the Department of Mathematics We accept t h i s t h e s i s as conforming t o the r e q u i r e d standard. THE UNIVERSITY OF BRITISH COLUMBIA • August, 1966. In presenting t h i s thesis i n p a r t i a l f u l f i l m e n t of the requirements f o r an advanced degree at the University of B r i t i s h Columbia,, I agree that the Library s h a l l make i t f r e e l y avail able for reference and study. 1 further agree that permission-for extensive copying of t h i s thesis f o r scholarly purposes may be granted by the Head of my Department or by his representatives. I t i s understood that copying or publication of t h i s thesis f o r f i n a n c i a l gain s h a l l not be allowed without my writ t e n permission. Department' of MATHEMATICS The University of B r i t i s h Columbia Vancouver 8, Canada Da^e September gOth, 1966 i i . ABSTRACT Three concepts of o r d i n a l numbers are examined w i t h a view to t h e i r i n t u i t i v e r i e s s and existence i n two p r i n c i p l e systems of axiomatic set theory. The f i r s t i s based on equivalence c l a s s e s of the s i m i l a r i t y r e l a t i o n between w e l l -ordered s e t s . Two a l t e r n a t i v e s are suggested i n l a t e r chapters f o r overcoming the problems a r i z i n g from t h i s d e f i n i t i o n . Next, o r d i n a l numbers are defined as c e r t a i n r e p r e s e n t a t i v e s of these equivalence classes,, and one of s e v e r a l such p o s s i b l e d e f i n i t i o n s i s taken f o r p r o v i n g the fundamental p r o p e r t i e s of these o r d i n a l s . F i n a l l y , a g e n e r a l i z a t i o n of Peano's axioms provides us w i t h a method of d e f i n i n g o r d i n a l numbers which are the u l t i m a t e r e s u l t of a b s t r a c t i o n s . TABLE OF CONTENTS Page CHAPTER Oj P r e r e q u i s i t e s 1 CHAPTER 1: The Can t o r - R u s s e l l Ordinals 8 CHAPTER 2: Sets Representing Ordinals 12 CHAPTER 3: On Zermelo's D e f i n i t i o n of O r d i n a l Numbers 17 CHAPTER 4: The Ca n t o r - R u s s e l l Ordinals as V i r t u a l Classes 31 CHAPTER 5: Approaches to O r d i n a l Numbers V i a Rank 36 CHAPTER 6: "Peano Axioms" f o r the Ordinals 42 BIBLIOGRAPHY 53 i v . ACKNOWLEDGEMENTS The author wishes t o express h i s a p p r e c i a t i o n f o r the i n v a l u a b l e a s s i s t a n c e rendered by Dr. D. Drake and Dr. M. Sion. F u r t h e r thanks are due f o r f i n a n c i a l a s s i s t e n c e t o the N a t i o n a l Research C o u n c i l o f Canada, 1. CHAPTER 0 : PREREQUISITES In t h i s chapter, we p r e s e n t the b a s i c f a c t s c o n c e r n i n g s e t t h e o r y and ordered s e t s which w i l l l a t e r be needed. A. SET THEORY To develop the f o u n d a t i o n s of o r d i n a l numbers i t i s e s s e n t i a l t o assume some t h e o r y of s e t s . We s h a l l draw from two such systems, Zermelo-Praenkel and von Neumanh-Berhays-Godel. To d e s c r i b e the l i m i t a t i o n s and d i f f e r e n c e s of these two systems, i t I s more p r o f i t a b l e t o d i s c u s s s e t th e o r y from Cantor's n a i v e p o i n t o f view f i r s t . 1. CANTOR'S NAIVE SET THEORY Cantor [ l ] d e f i n e s : "A s e t i s any c o l l e c t i o n i n t o a whole M of d e f i n i t e and separate o b j e c t s m of our i n t u i t i o n or our thought. These o b j e c t s are c a l l e d the elements of M." On the b a s i s of t h i s d e f i n i t i o n ^ we may r o u g h l y c h a r a c t -e r i z e s e t t h e o r y from Cantor's n a i v e p o i n t of view by the f o l l o w -i n g p r i n c i p l e s : ( i ) i f P i s a p r o p e r t y of mathematical e n t i t i e s then t h e r e e x i s t s a s e t whose elements are e x a c t l y those 1 o b j e c t s ^ V I s a t i s f y i n g the p r o p e r t y P . ( i i ) s e t s are mathematical e n t i t i e s and thus may 2. appear as elements of other sets\ ( i l l ) s e t s c o n t a i n i n g the same elements are i d e n t i c a l . U n f o r t u n a t e l y , as i s w e l l known, such a system i s i n c o n s i s t e n t (see Praenkel and B a r - H i l l e l [ l j f o r a d e t a i l e d account of the r e s u l t i n g paradoxes). ; P r i n c i p l e s ( i i ) and ( i i i ) seem unobject-i o n a b l e ; thus modern t h e o r i e s of s e t s put r e s t r i c t i o n s on p r i n c i p l e ( i ) . 2. ZEPJ^LO-raAENKEL SET THEORY This set theory can be described as a theory of l i m i t -a t i o n of s i z e of s e t s , I.e. paradoxes a r i s e i n Cantor's set theory by a l l o w i n g sets which are "too b i g " , as the set of a l l s e t s , the set of a l l o r d i n a l s , the set of a l l s e t s not elements of themselves, e t c . Thus i n s t e a d of p r i n c i p l e ( i ) we assume only s p e c i f i c i n stances of i t . We ensure the e x i s t e n c e , f o r any s e t , of i t s powerset and sumset. For two given s e t s , we can form the set whose elements are only these two s e t s . We assume, f o r any given s e t , any subset of i t which can be constructed according t o p r i n c i p l e ( I ) . An Axiom of I n f i n i t y I s added i n order t o guarantee the existence of sets c o n t a i n i n g an i n f i n i t e number of elementsw Arid the Axiom of Choice i s u s u a l l y i n c l u d e d . The universe of d i s c o r s e contains only s e t s , and there i s o n l y one set c o n t a i n i n g no elements. We w i l l r e f e r I n the sequel t o t h i s s e t theory as ZF . 1 ZF i s given a f u l l treatment i n Fraenkel [1]. Suppes [1] a l s o develops t h i s set theory, but he allows f o r the existence 3. of I n d i v i d u a l s ( o b j e c t s c o n t a i n i n g no elements) i n a d d i t i o n t o the empty s e t . 3. VON NEUMANN-BERNAYS-GODEL SET THEORY Thi s s e t theo r y conceives the paradoxes a r i s i n g not from assuming the e x i s t e n c e of s e t s which are too b i g , but by assuming these l a r g e s e t s as capable of membership i n other s e t s . Thus ZF's u n i v e r s e of discorpse i s extended t o two types o f obj e c t s ? s e t s , which are the s e t s o f ZF , and c l a s s e s , which are c o n s t r u c t e d from s e t s by p r i n c i p l e ( i ) . A l l s e t s are c l a s s e s , but not every c l a s s i s a s e t ; those c l a s s e s which are not s e t s are c a l l e d u l t i m a t e c l a s s e s . We may c h a r a c t e r i z e the u l t i m a t e c l a s s e s as those c l a s s e s which are i n c a p a b l e of. membership i n other c l a s s e s ^ e.g. the c l a s s o f a l l s e t s (denoted by V ), the c l a s s of a l l o r d i n a l s , e t c . In f a c t . a c l a s s I s an u l t i m a t e c l a s s i f and only i f i t can be mapped onto V . We w i l l r e f e r t o t h i s s et t h e o r y i n the sequ e l as NBG. NBG i s giv e n a f u l l treatment i n Godel [ I ] and Mendel son [ l ] - . 4. THE AXIOMS OF REPLACEMENT AND REGULARITY Both ZF and NBG assume the Axiom of Replacement, but the Axiom of R e g u l a r i t y i s o p t i o n a l . We d i s c u s s them separ-. •  . . . . i , .. .. a r e l y s i n c e they have important consequences f o r our development. The Axiom of Replacement s t a t e s t h a t i f f i s a 4. f u n c t i o n and domain f i s a s e t then range; f i s a set. T h i s axiom a l l o w s us t o form v e r y e x t e n s i v e s e t s which cannot he formed from the other axioms. We can d e s c r i b e i t s purpose t h i s way: the other axioms allow us t o form s e t s s t e p - b y - s t e p j t h i s axiom a l l o w us t o p r o g r e s s t o the l i m i t . The Axiom of Replacement i s assumed i n the s e q u e l , but lz mentioned where used. While the Axiom of Replacement e n l a r g e s our u n i v e r s e of s e t s , the Axiom of R e g u l a r i t y now r e s t r i c t s i t . T h i s axiom s t a t e s t h a t I f A i s a non-empty set (or c l a s s , i n NBG) then A has a member x which i s d i s j o i n t from A . Now by the other axioms of set theory, we n e i t h e r a f f i r m nor deny the. e x i s t e n c e of set's which are members of themselves, nor the e x i s t e n c e of s e t s c o n t a i n i n g an i n f i n i t e descending e - c h a i n , i . e . a s e t x h a v i n g the p a t t e r n .... x n € ... € x i e x. The Axiom of R e g u l a r i t y r e f u t e s the e x i s t e n c e of such s e t s . However, i t does not have the p l a u s i b i l i t y o f even the Axiom of Choice, and we do not assume I t i n the seque l , except i n Chapter 5. B. ORDERED SETS DEFINITION 1: . R ord e r s the set M i f f R.C M x M and t ( i ) f o r a l l m e M, (m,m) 1 R (R i s i r r e f l e x i v e ) , and ( I i ) f o r a l l m,n e M such t h a t m 4 n, e i t h e r (m,n) e R or (n,m) e R (R I s connected), and ( i i i ) f o r a l l m,n,p € M, i f (m,n) € R and (n,p) e R then (m,p) e R (R i s t r a n s i t i v e ) . DEFINITION 2: N i s an ordered s e t i f f N i s an ordered p a i r <M,R>, where M i s a s e t and R orde r s M. DEFINITION 3 : The ordered s e t N = <M,R> i s s i m i l a r t o the ordered s e t N 1 = <M',R'> i f f t h e r e e x i s t s a f u n c t i o n f which Is one-to-one, whose domain i s M and whose range i s M', and such t h a t f i s o r d e r - p r e s e r v i n g , i . e . f o r a l l x,y e M, (x,y) e R i f f ( f ( x ) , f ( y ) ) e R'1. THEOREM 1: Any s i m i l a r i t y r e l a t i o n ; i s an equiv a l e n c e r e l a t i o n . -C. WELL-ORDERED SETS DEFINITION 4: R w e l l - o r d e r e s the set M i f f R orde r s the set M and every non-empty subset N of M has an R - f i r s t element, i . e . t here i s an n € N such t h a t , f o r a l l p € N w i t h p + n, (n,p) e R. DEFINITION 5; N i s a w e l l - o r d e r e d s e t i f f N I s an ordered p a i r <M,R> where M i s ' a s e t and R w e l l - o r d e r s M. Suppose <M,R> i s an ordered s e t and N C M. We denote by R/N the s e t R fl (N x N), i . e . the r e s t r i c t i o n o f R t o N. THEOREM 2: I f <MjR> i s a w e l l - o r d e r e d s e t and N C M, then <N,R/N> i s a w e l l - o r d e r e d s e t . We s h a l l have many oc c a s i o n s t o d i s c u s s s e t s which are w e l l - o r d e r e d by e, i . e . s e t s M which are w e l l - o r d e r e d by { (x,y) : x,y e M and x € y }. T h i s w e l l - o r d e r i n g I s denoted by £ M . DEFINITION 6: A i s the i n i t i a l R-segment o f the s e t M corres-ponding t o m i f m e.M and R well-borders M and A = { x e M : (x,m) e R ]. DEFINITION 7: 'A i s an i n i t i a l segment of the w e l l - o r d e r e d s e t <M,R> i f f t h e r e e x i s t s an m e M such t h a t A i s the i n i t i a l R-segment c o r r e s p o n d i n g t o m. / By Theorem 2 an i n i t i a l segment A of a w e l l - o r d e r e d i • • set <M,R> can he w e l l - o r d e r e d by R/A. I i • i \ We now s t a t e , without p r o o f , the C o m p a r a b i l i t y Theorem f o r w e l l - o r d e r e d s e t s : THEOREM 3: L e t <M^P> and <N,R> be w e l l - o r d e r e d s e t s . Then e x a c t l y one of the f o l l o w i n g h o l d s : ( i ) <M,P> i s s i m i l a r t o <N,R>, ( i i ) t h e r e e x i s t s an i n i t i a l segment A of <N,R> such t h a t <M,P> i s s i m i l a r t o <A,R/A> , ( i i i ) t h ere e x i s t s an I n i t i a l segment B of <M,P> such t h a t <N,R> i s s i m i l a r t o <B,P/B>. D. ORDINAL NUMBERS In view of the c o m p a r a b i l i t y o f w e l l - o r d e r e d s e t s , i t i s convenient t o have measures f o r them, i . e . a standard c l a s s of o b j e c t s r e p r e s e n t i n g w e l l - o r d e r e d s e t s , two s i m i l a r w e l l -ordered s e t s b e i n g r e p r e s e n t e d by the same o b j e c t . These measures are c a l l e d o r d i n a l numbers (synonymously, J u s t o r d i n a l s ) . 8. CHAPTER 1 : THE CANTOR-RUSSELL ORDINALS Cantor [ l ] proposes: "Every ordered set M has a d e f i n i t e ' o r d i n a l type'... which we w i l l denote "by M . By t h i s we understand the g e n e r a l concept which r e s u l t s from M i f we o n l y a b s t r a c t from the nature of the elements m, and r e t a i n the order of precedence among them. Thus the o r d i n a l type M i s i t s e l f an ordered s e t whose elements are u n i t s which have the same order o f precedence among one another as the co r r e s p o n d i n g elements o f M , from which they are d e r i v e d by a b s t r a c t i o n . " Again, "A simple c o n s i d e r a t i o n shows t h a t two ordered s e t s have the same o r d i n a l type I f , and.only i f , they are s i m i l a r . . . " F i n a l l y , "The o r d i n a l type o f a w e l l - o r d e r e d set i s c a l l e d i t s ' o r d i n a l number'." Such a p r o p o s a l , as i t stands, I s unacceptable i n axi o m a t i c s e t theory, f o r we have no guarantee t h a t the o r d i n a l types e x i s t . Of course, we could i n t r o d u c e the o r d i n a l type of M as a new p r i m i t i v e f u n c t i o n , and impose the f o l l o w i n g as an axiom t o ensure t h i s f u n c t i o n ' s adequacy: i f M and N are ordered s e t s , then M = N I f f M I s s i m i l a r , t o N . However t h i s Is r e a l l y no s o l u t i o n . But Cantor's process of , a b s t r a c t i o n has m e r i t . We now d e s c r i b e a r i g o r o u s resolvement of t h i s problem based'on the eq u i v a l e n c e r e l a t i o n of s i m i l a r i t y . Cantor was concerned w i t h ordered s e t s (although he u s u a l l y supressed the o r d e r i n g r e l a t i o n , as we see i n h i s p r o p o s a l above). But a c o n s i d e r a t i o n of the o r d e r i n g r e l a t i o n o n l y i s s u f f i c i e n t . For l e t R be such a r e l a t i o n ; d e f i n e f i e l d R , denoted by 3?(R) , as domain R u range R. Then R orders 3(R) , and R orders the s e t A i f f A = 3(R) . i > . 9. Furthermore, we can i n an obvious way g e n e r a l i z e our d e f i n i t i o n of s i m i l a r i t y t o ordered p a i r s <3(R),R> , where R i s any r e l a t i o n , not. n e c e s s a r i l y an o r d e r i n g onev Thus Whitehead and R u s s e l l [1] d e a l w i t h r e l a t i o n s only, g e n e r a l i z i n g o r d i n a l types t o ' r e l a t i o n numbers'. DEFINITION 1: The r e l a t i o n R I s s i m i l a r t o the r e l a t i o n S i f f <3(R),R> i s s i m i l a r to <3(S),S> . DEFINITION 2; The r e l a t i o n number of the r e l a t i o n R , denoted by Nr(R) , i s the c l a s s of a l l r e l a t i o n s s i m i l a r t o R . THEOREM Is I f R and S are r e l a t i o n s , then Nr(R) * Nr(S) i f f R i s s i m i l a r to S . DEFINITION 3: An o r d i n a l type i s the r e l a t i o n number of ah o r d e r i n g r e l a t i o n . DEFINITION 4; An o r d i n a l number i s the r e l a t i o n number of a w e l l - o r d e r i n g r e l a t i o n . Thus an o r d i n a l number i s the o r d i n a l type of a w e l l - o r d e r i n g r e l a t i o n . DEFINITION 5: a i s a r e l a t i o n number i f f there e x i s t s a r e l a t i o n R such t h a t a = Nr(R) . S i m i l a r d e f i n i t i o n s f o r a t o be an o r d i n a l type or, o r d i n a l number are assumed. DEFINITION 6 : The w e l l - o r d e r i n g r e l a t i o n R i s l e s s than the ; w e l l - o r d e r i n g r e l a t i o n S i f f there e x i s t s an i n i t i a l segment 10. A of <3(S),S> such t h a t <3(R),R> i s s i m i l a r t o <A,S/A> DEFINITION .7 : Nr(R) < Nr(S) i f f R i s l e s s than S . > We o b t a i n immediately from the d e f i n i t i o n s : THEOREM 2: I f u,v are o r d i n a l numbers then \x < v i f f t h e r e e x i s t s w e l l - o r d e r i n g r e l a t i o n s R and S such t h a t H = Nr(R), v = N r ( S ) , and R i s l e s s than S . In view of the c o m p a r a b i l i t y of w e l l - o r d e r i n g r e l a t i o n s ; THEOREM 3; I f H a V are o r d i n a l numbers then e i t h e r u < v or a «= v or v < p, . We p r e f e r t o d e a l w i t h ordered s e t s r a t h e r than J u s t o r d e r i n g r e l a t i o n s ; thus DEFINITION 8: The C a n t o r - R u s s e l l o r d i n a l number of the w e l l ordered s e t <A,R> i s the c l a s s of a l l w e l l - o r d e r e d s e t s which are s i m i l a r t o <A5R> . Now l e t us examine the approach i n more d e t a i l . Three advantages are immediate. F i r s t l y , we can a c t u a l l y d e f i n e the o r d i n a i number of a w e l l - o r d e r e d s e t , thus r e s o l v i n g one c r i t i c i s m o f Cantor's p r o p o s a l . Secondly, by d e f i n i n g o r d i n a l numbers as equ i v a l e n c e c l a s s e s , we r e a l l y have a b s t r a c t e d from the nature o f the elements of w e l l - o r d e r e d s e t s . T h i r d l y , the I n t r o d u c t i o n o f o r d i n a l s by t h i s method i s i n t u i t i v e , and l e a d s t o a n a t u r a l development of t h i s theory. 11. But t h e r e I s one major o b s t a c l e t o a c c e p t i n g the Cantor-R u s s e l d e f i n i t i o n of o r d i n a l numbers: these o r d i n a l s are u l t i m -ate c l a s s e s (except f o r {#}). Thus the C a n t o r - R u s s e l l o r d i n a l s do not e x i s t i n ZF, and although they do e x i s t i n NBG, we cannot have c l a s s e s of these o r d i n a l s . ( T h i s was no problem f o r Whitehead and R u s s e l l , f o r they had developed a d i f f e r e n t s e t t h e o r y which enabled them t o have u l t i m a t e c l a s s e s as capable of elementhood. We d i d not d e s c r i b e t h e i r t h e o r y i n Chapter G, s i n c e i t I s not a p o p u l a r b a s i s f o r mathematics.) However i n Chapters k and 5> we show how t h i s d i f f i c u l t y can be p a r t i a l l y r e s o l v e d v i a the n o t i o n s of v i r t u a l c l a s s e s and rank. Another o b j e c t i o n i s t h a t the C a n t o r - R u s s e l l o r d i n a l s do not s a t i s f y completely Cantor's d e f i n i t i o n ; the o r d i n a l number of the w e l l - o r d e r e d s e t M i s not a w e l l - o r d e r e d s e t whose,elements are u n i t s h a v i n g the same order o f precedence among one another as the c o r r e s p o n d i n g elements of M . We s h a l l next be occupied w i t h d e f i n i n g o r d i n a l numbers which do s a t i s f y t h i s p r o p e r t y . 12. CHAPTER 2 : SETS REPRESENTING ORDINALS Inasmuch as the iCantor.-Russel d e f i n i t i o n of o r d i n a l numbers proves unacceptable i n b o t h ZP and NBG, we are l e d t o the I d e a l of choosing a r e p r e s e n t a t i v e from each o r d i n a l e q u iv-alence c l a s s and c a l l i n g t h i s r e p r e s e n t a t i v e the o r d i n a l . By t h i s method, not o n l y do the o r d i n a l s become s e t s , but a l s o we can d e f i n e these r e p r e s e n t a t i v e s without r e f e r r i n g a t a l l t o the concept of order J T h i s appears s u r p r i s i n g a t f i r s t , but we w i l l come t o i d e n t i f y an o r d i n a l w i t h the s e t of a i l l e s s e r o r d i n a l s , and thus our o r d i n a l s become w e l l - o r d e r e d by the € - r e l a t i o n ( t h i s i d e a i s . due t o von Neumann [ 1 ] ) . Obviously t h i s method w i l l not work f o r g e n e r a l o r d i n a l t y p e s , s i n c e they are not always comparable. S t i l l , we are l e f t w i t h f o r m a l l y d e f i n i n g these* r e p r e s e n t a t i v e s . I n t e r e s t i n g l y enough, a v a r i e t y of d e f i n i t -i o n s have been proposed which a l l prove e q u i v a l e n t (sometimes w i t h the Axiom of R e g u l a r i t y ) . We now l i s t the more popul a r of these d e f i n i t i o n s * p o s t p o n i n g the p r o o f of t h e i r e q uivalence u n t i l the end of the next chapter. The p r o o f t h a t these o r d i n a l s do i n f a c t p r e s e n t us w i t h a r e p r e s e n t a t i v e from each o r d i n a l e q u i v a l e n c e c l a s s a l s o appears i n t h a t chapter. As a p r e l i m i n a r y , we need two important n o t i o n s : DEFINITION 1: ' A s e t x i s t r a n s i t i v e i f f \jx c,x . DEFINITION 2: A non-empty s e t x i s well-founded i f f t h e r e i s 13. a y e x such t h a t y n x = j& . ZERMELO' S DEFINTTIGN: A set x i s an o r d i n a l number i f f ( i ) i f t e x then t U {t} e x or t U {t} = x , and ( i i ) i f z C x then Uz € x or Uz = x . Although Zermelo formulated h i s d e f i n i t i o n i n 1915* he never p u b l i s h e d i t ; i t f i r s t appeared In the l i t e r a t u r e i n Berrtays [ I ] . Thus t o von Neumann i s g e n e r a l l y a t t r i b u t e d the f i r s t d e f i n i t i o n of o r d i n a l s as sets w e l l - o r d e r e d by •€'.." Zermelo's o r i g i n a l d e f i n i t i o n contained the a d d i t i o n a l c o n d i t i o n : x 0 = . or' 0 e x , but t h i s i s implied"by ( i i ) . 1 . '¥e develop"the foundations of or d i n a l " number theory .based on t h i s d e f i n i t i o n i n the next chapter. von NEUMANN'S DEFINITION: A set x i s an o r d i n a l number i f f there e x i s t s a w e l l - o r d e r i n g R on x such t h a t every element of x i s equal t o i t s corresponding i n i t i a l R-segment. This d e f i n i t i o n f i r s t appears i n von Neumann [1] . I t o b v i o u s l y i m p l i e s t h a t an o r d i n a l i s the set of a l l l e s s e r o r d i n a l s . GODEL'S DEFINITION: A set x i s an o r d i n a l ntimber i f f ( i ) x i s t r a n s i t i v e , and ( l i ) every non-empty subset of x I s well-founded, and ( i i i ) every element of x i s t r a n s i t i v e . Gpdel proposed h i s d e f i n i t i o n i n a s e r i e s of l e c t u r e s i n Vienna i n 1937. He never p u b l i s h e d i t ; i t ' too appears f i r s t I n the l i t e r a t u r e i n Bernays [ l ] . C o n d i t i o n ( i i ) can be 14. dropped i f we assume the Axiom of R e g u l a r i t y . ROBINSON'S DEFINITION: A s e t x i s an o r d i n a l number i f f ( i ) x i s t r a n s i t i v e , and ( i i ) every non-empty subset of x Is well-founded, and ( I i i ) I f a,b e x and, a + b then a € b or b e a . T h i s d e f i n i t i o n appears i n Robinson [ 1 ] ; i t i s the most w i d e l y accepted s i n c e the b a s i c theorems of o r d i n a l s can be ob t a i n e d q u i t e e a s i l y i n view of the powerful t h i r d c o n d i t i o n . Again, c o n d i t i o n ( i i ) can be dispensed w i t h i f we assume the Axiom of R e g u l a r i t y . BERNAY 1S DEFINITION: A s e t x i s an o r d i n a l number i f f (1) x i s t r a n s i t i v e ( i i ) e v ery non-empty proper subset o f x i s an element of x . T h i s d e f i n i t i o n appears In Bernay's [ 1 ] , C o n d i t i o n ( I ) can s u r p r i s i n g l y be dropped, as the d e f i n i t i o n o f I s b e l l [1] shows. S e v e r a l other d e f i n i t i o n s are proposed i n S t e i n [ l ] , and t h e i r e q u i v a l e n c e t o some of the above d e f i n i t i o n s i s proved. We now d i s c u s s an i n t e r e s t i n g d e f i n i t i o n of o r d i n a l s which i n c o r p o r a t e s 1 the p r i n c i p l e of t r a n s f i n i t e i n d u c t i o n . In a s e t t h e o r y which admits u l t i m a t e c l a s s e s (like:NBG), we can d e f i n e the s e t N of n a t u r a l numbers as n{A : 0 e A , and i f x € A then x u {x} e A } . I t i s e s s e n t i a l t h a t u l t i m a t e 15. c l a s s e s e x i s t t o "be able t o make such a d e f i n i t i o n , Since the c l a s s of a l l sets c o n t a i n i n g a c e r t a i n set i s not a set. Now acc e p t i n g t h i s d e f i n i t i o n of N t h e p r i n c i p l e of i n d u c t i o n i s immediately forthcoming. For suppose P i s a prop e r t y of n a t u r a l numbers such t h a t P(0) and whenever P(x) then P(x U {x}); l e t A - { n e N ; P(n) } . By the d e f i n i t i o n of N, K A j thus N = A . Sion and Wil l m o t t [ l ] introduce the o r d i n a l s as a nat-u r a l extension of t h i s d e f i n i t i o n ; the c l a s s of o r d i n a l s i s def-ined f i r s t , and then an o r d i n a l i s defined as an element of the c l a s s or the c l a s s i t s e l f . We need a p r e l i m i n a r y n o t i o n : DEFINITION 3: A set A i s a nest I f f f o r a l l x,y e A , e i t h e r x c y or y £ x . SION AND WILLMOTT'S DEFINITION: (.1) Q = n{ A : ( i ) i f x e A then x U ,{x} e A , and ( i i ) i f B £ A i s a nest and B € V then UB € A } . ( 2 ) x i s an o r d i n a l i f f x e Q or x = Q Notice t h a t 0 € A i s i m p l i e d by (Ii)> I n c l u d i n g Q as an o r d i n a l causes no c o n t r a d i c t i o n since i t i s e a s i l y proved t h a t Q I s not a s e t , and so Q 4 Q • Analogous t o the previous d e f i n i t i o n of the set of n a t u r a l numbers, t h i s d e f i n i t i o n of o r d i n a l s i n c o r p o r a t e s the p r i n c i p l e of t r a n s f i n i t e i n d u c t i o n : i f P i s a pr o p e r t y of the elements of Q- such t h a t (a) i f P(x) t h a t P(x U {x}), and (b) i f B i s a nest of elements of Q w i t h the pr o p e r t y P and B i s a set then P(UB), then P(x) 16. f o r every x e Q . For l e t A = { x e Q : P(x) ) . Then from (a) and (b) we see A s a t i s f i e d ( i ) and ( i i ) of the d e f i n -i t i o n of Q and so Q c A; thus A = Q . 17. CHAPTER '5 : ON ZERMELO'S DEFINITION OF ORDINAL NUMBERS From the definitions of ordinal numbers in the pre-ceeding chapter, Zermelo's should be singled out as being more Intuitatively founded in that i t Incorporates the generating operations of successor and limit (union) by which higher ordinals are constructed from lesser ones. It therefore seems, logical to base a development of ordinal number theory on this definition; this we shall do presently. Our development Is carried our In ZF, without the Axiom of Regularity. The addition of this axiom would much simplify our work (Lemmas 1,2,9 could then be omitted). We restate Zermelo's definition: DEFINITION 1: A set x i s an ordinal (number) i f f ( i ) i f t e x then t o Ct) e x U [x) , and ( i i ) i f z c. x then Uz e x U (x) . LEMMA 1: If x i s an ordinal and t e x , then t |. t . Proof: Let w = [ y e x : y c x and i f t e y then t \ t ] . If t e Uw then t 4 t; thus Uw 4 UW' • Moreover, Uw c x . Since w c x , either uw e x or Uw = x by ( i i ) of Definit-ion 1. Case 1: Uw e x . Then either Uw U CtJw} e x or Uw U {tlw} = x by (I) of Definition 1. If Uw U {uw} e x then Uw u (Uw] e w i thus Uw u CUw] C Uw , implying Uw e uw , a contradiction. Therefore uw U (uw) = x . Now i f t e x then either t € Uw in which case t 4 t , or t = uw , and 18. Uw 4 Uw . Case 2: uw = x . Then-if t e x , t f t . A LEMMA 2: I f x Is an o r d i n a l then x ^ x . Proof: I f x € x then x 4 x by Lemma 1. C o n t r a d i c t i o n . Thus x 4 x A LEMMA 3: I f x i s an o r d i n a l then e i t h e r ux = x or Ux U tux) = x . Proof: Suppose ux 4= x and ux U {Ux} + x • Then, by D e f i n i t i o n 1, ux e x and Ux u {ux} e x . Thus Ux u CUx} c ux , Implying ux e ux , a con t r a d i c t i o n . ' Thus Ux = x or Ux U {Ux} = x . Furthermore, we cannot haye both Ux = x and Ux U {tlx} = x , f o r then x u {x} = x , Implying x e x , a c o n t r a d i c t i o n . A LEMMA 4: I f x I s an o r d i n a l then x i s t r a n s i t i v e . Proof: By Lemma 3, ux £ x , which i s t r a n s i t i v i t y . A LEMMA 5 : I f x and y are o r d i n a l s , then x e y i f f x c y . Proof: I f x e y then x £ y since y i s t r a n s i t i v e . . I f x = y then y € y , a c o n t r a d i c t i o n ; thus x c y . Conversely, suppose x"c y ; then tlx s y u {y} . By Lemma 3> e i t h e r Ux = x or ux U {ux} = x . I f Ux = x then x € y u {y} , and since x = y i s excluded, x e y . I f Ux U {Ux} = x then Ux u {Ux} c y , Implying Ux e y . Thus Ux u {Ux} e y U {y} by ( i ) of D e f i n i t i o n 1; so x € y U {y} . Since x = y i s excluded, x e y . A 19. LEMMA 6: I f A i s a non-empty s e t of o r d i n a l s then HA i s an o r d i n a l . P r o o f : We show OA s a t i s f i e s D e f i n i t i o n 1. Obviously CIA i s t r a n s i t i v e . Suppose now t e OA j then t e x f o r every x e A , and thus t u {t} € x U {x) f o r every x e A . Case 1: t u {t} € x f o r every x e A . Then t U ( t ) e HA . Case 2: t U {t} = x f o r some x e A . We then show t U, {t} = fS'A . C l e a r l y OA c. t u {t} . Now l e t s e t u {t} . I f s e t then s € CIA s i n c e OA i s t r a n s i t i v e . I f s = t then s e OA by h y p o t h e s i s . Thus t U ( t ) ^  HA , and so t u {t) = OA . The r e f o r e , f o r every t e DA , t u {t) € HA U {DA] . Suppose z £/TVA ; then z c.. x f o r every x e A . Thus oz e x i] [x] f o r every x e A . Case 1: uz € x f o r every x € A . Then Uz € OA . Case 2: Uz = x f o r some x e A . We*then show Uz - OA . _ C l e a r l y OA c Uz . Now l e t t € Uz ; then t e s f o r some s e z . Thus t € s f o r some s € HA , and, s i n c e nA I s t r a n s i t i v e , t e OA . Thus uz C hA , and so Uz = HA . Th'ereforei f o r every z C OA , \}z € OA U {HA} . We have thus shown t h a t OA i s an o r d i n a l . - - A The f o l l o w i n g lemma e s s e n t i a l l y s t a t e s t h a t the o r d i n a l s are w e l l - o r d e r e d by e (thus a l s o by c , i n view o f Lemma 5). LEMMA 7: I f A i s a non-empty set of o r d i n a l s then OA e A . Pro o f : O b v i o u s l y f l A c x f o r every x c A . Suppose OA 4 x f o r every x €'A ; then HA € x f o r every x € A by Lemma 5. Thus HA e OA , a c o n t r a d i c t i o n . T h e r e f o r e hA = x f o r some 20. x e A . & Co m p a r a b i l i t y of o r d i n a l s now f o l l o w s e a s i l y ; LEMMA 8: I f x and y are o r d i n a l s , then e x a c t l y one of the f o l l o w i n g h o l d s : x e y, or x = y, or y e x . Proof : By Lemma 7* x n y e {x,y} . The a s s e r t i o n f o l l o w s u s i n g Lemma 5. A LEMMA 9t I f A Is a ndn-empty set of o r d i n a l s t h e n A i s w e l l -i founded. Pr o o f : We show A n (HA) = J0 . Suppose t h e r e Is a y e A H (HA); then y e A and y e x f o r every x e A . Thus y € y , a c o n t r a d i c t i o n . A LEMMA 10: 0 i s an o r d i n a l . LEMMA 11: I f x i s an o r d i n a l then x u {x} i s an o r d i n a l . P r o o f : We show t h a t x U {x} s a t i s f i e s D e f i n i t i o n 1. Let t € x U {x} . I f t e x then t U {t} € x U {x} ; i f t = x then t u {t} e ( x u {x}3 ; thus f o r every t e x u {x} , t U it} e x u {x} u { x U {x}} . Now suppose z £ x U {x} j e i t h e r z c x or , z = w U (x} f o r some w £ x . I f z c x then uz e x u {x} . I f z = w'u {x} then Uz = Uw u x = x e x (J {x} . Thus, f o r every z c x U {x} , Uz e x u {x} u {x u Cx}} . A LEMMA 12: I f A i s a t r a n s i t i v e s e t of o r d i n a l s then A Is an b r d i n a l . 21. P r o o f : We show A s a t i s f i e s D e f i n i t i o n 1. L e t t € A., and suppose t u {t} 4 A U {'A') .. Since then t u ( t ) c A , t h e r e i s a y € A such t h a t y 4 t u i t ) . Since t u {t} i s an o r d i n a l , e i t h e r y = t u {t} or t u {t} € y. We have excluded y = t u {t} ; thus t u {t} e y.- Since A i s t r a n s i t i v e , t u i t ) e A . C o n t r a d i c t i o n . Thus t u {t) e A u {A} f o r every t e A . Now suppose z c A , and assume Uz 4 A U {A} . Since A Is t r a n s i t i v e , Uz e uA c A ; s i n c e we assumed Uz 4 A > there i s a y e A such t h a t y 4 Uz . Thus y 4 t f o r every t e z a and so, f o r every t e z , e i t h e r t e y or t = y by Lemma 8. We cannot have t € y f o r every t e z , f o r then z c y, i m p l y i n g uz e y u [y}> which c o n t r a d i c t s uz 4 A» Thus we must have y = t f o r some t e1' z. We show now t h a t y = uz. C l e a r l y y c Uz . Let now s e Uz; then s € v f o r some v e z. Since s e A, e i t h e r y e s or y = s or s e y. Since v i s t r a n s i t i v e , we exclude y e s, f o r then y e v c.uz. We a l s o exclude y = s, f o r then a g a i n y e uz. Thus s e y. The r e f o r e Uz c y , and so y = Uz . But then Uz € A, a c o n t r a d i c t i o n . Thus Uz ,€ A U {A} ; , Thus A'1 i s an o r d i n a l . A LEMMA 13: I f x i s ah o r d i n a l and y e. x , then y i s an o r d i n a l . Proofs L e t A = { y e x : y i s an o r d i n a l , and i f t e y then t i s an o r d i n a l }. We show A i s a ' t r a n s i t i v e s e t of o r d i n a l s . I f t e. uA , then t e y f o r some y e A ; thus t i s an o r d i n a l and, s i n c e y c x , t e x . I f s e t then s e y 22. s i n c e y i s t r a n s i t i v e ; thus s i s an o r d i n a l . T herefore t e A } and so A Is a t r a n s i t i v e s et of o r d i n a l s ; thus A i s an o r d i n a l . T h e r e f o r e A e x or A = x I f A e x then A € A s a c o n t r a d i c t i o n . Thus A = x , and every element of A i s an o r d i n a l . A LEMMA l4s I f A i s a s e t of o r d i n a l s then UA i s an o r d i n a l . Proof? C e r t a i n l y i f t'e UA , then t Is an o r d i n a l . Now suppose s € UUA ; then s's t f o r some t e UA ; then t e x f o r some x s A . Since x I s t r a n s i t i v e , s e x ; thus s"€ UA . T h e r e f o r e UA i s a t r a n s i t i v e s et of o r d i n a l s , and so,' by Lemma 12, UA i s an o r d i n a l . A LEMMA 15s I f x i s an ordinal> then t e x i f f t i s t r a n s -i t i v e and t c x . Proofs I f t e x then t i s an o r d i n a l ; thus t i s t r a n s -i t i v e . S i nce x i s t r a r i s l t i v e i t c., x ; we excluded t » x , so t i c x . Conversely, i f t i s a proper t r a n s i t i v e subset of x then x i s a t r a n s i t i v e s e t of o r d i n a l s ; thus t Is an o r d i n a l . Since t c x , t e x "'by Lemma 5. A LEMMA l6s I f x i s an o r d i n a l and f& £ t c x , then t i s well-founded. Proofs t Is a non-empty s e t o f o r d i n a l s ; thus t Is w e l l -founded by Lemma 9« A LEMMA 17s I f x i s an o r d i n a l , then x - Ux i f f t U {t} e x f o r every t e x . 23. P r o o f : Suppose x = Ux , and l e t t € x j then t U {t} e x U {x} . I f t "U'-{t} = x then t = u(t U {t}) = u x = x y which c o n t r a d i c t s t e x . Thus t U {t} e x f o r every t € x. Conversely, I f t 0 [ t ] e x f o r every t e x , then x c. Ux , and s i n c e Ux c x , tjx = x . k LEMMA 18s I f x and y are o r d i n a l s , then x = y i f f x u {x} = y u {y} . LEMMA 19s I f x i s an o r d i n a l , then t h e r e i s no s e t y such t h a t x € y e x U {x} . Proof : I f y e x. then x-e. ,x s i n c e x i s t r a n s i t i v e ; c o n t r a -d i c t i o n . I f y ='x' then aga.in x'/e x , Thus there can,.h^,.,no « such 7 . A DEFINITION 2: An o r d i n a l x + 0 i s a l i m i t o r d i n a l i f f x = Ux . DEFINITION 3 s An o r d i n a l x i s a successor o r d i n a l i f f t h e r e e x i s t s an o r d i n a l y s u c h t h a t x = y u {y},. LEMMA 20: I f x i s an o r d i n a l then x i s e i t h e r a l i m i t o r d i n a l or a successor o r d i n a l or J0 . Pr o o f : By Lemma 3 , x = Ux or x = Ux U CUx] . • We now show the B u r a l i ^ F o r t i paradox cannot be d e r i v e d i n ZF. LEMMA 21: There i s no s e t c o n s i s t i n g of a l l the o r d i n a l s . P r o o f s Suppose such a s e t e x i s t s , and l e t us denote i t by Z . I f t e Z then t U {t} <s Z s i n c e t u {t} i s an o r d i n a l . I f s c Z then Us <s Z s i n c e Us i s an o r d i n a l . Thus Z I s 24, an o r d i n a l by D e f i n i t i o n 1. But then Z e Z , a c o n t r a d i c t i o n . In Bachman [ l ] and S i e r p i n s k i [ l ] we can f i n d an e n c y c l o p e d i c treatment of the a r i t h m e t i c of o r d i n a l numbers. We here prove the fundamental theorems o f o r d i n a l number theory. THEOREM Is PRINCIPLE OF TRANSFINITE INDUCTION. Suppose P i s a p r o p e r t y o f o r d i n a l s such t h a t ( I ) P(0), and ( i i ) i f P(x) then P(x U {x}), and ( H i ) i f z i s a l i m i t o r d i n a l such t h a t P ( t ) f o r - e v e r y t e z , then ' P ( z ) . Then P(y) f o r every o r d i n a l y . Proofs Suppdse t h e r e I s an o r d i n a l t such t h a t P ( t ) i s f a l s e j then there I s a l e a s t o r d i n a l y such t h a t P(y) i s f a l s e . Now y may be J0 !, i n which case P(y) by ( i ) , or y may be a successor o r d i n a l , i n which case P(y) by ( I I ) * or y may be a l i m i t o r d i n a l , i n which ease P(y) by ( i i i ) . Contra-d i c t i o n . Ttojus P(y) f o r every o r d i n a l y . A The f o l l o w i n g r e f o r m u l a t i o n o f the P r i n c i p l e xif T r a n s f i r i i t e i n d u c t i o n i s somewhat e a s i e r t o applys THEOREM 2s Suppose P i s a p r o p e r t y of o r d i n a l s such t h a t , f o r every o r d i n a l y , i f x € y then P ( x ) , we have P ( y ) . Then 'P('y) f o r every o r d i n a l y . Proofs Suppdse there i s ah o r d i n a l t such t h a t P ( t ) i s " f a l s e , and assume t i s the l e a s t such o r d i n a l . The P(x) f o r every x € t . Thus,by the h y p o t h e s i s , P ( t j , a c o n t r a -d i c t i o n . Thus, P(y) f o r every o r d i n a l y. A 25. The f o l l o w i n g lemma i s a g e n e r a l i z a t i o n o f Theorem 2 to any w e l l - o r d e r e d sets LEMMA: Let <A,R> be a w e l l - d r d e r e d s e t , and l e t P be a p r o p e r t y o f the elements of A such that., f o r any a e A, i f P(b) holds f o r a l l b w i t h (b,a) e R > then P ( a ) . Then P(a) f o r every a € A . The f o l l o w i n g r e p r e s e n t a t i o n theorem shows t h a t the Zefmelo o r d i n a l s are an adequate c h a r a c t e r i z a t i o n of w e l l -ordered s e t s , I.e. the Zermelo o r d i n a l s capture a l l the w e l l -ordered s e t s up t o a s i m i l a r i t y . THEOREM 3s I f <A,R> i s a w e l i - o r d e r e d s e t t h e n t h e r e i s a unique o r d i n a l a such t h a t <A,R> i s s i m i l a r t o <a9£a>. Proof:, We d e f i n e by r e c u r s i o n a f u n c t i o n f on A such t h a t , f o r every x e A , f ( x ) = C f ( y ) s (y,x) c R} . (1) f ( x ) Is an o r d i n a l f o r every x e A . For l e t y e A w i t h f ( t ) an o r d i n a l f o r every t such t h a t ( t , y ) € R . Then f ( y ) i s a.set or o r d i n a l s , \ and f ( y ) i s t r a n s i t i v e by v i r t u e o f the t r a n s i t i v i t y of R; thus f ( y ) i s an o r d i n a l . Theref-ore 'f('x) i s an o r d i n a l f o r every x e A by the Lemma. (2) f i s one-to»ohe. For suppose not; l e t a be be the R - l e a s t element of A such t h a t there e x i s t s a b w i t h (b,a) € R and f ( a ) = f ( b ) . Then o b v i o u s l y f (b) = f (b«) from the d e f i n i t i o n of f , where b«' i s the immediate successor o f b under R . But c l e a r l y 26. f(b»)"» f ( b ) U { f ( b ) ) , a l s o from the d e f i n i t i o n of f . Thus f ( b ) e f ( b ) , a c o n t r a d i c t i o n . So f i s 1-1. (3) f ;(A) i s an o r d i n a l . For,by ( i ) , f ( A ) i s a s e t o f ' o r d i n a l s . That f ( A ) i s t r a n s i t i v e f o l l o w s from the t r a n s i t i v i t y of R . (4) f i s o r d e r - p r e s e r v i n g . For l e t a,b e A and suppdse (a,b) € R . By the d e f i n i t i o n of f , f (a) e f ( b ) . Conversely suppose f ( a ) e f ( b ) ; s i n c e R we 11-orders- A , e i t h e r a = b or (b,a) € R or (a,b) s R . I f a = b then f ( a ) = f ( b ) s i n c e f Is one-to-one. C o n t r a d i c t i o n . I f (b,a) e R then f ( b ) € f ( a ) j a c o n t r a d i c t i o n . jThus (a>b) .€ R / and so f i s o r d e r - p r e s e r v i n g . Thus l e t t i n g a = f ( A ) , f i s a s i m i l a r i t y mapping betweeh <A,R> and <a 5 £ a> . The uniqueness of a i s obvious. t Although i n ZF there Is no s e t . c o n s i s t i n g , of a l l the o r d i n a l s , the c l a s s Z of a l l the Zermelo o r d i n a l s does e x i s t i n NBGj Z i s an u l t i m a t e c l a s s . Now i n an obvious way, we can extend our d e f i n i t i o n of s e t s w e l l - o r d e r e d by r e l a t i o n s t o cover; u l t i m a t e c l a s s e s , and we denote such w e l l - o r d e r e d c l a s s e s by the ambiguous n o t a t i o n (A,R)j here (A,R) cannot r e f e r t o an ordered p a i r . We assume the concept of s i m i l a r i t y has been extended t o these w e l l - o r d e r e d c l a s s e s . Then the f o l l o w i n g theorem i s v a l i d i n NBG; 27. THEOREM 4: Let (A,R) be a w e l l - o r d e r e d c l a s s such t h a t , f o r any a e A, {'x e A : (x,a) e R } i s a s e t . Then (A,R) i s s i m i l a r t o (Z, £ Z) . Proof : Define f as i n Theorem 3; i t i s s u f f i c i e n t t o show th a t f ( A ) = Z . C e r t a i n l y f ( A ) a Z ; assume f ( A ) + Z , and l e t a be the l e a s t o r d i n a l i n Z - f ( A ) . Then o b v i o u s l y f ( A ) <£ a:. But f i s one-to-one, and thus, by the Replacement Axiom, A Is a set. C o n t r a d i c t i o n . Thus f ( A ) = Z . ^ As promised, we now prove the equi v a l e n c e of the def-i n i t i o n s of o r d i n a l s which were l i s t e d In Chapter 2. THEOREM 5s x i s a Zermelo o r d i n a l i f f x i s a von Neumann o r d i n a l . P r o o f : L e t x be a Zermelo o r d i n a l . Then by Lemma 7, x i s w e l i - o r d e r e d by £ x . Now suppose t e x j s i n c e x i s t r a n s i t i v e , t = { a e x : a e t } . Thus t equals i t s c o r r e s -ponding i n i t i a l £x-segment, and so x i s a von Neumann o r d i n a l . Conversely, l e t x be a von Neumann o r d i n a l w i t h R" the s u i t a b l e w e l l - o r d e r i n g on x . x I s o b v i o u s l y t r a n s i t i v e ^ Suppose x has elements which are not Zermelo o r d i n a l s ; l e t y be the s e t of a l l such elements. Then y has an R - f i r s t element t ; o b v i o u s l y t n y . Now i f s € t then s i s a Zermelo o r d i n a l . C l e a r l y t i s t r a n s i t i v e ; thus t i s a Z e r m e l o ' o r d i n a l by Lemma 12. T h i s c o n t r a d i c t s t e y ; thus y = J0 . So x i s a t r a n s i t i v e s e t 6f Zermelo o r d i n a l s , and so, by Lemma 12 a g a i n , x i s a Zermelo o r d i n a l . k 28. THEOREM 6: x I s a Zermelo o r d i n a l i f f x I s a GcJdel o r d i n a l . P r oof; I f x i s a Zermelo o r d i n a l -then x i s t r a n s i t i v e ; •by-Lemma l 6 , every non-empty subset of x i s well-founded; by Lemma 13* every element o f x i s t r a n s i t i v e . Thus x i s a Godel o r d i n a l . Conversely, suppose x i s a Go'dejL o r d i n a l , arid • t suppose x has elements which are not Zermelo o r d i n a l s . L e t y be the s e t of a l l such elements. Since every non-empty sub-s e t o f x i s well-founded, t h e r e i s a t e y such t h a t t n y>= j6 . I f s e t then s e x s i n c e x i s t r a n s i t i v e ; then s i s a Zermelo o r d i n a l , s i n c e t ft y = "p . Since every element of x i s t r a n s i t i v e , t i s a t r a n s i t i v e s e t of Zermelo o r d i n a l s , and so t i s a zermelo o r d i n a l , c o n t r a d i c t i n g t e y Thus y = 0 , arid so x i s a Zermelo o r d i n a l . A THEOREM 7i x i s a Zermelo o r d i n a l i f f x i s a Robinson o r d i n a l . Proof; I f x Is a Zermelo o r d i n a l then, as i n Theorem 6, x i s t r a n s i t i v e and every non-empty subset of x i s well-founded. Now l e t a,b e x w i t h a =f- b ; , then by Lemmas 13 and 8, a e b or b e a . Thus x i s a Robinson o r d i n a l . Conversely, suppose x i s a Robinson o r d i n a l . We show every element of x i s t r a n s i t i v e , from which w i l l f o l l o w t h a t x I s a Godel o r d i n a l , and thus a Zermelo o r d i n a l by Theorem 6. Suppose c e,x , and l e t a e b e c . By the t r a n s i t i v i t y of x , i t f o l l o w s t h a t a e x . Now e i t h e r a e c 29. or c e a or a = c . We cannot have c e a , f o r then the non-empty subset {a,b,c) of x i s not well-founded. We cannot have a = c , for then the non-empty subset (a>b) of x i s not well-founded. Thus a. e c ; so c i s t r a n s i t i v e . Thus x i s a Zermelo ordinal. A THEOREM 8 : x Is a Zermelo o r d i n a l I f f x i s a Bernays ordinal. Proof: I f x i s a Zermelo ordinal then x i s trsthsitlve and, by Lemma 15, every proper t r a n s i t i v e subset of x i s an element of x . Thus x i s a Bernays ordinal. Conversely, suppose x i s a Bernays ordinal. Let y be the set of a l l elements of x which are Zermelo ordinals, and l e t a e b e y . Since x i s t r a n s i t i v e , we have a e x . \ . . . . . . . . .,. . Since elements: of Zermelo ordinals are Zermelo ordinals, we have a € y . Thus• y i s a t r a n s i t i v e set of Zermelo ordinals;, so y i s a Zermelo ordinal. I f y f X , then y e x ; so y e y , a contradiction. Thus y = x , and so x i s a Zermelo ordinal. The following proof must be carried out i n NBG. THEOREM 9°. x i s a Zermelo ord i n a l I f f x i s a Sion and Willmott or d i n a l arid x e Y . Proof: L e t t i n g Z denote the class of a l l the Zermelo ordinals we have, by Lemma 11, I f x e Z then x U {x} e Z ; i f A i s a nest of elements of Z and A e Z , then t)A e Z by Lemma <j . . . '* . 14. Thus l e t t i n g Q denote the class of Sion and Willmott ordinals which are sets (In f a c t Q i s the only Sion and 30. Willmott ordinal which i s not a set), we have Q c Z by the d e f i n i t i o n of Q . We prove Q = Z by t r a n s f i n i t e induction (Theorem 2 ) . Indeed, assume x € Z and f o r every y e x we have y e Q. Case 1; x i s a l i m i t ordinal.-' Then Ux = x , and x being a nest of elements of Q we have x e Q . Case 2; x i s a successor ordinal. Then' Ux U tux} = x . By the Induction-hypothesis, ux e Q , and by the d e f i n i t i o n of Q, Ux U tux] e Q . Thus x e Q and so Q = Z . A 31. CHAPTER 4 : THE CANTOR-RUSSEL ORDINALS AS VIRTUAL CLASSES We devise a means of t a l k i n g about ultimate classes i n ZF without assuming t h e i r existence; thus the Cantor-Russell d e f i n i t i o n of ordinal number-s can be accepted i n that set theory.; A. THE VIRTUAL THEORY OF CLASSES Inconsistencies arize i n ZF by assuming, f o r every predicate F , the existence of { x : F(x) ) , i . e . by assum-ing { x ; F(x) } as being capable of membership. Quine [1] and Bernays and Fraenkel [ l ] describe a theory of classes which does not assume the { x • F(x) } as values of variables by introducing the usually p r i m i t i v e r e l a t i o n e as a defined notion. DEFINITION 1: y e { x ":• F(x) ) < i f f F(y). Here F(y) i s i d e n t i c a l with F(x) , except the former has free y whenever the l a t t e r has free x , and F(x) has no quanti-f i e r capable of binding the y of F(y) . The x i n { x : F(x) } i s a bound variable. We note that i n t h i s eliminable combination, class abstracts occur only after e and e occurs only before class abstracts. Since y e { x ; F(x) ) reduces to F(y) , there i s no reason f o r us to suppose that { x : F(x) ) exists. From t h i s modest beginning, we dan define the usual 32. c l a s s o p e r a t i o n s : A U B , A 0 B , A c B , e t c . , where A and B r e p r e s e n t c l a s s a b s t r a c t s . Moreover, we can Introduce the u n i v e r s a l c l a s s V as { x : x= x } , and the c l a s s o f a l l Zermelo o r d i n a l s , Z . Now orice we admit c l a s s e s as v a l u e s of v a r i a b l e of q u a n t i f i c a t i o n , we are committed t o r e c o g n i z i n g them as r e a l o b j e c t s . Thus once we admit q u a n t i f i c a t i o n of v a r i a b l e s a f t e r € we admit them as r e a l . And f o r ah adequate development of s e t theory, we must q u a n t i f y v a r i a b l e s o c e u r i n g a f t e r e . But then we are f a c e d w i t h a d e c i s i o n : should we i d e n t i f y a c l a s s a b s t r a c t w i t h i t s c o r r e s p o n d i n g s e t ( i . e . b o t h have the same members) when such e x i s t s * or should we keep them apar t ? 1. KEEPING THE REAL THEORY APART PROM THE VIRTUAL. DEFINITION 2: A s B i f f , f o r every x, x € A i f f x e B , where A and B are c l a s s a b s t r a c t s ^ DEFINITION 3s The s e t b r e p r e s e n t s the c l a s s B i f f , f o r every x, x € b I f f x e B . N o t i c e In t h i s d e f i n i t i o n two uses of «e ; the f i r s t , x € b , i s the p r i m i t i v e e., which'the second, x e B , i s the d e f i n e d one. THEOREM 1: Every s e t r e p r e s e n t s a c l a s s and..a c l a s s can be r e p r e s e n t e d by o n l y one s e t i P r o o f : L e t b be a s e t . Then B s { x : x e b } i s r e p r e s -ented by b . Now siippose B I s r e p r e s e n t e d by both b and 55. c . Then f o r every x, x e b i f f x e B , and x e c i f f x e B , and so, f o r every x , x e b i f f x e c ; thus b = c . A Not.every c l a s s i s r e p r e s e n t e d by a s e t . Por example, the c l a s s Z of a l l the Zermelo o r d i n a l s i s not r e p r e s e n t e d by a s e t . DEFINITION V: a* s { x s x e a } . That i s , the c l a s s r e p r e s e n t e d by the s e t a i s denoted by a*. We can how express the r e l a t i o n "a i s a subset of the c l a s s B" by a* c B , and the r e l a t i o n "A i s a s u b c l a s s of the s e t b" by A C b * . The method thus d e s c r i b e d of keeping a p a r t the v i r t u a l t h e o r y from the r e a l I s used i n Berhays and F r a e n k e l [1] t o develop a s e t t h e o r y s i m i l a r t o ZF., 2. THE'VIRTUAL THEORY FUSED WITH THE REAL. We now d e s c r i b e a method of i n d e n t i f y i r i g a c l a s s With its., c o r r e s p o n d i n g s e t when such e x i s t s , f o l l o w i n g Quine [ 1 ] . DEFINITION 5s a = 6 i f f , f o r every x, x € a i f f x e 6 , where a r e p r e s e n t s e i t h e r a v a r i a b l e or a c l a s s , a b s t r a c t . THEOREM 2: a = { x s F ( x ) } i f f , f o r every x, x e a I f f P ( x ) . T h i s f o l l o w s immediately from D e f i n i t i o n s 1 and 5. Thus, 3^. t a k i n g F ( x ) as x e a ', THEOREM 3s a = { x : x e a } . Now comes the c r u c i a l s t e p : DEFINITION 6s { x : F ( x ) } e 0 i f f t h e r e e x i s t s a y such t h a t y = { x : F ( x ) } and y e p . Summarizing, t o a f f i r m membership i n { x : F(x) } i s not t o suggest t h a t { x : F ( x ) } e x i s t s . But to a f f i r m membership on the p a r t of { x : F ( x ) } i s d e f i n i t e l y t o imply t h a t { x : F ( x ) } e x i s t s . Now we can e i t h e r d i s m i s s l a r g e c l a s s e s as v i r t u a l , or we can assume them the s t a t u s of u l t i m a t e c l a s s e s (as we do f o r NBG). We d i s m i s s them as v i r t u a l f o r our c o n s i d e r a t i o n s here (thus r e m a i n i n g i n ZF). B„ VIRTUAL CLASSES AND THE CANTOR-RUSSELL ORDINALS Inasmuch as the C a n t o r - R u s s e l l o r d i n a l s cannot be r e p r e s e n t e d by s e t s , we here need not make the d e c i s i o n as whether t o i d e n t i f y a c l a s s w i t h i t s c o r r e s p o n d i n g s e t when such e x i s t s , or not. DEFINITION 7: a .. I s the o r d i n a l number of ,x i f f x i s a w e l l - o r d e r e d s e t and, f o r every t , t e a i f f t i s s i m i l a r t o x . DEFINITION 8: a i s an o r d i n a l number i f f there e x i s t s a s e t 35. x such t h a t a i s the o r d i n a l number of x . Thus the C a n t o r - R u s s e l l d e f i n i t i o n of o r d i n a l numbers can be accepted i n ZF , the development f o l l o w i n g as i n Chapter 1. But here we n o t i c e t h a t although we have a c t u a l l y d e f i n e d p r d i n a l numbers, these o r d i n a l s do not e x i s t s .' Our v i r t u a l t h e o r y of c l a s s e s l e a d s us t o another c o n s i d e r a t i o n , t h i s time i n v o l v i n g NBG. In t h i s s e t theory, we o b j e c t e d t o the C a n t o r - R u s s e l l o r d i n a l s because we were unable t o t a l k o f c l a s s e s o f these o r d i n a l s . Now w i t h the v i r t u a l t h e o r y e s t a b l i s h e d , t h i s o b j e c t i o n can be e l i m i n a t e d , s i n c e the C a n t o r - R u s s e l l o r d i n a l s do e x i s t i n NBG. However, c l a s s e s of these o r d i n a l s w i l l remain f o r e v e r v i r t u a l i n t h a t theory. 36. CHAPTER 5 : APPROACHES TO ORDINAL NUMBERS VTA RANK We possess y e t another method of s a l v a g i n g a t l e a s t p a r t of the s p i r i t o f the C a n t o r - R u s s e l l d e f i n i t i o n o f o r d i n a l numbers i n ZF . T h i s method c o n s i s t s i n condensing those e q u i v a l e n c e c l a s s e s t o s e t s . C o n s i d e r a b l e ease i n the f o r m u l a t i o n i s c o n t r i b u t e d by the v i r t u a l t h e o r y o f c l a s s e s j we assume t h a t theory, , i d e n t i f y i n g a c l a s s w i t h I t s cor r e s p o n d i n g s e t when such e x i s t s . A. THE; NOTION OP RANK OF A SET S c o t t [1] i n t r o d u c e s a f u n c t i o n • d e f i n e d by r e c u r s -i o n on the Zermelo o r d i n a l s : t ( a ) - U sb*(p) , 0<a where < I s the n a t u r a l order f o r the o r d i n a l s , and sb$(0) i s the s e t of a l l subsets o f fr(P) •• Denoting the c l a s s o f a l l the Zermelo o r d i n a l s by Z , we d e f i n e H = U $(a) . aeZ Thus i f • x e H , the r e e x i s t s an o r d i n a l a such t h a t x c %(a) ; by v i r t u e of the w e l l - o r d e r i n g o f the o r d i n a l s , the f o l l o w i n g Is w e l l - d e f i n e d : DEFINITION 1: For x e H , the rank of x , denoted by p ( x ) , i s the l e a s t o r d i n a l a such t h a t x c «(a) . "37. Many authors* n o t a b l y Bernays [2] and Mendelson [ 1 ] , d e f i n e the rank of x as the l e a s t o r d i n a l a such t h a t x e ty(a) . But then the rank o f every s e t i s a successor o r d i n a l , and so we would not be able t o propose the d e f i n i t i o n of o r d i n a l s i n P a r t B nor the r e c u r s i v e d e f i n i t i o n o f rank i n P a r t C We now examine some i n t e r e s t i n g p r o p e r t i e s of t h i s h l e r a c h y . LEMMA 1: I f a i s an o r d i n a l then $(a) 'c H . LEMMA 2: I f x e H then x c H . Proof? By D e f i n i t i o n 1, x £ $ ( p ( x ) ) . By Lemma 1, t ( p ( x ) ) c H ( . A LEMMA 3: I f y*x € H and y e x then p ( y ) < p(x)... Proofs Since- x c . $ ( p ( x ) ) , y e f ( p ( x ) ) . Thus y e sb$(a) f o r some a < p(x) , and so y c i ( a ) f o r some a < p ( x ) . T h e r e f o r e p(y) _< a < p ( x ) . A LEMMA 4s I f y e V and y ;c.'H then y e H . Proof : L e t a = { p ( t ) s t e y } : a i s a s e t of o r d i n a l s by the Axiom of Replacement, and thus Ua i s an o r d i n a l . L e t 6 = Ua U tua} . Then for' every t £ y , p ( t ) < j3 , and so t e . Thus y a f(£) r , i m p l y i n g y e U {3} ) £ H. A . For the f o l l o w i n g theorem, we s h a l l need the Axiom of R e g u l a r i t y . We r e s t a t e i t i n a s l i g h t l y strengthened form: J58. i f A 4= 0» then t h e r e e x i s t s a y e A such t h a t y n A - 0 . Here A r e p r e s e n t s e i t h e r a s e t or a c l a s s . THEOREM Is The Axiom of R e g u l a r i t y Is e q u i v a l e n t t o the a s s e r t -i o n t h a t V = H . Proof : Mendelsdn [ l ] : Assume V = H and l e t 0 + A c V . Let a be the l e a s t of the ranks o f a l l the members of A , and l e t y e A such t h a t p(y) = a . Then y fl A - 0 ; f o r i f t h e r e i s a t € y d A , then, by Lemma 3 , p(t) < p(y) con-t r a d i c t i n g the m i n i m a l i t y of a . Conversely, assume the Axiom o f R e g u l a r i t y , and suppose ( V - H) 0 . Then, by t h a t axiom, there i s a y e (V - H) such t h a t y rY (V - H) = 0 . Thus y c H , and by Lemma 4, y e H , a ' c o n t r a d i c t i o n . Thus V = H . A Theorem 1 i n c r e a s e s the a t t r a c t i v e n e s s of assuming the Axiom of R e g u l a r i t y ; we, make t h i s assumption f o r the remainder o f t h i s chapter o n l y . Thus the n o t i o n of rank i s extended, t o a l l s e t s . B„; A DEFINITION OF ORDINALS EQUIVALENT TO ZERMELO'S We show t h a t the Zermelo o r d i n a l s are e x a c t l y those s e t s x w i t h the p r o p e r t y p(x) ^  x . LEMMA 1: I f a Is a Zermelo o r d i n a l then p(a) = a . 59. P r o o f : By i n d u c t i o n on a (Theorem 2, Chapter.3)- Suppose t h a t f o r every a < 8 we have p(a) = a . Then, f o r every a e p , we have a e sb$(a) c *(P); thus P£ $ (B ) . Now assume t h a t p (p ) 4 3 ; then B e $(a) f o r some a < B . Then p(a) < PO) _< a = p(.a) , a c o n t r a d i c t i o n . -Thus p (B ) = B . T h e r e f o r e , f o r every o r d i n a l a, p(a) = a . 4 Since p(x) i s , by d e f i n i t i o n , ah o r d i n a l , we now o b v i o u s l y have THEOREM 2: A s e t x i s an o r d i n a l number i f f p(x) = x . C. A REVISED CANTOR-RUSSELL DEFINITION For a n o n - t r i v i a l p r o p e r t y o f s e t s there Is always at l e a s t one s e t of the s m a l l e s t rank among a l l such s e t s , and the c o l l e c t i o n o f a l l such s e t s of s m a l l e s t rank forms a s e t . Thus, l e t t i n g <B,S> r e p r e s e n t ordered s e t s , and de n o t i n g as u s u a l the s i m i l a r i t y d e l a t i o n by « , we d e f i n e : \(<A,P>) = C <M,Q> : <M,Q> « <A,P> and f o r a l l <N,R>, i f <A,P> « <N,R> then p(M) < p (U) }. That i s , X(<A,P>) i s the c l a s s of a l l ordered s e t s of the l e a s t rank which are s i m i l a r t o <A,P>. We o b v i o u s l y have: ( i ) \(<A,P>) i s a s e t ; ( I I ) \ ( <A , P > ) * 0 ; ( i i i ) <M,Q> e \(<A,P>) i m p l i e s <M,Q> « <A,P>; ( i v ) \(<A,P>) = \(<M,Q>) i f f <A,P> « <M,Q> . 40. Thus \(<A,P>) may be taken a s J a n adequate approximation t o the n o t i o n of Cantor-Russell o r d i n a l . U n f o r t u n a t e l y , we have made use of the Zermelo o r d i n a l s , i n the d e f i n i t i o n of rank, In order t o d e f i n e these r e v i s e d C a n t o r - R u s s e l l o r d i n a l s . We now show how t h i s o b j e c t i o n can be e l i m i n a t e d . A new n o t i o n i s needed: DEFINITION 2: The t r a n s i t i v e c l o s u r e of the s e t x , denoted by T ( x ) , i s the s e t x u l)x u'utJx U UUUx ... T a r s k i [ l ] d e f i n e s by r e c u r s i o n a new f u n c t i o n ? on V: ?(x) = { y : there e x i s t s a z e T(x) w i t h y = f ( z ) } . We s h a l l prove 1 t h a t ?(x) i s . j u s t the rank of x . LEMMA 1: ?(x) i s t r a n s t i t i v e . J P r o o f : L et s e t e §(x). Then th e r e i s a z e T(x) such 1 t h a t t ='§(z), and there e x i s t s a w € T ( z ) such t h a t s * ?(w). But i f ,w € T ( z ) then o b v i o u s l y w € T ( x ) ; thus s € §(x), i and so ?(x) i s t r a n s i t i v e . A LEMMA 2: p(T(x)') _< p ( x ) . P r o o f : L e t a = p ( x ) ; i f s € T ( x ) , then, by repe a t e d use of Lemma 3, P a r t A, we have p ( s ) < p(x) = a . Thus s € $(a) by Lemma 2, P a r t A, and so T(x) c ty(a). T h e r e f o r e , by the d e f i n -i t i o n o f rank, p ( T ( x ) ) <a = p ( x ) . A THEOREM 3>: I f x € V then p(x) = | ( x ) . 41. Proof: By i n d u c t i o n (Theorem 2, Chapter 3) on the rank o f x. Le t p(x) = p , and suppose p(y) = ?(y) f o r every s e t y w i t h p(y) < P . I f t e ? ( x ) , then, by the d e f i n i t i o n of ? ( x ) , t h e r e e x i s t s a z e T(x) such t h a t t = ? ( z ) . By Lemma 3 / P a r t A, p ( z ) < p ( T ( x ) ) , and by Lemma 2 above, p ( T ( x ) ) < p ( x ) ; thus p ( z ) < p ( x ) , and then, by the i n d u c t i o n h y p o t h e s i s , p ( z ) = ? ( z ) . Thus § ( z ) i s an o r d i n a l , and so t = § ( z ) e p ; thus § ( x ) c . p • Assume ?(x) + P 5 s i n c e §(x) i s t r a n s - . i t i v e by Lemma 1, and s i n c e the elements o f §(x) are o r d i n a l s , then §(x) i s an o r d i n a l ; thus ?(x) e 8. Then by the I n d u c t i o n h y p o t h e s i s p(x) = §(x) < p = p ( x ) , a c o r i t r a d i c t i o n . Thus ?(x') = 0 = p ( x ) . T h e r e f o r e ?(x) = p(x) f o r a i l s e t s x. A We can now d e f i n e X(<A,P>) without r e f e r r i n g t o the Zermelo o r d i n a l s by r e p l a c i n g p ( M ) _< p ( N ) by ? ( M ) € ? ( N ) or |(M) « ? ( N ) . . 42. CHAPTER 6 : "PEANO AXIOMS" FOR THE ORDINALS" By a p r o c e s s of a b s t r a c t i n g from the elements of w e l l -ordered s e t s but r e t a i n i n g the order o f precedence among those elements, we a r r i v e d at the Zermelo o r d i n a l s . We now c a r r y the a b s t r a c t i o n even f u r t h e r . Before we e x p l a i n t h i s , l e t us again c o n s i d e r our concern f o r d e f i n i n g o r d i n a l numbers. We wished t o have a standard c l a s s of w e l l - o r d e r e d s e t s t o which we co u l d r e f e r i n order t o c h a r a c t e r i z e the o r d i n a l types of other w e l l -ordered s e t s . But c e r t a i n l y the f o l l o w i n g would be adequate: a w e l l - o r d e r e d c l a s s of " o b j e c t s " w i t h the p r o p e r t y t h a t any . w e l l - o r d e r e d s e t c o u l d be put i n t o a one-to-one, o r d e r - p r e s e r v i n g correspondence w i t h a l l the members of t h i s c l a s s which are l e s s than some unique member. (With the c l a s s o f a l l Zermelo o r d i n a l s , we have b o t h the standard c l a s s of w e l l - o r d e r e d s e t s and the w e l l - o r d e r e d c l a s s o f o b j e c t s w i t h the mentioned prop-e r t y . ) With t h i s c o n s i d e r a t i o n i n mind, we conclude t h a t i t i s not e s s e n t i a l f o r the o b j e c t s o f t h i s w e l l - o r d e r e d c l a s s t o be w e l l - 6 r d e r e d s e t s ; i t i s not necessary t o even know a n y t h i n g about them except the e x i s t e n c e o f a w e l l - o r d e r i n g among them. I t I s t o t h i s end t h a t we c a r r y our a b s t r a c t i o n . But how i s t h i s l e v e l of a b s t r a c t i o n t o be achieved ? A p r i m i t i v e (undefined) g e n e r a t i o n - f u n c t i o n f o r c o n s t r u c t i n g h i g h e r o r d i n a l s from l e s s e r ones i s s u f f i c i e n t . A c c e p t i n g t h i s p o s i t i o n , we now r e q u i r e axioms t o ensure t h i s p r i m i t i v e , f u n c t i o n ' s adequacy; we for m u l a t e a g e n e r a l i z a t i o n of Peaho's axioms f o r the n a t u r a l numbers. Such a choice i s determined 43. by the use of o n l y one p r i m i t i v e g e n e r a t i o n - f u n c t i o n i n both Peano's development and ours, and by the s i m p l i c i t y and i n t u i t -i v e n e s s of the axioms and the n a t u r a l development i t p r o v i d e s f o r b o t h t h e o r i e s . I t might appear t h a t the use of o n l y one f u n c t i o n t o generate the o r d i n a l s would be i n s u f f i c i e n t t o o b t a i n b o t h successor and l i m i t o r d i n a l s , but Peario does h o t r e a c h the t r a n s f i n i t e o n l y because he d e f i n e s h i s successor f u n c t i o n on n a t u r a l numbers; we d e f i n e our f u n c t i o n on s e t s of o r d i n a l s and thus we o b t a i n a l l the c l a s s i c a l t r a n s f i n i t e o r d i n a l s . Thus, as we s h a l l l a t e r see, by a p p l y i n g our f u n c t -i o n on s e t s of o r d i n a l s w i t h " l a s t " 1 elements ( i n the w e l l -o r d e r i n g t o be e s t a b l i s h e d ) we o b t a i n the analogue of the u s u a l successor o r d i n a l ; by a p p l y i n g our f u n c t i o n on s e t s of o r d i n a l s w i t h no " l a s t " elements, we o b t a i n the analogue of the l i m i t o r d i n a l . Thus the Zermelo o r d i n a l s w i l l be a model of our axiom system. Obviously, we cannot work independently of some th e o r y of s e t s ; we choose NBG i n which t o c a r r y out our development s i n c e we must q u a l i f y over u l t i m a t e c l a s s e s . In a d d i t i o n , we co u l d modify the axioms of NBG, as i n Mostowski [ 1 ] , t o a l l o w f o r the e x i s t e n c e o f I n d i v i d u a l s ( o b j e c t s c o n t a i n i n g no elements), i n which case we would not be a b l e t o say whether our o r d i n a l s were s e t s or not; they would not be u l t i m a t e c l a s s e s . Here, we do not accept t h i s o p t i o n . 44. A. THE AXIOMS In the f o l l o w i n g , Q denotes our c l a s s of o r d i n a l s t o be d e f i n e d , 0 i s a * p r i m i t i v e constant, and ' denotes our p r i m i t i v e g e n e r a t o r - f u n c t i o n . We w i l l o b v i o u s l y have Q £ V . DEFINITION Is G = Cl{ A s {0} e A, and i f a e A then a U {a 1 }•-,e A> and i f F c A and F e V then UF e A } . In other words, G i s the smailes c l a s s which s a t i s f i e s the mentioned c o n d i t i o n s . G i s w e l l - d e f i n e d s i n c e V a t l e a s t s a t i s f i e s those c o n d i t i o n s . AXIOM Is 0 e Q ."• AXIOM 2: I f a e G then a' € Q . AXIOM 3s I f a € G then a' + 0 . AXIOM 4 : I f a,b € G and a' = b» , then a = b . AXIOM 5: I f P C and i f 0 e P , and I f a e G i m p l i e s a' c P, then P * Q . -Axiom 5 i s a s i n g l e axiom as compared w i t h Peaho's Axiom of I n d u c t i o n , which i s an axiom schema. But here we can assume t h a t P e x i s t s by Axioms 1-4 and the other axioms of s e t theory. We now p r e s e n t some i n t u i t i v e models t o show the independence of our axioms. METATHEOREM Is Axioms 1-5 are independent. Proofs Since 0 i s a p r i m i t i v e constant, Axiom 1 i s o b v i o u s l y 45. independent from the o t h e r s . Axiom 2 i s independent, f o r the other axioms h o l d t r i v i a l l y f o r the model i n which Q = {0} . I f we propose a' = 0 f o r e v e r y <?a e G , then a l l the axioms except Axiom 3 are s a t i s f i e d " ; t h u s ? t h i s axiom i s .independent. D e f i n i n g a* = {0} f o r every a e G shows the independence of Axiom 4. I f we take Q* t o be Q u i (q**) : q e Q } , where • i s some I d e a l p o i n t , then Q* i s a model of Axioms 1-4 but does not s a t i s f y Axiom 5* thus showing the independence of t h a t axiom. A N o t i c e t h a t we c o u l d d e f i n e 0 = 0' , i n c l u d i n g jt) € G; t h i s would much s i m p l i f y our system. However, Axioms 1 and 3 would then be redundant. B. THE WELL-ORDERING OF THE ORDINALS LEMMA 1? I f q s Q and q + 0 > then t h e r e e x i s t s a unique a 6 G such t h a t q = a r . Proof: L e t P = (0) U { q. € Q : t h e r e e x i s t s an a e G w i t h a' = q } . I f b e G then c e r t a i n l y b' € P Thus P = Q by Axiom 5. Uniqueness f o l l o w s by Axiom 4. ' A DEFINITION 2: I f q e Q and q + 0 , we d e f i n e q* to be the unique a e.^Arsuch^fthat C iq = a' . We extend t h i s f u n c t i o n by c o n v e n i e n t l y d^ I n i r i g l J K O * = j& {although we do not n e c e s s a r i l y have 0 = 0' We now prove a s e r i e s of lemmas t o show t h a t G i s w e l l - o r d e r e d by i n c l u s i o n . 46. LEMMA 2: I f ft c G such that ( i ) {0} € ft, arid ( i i ) i f a € © then a u {a'} e ft, and ( i i i ) i f P c i and P € V then UP € 8 ,: then - ft = G . Proof; If ft s a t i s f i e s : ( ! ) - ( i l l ) then G £ ft by D e f i n i t i o n l j t h u s f t = G . 4 LEMMA .3:' I f a € G and t e a then t * c a . Proof: Let ft = [ a 4 G s i f t e a then t * c a } • Then (0) e ft since 0* = j& c [0] . Now suppose a € ft 'and l e t t € a u (a') ... I f t e a then, by hypothesis, t * c a c a u {a'} . I f t = a' then t * = (a ' ) * = a . But a c a u [a ' 3 , f o r i f a = a u {a '3 , then a' e a, implying by hypothesis that a c a , which Is a contradiction. Tlius a u {a'3 e ft . Now "suppose F c ft and P e V . I f t e UP , then t e a f o r some a e P ; thus t * c a e UP, implying UP e ft . Therefore ft = G by Lemma 2. & LEMMA 4: I f a e G arid t e a, then t + a' . Proof: I f t e a then t * c a by Lemma 3 . If t = a', then t * = ( a ' ) * = a by Axiom 4, which i s a contradiction. Thus t + a' . t LEMMA 5: I f a'e G then a' 4 a. Proof: I f a' e a then a' 4 a ' hy Lemma 4. Contradiction. LEMMA 6: I f a,be G and a c b u {b '3, then a < b . Proof: Suppose a = c u {b'3 where c c b . Since then 47. b 1 € a b c a by Lemma 3. Since b' 4 & , we have b e c , c o n t r a d i c t i o n c c b . Thus a c b . • A LEMMA 7 : I f a e G then {0} c a . LEMMA 8s I f - a,b e G and b c a., then b' € a . Proofs L e t fi = { a s C : i f b € G and b c a then b' e. a }. The p r o o f proceeds by two a p p l i c a t i o n s of Lemma 2 ; we f i r s t show t h a t the elements of fl are comparable w i t h the elements of G i and then we show t h a t fl = G . Let 3 - [ b c G ! i f a e fl then a c b or b c a 3 • Then {0} e 3 by Lemma 7 . Now suppose b e 3 and l e t a e fl; then a c b or b c a by h y p o t h e s i s . I f a c b then a c b u {b'3; i f b c a then b'! e a by the d e f i n i t i o n of fl , and so b u £b *} c a . Thus b u [b'3 e 3 . Now suppdse P c 3 and l e t a € fl . I f c € F e i t h e r a c c or c c a . I f c c a f o r every c € F then u P c a . I f a c c f o r some c e F then a c c c yp . Thus UF € 3 . Th e r e f o r e 3 = G by Lemma 2 . We now show fl = G . {03 e fl i s va c u o u s l y s a t i s f i e d . Suppose a' e fl s and l e t b e G w i t h b c a U (a 13; then b e a by Lemma 6. I f b = a then b 1 = a 1 e a U a t a H ; ' : i f b c a. then b' e a by h y p o t h e s i s . Thus a u {a'3 € fl . Suppose now F e e and F e V ; l e t b e G w i t h b c UF . We have shown t h a t f o r every c e F e i t h e r c c b or b e c . If> f o r every c € F , we have c e b then UF c b 9 which c o n t r a d i c t s b e UP . 48. Thus t h e r e must he a c e F w i t h h e c . Then b' e c c OP » and so uF e B . Th e r e f o r e B = G hy Lemma 2. A LEMMA 9' I f d c Q and d € V such t h a t ( i ) 0 e d, and ( i i ) i f b e G and b e d then b' € d , and ( i i i ) i f t e d then t * c d , then d e G . • Proofs L et a = u{ t * s t e d } . I f a•» 0 then d = {0} e G. Now suppose a 4 1 then a e G and a c d . I f we have a = d then d e G. I f a c d then a' e d by ( I i ) ; thus a U {a') e d . We show d c a u {a'} . Suppose t e d. I f t = 0 then t e a u {a'} ; i f t 4 0 then t i c a . For t * = a we have t = a' e a u {a 1}. For t * c a we have t e a . Thus d c a U {a 1} t and so d = a U (a') e G . A The f o l l o w i n g lemma e s s e n t i a l l y s t a t e s t h a t G i s w e l l - ordered by i n c l u s i o n . LEMMA 10: I f B c G and B | )5 , then flB e B . Proof : .(IB £ G by Lemma 9 • A l s o flB c a f o r every a e B. Suppose DS 4 a f°r every a e B ; then (OB)' e a f o r every a e. B by Lemma 8. T h e r e f o r e (flB)' e OB , a c o n t r a -d i c t i o n . Thus HB = a f o r some a e B . A t We are now prepared t o give the w e l l - o r d e r i n g f o r Q. DEFINITION 3: < = { (a,b) : a,b e Q and a* c b* } . THEOREM 1: Q i s w e l l - o r d e r e d by < . Proof : C e r t a i n l y < Is I r r e f l e x i v e and t r a n s i t i v e . To show 49. < i s connected l e t a,b e Q w i t h a f t . By Lemma 10, a* n b* € {a*,b*} ; thus a* c b * or b * c a* , and so a < b or b < a . Thus < i s an o r d e r i n g r e l a t i o n . To show < i s w e l l - o r d e r i n g r e l a t i o n , l e t f f P c Q . I f O.e P then 0 i s .the < - f i r s t element i n P s i n c e 0* f6 .. I f 0 £ P, l e t F = { p.* s p e P } . Then, F c G and F + jb . By Lemma 10, OF e F ; thus (fiF ) ' e P , and (OF) 1 I s the < - f i r s t element i n P. A To be abl e t o index any w e l l - o r d e r e d s e t w i t h the elements o f Q , we should c e r t a i n l y expect the f o l l o w i n g : THEOREM 2: Q i s not a s e t . Proof: Suppose Q e V . Then by Lemma 9, Q e G . By Axiom 2 we then have ©J e Q , c o n t r a d i c t i n g Lemma 5. Thus Q f 7. A c t u a l l y , Theorem 2 i s a c o r o l l a r y t o Theorem 3 f o l l o w i n g , u s i n g the Axiom of Replacement. We have i n c l u d e d i t here t o remain in d e p e n d e n t l y of the Zermelo O r d i n a l s . C. COMPARISON TO THE ZERMELO ORDINALS THEOREM >: (Q,<) i s s i m i l a r t o (Z, £ Z ) . Proof: Define f : Z - Q by f(0) = 0 and f ( a ) = { f ( t ) : t € a }'" f o r a =j= 0 • W e show f i s a s i m i l a r i t y mapping between (Q,<) and (Z, eZ). (1) f i s w e l l - d e f i n e d , i . e . f ( a ) € Q f o r every a e Z . T h i s i s o b v i o u s l y e q u i v a l e n t t o showing t h a t 50. g(a) = { f ( t ) t t e a } e G f o r every a e Z - [j6] ; we use i n d u c t i o n on Z (Theorem 1,, Chapter 3). g( 10}) = m {0} e G . Suppose now g(a) e G ; then g(a U [a]) = { f ( t ) : t e a } U {f(a)} = g(a) U (g(a)'} e G . L e t 0 be a l i m i t o r d i n a l such t h a t g(a) e 6 f o r every a € 0 . Then g ( 0 ) { f ( t ) i t e U0 3 = U{ g ( t ) : t e 0 } e G . Thus g(a) e G f o r every a e Z - [j6] , and so f i s w e l l - d e f i n e d . (2) f i s onto Q . By Lemma 2, we e a s i l y prove { g(a) : a e.Z - {0} } = G . Thus f i s onto Q by Axiom 5, s i n c e f ( a ) = g ( a ) ' . (3) f i s one-to-one. Suppose a,0 e Z and ; ; f ( a ) = f ( 0 ) ; then g(a) = f ( a ) * = f ( 0 ) * = g ( 0 ) . I f a + 0 we may assume a e 0 . Then f ( a ) e g ( 0 ) , Implying g ( a ) ' e g(a) y c o n t r a d i c t i n g Lemma 5. Thus a = 0 » and so f i s one-to-one. ( 4 ) f i s or d e r - p r e s e r v i n g s L et a,0 e Z and suppose a e 0 ; then f ( a ) e g ( 0 ) = f ( 0 ) * . Thus - ; f ( a ) * c f ( 0 ) * by Lemma 3, and thus f ( a ) < f ( 0 ) . Conversely, suppose a,0 e Z and f ( a ) < f ( 0 ) . Then we cannot have a = 0 , f o r then f ( a ) = f ( 0 ) s i n c e f i s one-to-one. And we cannot have 0 e a , f o r we have shown then t h a t f ( 0 ) < f ( a ) . Thus we must have a e 0 , and so f i s o r d e r - p r e s e r v i n g . A N o t i c e t h a t we cou l d have used the above s i m i l a r i t y mapping t o d e f i n e the w e l l - o r d e r i n g < on Q ; but again we p r e f e r r e d t o develop these o r d i n a l s independently of the Zermelo 51. o r d i n a l s . L e t us a l s o n o t i c e t h a t i f we d e f i n e our 'generator-f u n c t i o n as f o l l o w s : ( i ) 0 = and ( i i ) i f a e G then (a u {a'}' = a t ] {a'} / a n d ( i i i ) i f F c G and F e y then (U F ) 1 = U l a' : a e F } , then Q = Z > showing t h a t : METATHEOREM 2: The Zermelo o r d i n a l s are a model of pur axiom system. Inasmuch as bur g e n e r a t o r - f u n c t i o n i s p r i m i t i v e , we cannot s t a t e any r e l a t i o n s h i p o f membership or i n c l u s i o n between our o r d i n a l s . Furthermore, i f the axioms of NBG were m o d i f i e d t o a l l o w f o r the e x i s t e n c e of i n d i v i d u a l s , we would hot even -v know i f our o r d i n a l s would be s e t s or i n d i v i d u a l s ; . they would not be u l t i m a t e c l a s s e s . But we b e l i e v e t h a t we have succeeded i n a b s t r a c t i n g those p r o p e r t i e s of the Zermelo o r d i n a l s which are " r e a l l y o r d i n a l " , i . e . : THEOREM 4: Any w e l l - o r d e r e d s e t i s s i m i l a r t o the s e t of a l l the members of Q l e s s than some unique q e Q . The p r o o f f o l l o w s immediately from Theorem 3 above and from Theorem 3 of Chapter 3. Moreover, from Metathebrem 2 above and from Theorem 4 of Chapter 3» we o b t a i n : METATHEOREM 3: I f P i s an u l t i m a t e c l a s s w e l l - o r d e r e d by % such t h a t , f o r every p e P , { x e P : x K p ) e V , then (VjO ~) i s a model of our axiom system, where _0 i s the l e a s t member of P y and p i s d e f i n e d as the l e a s t member of not i n { x c P : x K p or x = p ] BIBLIOGRAPHY 53-The f o l l o w i n g a b b r e v i a t i o n s are used: AMM = American Mathematical'Monthly; BAMS•= B u l l e t i n , American Mathematical S o c i e t y ; FM = Fundamenta Mathematicae; JSL = Journal-of Symbolic Logic. BACBMANN, H. [1] T r a n s f i n i t e Zahlen. B e r l i n - G o t t i n g e n - H e i d e i b e r g , S p r l n g e r - y e r l a g , 1955, 204 pp. BERNAYS, P. [ 1 ] A System of', Axiomatic Set Theory> P a r t I I . JSL, V o l . 6, 19^1, pp. 1 - 17. [2] I b i d . , P a r t VI. JSL, V o l . 13, 1948, pp. 65 - 79-BERNAYS, P. and FRAENKEL, A. A. , [ l ] Axiomatic Set Theory. Amsterdam, North-Holland, 1958, 226 pp. B E r a , E , w . [1] The Foundations of Mathematics. Amsterdam^ Ho l l a n d , 1959. (2nd E d i t i o n , ^ CANTOR, G. [1] C o n t r i b u t i o n s t o the Founding of the Theory of Trans-f i n i t e Numbers. Tra n s l a t e d by P.E^B. ;JourdaIn> Chicago, Open Court, 1915. (Reprinted, New York, Dover, 208 pp.) .54. FRAENKEL,- A. A. [1] A b s t r a c t Set Theory. Amsterdam, North-Holland, 1953. (2nd E d i t i o n , r e v i s e d , 1961, 295 pp.) PRAENKEL, A.A. and BAR-HILLEL, Y. [1 ]',; Foundations of Set Theory. j^B€^rAim,',^&r%h:--H o l l a n d , 1958> 415 pp. GODEL, K. [ l ] The Consistency of the Contihuum Hypothesis. Annals of Math. Studies* # 3. P r i h c e t b h , P r i n c e t o n U n i v e r s i t y Press, 1940. (2nd E d i t i o n , r e v i s e d , 1951* 69 pp.) . XSBELL, J i R . [1] = A D e f i n i t i o n of O r d i n a l N i t e r s . • AMM* V o l . 67, I960, pp. 51 - 52, [1] I n t r o d u c t i o n t o Mathematical Logic. P r i n c e t o n , van! ^ostrand> 1964* 3Q0 pp. MOSTOWSKE, A. [ l ] tJber d i e Unabhangigkeit des Wohlordnungsatzes vom Ordnunsprinzip. FM, V o l . 47* 1939* pp. 219 - 242. von. NEUMANN, J . [1] Zur Eihfuhrung der t r a n s f i n i t e n Zahlen. Acta Szeged, V o l . 1, 1923, pp. 199 - 208. 55. QUINE, W.V. [ l ] Set Theory and i t s Logic. Cambridge,"Mass., Harvard U n i v e r s i t y Press, 1963, 359 pp. ROBINSON, R,M. [ l ] The Theory of Cl a s s e s , a M o d i f i c a t i o n o f von Neumann System. JSL, V o l , 2, 1937* pp. 29 - 36. SCOTT, D. [ l ] The Notion of Rank i n Set Theory. "jSummerclristltute f o r Symbolic L o g i c , Summaries, ;Cpr;nell;:'ltoiv0r"&ityV : ;.1957* pp. 267 - 269. SIERPINSKI, W. [1] C a r d i n a l and O r d i n a l Numbers. Warszawa, 1958, 487 pp. SION, M. and WILLMOTT, R. [1] On a D e f i n i t i o n of O r d i n a l Numbers. AMM, V o l . 69, 1962, pp. 381 - 386. SKOLEM, Th. A. [1] A b s t r a c t Set Theory. Notre Dame, 1962, 70 pp. STEIN, S.K. [1] P u l l Classes and O r d i n a l s . JSL, V o l . 25, i960, pp. 217 - 219. SUPPES, P. [ l ] Axiomatic Set Theory. P r i n c e t o n , vah N^bstrand, i 9 6 0 , 265 pp. 56. TARSKE, A. [1] The Notion of Rank i n Axiomatic Set Theory and some of i t s '-Applications'.'' BAMS., Vol. 6 l , 1955. - 'py.. abstract). • WHITEHEAD, A.N. and RUSSELL, B. [1] P r i n c i p i a Mathematica. Cambridge, England, Cambridge University Press, Vol I, 1910, 666 pp.; Vol. II, 1912, 772 pp.; Vol. 111,1913, 491 pp. 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0080598/manifest

Comment

Related Items