FIRST ORDER TOPOLOGY BY JOHN MALYON INGLIS B.Sc. , U n i v e r s i t y o f B r i t i s h Columbia , 1975 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE i n the Department o f MATHEMATICS We accept t h i s t h e s i s as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA September.-, 1974 In p r e s e n t i n g t h i s t h e s i s in p a r t i a l f u l f i l m e n t o f the requirements f o r an advanced degree at the U n i v e r s i t y of B r i t i s h Columbia, I agree that the L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r reference and study. I f u r t h e r agree tha t permiss ion fo r e x t e n s i v e copying of t h i s t h e s i s f o r s c h o l a r l y purposes may be granted by the Head of my Department or by h i s r e p r e s e n t a t i v e s . It i s understood that copying or p u b l i c a t i o n of t h i s t h e s i s f o r f i n a n c i a l ga in s h a l l not be a l lowed without my w r i t t e n p e r m i s s i o n . Department of The U n i v e r s i t y of B r i t i s h Columbia Vancouver 8, Canada - 11 -Supervisor ; J3r. Andrew Adler ABSTRACT A t o p o l o g i c a l space may be viewed as an algebraic s t r u c -ture. For example, i t may be viewed as a ( complete atomic ) Boolean algebra equipped with a closure operator. The l a t t i c e o f closed subsets i s another algebraic s t r u c t u r e which may be associated with a t o p o l o g i c a l space. Tne purpose o f t h i s t h e s i s i s p r i m a r i l y to i n v e s t i g a t e the metamathematical p r o p e r t i e s o f algebraic s t r u c t u r e s associated with t o p o l o g i c a l spaces. More s p e c i f i c a l l y , we w i l l f i r s t consider questions of dec-i d a b i l i t y o f the t h e o r i e s of these a l g e b r a i c s t r u c t u r e s . I t turns out that these t h e o r i e s are undecidable. We w i l l also examine c e r -t a i n equivalence r e l a t i o n s on the c l a s s o f t o p o l o g i c a l spaces that a r i s e n a t u r a l l y from viewing them as f i r s t - o r d e r s t r u c t u r e s . F i n -a l l y we w i l l show that c e r t a i n c l a s s i c a l theorems of model theory do not hold f o r t o p o l o g i c a l spaces. _ - I l l -ACKNOWLEDGEMENTS I would l i k e to thank Dr. Andrew Adler f o r supplying the concepts on which t h i s thesis i s based and his generous help throughout i t s preparation. I would also l i k e to thank Br, P. Belluce f o r reading the thesis. - I V TABLE 0? CONTENTS Chapter 0 Chapter 1 Chapter 2 1. I n t r o d u c t i o n 2. The Basic D e f i n i t i o n s page 1 2 -Some U n d e c i d a b i l i t v Results 1. Ar i t h m e t i c o f F i n i t e Sets 2. U n d e c i d a b i l i t v o f the L a t t i c e o f Closed Subsets 3 . U n d e c i d a b i l i t y o f Closure Algebra 4. U n d e c i d a b i l i t y o f the Topology o f |Rn f o r n > 2 5. An Incompleteness Result Elementary Equivalences o f Top- o l o g i c a l Spaces 1. Weak: Elementary Equivalence 2. Strong Elementary Equivalence 5. The Rel a t i o n s h i p between Weak and Strong Elementary Equivalence 4. The R e l a t i o n s h i p between Element-ary Equivalence and Homeomorphism 17 18 19 21 23 24 28 - V -5. Some Results about A(T) and L(T) page 30 6 . The Product Problem 32 7. Elementary P r o p e r t i e s 33 8. D i s c r e t e Spaces 36 9. A P a r t i a l C h a r a c t e r i z a t i o n o f the Real Numbers 43 Chapter 3 The C l a s s i c a l Theorems o f Model 1. The Compactness Theorem 49 2. The Completeness Theorem 53 3» The Downward Lowenheim-Skolem Theorem 54 Bibliography 59 - 1 -CHAPTER 0 . 1. I n t r o d u c t i o n . A t o p o l o g i c a l space may be viewed as an a l g e b r a i c s t r u c -t u r e . For example, i t may be viewed as a ( complete atomic ) Boolean algebra equipped with a closure operator. The l a t t i c e o f closed subsets i s another a l g e b r a i c s t r u c t u r e which may be associated with a t o p o l o g i c a l space. The purpose of t h i s t h e s i s i s p r i m a r i l y to i n v e s t i g a t e the metamathematical p r o p e r t i e s o f alge b r a i c s t r u c t u r e s associated with t o p o l o g i c a l spaces. I t i s indeed i n t e r e s t i n g that the the o r i e s o f these a l g -ebraic s t r u c t u r e s associated with t o p o l o g i c a l spaces are undec-l d a b l e . In the f i r s t chapter we concentrate on u n d e c i d a b i l i t y . Among other t h i n g s , we prove that the set o f sentences o f elem-entary l a t t i c e theory, true i n the l a t t i c e of closed subsets o f , i s not r e c u r s i v e , and that the elementary theory o f t o p o l o g i c a l l a t t i c e s i s undecidable. The proof we g i v e follows the mam o u t l i n e o f an e a r l i e r proof given by. Grzegorczyk ^see [ j ] j . That e a r l i e r proof however had some gaps and e r r o r s . In the second chapter we examine some equivalence r e l a t i o n s on the c l a s s o f t o p o l o g i c a l spaces that a r i s e n a t u r a l l y from viewing them as f i r s t - o r d e r s t r u c t u r e s . This y i e l d s a. p o s s i b l e - 2 -c l a s s i f i c a t i o n o f t o p o l o g i c a l spaces that i s much coarser than homeomorphism. In the second chapter we also look at the exp-r e s s i v e power o f f i r s t - o r d e r languages i n the study o f topology, and obtain p a r t i a l r e s u l t s toward the problem o f c h a r a c t e r i z i n g the r e a l numbers. In the t h i r d and f i n a l chapter we look at c e r t a i n c l a s s -i c a l theorems o f model theory and examine the question o f whether these r e s u l t s hold f o r t o p o l o g i c a l spaces. A s e r i e s o f counterexamples shows that the completeness theorem, the comp-actness theorem, and Lowenheim-Skolem theorems f a i l i n t h i s new s e t t i n g . 2. The Basic D e f i n i t i o n s . We f i r s t give some standard d e f i n i t i o n s i n order to e s t -a b l i s h n o t a t i o n . A p a r t i a l l y ordered set X , with p a r t i a l ordering *C , such that f o r any a,b £ X the set £ a,b^ has an mfimum and supremum i s c a l l e d a l a t t i c e , and the sup and i n f o f the set <£a,b^ are denoted r e s p e c t i v e l y by a VJ b and a / l b . I f i n a d d i t i o n there i s a smallest element 0 and a l a r g e s t element 1 , and f o r every a E X there i s a b£ X, denoted by 1-a, such that a U b = l and a O b — o then the l a t t i c e i s s a i d to be - 3 -complemented. I f the l a t t i c e has the property that f o r any a,b,c63X (anb ) l/c = ( a u c)fl (bUc) and (aU b) 0 c = (a n c) U (b f\c) then i t i s s a i d to be d i s t r i b u t i v e . A l a t t i c e that i s both complemented and d i s t r i b u t i v e i s a Boolean algebra. Now l e t T be an a r b i t r a r y t o p o l o g i c a l space. (1.) Let L ( T ) denote the set of closed subsets o f T , and f o r A , B£L(T) w r i t e A<B i f A c B. C l e a r l y s i s a p a r t i a l ordering on L ( T ) . We also l e t AU B and AH B be r e s p e c t i v e l y the sup and m f o f the set { A , B | . Then L ( T ) together with < , H and KJ i s a l a t t i c e , c a l l e d the l a t t i c e o f closed subsets o f T. Also L ( T ) has a smallest and a l a r g e s t element. The smallest element 0 i s ^ , and the l a r g e s t element 1 i s T. So we l e t the language f o r t h i s s t r u c t u r e be the language o f l a t t i c e theory enriched by a d d i t i o n o f the n o n - l o g i c a l constants 0,1. We l e t L w denote t h i s language. (2.) Let 0 ( f ) denote the set of open subsets o f T, again with p a r t i a l ordering < given by i n c l u s i o n , and sup and m f defined by unions and i n t e r s e c t i o n s r e s p e c t i v e l y . Again 0 ( T ) i s a l a t t i c e c a l l e d the l a t t i c e of open subsets o f T. 0(T) has a smallest element 0, and a l a r g e s t element 1, both given as above m So we l e t the language f o r t h i s s t r u c t u r e again be L^« (3.) Let B(T) be any Boolean algebra o f subsets o f T, con-t a i n i n g a l l the closed subsets o f T, with p a r t i a l o rdering given by i n c l u s i o n , and sup and i n f given by union and i n t -e r s e c t i o n r e s p e c t i v e l y . Boolean d i f f e r e n c e , — , i s the usual s e t - t h e o r e t i c d i f f e r e n c e . Notice that B(T) also contains a l l the open subsets o f T. In t h i s t h e s i s four d i f f e r e n t v a r i a n t s o f t h i s s t r u c t u r e are used. We l e t L denote the language o f Boolean algebra. (a) Let L c denote the language obtained by strengthening L by the a d d i t i o n o f a unary f u n c t i o n symbol C. For A£B(T) CA i s i n t e r p r e t e d as the smallest closed set conta i n i n g A. So C obeys the usual Kuratowski axioms. (I) A < CA ( I I ) C(Au B ) - C ( A ) U C ( B ) ( i l l ) C0 = 0 ( i v ) CCA-CA Then B(T) together with C i s c a l l e d a t o p o l o g i c a l Boolean algebra based on a clo s u r e operator, or simply a cl o s u r e algebra. (b) Let L j denote the language obtained by strengthening L by the a d d i t i o n o f a unary func t i o n symbol I , such that f o r Ae B(T) EA i s i n t e r p r e t e d as the l a r g e s t open set con-- 5 -tained i n A. Then B(T) together with I i s c a l l e d a top-o l o g i c a l Boolean algebra based on an i n t e r i o r operator. (c) Let L^ denote the language obtained' from L by adding a predicate symbol K, K(A) i s s a i d to hold i f A i s closed i n T. B(T) together with K i s c a l l e d a t o p o l o g i c a l Boolean algebra based on a closedness p r e d i c a t e . (d) Let L Q denote the language obtained from L by adding a predicate symbol 0. 0(A) i s s a i d to hold i f A i s open i n T . B(T) together with 0 i s c a l l e d a t o p o l o g i c a l Boolean algebra based on an openness p r e d i c a t e . In t h i s t h e s i s B(T) w i l l e i t h e r be the power set o f T, A(T) , or the Borel sets o f T. Both of these are c l e a r l y Boolean algebras having a l l the p r o p e r t i e s o f B(T) . - 6 -CHAPTER 1. Some U n d e c i d a b i l i t y R e s u l t s . We now show that the t h e o r i e s o f l a t t i c e o f closed sub-sets and closure algebra are undecidable. To do t h i s we show that c e r t a i n c o n s i s t e n t f i n i t e extensions of these t h e o r i e s are undecidable, because they contain ordinary a r i t h m e t i c . Ordinary a r i t h m e t i c i s w e l l known to be e s s e n t i a l l y undecid-able ( see [7,1 ^ . 1. Ari t h m e t i c o f F i n i t e Sets. The a r i t h m e t i c o f f i n i t e sets has n o n - l o g i c a l symbols f$ t ~ t S , i ~ , and X wit h the f o l l o w i n g i n t e r p r e t -a t i o n s : (1) ^ i s the empty set i f A,B,C are assumed to be f i n i t e sets we w r i t e : ( i l ) A ^ B f o r A-B ( i l l ) S(A,B) f o r B = A - r l ( i v ) 4-(AB,C) f o r C~A+B (v) x (AB,C) f o r C=A-B where A denotes the c a r d i n a l i t y o f A. - 7 -This theory has the f o l l o w i n g axioms: ( I ) V * A 3 B ( S ( ' A , B ) ) ( I I ) ' 1 3 A ( S ( A , / ) ) ( i l l ) S ( A , B ) ^ S(C,D)—^> ( A ^ C < ^ - > B ^ D ) ( i v ) V A B 3 C(+- (AB,G)) (v) 4 - ( A ^ , A ) ( v i ) 4- ( A B,C) A 4 ~ ( B E , E ) A A ^ D A B ^ E C^F ( v i i ) + ( A B , C ) A + ( A E , F ) A S ( F , K ) A S ( E , B ) — > C # K ( v i i i ) V AB3 C(X ( A B , C ) ) ( i x ) X ( A / , / ) (x) X ( A B , C ) A S ( D , B ) A X ( A D , F ) A - V - ( F A , E ) ->C«-B ( x i ) X ( A B , C ) A X ( B E , ? ) A A ^ B A B ^ E - ^ C ^ F C l e a r l y the a r i t h m e t i c of f i n i t e sets can be viewed as ord-i n a r y a r i t h m e t i c . Ordinary a r i t h m e t i c was shown to be essent-i a l l y undecidable i n " Undecidable Theories " by Tarsk i , Mostowski ,and Robinson ( see {_ 7 ^ . . So the a r i t h m e t i c o f f i n i t e sets i s e s s e n t i a l l y undecidable. 2. U n d e c i d a b i l i t y o f L a t t i c e o f Closed Subsets. Let M be the set o f sentences o f L w t h a t are true i n the l a t t i c e o f closed subsets o f every t o p o l o g i c a l space. We w i l l prove that M i s not r e c u r s i v e , by showing th a t a c e r t a i n f i n i t e extension o f M i s undecidable. We now construct a f i n i t e extension by adding s i x axioms to the l i s t M. These axioms are a l l formulas o f . Axiom 1. The space T i s connected. This can be w r i t t e n i n as: VAB( A V B - l A A n B - 0 >A = 0 V B = 0 ). The property that A e L ( T ) i s an atom o f L(T) can be w r i t t e n i n as; A ^ O A V B ( B ^ A A B ^ O — > . B S = A ). This formula i s abbreviated as atom(A). We thus g i v e : Axiom 2. Every non-empty element o f L(T) contains' an atom o f L ( T ) . This can be w r i t t e n i n as: \/A( A # 0— > 3 B ( a t o m ( B ) A B ^ A ). Axiom 3. The space T i s not n e c e s s a r i l y normal, but given d i s j o i n t sets A,B£L(T) there are open sets containing each tha t do not i n t e r s e c t . This can be w r i t t e n i n as: V/AB( A R B = 0 >3 CD( A^ G A AnD= 0 A B < D A B 0 C = 0 A C U » = l ). In order to w r i t e e f f i c i e n t l y the remaining axioms, the f o l l o w i n g abbreviations are u s e f u l . We w r i t e : (1) Connect *"(A) f o r \f BC( A ~ B A C A B U C = 1 >B = 1 VC=1 ). - 9 -This says t h a t the complement o f A i s connected. (2) Comp*(A,B) f o r 3 <A A Connect * (A-) A V C( B< C s C £ A A Connect * ( C ) >A=C ). This says that the complement o f A i s a connectedness comp-onent o f the complement o f B . (3) . Discrete(A) f o r V B ( B < A A atom ( B ) — > ^ C( C f l B = 0 A A < CUB ). This says that A i s a union o f atoms, each o f which i s con-tained i n an open set that does not i n t e r s e c t the r e s t of A . I f the underlying space i s , Discrete(A) holds i f and only i f A i s d i s c r e t e . Now we l i s t some more axioms: Axiom 4 . This axiom insu r e s the existence o f c o l l e c t i o n s o f atoms o f a l l f i n i t e c a r d i n a l i t i e s . We w r i t e i n : \/A( A ^ l >3B( A< B r x B + A A B + l A 3 C( atom (C) A C < B ^ C H A ^=0 ) ) ) . Axiom 5. This i s the most important axiom. I t says that given d i s j o i n t d i s c r e t e (closed) sets A and B , and any connected open set 0 conta i n i n g A and B , and given any p a i r o f atoms, one o f the p a i r from each o f A and B , there are d i s j o i n t connected open sets contained i n 0 , one co n t a i n i n g the p a i r - 10 -and the other containing the r e s t o f A and B . We w r i t e i n : \/ABC( AH B = 0 A D i s c r e t e (A) A D i s c r e t e ( B ) A CR A - 0 A C O B - 0 —>\/ab( atom(a) A atom(b) A a< A A b ^ B ^ ^ 3 DE( C < D A C < E A afAE = 0 A b n E= 0 A V pq( p< A A atom(p) A pz/t a — > p n D = 0 A q ^ B A a t o m ( q ) A q ^ b — > q O E = 0 ) A D U E = 1 ))) . Before g i v i n g the f i n a l t e c h n i c a l axiom we re q u i r e the f o l l o w i n g important d e f i n i t i o n : In Lyy we w r i t e A = B f o r AO B= 0 A D i s c r e t e ( A ) A D i s c r e t e ( B ) A 3 M( E A A Eg A F A A U A A F B A U B )• Where: E A i s V a( atom(a) A a^A-^3 0( Comp^ (C,M) A aH C =0 )) . F A i s V C( Comp*(C,M) > 3 a ( a ^ A A atom (a) A a f l C =0 )) . U A i s V a'( a'^ A ^ atom (a') A a' a — ^ a ' t j C ^ C ) . Simply, we have A = B i f A and B are d i s j o i n t d i s c r e t e s e t s , and there i s an open set M such that each connectedness component o f M contains p r e c i s e l y one atom from each o f A and B , and each atom o f A and B i s contained i n some connectedness component o f M . We now add the f i n a l axiom; Axiom 6. This axiom insures the existence of a s u f f i c i e n t supply o f d i s j o i n t d i s c r e t e sets , A and B such that A = B - 11 -More p r e c i s e l y , i f A i s any d i s c r e t e set and B i s any sub-set o f A , then there i s a. d i s c r e t e set C , d i s j o i n t from A, such that C = B . This can be w r i t t e n i n as: \/AB( B< A ^ D i s c r e t e (A)- D i s c r e t e (C) A C HA^ 0 A C = B )) . I t i s now necessary to check that the theory, M ' say, obtained by adding axioms one through s i x to the theory M i s c o n s i s t e n t . We do t h i s by showing that the theory M ' has a model. P r o p o s i t i o n . The l a t t i c e o f closed subsets o f IR i s a model o f the theory M / . Proof. Axioms one through four c l e a r l y hold i n the l a t t i c e o f closed subsets o f Jf{ Now, given d i s j o i n t d i s c r e t e sets A, B i n Al/B i s also d i s c r e t e . There i s a homeomorphism o f ^ onto i t s e l f that takes any d i s c r e t e subset of IR^ to a subset of . So AUB can be assumed, without l o s s o f g e n e r a l i t y , to be a subset, S say, o f X* TL . Given any two points a,b o f S, there i s an open subset -JJ o f fR which i s connected and contains both p o i n t s , and whose closure contains no other points o f 1^2., F i n a l l y given an open s e t , 0 , i n //^ , containing S , i f we l e t U ' - ( j a o and ,y,'= [JR 3" - closure of y ] H 0 , then ,y' and ? ' - 12 -are open d i s j o i n t sets contained i n 0 such that a and b are i n U ' , and S - |a,bj- i s contained i n V / . Assuming a £A and bfcB , we have that axiom f i v e holds i n the l a t t i c e o f closed subsets o f fR . A l s o , given any d i s c r e t e set A i n (R 3" , since A i s d i s c r e t e there i s a d i s j o i n t family o f open sets i n [R such that each member o f the fa.mily contains p r e c i s e l y one element o f A , and conversely each element o f A i s contained i n some member o f the fa m i l y . Let B be any ( non-empty ) sub-set o f A . Let C be the subset o f (R c o n s i s t i n g of prec-i s e l y one p o i n t , that i s not i n B , from each of the above open neighbourhoods o f the points o f B . Then l e t t i n g M , i n the d e f i n i t i o n o f =z t be the complement o f the union o f a l l the above neighbourhoods o f the points o f B, we have C c=B . So axiom s i x holds i n the l a t t i c e o f closed subsets o f f R 9 " . This completes the proof. Remark: The above proof, w i t h only minor m o d i f i c a t i o n s , works equally w e l l f o r the l a t t i c e of closed subsets o f (R t f o r n > 2 . Hence the l a t t i c e of closed subsets o f l R n , f o r any n >. 2 , i s a model o f the theory M We now g i v e one more d e f i n i t i o n ; In L^ we w r i t e f i n ( A ) as the abbre v i a t i o n f o r - 13 -Di s c r e t e . ! A ) A 1 3 B ( B ^ A / \ B c ( C £ B C ^ B A 3 D( .DO A= 0 A C^D \ D = B ))) . I t i s now necessary to check that given an A£L(T) such that f i n ( A ) holds, that A i s indeed f i n i t e . In f a c t we have: Lemma. I f A £ L(T) i s a d i s c r e t e s e t , then f i n ( A ) holds i f and only i f A i s f i n i t e . Proof. Obviously,given any sets A and B4 such that A ==: B , then A and B can be put i n a one-to-one correspondence. So i f A£L(T) i s such that f m ( A ) does not h o l d , then A can be put i n a one-to-one correspondence with a proper subset o f i t s e l f , and hence i s i n f i n i t e . So i f A i s f i n i t e then f i n ( A ) holds. Conversely, suppose A i s i n f i n i t e . Then A contains a countabiy i n f i n i t e subset, B say. Then there i s a proper sub-set C o f B, such that there i s a one-to-one correspondence between B and C . By axiom s i x there i s a d i s c r e t e set D, d i s j o i n t from A , such that C = D . Again, C and D can c l e a r l y be put i n a one-to-one correspondence, so there i s also a one-to-one correspondence between D and B . We now assume that and that the one-to-one correspondence i d e n t i f i e s d^ and - 14 -b. , f o r a l l j . B y axiom f i v e , there are d i s j o i n t open conn-ected sets and i n T such that d.^ , b 1 £ M 1 and B - | d 1 | , B - C Ni • Proceeding i n d u c t i v e l y , assume M l ' M 2 * ' M n ' W n n a v e ^ e n constructed, where M l » M 2 ' ' M n ' N n a r e d l s D o l n ' t open connected s e t s , d j ' b j e M j » f ° r 1 - J ' n ' 8 1 1 ( 3 1 ' { d l ' d 2 > dn} and B - ^ » b 2 ' ' ^nj" a r e b o' t l : 1 contained i n N n . Then again by axiom f i v e , there are d i s j o i n t open connected sets M , , and N , , contained i n N such that d„ , , , n + 1 n 1 n+ 1 * bn-KL € "n+1,and B - ^ , , d n , d n + 1 j and B ~ ( b l » ^2 » » b n i b n - f l } a r e b o" f c n contained i n Wn4. x . Let M — [J M n , then M* i s an open subset o f T , Also f o r each n , d i s the only atom of D that i s i n M_ ' n n , and b i s the only atom o f B that i s i n M . Furthermore n n ( 11 1 . , i s a d i s j o i n t family of open connected sets o f v. njn — i , ^ . * . T. M Q i s open i n T , so f o r any a £ M n there i s an open neighbourhood N o f a contained i n M , and so JJOM* C M n , and so each M n i s open m the r e l a t i v e topology on , i n h e r i t e d from T . A l s o , suppose a 6 M ^ i s such that f o r every open set N i n T , where M^HN contains a , M^A N contains a point of M n . Then every open neighbourhood. N o f a contains a point o f M n . Suppose a<eMm , where mf n . Then there i s no open neighbourhood of a that i s contained i n M_ . But t h i s i s impossible since M m i s open i n T . Hence - 15 -M n i s also closed i n the r e l a t i v e topology. Hence no proper superset, i n M ^ , o f M i s connected. Then l e t t i n g M , l n the d e f i n i t i o n o f =• , be the complement- o f M m T , we have DS^B . Hence i f f i n (A) holds then A i s f i n i t e . Q.E.D. . A c t u a l l y , we have proved more than the conclusion o f the l a s t theorem; i f A and B are d i s c r e t e and at most countable then A and B can be put i n a one-to-one correspondence i f and only i f A ~ B . S p e c i f i c a l l y we have: C o r o l l a r y . I f A and B are f i n i t e sets i n T , then B i f and only l f A ^ B . We are now ready to elementarily define the remaining n o n - l o g i c a l constants o f the a r i t h m e t i c o f f i n i t e s e t s i n the theory M / . We wr i t e i n L w ; S(A,B) f o r f m ( A ) A f i n ( B ) A 3 C( atom(C) A C O A = 0 A B = AUC ), ~\- (AB,C) f o r f i n ( A ) A f m ( B ) A f m ( C ) A 3 DE( C = D U E A D H E = 0 A A ^ T J A B Q ^ E ) , X (AB,C) f o r f m ( A ) A f i n ( B ) A f m ( C ) A 3 DF( F ^ B A F ^ B A C ^ D A \/ B( Cbmp*"(l-E,l-D) >atom (E f) F) A Ef\ C ^ A )) , and we w r i t e 0 i n the obvious way. - 16 -I t i s c l e a r that i f A^B and G are f i n i t e sets then S(A,B) holds i f and only i f B = A + 1 , -f (AB,C) holds i f and only i f A+ B - G ,and X(AB,C) holds i f and only i f A • B = C . So we have: P r o p o s i t i o n . The a r i t h m e t i c o f f i n i t e sets can be l n t e r -preted i n the theory M . / P r o p o s i t i o n . The theory M i s undecidable. Proof. By the l a s t p r o p o s i t i o n and the f a c t that the theory M/ i s c o n s i s t e n t , i t i s c l e a r that the theory M ' I S a con-.} s i s t e h t extension o f the a r i t h m e t i c of f i n i t e s e t s , which i s known to be e s s e n t i a l l y undecidable. Hence M ' i s undecidable. Q.E.D. Theorem. The elementary theory M of the l a t t i c e o f closed subsets o f t o p o l o g i c a l spaces i s undecidable. Proof. Suppose M i s decidable. ( Axiom l . 1 ) ^ ( Axiom 2. ) ^ ( Axiom 3. )yy ('Axiom 4.: ) ^ ( Axiom 5. ) ^ ( Axiom 6.) i s a sentence , Ax say , o f L w » and the theory M together with the sentence Ax i s the theory M ' .So by the deduction theorem, f o r any sentence T of L w , Ax >T i s a theorem - 17 -o f M i f and only i f T i s a theorem o f M . So i f M i s decidable there i s a d e c i s i o n procedure f o r sentences o f the form Ax =>T i n M , and hence there i s a d e c i s i o n procedure f o r M . Hence M i s decidable, which c o n t r a d i c t s the l a s t p r o p o s i t i o n . So M i s undecidable. Q.E.D. 3 . U n d e c i d a b i l i t y o f Closure Algebra. A l l the axioms and d e f i n i t i o n s that were w r i t t e n i n can also be w r i t t e n m . The property that A i s an atom can be w r i t t e n i n L c as A^O h\/B{ B < A h B ^ O — > 3-A ) , which i s the same as i n L w . The property that A i s an atom ( o f a Boolean algebra o f subsets of a t o p o l o g i c a l space ) i s denoted by atom (A) , as before. However f o r our purpose, here to re-use the proof o f the u n d e c i d a b i l i t y of l a t t i c e o f closed sub-s e t s , we i n s i s t that the atom be clo s e d , and formally w r i t e at(A) as an abbreviation f o r A £ 0 A CA= V B'( CB = B^ B<A N B^O—> B = A ). We can now w r i t e any d e f i n i t i o n or axiom, formerly w r i t t e n i n L,„ , i n L„ by r e p l a c i n g a l l occurrences o f atom W. KJ. i n the sentence by a t , and making the necessary additions, to insu r e that a l l the objects mentioned i n the sentence are closed. For example, axiom 2 . i s w r i t t e n i n L c as V A(CA = A^ A#G - 18 -> 3 B ( CB = B A at(B) A B<A ) ) . Then these new d e f i n i t i o n s and axioms have p r e c i s e l y the same " t o p o l o g i c a l meaning" as the o l d ones. Let K be the set of sentences of closure algebra true i n every t o p o l o g i c a l space. By adding the counterparts o f axioms one through s i x to N we obtain a theory N'y , such that the ordina r y c l o s u r e algebra on IK i s a model o f N ' , and i n which the ar i t h m e t i c o f f i n i t e sets i s d e f i n a b l e . I n e x a c t l y the same way as before t h i s shows that N i s not a r e c u r s i v e s e t . So we have: Theorem. The elementary theory of closure algebras of t o p o l o g i c a l spaces i s undecidable. 4. U n d e c i d a b i l i t y o f the Topology o f fR. f o r n > 2 . As a bonus from the f a c t that both t h e o r i e s M and N have as models /R , f o r n > 2 we have: Theorem. The elementary theory of. the l a t t i c e o f closed subsets o f |Rn , f o r n > 2 i s undecidable. Theorem. The elementary theory o f the closure algebra, o f , f o r n > 2 , i s undecidable. - 19 -5. An Incompleteness Result. I t i s w e l l known that Zermelo-Fraenkel set theory together with the axiom o f choice, which i s often abbreviated as Z.F.C., i s r e c u r s i v e l y axiomatizable. I t i s also c l e a r that the l a t t i c e o f closed subsets o f i s def i n a b l e i n Z.F.C.. These two fa c t s allow the f o l l o w i n g r e s u l t . Theorem. There i s a sentence S o f elementary l a t t i c e theory such that i t i s n e i t h e r provable nor r e f u t a b l e i n Z.F.C. whether S holds i n the l a t t i c e o f closed subsets o f (fi^. Proof. Since the ordinary mathematical notions can be def-ined i n Z.F.C. , there i s a formula A(x) o f Z.F.C. which a s s e r t s that x i s a closed subset o f ( ] ^ . Now l e t S be any sentence o f . R e l a t i v i z e S to the l a t t i c e o f closed subsets o f 1R by r e p l a c i n g every occurrence o f 3 u F ( u ) l n S by 3 u ( A(u) /\?(u') ) and every occurence o f \f u F(u') by V u( A(u')—>F(u) ') . C a l l the r e l a t i v i z e d sentence S ^ . Define the r e l a t i o n <: i n terms o f the membership r e l a t i o n o f Z.F.C. i n the n a t u r a l way. Let K be the c o l l e c t i o n o f a l l sentences S ^ where S ranges over the sentences o f elementary l a t t i c e theory. K i s c l e a r l y a r e c u r s i v e c o l l e c t i o n . To prove i n 'Z.F.C. that S holds i n the l a t t i c e o f closed subsets o f - 20 -f\\ means p r e c i s e l y to prove i n Z.F.C. . Now we show that not every sentence o f the form S ^ i s provable or r e f -u t a b l e m Z.F.C. For since Z.F.C. i s r e c u r s i v e l y axiomat-l z a b l e the f o l l o w i n g two l i s t s can be s y s t e m a t i c a l l y generated: (1) the l i s t o f theorems-of Z.F.C. , (2) the l i s t of sentences that are r e f u t a b l e i n Z.F.C. . I f every S ^ i s e i t h e r provable or r e f u t a b l e , sooner or l a t e r i t must show up i n one o f the l i s t s (1) or (2) , and so we would have a d e c i s i o n procedure f o r p r o v a b i l i t y i n Z.F.C. o f sentences o f the form S . Since i f S is . p r o v a b l e i n Z.F.C. , S i s true i n the l a t t i c e o f closed subsets o f fR 3*; we would thus have a d e c i s i o n procedure f o r t e s t i n g which sent-ences S are true i n the l a t t i c e o f closed subsets o f fR'5*. In the l a s t s e c t i o n such a. d e c i s i o n procedure was shown not to e x i s t . This c o n t r a d i c t i o n e s t a b l i s h e s the r e s u l t . Remark. I t i s not pre s e n t l y known whether or not the l a t t i c e o f closed subsets o f IR i s complete with respect to set theory. However, i t i s known that the f i r s t - o r d e r theory o f the l a t t i c e o f closed subsets o f FR' i s decidable, ^ see [ §jj . - 2 1 -C H A P T E R 2 . Elementary Equivalences of Topological Spaces. For a language L , r e c a l l that two L ~ s t r u c t u r e s A and B are elementarily equivalent i f any sentence o f L i s true i n A i f and only i f i t i s true i n B. I f A and B are elementarily equivalent we w r i t e • 1 . Weak Elementary Equivalence. Theorem 1 . I f and T 2 are t o p o l o g i c a l spaces, then L(T. ) ~ L ( T „ ) i f and only i f 0(1' ) ^ 0 ( T 0 ) . Proof. Let S be any sentence o f L^ . Form another sent-ence S ^ o f L.w by r e p l a c i n g a l l occurrences of 0 i n S by 1 , a l l occurrences o f 1 by 0 , a l l occurrences of f\ by \J , a l l occurrences o f \J by , and r e v e r s i n g the d i r e c t i o n o f a l l occurrences o f ^ ; that i s A < B becomes B ^ A , For example i f S i s V B:?A( A ^ O A At< B a V CD( A = C U © > C - 0 V J S = 0 )) , then S i s V B ^ A ( A ^ l A B < A A \/CB{ A= C H D — > C = 1 V D = 1 ) ) . C l e a r l y any S and 3 * describe prec-- 22 -l s e l y the same t o p o l o g i c a l property, the only d i f f e r e n c e being that one o f these two sentences describes the property i n terms o f open s e t s , and the other describes i t i n terms o f closed s e t s . Suppose L^-,) L ( T 2 ) and that S i s true i n 0 ^ ) .Then c l e a r l y S* i s true i n L ^ ) and hence i n L ( T 2 ) . Observing that S** i s S , we have that S i s true i n 0(T 2) . By symm-e t r y , i f S i s true i n 0(T 2) , then S i s true i n 0{T-±) . In e x a c t l y the same way, we show that 0(T-. ) /^/ 0(T 9) i m p l i e s L('T, ) ~ M^o) . Hence L(T-, ) ^ L(T«) i f and only i f 0(T->) ~ 0 ( T 2 ) c e Q.B.D. B e f i n i t i o n 1. Let T^ and T 2 be t o p o l o g i c a l spaces. We say T-L and T 2 are weakly elementarily e q u i v a l e n t , and we w r i t e T j L ^ ^ T g i f L ( T 1 ) ^ ^ L ( T 2 ) , ( or e q u i v a l e n t l y 0 ( T . . ) / ~ 0 ( T 2 ) ) . 1 e.e. * In l i g h t o f Theorem 1. we s t a t e the f o l l o w i n g r e s u l t . The proof i s easy, and so we omit i t • P r o p o s i t i o n 2. I f ^ and T 2 are t o p o l o g i c a l spaces, then L(T ) and L(T^) are isomorphic i f and only i f 0(1^) and 0(T o) are isomorphic. - 23 -2. Strong Elementary Equivalence. Theorem 3. I f T X and T 2 are t o p o l o g i c a l spaces, then the f o l l o w i n g are equivalent; (1) A ( T T ) / ^ A ( T ? ) as Lr - s t r u c t u r e s . (2) A(T-j_) /-^ A ( T 2 ) as L K - s t r u c t u r e s . (3) A(T 1) ^ A(T 2) as L Q - s t r u c t u r e s . (4) A(T-i ) A ( T ? ) as L T - s t r u c t u r e s . Here A ( T 1 ) denotes the Boolean algebra o f subsets o f the t o p o l o g i c a l space Proof. ( l ) = A k ( 2 ) . Let S be a sentence o f L K , then S i s true i n A ( T 1 ) i f and only i f the sentence, S ^ , formed from S by r e p l a c i n g a l l occurrences o f " K ( A ) " by " G A ~ A " , I s true i n A ( T X ) . Since A ( T 1 ) ^ A ( T 2 ) as L G -s t r u c t u r e s , S ^ i s true i n A ( T 1 ) i f and only i f S ^ i s true •in A ( T 2 ) . Hence S i s true i n M\) l f and only i f S i s true m A ( T 2 ) . So A ( T 1 ) A ( T 2 - ) A S L K - s t r u c t u r e s . (2) ^=^(3) • Let S be a sentence o f L Q , then S i s true i n A ( T X ) i f and only i f the sentence, S ^ , formed from S by r e p l a c i n g a l l occurrences o f " 0 ( A ) " by " K ( l - A ) " , i s true i n A ( T X ) • Then by the same reasoning as above, since A ( ? 2 ) / ^ / A ( T 2 ^ a s % - s t r u c t u r e s , we have that A ( T ^ A ( T g ) - 24 -as Lg - s t r u c t u r e s . ^3) r ± ^ ( 4 ) , Let S be a sentence of L j , then S i s true i n A(T 1) i f and only i f the, sentence, S ^ , formed from S by r e p l a c i n g a l l occurrences of 11 IA = B " by " B <A ^ O ( B ) f\ \j C( C < A A 0 ( C ) — > C ^ B ) " , i s true i n A'(TX) . Then again since A^-^) /^/A(T 2) as L Q - s t r u c t u r e s we have that A(T-±) •^J A(T ) as L T - s t r u c t u r e s . (4) =z=>(l) . Let S be a sentence of L^ , then S i s true i n A(T •) i f and only i f the sentence, S , formed from S by r e p l a c i n g a l l occurrences o f " CA— B " by " I ( l - A ) = 1-B " , i s true i n A(T ) . By "the same reasoning as above, we have that A(T ) A(T ) as L - s t r u c t u r e s . That completes 1 c.c 2 C the proof. D e f i n i t i o n 2. I f one, and hence a l l , of the conditions of the l a s t theorem hold we say T^ and T^ are s t r o n g l y elem-e n t a r i l y equivalent and w r i t e T^/^JT 3. The R e l a t i o n s h i p between Weak and Strong Elementary Equivalence. In t h i s s e c t i o n we show that strong elementary equivalence - 25 -i s indeed stronger than weak elementary equivalence. Theorem 4 . Let Tj_ and T2 be t o p o l o g i c a l spaces. I f Tj, Tp , then T]_ T 2 * Proof. Let S be any sentence o f L^ . Let S ^ be the sent-ence o f L^ obtained from S by adding K ( A ) immediately a f t e r the f i r s t appearance o f a v a r i a b l e A . For example i f S i s the sentence " A ^ O A \ / B C ( BUC = l A B f ) C = 0 ^ B = O v C — 0 ) " , then S * i s the sentence " A ^ 0 A K ( A ) A \J BC( K(B) A K(C) A BUC=-1 A B r i C - 0 >B — O y C = 0 ) ". C l e a r l y any sentence S o f L i s tru e i n L(T ) i f and only i f the sentence i s W 1 true i n A(T, ). . i f /^J T 9 , then f o r any sentence S o f L^ , the sentence S ^ i s true i n A(T-|_) i f and only i f S ^ i s true i n A ( T 2 ) . Hence S i s true i n L(T]_) i f and only i f S i s true i n L ( T 2 ) . So T - L T 2 . Q.E.D. However two spaces that are weakly elementarily equivalent need not be str o n g l y elementarily equivalent. We give a few examples: Example 1. Let be the one point space with the only p o s s i b l e topology. E x p l i c i t l y , (^ arid the point i t s e l f are - 26 -the only open subsets of . Let T 2 be any space c o n s i s t -i n g o f more than one p o i n t , and having the g l o b a l topology. That i s ^ and T 2 are the only open subsets. Then the map y : O J T ^ — > 0 ( T g ) defined by y{j>)= j) and ^ ( T - ^ - T 2 i s c l e a r l y a l a t t i c e isomorphism. So 0(T,) 0(T ?) , and so T /~^ > T . Since the topology on T, i s d i s c r e t e , the sent-ence \/ A( CA=A ) i s true i n A(T, ) . However the sentence VA( GA =A ') i s c l e a r l y not true i n A(Tg) . So T x and T 2 are not s t r o n g l y elementarily equivalent. Example 2 . There are also examples of i n f i n i t e weakly elem-e n t a r i l y equivalent spaces that are not s t r o n g l y elementarily equivalent. Let (X, <) be any densely ordered set without f i r s t or l a s t elements. We define a subset € o f X to be closed i f whenever x € C and y > x then y £ C . C l e a r l y the f i n i t e union of these closed sets i s closed. Suppose J C^.l i £ j. i s a family o f these closed s e t s , then f o r j C x , x£ C 1 f o r a l l i£ I . So f o r any y > x , y£ ^ f o r a l l i £ l , and s o y^^r c • S o t n e i n t e r s e c t i o n o f any family o f these closed sets i s c l o s e d , and so the closed sets described above define a topology, J , on X . This topology i s c l e a r l y T Q but not . Consider fR. and (j^with t h e i r usual dense ordenngs. We l e t "7 b e t n e topology on defined as above, and we l e t /, - 27 -be the topology on (j^ , a l s o defined i n t h i s way. Define a map h : L ( I R , 7 , R ) > L ( f e » 7 ^ ) b y h (A) = [xeA| xefej f o r A ( L( (f^ , ) . Let A , B € L( , jf |R ) » and assume A C S . This can be assumed without l o s s of g e n e r a l i t y since c l e a r l y e i t h e r A c B or Be A . Then h( Au B ) - h(B) , and h( A R B )=h(A) . Also since h(A) i s c l e a r l y contained i n h(B') , we have h(A) U h ( B ) = h ( B ' ) and h(A)f\ h(B) = h(A) . So h( Au B ) = h ( A ) U h ( B ) and h( ARB )=h'(A)Rh(B) . Suppose A<^B , then there i s a b (j^ such that be B but b ^A , and .so h(A)<^h(B) . So . h i s i n f e c t i v e . Let 3 6 L ( ^ , J^) , then B C . -Let b e l R be the greatest lower bound o f B . C l e a r l y i f we l e t C-|x£(R.|x> b j then C t L ( fl{ ,7»R ) » a n c i h ( C ) — B . So h i s s u r j e c t i v e , and hence i s an isomorphism. So ( JR . , J f l ^ ) ( ( J ^ » j f ^ ) • Consider the f o l l o w i n g statement: For every non-empty closed s e t , C , which i s not the whole space, there i s an element a i n the space such that e i t h e r : (a) a t C and f o r every closed s e t , B , where 3 C C , a.£B , (b) a.^ C and f o r every closed s e t , B , where B^C , a £ B . This can be w r i t t e n i n L^ as: V C( K ( C ) / v C ^ O A Cfl >3a.( atom(a) A ( a < C^ V B{ B^C^ B-fC A K ( B ) — > a n B = 0 ) ) v ( a O G ^ G ^ V B( C S B A B 4 C / V K ( B ) ) a ^ B ) ) ) ) . This statement says that every closed subset of the space, that i s not (j) or the space i t s e l f , has a greatest lower bound. This - 28 -statement i s c l e a r l y true f o r the space ( jj^ , "~J^ ) . However i f C= | x e ^ | x ^ / a j , then C i s a proper non-empty closed sub-set o f ( ( j ^ , t such that (a) does not hold since C has no l e a s t element, and (b) does not hold since there i s no l a r g e s t r a t i o n a l i n the complement o f C . So ( jj^ , T ) and ( (jpt » j " ^ ) a r e n o _ t s t r o n g l y elementarily equivalent. I f the densely ordered set -£,fajis given the topology described i n t h i s example, then an a p p l i c a t i o n o f the above reasoning shows that t h i s space and the r e a l numbers, wi t h topology described as above, are weakiy but not s t r o n g l y elem-e n t a r i l y equivalent. So there are i n f i n i t e weakly elem e n t a r i l y equivalent spaces o f the same c a r d i n a l i t y that are not st r o n g l y elementarily equivalent. 4 . The R e l a t i o n s h i p between Elementary Equivalence and Homeomorphism. P r o p o s i t i o n 5. Let ^ and T g be t o p o l o g i c a l spaces. I f T, and T 0 are homeomorphic , then T, T0 . Proof. Suppose there i s a homeomorphism h ; > T g , then h induces a map h ^ : A(T ) H ( T 2 ) defined by - 29 -( A ) = ^h(a) ^ a t A J , f o r A € A ( T 1 ) . I t i s immediately apparent that the m j e c t i v i t y and s u r j e c t i v i t y o f h guarantee r e s p e c t i v e l y the m j e c t i v i t y and s u r j e c t i v i t y o f h ^ . F i n a l l y , h i s bicontinuous .So h ^ and i t s ( set-theo-r e t i c ) i n v e r s e , h^, , send closed sets to closed sets . So h ^ (CA)—G h ^ (A) and h~^I (GA)-C h~' (A) .So h ^ i s an isomorphism , and so T^ Tg S.e.e. Q.E.B. C o r o l l a r y 6 . Let ^ and T g be t o p o l o g i c a l spaces. I f T, and T 0 are homeomorphic , then T, T~ . Proof. By p r o p o s i t i o n 5. , i f ^ and" T g are homeomorphic, then T, T„ . By theorem 4 . , we also have T, •^^T^ 1 2 < .^e.e. c S.e.e. Q.E.D. Remark.. Both weak and strong elementary equivalence are much weaker equivalence r e l a t i o n s on the c l a s s o f t o p o l o g i c a l spaces than i s homeomorphism. There are s t r i c t l y more than the continuum number o f non-homeomorphic t o p o l o g i c a l spaces. However, i n view o f the " s i z e " o f the language L^ , a w e l l known r e s u l t o f model theory guarantees that there, are at most, the continuum number o f equivalence c l a s s e s up to weak element-ary equivalence. - 30 -Again m view o f the " s i z e " o f the languages L g , 1^. , L Q and L j , the above reasoning shows that there are a l s o at most the continuum number of equivalence c l a s s e s up to strong elementary equivalence. §. Some Results about A(T) and: L ( T ) . Theorem 7. Let T^ and T 2 be t o p o l o g i c a l spaces. (a) I f T x arid T 2 are -spaces and L(T^) and L ( I 2 ) are isomorphic, then. T-^ and T 2 are homeornorphic. (b) I f A(T-L) and A(T 2) are isomorphic, then ^ and T 2 are homeornorphic. Proof. (a) I f 1* and T 2 are ^ -spaces , then L ( T 1 ) and L{T^) contain r e s p e c t i v e l y a l l the s i n g l e p o i n t subsets o f and ? 2 . Let h : L ( T 1 ) >L(T 2) be an isomorphism. Suppose there i s a s i n g l e p o i n t subset A o f T^ , and subset B o f T 2 with more than one element , such t h a t h(A) = B . Then h~\'(B) = A , and since h i s an isomorphism and hence preserves <• , h also sends a s i n g l e point subset o f B to A This c o n t r a d i c t s the m j e c t i v i t y o f h . C l e a r l y h[<p)—cji , and so again by the i n j e c t i v i t y o f h , h does not send . \ - 31 -s i n g l e point sets to <j> . So h sends one point sets to one point sets , and by symmetry t h i s i s also true o f h~ f . So h induces a b i s e c t i o n h ^ : T^ >T 2 ., and h~* Induces a b i s e c t i o n h"^ : T^-^H^ which i s the inverse o f h ^ . For any set A f c L ^ ) , h ^ . ( A ) = | h ^ (a) | a£ A^=h(A) , so h^. i s a closed mapping. S i m i l a r i l y h^' i s a closed mapping . So h i s a homeomorphism, and so i s homeornorphic to (b) Let g : A(T ) >A{1^) be an isomorphism. We have already that A(T^) and A(Q?2) contain r e s p e c t i v e l y a l l the s i n g l e point subsets o f T^ and . By e x a c t l y the same reasoning as above, g induces a b i s e c t i o n g ^ • T.^ ——> , and g~' induces a b i s e c t i o n g ^ l : >T , such that i s the inverse o f g ^ . The isomorphisms g and g ' preserve the closure operator , so g^ and g ~ y are closed mappings. So g : T >T i s a homeomorphism . This completes the proof. 7^ IL 2 Making use of the r e s u l t that f i n i t e e l ementarily equivalent L - s t r u c t u r e s are isomorphic as L - s t r u c t u r e s , we obtain the f o l l o w i n g c o r o l l a r i e s : C o r o l l a r y 8. I f T and T are f i n i t e T -spaces, then * 1 2 1 T and T are homeornorphic i f and only i f T ./ 1 T . 1 2 1 2 Proof. . C o r o l l a r y 6 . shows one d i r e c t i o n i s t r u e . Conversely - 32 -suppose T and T 2 are f i n i t e and weakly elem e n t a r i l y equiv-a l e n t . Then L(T ) and L ( T 2 ) are f i n i t e e l e m e n t a r i l y equiv-a l e n t L„, - s t r u c t u r e s . So L(T ) and L ( T 0 ) are isomorphic. W L d By theorem 7 . (a) , i f we assume T and T 2 are T^ -spaces, then T and T g are homeomorphic. Q.E.D. Co r o l l a r y 9 . I f ^ and T g are f i n i t e t o p o l o g i c a l spaces, then T, and Trt are homeomorphic i f and only i f T-. -^-^ T„ . Proof. P r o p o s i t i o n 5* shows that one d i r e c t i o n i s t r u e . Con-ve r s e l y suppose T^ and T 2 are f i n i t e and s t r o n g l y element-a r i l y equivalent. Then A(T^) and A(Tg) are f i n i t e element-a r i l y equivalent L - s t r u c t u r e s . So AfT.^) and A(T 2) are isomorphic. Then theorem 7. (b) shows that T and T g are homeomorphic. Q.E.D. 6 . The Product Problem. ———.—| Suppose T^ , T^ » ^ 2 T ° & r e " t o P o l o S l c a l spaces, and that T T and T /r^j T ' . I t i s c e r t a i n l y o f m t -1 \jj.e..c. 2 1 oj.e.e. 2 erest whether or not T X T / ^ v ^ T „ X T / l n general. I t i s also o f i n t e r e s t whether o r not the version o f t h i s concerning - 33 -strong elementary equivalence i s true. At t h i s time, both o f these important problems remain unsolved. However, there are examples that show the converse i s not true f o r the case of strong elementary equivalence. More p r e c i s e l y , i f ^ y T_ T ' , then T, i s not n e c e s s a r i l y s t r o n g l y elem-/ / e n t a n l y equivalent to T 0 , even though T, T 0 . Example. Consider the spaces , and jj^ with t h e i r usual t o p o l o g i e s . Since |Rx (R^° and |R^X [ R ^ ° (R*° , we have |R X 1 R ^ ° = |R*X |R*Hmd hence .|R X ( R * * ^ Consider the sentence, S , o f which says the space minus any p o i n t i s connected. This can be w r i t t e n i n as: \/a( atom (a)- > I B A ( A% 0 a A ^ 1 A K(A) ^ K ( l - ( A-a ))') . C l e a r l y S i s true i n A( fR9") , but since removal of any point disconnects |R* , S i s not true i n A( ) . So jf^ and are not s t r o n g l y elementarily equivalent. 7 . Elementary P r o p e r t i e s . A weak elementary property i s a t o p o l o g i c a l property that can be "described" i n L w . S i m i l a n l y a strong elementary prop-e r t y i s a t o p o l o g i c a l property that can be "described" i n a.ny and hence a l l o f the languages L c , L.K , L j , and L Q . E q u i v a l e n t l y , a weak ( r e s p e c t i v e l y strong ) elementary property i s a t o p o l o g i c a l property, such that given two weakly ( respect-i v e l y s t r o n g l y ) elementarily equivalent t o p o l o g i c a l spaces, e i t h e r both or n e i t h e r of the spaces has the property. So i n order to show a c e r t a i n property i s not a weak ( r e s p e c t i v e l y strong ) elementary property, i t i s necessary to f i n d two weakly ( resp-e c t i v e l y s t r o n g l y ) elementarily equivalent t o p o l o g i c a l spaces such that one o f the spaces has the property and the other doesn't. Example 1. Connectedness has been p r e v i o u s l y described i n . So connectedness can c l e a r l y also be described m any o f the "strong languages". Hence connectedness i s both a strong and a weak elementary property. Of course any weak elementary property i s also a strong elementary property. Example 2. A l l o f the usual separation p r o p e r t i e s are strong elementary p r o p e r t i e s . To say that a space i s we wr i t e m : V A B ( atom(A) A atom(B)^ A £ B^ 3 - P Q ( A ^ P a 3< Q ^ A 0 Q— 0^ B f l P = 0 A C(1-P)-1-P AC(1-Q)=1-Q )) . S i m i l a r i l y we w r i t e i n : \/AB( atom(A) A atom(B) A A ^ B — > 3 P Q ( A < P A B < Q A POQ^O^ C(l-P) - 35 -=-l-P A C(l-Q) = l-Q )) to say that a space i s T 2 ( Hausdorff ), \/AB( atom (A) A CB=B A Ar\B = 0 ^ PQ( A < P A B < Q A PO Q= 0 A C(1-P)~1-P A-C(1-Q)=1-Q )) to say that a space i s T^ ( Reg-u l a r ) , and \/ AB( CA = A A CB = B / V A 0 B = 0 ^3pQ( A < P A B < Q A Pf\-Q=0 A C ( l - P ) = r l - P A C(l-Q) = l-Q )) to say that a space i s . (Normal) Example 3 . The separation property T^ i s not a. weak elem-entary property. For example, consider the r e a l numbers wi t h | (j)^ U { IR} U { [ n " Kk » n +^| n ^ 1 } U s e t o f a l l f i n i t e unions o f closed i n t e r v a l s o f the form £ n- '/3 ,n+^^ J , where n ^ ^ a s the family o f closed subsets. C l e a r l y t h i s family o f closed subsets describes a topology. Also consider the i n t e g e r s , , with (j) ,~fj^, s i n g l e p o i n t s , and f i n i t e c o l l e c t i o n s o f s i n g l e points as the closed subsets. This a l s o describes a topology. Consider the mapping Y ' : L ( ~JL ) ^ ^ ^ ^ s u c h t h a t f o r n» n l > » n k c I . ^ ({»})= [»- •/? .»+y3] >t( ni •—- n* '= [°i - /v n 1 + u y [ n f c - y% ,n k + 1 / 3-| , ^ ( j, ) j , and 7 ) — ^ . C l e a r l y i s a l a t t i c e isomorphism, and hence ~Jj__rsj ^ , Since s i n g l e points are closed i n /£_is a ^ -space. However s i n g l e points are not closed i n , and hence ft^ i s not a T 1 -space. Hence the separation property ^ i s not a weak elementary property. In view of example 2, i t i s c l e a r that - 36 -the above spaces \J\ and ~]J_ are not s t r o n g l y elementarily equiv-a l e n t . S i m i l a r i l y , among many other simple t o p o l o g i c a l p r o p e r t i e s , dense, nowhere dense, and t o t a l l y disconnected can e a s i l y be shown to be strong elementary p r o p e r t i e s . In the next s e c t i o n , we w i l l show that s e p a r a b i l i t y and compactness are n e i t h e r weak nor strong elementary p r o p e r t i e s , 8. D i s c r e t e Spaces. Let L ^ denote the language of Boolean algebra equipped i n a d d i t i o n with unary predicate symbols at and f i n , where at(A) i s i n t e r p r e t e d as " A i s an atom " and f i n ( A ) i s i n t e r -preted as " A i s f i n i t e " or sometimes as 11 A i s at most count-able ". I n i t i a l l y we prove the f o l l o w i n g . Lemma 10. Let f i n be i n t e r p r e t e d as f i n i t e . I f S i s any sentence o f L * , then there i s a q u a n t i f i e r f r e e sentence T o f L ^ such that i f B i s any i n f i n i t e power set algebra, then S i s true i n B i f and only i f T i s t r u e m B . Proof. Consider the formula ^ x p ( x» v i • ~ » v n ) * - 37 -where P i s quantifier free. P can be written i n the form P^ \j P 2 V V J ? k where each P 1 rr P 1( x, y± , , y Q ) i s of the form A-^ A^n. where the A., are of the form V or n V , where V i s atomic. The formulas x ( ^ v P g v -yP^. ) and ^ x P l V /^x P 2 V — v;3x Pfc a r e e ( l u l v a l e n " t . So i n order to prove that ^ x ^ l s equivalent ( with respect to i n f i n i t e power set algebras ) to a quantifier free formula i t i s c l e a r l y s u f f i c i e n t to prove that each 9 x p 1 ( x » Jj_ . » YQ ) i s equivalent to a quantifier free formula. So i n order to simplify things we can assume that P i s a conjunction of atomic formulas and negations of atomic formulas. P( x , 71 f , y n ) mentions " o b j e c t s " y x , , yQ_ ^ These objects p a r t i t i o n the algebra into at most 2 n parts. More precisely these parts are a l l sets of the form Vv^ O — H Wn , where each i s either y.. or the complement of y^ . For the moment, i n order to simplify things we w i l l write a' f o r 1-a, where a i s an object. P( x, y 1 , , y n ) i s of the form A f\^m w n e r e each i s either a—b or aqtb or at (a) or "l at (a) or f i n (a) or 1 f i n (a) , where a and b are constructed from x and , , y n by use of U , H , and ' , To determine i f an x exists that s a t i s f i e s these conditions i t i s only necessary to know whether or not certain unions of the n ' 2 parts are atoms, and whether or not certain unions of these are - 38 -f i n i t e . This can be described by a combination of quantifier free formulas that involve only y^ , , y n , t h e i r Boolean comb-inations, at and f i n . The proof, up to now, i s rather unintuitive and should be c l a r -i f i e d by an example. Consider the sentence " 1 x ( x n y n = y 0 i at( y 4 O x ) A ~» ( x n y 3 = 0 ) ,\ "1 fm(x) A x v j y 4 = l ^ a t ( y 1 ) ) •» . For an x to exist such that x H y ^ - y ^ i t i s necessary and s u f f -i c i e n t that y 2 be contained i n y^ , For an x to exist such that also 1 at( y ^f\x ) holds i t i s necessary and s u f f i c i e n t that i n addition to y 2 being contained i n y^ that y^f\ ( y 2uyj) i s not an atom. S i m i l a n l y , for the remaining parts of the above sentence, i n addition to the f i r s t two, to be s a t i s f i e d by some x, i t i s necessary and s u f f i c i e n t that i n addition to the already mentioned conditions that y ^ f U y 2 u y l ' * y 2 u y l l s n o" f c f l n l ' t e » y^ be contained i n y2Uy-j_' , and f i n a l l y that y1 i s an atom. To describe t h i s situation by the above mentioned scheme we would write " ( y 2 ny 1 =y 2 )A ("« a t ( y ^ l y 2 u y i ) - ) ^ ( i ( - y 3 n ( y 2 uy i ) =ro ) ) A ( i f m ( y2u y-^ )) N ( y4V\( y2nyi )=° ) A ( a * ^ ) ) " . This sentence i s quantifier free. Now consider a sentence of the form \/ z3 x P( x, z, y x , , y ) , where P i s quantifier free. By the above, the sentence ^ x ^ i s equivalent ( with respect to i n f i n i t e power set algebras ) to Q( z, y1 , , y n ) which i s quan t i f i e r free. So the sent-some - 39 -ence \/ z ^ | x P i s equivalent to ^ z Q , which i s i n turn always equivalent to ^ ^| z ( T Q ) . We know that the sentence z ( - | Q ) i s equivalent, i n our sense, to some q u a n t i f i e r f r e e sentence S3 . So f i n a l l y \J z ^ x P i s equivalent to "| S , Generally, the same s o r t o f procedure-, as i n the l a s t paragraph w i l l show th a t any prenex normal form sentence i s equivalent ( wi t h respect to i n f i n i t e power set algebras ) to a q u a n t i f i e r f r e e sentence. We may have to apply the procedure many more times though. That completes the proof. For a s i m i l a r technique o f q u a n t i f i e r e l i m i n a t i o n see £ 4j , Theorem 11. Any i n f i n i t e d i s c r e t e spaces, A and B, are s t r o n g l y e l e m e n t a r i l y equivalent. Proof. Let S be any sentence o f L^ . Let S be the sent-ence o f L,» formed from S by d e l e t i n g a l l occurences o f the pred i c a t e symbol E . For example i f K(A) occurs i n S then we remove i t . Every subset o f a d i s c r e t e space i s c l o s e d , and so 'S i s t r u e i n power set algebra o f a d i s c r e t e space i f and only i f S i s t r u e . Now l e t 1 be any sentence o f L , Then by lemma 10 , 1 i s equivalent,with respect to i n f i n i t e power set algebras,to a q u a n t i f i e r f r e e sentence Q o f L , But Q is made tip only o f 0 , 1 , f i n , at , U , n » - , and s , So i f Q is - 4 0 -true i n any i n f i n i t e power set algebra, i t i s tru e i n a l l i n f i n -i t e power set algebras. But S i s also a sentence o f L . So S i s e i t h e r true i n a l l i n f i n i t e power set algebras o r m none. This shows that any i n f i n i t e d i s c r e t e spaces are st r o n g l y elementarily equiv-Now consider the countable d i s c r e t e space. This space i s c l e a r -l y separable. Since no proper subspace o f a d i s c r e t e space can be dense, i t i s also c l e a r that no uncountable d i s c r e t e space i s separable. But we have j u s t shown that any i n f i n i t e d i s c r e t e spaces are s t r o n g l y elementarily equivalent. So we have proved the f o l l o w -i n g . C o r o l l a r y 12^ S e p a r a b i l i t y i s not a strong elementary property. ( Hence s e p a r a b i l i t y i s not a weak elementary property ). F i n a l l y we t a c k l e the problem o f showing that compactness i s not a strong elementary property. Theorem 11. The one point c o m p a c t i f i c a t i o n s o f any i n f i n i t e d i s c r e t e spaces are st r o n g l y elementarily equivalent. Proof. F i r s t l y , d i s c r e t e space are l o c a l l y compact Hausdorff spaces, so t h e i r one point c o m p a c t i f i c a t i o n s are defined. - 41 -In the proof o f theorem 11 we proved more than was requi r e d . We showed that any i n f i n i t e power set algebras are el e m e n t a r i l y equivalent with respect to the language L . We now add to the language a pred i c a t e symbol 0 , which we w i l l as before i n t -e r p r e t as open. I t i s c l e a r that the power set algebras o f i n f i n i t e d i s c r e t e spaces are s t i l l e lementarily equivalent with respect to t h i s new language. We f u r t h e r add a constant symbol a to t h i s new language to obtain a language L , This constant symbol can be thought o f as the point o f i n f i n i t y . I t i s a standard r e s u l t o f model theory that adding a constant symbol to a language does not a f f e c t elementary equivalence. In p a r t i c u l a r , the power set a l g -ebras o f i n f i n i t e d i s c r e t e spaces are elementarily equivalent w i t h respect to the language L . For a reference on t h i s and other b a s i c p o i n t s o f l o g i c see £^63* Let D- and D_ be i n f i n i t e d i s c r e t e spaces. Let A. be the set o f sentences o f L which are true i n A(D.) and such that -a occurs a f t e r a l l occurences o f v a r i a b l e s and constants. For example the sentence " V x 3y (U-aJs-? ( x-a)U(y-a)) " i s an e l -ement o f A± and A 2 * We know A~L^=z A g . Let T . . be the theory having the c o l l e c t i o n A. as axioms. We add the axiom *' V x ( a .< 2 c ^ 0 ( x ) «f » f m ( l - x ) ) " to both t h e o r i e s , f x and f £ , and obtain t h e o r i e s and S 2 r e s p e c t i v e l y . C l e a r l y S 1 » S 2 . Let 3 denote the one point c o m p a c t i f i c a t i o n o f B. . I t i s c l e a r that a sentence o f L i s true i n A(© ) i f and only i f i t J - 42 -i s a theorem o f S . Since S 2 = 5 S , a sentence o f L i s e i t h e r 2 1 2 ' true m both A ^ ) and A(:E>2) or i n n e i t h e r . But a sentence o f LQ I S also a sentence o f L . So D^ r ^ J T)^ • That completes the s.e.e. proof. U n t i l now we have i n t e r p r e t e d the predicate symbol f i n as f i n -i t e . The proof o f lemma 10 does not req u i r e t h a t f i n be i n t e r p r e t -ed as f i n i t e i n order to be v a l i d . A l l that i s r e a l l y required i s that f i n be i n t e r p r e t e d as " having smaller c a r d i n a l i t y than the space i t s e l f M . The same i s true o f the proof o f theorem 13. So i n t h i s whole s e c t i o n f i n could be i n t e r p r e t e d f o r a topolog-i c a l space i n t h i s new sense. Let A be the d i s c r e t e space with c a r d i n a l i t y c . Let A be the one point c o m p a c t i f i c a t i o n o f A . Let B be the space o b t a i n -ed from A by adding a s i n g l e point a , and with topology con-s i s t i n g o f the open sets i n A and subsets o f B which contain the point a and have at most countable complement-; By the above reasoning A C"5T/ B . But A i s compact and B i s not. So we have proved the f o l l o w i n g r e s u l t . m C o r o l l a r y 14. Compactness i s not a strong elementary property. ( Hence compactness i s not a weak elementary property ) 4 - 43 -9. A P a r t i a l C h a r a c t e r i z a t i o n o f the Heal Numbers. In t h i s s e c t i o n we look at the e x p r e s s i v e power of the l a n g -uage I»c ( o r e q u i v a l e n t l y the languages L j , and L Q ) . In p a r t i c u l a r , we o b t a i n p a r t i a l r e s u l t s toward the problem of char-a c t e r i z i n g the r e a l numbers i n . So any t o p o l o g i c a l space which i s s t r o n g l y e l e m e n t a r i l y e q u i v a l e n t to the r e a l numbers shares many important t o p o l o g i c a l p r o p e r t i e s with the r e a l numbers. We now l i s t s e v e r a l axioms which d e s c r i b e a t o p o l o g i c a l space X . Most o f the p r o p e r t i e s d e s c r i b e d by these axioms have already been w r i t t e n i n i n t h i s t h e s i s or o b v i o u s l y can be w r i t t e n i n Lg • The few p r o p e r t i e s t h a t t h i s does not apply to w i l l be d e s c r i b e d i n as they are i n t r o d u c e d . D e f i n i t i o n s and theorems are g i v e n i n the a p p r o p r i a t e p l a c e s . Axiom 1. I i s Hausdorff. Aymm P. . X i s connected. Axiom 3 . Removal o f any p o i n t from X d i s c o n n e c t s X i n t o e x a c t l y two connectedness components. D e f i n i t i o n . I f a, b, c £ X , we say c separates a from b i f a and b l i e i n d i f f e r e n t connectedness components of X —{cJ „ L e t p and q be any two f i x e d d i s t i n c t p o i n t s o f X . - 44 -We say that a i s l e s s than b with respect to ^p, , or simply t h a t a i s l e s s than b and we w r i t e a ^ b i f one o f the f o l l -owing f i v e p r o p e r t i e s holds. ( 1 ) a separates p and b , but a does not separate q and p , and q does not separate a and p , For example : r , , % P a b ( 2 ) a separates p and q , but b does not separate p and q , and q does not separate a and b. For example : > # • • < ~ % a, P b ( 3 ) a and b both separate p and q , and a also sep-arates b and q . For example : , » ., • , _ % o* fe ? ( 4 ) b separates p and q t and q separates a and h . For example : » « > » - — — — ft. \ bp ( 5 ) b separates a and q , and q separates p and b , For example : — • • • • — <>-• »> 1 P We w r i t e a b i f a < b or a r = b . The above d e f i n i t i o n can c l e a r l y be w r i t t e n i n the language L . I t i s also c l e a r t h a t ^ i s a p a r t i a l ordering on the space X . E q u i v a l e n t l y the p a i r ( X, < ) i s p a r t i a l l y ordered . - 45 -Axiom 4 . ( X, <L ) i s densely ordered. Axiom 4 can be w r i t t e n i n L^ as V a \j b ( atom ( a ) ^ atom ( b ) ^ a ^ r b > a ^ t > V b ^ a / \ ^ c ( atom( c ) A c ^ a c ^ r b ( a £ c A c £ b ) N / ( c j g a . b f c ))) . We now give two obvious but important d e f i n i t i o n s , A subset A o f X i s an i n t e r v a l i f whenever a, b ,c fe X are such that a, b fe A and a $ c ^ b then c fe A , A subset A o f X i s * * r i " ) bounded i f there e x i s t a, b fe X such that A C j c ^ l l a c £ b > , The terms upper bound , bounded below and so on have the obvious meanings here. Axiom 5, ( X, i s ) i s complete. Axiom 5 can be w r i t t e n i n L^ as V A ( 3 B ( atom( B ) A V a ( a £ A A a t o m ( a ) —>a 4 B )) > 3 C ( atom( C ) A \ / a ( a < A jyatom( a ) —^ a £ C )) © ( atom( B ) • V a ( a * A A atom( a ) — > a«£ B )- >C ^.B )) . This says t h a t any subset o f X which has an upper bound has a l e a s t upper bound. P r o p o s i t i o n 15. ( X, f£ ) has the property that every i n f i n i t e * bounded subset, Y , has an accumulation point i n X. ( This i s o f course true o f any complete densely ordered space ) . Proof. E x t r a c t any sequence ( y n ^ n m 1,2 from Y. Let X Q S I g . l . b . ( y n , 7 n 4 . 1 Then < x n ) n » i , 2 , i s an i n c r e a s i n g sequence which i s bounded above. Since ( X , i ~ ) i s comp-- 46 -l e t e there i s a l e a s t upper hound , b , f o r the sequence . C l e a r l y every open neighbourhood o f b contains some o f the seq-uence ( x n ^ , f o r otherwise an upper bound f o r t h i s sequence, s m a l l -er than b , could e a s i l y be found. So b i s an accumulation point o f the sequence { ^ n ^ . I t fol l o w s immediately that b i s also an accumulation point o f ^ y Q ^ .So b i s an accumulation point o f Y. P r o p o s i t i o n 16. ( X, 4s. ) l s uncountable. Proof. Since ^ i s a dense order, X i s c l e a r l y i n f i n i t e . * ' • r Suppose X i s countably i n f i n i t e , and l e t X s £ x 1 , x 2 , c. Let be any bounded neighbourhood o f x^ . Proceeding i n d u c t -i v e l y , suppose U n has been constructed such that U n ^ ^ , then there i s a non-empty open set u n + , j L s u c t l "that u n ^ ^ C U n and x n 4 * W l * H e n ° e " l 2 u"2 ? — - <f> ' B u t l f y.. i s picked such that y.. fe u\ , then £ y 1 , y 2 , J i s bounded since U, i s bounded. By p r o p o s i t i o n 15 ( X, £ ) i s complete. So , y 2 , J has an accumulation p o i n t , y , say. Then si n c e J y n , y n + > 1 , J l s contained i n U n f o r each n , y must be a l i m i t point o f U R f o r each n . Since U R i s c l o s e d , y fe f o r each n . So yfe pj' U Q . This i s a c o n t r a d i c t i o n . Hence ( X, £r ) i s uncountable. Lemma 17. I f A i s a subset o f X without accumulation point i n X , then A i s countable. - 47 -_ Proof. S e l e c t any a £ A . I f a i s not the l a r g e s t element o f A , then there i s a next l a r g e r element, a.^ say. Otherwise A would have an accumulation p o i n t . Proceeding i n d u c t i v e l y , having found a , i f a i s not the l a r g e s t element o f A , then A has n * n ' a next l a r g e r element, a ^ say. I f there i s a b £ A such that a < b , but b i s not one o f the a 's , then the i n f i n i t e subset * £ a^ , a 2 , a^ , J of A i s bounded above by b and bounded below by a . By p r o p o s i t i o n 15 t h i s subset o f A must have an accumulation p o i n t , and so A must have an accumulation p o i n t . This i s a c o n t r a d i c t i o n . S i m i l a n l y we l e t a_^ be the next s m a l l -er member o f A a f t e r a , i f a i s not the smallest member o f A . I f a n i s not the smallest element o f A , we l e t a _ ( n . * . T _ ) o e the next smaller. By the same reasoning as above, every element o f A , smaller than a , i s a^ f o r some p o s i t i v e i n t e g e r m . Thus A i s the union o f the po i n t a with two other s e t s , which are at most countable. So A i s at most countable. Q . E . I . We now add a f i n a l axiom to the l i s t . Axiom 6. ( l ) For every point a € X there i s a subset A* of X , such that a i s the only accumulation point o f A* , and * a f o r a l l b £ A* , a <.b . a * ( i i ) For every point a € X there i s a subset A* a o f X , such that a i s the only accumulation point o f A_ , and f o r a l l b £ A . b < a . a * - 48 -- + Lemma 18. For any a £ X , A a and A & are both countable. P r o o f f P i c k any b £ A™" . The set o f a l l x £ A & such that x ^ b has no accumulation p o i n t , and i s hence countable ( o r perhaps f i n i t e ) • We l e t b, be the next l a r g e r element o f A_ a f t e r b , and proceeding i n d u c t i v e l y i f b R has been found, f o r a p o s i t i v e i n t e g e r n , we l e t b n ^ . i l a e the next l a r g e r element of A & a f t e r b . I f there i s a yg A. such that b y , but y i s not one n a $ o f the a m 's , then there must be an i n f i n i t e number o f elements o f A , l e s s than y , and so A_ has an accumulation point which i s no greater than y . This c o n t r a d i c t s the f a c t that a i s the only accumulation point o f A„ . So A„ i s the union o f two countable sets and i s hence countable. S i m i l a r reasoning shows that A_ i s countable. Theorem 19. ( X,< ) i s f i r s t countable. _ Proof. Let S be the set o f a l l open subsets o f X o f the form fx I aif-C x <b'Z, where a*£ A*" and b'£ A*. By the l a s t lemma, i t i s c l e a r that S i s a countable family o f open s e t s . Let B be any open neighbourhood of the point a £'X . I t i s c l e a r that there i s an open i n t e r v a l o f X , A , contained i n B and c o n t a i n i n g the point a . This open i n t e r v a l must contain some point p £ A"* and some point q £ A^. Then £ x \ p < x < , q l i s a member o f S which i s contained i n A and hence i n B. 'So S l s a countable l o c a l base at a . So ( X , £ ) i s f i r s t countable. * - Q.E/1. - 49 -CHAPTER 3 . The C l a s s i c a l Theorems o f Model Theory. In t h i s chapter we examine the question o f whether the comp-actness theorem, the Lowenheim-Skolem theorems, and the complete-ness theorem hold f o r t o p o l o g i c a l spaces. We give counterexamples to show that these r e s u l t s f a i l i n t h i s new s e t t i n g . Let S be a set o f sentences o f L^ . Suppose that A"(T) i s a model o f S , where T i s a P a r t i c u l a r t o p o l o g i c a l space, l e say tha t A(T) i s a t o p o l o g i c a l model o f S , o r oft e n more l o o s e l y say that T i s a t o p o l o g i c a l model o f S . This d e f i n i t i o n w i l l be used sev e r a l times i n t h i s chapter. 1. The Compactness Theorem. Let S be any c o l l e c t i o n o f sentences o f L^ , and suppose that every f i n i t e s u b c o l l e c t i o n o f S has a t o p o l o g i c a l model. The compactness theorem guarantees that S has a model, and i n f a c t has a model which i s a Boolean algebra with unary operator symbol. In the f o l l o w i n g , we show that S need not have a top-o l o g i c a l model. We now give a l i s t o f axioms that describe c e r t a i n t o p o l o g i c a l p r o p e r t i e s . A l l these can c l e a r l y be expressed i n the language L;r, - 50 -We w i l l show that although any f i n i t e c o l l e c t i o n o f these axioms has a t o p o l o g i c a l model, the e n t i r e l i s t has no t o p o l o g i c a l model. For convenience, the space that these axioms attempt to describe w i l l be denoted by X . Axiom 1. X i s normal. Axiom 2. X i s connected. Axiom 3. I f a 6 X , then X — £aj has at most two connected-ness components. D e f i n i t i o n . A point a i s c a l l e d r e g u l a r i f X —{a} i s connect-ed. Otherwise i t i s c a l l e d a vertex p o i n t . I f a i s a r e g u l a r point and x i s a vertex p o i n t , then we l e t I(a,x) denote the connectedness component o f X —{x} that contains a . Axiom 4 . There i s a r e g u l a r point a such that : ( 1 ) For any vertex points x and y , e i t h e r I(a,x) C I ( a f y ) or I(a,y) C I(a,x) ( 2 ) There i s a vertex p o i n t x ^ such that f o r any vertex p o i n t y , i f I ( a , x f ) C I(a,y) then x f — y . There i s a vertex point x x such that f o r any vertex p o i n t y , i f I{atx±) I(a,y) then x x-» y . ( 3 ) I f x i s a vertex point which i s not x f , then there i s a vertex point y such that I(a,x) « j^I(a,y) , and i f z i s a vertex point such that I(a,x) t ^ I ( a , z ) ^ I(a,y) , then - 51 -sssy . I f x i s a vertex point which i s not x i , then there i s a vertex point y such that I(a,y) I(a,x) , and i f z i s a vertex point such that I ( a , y ) C I ( a , z ) CZ I(a,x) , then z = y . ( 4 ) Let S be any set o f vertex points such that i f x € 6 and I ( a , y ) C I(a,x) , where y i s a vertex point , then y fe S . Then there i s a vertex point z such that f o r a l l x fe S , I(a,x) Cm I(a,z) > £>n<i there i s no vertex point y I(a,y) C I(a,z) and I(a,x)C I(a,y) f o r a l l x feS . Axiom 5. This w i l l c o n s i s t o f an i n f i n i t e l i s t o f axioms. We l e t axiom 5(n) , f o r each p o s i t i v e i n t e g e r n , say that there e x i s t at l e a s t n vertex p o i n t s . The e n t i r e l i s t o f axioms that we have j u s t given w i l l be den-oted by . Lemma 1. has no t o p o l o g i c a l model. _ P r o o f . By axiom 5 , the set V o f vertex points must be i n f -i n i t e . Let a. be a vertex point that s a t i s f i e s a l l the co n d i t i o n s o f axiom 4 . We w i l l now use these c o n d i t i o n s . There i s an x Q f e V such that f o r any y g V ,. I(a,x Q) C I(a,y) . Proceeding i n d u c t -i v e l y , having found x n f e 7 , there i s an x n 4 i l € V such that I ( a , x n ) C I ( a , x n + 1 ) » a n d l f z £ v l s s u c h t h a t I ( a » x n ) ^ I ( a , z ) C 1 ( a f \ + x ) , "then Z S Z Q + 1 . - 52 -By p a r t ( 4 ) o f axiom 4 , there i s a y fe V such that I ( a , x n ) C I(a,y) , f o r a l l n , but there i s no z Q V such that I ( a , x n ) C I ( a , z ) , f o r a l l n , and I ( a , z ) <j^I(a,y) . There i s a w fe V such t h a t I ( a , w ) I ( a , y ) , and i f u fe V i s such that I (a,w) C I (a,u) ^ I (a,y) , then w S u . C l e a r l y I(a,w)sf: I ( a , x n ) , f o r any n . There are no other p o s s i b i l i t i e s . So „A_ has no t o p o l o g i c a l model. ^ _ Lemma 2 . Any f i n i t e subset o f the l i s t o f axioms , A , has a t o p o l o g i c a l model. Proof. Any f i n i t e subset o f contains only a f i n i t e number o f the axiom 5(n) f s . Hence we need only have a f i n i t e number, m say, o f vertex p o i n t s . iFor the case m ss 3 , the f o l l o w i n g diagram d e p i c t s a subset o f I B which has three vertex p o i n t s , and i n which axioms one through f o u r h o l d . ^ - 53 -x Q , x1 and x 2 are the vertex p o i n t s . I t i s c l e a r that f o r any i n t e g e r m a s i m i l a r diagram can be given that depicts a subset o f (|^ , with ( at l e a s t ) m vertex p o i n t s , i n which axioms one through four hold. Theorem 3 . The compactness theorem does not hold f o r t o p o l o g i c a l spaces. More p r e c i s e l y , i f S i s a set o f sentences o f such tha t any f i n i t e subset o f S has a t o p o l o g i c a l models then S need not have a t o p o l o g i c a l model. 2, The Completeness Theorem. In the l a s t s e c t i o n we gave an i n f i n i t e s e t , .A. , o f sent-ences o f L c such that any f i n i t e subset o f J\, has a t o p o l o g i c a l model , but A i t s e l f has no t o p o l o g i c a l model. By the ( ordinary) compactness theorem, A has a model and hence i s a c o n s i s t e n t s e t o f sentences.We have the f o l l o w i n g theorem. Theorem 4. The completeness theorem does not hold f o r topolog-i c a l , spaces. More p r e c i s e l y , i f S i s a c o n s i s t e n t s e t o f sent-ences o f , then S does not n e c e s s a r i l y have a t o p o l o g i c a l model. - 54 -5. The Downward Lowenheim-Skolem Theorem. Let S be a set o f sentences o f L^ , and suppose that S has a t o p o l o g i c a l model. L^ i s a countable language, and so by the downward Lowenheim-Skolem theorem, S has a model which i s an at most countable Boolean algebra with u n i t a r y operator symbol. The f o l l o w i n g example shows that S does not n e c e s s a r i l y have an at most countable t o p o l o g i c a l model. So the downward Lowenheim-Skolem theorem does not hold f o r t o p o l o g i c a l spaces. As c a r d i n a l i t y i s important here, i t i s necessary to be more c a r e f u l l about the d i s t i n c t i o n between T and A(T) , where T i s a t o p o l o g i c a l space. In s e c t i o n 9 o f chapter 2 , we e x h i b i t e d a s e t , ^ say, o f sentences which describe a t o p o l o g i c a l space (X, £ ) # A( JR ) i s a t o p o l o g i c a l model o f , and i n f a c t (X, £ ) has many of the t o p o l o g i c a l p r o p e r t i e s o f the r e a l numbers. By p r o p o s i t i o n 16 , (X,6 ) i s uncountable, and so A((X, £ )) has c a r d i n a l i t y at l e a s t 2 C . So i s a set o f sentences of Lg which has a t o p o l o g i c a l model, but has no t o p o l o g i c a l model o f c a r d i n a l i t y * C c . Most importantly ^ has no countable topolog-i c a l model. Theorem, 5. The downward Lowenheim-Skolem theorem does not hold f o r t o p o l o g i c a l spaces. More p r e c i s e l y , i f S i s a set o f sent-ences o f L that has a t o p o l o g i c a l model, then S does not nec-C - 55 -e s s a n l y have an at most countable t o p o l o g i c a l model. We s h a l l devote the r e s t o f t h i s s e c t i o n to examining how bad-l y the downward Lowenheim-Skolem theorem f a i l s f o r t o p o l o g i c a l spaces. I t turns out t h a t , i n a sense, i t may not f a i l very badly. There are only countably many sentences of , and so there are c sets o f sentences of l c ,.We suppose that S Q , , , S , , where a<. c , i s a w e l l - o r d e r i n g o f t h i s family o f s e t s . I f "S has a. t o p o l o g i c a l model, l e t u be the s m a l l -a / a . est c a r d i n a l i t y o f t o p o l o g i c a l models o f S„ , I f S has no top-a, a o l o g i c a l model , l e t jx & be 0 , We l e t "X Q be fX Q . Suppose "X ^ has been defined f o r a l l b ^. a . -We l e t X a — sup ( { ^ g \ U (Xh l D a } ) • A n a l l y , l e t A = sup "X a . We now have t n v -l a l l y the f o l l o w i n g theorem. i Theorem 6 . _Let S be a set o f sentences b f I»c which has a t o p o l o g i c a l model. Then S has a t o p o l o g i c a l model o f c a r d i n a l -i t y <£ X • ( ^ 1 8 t i i e i n f i n i t e c a r d i n a l defined above ) , Con.iecture. X 5 = , 2 C . That i s , S has a t o p o l o g i c a l model such tha t the underlying t o p o l o g i c a l space has c a r d i n a l i t y ^ c . There i s no hard evidence to support the above conjecture. I t seems reasonable s i n c e there appears to be no property of elem-entary topology that requires the t o p o l o g i c a l space , u n d e r l y i n g a t o p o l o g i c a l model, to have c a r d i n a l i t y ^ c , - 56 -We do have a p a r t i a l r e s u l t though. Loosely, i f there e x i s t s a measurable c a r d i n a l , then e i t h e r the ^ m theorem 6 i s very l a r g e , o r closure topology does not determine the elementary theory o f the r i n g o f continuous functions on a t o p o l o g i c a l space. The l a t t e r seems more p l a u s i b l e . As a general reference on the r i n g of continuous functions on a t o p o l o g i c a l space see 11 Sings o f Cont-inuous Functions " , by Gillman and J e n s o n . This reference i s ^2*^ i n the b i b l i o g r a p h y . We l e t C(X) denote the r i n g o f continuous functions on a space X . We now s t a t e our r e s u l t p r e c i s e l y . Theorem 7. I f there e x i s t s a measurable c a r d i n a l then e i t h e r : ( 1 ) There e x i s t I - i -spaces, X and Y , such that X /—• / Y , but C(X) and C(Y) are not e l e m e n t a n l y equivalent with respect to the language of r i n g theory. or ( 2 ) There e x i s t s a space, X , with measurable c a r d i n a l , which i s not s t r o n g l y elementarily equivalent to any space with non-measurable c a r d i n a l . . Proof. A l l spaces i n t h i s proof are T - i -spaces. A space X i s s a i d to be externally disconnected i f every open subset of X has open c l o s u r e . X i s a p-space i f every prime i d e a l of C(X') i s maximal. By 12 H- 6 on page 169 o f Gillman and J e n s o n we have: ( a ) 'Every extremally disconnected p-space with non-measurable - 57 -c a r d i n a l i s d i s c r e t e . By 4 J - 8 on page 63 o f Gillman and J e n s o n , a space X i s a p-space i f and only i f f o r every f £ C(X) there i s a f Q £ 2 C(X) such that f f Q == f . The l a t t e r property i s c l e a r l y an elementary property o f the r i n g o f continuous functions on a top-o l o g i c a l space, ( In other words, the l a t t e r property can be des-c r i b e d i n the language o f r i n g theory ) . So we have; ( b ) The property o f being a p-space l s an elementary property o f the r i n g o f continuous functions on a t o p o l o g i c a l space. We also have c l e a r l y : ( c ) Extreme disconnection i s a strong elementary property. Now l e t X be a d i s c r e t e space with measurable c a r d i n a l . By 12 H- 7 on page 169 o f Gillman and J e n s o n , the real-compact-l f i c a t i o n , R(X) , of- X i s an extremally disconnected p-space, wi t h measurable c a r d i n a l , which i s not d i s c r e t e . We r e f e r the reader to Gillman and J e n s o n f o r a d e f i n i t i o n o f real-compact-l f i c a t i o n . Suppose there i s a t o p o l o g i c a l space, Y , with non-measurable c a r d i n a l , such that l ( X ) ^ x ^ Y and C( H(X)) i s e l e m e n t a r i l y s.e.e. equivalent to C(X) w i t h respect to the language of r i n g theory. Then by ( b ) and ( c ) Y i s an extremally disconnected p-space, and by ( a ) Y i s d i s c r e t e . But discreteness i s a strong elementary property and so S(X) i s d i s c r e t e . This i s impossible. - 5 8 -The proof i s complete. Extreme disconnection i s a weak elementary property as w e l l as a strong elementary property. A space i s extremally disconnected i f and only i f the maximal open set contained i n the complement o f each open subset has open complement. This can e a s i l y be described i n I»w . A T ^ -space, and i n f a c t any T^ -space, i s d i s c r e t e i f and only i f the complement of every closed subset i s clos e d . This can also be e a s i l y described i n . So the l a s t theorem holds equally w e l l f o r weak elementary equivalence. We have proved the f o l l o w i n g : Theorem 8 . I f there e x i s t s a measurable c a r d i n a l then e i t h e r : ( 1 ) There e x i s t T,i -spaces, X and Y , such that X ' — ' Y , but C(X) and C'(Y) are not elementarily equivalent with respect to the language of r i n g theory. or ( 2 ) There e x i s t s a space, X , with measurable c a r d i n a l , which i s not weakly elementarily equivalent to any space with non-measurable c a r d i n a l . - 5 9 -BIBLIOGRAPHY Dugundji J . , " Topology •» , A l l y n and Bacon , 1966 Gillman L. and J e n son M. , " Rings o f Continuous Functions " , Van Nostrand , I960 Grzegorczyk A, , w U n d e c i d a b i l i t y o f some Top o l o g i c a l Theories " , fundamenta Mathematicae , Volume 38 , 1951 K r e i s e l G. and K r i v i n e J.L. , " Elements o f Math-ematical Logic " , pp. 65-71 , North Holland , 1967 Sabm M. . , n D e c i d a b i l i t y o f Second Order Theories and Automata o f I n f i n i t e Trees " , Trans. Am. Math, Soc. Volume 141 , 1969 Schoenfield J . , " Mathematical L o g i c n , Addison f e s l e y ,1967 T a r s k i A. , Mostowski A. and Eobmson S. , " Undec i d a b l e Theories " , North Holland , 1953
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- First order topology
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
First order topology Inglis, John Malyon 1974
pdf
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
Page Metadata
Item Metadata
Title | First order topology |
Creator |
Inglis, John Malyon |
Publisher | University of British Columbia |
Date Issued | 1974 |
Description | A topological space may be viewed as an algebraic structure. For example, it may be viewed as a (complete atomic) Boolean algebra equipped with a closure operator. The lattice of closed subsets is another algebraic structure which may be associated with a topological space. Tne purpose of this thesis is primarily to investigate the metamathematical properties of algebraic structures associated with topological spaces. More specifically, we will first consider questions of decidability of the theories of these algebraic structures. It turns out that these theories are undecidable. We will also examine certain equivalence relations on the class of topological spaces that arise naturally from viewing them as first-order structures. Finally we will show that certain classical theorems of model theory do not hold for topological spaces. |
Subject |
Topological spaces |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-01-20 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0080109 |
URI | http://hdl.handle.net/2429/18788 |
Degree |
Master of Science - MSc |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-UBC_1974_A6_7 I54.pdf [ 3.33MB ]
- Metadata
- JSON: 831-1.0080109.json
- JSON-LD: 831-1.0080109-ld.json
- RDF/XML (Pretty): 831-1.0080109-rdf.xml
- RDF/JSON: 831-1.0080109-rdf.json
- Turtle: 831-1.0080109-turtle.txt
- N-Triples: 831-1.0080109-rdf-ntriples.txt
- Original Record: 831-1.0080109-source.json
- Full Text
- 831-1.0080109-fulltext.txt
- Citation
- 831-1.0080109.ris
Full Text
Cite
Citation Scheme:
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}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0080109/manifest