UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

On some definitions of a finite set Gutteridge, Lance 1969

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

Item Metadata

Download

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

Full Text

ON SOME DEFINITIONS OF A FINITE SET by LANCE GUTTERIDGE B . S c , U n i v e r s i t y of B r i t i s h Columbia, 1967 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE i n the Department of MATHEMATICS We accept t h i s t h e s i s as conforming to the r e q u i r e d standard THE UNIVERSITY OF BRITISH COLUMBIA August, 1969 In presenting th i s thes i s in pa r t i a l f u l f i lment of the requirements fo r an advanced degree at the Un ivers i ty of B r i t i s h Columbia, I agree that the L ibrary sha l l make i t f ree l y ava i l ab le for reference and study. I fur ther agree tha permission for extensive copying of th i s thes is for scho lar ly purposes may be granted by the Head of my Department or by his representat ives. It is understood that copying or pub l i ca t ion of th i s thes is f o r f i nanc ia l gain sha l l not be allowed without my wr i t ten permission. Department of The Univers i ty of B r i t i s h Columbia Vancouver 8, Canada Date ^tyCy^t/TrdoC^ i i ABSTRACT S i x d e f i n i t i o n s o f a f i n i t e s e t a r e s t u d i e d ; and each i m p l i c a t i o n between the d e f i n i t i o n s i s shown t o be e i t h e r d e r i v a b l e f r o m the Z e r m e l o - P r a e n k e l axioms o r i n d e -pendent of them. The method of B o o l e a n - v a l u e d models, as s t u d i e d by D. S c o t t , i s used t o show t h a t i t i s c o n s i s t e n t w i t h the Z e r m e l o - F r a e n k e l axioms t o deny some of t h e s e i m p l i c a t i o n s by c o n s t r u c t i n g a p p r o p r i a t e models. The s i x d e f i n i t i o n s a r e shown t o s a t i s f y a l i s t o f p r o p e r t i e s which a d e f i n i t i o n o f f i n i t e s h o u l d r e a s o n a b l y p o s s e s s . I t i s a l s o shown t h a t any d e f i n i t i o n w hich s a t i s f i e s t h e s e p r o p e r t i e s must encompass a l a r g e r c l a s s o f s e t s than the f i r s t d e f i n i t i o n and a s m a l l e r c l a s s than the s i x t h . Three more d e f i n i t i o n s , w hich do not p o s s e s s t h e s e p r o p e r t i e s , a r e mentioned, and the d i f f e r e n c e s between t h e s e d e f i n i t i o n s and the f i r s t s i x a r e d i s c u s s e d . i i i TABLE OP CONTENTS Page CHAPTER 1 - PRELIMINARY 1 . 1 I n t r o d u c t i o n 1 1.2 Axioms of Set Theory 1 1.3 Ordered P a i r s , O r d e r i n g s , and O r d i n a l s . . . . 3 1.4 Boolean Algebras . . 5 CHAPTER 2 - DEFINITIONS OF FINITE 2 . 1 I n t r o d u c t i o n . . . 8 2 . 2 D e f i n i t i o n s 9 2 . 3 Some E q u i v a l e n t D e f i n i t i o n s . . . . . . . . . 1 1 2.4 I m p l i c a t i o n s between the D e f i n i t i o n s . . . . . 1 8 2 . 5 P r o p e r t i e s of the D e f i n i t i o n s . 24 2 . 6 Some R e s u l t s Concerning a C l a s s of D e f i n i t o n s 2 6 CHAPTER 3 - BOOLEAN VALUED MODELS 3 . 1 I n t r o d u c t i o n 2 9 3.2 The Universe V ^ 3 0 3 « 3 A s s i g n i n g Boolean Values to Sentences 3 1 3. 4 Automorphisms of S V ^ ) 3 7 3 . 5 Subsystems of the Type V ^ 4 3 3 . 6 Embedding the Standard U n i v e r s e V 4 5 3 . 7 j 3 - V a l i d i t y of the Axioms of Set Theory . . . 4 7 3.8 A Model f o r Sentences'/3-Valid i n . . . 5 4 CHAPTER 4 - THREE MODELS OF SET THEORY 4 . 1 I n t r o d u c t i o n 6 2 4.2 General Remarks 6 2 4 . 3 Model I 6 8 4.4 Model I I . . . . 84. 4 . 5 Model I I I ; . . . . . . . 8 7 i v CHAPTER 5 - DISCUSSION OP RESULTS 5.1 I n t r o d u c t i o n . . . . 92 5.2 S e v e r a l R e l a t i v e C o n s i s t e n c y R e s u l t s 92 5.3 Some I m p l i c a t i o n s Independent from Z-F . . . 93 • 5 .4 Some A d d i t i o n a l D e f i n i t i o n s 94 5 .5 Concluding Remarks . . . . . . 96 BIBLIOGRAPHY . . . . . . 99 / V A CKNOWLEDGEMENTS I wish to thank my supervisor, Professor David W. Bressler, f o r his help i n the preparation of thi s t h e s i s . I also wish to thank the University of B r i t i s h Columbia and the National Research Council of Canada f o r t h e i r f i n a n c i a l a i d during my studies. 1 CHAPTER 1  PRELIMINARY 1.1 I n t r o d u c t i o n In t h i s chapter we p r e s e n t some d e f i n i t i o n s and r e s u l t s t h a t the reader should be f a m i l i a r w i t h . F o r a more d e t a i l e d treatment of s e t theory the reader Is r e f e r r e d to the book by Suppes [27] and Chapters 1 and 2 of the book by Cohen [ 1 ] . Some knowledge o f the b a s i c ideas of mathematical l o g i c i s r e q u i r e d , p a r t i c u l a r l y i n Chapter 3 , but because even the most b a s i c concepts r e q u i r e c o n s i d e r a b l e develops ment, these concepts are not d i s c u s s e d i n t h i s p r e l i m i n a r y and the reader i s r e f e r r e d to the book by S c h o e n f i e l d [ 2 1 ] . F o r a d e t a i l e d treatment of Boolean a l g e b r a s the books by Halmos [7] and S I k p r s k i [23] are recommended. 1.2 Axioms of Set Theory F o l l o w i n g are the Zermelo-Fraenkel axioms which we w i l l use i n t h i s paper: i ) ( e x t e n s i o n a l i t y ) VA V B(Vx(x e A <-> x e B) -» A = B) i i ) (comprehension)' - axiom schema VA 3 BVx(x € B <-> x e A A $(x)) i i i ) ( f oundation) - axiom schema VA(Vy € A ( $ ( y ) ) - $(A)) - YB($(B)) 2 i v ) (replacement) - axiom schema VA^BVx e A 3 y e B(3z*(x,z) - «(x,y)) v) (power s e t ) VA3BVx(x € B <-> Vy e x ( y e A)) 1 v i ) (union) VAz3BVx(x e B <-> 3 Z e A ( x € z ) ) v i i ) ( i n f i n i t y ) 3 A ( 3 * ( x e A) A Vx e A ^ y e A(x € y ) ) We w i l l denote the above axioms i ) - v i i ) as Z-F. Most treatments of s e t theory i n c l u d e the axiom of choice i n the Zermelo-Fraenkel axioms, but i n t h i s paper we w i l l be working mainly with r e s u l t s t h a t are proved without the axiom of c h o i c e . Thus we give i t here as a separate axiom. (AC) VA ^ BVx e A(3y € x3«z € A ( y € z) - 3 !Y e x ( y € B)) Axiom i v ) i s not u s u a l l y g i v e n as an axiom schema but as the e q u i v a l e n t axiom i v ) ' V A 3 y ( A = 0 V (y e A A Vz(z e A -* - z € y ) ) ) . The axiom schema j u s t expresses the i d e a t h a t i n d u c t i o n can be c a r r i e d out on the e r e l a t i o n which i s e q u i v a l e n t to the statement t h a t every s e t i s well-founded. For the power s e t of A whose e x i s t e n c e i s guaranteed by axiom v) we use the n o t a t i o n P(A) . For the statement t h a t these axioms are c o n s i s t e n t 3 we s h a l l use the notation Consis(Z-P) , and indeed to express the f a c t that an a r b i t r a r y set of non-logical axioms T i s consistent we s h a l l use the notation Consis(T) . 1.3 Ordered Pairs, Orderings and Ordinals D 1.3-1 Por sets x, y we define the ordered p a i r <x,y> = {(x},{x,y)) Por a set R we denote the formula <x,y> e R by xRy and the set (<y,x> : xRy) by R - 1 . D 1-3*2 We say that R orders A i f f o r a l l x,y,z € A we have: i ) xRx i i ) xRy or yRx i i i ) xRy and yRx implies x = y iv) xRy and yRz implies xRz. D 1-3-3 R well orders A i f R orders A and f o r a l l S c A there i s a y e S such that f o r a l l x e S yRx . T 1.3.4 (Zermelo) AC i s equivalent to the statement that f o r a l l A 4 there i s an R t h a t w e l l orders A . I f we r e p l a c e " w e l l o r d e r " by "order" we get a weaker form of the axiom of choice (see [ 1 ] ) . (Ordering P r i n c i p l e ) : e v e r y s e t can be ordered. P 1 .3 -5 A s e t a i s an o r d i n a l i f a i s w e l l ordered by (<x,y> : x,y € a and x e y or x = y) and i f f o r a l l x € a and y € x we have y e a . We denote "a i s an o r d i n a l " by a e OR . As u s u a l we w i l l use ID to denote the f i r s t I n f i n i t e o r d i n a l . D 1.3.6 We w r i t e |A| = |B| I f there i s a 1-1 f u n c t i o n from A onto B and |A| <_ |B| i f there i s a 1-1 f u n c t i o n from A i n t o B . |A| < |B| i f IA J < |B| and |A| 4 |B| . D 1.3.7 . / a i s a c a r d i n a l i f a e OR and f o r a l l j3 e a we have |j3 \ < \a\ . D 1.3.8 I f (A,R) and (B,R^) are ordered s e t s we w r i t e A « B i f there i s a 1-1 f u n c t i o n f from A onto B such t h a t i f x,y € A and xRy then f ( x ) R 1 f ( y ) . . 5 1.4 Boolean Algebras D 1.4.1 A Boolean algebra i s a r e l a t i o n a l system (j3, —,•,+) where — i s a unary r e l a t i o n , and are binary r e l a t i o n s and furthermore i ) A + B = B + A A « B = B-A i i ) A + (B + C) m (A + B) + C A.(B-C) « (A'B).C i i i ) (A.B) + B = B (A + B)-B = B iv) A-(B + C) = A-B + A.C A + (B-C) = (A + B)•(A + C) v) (A.-A) + B « B (A + -A)«B = B We introduce the following defined operations and constants. A => B = -A + B = -(A'-B) A <=> B = (A => B)•(B => A) 31 = A + -A CD = A • -A We define the following r e l a t i o n on j3 A <_ B i f (A => B) = 1 . We denote by 2 the Boolean algebra (CD,31} . D 1.4.2 j3 a Boolean algebra, T a set and Afc e B f o r ,t e T . B i s the sup(join) of a l l the sets Afc , t e T i f i ) f o r a l l t e T A t < B' implies B < B' i i ) f o r a l l t e T Afc < B 6 We denote th i s sup by 2 A. . By d u a l i t y we teT z have TT A 4 - > t h e i n f (meet) of a l l the A. , t e T . t e T , c D 1.4.3 A Boolean algebra 0 i s complete i f f o r a l l {A. ). m c /8 there i s a B e j8 such that B = 2 A. . t t e i t e T X, T 1.4.4 (Rasiowa-Sikorski) j3 a Boolean algebra. Let X n be a set and „ e j3 f o r n e UD and x e X . I f a M = 2 a„„ e 0 , n,x n x e X ^ xn then there exists a homomorphism h : j3 -• 2 such that h(a ) = 2 h(a ) n xeX n n x Proof: Let S be the set of a l l prime ideals of j3 , and l e t S(a) = {p e S : a p] . We can regard S as a topolo-g i c a l space when G « (S(a) : a e /3) i s taken as a clopen basis. Now each prime i d e a l is/associated with a unique homomorphism from j3 onto 2 . Let be the set of a l l prime ideals whose associated homomorphism do not preserve 2 a i . e . h(a„) 4 2 h(a ) . The set xeX n x n xeX n x n n S(a_) - U S t a ) i s closed i n S . Suppose i t s i n t e r i o r xeX n n x i s not empty. Then there i s a b e j3 such that S(b) c s(a ) - U S(a ) or n xeX n n x 7 e q u i v a l e n t l y S(a_„) c S(a) - S(b) = S ( a - b) f o r every x e X n . Now the f u n c t i o n t h a t maps x i n t o S(x) i s an isomorphism from j3 to the f i e l d of clopen subsets of S . T h e r e f o r e a n x <_ a n - b ^ a n f o r a l l x e X n . T h i s con-t r a d i c t s the f a c t t h a t a = E a . Th e r e f o r e the i n t e r i o r n X€X n n x of S must be v o i d and thus S must be nowhere dense i n n n S . Now i f P i s the s e t of a l l prime i d e a l s whose a s s o -c i a t e d homomorphism pr e s e r v e s the sups then S-P must be of f i r s t c ategory i n S . Now i t i s known t h a t S i s com-p a c t , t h e r e f o r e P i s dense i n S . C l e a r l y then P ^ 0 . (See [17]). / 8 CHAPTER 2  DEFINITIONS OP FINITE 2.1 I n t r o d u c t i o n In t h i s paper we w i l l d i s c u s s s e v e r a l d e f i n i t i o n s of the s e t t h e o r e t i c p r o p e r t y c a l l e d " f i n i t e " . The e a r l i e s t d e f i n i t i o n was j u s t a f o r m a l statement of the i n t u i t i v e f e e l i n g t h a t any " f i n i t e " s e t should be e q u i v a l e n t to an i n i t i a l segment of u> . Then Dedekind [2], i n an attempt to d e f i n e " f i n i t e " without u s i n g the I n t e g e r s , suggested t h a t a s e t should be " i n f i n i t e " i f i t can be p l a c e d i n a 1-1 c o r r e s -pondence wi t h a proper subset of i t s e l f . These two d e f i n i -t i o n s were proved to be e q u i v a l e n t u s i n g the a x i o n of c h o i c e , but R u s s e l l and Whitehead [28] asked whether mediate c a r d i n a l s , c a r d i n a l s which are f i n i t e i n the f i r s t sense but i n f i n i t e by Dedekind*s d e f i n i t i o n , c o u l d e x i s t i f one d i d not assume the axiom of choice ( m u l t i p l i c a t i v e axiom). R u s s e l l and Whitehead demonstrated some p r o p e r t i e s t h a t these c a r d i n a l s would have i f they e x i s t e d but i t was not u n t i l the work of F r a e n k e l [5], Mostowski [16] and Cohen [1], t h a t the e x i s t e n c e of mediate c a r d i n a l s c o u l d be shown to be c o n s i s t e n t w i t h the axioms of s e t theory. S e v e r a l other d e f i n i t i o n s were proposed by Whitehead and R u s s e l l [28], T a r s k i [26], Kurow-towski [11] and L£vy [13]' I t i s the purpose of t h i s paper to i n v e s t i g a t e the interdependences of these d e f i n i t i o n s and to 9 prove some c o n s i s t e n c y r e s u l t s . A l l p r o o f s i n t h i s chapter t h a t use the axiom of choice or the o r d e r i n g p r i n c i p l e w i l l be s t a r r e d . 2.2 D e f i n i t i o n s We f i r s t d e f i n e a f t e r R u s s e l l and Whitehead. D 2.2.1 A s e t A i s r e f l e x i v e i f there i s a proper subset of A say B and a 1-1 f u n c t i o n from A onto B . A s e t A i s i r r e f l e x i v e i f i t i s not r e f l e x i v e . The f o l l o w i n g d e f i n i t i o n was suggested by T a r s k i D 2.2.2 Given a s e t B we d e f i n e minel(B) by x e minel(B) i f and o n l y i f f o r a l l y e B , .y i s not a proper subset of x (minel(B) i s the s e t of a l l minimal elements i f B under the I n c l u s i o n o r d e r i n g ) . S i m i l a r l y we d e f i n e x e maxel(B) i f and o n l y i f f o r a l l y e B , x i s not a proper subset of y . Now we g i v e the main d e f i n i t i o n s of a f i n i t e s e t t h a t we w i l l be c o n s i d e r i n g i n t h i s paper. D 2.2.3 ( T a r s k i ) A s e t A i s f i n i t e 1 i f f o r any B c p(A) such t h a t B 4 0 we have minel(B) ^ 0 . 10 D 2.2.4 (Levy) A s e t A i s f i n i t e 2 i f f o r a l l B, C such t h a t B n C = 0 and A = B U C we have B f i n i t e 1 or C f i n i t e ^ D 2.2.5 ( T a r s k i ) A s e t th a t B i s ordered by i n c l u s i o n we have maxel(B) 4 0 • A i s f i n i t e 3 i f f o r a l l B c P(A) such D 2.2.6 A s e t A i s f i n i t e ^ i f f o r any B c A and R such t h a t R orders B we have R w e l l orders B . D 2.2.7 ( T a r s k i ) A s e t A i s f i n i t e ^ i f P(A) i s i r r e f l e x i v e . D 2.2.8 (Dedekind) A s e t A i s f i n i t e ^ i f A i s i r r e f l e x i v e . O c c a s i o n a l l y i t i s more convenient t o use the / concept of i n f i n i t e r a t h e r than f i n i t e i n a p r o o f , so we d e f i n e D 2.2.Q 1 - 1, 2, 3, K, 5, 6. A s e t A i s i n f i n i t e . ^ i f A i s not f i n i t e ^ ^ f o r 11 2.3 Some Equivalent Definitions We f i r s t prove the following lemma. L 2.3.1 A i s r e f l e x i v e i f and only, i f there i s a 1-1 function from uu into A . Proof: Suppose f i s a 1-1 function from u) into A . Denote f(n) by x n and l e t B = ( x Q , x ^ ...} . Define F , a function from A into A , by r rx x I B P(x) = { xn+l x = x n c B . Clearly P i s 1-1 and maps A onto A-(x Q} . Therefore A i s r e f l e x i v e . Now suppose A i s r e f l e x i v e , then there i s a 1-1 function, say P , from A onto a proper subset of A^ say B . / Consider x Q e A - B and define a sequence rec u r s i v e l y by x n + 1 = P(x n) f o r n >. 1 . I t i s s u f f i c i e n t to show that x^ ^ x j f o r 1 / j • We notice that x e A - B and x_ e B f o r n > 1 , therefore x„ ^ x. o n — ' o j f o r a l l j / 0 . Suppose there are i , j such that x i = x^ and i 4 j l e t k be the least integer such that x k = x^ . But then = ^ j . ^ as F i s 1-1, a contradiction, so the function that takes n into x n i s a 1-1 function from ou 12 into A . T 2.3.2 The following are equivalent i ) A i s f i n i t e ^ i i ) I f B c p(A) and B ^ 0 then maxel(B) ^ 0 (Tarski). i i i ) I f a) L c p(A) b) 0 e L c) i f x e A then [x] e L d) f o r a l l B,C € L we have B U C e L then L = P(A) (Kuratowski). iv ) A belongs to a l l sets B such that a) 0 e B b) f o r a l l x e A we have (x) e B c) f o r a l l C,D e B we have C U D € B (S i e r p i n s k i - T a r s k i ) . v) There i s an n € UJ and a 1-1 function f that maps n onto A . v i ) There i s an R such that both R and R*"1 well order A (Stackel). v i i ) P(P(A)) i s i r r e f l e x i v e (Whitehead-Russell). Proof: i ) - i i ) Assume A i s f i n i t e - ^ Consider B c p(A) and B ^ 0 . Let C = (A - D : D e B) . 13 As A i s f i n i t e 1 , A e C and C c p(A) we have mine! 0^0. C l e a r l y • m inel C = maxel B . Thus maxel B 4 0 « i i ) -» i i i ) Assume t h a t A s a t i s f i e s i i ) . L e t L be as i n i i i ) and suppose C € P(A) !. Por M = (D € L : D c C) we have M c P(A) and M ^ 0 as L c p(A) and 0 e L . By i i ) maxel M 4 0 , but i f D e maxel(M) and D / C then there i s an x € C - D and D u fx] e M . T h i s c o n t r a d i c t s the statement t h a t D e maxel M and so we must have D = C and thence C € L . T h e r e f o r e L = P(A) . i i i ) •-• i v ) Assume t h a t A s a t i s f i e s i i i ) and B i s as i n i v ) . L e t L = [D e B : D c A) . C l e a r l y L s a t i s f i e s a l l the p r o p e r t i e s i n i i i ) and thence L = P(A) . T h e r e f o r e A c B as L a B . i v ) -» v) Assume t h a t A i s as i n i v ) and l e t B = (C c A : f o r some n e w there Is a 1-1 f u n c t i o n C l e a r l y f i s 1-1 and maps n^ + n 2 onto C u D , thence C U D € B . T h e r e f o r e B ' s a t i s f i e s the c o n d i t i o n s from n onto C) Now 0 e B and f o r (x) e A we have (x) e B . I f C,D e B then there are 1-1 f u n c t i o n s f ^ f g and i n t e g e r s n^ and n^ such t h a t f ^ maps n^ onto C and f 9 maps n~ onto D . Define f by n, < I < n n + n, i < n 14 of Iv) and we have A € B . v i ) L e t A be such t h a t f o r some i n t e g e r n € uu there i s 1-1 f u n c t i o n from n onto A . Define R c A x A by <x,y> e R i f f f ~ 1 ( x ) <_ f _ 1 ( y ) . As any subset of n has a minimum and a maximum under < we must have t h a t R and R~^ both w e l l order A . - i ) Suppose A s a t i s f i e s v) and A i s i n f i n i t e ^ By v) there must be a w e l l o r d e r i n g o f A and thus A « a f o r some o r d i n a l a . T h e r e f o r e we can w r i t e A as (x^ : £ < a) . As A i s i n f i n i t e ^ there must be a B c P(A), B ^ 0 such t h a t minel(B) = 0 . Now suppose a < uu i e : a = n f o r some n e tu . L e t C = [m : there i s a D € B such t h a t |D| = m} . We see that C Is a subset o f i n t e g e r s l e s s than n and thus there must be a s m a l l e s t i n t e g e r i n C say j . Then there i s a D e B such t h a t |D| = j , but c l e a r l y t h a t would mean D, e minel(B) . T h i s i s a con-t r a d i c t i o n so we must have a >_ uu , but i f R p l a c e s the o r d e r i n g of a on A then R x p l a c e s the o r d e r i n g of a* on A which i s not a w e l l o r d e r i n g . T h e r e f o r e A must be f i n i t e ^ . We have now shown t h a t the s t a t e -ments i ) - v i ) a re e q u i v a l e n t and so I t i s s u f f i c i e n t to show t h a t v i i ) i s e q u i v a l e n t t o v ) . 15 v) v i i ) Suppose there i s a 1-1 function f from n onto A . gn Then c l e a r l y we have a 1-1 function from m = 2 onto P(P(A)) . Now i f P ( P ( A ) ) were r e f l e x i v e we would have to have a 1-1 function from m onto some j with j < m which i s impossible. Therefore P(P(A)) i s i r r e f l e x i v e . v i i ) - v) Suppose that there i s no 1-1 function from any integer onto A . For each n e w define x = {B c A : there i s a 1-1 function from n onto B}. n Now x ^ 0 as GC € x . Clearly A i x f o r a l l o o T n n e w , thence i f x^ 4 0 then f o r B e x^ and y € A - B we have B U (y) e x k + 1 . As x 1 ^ x^ f o r a l l i / j we must have P(P(A)) Is r e f l e x i v e by L 2.3.1. a Whitehead and Russell [ 28 ] suggested an a l t e r n a t i v e d e f i n i t i o n f o r f i n i t e ^ which they termed "inductive", using the following schema. ^ D 2 . 3 . 3 A i s inductive i f f o r a l l $ (formulas with one free variable) such that i ) H?) i i ) $(B) implies $(B U fx}) f o r a l l B,x ,we have $(A). Now i n the f i r s t order language used to express the 16 Zermelo-Fraenkel axioms t h i s d e f i n i t i o n would have to be an i n f i n i t e c o n j e c t i o n , where each component of the c o n j e c t i o n would express the p r o p e r t y f o r a p a r t i c u l a r $ . As t h i s i s not a sentence i n a f i r s t o r d e r language we have to f i n d another method i f e x p r e s s i n g the i d e a of i n d u c t i v e s e t s . The d e f i n i t i o n i n T 2 . 3 . 2 ( i v ) i s b a s i c a l l y the same i d e a but s u b s t i t u t e s s e t f o r p r o p e r t y and r e s t r i c t s the mention of a l l s i n g l e t o n s to s i n g l e t o n s i n c l u d e d i n A . However we can c o n s i d e r the f o l l o w i n g theorem schema f o r i n d u c t i o n on f i n i t e s e t s . That i s f o r each sentence w i t h one f r e e v a r i a b l e § we have the theorem T 2.3.4 - Theorem schema I f A i s f i n i t e - j ^ and i ) «(•*) i i ) F o r a l l x and a l l B such t h a t $(B) we have *(B U (x)) then $(A) . P r o o f : By the axiom schema of s e p a r a t i o n there e x i s t s a s e t B = (D : *(D) and D e P(A)} . C l e a r l y B c p(A) and as $(0) we have 0 e B . I f C € B and x e A then *(C) and $(C U (x)) hence we have, C U (x) e B . By T 2 . 3 . 2 we have A c B and thence $(A) . 0 ) T 2.3.5 A i s f i n i t e 3 i f and only i f there i s a B c P(A) such that B i s ordered by i n c l u s i o n and B i n f i n i t e - ^ Proof: I f A i s i n f i n i t e 1 there i s an L c P(A) L ^ and maxel(L) = 0 , with L ordered by i n c l u s i o n . Clearly L i s ordered by reverse i n c l u s i o n which cannot be a w e l l -ordering as maxel(L) = 0 , therefore by T 2.3.2 L i s i n f i n i t e ^ Suppose • B c P(A) , B ordered by i n c l u s i o n and B i n f i n i t e . As B i s i n f i n i t e , either i n c l u s i o n or i x x reverse i n c l u s i o n cannot well order B . Therefore there i i must be a subset of B say S with no maximal element by i n c l u s i o n . Therefore A i s i n f i n i t e ^ . 3 T 2.3.6 A i s f i n i t e ^ i f and only i f f o r a l l X c A such that there i s an R that orders X we have X i s f i n i t e ^ . / Proof: Suppose A i s f i n i t e ^ and l e t X c A . I f R orders X then R 1 orders X and as A i s f i n i t e ^ we must have that both R and R"1 well order X . Therefore by T 2.3-2 we have X i s f i n i t e ^ . Suppose that every sub-set of A that can be ordered i s f i n i t e ^ . Suppose R orders X c A and there exists a subset S c X that has no 18 minimal element wi t h r e s p e c t to R . Define S = (Z e S : yRz) f o r y e S .. T = ( S l y e S) c P(X) and y y m inel(T) = 0 , t h e r e f o r e X i s not f i n i t e ^ a c o n t r a d i c t i o n . 8 A s e t A i s i n f i n i t e ^ i f and o n l y i f |P(A)| > A s e t A i s I n f i n i t e g i f and o n l y i f |A| > Proof: The r e s u l t i s c l e a r from L 2.3.1. 2.4 I m p l i c a t i o n s between the D e f i n i t i o n s T 2.4.1 I f A i s f i n i t e 1 then A i s f i n i t e g . P r o o f : T h i s i s e q u i v a l e n t to the statement t h a t i f A i s i n f i n i t e 2 then i t i s i n f i n i t e ^ . Suppose A i s i n f i n i t e 2 , then A = B U C where C,B are i n f i n i t e 1 and C D B *= 0 . Now B i n f i n i t e - ] ^ i m p l i e s t h a t there i s a Q c P(B) , Q ^ 0 and minel(Q) - 0 . C l e a r l y Q c p(A) , hence A i s i n f i n i t e 1 . a . T 2.4.2 I f A Is f i n i t e 2 then A i s f i n i t e ^ . 19 P r o o f : We g i v e here the pr o o f by Levy [13] t h a t i f A i s i n f i n i t e ^ then i t i s i n f i n i t e g . L e t us assume t h a t A i s i n f i n i t e ^ . Then there i s a K c P(A) such t h a t K i s ordered by i n c l u s i o n and maxel(K) = 0 . Now there are two cases a) a l l members of K are f i n i t e ^ b) there i s a member of K t h a t i s i n f i n i t e ^ Case a) Consider a l l s e t s of the form Q = [y : y € K and y c x] . Now Q v c p(X) and X X Q v / ^ as A i s i n f i n i t e , , t h e r e f o r e Q„ must be X j X f i n i t e , . By T 2.3.2 we have t h a t |Q | = n , and _L X X n 4 n f o r x ^ y s i n c e f o r a l l x,y € K x c y or x y y c x . T h e r e f o r e there must be a 1-1 f u n c t i o n from to i n t o K , and we can w r i t e [A^A-^Ag, ...) c: K wit h A.^  c A i + 1 f o r each i € tu . L e t 00 B = U ^ ( A 2 1 + 2 - A 2 i + i ) a n d C = A - B . C l e a r l y oo / U0 ^ A 2 i + l " A 2 i ^ C 0 * N o w B i s i n f l n l t e i a s i f n L = ( U (A 2i+2 " A 2 i ) '' n € ^ w e h a v e L c p ( B ) > L / |Z( and maxel(L) = 0 . S i m i l a r l y C i s i n f i n i t e ^ Thus A i s i n f i n i t e 2 . Case b) Let B e K and suppose B i s i n f i n i t e - ^ . L e t C «= A -20 Now i f C i s f i n i t e 1 l e t L = (x 6 K : B c x] .We know that L 4 0 as m a x e l ( K ) V 0 so i f M = {A - x : x e L) we have M ^ 0 and M c P(C) hence minel(M) 4"0 • However minel(M) = maxel(L) c maxel(K) , a c o n t r a d i c t i o n . Therefore j we must have C i n f i n i t e - j ^ and thence A i s I n f i n i t e ^ Q T 2.4.3 I f A i s f i n i t e 3 then A i s f i n i t e ^ . Proof: Suppose that A i s i n f i n i t e ^ , then there i s an R that orders L a subset of A but does not w e l l order L . There must be a subset S of L such that S has no minimal element w i t h respect to R . Let K = (y € S : xRy) f o r a l l x e S and l e t K = (A - K : x e S ) . C l e a r l y K c P(A) and K i s ordered by i n c l u s i o n . As S has no minimal element w i t h respect to R we have maxel'(K) = 0 and hence A i s I n f i n i t e ^ . Q / T 2.4.4 I f A i s f i n i t e ^ then A i s f i n i t e ^ . Proof: Suppose A i s i n f i n i t e s then there must be a 1-1 f u n c t i o n f from ou i n t o P(A) . Let us denote f ( n ) by A . To each x e U A. l e t us a s s o c i a t e a b i n a r y f r a c t i o n n 1=0 1 21 b x = 0 * d i X d 2 X ••• d e f l n e d b y y r 1 x e A « d x - { n . n 1 0 x M N Now f o r each r e a l number 0 < r < 1 l e t 00 p, = {x e U A, : b <, r) . Cl e a r l y B c A and r, < v0 r 1 0 ~™" 00 implies B cr B . Now (b : x e U A. ) must be i n f i n i t e , r l r2 x i=0 1 1 f o r I f i t we f i n i t e , these would be a 1-1 map from 2 m onto 00 (A , A,, ...} where m = |{b : x e U A.}| which i s a con-o i x 1 = 0 1 t r a d i c t i o n . Therefore B = (B r : 0 < r <_ 1} i s i n f i n i t e ^ and A i s i n f i n i t e ^ by T 2.3.5- H T 2.4.5 If A i s f i n i t e ^ then A i s f i n i t e ^ . Proof; Assume that A Is i n f i n i t e ^ then there i s a subset B = ( x Q , x ^ ...} c A where ^ x^ f o r i ^ j . Let R = (<x 1 , X j > : i > j) . Clearly R orders B but R does not well order B , hence A i s i n f i n i t e ^ . 8 T 2.4.6 If A i s f i n i t e . , the A i s f i n i t e , - . 5 6 22 Proof; Suppose A i s i n f i n i t e ^ , then there i s a 1-1 function from A onto a proper subset of A . Define g a function on P(A) by (f(x)) y = (x) f o r some x e A . Clearly g i s 1-1 and maps P(A) into a proper subset of P(A) . Therefore A i s i n f i n i t e ^ . ' B equivalent i f the axiom of choice i s assumed. Proof; By the previous theorems i n thi s section i t Is, s u f f i c i e n t to prove that i f A i s in f i n i t e - ^ then A i s i n f i n i t e ^ . Suppose A i s i n f i n i t e - ^ . Using the well order-ing p r i n c i p l e we can well order A , thus A must be equi-valent to some cardinal C , as' A equivalent to n < tu would imply A i n f i n i t e ^ . Therefore we must have |A| >_ f uo| and by T 2 . 3 . 7 A Is i n f i n i t e g . 61 *T 2 . 4 . 8 The d e f i n i t i o n s of f i n i t e 1 though to f i n i t e ^ are equivalent i f the ordering p r i n c i p l e i s assumed. g(y) y 4 (x) f o r some x e A *T 2 . 4 . 7 A l l the d e f i n i t i o n s f i n i t e ] ^ through to f i n i t e ^ are 23 Proof t By the previous theorems i n th i s section i t i s s u f f i c i e n t to show that A i s i n f i n i t e ^ ^ i t i s i n f i n i t e ^ . Let A be i n f i n i t e ^ By the ordering p r i n c i p l e there i s an R that orders A . Now i f R does not well order A we are done . I f R does well order A , R*"1 must order A but cannot well order A as A i s i n f i n i t e ^ . Therefore i n both cases A Is i n f i n i t e ^ . • »T 2.4.9 I f we assume the ordering p r i n c i p l e then A f i n i t e implies A f i n i t e ^ . Proof: Assume A i s f i n i t e ! , . B y T 2.4.8 and the ordering p r i n c i p l e A i s f i n i t e ^ . By T 2.4.4 A i s f i n i t e , . . L 2.4.10 I f A, B are f i n i t e ^ then A U B i s f i n i t e ^ . Proof: Let L be a subset of P(A U B) that i s ordered by i n c l u s i o n . Let «=> (A D M : M € L) and K 2 = [B 0 M : M e L) . As L i s ordered by i n c l u s i o n so must be and K 2 , and so A,B are f i n i t e ^ we have maxel(K..) / 0 and maxel(K 0) ^ 0 . Let C. e maxel(K-) 24 and Cg e maxel(K 2) As L i s ordered by i n c l u s i o n and C l c D l € L a n d C2 c D2 € L there must be a D € L such that C 1 U C 2 c D . Now D PI A c C 1 as C 1 e m a x e l ^ ) and D 0 B c C 2 as C"2 e maxel(K 2) . Therefore (D 0 A) U (D fl B) - D c U C"2 c D , and hence 'D = ^ U Cg. As this proves U C 2 c maxel(L) we have shown that A U B i s f i n i t e ^ ' T 2.4.11 (Levy) If a l l f i n i t e ^ sets are f i n i t e 2 then a l l f i n i t e 2 sets are f i n i t e ^ . Proof: Assume that a l l f i n i t e ^ sets are f i n i t e 2 . Suppose K Is f i n i t e 2 but l n f l n l t e 1 . Now 2 x K = (0) x K U (1) x K i s c l e a r l y i n f i n i t e ^ K i s f i n i t e ^ by T 2.4.2, and so by L 2.4.10 2 x K i s f i n i t e ^ . This i s a contradiction as 2 x K i s i n f i n i t e 2 and we have assume that a l l f i n i t e ^ sets are f i n i t e g . Therefore we must have that K i s f i n i t e ^ . 69 2.5 Properties of the Definitions Following i s a set of properties that i t would seem desirable f o r a d e f i n i t i o n of f i n i t e to s a t i s f y . 2.5.1 i ) For a l l x , (x) i s f i n i t e . 25 i i ) I f A i s f i n i t e and B c A then B i s f i n i t e , i i i ) I f A i s f i n i t e then A U (x) i s f i n i t e , i v ) I f A i s f i n i t e and f i s 1-1 and maps A onto B then B i s f i n i t e . •i v) uu i s i n f i n i t e . T 2.5.2 A l l the d e f i n i t i o n s f i n i t e ^ i - 1, 2, 3, 4, 5, 6, s a t i s f y the c o n d i t i o n s i n 2.5.1. Proof: C l e a r l y (x) i s f i n i t e ^ f o r a l l x and tu i s f i n i t e ^ , thus by the theorems i n 2.4 we can see th a t a l l the' d e f i n i t i o n s s a t i s f y c o n d i t i o n s i ) and v ) . C o n d i t i o n s i i ) and i v ) are easy to check and t h e i r p r o o f i s l e f t to the re a d e r . We now show t h a t a l l the de-f i n i t i o n s s a t i s f y c o n d i t i o n i i i ) . I f A i s f i n i t e ^ there i s a 1-1 map from an i n t e g e r n onto A , thus there i s c l e a r l y a 1-1 map from n + 1 onto A U (x) i f x A . Th e r e f o r e i f x A then A U (x) i s f i n i t e 1 and i f x e A then A U {x} = A which i s f i n i t e ^ I f A i s f i n i t e 2 and A U (x) = B U C then one of B - ( x ) , C - (x) i s f i n i t e ^ . By the above r e s u l t one of B,C i s f i n i t e 1 and thus A U (x) i s f i n i t e g . Suppose A i s f i n i t e ^ . L e t L c P(A U {x}) be ordered by i n c l u s i o n . L e t K «= (y - (x) : y e L) . C l e a r l y 26 K i s ordered by i n c l u s i o n and thus maxel(K) ^ 0 . L e t C e maxel(K) , i f C / maxel(L) then f o r some y e L C c y (C ?*"y (C ^  y) , but y £ K , thus y = C U fx) and y e maxel(L) . Th e r e f o r e A U {x} i s f i n i t e ^ ' Suppose A i s f i n i t e ^ . L e t R order a subset of A U (x) say S . Thus R w e l l orders S - {x} and hence R w e l l orders S . Th e r e f o r e A U (x) i s f i n i t e ^ . Suppose P(A U {x}) Is r e f l e x i v e , then there i s a subset B = (A Q , A.^ A g , ...) c p(A U (x)) . L e t C, = [ A i - (x) : A± e B) . C l e a r l y i f B i s countably i n -f i n i t e then C i s countably i n f i n i t e . T h e r e f o r e P(A) i s r e f l e x i v e . I f A u (x) i s i n f i n i t e g then |A U (x) | >. X o so c l e a r l y |A| >_ oo and A i s i n f i n i t e ^ . 2.6 Some R e s u l t s Concerning a C l a s s of D e f i n i t i o n s A d e f i n i t i o n of f i n i t e i s a one p l a c e p r e d i c a t e t h a t a s s i g n s a value t r u e o r f a l s e to any s e t . I t i s c l e a r t h a t we co u l d take any such p r e d i c a t e and c a l l i t a d e f i n i -t i o n of f i n i t e . However to make a meaningful d e f i n i t i o n we must have some f e e l i n g t h a t the p r e d i c a t e expresses a p r o -p e r t y t h a t i n some way c h a r a c t e r i z e s the concept of b e i n g f i n i t e . I f we make the r e s t r i c t i o n t h a t a d e f i n i t i o n of f i n i t e (a p r e d i c a t e ) should s a t i s f y the l i s t 2.5.I then we can show some r e l a t i o n s h i p between these d e f i n i t i o n s and some of the p a r t i c u l a r d e f i n i t i o n s we have been s t u d y i n g . 2 7 The f i r s t r e s u l t we s h a l l show i s t h a t i f a p r e d i -cate does s a t i s f y 2 . 5 . I then i t w i l l have to c a l l any f i n i t e ^ s e t f i n i t e i n i t s own sense ( i . e . - a s s o c i a t e the value t r u e to any f i n i t e 1 s e t ) . T h i s means t h a t the f i n i t e - j ^ d e f i n i t i o n i s the most r e s t r i c t i v e , i t separates out the s e t s t h a t must be f i n i t e under any d e f i n i t i o n t h a t agrees w i t h 2.5.1. In f a c t as the f o l l o w i n g schema shows o n l y c o n d i t i o n s i ) , i i ) , i i i ) from 2 . 5 . I are needed. T 2.6.1 - Theorem Schema I f $(x) i s such t h a t i ) *({x}) f o r a l l x i i ) $(A) and B c A i m p l i e s §(B) i i i ) $(A) i m p l i e s $(A U (x)) f o r a l l x and S i s f i n i t e 1 then *(S) . Proof; C l e a r l y 0 c (x) , hence we have $(#) . T h e r e f o r e by the theorem f o r $ i n the theorem schema 2 . 3 - 4 we have «(S) . We can a l s o show t h a t i f *(x) i s a p r e d i c a t e t h a t s a t i s f i e s 2 . 5 . I i i ) , i v ) , v) then any s e t t h a t i s a s s i g n e d the value t r u e by $ ( c a l l e d f i n i t e by $) must be f i n i t e ^ . T h i s means t h a t f i n i t e ^ i s the weakest d e f i n i t i o n of f i n i t e a l l o w e d under 2.5.1. 28 T 2.6.2 - Theorem Schema If $(x) i s such that i ) $(A) and B c A implies $(B) i i ) i f $(A) and there i s an I7.I function from A onto B then §(B) . " • i i i ) -» *(OJ) then $(S) implies S i s f i n i t e ^ . Proof: Assume that $ i s as i n i ) , i i ) , i i i ) and that §(S) . Now suppose S i s i n f i n i t e ^ , then there exists a 1-1 function f from to into S . Let B be the image of u) under f . As B c S we have $(B) . As f i s 1-1 and onto B we must have l(ti)) , but by i i i ) -• §(00) . This i s a contradiction so S must be f i n i t e / - . / 29 CHAPTER 3  BOOLEAN-VALUED MODELS .3»1 I n t r o d u c t i o n To show the independence of some i m p l i c a t i o n s between these d e f i n i t i o n s of a f i n i t e s e t , we must c o n s t r u c t some models of Z-F. We w i l l use the method of Boolean va l u e d models developed by D. S c o t t [ 2 0 ] . These r e s u l t s can a l s o be o b t a i n e d u s i n g the n o t i o n of f o r c i n g , w i t h which Cohen [1] proved the independence of the axiom of c h o i c e , as was shown by H. Sayeki [ 1 8 ] . However the methods of Mostow-s k i [16] and Levy [ 1 3 ] , developed f o r s e t t h e o r i e s t h a t admit the e x i s t e n c e of Urelemente. can be c l o s e l y p a r a l l e d i n the Boolean valued models. Most of these r e s u l t s have been e s t a b l i s h e d by Jech and Sochor [ 8 ] , [9] as a consequence of t h e i r remarkable theorem which shows f o r a c e r t a i n c l a s s of sentences t h a t independence from s e t theory w i t h Urelemente i m p l i e s independence from Z-P. The method p r e s e n t e d here g i v e s a good understanding of what happens when the axiom of choice i s no l o n g e r v a l i d . We w i l l c o n s t r u c t our models i n s i d e a s e t V t h a t i s a model of the Z-P axioms under some b i n a r y r e l a t i o n R c V x V . The e x i s t e n c e of t h i s s e t i s e q u i v a l e n t t o the statement Consis(Z-P) . (See [1], p. 78). 30 3.2 The Universe V ^ ) Now i f 0 i s a complete Boolean Algebra, we construct a universe by induction. D 3.2.1 1 V ^ ) « (u € i 8 d o m ( u ) : there i s a r\ < a and dom(u) c V ^ ) T) • f o r a l l a e OR . D 3.2.2 V ^ ) = U f V ^ : a € OR) ( 6) Each member of V V P ' i s a function from some set of members of to 0 . The intention i s that these functions should be analogous to the c h a r a c t e r i s t i c function of a set, and i n f a c t i f j3 Is the algebra 2 , w i l l turn out to be isomorphic to the standard universe of Z-F set theory V . D 3-2.3 / A subset of , sa If f o r each v e S V ^ , dom(v) c Sv(P) . y S V ^ , i s a subsystem of D 3.2.4 SVV>> a s v ^ ) n v |p ) . a . 31 3.3 A s s i g n i n g Boolean Values to Sentences Now as the f u n c t i o n s t h a t determine s e t s i n SV^\ i n the manner of a c h a r a c t e r i s t i c f u n c t i o n , take values i n j3 i n s t e a d of j u s t [0,1} , i t i s n a t u r a l to assume t h a t sen-tences about elements of t h i s u n i v e r s e should a l s o take values i n j3 i n s t e a d o f j u s t [0,1) (or [ t r u e , f a l s e ) ) . We begin by a s s i g n i n g values t o the atomic sentences ,. Por a formula $ we use to denote the v a l u e i n j3 a s s i g n e d to i t . D 3.3.1 I f u,v e S V ^ then llu e v|| = S (v(y).||u = y| yedom(v) and ||u = v|| = TT, > U ) => h € v||). TT, (V(y) => ||y i u||) xedom(u) yedom(v) We note t h a t the value of |[u e v|| Is d e f i n e d i n terms of sentences of the form ||x e y|| , ||x = y|| where x,y € S V ^ ^ f o r some TI < a j u s t by s u b s t i t u t i n g the d e f i n i t i o n s twice, and s i m i l a r l y f o r ||u = v|| . Thus t h i s d e f i n i t i o n Is by i n d u c t i o n on the o r d i n a l s . Now we a s s i g n j3-values t o a l l sentences. D 3-3.2 V. #2'|| = || + n # 2 u 32 A #2|| = H^ll-llfgll M i l - -11*11 • 11^ - *g|| = l l ^ l l l l * 2 II <-> f2|| « 11^ || <=> ||#2|| H3u#(u)|| = 2 ||t(u)|| ||Vu§(u)|| = TT , l l«(u)| | This assigns a 0-value to every sentence as by repeated a p p l i c a t i o n of the above rules every sentence be-cause of i t s f i n i t e length must be reduced to a combination of values of atomic formulas which have values assigned by D 3.3.1. D 3-3-3 A formula $ i s g-valid i n SV^) i f ||*|| = H Now as D. Scott [20] points out, we have the following two theorems which hold independently of jS or / SV<*> are 0-valid i n SV A l l the rules and axioms of propositional l o g i c (0) T 3 . 3 . 5 A l l the rules and axioms of predicate l o g i c are 33 0 - v a l i d i n S V ^ . We must check t h a t axioms of equality are 0 - v a l i d i n S V ( / J ) . •j T 3.3.6 ( S c o t t ) u,u',v,v',w € S V ^ ^ , x e dom(u) a) ||u = u|| = 3L b) u(x) <. ||x c u|| c) ||u = v|| = ||v = u|| d) ||u = v||.||v = w|| < ||u = w|| e) ||u = u ' l l - l l u € v|| < ||u' e v|| f ) ||V - V ' l l - l l u € V|| < ||U € V ' | l Proof: Each p a r t w i l l be proved by i n d u c t i o n . Assume. u,u',v,v',w € Svj^) and r e s u l t s a) - f ) are t r u e f o r any members of , r\ < a . We w i l l show a) - f ) to be tr u e f o r u,u',v,v',w u s i n g the f a c t t h a t they are tr u e f o r members of dom(u), dom(u'), dom(v), dom(v') and dom(w) . a) Consider x e dom(u) ||x € u l | = S u(y)-||x = y|1 > u(x) • ||x = x|| = u(x) yedom(u) Th e r e f o r e ||u = u|| = E (u(x) => ||x e u||) = 3L xedom(u) b) ||x € u|| « E u(y).||x = y|| > u(x) ||x = x|| = u(x) yedom(u) c) Obvious from the symmetry of the d e f i n i t i o n s o f ||u = v| 34 and ||v = u|| . Let x e dom(u) , y e dom(v) , z € dom(w) ||x = y||#||y = z|| <_ ||x = z|| by induction hypothesis. <_ ||x = z||«w(z). Now taking the sup of both sides we get S ||u = v||.||v = w||.u(x>||x = y||-v(y).||y = z||.w(z) zedom(w) < E ||x = z||-w(z) , Z€dom(w) i which s i m p l i f i e s to ||u = v||-||v = w||.u(x).||x = y||-v(y).||y e w|| < ||x e w|| • Also, as ||v = w||-v(y) <. ||y e w|| we get ||u = v 1  -11 v = w||.u(x).||x = y||-v(y) <. ||x e w|| • Taking the sup of both sides again S ||u = v 1  -1|v = w||-u(x).||x = y||-v(y) < E ||xew y€dom(v) yedom(v) which s i m p l i f i e s to ' / . ||u = v||.||v = w||.u(x)-||x € v|| <. ||x e w|| and as ||u = v||'u(x) <_ ||x c v|| we get ||u = v||.||v = w||.u(x) <_ ||x e wII . By simple Boolean operations we have f o r any7 x e dom(u) Therefore ||u • v||'||v = w|i-u(x).||x = y||-v(y)'||y = z||-w(z) ||u = v||- ||v = w|| < u(x) => ||x € w|| so we can write llu = v||.||v II < TT , , xedom(u) u(x) «=> ||x € w|| S i m i l a r l y ||w = v|| • ||V w(z) => ||z e u|| . Therefore 35 l|u = v||.||v = w||.||w = v||.||v = u|| < TT , xedom(u) ; => ||x € w|| U . w(z) => ||z e u|| m | | u « w|| zedom(w) which simplifies to ||u = v||.||v - w|| < ||u = w|| . ! e) Let y e dom(v) Ilu = u'U-llu - y|| < ||u' = y|| by d) Therefore ||u = u'||.||u = y||.v(y) < | |u' = y||.v(y) and taking the sup of both sides we get E ||u = u'||.||u . y | | .v(y) < E ||u' » y|| »v(y) yedom(v) yedom(v) which simplifies to Ilu - u 'H Iu € v|| < Hu' e v|| f) . Let y e dom(v) IIv - v'||-||u = y||.v(y) < (v(y) => ||y € v'||).||u - y||..v(y) = (-v(y) + ||y e v'||).||u = y||.v(y) < ||y e v'||.||u = y|| < ||u e v'|| by e) Taking the sup of both sides we get E ||v = v'||.||u = y | | .v(y) < E ||u c v'|| yedom(v) yedom(v) which simplifies to llv = v'lHIu e v|| < ||u c y'|| . T 3.3.7 $(u) a formula and u ,v e SV^^ then • Ilu = v||.||$(u)|| < ||»(v)||- . 36 Proof; If §(u) i s an atomic formula the result follows from 3.3.6. Suppose the result is true for a l l formulas of length </n - 1 . Let $(u) be a non-atomic formula of length n . It is sufficient to show the result for three cases a) $ = b) § = $^  A $2 c) $ «= 3 x $ ^ Case a) 11*^ )11 = l l ^ v j l l . l l u = v|| + l l ^ M H - H u ft V|| < ||»1(u)|| + ||u fi v|| by the induction hypothesis . . Therefore -||*1(v)|| > - ( H ^ u ) ! ! + ||u ^  v||) - ( - H ^ C u J l D - H u - v|| Therefore ||*(v)|| > j|*(u)||-||u s v|| . Case b) l l « ( v ) | f = 1 1 * ^ ( ^ ) 1 ! I I ( i x ) I I -II«2(ix)II • = v|| = ||t(u)||.||u = v|| . . Case c) ||#(v)|| = E U±(v)\\ > E ||u « v M I ^ C u ) ! ! x e S V ^ x c S v ' r ^ . = ||u = v||. E | | M u ) | | = ||u = v||..||$(u)|| . *.8V<r> and the result i s proved. \ 37 T 3-3-8 I f $(x) i s a formula and u c SV^^ then a) || 3x e u$(x)|| = E (u(x)-||*(x)||) xedom(u) b) ||Vx € u i(x)|| - T T , (u(x) => ||f(x)||) i X€dom(u) Proof; || 3x € u#(x)|| = E ||y € u||-||#(y)|| y e S V ^ = E ( E u(x)-||x = y||)-||*(y)|| y e S V ^ ) xedom(u) = E u(x)( E # ||x - y||-||$(y)||) x€dom(u) y e s v ^ ^ E u(x).||3y(x = y A $(y)|| xedom(u) E u(x)-||»(x)||-xedom(u) and by the r e l a t i o n s h i p between 3 a n d v w e have || YX € U»(X)|| = -II 3x € u(-*(x)|| S u(x)-||«(x)|| X€dom(u) = TT, -(u(x).-||»(x)||) xedom(u) = TT, (u(x) => ||#(x)||) . xedom(u) Automorphisms of S V ^ In t h i s section we w i l l show that c e r t a i n automor-phisms of /3 can be extended to automorphisms of SV^^ . To be an automorphism of S V ^ a function must not only be 38 1-1 and onto but also preserve the evaluation of sentences In S V ^ i.e.. i f h i s an automorphism of S V ^ and $(u^, u 2 , u n) i s a formula then h d l ^ , u 2 , un)||) = p C h C ^ ) , h(u n))|| . i T 3.4.1 I f h i s an automorphism of £ then h can be extended to 1-1 function that maps onto . Proof: Let u e V V P ' and l e t h be an automorphism of j3 . We w i l l define the extension h of h by induction on the leve l s . , 3-4.2 dom(h(u)) = (h(x) : x € dom(u)} . ' 3-4.,3 h(u)(x') = S h(u(x)) . xedom(u) / h(x)=x' We f i r s t show that h i s 1-1 . Assume f o r a l l ri < a that i f x,x' e then x' ^ x implies h(x') = h(x) . Consider u,u' e . Suppose h(u) = h(u'), then dom(h(u)) = dom(h(u')) . Now i f x € dom(u) - dom(u') then h(x) e dom(h(u)) - dom(h(u')) by the induction assump-t i o n . Therefore dom(u) = dom(u') . Now consider 39 x € dom(u) and l e t h(x) = x' . ; h(u)(x') = E x h ( u ( y ) ) = h ( u ( x ) ) y_edom(u) h(y)=x' by the i n d u c t i o n h y p othesis and s i m i l a r l y h ( u ' ) ( x ' ) = S h ( u ' ( y ) ) = h ( u ' ( x ) ) . yedom(u ) h(y)=x' However, h(u) = h(u') so we must have h(u(x) = h ( u ' ( x ) ) and as h i s 1-1 i t f o l l o w s t h a t u(x) = u'(x) f o r a l l x e dom(u) = dom(u') . There h i s 1-1. Now as h i s 1-1 we can r e w r i t e our d e f i n i t i o n o f h as 3.4.4 h ( u ) ( x ' ) = h ( u ( x ) ) where x i s the unique member of such t h a t h(x) = x' . Now we s h a l l show t h a t h i s onto. L e t us assume f o r ri < a and a l l x e V\ p' th e r e i s an x' e such t h a t h(x') = x . L e t u e . Le t dom(u') = ( x ' : f o r some x e dom(u) h(x') = x) and u'(x') = h _ 1 ( u ( x ) ) where h(x') = x . Note t h a t h ^ M x ) ) e x i s t s and i s unique as h i s 1-1 and onto. Now dom(h(u')) = (h(x') : x' e dom(u')} = {x t x € dom(u)} as f o r each x e dom(u) t h e r e i s an x' such t h a t h(x') = Xj by the i n d u c t i o n h y p o t h e s i s . T h e r e f o r e dom(h(u')) = dom(u) and 40 h(u')(x) = h(u'(x')) = h C h - V W ) ) - u(x) where h(x') = x . T 3.4.2 If h is an automorphism of /J and h ( S V ^ ) = S V ^ then h restricted to S V ^ is an auto-morphism of S V ^ . Proof: By T 3.4.1 the r e s t r i c t i o n of h to S V ^ i s 1-1 and onto. Therefore i t i s s u f f i c i e n t to show that f o r a l l formulas ^ ( u ^ u 2 , ..., u ) that h d l K u ^ un)||) = p C h C ^ ) , h(u n))|| . We f i r s t show the r e s u l t f o r atomic formulas. Let us assume f o r TI < a and z,w e S V ^ that T) h(||z = w||) = ||h(z) = h(w)]| and h d i z € win = iih(z) € h-(w)ii . Consider u,v e SV^^ . Let z e dom(v) . a) h(||z e u||) » h( E u(w)-||w = z||) W€dom(u) E h(u(w)).h(||w - z||) wcdom(u) E h(u(w)).||h(w) = h(z)|| wedom(u) = E h(u)(h(w)).||h(w) = h(z)|| h(w)edomh(u) 41 = ||h(z) € h( U)|| also using the above we get b) h(||z = u||) -= h( TT, Mx) => ||x e u||) TT, (u(y) => ||y e z||)) xedom(z) yedom(u) = TT, (h(z(x)) => ||h(x)eh(u)|| TT, (h(u(y))=>||h(y)eh(z)||) xedom(z) yedom(u) - x TT Rz)(h(x)) => ||h(x) e h(u)|| h(x)edom(h(z)) ' -/ , TT ,-, X Nh(u)(h(y)) => ||h(y) € h(z)|| h(y)edom(h(u)) = ||h(z) = h(u)|| Now h(||u € v||) = h( S u(w).||w = v||) t h e r e f o r e u s i n g a wedom(u) s i m i l a r argument to a) above and the f a c t t h a t h(||w = v||) = ||h(w) = h(v)|| by p a r t b) above we get h(||u e v||) = ||h(u) e h(v)|| . A l s o f o r h(||u = v||) , u s i n g a s i m i l a r argument to b) and the f a c t t h a t h(||z € u||) = ||h(z) € h(u)|| and h(||y e v||) = ||h(y) e h(v)|| f o r z e dom(v) and y 6 dom(u) we get h(||u = v||) = ||h(u) = h(v)|| . We now show t h a t i f $(u,, .... u ) i s a formula u, , .... u € S V ^ ^ then v 1' * n 7 1' * n h ( | | $ ( U l J u n)||) - HfChC^), h(u n ) ) | | . We have e s t a b l i s h e d the r e s u l t f o r atomic for m u l a s . Suppose the r e s u l t i s t r u e f o r a l l non-atomic formulas of l e n g t h <_ n - 1 and f u r t h e r suppose t h a t $ i s non-atomic and has l e n g t h n . I t i s s u f f i c i e n t to show the r e s u l t f o r three cases i ) $ = - v $ 1 i i ) $ = * A $ 2 i l l ) I = 3 U $ X 42 Case i ) h(||f( U l, un)||) = h ( - |U 1(u 1, un)||) = -h(||$1(u1, un)||) = -||»1(h(u1).f h(u n))|| - p ( h ( U l ) , h(u n))|| Case i i ) hdl*^,...,1^)11) = h(||$1(u1,...,un)||.||$2(u1,...,un)||) = ||$1(h(u1),;..,h(un)||.||$2(h(u1),...,h(un))|| = H^hC^), h(u n)j| Case i i i ) h d l ' * ^ , un)||) = h(|| |u$1(u, u 1, un)||) E ||*1(u, u x, un)||) ueSV ( p ) = E H^ChCu), hC^), h(u n))|| u 6SV ( p ) = E ||$ 1(h(u 1), .../h(u n))|| u'eSV ( p ) = E II^Cu', h ^ ) , h(u n))|| u'eSV ( p ) = ||^(hC^), h(u n))|| Notice that we can change from quantification over a l l u' e S V ^ such that u' = h(u) to quantification over a l l u' e S V ^ as h i s onto. 43 L 3-4.3 I f h i s an automorphism of /3 then i ) hg - h g i i ) h " 1 = h' 1 i i i ) i d , = i d ^ . Proof s Parts i ) and i i ) are e a s i l y checked using 3.4.2 and 3 . 4 . 3 . Part i i i ) follows d i r e c t l y from i ) and i i ) as -1 - r - l — ic SVV i d j3 = h-h = h'h = i d . 3.5 Subsystems of the type In the previous sections we have discussed the properties of a r b i t r a r y subsystems of . There i s no assurance however that the axioms of set theory w i l l be J3-v a l i d i n these systems. In thi s section we are going to construct a general type of subsystem such that i t w i l l be possible to show the j 3-validity of the axioms i n these sub-systems . / We need some d e f i n i t i o n s D 3 ^ - 1 For G a group, T i s a f i l t e r of subgroups of G i f F i s a c o l l e c t i o n of subgroups of G , and a) G e r b) i f H,K e T then H fl K e T c) H c T and K a subgroup of G such that H c K then K e T . 44 D 3.5.2 T , a f i l t e r of subgroups of G , i s normal i f f o r a l l g e G and H e r we have gHg" 1 e T . The above d e f i n i t i o n i s a modification of the work of Scott developed by H. Sayeki [ 1 9 ] . Now consider a group of automorphisms of £ , we define D 3.5.3 G u = (g e G : ||g(u) = u|| = H } f o r a l l u e V O ) Now f o r each group G of automorphism of j8, and f o r each f i l t e r of subgroups of G , say T , we get a sub-system of c a l l e d by defining as follows D 3.5.4 = [u € V ^ ) : dom(u) c f o r some r\ < a and G u e T) and f o r a l l a € OR v<r> = u vlp) . a€0R a Now we w i l l show t h a ^ i n the case of a normal f i l t e r (T) T the automorphisms of V v ' that are extensions of members of G s a t i s f y the requirements of T 3.4.2. L 3.5-5 I f r i s a normal f i l t e r of subsets of G and h € G then h(V^ F^) = . 45 Proof: Assume that h ( v £ r ' " ) c f o r a l l TI < a . Let u e . Then dom(h(u)) = (h(x) : x € dom(u)} c V^'' by (D the induction hypothesis. As u e V v ' we have that G U e T . Now consider h e G . ' ! ' ' h G u h _ 1 = (hgh" 1 : ||g(u) - u|| = 31} = (g : llh^ghfu) = u|| = IL } = {g : ||ih(u) = h(u)|| = 3L ) = G h ( u ) , Now as T i s normal we have GT-/ \ e T . There-h(u) fore h(u) € V ^ ' and h(V^ F^) c V ^ ' . Now h" 1(V^ r^) c V ( r ) so h ( h ~ 1 ( v ( r ' 1 ) ) = c h(V^ F^) . Therefore h ( v ( r ) ) = For the re s t of th i s chapter we s h a l l prove r e s u l t s (T) about subsystems of the form V v ' where T i s normal.' (T) Remember that each V v ' i s determined by three things i ) a complete Boolean algebra j3 i i ) a group G of automorphisms of j3 (or more p r e c i s e l y a subgroup of the automorphism group of /3) i i i ) r a f i l t e r of subgroups of G (we w i l l , from t h i s point on, always assume that V i s normal). Embedding the Standard Universe V . In t h i s section we w i l l show that the standard (2) universe V i s isomorphic to V v ' and can be embedded into 46 D 3.6.1 Por a l l y in V we define a member of ¥ = [<X,J1> : x e y) . As for x e y we have rank x < rank y this definition i s by induction on rank. | T 3.6.2 (Scott) (2) i ) for each u e V v ' there i s a unique y e v with llu = ? l l i i ) x € y i f and only i f ||x e y|| = 3L i i i ) x = y i f and only i f ||x = y|| = 1 . This can be proved by induction. (2} This theorem shows that V and V v ' are iso-(2) (T) morphic, we now show that Vv ' c Vv ' . T 3.6.3 If T is a normal f i l t e r of subgroups of G , and G a group of automorphisms of B then v(2) c v ( r ) , Proof; Let a be an ordinal. Suppose that for a l l t| < a v ( 2 ) c v ( f ) and that for a l l u e V ^ 2 ^ , G c G . L e t Tl Tl U v € V^ 2) . Clearly dom(v) c V^r^ . Let g e G . If x € dom(v) then x =» y for some y e V and G c G Therefore 47 l l x € I(v)|| = XI g(v(y))-||g(y) - x|| . y€dom(v) . * g ( v ( x ) ) . | | i ( x ) = x|| = g ( v ( x ) ) « v(x) as v(x) i s 1 o r Dl . > S i m i l a r l y ||g(x) € v|| >.g(v)(g(x)) , and t h e r e f o r e ||g(v) = v|| = 1 . C l e a r l y then f o r a l l g e G . We have (T) g e G v and hence v e V v ' . 3.7 0 - v a l i d i t y of the Axioms of Set Theory We w i l l show i n t h i s s e c t i o n t h a t the axioms 1-7 (which does not i n c l u d e the axiom of c h o i c e ) are 0 - v a l i d i n V^r^ . We are f o l l o w i n g c l o s e l y the paper by S c o t t [17] and w i l l use h i s p r o o f of the main theorem i n t h i s s e c t i o n . T 3.7.1 ( S c o t t ) . ' Axioms 1-7 of Z-F are j B - v a l i d i n V^) . Proof; a) The axiom of e x t e n s i o n a l i t y Is VuVv(Vx(x e u <—> x e v) •* u = v) Now ||u = v|| = TT, (u(x) => ||x € v||) TT , (v(x) => ||x c u l l ) xedom(u) xedom(v) = ||Vx(x e u <-> x e v)|| . T h e r e f o r e ||Vx(x € u <—> x e v) -» u = v|| = 3L , f o r a l l (T) u,v In Vv ' and the axiom of e x t e n s i o n a l i t y i s j 8 - v a l i d 48 i n V<r> . b) Given a formula $(x; u 1 , u m ) wi t h one f r e e v a r i a b l e and parameters u^, . . ., u m the axiom of com-prehension s t a t e s V u ^ v V x ( x € v <—> x € u A $(x)) . (T) Now c o n s i d e r u, u^, ..., u n e V v ' and l e t dom(v) = dom(u) and v(x) = u(x) -1| i(x) || (where $(x) r e f e r s to the formula $(x, u^, u n ) w i t h u l ' "''' u n a s f i x e d parameters). We must have t h a t ||VwVx€u(u = w - ($(x) - |z € w(z = x A §(z))))|| = TL T h e r e f o r e f o r g e G 0 G n ... PI G u u l > T T u(x) -> ||u-g(u)|| => ||*(x)|| xedom(u) => E g(u(z))$(g(z)).||z - x|| = 31 zedom(u) hence T T , u(x)||*(x)||->||x 6 g(v)|| xedom(u) T T v ( x) => ||x e g(v)|| » 3L xcdom(v) s i m i l a r l y T T g ( v ) ( x ) => ||x e v|| - 3L xedom(g(v)) and hence G u c G y . Thus v € . Now ( V u ^ W x ( x e v <—> x e u A $(x)) <—> (Vx e v(x e u A §(x)) A Vx c u($(x) -» x e v)) T h e r e f o r e ' 49 ||Vu3Wx(x e v <—> x e u A $(x))|| = ||Vx e v(x e u A *(x))||.||Vx e u($(x) - x € v)|| - ( TT, u(x).||$(x)|| => ||x e'u|'|.||#(x)||) xedom(v) . ( TT, U ( X ) . | | « ( X ) | | - lU 6 V||) xedom(u) = 1 « 3L = 1 . Thus the axiom is j3-valid in . The axiom of foundation is Vx(Vy e x(l(y) .-» $(x)) -» Vxi(x)) where $ is a formula with one free variable. Let b = ||Vx(Vy e x($(y) -» §(x))) || . We want to show that h <_ ||$(x)|| for a l l x € . (T) (T) Assume true for x € V i ' where TI < a . Let x e Vi ' T| • a Thus for y e dom(x) we have b <. Il$(y)ll and hence / h < TT, .My) => ||i(y)||) yedom(x) - || Vy e x§(y)|| but b - TT, IIVy € z$(y),|| => | |«(z)|| zeV<r> < IIVy € x*(y)|| => ||*(x)|| . Therefore b <_ ||$(x)|| and by induction we have that the axiom of foundation is j3-valid In The axiom of replacement is Vu^Wx G u 3 y e u (3z§(x,z) -» $(x,y)) Now we must have 50 l|Vx3yQz§ ( x , z ) - *(x,y))|| = 3L . (T) T h e r e f o r e f o r a n y x e V v 1 S ||3z*(x,z) - #(x,y)1| - 3L . Now a s j3 i s a s e t a n d | | 3 . z $ ( x , z ) -» *(x,y)!|| r a n g e s o v e r j8 , f o r e a c h x t h e r e i s a n o r d i n a l cc s u c h t h a t S- | | 3 z § ( x , z ) - § ( x , y ) | | = 1 . x Now d o m ( u ) i s a s e t , s o we c a n c o n s i d e r a » s u p a x e d o m ( u ) L e t v = V^ r)x(7i } . C l e a r l y v € a n d S v ( y ) . | | 3 z § ( x , z ) - *(x , y ) | | = 2L y e d o m ( u ) f o r x e d o m ( u ) . T h e r e f o r e ||Vx e u |y e v ( 3 z $ ( x , z ) $ ( x , y ) ) | | - 3L (T) a n d c l e a r l y t h e a x i o m o f r e p l a c e m e n t i s p - v a l i d i n Vv ' T h e a x i o m o f p o w e r s e t i s V u ] ] v V t ( t e v <-> V x e t ( x e u ) ) o r e q u i v a l e n t l y • / V u 3 v ( V t e v V x € t ( x e u ) A V t ( V x e t ( x c u ) -» t e v ) ) (T) now c o n s i d e r a n y u e Vv ' a n d d e f i n e v b y d o m ( v ) = {flo*W n V ( r) a n d v ( t ) » ||t c u|| » ||Vx e t ( x e u)|| . L e t g e G u . Now ||g(u) m u - V x ( x c u -» 3 y ( y c s(ti) .A y = x)|| = X. T h e r e f o r e a s ||g(u) « u|| = 1 we h a v e 51 1 = TT ||xc u||=> S ||y c g(u)||-||y - x|| x c v ' r ) , yev' 1' : and thence v(x) <. E ||y c g(u)||'||y « x|| f o r a l l x € dom(u) . y c v ' r ' ; Now ||Vt € vVx e t(x e u)|| - TT, v(t) => TT, t(x) -> ||x e u|| t€dom(v) xedom(t) TT, lit c u|| => ||t c u|| = 1 tedom(v) Now f o r t e define t ' by dom(t') = dom(u) and t'(x) - ||x € t|| . Clearly G t 0 G u c / hence "It i s s u f f i c i e n t to show that ||Vt(Vx e t(x e u) -» t e v)|| - 3L Let b = ||Vx e t(x e u)|| f o r some t € . We want to show that b <_ ||t € v|| . Now lit = t ' | | . | | t ' € V|| < ||t € V|| . Consider y e V^r^ and l e t dom(y') •> dom(g(u)) and y'(t) = ||t € y|| f o r t-e dom(y') . Cl e a r l y y' e V ^ , ||y' c y|| = 3L and y' e dom(g(v.)) . Now l l y ' - y l l > lly'^ll-||y^g(u)||.||Vx€g(u)(x€y - xey')|| - Ily c g(u)|| Therefore Ily <= g(u )|Hly « xll = Ily; = y'||.||y c g(tt)||.||y - x|| < ||y' c g(u)||.||y' = x|| 52 hence l|x € g(v)|| = E _ ||y c g(u)||-||y - x|| y€dom(g(v)) > E , ||y c g(u)||.||y - x|| y e V< r> >^  v(x) f o r a l l x e dom(v) S i m i l a r l y ||x € v|| >.g(v)(x) f o r x e dom(g(v)) and hence G^ c G y and v e . b - ||Vx(x e t - x e u)|| = IT | | X € t|| -> ||X € U | | = TT , , t ' ( x ) => | | X 6 U|| xedom(t ) = ||Vx e t'(x € uj|| < ||t' e v|| so i t i s s u f f i c i e n t to show that b <. ||t = t'|| . We have that ||Vx e t'(x e t)|| = TT, t ' ( x ) -> ||x e t'|| - 3L X€dom(t) Now l e t x e dom(t) and x' e dom(t') b.t(x).||x - x ' l l-u(x') < ||x;- e t|| = t'.(x) < ||x' e t'|| therefore b-t(x).||x = x'||.u(x') 1 ||x e^t'H and t E b.t(x).||x * xf..||.u(x') - , E ||x e t,'j| x edom(u) x edom(t ) as dom(t') = dom(u) . Thus b*t(x).||x e u|| <. ||x € t'|| and b't(x) <_ (t(x) »> ||x e u||)-t(x) < ||x € u|| . 53 Therefore b't(x) ' l|x e u|| - b't(x) and hence b.t(x) <. ||x e t'|| or b <. (t(x) => ||x e t''||) • As th i s i s true f o r any x c dom(t) we have b < TT t(x) => ||x e t'|| = IIVx € t(x e t')|| thus xedom(t) i b <_ ||t = t'|| . We have shown that the axiom i s jS-valid i n V<r> . The axiom of union Is Vu3]vVx(x e v <—> 3 y e u(x € y)) which i s equivalent to V u 3 v ( V x e v ^ y e u(x € y) A Vy e uVx e y(x e v)) (T) Consider any u e V v ' and define v by dom(v) m U dom(y) and v(x) = ||3y e u(x e y)|| . yedom(u) By a s i m i l a r argument to the one we used i n part e) we (T) can show that G u G v and thus v e v v ' . , . Now ||Vx e v ^ y e u(x e y)|| - TT v(x) «> ||3y e u(x e y)|| xedom(v) = TT, V(x) => V(x) = 3L xedom(v) ||Vy e uVx e y(x e v)|| - TT, u(y) »> TT, y(x) yedom(u) xedom(y) o> ||x e v|| > TT, u(y) •. y€dom(u) - > ( TT, y(x).-> O y c u(x e y)||) xedom(y) TT, TT, u(x)-y(x) => l| 3 y e u(x e y)|| y€dom(u) xedom(y) Consider y € dom(u) , x e dom(y) 54 U(y).Y(x) < ||x 6 y||.u(y) < E u(z)-||x e z|| . zedom(u) = I I 3 Z € u(x € Z)|| /. U(x).U(y) »> || 3y e u(x e y)|| = 3L and the axiom i s j3-valid i n V v ' . • g) The axiom of i n f i n t y i s 3 V ( 3 X e v A Vx € v3y e v(x e y)) Now by T 3-6.3 V^ 2) c y( T) thus uJ e . Clearly ||t5e tu|| = IL and ||Vx e v ^ y e v(x c y)|| TT, v(x). E v(y)-||x e y|| xedom(v) ycdom(v) : " > TT II* e m i | | - 1 . netu Thus the axiom of i n f i n i t y i s j 8-valid i n . 3.8 A Model f o r Sentences j3-Valid i n Now that we have shown that a l l the axioms of Z-P (T) are j3-valid i n V v ' we want to show there i s a model of m / a l l sentences j3-valid i n V v ' . We do th i s i n two steps. F i r s t by placing one a d d i t i o n a l r e s t r i c t i o n of & we show that there i s a countable.subset M of V v ' which has j8-values assigned to formulas r e s t r i c t e d to M such that f o r any sentence the jS-value agrees with that of V v ' . Then we show that there i s an equivalence r e l a t i o n on M such that the equivalence classes and a suitable r e l a t i o n between them i s a model f o r a l l sentences j8-valid In M . 55 We w i l l now r e q u i r e t h a t j3 s a t i s f y the countable c h a i n c o n d i t i o n ( a b b r e v i a t e d c.c.c.) which s t a t e s t h a t i f a subset of j3 i s p a i r w i s e d i s j o i n t then i t must be countable. (T) Now i f M Is a subset of V v ; f o r a formula i $ ( x x , x n ) we d e f i n e 11*0^, . u n ) l l M f o r u,, ..., u € M by i n d u c t i o n . i ) 11^ - u 2 | | M o || U l - u2|| , e u 2 H M - € Ug|| i i ) l i $ 1 ( u 1 , u n ) A i2(\ilt u n ) | | M = ||$ 1(u 1, % ) l l M ' I U 2 ^ u i » "n^M i i i ) ||-i$(u 1, u )|| M = - l l l f ^ , u n ) l l M i v ) H 3 u * ( u , u1, u n ) | | M - S M I I $ ^ U ' u l ' ' " ' "n^M T 3.8.1 I f |3 i s a Boolean Algebra s a t i s f y i n g the c . c . c . and r i s a normal f i l t e r of subgroups of G , G a group of automorphisms of j3 . Then there i s a countable subset M o f V v ' such t h a t f o r a l l sentences * ^ l l * l l M = 11*11 . Proof: Suppose N i s a countable subset of . Consider a formula $(x, x ^ .'.., x ) and n members of N u 2 > ''•> u n • H 3 u ( * ( u , u x , u n ) ) | | = S ||'«(u, u x , ..., u n)|| . u c V ( r ' 56 Now as 0 satisfies the c.c.c. there i s a count-er) able set of members of Vv ' say f $(<u 1, un>) = [V 1,. Vg, ...} such that S ||*(u, u l f u )|| = S ||§(V., u,, u )|| . u e V ( r ) Let (N)* be N unioned with the sets f $(<u^, ..., un>) for a l l formulas § an n-tuples in N . Clearly (N)* is countable. Now let M Q . [0). and M K + 1 = (M )'* . Define W to be U M, . Clearly M i s countable. k€U) K Suppose that for a l l non-atomic formulas $(x^, ..., x n) of length <_ n-1 and for u^, ..., u n e M that 11*0^ , %)IIM = , un)|| . L e t $(x^, . . . x ) be of length n . If $ Is of the form $^  A $g or - t $ ^ clearly \\i(\x19 u n)|| M = | | u n ) | | . Suppose ^ ( u ^ u n) - 3 u*i( u» u!> "•> u n ) then || 9(vLlf ..., un)|| = S ||$1(u, u x, . .., un)|| . Now let ueV^F^ f kC^) be the least integer k such that e , and let S « maxfkCu^), k(u n)} . Therefore there Is a set (V 1 > Vg, ...) in C M such that E ||$ (u, u u )|| = S ||§ (V u u )|| r(T) x 1 n • . ieu) 1 1 1 n ueVv Therefore as £ II $ ueM 1 ( u , yxlf un)|| <_ T, I s ^ u , u x, ... ,ueV^r^ we must have that P(un, u )|| = Z IIMu, u u )|| 1 • ueM . • n " *> \\*(ult u n)|| M . Let h : j8 2 be a homomorphism. i D 3.8.2 Por u,v e M we define u H n v l f n ( J ! u = VH) T 3.8.3 « h is an equivalence relation. Proof: This follows directly from the following a) ||u » v|| = Ti b) ||u - v|| -.Uv- u|| c) ||u . v||.||v = w|| < ||u - w|| which were shown in T 3.3-6. D 3.8.4 M/=h is the structure of equivalence classes of M under =h where there i s one binary relation symbol e defined by [u] e [v] i f and only i f h(||u e v||) ~ 1 . D 3.8.5 If *(ui» u n ) i s a formula then $/h{[u^], [u n]) is the result when a l l elements u 1 58 o c c u r i n g i n $ a r e r e p l a c e d b y [ u ^ ] a n d a l l o c c u r r e n c e s o f e a r e r e p l a c e d b y •e . (i i s a s s u m e d t o b e i n p r i m i -t i v e t e r m s - t h a t i s w i t h n o d e f i n e d r e l a t i o n a l s y m b o l s ) . T 3.8.6 T h e r e i s a n h : & - 2 s u c h t h a t M / s h u n d e r t h e (T) r e l a t i o n e i s a m o d e l o f a l l t h e s e n t e n c e s j 3 - v a l i d i n V v ' P r o o f : C o n s i d e r a l l sums o f t h e f o r m S ||* (x , u . . , u )|L , u 1 f u e M . x e M 1 n A s M i s c o u n t a b l e t h e r e a r e o n l y a c o u n t a b l e n u m b e r o f s u c h s u m s . B y t h e R a s i o w a - S i k o r s k i Lemma T 1.4.4 t h e r e e x i s t s a n h : B -» a t h a t p r e s e r v e s a l l t h e s e sums i . e . h ( S ||* (x , u , u_ )|| M ) x e M n M = E h ( | | * ( x , u u )|| ). x e M l n m H $ l ^ u l ' ' " * u m ^ = ^ a n d b y o u r a s s u m P t i o n / . • . i ^ / h ( [ u ^ ] , [ u m ] ) i s f a l s e i n M / = h a n d t h u s $/h([u1], . [ u J ) i s t r u e i n M / = h . I f ||*(u l f . . . , u m ) | | « Q we h a v e t h a t $ / h ( [ u - L ] , [ u m ] ) i s f a l s e i n M/= , b y a s i m i l a r a r g u m e n t . 59 By the definition of [u] i f ||u = v||M » 3L then [u] = [v] and i f ||u = v||M •» CD then [u] 4 [v] . By the definition of the binary relation € i f ||u e v|JM =» 1 then [u] e [v] is true In M/sh and i f ||u e v||M = (D then [u] e [v] i s false in M/=h . Now assume that for any non-atomic formula i(vLls u m) of length < n-1 that «/h([u 1], , [u m]) is true in M/% i f l l * ^ , . u m ) l l M = 1 and Is false In M/ah If ||«(Ul, u m)|| M - Q . Let $(u,, .... u ) be a non-atomic formula of l m length n . We consider three cases: i ) i(ult uffl) - ^ ( u ^ u m) A $ 2 (u 1 , u m) . Now i f ||§{\x-y, um)H]yi 8 3 1 then II^(uj, u m ) l l M - 1 and p^u.^ . . . , um)|| M - IL and hence by our induction assumption we must have that i/hftuj], [ u J ) = $ 1/h([u 1], [ u J ) A i 2 M i v i 1 ] t [um]) is true in M/=, . If ||$(un, u )|L » 0) then 60 | | $ 1 ( u 1 , . . . , u m ) | | M <. - | | $ 2 ( u 1 , . . . , u m ) | | a n d a s {b € j3 : h ( b ) «= CD) i s a p r i m e i d e a l t h e n o n e o f h ( | | $ 1 ( u 1 , . . . , u m ) | | M ) , h f p g f ^ , . . . , u m ) | | M ) i s CD e a . A s l e n g t h <. n-1 a n d l e n g t h - § 2 <_ n-1 we h a v e b y o u r i n d u c t i o n a s s u m p t i o n t h a t o n e o f j $ 1 A ( [ u 1 ] , [ u J ) , $ 2 / h ( [ u 1 ] , [ u m ] ) i s f a l s e i n M/H^ a n d c o n s e q u e n t l y t h e i r c o n j u n c t i o n i s f a l s e i n M/% . i i ) I f H u ^ . » . , u m ) = - i $ 1 ( u 1 , . . . , u m ) i t i s e a s y t o s h o w t h a t S/hCfu^], [ u m ] ) i s t r u e i f • H*^, . . . , u m ) | | M » 1 a n d f a l s e i f v ^ )H M = CD. i i i ) i(ult u m ) j - 3 u * 1 ( u , ult . . . , u m ) I f '\\i(\ilt . . u m ) | | M - 1 t h e n £ | | $ ^ ( u , u ^ , . . . , um)lljvj - a n d b y o u r c h o i c e o f h • . • •/ we h a v e h ( S ||Mu,. u u )|L) ' u e M m n = E h ( | | $ , ( u , u-, . . . , u )-|| ) = 1 . u e M / T h e r e f o r e t h e r e m u s t b e a v e M s u c h t h a t h ( | | § ( v , u 1 , u m )||) = Ti a n d b y o u r i n d u c t i o n a s s u m p t i o n i^/h([v], [u^] s . . . , [ % ] ) i s t r u e i n M / = h . T h e r e f o r e * / h ( [ U l ] , [ u m ] ) = 3 [ u ] $ 1 / h ( [ u ] , [ U ; L ] , [ u m ] ) i s t r u e i n M / a ^ . S i m i l a r l y i f H*^, U ^ H M - 0! t h e n $ / h ( [ u , ] , [ u ] ) i s f a l s e i n M / s , . Now a s J 61" we have shown that f o r a l l sentences $ j3-valid i n (T) v , l l $ l l M ~ 3 1 then we must have $/h true i n M/=h Now as we have shown i n T 3.7.1 that a l the axioms Z-F are p\-valid i n V^ r^ we can see that f o r each . (where 0 s a t i s f i e s c.c.c.) there exists a model of Z-P + (T) a l l sentences jS-valid i n V v ' or equivalently Consis(Z-P + a l l sentences jS-valid i n V ^ ) . / 62 CHAPTER 4  THREE MODELS OF SET THEORY 4.1 Introduction Having developed a method of constructing models i n Chapter 3, we now proceed to study three d i f f e r e n t models i n order to e s t a b l i s h the desired independence r e s u l t s . In each of these models the axiom of choice i s not v a l i d and, i n f a c t , the ordering p r i n c i p l e i s not v a l i d i n the second and t h i r d model. As shown i n Chapter 3, every subsystem (T) V v ' gives r i s e to a model of Z-F and any sentences jS-valid i n V^ r^ . In t h i s -Chapter only w i l l be demonstrated, and the statements which are to be true i n the model w i l l be (T) shown to be 0-valid i n V v 1 . 4.2 General Remarks In this chapter we w i l l be dealing with spaces of (MXX the form X = 2 , where l i s countably i n f i n i t e . Now the discrete topology on 2 gives us a product topology on X, and the measure |i on 2 with M((0)) • 1/2 , (i(fl}) • 1/2 induces a product measure on X . D 4.2.1 X = 2 U ) X I, I f B i s the set of Borel subsets of X and T) i s the i d e a l of measure zero sets, then the Lebesgue 63 algebra of X i s £ = B/r\ , i . e . j3 i s the set of a l l equivalence classes of Borel subsets of X produced by the equivalence r e l a t i o n : A equivalent to C i f and only i f H(A - C U C - A ) = 0 . This i s a well known Boolean algebra that s a t i s f i e s the c.c.c. Now i f G i s a group of permutations of I , we can extend G to a group of automorphisms of 0 by defining g(p)(<n,i>) » p(<n,g(i)>) f o r a l l p € X g(A) = (g(p) : p e A) f o r a l l A e B g([A]) = [g(A)] f o r a l l [A] e j8 It Is clear that t h i s extension i s well-defined, as f o r a l l g e G we have: g i s a homeomorphism of X and that g preserves measure. In t h i s chapter we w i l l sometimes use the same symbol f o r a permutation of I and f o r an automorphism of 0 . Even though they are completely d i f f e r e n t functions, the extension of one to the other i s so natural that no con-fusion should r e s u l t . / I f f o r some set L and f o r each i e L we have G i a subgroup of G , we can use these sugroups to generate a f i l t e r of subgroups, as each G i can be considered a subgroup of automorphisms of 0 . D 4.2.2 G a group of automorphisms of j3 . G. a subgroup 64 of G . for each i e L . Then T i s the f i l t e r of subgroups generated by the G^  , If H c r i f and only i f D G, c H for some J a f i n i t e i e J 1 i subset of L . Now for T constructed in this manner we have the following theorem: T 4.2.3 If 0± - (g e G|g(i) - i) for I e I and i f f is generated by the subgroups G^  , then T i s normal. Proof: Consider g e G . gG.g"1 - fgg'g^lg'Ci) - i for I e 1} = ( g ' l g ^ g ' g f i ) = i for i e 1} = t V l g ' g ( i ) = g(i) for i e 1} = Gg (D Therefore gG^g"1 e T for a l l /g e G and i e I , and T is normal. (T) We now show that in Vv ' , where T is generated by a set of subgroups of G, say G± where i e L , then (T) every memher of Vv ' in a certain sense depends only on a f i n i t e subset of L . 65 T 4.2.4 T a f i l t e r of subgroups generated by [G^ : i e L}. (T) Then for x e Vv ' there is a f i n i t e subset of L which we wi l l denote by A(x) such that n G. c G and i f J c L ieA(x) 1 x and n G, c Q then A(x) c j . i e J 1 • Proof; ' (T) Consider x e Vv ' . Clearly G e T and so there must be a f i n i t e J c L such that fi c G . i e J x Let Z(x) « n(J : D G. c G ) . We must show that i e J 1 x D G. c G . Suppose fl G. fl G c G and ieA(x) 1 x ieA 1 m x fl G. fl G c G with m 4 n . Now i f g,h e G v then ieA 1 n x x gh e G x as ||ih(x) » x|| - g(||h(x) . g " 1 ^ ) ! ! ) > g(||x = h(x)||.||x «= T\r)\) > g(g _ : L(llg(x) - x||)) - 1 . Now i t is simple to check that any f e fi G. can be ieA(x) 1 expressed as a product of functions from fi G. fi G_ and - ieA 1 m fi G. fi G . Therefore fi G. c G . and consequently i f ieA 1 n ieA 1 x fi 0. c. G and fi G. c G then fi G. c G i e ^ 1 x i e J 2 1 x l e f J ^ J g ) 1 x Clearly A(x) has the desired properties. In some of the following sections we w i l l be dealing 66 with function© i n the model. To consider functions we must examine the ordered pairs of the model. D 4.2.5 For u,v e V^ r) we define after Scott I a) ( u } ( r ) = (u) x (31} b) (u,v} ( r ) « (u,v} x (31 } c) <u,v>(r) - Uu}(r),(u,v}(r).} x (31 } L 4.2.6 fry For u,v € Vv ' we have a) (u} ( r>, ( u , v } ( F \ <u,v>(r) e V ( r> b) ||k e [u} ( r)|| -•..||x = u|| c) - ||x e (u,v} ( r )|| = ||x = u|| + llx - v|| Proof; a) Clearly G c G m , G n G„ c G , r* and U u v (u,v} ( T ) G u ° G v C G (T) ' T h e r e f o r e • <u,vV ' lu)(T), (u,v} ( r>, <u, v> b) ||x ,e (u}(r>|| = S (u)<r)(y)||y - x||- Hu -x| yedom((u}) c) ||X € (U,v}f r?.||- S'.. (U,v}^ r)(y)||y = X|| . yedom(u,v}' ' - = 1 . ||x ••• u|| + 31 ||x r=v|| = ||x » u|| + ||x m v|| . 67 We see then that <u,v>v has a l l the properties of an ordered p a i r i n V v ' . There i s one r e s u l t concerning f i n i t e sets i n (T) (T) a r b i t r a r y V v ' that we can prove. I f a member of V v ' considered as a function mapping into /3 i s f i n i t e , that i s (T) f i n i t e i n the set theory that V v ' i s being constructed in, (T) then i t i s f i n i t e 1 i n V v ' . The converse of this s t a t e -ment i s not true, i t i s possible to have an i n f i n i t e set of (T) members of V v ' such that the constant function from that set to 3L i s f i n i t e 1 i n . T 4.2.7 For a l l K ' e such that K ' f i n i t e ( i n the set theory V v ' i s constructed in) land ||K = K'|| = l we have ||L C K|| <. ||L f i n i t e 1 H f o r a l l L e . Proof; Consider K' such that K ' e and | K ' | « 1 I.e. K ' = (<u,b>) f o r some u 7 e . ||K' f i n i t e i | | > O x V y ( y e K ' - y = x)|| = S TT (Ily e K 'H => ||y - xii) xeV^ ' yeV^ ' > TT, % 0 | | y = u|| «> ||u = y||) = 1 yeV<r> Now assume that f o r K ' e V^-V and (K' I <_ n-1 we have ||K'•.•finlte 1|| • - 31 . 68 Suppose |K'|••- n and K' e i . e . K' - {<U;L,bn>, ..., <un,bn>} . Clearly . A . [\i , u n - 1 ) x [1 ) i s i n V^ r) as G n . . . n G c G. and by our induction u l u n - l R 1 assumption ||A finite ^ J I = 1 . Let v = A U ( u n ) ^ • Now v e V ^ ) a s 1 < } < n Q± cz G y . Also ||x e vl| - E v(y).||y - x|| - Z A(y).||y = x|| yedomfv) y€dom(A) + llx - u J - ||x 6 A|| + ||x . un|| This means that v i s the union of A and singleton u i n ||K' f i n i t e | | > ||K' e V||.||A f i n i t e ^ = TT, K'(y) => ||y c v|| yedom(K') = TT b, => 3L K K n 1 Consider L € ' ||L f i n i t e 1 | | >. ||L C K'H-HK' fini.te.JI = ||L c K'|| . ||L c K ' l i • ||K - K'|| . ||L C K | Model I This model i s s i m i l a r to the model + developed by Mostowski [14]. The basic ideas f o r most of the proofs i n t h i s model come from Levy [12], Let X m 2 w X ? where Q i s the set of r a t i o n a l 69 numbers having the usual ordering, and l e t 0 be the Lebesgue algebra of X . A l s o , l e t G = fg : Q - Q|g Is 1-1 and onto and f o r x < y we have g(x) < g(y)} and GjL m (g e G|g(i) - i ) f o r a l l i e Q . Now G i s a group of permutations of Q and each G^ i s a subgroup of G . As we have shown i n 4.2 we can consider G as a group of automorphisms of 0 and generate a normal f i l t e r of subgroups T using the subgroups G i , ( T V I e Q . We know from Chapter 3 that V v ' w i l l give r i s e (T) to a model of Z-P + a l l sentences j3-valid i n V v ' . Now we w i l l consider some non-standard subsets of (T) the integers In V v ' . Let dom(u^) = dom(tu) and ! u ±(n) - [(p e X : p(<n,i>) «= 1}] f o r a l l I e Q . C l e a r l y c n G i c G u ' t h e r e f o r e u i e v f o r a l l i e Q . Now i f ±43 then \WA - u.|| = TT^Cn) <«> u (n) 7 1 J n<tu 1 J • [(p e X : p(<n,i>) = p(<n,j>) f o r a l l n e m)] =- Q I t Is also easy to show that \\u^ e Pw|| = 1 but ||ui €'P*w|| = (D (see Scott [20] pp. 65-66) which means the (2) u A ' has no Isomorphic image In the standard universe V v ' . Let U be the constant function 70 [ u ± : i e Q}x{H} . For any g e G we have ||g(U) - u|| » 1 , (T) hence G c Gy and therefore U e Vv ' . (T) Now for x e Vv 1 we define I(x) - { u ± : i e A(x)} x (1) . I(x) e as fi Cr. c G T / \ . For A c Q and A i€A(x) 1 I ( x ) f i n i t e we define I A «= : i e A) x (1) , and as fi G. c G T we have I. e . ieA 1 XA R T 4.3.1 ||U is in f i n i t e 1 | | - 1 Proof: Let L = {I A : A c Q , A fin i t e ) x [1) . Clearly G c G L and thus L e . Now )L c p(u) || . ||Vx e L(x c U) || TT, L(x) »> ||x 6 U|| xedom(L) TT l l i A c u|| A C Q / * A f i n i t e TT TT, I A(x) -> ||x e U| A C Q x€dom(l.) * A f i n i t e Clearly ||3x(x e L)|| « 1 , therefore ||L ^  0\\ = 1 . Now |maxel(L) ^ 0|| = O x e LVy e L ( - x £ y)|| . 2 L(x); TT, L(y) -> -(llx c y||.|lx ^ y| X€dom(L) y€dom(L) . T, T T - ( I H A <= i B | | - | | i A / L U ) A C Q B c Q . a M * A f i n i t e B f i n i t e Now.if A [± l t ± 2, i n ) with i 1 < ± 2 < ... < i Let A* « ( i _ , i „ i _} . Therefore i 1 n n+l ||maxel(L) / 0\\ < S - ( | | l A c I A J|.||l A 4 I A * i A c Q A f i n i t e but ||IA c i || . TJ. and ,lTA * V " " "I^A 8 5 IA*'I " ( I A * ( u i -> K e *A n+l n+l > -( S 1|u = u, ||) = 1 1<J<P x j ^n+l so we must have ||maxel(L) 4 $\\ - ® • ||maxel(L) = 0|| . -||maxel(L) 4 0|| = 3L . Hence ||u i n f i n i t e ] L l | > ||L c P(U)||||L 4 0lll|maxel(L) - J2f|| = D 4.3.2 For s,t € Q we define U S m {u r : r < s) - [u r : t < r) uJ = [u r : s < r < t) and for convenience let be [ u l instead of 0 . 8 S L 4.3.3 i ) . For a l l y e there Is a y ' e such that dom(y') - dom(U) and ||y « y'1| > ||y c u|| 72 r(ry i i ) i f y € VK } and i f A(y') « ( i ^ ..., i j then i z,w e U . k + 1 we have y'(z) « y'(w) , k = 0, 1, . n x k (where i Q - » and i n + 1 ° +09) • Proof: i ) Let dom(y') «= dom(U) and l e t y'(u ) «= ||ur e y|| f o r u e dom(U) . y' e as G c G / . Now *^ y y lly' c y|| «= TT, , V ( x ) -> llx e y|| = l ' also xedom(y ) ||Vx e U(x e y x e y')|| B 1 thus lly - y'll > IIY' C YW'PX e U(x € y - x e y')||-|ly c XT 11. = lly c u|1 . i i ) Let y e and A(y') « ( i _ , . i ) . Suppose i u^,u e U< . Now there i s a g e n G. c G / r 8 A k ieA(y') 1 y such that g(r) = s and g(p) = p f o r p € Q - ( i ^ * 1 ^ ! Therefore 1 - ||g(y') =» y'll < g(y')(u B) <=>"y'(u) - g(llu B € y'/H) <=> y'(u s) = l|ur e y'll<=> y'(u B) = y ' ( 0 <=> y'(u a) • Hence y ' ( u r ) •• y ' ( u s ) • T 4.3.4 - ||U i s f i n i t e 6 H » 3L 73 Proof t ||U is f initegH >. ||VS(S c U A S i n f i n i t e 1 - S cannot be well ordered) || = TT IIS <= U||« ||S i n f i n i t e 1 || = ||S cannot be well ordered || (T) We want to show for any S e,VV ' that ||S c u||.||S i n f in i t e 1 | | <_ ||S cannot be well ordered | | . If Hs c U||'||S i n f i n i t e . ^ =» CD i t is clear , so let us assume that ||S c U||-||S infinite-JI > CD . Let S' be as in L 4 . 3 - 3 . CD < ||S c U||.||S Infi n i t e ^ ! <. ||S' in f in l te ] L l| as ||S c-u|| < ||S - S'|| . Now i f ||S' in f in i te || > CD there must be a (s,t) c Q such that x (9) c s ' and 9 > CD . Letting dom(S") - and S"(x) «=S'(x) for x e we have S" e V^' and ||s* c S' || = 1 . Now 3 ||S cannot be well ordered || _> ||s'cannot be well ordered||• ||S - S#|| >. ||S' cannot be well ordered ||• ||S c u|| J> ||S* cannot be well ordered||-||S c u|| It is clearly suff ic ient to show that ||S" cannot be well ordered || >. ||S' 4 0|| . Let §(R) be the sentence VT(T c S" - (^x e TVy e T(xRy))_).. . This sentence Is the extra condition to make an ordering a 74 well ordering. ' Let b = ||S' yi 0\\ . •||*(R)||- TT, l | T £ S ' | l - > ( = T(x) TT T(y) => ||xRy||) T e V ( r ) xedom(T) y €dom(T) Now A(S") U A(R) i s f i n i t e , therefore there must be an open i n t e r v a l of Q say (p,q) included i n (s,t) such that (p,q) 0 (A(S") U A(R)) = 0 . q L e t t i n g dom(T) « U p and T(x) •> S*(x) f o r x e dom(T) we have T € and llT c s ' l l * 1 . Therefore ||»(R)|| < E • T(x) TT, (T(y) => ||xRy|| ) xedom(T) yedom(T) Now f o r each t e (p,q) l e t t * - t+(q^t)()T PV I f x m u t we denote by x* and I f x « u f c 4 t then we denote u f c by x # . We define g T e G by i r k k t (p,q) / k* k e (p,q) and notice that grp € G R . ||*(R)II< E T(x) • (T(x*) =>/ ||xRx*||) and xedom(T) ||*(R),|| < E T(x)-(T(x #) => HxRxJI) . Therefore xedom(T) gT(||$(R)||) = ||f(g T(R))|| = ||l(R)|| < E g T ( T ( x ) ) ( g T ( T ( x # ) ) => ||x*Rx||) x€dom(T) now &p(T(x)) - gT(||x € S||) ||x* e S 1| «= T(x*) and g T ( T ( x # ) ) m grpdlx, e Sl|) » ||x e S|| m T(x) Therefore 75 H*(R)H < S T ( x ) - ( T ( x * ) -> ||xRx*|l) . S T ( x * . ) ( T ( x ) - > ||x*Rx||) xedom(T) xedom(T) Now ||R i s a well ordering of S"|| .<. ||§(R)||.||R i s an ordering of S"|| + (-b) < ||$(R)||.||Vx c S"Vy G S" (x / y (xRy <-> -jyRx))|| + (-b) < ||f(R)||. TT, , S'(x) -> TT, , S"(y) xedom(S ) y€dom(S ) => (l|xRy|| <=> -HyRxH) + (-b) < ||*(R)||. TT T ( x ) => (T(x*) (||xRx*|| <«>.-| lx*Rx||) + (-b) xedom(T) as dom(T) c dom(S) and ||x yi x*|| > 31 . .V ||R i s well ordering of S"|| < S T ( x ) - T ( x * ) . ( T ( x * ) *=> ||xRx*||)(T(x) ~> ||x*Rx||) xedom(T) TT T ( x ) . T ( x » ) => (||xRx*|| <=> -||x*Rx||) + (-b) X€dom(T) < S T(x)-T(x*)(||xRx*||-||x*Rx||)(||xRx*|| <=> -||x*Rx||)+(-b) xedom(T) = Q + (-b) Therefore ||VR(~.R well orders S")|| >. b = ||S 4 0\\ hence ||S" cannot be well ordered|| _> ||S 4 0\\ and we are done. T 4.3.5 ||P(U) i s f i n i t e f i | | => 3L . Proof; As shown In the proof of T 3.7.1 e) there i s a v e V^'' such that ||v m p(U)|| = 3L . Now 76 ||v i s . f i n i t e g j l - | | V x ( x infinite - j ^ A x c v - x can't be well ... ordered)|| - TT | |x i n f i n i t e , II « | |x c v || x c V ^ => T l x can't be well ordered|| 1 . (T) Also f o r x e V we have | | x " i n f i n i t e 1 A x c v|| => | | V E ( E f i n i t e ^ ^ - ] y e v(y e x A y £ E ] = H thus | |x i n f i n i t e , ||-||x c v|| < TT l lE f i n i t e , || 1 "E6v(r) 1 -=> ' S v(y).||y 6 x||-||y k EH yedom(v) Por each A f i n i t e , A C Q l e t us consider the following sets. Suppose A « ( i , , ..., i } then define I i 1 i m i V ± ( A ) - u ± x{b*)uu 1 1x{b*}uu 1 2x{b 2iu...uu^^^ 1 1 1 m where b 1 = 3L i f i s l(mod 23) and CD otherwise, 1 < i < 2 2 m + 2 . Cle a r l y f o r 1 < i < 2 2 m + 2 V^A) e as n G c G , A ) . i €A 1 V A ' Por y € VF) define ( y ) ± - V ± (A (y)) and k(y) = 2 2 ' A ( y ^ + 2 , i ( 7 ) = 2|A(y)| + 2 . Now I f dom(y) = dom(U) then by L 4.3.3 s v l l y » iy)A - - s . • TT (e, <->.b*) l<i<k(y) ? 1 • l<i<k(y) 1< JOt(y). 3 3 77 t h i s i s easy to check using the f a c t that 0j <=> CD = - 8 j and 9j <=> 1 « 9j . Consider P - (u e : dom(u) = U and A(ui c A(x)) jX (1)' . P e as fl G. c G-p . ieA(X) 1 F Let Z = U (v, (A) : 1 <_ i <_ 2 2' ! A! + 2) x ri) ACA(X) 1 Z e -as n G. c G 7 . ieA(X) 1 6 Now dom(Z) i s f i n i t e thus ||Z i s f i n i t e - ^ = 1 by T 4.2.7. Now ||P c Z|| = TT F(y) => ||y € Z|| yedom(F) Edom(F) yeyedom(F) wedom(Z) T T - . s - . llw = yi edom > T T F . z' J l ( y ) i = yll - i ' ye dom(P) l<i_<k(y) Therefore ||P f i n i t e j l >_ ||F c Z||-||Z f i n i t e 1 j | = 1 . Combining t h i s with our previous remark we have ||X i n f i n i t e ||. ||X c vj| < Z , v(y.) • ||y e X||.||y t F|| yedom(v) Z , Jly <= U||.||y e X||.||y * P|| yedom(v) < Z • ||y - y'||-||y € x||'.'||y * F|| < z Jy', € X||.||y' $ F|| y€dom(v) . yedom(v) < £ , ,(||y' e X||.||y/., * P||. Z ||(y')i = y ' i | ) yedom(v) l<i_<k(y') < Z , . Z , ||(y ;0i € X||.|i(y')i i Fj| yedom(v) l_<i_<k(y') 78 Now i f f o r y e dom(v) we have ( y ' ) i G dom(F) then | | ( y ' ) i e P|| = (D and c l e a r l y ' ! | | ( y ' ) i € X||.||y^ k P|| <. ||X can't be w e l l ordered|| . I f f o r y e dom(v) we have ( y ' ) i £ dom(P) then there must be an 1 € Q such that i e A ( ( y ' ) 1 ) - A(X) . T h i s means t h a t the values of ( y /^i( ui<;) ™ust change as k v a r i e s over any i n t e r v a l ( r , s ) c Q such t h a t i G ( r , s ) « L e t ( r , s ) be such an I n t e r v a l with the added c o n d i t i o n t h a t i t i n t e r s e c t s A(X) u A ( ( y ' ) 1 ) o n l y a t i . L e t the values t h a t ( y ' J ^ f u ^ ) assumes as k G ( r , i ) , k e ( i , s ) and k - i be 9^, 9 2 and 9^  r e s p e c t i v e l y . We can r e a d i l y see th a t [9, ,90,9,) = f(D,3L) . Now f o r q e ( r , s ) d e f i n e As i e A ( ( y ' ) , ) - A(x) and ( r , s ) n A(X) = 0 we have k k k ( r , s ) q e ( r , s ) " * 1 S q ( ( y ' ) l ) o n l y d i f f e r i n the value s they assume on and (r , s ) 0 A(X) o 0 L e t R = (<Iq((y')±),uq>(F) : q e (r , s ) } x R G v as G p c G R . Now l l g q C C y ' ) ! ) . . - S j ( ( y ' ) - i > H ( 0 l < = > e 2 ) , ( 0 2 < m > 0 3 ) = 0 1 f 0 r q / j as (9 1,9 2,9 3) = {(D,l) . A l s o . ||u - Uj||= 0 f o r 79 q 4 j • Using these facts i t i s easy to show that ||H i s 1-1 and maps P onto U^ ,x «= 1 . • Let K « 'x [ l ] . Now ||X can't be well ordered|| >. ||P can't be well ordered|| • ||P c x|| >_ ||P c xll-HJP! = !K|||-||K can't be well ordered|| >. ||P c X||.||K infinite-JI-||K C U||.||U i s f i n i t e 6 | | > ||P c X||.||K i n f i n i t e ^ = ||P c x|| = || ( y ' ) ^ e X|| as ||U i s f i n i t e 6 H = 1 by T 4.3-4 and ||K i s i n f i n i t e ^ ! = 1 can be shown using the same proof as T 4.3-1 but replacing U by K . Therefore f o r y € dom(v) we have \\(y')± e Xj| -1| ( y ' ) ± / P|| < ||X can't be well ordered|| and thus ||P(U) i s f i n i t e 6 | | « 3L . We w i l l now show that the ordering p r i n c i p l e holds i n v' r> . ' , D 4.3-6 A,B <= Q A,B f i n i t e A-?B i f and only i f |A| < |B| or i f |A| «= |B| and A i s less than B under the lexicographical ordering Induced by < . L 4.3.7 If g e G and A,B are f i n i t e subset of Q such that A~3B then g(A) —3g(B) . The proof of thi s lemma i s l e f t to the reader. 80 L 4.3.8 I f x e V^ r) and g e G then g(A(x)) » A ( g ( x ) ) . Proof; Suppose g~^"hg e 0 G. , then i e A ( x ) 1 ||g" 1hg(x) B x|| m 1 . T h e r e f o r e i f hg(q) = g(q) f o r q e A(x) then ||hg(x) = g(x)|| = 1 , or i n oth e r words i f h e n G. then h e G— / v . By the d e f i n i t i o n o f i € g ( A ( x ) ) 1 «< x> A ( g ( x ) ) we must have A(g(x)) c g(A(x)) . By r e v e r s i n g the above argument we see th a t g - 1 fl_ G. g c G . Now i e A ( g ( x ) ) 1 x g " 1 n_ g i s the s e t of a l l h e G such t h a t h(q) = q i € A ( g ( x ) ) f o r q e g " 1 ( A ( g ( x ) ) ) . Now by the d e f i n i t i o n of A(x) we must have A(x) c C . T h e r e f o r e |C| >^  |A(x) | as g " 1 i s 1-1 i t f o l l o w s that | A (g(x))| > |A(x)( - |g ( A ( x ) ) | . Thus A(g(x)) = g(A(x)) . (T) We now show th a t every s e t i n V v ' can be ordered. B a s i c a l l y the proof r e s t s on the f a c t t h a t a l l members of (T) V v ' can be a s s o c i a t e d w i t h a f i n i t e subset of Q , which (T) can be ordered. I f two elements of V x ' are a s s o c i a t e d with the same subset then we can use the w e l l - o r d e r i n g p r o -(T) p e r t y of the s e t the o r y V v ; i s c o n s t r u c t e d i n , t h i s i s because they depend on the same members of Q and any f u n c t i o n t h a t keeps these members f i x e d w i l l keep f i x e d any d e s i r e d o r d e r i n g of these elements o f . 81 T 4 . 3 . 9 ||Vu3R(R orders u)|| = 3L . Proof; (T) Consider u e V v ' . We have used the n o t a t i o n I ( x ) f o r the f i n i t e subset of U i n t h a t x "depends" upon. Now f o r I ( x ) to occur i n a formula as a f r e e occurence of x we must show t h a t the f u n c t i o n t h a t takes (T) x i n t o l ( x ) e x i s t s i n V v ' . Let P = {<x,I(x)>( r' : x e dom u} x (3L } . Now by L 4 . 3 - 8 g(A(x) m A(g"(x)) , t h e r e f o r e I ( g ( x ) ) . g ( l ( x ) ) . So G c G„ and P e . U r Now f o r a l l A,B f i n i t e subsets of Q we have the o r d e r i n g A — $ B or B - ^ A , i t would seem n a t u r a l t o extend t h i s o r d e r i n g t o the s e t s I ( x ) i n . Let R' = ( < l ( x ) , I ( y ) > ( r ' : x,y e dom(u) and A(x) A( y ) } x ( l } By L 4 . 3 . 7 A B i m p l i e s g ( A ) — * g ( B ) and i t i s c l e a r t h a t G c G_, thence R' e . L e t U rt (T) dom(WA) = f<x,y> v ' : x,y e dom(u) and A(x) » A(y) = A) . (T) Using the w e l l o r d e r i n g of the s e t theory which V v ' Is c o n s t r u c t e d i n we can order the s e t (x : x e dom(u) and A(x) = A} and w r i t e i t as (u^ : § < n) . We now d e f i n e W A « x , y > ( r > ) . ( S' ||x=u H|y=uJ|>( fT K^lk!|u^||) +||x=y|| 82 we note t h a t D G . c G w , and hence W. e . ieA 1 WA * We wish t o show t h a t f o r a l l x,y,z e dom(u) such t h a t A ( x ) = A(y) = A ( z ) » A t h a t : i ) W A(<x,x> ( r )) = 1 i i ) ||<x,y> ( r ) € WA| l<ll<y,x>(r) e WA|| < i i i ) !l<x,y>(r) * WA| l-ll<y,x>(r) * WAH -i v ) ||<x,y> ( r ) e WA| l-ll<y,Z>(r) e WA|| < i ) and i v ) are s t r a i g h t f o r w a r d , f o l l o w i n g a re the pr o o f s of i i ) and i i i ) . a) ||<x,y>(r) e WA||.||<y,x>^) e.WA|| = ZZZ W A(<Z 1,W 1>^)).||Z 1 «= x||.||W1 « y|| <Z 1,W 1>^ r^edom(W A) V W A(<Z 2,W 2>^)).||Z 2 = y||.||W2 = x|| . <Z 2,W 2> ( r )edom(W A) <Z 1,W 1> ( r ) €dom(W A) <Z 2,W 2>( r^edom(W A) § 1 < n 1 < a ? 2<n 2<a + 8-llx = y|| where b i s enual to ly = u |.|x = u |.|x = u II - ||y = u |  *1 ^1 %2 ^2 . ( | | y ^ u ||.||x ^ u '||+||y / u . ||.||y/« || H 5 2 H ^2 + llx > ^ l l ' l l ^ * yll+Hx ^  Un-H *ll x / u? Il) 83 < I ly - u . M | y ^ u . II + ||x 4u ||.||x = u || = CD . h h "1 ; / . ||<x,y>^' € WA||.||<y,x>(r) € W j = 9 .||x = y|| < ||x » y|| b) Let d ( x , y ) - £ ||x «= u ||.||y « u || ?<r|<a 9 -n e ( x,y) = T T l l x 4 u Ij + ||y ^  u J | . ' 5<n<a 1 1 9 Clearly e ( x,y) - - d ( y , x ) . ||<x,y> ( r' rwA|| = - E (d(Z,W)e(Z,W)+||Z = W||) <Z,W>'r^edom(WA) -11= - x||.||w = y|| < ( d ( y , x ) + e ( y , x ) ) . | | x + y|| < H<y,x> ( r> € WA||.||x / y|| : s i m i l a r l y l l < y , x > k WAH < ' | | < x , y > ( r > •€ W A M l x / y l l Therefore . j l < x , y > i WA||.||<y,x> k WAH < ||<y,x> e WA||.||<x,y> e WA|| • ||x / y|| < l l x = y|| .||x 4 y l l = CD using the r e s u l t established i n a). Thus we have show that has the properties i ) - i v ) . (V) Let dom(R) «= (<x,yV ' : x,y e dom(u)} and l e t R(<x,y> ( r' - | | l ( x ) - 4 l ( y ) H + | | l ( x ) - l(y)|| £ H l ( x ) = I A || .||<x,y> ( r ) e WA|| ACQ A f i n i t e where ||l(x) -i I(y)|| = ||<P//x,P/,y>^r) e R'|| . We use P"x (T) to denote the image of x under P i n V v ' . Now the properties 84 •a) |JVx e u(xRx)|j = 1 b) ||Vx e uVy e u(xRy v yRx)|| = 1 c) || Vx e uVy e u(xRy A yRx •* x = y)|| = 1 d) ||Vx e uVy g uVz G u(xRy A yRz -» xRz)|| = 1 are easy to check, as they are d i r e c t consequences of the ordering properties of and conditions i ) i v ) above. Model II This model i s the one constructed by Scott to show the independence of the axiom of choice i n a Boolean valued model. Let X = 2 U ) X u , and j3 be the Lebesgue algebra of x Let G = (g : ui -* OJ |g i s 1-1 and onto) . Por every n G tu we define G = -(g e G : g(n) *= n) . G i s a group of permutations of tu x ui and each G n i s a subgroup-of G . So by 4.2 we have a normal f i l t e r of subgroups T generated by the subgroups G m . As i n 4.3 we have some non-standard subsets of the integers i n V V 1 . Let dom(u^) = dom(uj) f o r I G uu , and l e t UjCn) » {p G X : p(<n,i>) - 1} l e t U = { u ± : i G UJ) X {1} (T) G 4 c G and G c GTT , hence u. G V V ' f o r i G uu and i u^ U I (T) U G V ' . The sets l ( x ) and I A are. s i m i l a r to the corresponding ideas i n 4.3; and the proofs that l ( x ) G (T) and I A G V V ' f o r A c UJ and A f i n i t e are Ide n t i c a l to 85 t h o s e i n 4.3 i f u) i s s u b s t i t u t e d f o r Q . As i n 4.3 we have: T 4.4.1 |U i s i n f i n i t e ^ ! = H The p r o o f i s i d e n t i c a l to T 4.3.1 except t h a t t» s h o u l d be r e p l a c e d by Q wherever i t o c c u r s . In t h i s model we have: T 4.4.2 |U i s f i n i t e 2 | | = 1 . Pro o f : Por L € l e t dom i / = dom U and, l / ( x ) • ||x € L|| f o r x e dom U . Then ||L' CL|| = TT, , L'(x) -> ||x € L|| - 1 • • xedom(L ) and ||Vx e U(x e L - x e l / ) | | = IL / as f o r u i > u j e dom(u) and I ^ j we have . Ilii^ «= Uj|| «= (fi . Now ||L' C L||.||Vx € U(x e L - x € L')|| «||L C U|| < ||L' cu||i||L - L'H - HL - L ' H ' t h e r e f o r e ||L > l / | | >. ||L C TJ|| SO we have ||L C U||'||L i n f i n i t e 1 H <.,||L' i n f i n i t e ^ ! < IT, ||P f i n i t e , ! ! .-> S , , L'(y)||y * P|| F e V ( r ) yedom(L ) Now ||I(L') f i n i t e 1 l | - « 1 as dom(l(l/)) i s f i n i t e and we can apply T 4.2.7. Therefore .i|L' i n f i n i t e | | < E L'(y)-||y * I(L #)|| yedom(L ) E L ' ( y ) . | | y M ( L ' ) | | j yedom(U) E L'(u, ) i i M L ' ) 1 Now consider i , J <fc A(L') , i ^  j , and l e t | i k - J f(k) J j k = i JL k otherwise Clearly f e G^' . Therefore 1 - ||L' - f(L')|| < L ' ( U L ) <=> f ( L ' ( U L ) ) = L '(u^) <=> L 7 (u j ) , and hence L '(u^) « L ' ( U J ) . This implies that jl^ ± € L|| - j|uj e L|| f o r a l l i , j £ A(L') and therefore E L ' ( u .) « E ||u, e L|| - IT ||u, e L|| i*A(L') 1 i*A(L') 1 • i < M ( l / f 1 Then we have ||L' i n f i n i t e | | < TT , K € L l ! - TT l l y i KL')!!^ l l y e i^A(L') 1 yedom(U) = IIVy € U(y * I(L') - y e L)|| = ||Vy e U(y * L - y € l( L ' ) | | = ||U - L a I(L')|| - ||U - L c l(L')|| • ||l(L') f i n i t e ^ < ||U - L f i n i t e j l As ||L infinite - J j-||L c U|| <. | | l / f i n i t e . ^ we have 87 ||L i n f i n i t e ^ ' | | L C U|| <. ||U - L f l n i t e 1 | | . Now ||L G U|| < ||L C U||-||L f i n i t e j l + ||L C U||.||L i n f i n i t e 1 H <. ||L f i n i t e 1 H + ||U - L fi.nite.JI but (L c U - L f i n i t e 1 V U - L f i n i t e 1 ) implies that U i s f i n i t e 2 . Therefore we must have ||u i s f i n i t e 2 | | = 1 . Model III This model Is s i m i l a r to the one that Cohen [1] constructed to show the independence of the axiom of choice f o r countable sets of doubletons. There i s an ordered set of non-standard sets of the integers as In 4.4, but i n this model there i s also a p a r a l l e l s t r i n g of s i m i l a r sets. The intention Is that corresponding members w i l l be In a sense distinguishable only up to a f i n i t e number. Any l i n e a r ordering of an i n f i n i t e subset of the union of these two' strings would allow one to d i s t i n g u i s h between more than a f i n i t e number i n the model so that the union of these two strings must be f i n i t e i n the model. However, as we s h a l l / show, t h e i r powerset w i l l be r e f l e x i v e . Consider X = 2®*^*®*^ where Q denotes the r a t i o n a l s In (0,1) , and l e t /3 be the Lebesgue algebra of X . Let L q « (<q 1,0> s l e w ) and " ^ < (li» 1 > s i € w) f o r a l l q e Q . Let f(g) be the d i s j u n c t i o n of the two properties i ) f o r a l l q e Q and x e L_ , y e fh , we have g(x) e L 88 g(y) e nq • i i ) f o r a l l q e Q and x € L , y e % , we have g(x) e ft?, g(y) 6 L q • Let G = {g : Qxwx2 -* Qxwx2|g i a 1-1 onto and $(g)} and f o r r € Q l e t G r - Cg e G : g(<r,i,J>) « <r,i,j> f o r a l l i € uu, j € 2} Clearly G i s a group of permutations of Qxuox2 and each G r , f o r r e Q , Is a subgroup. Now with arguments s i m i l a r to those i n 4.2, i t Is easy to show that the subgroups G r generate a normal f i l t e r of subgroups T . Let us consider some non-standard subsets of the integers. Let domfu^j) = dom(v^j) = dom w and l e t Ujj'Cn) - [{p e X : p(<n,i >J,0> - 1}] • V l J ( n ) - [{p € X : p(<n,i,J,l> - 1}] (T) " i j ^ i j e V f o r 1 € °- a n d J e w as i n previous models. Now l e t U q = ( u q i : i e w) x {1 } V q = [v : i € w) x C3L/5 T = {U q,V q : q e Q) X (1 )• . It i s easy to show that G q C G U > G q C G V a n d G C °T Q, Q so U q,V q T e V^ r? f o r a l l q e Q . T 4.5.1 • ||T i s i n f i n i t e ^ ! «= 1 . Proof; Let d n : Q -* 2 be the function that maps a r a t i o n a l i n Q = (0,1) to the nth d i g i t of i t s binary expansion. Let K n = t u q > v q : d n ( q ) = ^ x ID • Clearly (r) G c G R and so K n e VK > f o r a l l n e w l e t K.(K : n e co) x (1 ) and note that G c ov and i n i\ ||K c P(T)|| = 3L . Let P = (<n,Kn>^F^ : n e tt>) . As G c G} f o r a l l n e iu , we have G c G p and thus P e V^ r^ . Now If i , j e tt) and i 4 J then l|K± « Kjll < IIU i e K±|| «> ||U e Kj|| , . = 3L => (D = (H Thus we have ||P maps oo onto K and i s l - l | | «= 3L and considering that ||K C P(T)|| »/3L , we get ||T i s i n f i n i t e ^ • 3L. T 4.5.2 ||T i s f i n i t e ^ l l « 1 . Proof; By T 2.3.6 we know that 90 (IT i s - f i n i t e ^ H <. ||VRVX(X c T A R orders X - X i s f i n i t e 1 ) | | - TT TT "||X''c T||.||X I n f i n i t e . II => | h R orders X|| Consider any R € and l e t dom(R') « (<U ,V >^r^:qeQ} and R'(<U q,V q>( r') = ||u R V || . Using a s i m i l a r argument to that i n T 4.4.2 we have ||R orders X||-||X c T|| < ||R' orders X| I f f o r any X € we l e t dom(x') = dom(T) and X'(y) - ||y e X|| we have ||X c T|| <. ||x = x'|| . Now ||X c T||.||X i n f i n i t e 1 H < ||x' i n f i n i t e ^ and ||X' i n f i n i t e , || < TT, II z f i n i t e i || => ||3y 6 X'(y 1 z)\\ (T) x = TT, IIz f i n i t e J I «=> E X' ( y ) . | | y k *\\ z e V ( r ) 1 y€dom(X) Now as G R/ G^/ e T these must be a f i n i t e subset of Q , say T , such that D G. c G„ / fl G Y i . Let F = iV±,V± : i i ' J ] x {1} Now ||P f i n i t e j l = 1 by T 4.2.7 as dom(F) i s f i n i t e . Therefore ||x' i n f i n i t e || < E X'(y).||y *'F|| 1 y€dom(X') • . - E X ' ( U ) + X ' ( V ) . q£j q q Choose an I £ J and l e t f<q,n,k> q ^ i f(<q,n,k>) . T — <q,n,l-k> q » i fo r a l l <q,n,k> € Qxtnx2 . Cle a r l y f e G R 0 G^/ therefore 9 1 .1 = ||X' . f(X')|| < x'(u ±) <=> ffx 'C^)) - x'Cu±) <=> x'O^) and hence X'(U ±) = 11% e X|| -X'O^') -\\V± e x|| ... A l s o 1 - ||f(R') = R'|| < R'iKV^V^) <-> ( R ^ U ^ V ^ ^ ) ) = R'(<U 1,V 1>^ r)) <«> ( R ' ( < V 1 , U 1 > f r ) ) ) t h e r e f o r e 11% R V±|| = ||V± R %|| . Now ||R orders X||.||x c T|| < ||R' orders X|| < 11% € Xll-IIVj e X|| => ||% R V 1l|.(-||V i R %||) + ||V1 R V±\\.(-\\V± R U±||) + HV^H = 11%. € X|| => Q = -11% € X|| The r e f o r e -||R orders X|| + -||X c T|| _ > E ||% e X|| + ||V e X|| > ||X c TH - Hx i n f i n i t e 1 H ||-R orders X|| > ||x c T||»||X i n f i n i t e - | | - . T h e r e f o r e ||T f i n i t e , || / 1 92 CHAPTER 5  DISCUSSION OF RESULTS 5.1 Introduction In t h i s chpater we w i l l examine the r e s u l t s of Chapter 2 and Chapter 4, and show the independence of a l l the. Implications between the d e f i n i t i o n s i n Chapter 2, that were not proved as theorems In Chapter 2. 5.2 Several Relative Consistency Results As we constructed a l l our models i n a set V of a Z-F set theory, whose existence Is equivalent to consis(Z-F), a l l our r e s u l t s as r e l a t i v e to consis(Z-F) . i ) In Model I there exists a set A such that a) A i s i n f i n i t e 1 b) A i s f i n i t e g c) P(A) i s f i n i t e 6 and also i n Model I the ordering p r i n c i p l e i s true. Therefore by T 2.4.8 A i s i n f i n i t e ^ . As P(A) i s f i n i t e ^ , A i s f i n i t e , . . Therefore Consis(Z-F) -» Consis(Z-F+there i s a set that i s f i n i t e , . but i n f i n i t e ^ ) and Consis(Z-F) -• Cons Is (Z-F+t here i s a set that i s f i n i t e ^ but i n f i n i t e ^ ) . Now as A i s infinite - j ^ by T 2.3-2 v i i ) P(P(A)) i s 93 i n f i n i t e ^ . T h e r e f o r e B = P(A) i s f i n i t e ^ but i n f i n i t e , and C o n s i s ( Z - F ) -• Consis(Z-F+there i s a s e t t h a t i s f i n i t e ^ but i n f i n i t e ^ ) . i i ) In Model I I there i s a s e t A such t h a t a) A i s i n f i n i t e 1 b) A i s f i n i t e 2 . T h e r e f o r e we have Consis(Z-F) -* Consis(Z-F+there i s a s e t t h a t i s i n f i n i t e but f i n i t e 2 ) . Now by T 2.4.11 there must be a s e t B i n Model I I such t h a t B i s f i n i t e ^ and i n f i n i t e 2 , hence Consis (Z-F) -» Consis (Z-F+there i s a s e t t h a t i s i n f i n i t e but f i n i t e ^ ) • i I i i ) In Model I I I there i s a s e t A such t h a t a) A i s f i n i t e ^ b) A i s i n f i n i t e ^ . , T h e r e f o r e we have Consis (Z-F) -* Consis (Z-F+there Is a s e t t h a t i s f i n i t e ^ but i n f i n i t e , . ) and as A i s i n f i n i t e ^ by T 2.4.4 we have Consis (Z-F) -» Consis (Z-F+there i s a s e t t h a t i s f i n i t e ^ but i n f i n i t e ^ ) • I m p l i c a t i o n s Independent from Z-F I t has been proved by Godel [6] (see [1] p. 95) t' 94 Consis(Z-P) -• C o n s i s ( Z - F + AC) . A l s o by T 2.4.7 Consls(Z-P + AC) C o n s i s ( Z - F + a l l f i n i t e ^ s e t s are f i n i t e . ^ . T h e r e f o r e C o n s l s ( Z - F ) -» C o n s i s ( Z - F + a l l the d e f i n i t i o n s , f i n i t e . ^ are e q u i v a l e n t , i = 1, 2, 3, 4, 5, 6) . T h e r e f o r e i f we assume Consis(Z-P) the f o l l o w i n g i m p l i c a t i o n s are independent of the axioms Z-P i ) VA (A f i n i t e 2 A f i n i t e 1 ) i i ) VA (A f i n i t e ^ -* A f i n i t e 2 ) i i i ) VA (A f i n i t e ^ A f i n i t e ^ i v ) VA (A f i n i t e c — » A f i n i t e ^ -, v) VA (A f i n i t e ^ -* A f i n i t e . - ) . , v i ) VA (A f i n i t e c A f i n i t e ^ ) v i i ) VA [A f i n i t e 6 A f i n i t e ^ ) v i i i ) V A (A f i n i t e ^ - A f i n i t e ^ ) / These r e s u l t s combined with the theorems of 2.4 give a complete p i c t u r e of a l l the r e l a t i o n s h i p s between the d e f i n i t i o n s finite - j ^ through t o f i n i t e ^ . Some A d d i t i o n a l D e f i n i t i o n s ., Levy [13] c o n s i d e r e d three more d e f i n i t i o n s . 95 P 5-4,1 A i s f i n i t e ^ i f |A| = 0 or |A| + |A| 4 |A D 5.4.2 A i s f i n i t e g i f | A | = 0 , | A | = 1 or A x A l 4 |A | . D 5.4.3 IA| 4 |c| A i s f i n i t e ^ i f f o r a l l c a r d i n a l s c >. u) We have the f o l l o w i n g i T 5.4.4 I f A i s f i n i t e 1 then A i s f i n i t e i + 1 f o r i = .6, 1, 8 . Proof: We s h a l l show t h a t i f A i s i n f i n i t e i + 1 then A i s ' i n f i n i t e ^ . / I f A i s i n f i n i t e ^ - then there e x i s t s a 1-1 f u n c t i o n f from A x (0} U A x (1} Into A . C l e a r l y there i s a 1-1 f u n c t i o n g from A i n t o ( f ( x ) : x € A x {0}} , thus A i s i n f i n i t e ^ . Suppose A i s i n f i n i t e g , then |AxA| = |A| . C l e a r l y |A| < |A| + |A| and |A| + |A| <. |AxA| = |A| . T h e r e f o r e by the C a n t o r - B e r n s t e i n theorem |A| = |A| + |A 96 C l e a r l y i f A i s i n f i n i t e ^ then |A| = |c| f o r some c a r d i n a l o' >. uu and i t i s w e l l known t h a t |cxc| = |c|. I t can be seen Immediately by the theorem schema T 2.6.2 t h a t f o r each of the d e f i n i t i o n s f i n i t e ^ , , f i n i t e g and f i n i t e ^ i s e q u i v a l e n t to f i n i t e ^ o r they do not s a t i s f y the c o n d i t i o n s i i , i v , v i n 2.5.1. Now uu i s c l e a r l y i n f i n i t e . ^ f o r i = 7, 8, 9 and as the d e f i n i t i o n s are a l l based on c a r d i n a l i t y they a l l s a t i s f y 2.5.I i v ) . T h e r e f o r e f o r i = 7, 8, 9 e i t h e r f i n i t e ^ ^ i s e q u i v a l e n t to f i n i t e ^ o r there Is a s e t t h a t i s f i n i t e . ^ but has an i n f i n i t e . ^ s u b set. The second choice can occur as Jech and Sochor [9 ] and H. Sayeki [18 ] have shown t h a t 1 Consis(Z-F) -» Consis(Z-F+there i s a s e t t h a t i s i n f i n i t e i but f i n i t e 1 + 1 ) f o r i = 6, 7, 8 . 5.5 Concluding Remarks Unless we accept the axiom of c h o i c e there seems to be no one d e f i n i t i o n t h a t w i l l completely capture the i d e a of f i n i t e n e s s . A l l of the d e f i n i t i o n s suggested so f a r seem to l a c k p r o p e r t i e s we would l i k e to r e q u i r e and possess p r o p e r t i e s we would l i k e to f o r b i d . F o r example there are i n f i n i t e ^ s e t s t h a t cannot be d i v i d e d i n t o two i n f i n i t e . ^ p a r t s and there are f i n i t e ^ s e t s which have p a r t i a l l y ordered c o l l e c t i o n s of subsets w i t h chains of a r b i t r a r y l e n g t h . These d i f f i c u l t i e s a r i s e when we c o n s i d e r s e t s f o r which no 97 w e l l o r d e r i n g can be shown to e x i s t . I t would be easy to d i s m i s s these s e t s as b e i n g a r t i f i c i a l and thus excuse any p a t h o l o g i c a l p r o p e r t i e s they p o s s e s s . However t h i s i s not the case, most of our examples i n t h i s paper were subsets o f the r e a l numbers, t h a t i s the power s e t of uu , or subsets of the power s e t of the r e a l numbers. We are f a c e d then with the problem t h a t we cannot even s a t i s f a c t o r i l y d e f i n e f i n i t e f o r s e t s of r e a l numbers without r e s o r t i n g t o the axiom of c h o i c e . Most o f these problems develop when we f o r m a l i z e our Ideas of f u n c t i o n s and o r d e r i n g s from a b s t r a c t p r o p e r t i e s to the e x i s t e n c e of c e r t a i n s e t s . T h i s i s why we can have countable models of s e t theory, even though there w i l l be uncountable s e t s i n s i d e the model. They are uncountable not because they have some p r o p e r t y t h a t we can observe from o u t s i d e the model, but because no s e t e x i s t s i n the model th a t w i l l p l a y the r o l e as a f u n c t i o n from the i n t e g e r s . A l l the models c o n s t r u c t e d i n t h i s paper were countable, but were c o n s t r u c t e d i n such a manner t h a t c e r t a i n s e t s c o u l d not e x i s t i n the model which allowed the d e s i r e d c o u n t e r -examples . To examine the q u e s t i o n f u l l y then we have to l o o k a t s e v e r a l d e f i n i t i o n s , each one of which expresses some p r o p e r t y t h a t I n d i c a t e s f i n i t e n e s s , and see how they are r e l a t e d to each o t h e r . As we cannot c o n s i d e r every p r e d i c a t e as a d e f i n i t i o n o f f i n i t e t h e r e must be some 98 acceptable properties a d e f i n i t i o n of f i n i t e should have. In Chapter 2 we have suggested a l i s t of such properties and examined a r b i t r a r y predicates that s a t i s f y these properties. As was shown i n 5.4 there have been d e f i n i t i o n s suggested that do not s a t i s f y these properties and yet s t i l l seem to be v a l i d d e f i n i t i o n s of f i n i t e . There are two ways i n which a set can s a t i s f y the d e f i n i t i o n s f i n i t e ^ , f i n i t e g and f i n i t e ^ , either a set i s f i n i t e or i t i s highly non-standard, that i s certain functions and re l a t i o n s concerned with the set do not e x i s t . The d e f i n i t i o n of f i n i t e ^ c l a s s i f i e s any set that can't be well ordered as f i n i t e . I t i s clear that any i n f i n i t e ^ set i s i n f i n i t e but can't there be i n f i n i t e sets with no well ordering? The l i s t of properties i n Chapter 2, which limi.ted the d e f i n i t i o n to be more r e s t r i c t i v e than f i n i t e ^ , was adopted i n t h i s paper to avoid d e f i n i t i o n s that don't separate pathological sets from f i n i t e ones. >• / 99 BIBLIOGRAPHY Cohen, P. J . : Set Theory and the Continuum Hypothesis. Benjamin, New York, 1966. Dedekind, R.: "Was slnd und was sol l e n die Zahlen", III Auflage Braunschweig (1911). Doss, R.: "Notes on two theorems of Mostowski", Journal  of Symbolic Logic 10 (1945), pp. 13-15-Praenkel, A.: "Sur l 1axiom du choix", Enselgnement Math. 31 (1935), PP- 32-51. Praenkel, A.: Abstract Set Theory. North Holland P u b l i -shing Company, Amsterdam, 1953• Godel, K.: The Consistency of the Axiom of Choice and  of the Generalized Continuum Hypothesis with the Axioms  of Set Theory. 4th p r i n t i n g . Princeton. 1958. Halmos, P.: Lectures on Boolean Algebras. Van Nostrand, Princeton, 19^ 3^  Jech, T.j Sochor, A.: "On 9-Model of the Set Theory", B u l l e t i n de L'Academie Polonaise des Sciences 14 no. 6 (1966), pp. 297-303. Jech, T.j Sochor, A.: "Applications of the 9-Model", B u l l e t i n de L'Academie Polonaise des Sciences 14 no. 7 (1966), pp. 351-355- ' Jensen, R. B.: Modelle der Mengenlehre. Lecture Notes i n Mathematics Series, Springer-Verlag, 1967. Kuratowski, C : "Sur l a notion de 1'ensemble f i n i " , Fundamenta Mathematicae 1 (1920), pp. 129-131. Lauchli, H.: "The Independence of the Ordering P r i n c i p l e from a Restricted Axiom of Choice", Fundamenta Mathema-ticae 55 (1964), pp. 31-43. LeVy, A.; "The independence of various d e f i n i t i o n s of fi n i t e n e s s " , Fundamenta Mathematicae 16 (1958), pp. 1-13. LeVy, A.: "The interdependence of certai n consequences of the axiom of choice", Fundamenta Mathematicae 54 (1964), pp. 135-157. . . . . . . 100 JMarek, W.; Onysziewicz, J.: "Generalized Dedekind Numbers", B u l l e t i n de L'Academie Polonaise des Sciences 24 no. 9 (1966). "" Mostowski, A.: "Uber die Unabhangigkeit des Wohlord-nugssatzes vom Ordnungsprinzip", Fundamenta Mathematicae 32 (1939), PP. 201-252. Rasiowa, H,; S i k o r s k i , R.: "A proof of the completeness theorem of Godel", Fundamenta Mathematicae 37 (1950), pp. 193-200. Sayeki, H.: "Definitions of the f i n i t e set and the axiom of choice", Unpublished paper (1969). Sayeki, H.: "Independence of a weak axiom of choice", Unpublished paper (1969)• Scott, D.: "Lectures on Boolean valued models f o r set theory", Mimeographed copy of paper. To appear as "Boolean valued models f o r set theory", Scott, D. and Solovay, R. Schoenfield, J . J Mathematical Logic. Addison-Wesley, Reading Mass., 1967. S i e r p i n s k i , W.: "L«hypotheses generalisee du continu et l 1axiom du choix", Fundamenta Mathematicae 34 (1947), pp. 1-5. S i k o r s k i , R.: Boolean Algebras. 2nd e d i t i o n , Springer-Verlag, B e r l i n , 1964. Specker, E.: "Zur Axiomatik de Mengenlehre", Zeits c h r . f . Math.. Logik und Grundlagen 3 (1957), pp. 193-199. Stakel, P.: "Zu H. Webers Elementarer Mengenlehre", Jahresker. d.d. M.-V. 16 (1907), p. 425-T a r s k i , A.: "Sur les ensembles f i n i s " , Fundamenta  Mathematicae 6 (1924), pp. 45-95. Suppes, P.: Axiomatic Set Theory. Van Nostrand, Princeton, 19W. Whitehead, A.j Russell, B.: P r i n c i p i a Mathematicae Vo l . I I , Cambridge, 1912. Wrinch, D.: "On Mediate Cardinals", American Journal  of Mathematics 45 (1923), pp. 87-92. 101 [30] Zermelo, E.: "Sur les ensembles f i n i s et lep r i n c i p e .'de l»induction complete", Acta. Math. 32 (1909). pp. 85-193. 

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-0080467/manifest

Comment

Related Items