Universal lnfinite Partial Orders Citation Johnston, John Beverley (1955) Universal lnfinite Partial Orders. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/WSQ4-ZA23. https://resolver.caltech.edu/CaltechETD:etd-01162004-140541 Abstract NOTE: Text or symbols not renderable in plain ASCII are indicated by [...]. Abstract is included in .pdf document. We consider infinite partial orders in which the order or comparability relations are transitive, non-reflexive, and nonsymmetric. Our purpose is to construct for each infinite cardinal [...] a so-called [...] partial order in which every partial order of cardinality [...] can be isomorphically embedded. Using the Axiom of Choice we easily construct an [...] partial order of cardinality [...], while for those infinite cardinals [...] for which [...], the General Continuum Hypothesis enables us to construct an [...]; universal partial order of cardinality [...]. Item Type: Thesis (Dissertation (Ph.D.)) Subject Keywords: (Mathematics and Physics) Degree Grantor: California Institute of Technology Division: Physics, Mathematics and Astronomy Major Option: Mathematics Minor Option: Physics Thesis Availability: Public (worldwide access) Research Advisor(s): Dilworth, Robert P. Thesis Committee: Unknown, Unknown Defense Date: 1 January 1955 Record Number: CaltechETD:etd-01162004-140541 Persistent URL: https://resolver.caltech.edu/CaltechETD:etd-01162004-140541 DOI: 10.7907/WSQ4-ZA23 Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided. ID Code: 195 Collection: CaltechTHESIS Deposited By: Imported from ETD-db Deposited On: 16 Jan 2004 Last Modified: 29 Jun 2023 22:04 Thesis Files Preview PDF (Johnston_jb_1955.pdf) - Final Version See Usage Policy. 2MB Repository Staff Only: item control page

UNIVERSAL INFINITE PARTIAL ORDERS Thesis by John Beverley Johnston In Partial Fulfillment of the Requirements For the Degree of Doctor of Philosophy California Institute of Technology Pasadena, California 1955 ACKNOWLEDGEMENTS I wish to express my sincere gratitude to Dr. R.P. Dilworth for the training he has given me and for his encouragement and friend= ship during the past four years, I showld also like to thank the California Institute of Technology for the financial assistance which has made possible these studies, and particularly the Mathematics Department for recommending this assistance. - iii - ABSTRACT We consider infinite partial orders in which the order or comparability relations are transitive, non-reflexive, and non= symmetric. Our purpose is to construct for each infinite cardinal a somcalled "-universal" partial order in which every partial order of cardinality can be isomorphically embedded. Using the Axiom of Choice we easily construct an N-universal partial order of cardinality 2% » while for those infinite cardinals N for which ho = 2% » the General Continuum Hypothesis enables us to construct an xX -universal partial order of cardinality x. Seetion 1. 26 36 he TABLE OF CONTENTS Title ACKNOWLEDGEMENTS | ABSTRACT Classes ~ fundamental conceots Cardinals Partial orderings of classes Linear orders and linear extensions of partial orders Universal infinite partial orders REFERENCES Page ii iii ~i 12 25 37 a4 -1- UNIVERSAL INFINITE PARTIAL ORDERS 1. Classes~fundamental concepts. We abstract from experience the concept of the collection of a definite group of objects into a whole; this new entity, this collection into a whole, we then call a class. The objects are called the elements or members of the class; the class is said to contain or to be composed of its elements, while the elements are spoken of as belonging to or being contained in the class. To exhibit a class which contains the elements a, b, c (and possibly others) we write { a, by c, *** }3 we denote the class of objects a which satisfy some property P by { a: a4 satisfies P }. The assertion that an object a belongs toa class A is written a cA; the assertion that a does not belong to A is written a fA. Many paradoxes have been stated in connection with the concept of class; some of them arise from the use of the word "all" and from our intuitive feeling that, given an object a anda class A we should be able to assert exactly one of the statements: ac A, a £ A. Perhaps the simplest such paradox is furnished by the following self-contradictory "class": "the class C, which is composed of all those classes which are not members of themselves". If we assume that C €C we immediately conclude that C #¢ C, and conversely. As a result of the existence of such paradoxes, and in order to establish a firm foundation for the construction of a consistent theory, it has been found necessary to single out certain "well-behaved" classes which are then called sets, and to lay down various axioms -2- governing the behavior of both sets and classes. We shall not attempt to give here any complete exposition of an axiomatic theory of classes; instead we shall simply mention those concepts, rules, and results which are pertinent to our subject. 1.1. We have under consideration a universe of classes and a universe of sets, with the understanding that every set is a class. A class which is not a set is called a proper class. Certain classes, such as the empty-or void-class /\ , the finite classes, and the denumerable classes, are immediately defined to be sets. In addition, many methods are defined for the construction of new classes, together with rules stipulating when the newly formed classes are to be sets. 1.2. A class A is called a subclass (subset) of a class (set) B if every element of A is also an element of B, in symbols A & B. For every class A, A © A; if A & B, the class of those elements of B which are not also in A is denoted by B-A. If ACB and BC A then A and B are identical, which we denote by A= B. The collection of all subclasses of a class A is again a class, denoted by Tr(a); if A isa set, I(A) is alsoa set. As an example, the set { x,y, 2 } has the eight subsets: Tj, = A T = {yo 2} T = {x} To = {2.x} T= {y} T = {x,y} tT = {2} Ty = {x,y,z}. Finally, classes having no elements in common are said to be disjoint. -~3- 1.3. Given any two objects a and b we may form the set { a, { a, b }}, which consists essentially of the two objects but has the property that within it the object a is distinguished as, say, "first", and the object b as "second", The set { a, { a, b } } may thus be called the ordered pair containing a and b (in that order), and is usually denoted by <a, b>. 1.4. Given two classes A and B, the collection of all ordered pairs <a, b> with aecéeA and beB is again a class, called the cross product of A and B and denoted by A x B If A and B are both sets, then A x B is a set. A simple example shows the reason for using the notation A x Br let A= {0,1} (two elements) and B= { x, y, 2 } (three elements). Then A x B has the six (=2 x 3) elements: <0, x>, <1, XK >, <O,y>, <ls,y>sy, <0, 23>, <1,2>. 1.5. A class M, all of whose elements are ordered pairs, is called a (single-valued) mapping if M contains no two pairs <a&, b> and <a,c> with b distinct fron c. M is said to be bi- unigue if in addition it contains no two pairs <a, b> and < cy, b> with a distinct from c. The collection of first (second) elements of the pairs of M is a class called the domain (range) of M and denoted by D(M) [R(M)]; M is said to map D(M) onto R(M). For an element ac € D(M) there is a unique element f © R(M) for which <a, B> e M; -AjA- this element B is called the image of a by M and is denoted by M‘*a, so that we have <a,M‘a>eM. If the domain and range of a mapping M are sets, then M itself is a set and is called a function. The converse» uM, of a bi-unique mapping M is the class of pairs of M taken with the first and second elements interchanged; if M is a function then M° is a function. If M and N are mappings with D(N) = R(M), then the composition MN of the mappings Mand N is the class of ordered pairs <a; c > for which there exists an element b with <a,b>eM and <b, ec >eEN; MN is @ mapping and if both M and N are functions, then MN is a function, 1.6. For no proper class A and set X is there a bi- unique mapping of A onto X. This has the immediate consequence that a mapping is a function if and only if its domain is a set. 1.7. Given two classes A and B, a mapping M for which D(M) =A and R(M) © B is said to map A into B; to express this we write M:A > B. The collection of all such mappings is a class which we shall denote by By if both A and B are sets then BA is again a set. Again, a simple example will show the reason for using the notation B*: let A= { x,y, 2} (three elements) and B= (0, 1} (two elements). Then Be has the eight (= 2?) elements: <x,0>, <x,0>, M, = <y,0>, ’ M, = <ys 17s 9 <2, 0> <2,1> Z, O> y, \< 2, 1 > <x, 0 » fex,1>, M3 = <y,1>s>ps; My =< <y¥e1>, ’ <2, 0> (<2, 0 > <x,O0>, <x,1>, y= <y,; Ory ’ M, = <y,1>, ° <2, 1> <2, 1> Suppose now that we form the eight subsets T, = { ws weaA and M,*w = 1} of Ay i = 15 25 wee » Se Then Ty» eee y Ty are exactly the subsets of the example in 1.2., showing the essential similarity between the classes T(A) and {0, 1}4, 1.8 let M be a mapping with domain A such that for each aceA, M‘a is aclass. The collection of elements x such that there exists an aeéA for which x eM‘a is a class called the class union of the M‘a over the index class A and is denoted by (UW {M‘aza eA}. The collection of elements x which belong to all the M‘a is a class called the class intersection of the M‘a over the index class A and is denoted by (\{M‘a:a cA}. The union and intersection of two classes S and T are denoted more simply by SuT and ST. Finally, all of the above statements hold if the words " mapping" and "class" are simultaneously replaced by "function" and "set", -6- 1.9. Finally, all of the results to be presented in this paper require the following assumption. Axiom of Choice: Let F be a function with domain X (which by 1.6. is a set) such that for each aeX, F*‘a is a non-void set. Then there exists a function f:X > \) { F‘asa eX } which has the property that for each a € X, fae Faq. The collection of all such functions f is a set which we denote by I[{F‘a:ace X}. It is easily seen that this (product) set is a generalization of the cross product defined in 1.4. . The Axiom of Choice can be stated also in the following equivalent form: Given any set X there exists a function F: I(x) >xX such that for each non-void subset T of X, F‘T eT, and FA =F*X, - 7 =- 2. Cardinals. Perhaps the simplest property possessed by a set is the "number" of elements belonging to it. For a given finite set this nunber may be ascertained (uniquely) by some counting process; for infinite sets the concept of number requires a new definition. This definition may be gained by looking more closely at what is meant by the statement "the finite sets X and Y have the same number of elements". For example it is evident that the sets {a,b,c} and {a5 6B, 3 } both have three elements. However, in this case the peculiar nature of the elements themselves leads us to a further observation, namely that we may associate a with a, B with b, and Y with c. In effect, these associations, expressed in terms of ordered pairs, furnish us with a bi-unique function F= { <a,a>y, <b, B>,<c, ¥>} which maps {a,b,c} onto {a, B, o}. it is easily seen that there are exactly n! (0! = 1) such functions between any two sets of n elements each and no such functions between sets of differing numbers of elements. Thus the notion of "the same number of elements" for finite sets is equivalent to the existence of bi-unique functions; extending this idea gives us the concept of "number" for infinite sets. 2e1. Two sets S and T are said to be equivalent, written S~T, if there exists a bi-unique function F which maps S onto T. The identity function I= {<a,a>:aceS } shows that S~S for each set 5S; the relation of equivalence is reflexive. If 5S ~T by a function F, the function F° leads to the statement that T ~ 3; =~ Sm the relation of equivalence is symmetric. If $~T by a function F and T~U by a function G, then S ~U by the function FG; the relation of equivalence is trunsitive. Thus the relation of equivalence splits the universe of sets into disjoint collections within each of which any two sets are equivalent. We consider each collection to be an entity which we call a cardinal; an arbitrary cardinal is denoted by the symbol m. Each set S belongs to exactly one cardinal wm ; we say that S has cardinality m or is of cardinality m and write {s| = m. The finite cardinals are simply the non-negative integers nz; the infinite cardinals are usuallydenoted by the symbol XN 3; Noy denotes the cardinality of the set of (non-negative) integers. We next consider various operations between cardinals. For this purpose we shall need representative sets having given cardinalities, and it can be shown that we can construct for each cardinal m a standard representative set S(m) of cardinality m with the property that for distinct cardinals m and n , S(m) and S(n). are disjoint. 2.2. For two cardinals m and yn we say that " m is less than or equal to n", in symbola m < yn , if there exists a subset of S(n) which is equivalent to S(m). This definition is easily seen to agree with the usual one for non-negative integers m and n. We easily show that this relation is transitive by forming the com- position of appropriate functions. F. Bernstein has shown that if msSnand nS m_», then m = n. We say that " m is strictly less than n ", in symbols m< n ,if m< n and mF Ne By the Axiom of Choice (1.9.) it will result in 3.10. that for any two -~9- cardinals m and vy we must have exactly one of the three relations m< WT, M = Nygor n< Me 2.3. If F is a function with domain X such that for each aéX, F‘a is a cardinal, then we define the sum ¥{F ‘asa € x} of the cardinals F‘q over the index set X tobe Y{F‘asae X} = |U{s(F‘a):a eX} |. (The disjointness of the S(F‘a) is of prime importance here.) For finite sums of non-negative integers this definition is seen to agree with the one for ordinary addition. It is clear that for each Bex, Fp < L{Ffazace xX}. The sum of two cardinals m and n is simply denoted by m+n . 24 If F is a function with domain X such that for each a €X, F‘a is a cardinal, then we define the product Tl {F‘ asa € X} of the cardinals F‘gq over the index set X to be Tl {Ffasae xX} =| TL{S(Ffa)tsac xX} |. For finite products of non-negative integers this definition is seen to agree with the one for ordinary multiplication (see 1.4.). It is clear that for each pex,F*fB < TI{Ffatae xX}. The product of two cardinals m and n is simply denoted by mxn . 2.5. For two cardinals m and n we define m to the power yn , in symbols m” , to be m= is(m)8OM)} For any Q set S, 2i5| is clearly the cardinality of I(S); it is easily show by assuming the contrary that for every cardinal m, m < 2™ e From this we see that there is no “largest" cardinal. We shall make frequent use of the General Continuum Hypothesis: If XX is an ~10 = spss £4 : . . x infinite cardinal there exists no cardinal m for whieh KR <m<2°. ey, of Choice. This hypothesis has been shown by W. Sierpinksi [1] to imply the Axiom 2060 Some easil roved results concerning cardinals are co the following: (1) (2) M5 * "3 Mo ™M *) Fem, ; (m, if ™ 4 Sm, and m is arbitrary, then mys ms If X is an index set and m(a) is a unique cardinal associated with the slement a of X, thens K{mraexX} = |x} xm; II{msaex} = m! ; Trims ex} = m D{ma}ra e X} ; TIL m(o)1™ sac X} =[TI{m(a)za c xX } y™ ; 2 if nia) is another unique cardinal associated with ay and if m({a)< wy(a) for each a € X , then Z{m(aldtaexX} < FK{nlaltacxX} and LA Tl {m(a)ia ce xX} Ti{ntasae xX} . let F be a function with domain Y such that for each Be Y, F‘g is aset andthe F‘B are pair wise disjoint; -l1- define X= U{F‘p : pe}. If for eacho eX m(a) is a unique cardinal, then: Lim(ajiae xX}; (8) Z{Limla:acKPr‘p} : per} (9) TT {Ii{m(a):ae Fp } fer} TI{m(a):a € X} ; (10) I{ L{m(a):a ce FSB } Ber} = E{I{m(a)iae Re) } se ex’ ana e'p oF p of for fpeYy}. We next introduce some structure into our classes and develop some powerful tools of investigation and construction. -12- 3. Partial orderings of classes. Many classes arising in our experience and in mathematics exhibit relations between their elements, for example: "a is south of b®, "a is below b", "a is the father of b", "a is a subset of b*, Some of these relations are transitive: if a is south of b and b is south of c, then a is south of c. On the other hand, "a is the father of b" is not transitive. We also note that two objects need not be comparable by a given (transitive) relation: an iceberg is neither above nor below the surface of the body of water in which it floats. We abstract from these and other examples the notion of a (transitive) partial ordering of a class. 3.1. For aclass A, a subclass B of A x A is called a partial ordering of A (or A is partially ordered by B) af it satisfies the conditions: (i*) for no aeéA is <a,a>eB (B is non-reflexive); (2*) for no a, beA with a#b are both <a, b> and <b, a> eB (B is non-symmetric); (3*) if <a, b> and <b, c¢> eB, then <a,c>eB (B is transitive). Note that B may be void. We usually write "a < b" (to be read "a is less than b") in place of <a, b > € Bs; with this convention we say that the class A is partially ordered by the relation "<" if: (1) for no aéA do we have a<a; (2) For no ay beA with a #b do we have both a <b and b < a; (3) af a<b and b<c then asa -13- In place of a <b we sometimes write b >a ("b is greater than a"). Clearly, any subclass of a partially ordered class A is again partially ordered by the same relation; it is called a suborder of A. A set which is partially ordered is called (together with its relation "<"") simply a partial order. Elements a and b of A for which either a<b or b<a holds are said to be comparable, while if neither a<b nor b<a holds then they are said to be non-comparable; if a< b then the pair <a, b> (€ B) is spoken of as an order relation or comparability, while if neither a<b nor b<a_ holds then both <a,b> and <b, a> (¢B of course) are called non-comparabilities. An element m of A for which there is no acéA with a>m is called a maximal element of A, and analogously for a minimal element. If D&A and b€éA_ such that for each ae D we have either b>a or b=ay, then b is called an upper bound (in A) for D, and analogously for a lower bound. An example of a partial order is furnished by the eight subsets Tye eee 9 Tg of P({ay, by c } ) given in 1.2. when the ordering is by subset inclusion. This partial order can be exhibited graphically as follows: { bee } Bs 9 a c By ay al a at &, b - 14- 3-2. A partially ordered class A is said to be linearly ordered by "<" (the class B of 3.1. is called a linear ordering of A) if in addition we have: (4) for every two distinct elements a, bd of A, either a <b or b<a_ holds. Every subclass of a linearly ordered class is itself linearly ordered. A linearly ordered set is called simply a linear order. If a subset T of a partial order S$ is itself a linear order, then it is called a chain of 5S. If a<b ina linearly ordered class then we say that “a precedes b" or that "b follows a". If F is a function with domain D such that for each deD, F‘d is a non-void linear order, then [I{F‘d:d € D} can be made into a partial order which we shall denote by P( [[{F‘da:d ¢ D} ) by introducing the order relations: for f,, f, ¢ II{F‘d:deD } , we define f,<f, if and only if fpa<fyd in Fd for every deD. If every F‘d is a certain linear order L, then we denote the partial order P( [T{F‘d:d eD}) more simply by p(1) . 3.3. <A partially ordered class A is said to be well- ordered by "<" (the class B of 3.1. is called a well-ordering of A) if in addition we have: (5) every non-void (partially ordered) subclass U of A has a minimal element. Every subclass of a well-ordered class is itself well-ordered. A well~ ordered class A is immediately seen to be linearly ordered by con- sidering all subclasses having two elements; the minimal element of 2 each non-void subclass U is thus unigue and is called the "first element"of U. If p is an element of A, we define p to be the subelass 6 = { time A and w<p in A} (fp does not contain pe A segment of A is any subclass U of A which satisfies the condition: if GO eU and tT EA such that tt < @O in Ay then tT €U; if U is a segment not equal to A, then U is called a proper segment of aj every proper segment U of «A is easily seen to sequal e) where Pp is the first element of A-=-U. A can have atmost one maximal element; if it exists, this maximal element is called the last element of aA. Every element which is not a last element of A has & successor Px namely the first element of the subclass {a:1>p in A} . Tf p is an element for which f has a last element ps then Pp is the successor to p. and o. is called the predecessor of p - If an element p has no predecessor and is not the first element of aA, then it is called a limit clement of A; we write p =lin{o:o ev} if V is any subclass of B having the property that for each 7c Pp there exists a @ in V_ such thet a<O (9 itself is such a subclass), More generally, if V is any subclass of A, lin {o: o eV} is defined to be the first elenent of A not less than any element of V, if such an element exists. We are now already in a position to prove the following strong form of transfinite induction. 3e4¢ Theorems Let A be a class and W a well-ordered class. Let there be mappings T:W >T(W) and R:I(A) x WA, Then there exists a unique mapping F:W >A such that for each -~16- pew, F°p =R°<F(p,T), p >» where F(o, T) = {Flu : pe pntfo}-. Proof: 1) Let C be the class of mappings F(U):U » A whose domains are segments U of W and which have the property that for each p €U, FU) ‘p =R‘<FU)[p, 7, p>, where FU)[p, T) = {FU)‘u sue Pntsp} . Note that if U and V are segments of W, then either U © V or V € Ue 2) let F(U) and F(V) € GC with U GS V. Suppose there exists a p €U_ such that F(U) “p # F(V) “p - let o be the first such p. Then FU)‘, = F(V)‘ for all poe ©, sothat FU) [o, T) = F(V) lo, Tl. But then Vv i FU)S'o =RS< FU) Lo, Tl o v i R*‘<F(WV) lo, TI, 0 FIV)So , a contradiction. Thus any two mappings in C. agree on the smaller of their two domains. 3) Define F= U{F(U):F(U) eC } . By 2), F is a mapping F:D(F) > A. Since D(F) is a union of segments of W, D(F) is itself a segment of W. For p € D(F), there exists an F(U) € C such that p ev and Fo. = FU), for all peu. Ts Fp, 7) = FU) p > T] ana Flo = FWU)‘p =R ‘ <F) Ep, Tl, p >= R § <F(p,T), p >. Hence’ F has the desired property on the domain D(F) and by 2), F is unique. 4) Suppose that D(F) # We Let po be the first element of W- D(F), go that D(F) = p +» We may then define a mapping G:D(F) uv {p} >A as follows: for pi € D(F), G “MM =F “Md » while G ‘p = R‘< F(p » T)s p >. But then we clearly would have Ge Cy so that D(G) G D(F) and ) € D(F), a contradiction. Thus D(F) = W, which completes the proof of Theorem 3.46 . — Now, using the second form of the Axiom of Choice (1.9.), we obtain the following useful corollary to Theorem 3.4. . 3.5. Theorem: Let A be a set and W a well-ordered class. Let there be mappings T:W>I(W) and R:f(A) x WPA). For each p e€W consider the following implication: if there is a mapping F(p): Pp >A such that foreach ep ,F(p)"w e é R“<F(p)(Cy,Tl, HW >» then R <F(p)[p,Tl, p> is |@ non-void subset of A, where for WE PY {p} 9 F(p) Ly, 7) { F(p) ‘vs ve Fat y }. If this implication holds for every _p eW, then there exists a (not necessarily unique) mapping F: W > A such that for each peW, F°p eR“ <F(p,T), p > » where F(p, 7) = { F‘u 2 ME PAT. p } . Proof: 1) By the Axiom of Choice let there be a function Z:Tr(A) >A such that for non-void subsets B of A, Z‘BeB, while 2‘A =2Z°A. (The theorem is vacuously satisfied if A is void.) We define a mapping - 18 - G:T(A) x W>A as follows: for BCA and pew, G‘<B,p> =Z°R‘<B, p>. Then by Theorem 3.4. there exists a mapping F:W > A such that for each p € Ws F’p =G “<F(ps 7), p >> where F(p, T)= {Fou tr ME PNT}. 2) Suppose there exists a p ewW such that F‘O gRo< F(p, T),p>3 let o be the first such 9 . Then for all pre O,F “UU € ‘ R°<F( pt, T), > so that the mapping F MN G@ x A is a mapping F(a): G@ >A such that for each pp eG, F(a) ‘yu & 4 R°<Flo) [u, Tl, 4 >. By the hypothesis of the theorem then R‘< F(a) [o,T],O0> is a non-void subset of A. But then Bo G*‘<F(o,T),7>=64%<Ko)[o, Tl, o > Z°R‘<Fo)lo,T],7>€R6<Fo)[o, M,0> R‘<Fl(o,T), o>, contrary to our assumption. Thus F satisfies the conclusion of Theorem 3.54 .« We note that Theorems 3.4. and 3.5. have several natural corollaries according as D(R) =T(A) instead of T(A) x W, or Tp = p for all p €W, or both. In the remainder of this paper, when we refer to these theorems it is to be understood that we are using which ever corollary is applicable. 3.6. A bi-anique mapping M whose domain A and range B are partially ordered classes is said to be an isomorphism between the partially ordered classes A and B (in symbols A x B) if we have the conditions x <y in A if and only if M‘x<M‘y in B. Two partially ordered classes A and B are said to be isomorphic (to one another) if there exists an isomorphism between them; isomorphic linearly ordered classes are said to be similar (to one another). The relation of isomorphism is reflexive (A TA under the identity mapping I‘a=a)s3 symmetric (if A M B then B xe A), and transitive (if A 7B and B n C then A \-C). Thus the universe of partially ordered classes is split into disjoint collections of isomorphic partially ordered classes. As we did in 2.1. for collections of equivalent sets, we may think of each such collection as an entity which we call an order type and assume that for each order type we have a particular abstract representative. 3.7. The order types possessed by well-ordered sets are called ordinals; we shall denote ordinals by small Greek letters; a well- ordered set R which belongs to an ordinal p is said to have ordinality pie The collection of ordinals is taken to be a class which we denote by Ord. We introduce order relations into Ord as follows: let Ps o be ordinals and R,S_ be the abstract representatives of ordinalities P ,» & respectively. We say that " P is less than o", in symbols Pp < Tor o7 P 5 if R is similar to some proper Segment of S. To show that these order relations constitute a partial ordering of Ord, it is sufficient to show that for any two well-ordered sets V and W there can exist at most one function f:V >W whose range is a segment of W and which is an isomorphism between V and R(f). Suppose by way of contradiction that f and g are two distinct - 20 - such isomorphisms and let mm be the first element of V such that f‘uf#g‘us; we may assume that fa >g%m in W. Since R(f) is a segment of W and fa >g‘n in W, we may define v = £° < ga‘; then u = £° “‘e‘n> #94 g¢a = Vv in V, since f is an isomorphism But now w> V in V implies that g‘u>g‘v in Ws so that fv =gin>g‘v in Wy, contrary to the minimality of 1; thus f=g and we have a partial ordering of Ord. 3.721. Next we show that Ord is actually linearly ordered. Let S, T be the representative well-ordered sets for arbitrary ordinals Oo » t respectively. Define Z:IF'(S) >S to be the function such that for US S,U#S, Z‘U = first element of S-U, and 2°S=2‘A. Then by Theorem 3.4. there exists a unique function F:T > 5 such that for each p ET, Fp =2 ‘ {Fut pe Pp}. We easily verify the following three statements: If F is bi-unique and R(F) # S, then F is an isomorphism between T and the proper segment R(F) of S, so that tT < o. If F is bi-unique and R(F) = S, then F is an isomorphism between T and 5S, so that tT = o. If F is not bimunique, let p be the first element of T for which F‘p = F4u for some MM <P ; then FMP x S is bi-unique and R(FNG*S) =S; FN p xS is then an isomorphism between S and the proper segment Pp of T, so that o < UT. Thus Ord is linearly ordered. 347.2. We see from 3.7.1. that for the representative well- ordered set R of ordinality p there is a bi-unique correspondence between the set of proper segments of R and the collection of ordinals M< Ps namely p « Since there is also a bi-unique correspondence -21- between the set of proper segments of R and the set of elements of R (3.3.), we see that p is actually similar to R. Thus, p is a set (1.6.) and is well-ordered with ordinality p. We take f as the standard well-ordered set of ordinality Pe At the same time we also see from the above that Ord is well-ordered. 3.7.3. Suppose that Ord were a set. Being well-ordered it would have some ordinality 2, from which it would follow by 3.7.2. that Ord = Q - But this leads to the contradiction @ e Q » Since Q is assumed to be in Ord. Thus, Ord is a well-ordered proper class. 3.74 We introduce addition and multiplication into Ord as follows. Let p, O € Ord. P+ oO is defined as the ordinality of the (clearly well-ordered) set p U G@ , where the order relations of p and & are retained and it is understood that every element of p precedes every element of O& . To define pxo i for < a, B > and< m,v>& OP xO , we define <a, A ><<ji1,V> if and only it if B< v ,or, B=V and a <3 these order relations are easily = seen to constitute a well-ordering of p x & , and we define pxeo to be the ordinality of this set p xo, 328. The Axiom of Choice is equivalent to the Well Ordering Theorem: For every set S there exists a well—ordering of S. Clearly, we may pick out the first element of each non-void subset of a well- ordered set, so that the Well Ordering Theorem implies the (second form of the ) Axiom of Choice (i.9.). To prove the converse: Let A bea set and Z:T(A) ~A a function such that for each subset T of A, T - 22 = Z# A, Z°T eA-T, and z°A=2Z‘°A . By Theorem 3.4. there exists a unique mapping F:0rd > A such that for each p € Ord, Fip=Z°{ Fy spe P}. F carnot be bi-unique, by 1.6.. Let T be the first non-zero ordinal for which F‘a = F ‘0; then it is easily shown that F © 7x A is a bi-unique function which maps 7 onto A and thus furnishes A with a well-ordering of ordinality @. 329. The Axiom of Choice is equivalent tc the Maximal Principle: Every partial order P has a maximal chain C (meaning that no element of P-C is comparable with every element of 6); thus if every chain of FP has an upper bound in P then P has a@ maximal element. First, let A be a set and B the set of well= ordered subsets of A (a given subset of A may appear in B with many well-orderings). B is partially ordered by the relations: for C,; DeB, C<D in B, if and only if C is a proper segment of D. Application of the Maximal Principle to B yields a well-ordering of A. To prove the converse: Let P be a partial order with an imposed well-ordering P= {p(m): Me P for some p € Ord } (this well-ordering has no necessary connection with the partial ordering of P). Then,taking both A and W in Theorem 3.4. to be the well-ordered set Py, the range of the function F is a maximal chain of FP provided that we define the function R:I(P) x P>P as follows: for B © P and for peP, p if BU{p} is a chain of P, R‘<B,p> = and p(O) otherwise -23- 3.10. By the Well Ordering Theorem there is for every cardinal m the non-void set of ordinals which are the ordinalities of well-ordered sets of cardinality m 3; if p is such an ordinal we have lpl =m and write simply |p| =m. The first ordinal so asso~ ciated with m is called the initial ordinal of m . The asso- ciation of each infinite cardinal NX with its initial ordinal w easily yields the result that the collection of infinite cardinals is a proper class well-ordered by magnitude and actually similar to Ord. Using the isomorphism which provides this similarity, we may index the infinite cardinals as XX, (a € Ord) and denote by w, the initial ordinal of Roe It is evident that each We must be a limit ordinal (3.3.). If V is any set of cardinals m , then lim {m: m eV} is defined to be the smallest cardinal > m for all m € V3; if Xx is a limit ordinal or zero, %, =lim {m: m< X,} and R, a» is called a limit cardinal. For any set S of cardinality x a (a € Ord) we may assume that there is a well-ordering of Ss. under which we may write S= {s(pi): we a, }. Finally, the General Continuun Hypothesis now states that for a, 6 € Ord with a>86 , Ra 2 2%, equality holding if and only if a= f+ 1. 3.11. We have the following facts concerning cardinals and ordinals. If V is a set of cardinals, some of which are infinite, then S{memev} =lim{m: meV}. Let o € Ord; we consider functions f having some domain B such that for each xeB, fx is a cardinal < Ry and such that Ry = {ft “x:x eB } « Among these functions f there will be one of minimal cardinality; we denote this -~24- minimal cardinal by m(a) and notice that Ros om (a) < Kae If m(a) < ®, we call &, singular; if m(a) = X, we call x a regular; every non-limit cardinal is regular; a regular limit cardinal is called inaccessible. For ace Ord and m < Room xR = 3X . By the General Continuum Hypothesis, we have: a ( 1 o=™Mm, x o<m< m(a), a xs a < x m(a)<ms< 8, and a o+] m If ~ is a limit ordinal and B is a set of ordinals B <> such that A =lim {p:peB} » then WwW = lin {W, : B&B} =lim { We 44% 6 €B}. Among such sets B there will be one of minimal cardinality; this minimal cardinal is in fact the m(2A) of the preceding paragraph. If ji, V € Ord and pi > 0, then there exist unique ordinals @(M,V) and $(M,V) such that @O(M,v)<v, O(M,VvV) <M >» and v has the representation ve Mx @(py,v)+ & (u,v). -~ 25 = 4. Linear orders and linear extensions of partial orders. The investigations reported in this thesis are the results of an attempt to generalize the well known fact that every denumerable linear order is similar to some set of rational numbers. In particular, we generalize the following proof of that fact: Let L be a demumerable Linear order with its elements numbered Age Bye eee » ay cess We map a, onto the dyadic rational r,=1 = 1/2°. Suppose we have mapped Ayr cee 9 OL onto dyadic rationals Pyy cee oe TL in such a way that the linear order { Por cee o TL J is similar to the linear order { Qos see 9 a } - We then map a onto the smallest dyadic rational n+ r of the form k/2""!, x odd and 0 < raey < 29 which yields nt+1 {to coe Tos Tray } similar to { Bos see 9 Be BL, } + Continuing n by induction gives us the desired set of (dyadic) rationals. The above proof has essentially two parts, namely, the existence of appropriate minimal dyadic rationals and an induction to ebtain an isomorphism. In the following discussion we construct for each infinite cardinal Ro a set of "dyadic rationals", show the existence of the necessary minimal rationals, and present an inductive process in a form which is of use for further work. 4e1. Definition: Let ae Ord. If the functions f: G, 72 are ordered according to first differences, the set 37a becomes a linear order which we shall denote by L(2 ”%), We shall call a function fra, > 2 a rational if there exists an ordinal »(f) Qy necessarily unique, such that f‘ (f)=1 while fu =O for n(f) < M < W, + Throughout further discussions, » will be used - 26- exclusively to denote this "terminating ordinal" of the rationals. We ~Wa shall denote by Le the suborder of L(2 *) consisting of the rationals. Regarding these linear orders Lo we prove the following theorem concerning the existence of minimal elements, 42. Theorem: Let a€é Ord. Then Ly is a linear order of _ x cardinality » cain, n € a, } »sothat XN < |L I <2". let p be any ordinal ¢ ae and let A be any subset of L, such that for each fed, n(f) < p- Then there exists a (unique) minimal element h(A,p) in L, such that n{nlas p)] =p and h(4,p)>f in L, for every feA. Define B= { g:g € Ly ng) < p , and g>f in L, for every feA}. Then for every g eB, g > h(Ay Pp) in Lo Assuming the General Continuum Hypothesis, Lo has cardinality Rye Proof: 1) L,= U{Mn)i ne oF } where T(7) = {fifeL, and n(f) =n} » and the T(7) are disjoint. But In()| = ain! <2 “e sothat xs L{IMy)len © O,} = ILI s a= Pad x x Z{2 “syne OL} = Nyx 2 %=2 °°. Assuming the General Continuum Hypothesis, |T(7)| < x,» so that XX < |L,| = — —— _ 20 wy Z{ (Ty) I: ne a +< KAR Ye oO, } = RUF Ry 2) If A is void, the theorem is clearly satisfied by the rational h(A, p) defined as follows: h(A, p)*p = 1 while h(a, p)*m =0 for we Ws M # p » In the remainder of the proof, A is assumed to be non<-void,. - 27 = 3) We define a function R:I[P(A)] xO >1(A) as follows: for Ke p and for the void collection of subsets of A, that is for AecTir(4)], R6<A,M>={f:feA and £‘O= max { k‘O:k eA} }; for ph e€ 6 and for Ye rir(4)] such that Y # A y we put ¥(*) = (V{e:ee ¥} ana R°<Y, >= {ff cA and f Sys = max{k ‘yi ck © ¥(*) F} ; if Y(*) is void, then sois R‘<Y,u>. Then by Theorem 3.4. there exists a unique function F: p > 1P(A) such that for each WEP Pou =R‘*< FCG)» > , where F( fa) ={Fly:ve pf }. This function F is seen to have the following properties: a) For Ms u<p » Fou > F‘y~, and the set { o 3M —p and FS yu is non-void } is a segment of pe b) For ve p with fy» £, & Fy, we have fy. f, € Pou and “a= f,‘é forall U Sve c) Ifve p »f, € Fey, and f, A such that fo’ = f)‘n for all 4 <v, then f, € Fy for all USV . d) For any ve p , F*v is non-void if and only if v=0, or, v> © and there exists some f€A such that fe Foy for all WU<vV. e) For oe pP such that there is an f, © F‘o, and for every V S$ o » there exists no f, €A such that fyp= £,‘p au? f,°u . 4) We define the rational h(A, p) of L, a8 follows: for all i <V while f \ a} For wep such that F°y1 is void, h(A,p)‘ ys = 0, = 28 - b) For pep such that F‘,: is non-void, h(A, p) «ps = fu for any f € Fu, by 3b). c) h(a, p)‘p = 1 and n(A, p) ‘x4 =O for p<u< Wee By 3a), we have thus defined h(A,pP) over the whole domain Oi Clearly h(A,p) e L, and m {has p)) =p. 5) Suppose there isa ve p and an f €A_ such that f*U = n(As pu for all wo < v . Then we can show that fe Fu forall w<v . For suppose the contrary and let vt be the first ordinal < v such that f ¢ F‘t. Then either rt =O or fe F‘jx for all HM < Ty, 80 that by 3d), there exists some ke F‘t. By 3b), k*y = £44 = h(Ayp)*p for all p< % , while by the hypothesis on f and by 4), f‘t=h(A,p)°v =k‘? . From this, 3c) yields f e€ F‘r a contradiction. Thus indeed f ¢€ Fou for all p<v. 6) Suppose that f is an element of A such that f € Fou for all he ) « We shall show that h(A, p) > f in Ly By 4)> h(Ay Pp)“ = f{u for all <p ,while h(Asp)*p =1>0=f'p, since »(f) <P. Thus h(A,p)>f in L. 7) Suppose that fe A such that for some Me p »,f¢ Fou e We shall show that in this case also, h(A, p) > f in Lie let oO be the first ordinal «¢ Pp such that f ¢ F‘o. Then either o = 0 or fe F*u for all M< © 5 so that by 3d), there exists some ke Fo, By 3b) and4), ke F4u forall we oo, k‘p = féu =h(A,p)" for all p< o ,and k*o=h(s,p)'o. If f‘o =k‘o then by 3c) f & Ffo, a contradiction. By 3e), fof k‘o. Tus f°o <k‘o =h(A,p)‘o and we have h(A,p)>f in Loe - 29 - 8) let t be contained in L, such that n(t) = p and t<h(A, p) in Loe We shall show that there exists an element f of A such that f >t in Lye Since 7 (t) = nla(as p)] =p; t and h(A, p) must differ at some first ordinal a < p . ‘This requires that t°o =0<1=h(A,p)‘o, so that by 4), Fiao is non-void.e Let feFo. By 3b), fe F*ut for all p< o& and by 4)o h(A,p)° x1 = £4. for all po < o , while tu = h(a, p) Sn =f‘u forall u< oO and to <h(a,p)‘o = flo. Tms £>t in L,. Steps 6), 7), and 8) assure that h(A,p) is the minimal element k of Ly having the properties that 1» (x) = p and k>f in L, for all f € A. We need only show that for each g eB, g>h(A, p) in L,. 9) Suppose that there exists some k € A such that k« Fou for all M ep 3 let ge B. We shall show that in this case g > h(A, P) in Li. By 4), n(A,p)*m =k‘p for all pep. Since g>k in L, and since n(g)s n{k) < p,g and k must differ at some first ordinal o <p , and g‘o >k‘o. But then gi = kp = h(A, p) ‘x4 for all p< Oo ,while g‘o>k*o=h(A,p)‘o so that g > h(A, p) in Loe In the remainder of the proof we assume that there exists no k eA such that ke Fu forall wep . 10) In accordance with the assumption we have made in 9), let w be the first ordinal <P such that there exists no f eA for which feF‘u for all <1, 7 > 0. We shall show that « must be a limit ordinal. For suppose that m had a predecessor m*, By the minimal property wu, there exists a ke A _ such that k « Fox for all M < W*, or 7* = 0, so that by 3d), there exists some f € F* w*, - 30 - Then by 3b), f € F ‘ps for all f4< 1, contrary to the assumed property of tu. Thus ww must be a limit ordinal; the meaning attached to @ in this step will be retained throughout the following steps. 11) There exists no ordinal Tt <a such that h(A,p)‘r=1 while h(ay p )<u =O for tT < (<1. For suppose the contrary. Since 7 is a limit ordinal, t +1< 1 so that by the minimal property of i, there exists some k eA such that ke F‘u forall w<t+l. By 4), then, h(A4, P) =k for all pp st. If ke =0 for all p such that T < “4 <m, then k‘pi =h(A,p)‘yr for all wet so that by 5), k € Fou for all Me T, a contradiction. Thus suppose 5 to be the first ordinal such that t < 8< a and k*§ =1. Then k“u=h(A,p)°p for all p< 8 while k‘§=1>0=h(4, p)‘5 so that k>h(A,p) in L,» contrary to 6) and 7). 12) Suppose that a = p 3 let g eB. be shall show that g > h(A, p) in Li. Since » (g) <p nlaa, pil, g and h(A, p) must differ at some first ordinal § < pe If § = p » then n(A,p ) n (ge) = e‘n(g) =1 while h(A, p )* ps = g‘u=0 for nig)<M<peat, contrary to 11). Thus 5< p =. Since a is a limit ordinal, §6 +1< 7 so that by the minimal property of mu there exists some k eA such that k € Fy for all p< § +1. By 4), then, k‘p =hlAyp)*u = ec for all p< § while k°§ =h(A,p)‘ Z#e’S. IF g68 <h(A, p)* 6 then g<k in Los contrary to the definition of B. Thus g“§ > h(4,p)‘§ and we have g > h(a, p) in Loe 13) Suppose finally that a < p 3 let ge B. We shall show that in this last case also, g>h(A,p) in L° By 10) and 34), Fa is void, -31- so that by 3a) and 4), h(A, p yu =O for 1S pi<p. As in 12), g and h(A4,p) must differ at some first ordinal § < p.- If =p, then we must have 7(g) < ww. But then h(A, p)* n (g) =l=g ‘n(g) while h(A, p)‘ pu =g‘=0 for n(g) < pM < my contrary to 11). If ms 6 < Pp, then necessarily g‘§ =1>0=h(A, p)° § while BoM=h(A,p)‘ x4 for all ps < 8 , so that g>h(A,p) in L. Finally, if & <1, 6+1< 7 since m is a limit ordinal, so that by the minimal property of wt, there exists some k ¢ A such thet ke F“y for all p< § +1, Then by 4), g4=h(A, p)o py = ku for all M< § while k°S =n(A,p)‘S #e°8.~ If g68 < h(a, p)*S then g<k in L,, contrary to the definition of B, Thus g‘6 > h(A, p)'s and we have g>h(A,p) in L,+ This completes the proof of Theorem Ae2e « 43. If P is a partial order and Q a linear order on the same set of elements, then @ is called a linear extension of P if every order relation of P is also an order relation of Q. If P is a partial order and L a linear order we say that a bi-unique function F:P ~ L generates a linear extension of PF if a<b in P implies that F‘a< Fb in L; the linear extension generated is the set of elements of F together with the order relations trans= mitted from L to P by means of the converse function Fo, If P is already a linear order, F constitutes an isomorphism between P and R(F) SL; we say that F embeds P in Ly, or that F is an embedding of P in L. -32- We now use Theorem 4.2. to prove a theorem concerning linear extensions of partial orders; the theorem is stated and proved in the following form for use in 5.10. . 4e4e Theorem: Let ace Ord. Let F be any partial order of cardinality ¥, with an imposed well-ordering P = { p( MItpED, }. For v< © denote by P,, the set {p(uidi pe UV}. Consider any two ordinals 9 and o& such that OS P<oE 3 define W=P,- P and for <vyso,W,=P,-P . We define a function a” *p pave v= ty 7 “p H:P >P(P) as follows: for peP, H#Sp={x x<p in P}. If there is a function 4G: Po > Lo which generates a linear extension of Po in such a manner that for each PCy) & Po 9 nla‘ p(y] = b P) then there exists a unique function extending G to the domain P, » F(G, o):W > L» which has the following two properties: a) For each p(y) ew, m[F(Gs o)* p(y] = yi. Now if for each p(y) EW we let A(G,v) = { G*p(ui)ip(p) € Pon Hp(v) } U { F(G, 0) * p(s) ep(ya) EW, AHS p(v) } , then fe AG, v) implies that m(f) < v so that the rational h[A(G,v),v] of Theorem 4.2. exists. The second property of F(G,o) is that b) For each p(v) Ee Wy F(G,o)‘ p(y) =h[A(Gyv),v]. These properties of F(G,0) assure that the combined function GUF(G;o) is a bi~unique function from Py, into L, which generates a linear extension of Pg in such a manner that for each p( MM) & Pos nlau Fao) © pul =p. Proof: 1) Define a function T:W >I(W) as follows: for p € W, T’ p = WNH‘p. For peW and BCL, define B <p> =Bu {G*aqrq e Pp A HS p }. =~ 33 = 2) We define a function RiT(L ) x W> Ly as follows: a) For p(v) eW and BC L, Such that there exists an f & B with n(f)>v, R*<B, p(v) > =the unique rational k € Le which has 7(k) = 0. b) For p(v) e€W and BE L, such that f€B implies that nif) < Vv, we have also that feB<p(v) > implies that n(f£) < V so that the rational h[B< p(v) >, v]_ exists; we put R‘<B, p(v) >=h[B< p(v) >, v]. By Theorem 3.4. there exists a unique function F(G,0):W~>L such a that for each p(v) € Hy F(Gyo) “p(v) =R°< F(G,o)[p(v), Ts piv) >» where F(G, o)[p(v), TL = { F(G,0) “p(y )ep(u) e Wy A TS p(y)}. 3) Suppose that there exists 4 p(y) eW with s > 0 such that n [F(G, o) * p(ui)] = 0. Let p(v) be the first such p(y de Then fe F(G,o)[p(v), T] implies that f = F(G,0)‘ p(ji) for some P(j4) & Wy, So that by the minimal property of p(y), nf) = M< vy, by 2). But then F(G,o)[p(~),T] is a subset B GS L, for which f€B implies that n(f) <v, so that F(G,0)‘p(v) = R°<B, p(v) > =h[B<p(v) >, v] and thus we have »[F(G,o)*p(v)] = Vv > 0, contrary to our supposition. Thus for each p(y) EW, nlF(Gso Yp(pi)] = pa y by 2). 4) By 3), for each p(y) eW, fe F(G,o)[p(v), T] implies that n(f) < v. Then by the definition of F(G,o), we have that F(G,0) “p(v) =h{ FG, o)[p(v), TI < ply )>> v}e -~ 34 - But . F(G,o)[p(v)sT] < pv) > = { F(Gyo) © p(y )ep(pe) & Wyn tS ply) } U {GS p(y)ip(ui) € Po MHS p(y) } = AlGV), since Wy, A TSp(v) =W, a HS p(v). Thus, F(G,o)‘ p(v) = n[A(G, v), Vv]. 5) let P(u ) and p(y) be comparable elements of Py with pcv If v < p then by the assumption on G, G‘ p(y) <G‘p(v) in L, if and only if p(y) <p(v) in P, If p $V <o then GU RG, oO)“ p(y) € FG, o)[plv),T] < p(y) > if and only if p(pi) <p(v) in P; that is, Gu F(G,o)‘ p(y) < F(G,0)‘p(v) in L, if and only if p(y) <p(v) in P. This completes the proof of Theorem 44. . 45. Definition: Let ace Ord. We call a linear order L X c~universal if every linear order of cardinality Re can be embedded in IL. The following theorem, obtained in a somewhat different manner by N. Cuesta Dutari [2; 243, Theorem 15], can be obtained as a direct corollary to Theorem 4.4. « 4.6. Theorem: let ace Ord. let L be any linear order of cardinality X, with an imposed well~ordering L= { p(y): pe oO} Then there exists an embedding F:L > Lo of L in Le having the il property that for each p(y) el, nIF* Pu )] M 3 that is, be is an X universal linear order. Assuming the General Continuum Hypothesis, Lo has cardinality Roe ~ 35 = Proof: In Theorem hehe let P be the linear order L of the present theorem. let O= p and o = W, so that G is the null function and we have F(A, W/L > Li. The function F = F(A, o,) clearly satisfies the conclusion of Theorem 4.6. . Theorem 4.6. has also been obtained by W. Sierpinski [3; 62, Theorem 3] for non-limit cardinals Xj The method of proof wouid work as well on all regular cardinals but not on singular cardinals. The proof is based on the following statement, which is due to F. Hausdorff [4; 181-182]. let ae Ord. A sufficient condition that a linear order L be X universal is that L have the two properties: a) If E € L such that [E| < Roe then there exist elements a(—), b(E) in L such that for every ce E, a(E) <e < b(E) in Le b) If E,»E, S L such that lz,\, {E.,| < 3, and such that for each a € KH and each a_cE we have a, <a, in Ly 1 t+ ~~ 2° 2 1 25 then there exists an element b(Ey» Ey) in L such that for each a, € EB, and each a, €E, we have a, < b(z,» Ey) <a,in L. 2 That this condition is not a necessary one is easily seen by considering appropriate subsets of Lo for singular cardinals Xo As another corollary to Theorem 4.4. the theoremon linear extensions of a partial order, due to E. Szpilrajn [5], may be given in the following form. 4e7. Theorem: Let ae Ord. Consider any partial order P of cardinality %, with an imposed well-ordering, P= { P(ps)epe ds }, let a und b be distinct non-comparable elements of P. Then there - 36 ~ exists a function F:P > Lo which generates a linear extension of P in which a<b and which also has the property that for each P(ujdeP, Fop(ul ey. 1) Let us construct a new well-ordering of FP, P= {q(p)sp & O, } ’ in such a way that q(0) =b and q(1) =a. Then let O=p , o = Ws and let F(A, wo )eP > L, be the function of Theorem 4.4. for this newwell-ordering of P. Since b= q(0) €q(1) =a in P, we have that F(A, w,) . q(1) < F(A, wo) ‘ q(G) in Le by Theorem 44. So that F(A, wo) generates a linear extension L of P in which a <b. 2) Consider now the original well-ordering of P under which we may write L= { p(s) & @ }+ Then the function F:L > L, of Theorem 4.6. clearly sutisfies the requirements of Theorem 4.7. - 37 = 5. Universal infinite partial orders If P and & are partial orders and a bi=unique function F:P > Q is an isomorphism between P and R(F) € Q, we say that F embeds P in Q or that F is an embedding of P in We consider now any partial order P and denote by S_ the set of all linear extensions L of P. By the theorem of E. Szpilrajn [3] (which applies to both finite and infinite partial orders), the set of order relations which are common to all the LeS is exactly the partial ordering of P. Let us define the "elemental" function F:P >P( T[{l:LeS}) by: for ae P and Fla= Fa) elI{L:bes}, F(a)‘ L=a for each LeS. Then by the above remark, F is clearly an embedding of P in P(][{i:LeS} ); we say that 5S realizes P. Various subsets of S may analogously realize P; among such realizing sets of linear extensions of P there will be one of minimal cardinality (> 1, of course) because of the well-ordering of the class of cardinals. B. Dushnik and E.W. Miller [6] call this minimal cardinal the dimension of P and prove the following statements: (1) Every infinite partial order has a dimension less than or equal to its cardinality. (2) Ifa partial order P has an embedding in a second partial order 4, then dimension P < dimension Q. (3) For ae Ord and m satisfying Oo<me< mo there exists a partial order of cardinality x and dimension m. We make immediate use of the above observations in the next two theorems. - 38 - 5.1. Definition: Let «ec. Ord and m be any cardinal satisfying 0 < | ms X,- We call a partial order P x afm )- universal if every partial order @ of cardinality 3 and dimension < m has an embedding in ». If m = a? We call P simply X cuniversal by virtue of 5.(1). 5.2. Definition: let ae Ord and m be any cardinal satisfying 0 < M< N 3 let m have initial ordinal £( ¢€<¢ w,)+ We consider the partial order p(n). A function F: € > be will be called a limited series if there exists an ordinal § &€ QO. such that for each pi € Es, niFs M) = 8&3 this ordinal § will be denoted by A(F). We denote by P(m) the suborder of P(e) consisting of the limited series. We now show that each P(m) is NX (m )-universal. 5.3. Theorem: let oa c€ Ord and m be any cardinal satisfying Oo<m< Roe let P be any partial order of cardinality a with an imposed well-ordering, P= { PC pads pA & Qe } , which has a dimension n where O< n < me Then there exists an embedding F:P = P(m) of FP in Pim) having the property that for each P(u) eP and F* p(y) = F(x) e Po(m), AlF(p4)] = 4. That is, Pa m) is an x m)-universal partial order;also P(m) has dimension m . In particular, Pi ®) is an % universal partial order of SN dimension W&N a and cardinality 2 °. Assuming the General Continuum Hypothesis , P(m ) has cardinality N q Whenever m < No. Proof: 1) Pi(m) = U{t($): &e wo } where (8) = {FP e P(m) and = 39 = A(F) = 8}, and the T(§) are disjoint. Now [t(§)} = 2™*/8i, .. If m = 8, then 2mx] 8] 22 Ne for § > 0, so that |P.(,)I = P{lrC Sl: $e QO, }=2 °°, However, 1f m < X .» then by the General Continuum Hypothesis we have |7(8)] < X& a 8 that x Q < — 2 Pp = r VI. za < e ,_\ = kad IPdm)p = ZC [raed ec Qi} s Zt{k 3 be OL} Ke = NN, 0. 2) Denote by € the initial ordinal of m and by v the initial ordinal of nev S$ €3 let K be a realizing set of cardinality n of linear extensions of P with an imposed well~ordering, k= {l(y)i poe VT}. By Theorem 4.4., taking O= p and o = + \.t/ > nese mhacddane a: ra + = Ws let GC ya dsLU) L, be an embedding of (pa) in Lo having the property that for each p(v) e L(y), LCs) ‘p(vil =v for each pre T. If x < € , define Gla) = G(0} for tT<cu< €. Foreach p(v)e¢P, define o function F(v): € = Le by putting BCU) op = G(s) “ p(v) for each MoE €« Then each Fl(y) ¢« Pf m) and we may define the desired function PrP = P(m) simply by putting Flp(v)=F(v) for each v(y) cP. By the definition of K, F is an embedding of P in Pm); further , F has the property that for each p(j1) © P and FP‘ p( M) Fide Py AlPGu)} = py. 3) By 5.(2,3) and step 2) above, we have dimension P Cm) => Me. We shall. snow that dimension P(m) < m by defining m linear extensions of P itm) and showing that these extensions realize Pm) 3 we shall then have dimension P Cm) =m, - 40 = 4) For each 44 c & we define a linear extension Liu) of P{(m) as follows. For distinct elements Fis F of Pi(m)s we define F,<F, in L(y) if and only if: a) Fa < Ryo in L3 or 6 ne ‘ ‘ . b) Fy M=F ym and Fy, vy >Fov in Ly for the first ordinal z . ‘ ¢ v€ € for which Fry #Fjv. It is easily seen that each L( m4) is a linear extension of Pi(m). Thus in order to show that the set { LCi): a ce €} realizes Pim), we need only consider non-comparable elements of Pf Me 5) Let F, and F, be distinct non-comparable elements of Pi(m). Since these elements are distinct there exists a first ordinal pe é such that Fy 9 Z Fp P » and we May assume that F,'p < Fp in, Lj« Thus we have F, <F, in L(p ). Since F, and F, are non~ comparable in P (m), there mst exist an ordinal o € € such that o#p and Pio 2Fyfo in L. If Fio > BYo in L, then we have F,>F, in Wo). If Fo = F,‘o » then p is the first ordinal in ¢ for which Fy‘p #8,‘p , and the fact that F,“p < F,* p in L, implies that again F,>F, in L(o). Thus the set { L( iM ): Me é } realizes Pi(m)s showing that dimension P Cm) < m and completing the proof of Theorem 5.3. . It is easily seen that Theorem 5.3. reduces to Theorem 4.6. when ™ = 1, Also it should be noted that steps 3), 4), and 5) of the proof of Theorem 5.3. are direct generalizations of the corresponding steps given by H. Komm [7; 510~511] in his proof of essentially the same theorem for the case x a = x °° -41- 54. We see from Theorem 5.3. that it should be possible to construct for each a € Ord some suborder of Pie KY) which would be of cardinality and also would be (mn )-universal for all m< WN simultaneously. To see what suborder of P. ( x) should be constructed, we consider a partial order FP of cardinality Ox a and dimension m < & o with an imposed well~-ordering ={p(plise OL}. let FP +P (m) be the embedding of Theorem 5.3. . We must extend this embedding to some embedding G:P > P R53 this problem is equivalent to extending each limited series Fe Pi (m) to a limited series He Pf Ris The most obvious way is to define H bys H® pa = Feu for KM e€& where & is the initial ordinal of m ( € < ), and H°pw=F°O for €és<sus W + This method can easily be shown to yield the desired result, but we shall find that the following method leads to a further application. Suppose we have a limited series F ¢€ P y(n ), ns Ry» and wish to extend F toa limited series He Po Ro ). We may make a "periodic" extension of F, that is, we may define for each Me 5 9 Hy = Fr, where 0 <r <n and r is congruent to KB modulo n. By analogy, if F is a limited series in Pi(m)s m with initial ordinal €< GW» we may extend F periodically to a function He PUCK) by means of: for yi & Oo Hu =F (E sp)s (3.11.) where O< @G (Es) < € and $(€ 4) is essentially " congruent to MM modulo € ". We now make use of this idea of periodicity. -42- 55. Definitions Let a € Ord. We call a partial order PF X “Sub-universal if every partial order of cardinality WN a and dimension < Ro has an embedding in P. 5.6. Definition: Let ae Ord. A function Fe PCR) will be called a periodic limited series if there exists a non-zero as — é,, —- mé =< ordinal we W) such that F°M = F $ (1,44) for each bE Woe The minimal (non-zero) such ordinal « will be denoted by I] (F). We denote by Po the suborder of Pf x.) consisting of the periodic limited series. 5.7. Theorem: Let ace Ord and let P be any partial order of cardinality Ro with an imposed well—ordering, P= { p(y): a & QO. } » which has a dimension m where O<™< woe Then there exists an embedding H:P > Po of F in Po having the property that for each p(w) © P and H‘ p(s) = HC) EPs alH(q)] = and II (H(u4)] < € » the initial ordinal of m . That is, Po is an “Sub-universal partial order; also, Po has dimension m(a) where lim {m:m< 8 x } 0 < ma) < oe so that if W& a is a limit cardinal, Po has dimension Roe Assuming the General Continuum Hypothesis, Po has cardinality Roe Proof: 1) PF U{LU{T( 8, m:0<0< wis : §< Ww} where T(8, 7) ={ FF € Py A(F) = 8 ,and JI (F) =a } » and the T( 8, 7) are disjoint. Now |T( 8, m)| = gl 8 * Lie so that, assuming the General Continuum Hypothesis, |T( 5, 7)| < XX, and we have -43- a7 3 s Z{2{K 20 << wip 2s8< wi} = RoE RY 2) Tet F:P > Pom) be the embedding of P in Pm) of Theorem 5.365 and consider each image F* p(y) =F(u) e Pi(m). We define — C new functions H(44) © P, by: for p e OD), H(p )*p = F(y) ® (6 sp); = < . : . clearly AL HC )] = and ITLH(ps l< ¢ We now define the desired function H:P +P by putting each H ° PC )= HC )3 H clearly satisfies the conclusion of the theorem. 3) By 5.(2,3) and step 2) above, dimension P,2m forall m< & 3 by Theorem 5.3. and 5.(2), since Ps Pf Ros dimension P_< Ns Thus P| has dimension m(a) satisfying lim {m:m< xX } < m(a) < X (3 this completes the proof of Theorem 5.7. . 58 In our final theorem we shall show that for certain ordinals 4, P. is actually x universal. So far, in Theorems 536 and 5.7. we have embedded partial orders FP in the partial orders Pi(m), Pa Ri) or P, by means of realizing sets of linear extensions; essentially we embedded all of P at once. We now consider means of embedding partial orders inductively. To make clear the ideas we shall show how to embed inductively in P, a partial order P = 4p (ps): Me Oy } whose first four elements form the partial order p(>) p(3) > pi), Qs p(3) > p(2). ° p(0) pi) p(2) mim We wish to map each p/( M) of P onto some periodic limited series F(pi) € P, so that Al F( M l= MM + To exhibit the embeddings graphically we shall consider the linear order Lo to be the set of dyadic rationals between O and 2; that is, we shall associate with each function f € L, the dyadic rational y fin = m4) fin n=o 2" n=o 2” e 5.8.1. We see immediately that the partial order {p(0), p(1), p(2)} (no comparabilites) has dimension 2 and is in fact realized by the two linear extensions p(2) p(t) Lo? p(0) and Ly: p(0) . Thus we can embed { p(O), p(i), p(2) } in P, by mapping each pli), i = 0, 1, 2, onto Fi) € P, where: ‘ _ ae — FCO)" = 5 for all ME Ws l f FT or j4 even, 2 F()“p = 2. for odd and gi P , 4 for ‘M even, 2 F(2)“u4 = odd. Nol o 5 x - 45 - But this embedding cannot be extended.to an embedding of Q in Po for the following reason. Suppose we map p(3) onto some function : a ‘ ‘ F(3) in Po We must have both F(3) Mb? F(i) Mo and F(3)" > F(2) ‘x4 for all MM & W,- This would require that F(3)°p4 > F(O)"p4 for all We Qa» and we could not obtain the necessary non-comprability < p(3), p(0) >. The difficulty, of course, lies in the fact that we have utilized only two of the six possible linear extensions of {p(0),; p(1), p(2)} 3; every realizing set of linear extensions of Q has a linear extension in which both p(0) > p(1) and p(0) > p(2), We next show how to overcome this difficulty. 528-2. We define a sequence of standard functions F(a) € Pos M € G))» satisfying al (yi )] = MM as follows: F(O)*n4 = 3 for all poe Oo» a[F(O)} = O and JI[F(0)} = 1; L, iM = 0 modulo 25 2 F(i)u = + » KM =1 modulo 2, 2 alF(i4)] = 1 and TI[F(1)] = 2; ( ’ = 0, 1 modulo 8, ’ = 2, 3 modulo &, FQ) = 4 =4,5 modulo 8, m 6, 7 modulo 8, Sole Nol Mole Mol& x : “© F th - 46- ‘alF(2)1 = 2 and IT[F(2)] = 8; (4 = “3 > M #0, «66 5 7 modulo &, 2 4 » M = 8, wee 515 modulo 64, 2 4 » M 316, 2... 323 modulo 64, ’ 2 4 » M =2hy oes 931 modulo 64, 2 F(3) ‘a = < 9 53 M3325 «ee 539 modulo 64, 2 u » MK FLO, eee 547 modulo 64, 2 2 & » M 556, eee 363 modulo 64, \ 2 a{F(3)] = 3 and IT [F(3)] = 64; etc. The first four of these functions are shown in Fig. 1. It is clear from the metnod of formation that each Py) has TifF(p)) = II {2” > vs ph = ghtviv sy}. oo M(H) It is also clear that for each ne Wo» every linear order formed from the set of elements { a(0), ... » a(n)} is ebedded in L, by the associations a(i) > F(a)‘ for some ju < 2 n(m+t ) . 528.3. We embed Q in Py as follows. Since there are no comparabilities between p(0),p(1), and p(2), we map p(i) onto F(i), i = 0, 1, 25. Now we cannot map p(3) onto F(3) directly since we -. | =a ee _ tj raf al ph ih hi = a ne 1) \ ij - Tre! = fo } ee. v7 at 7] 1 au ; \. y 4 y jj - f- a i} ~ _— a 7 Lo 7 aes * FU) — — F(i2)----- *° G(3) -------- Libs - 4&8 - need p(3) > p(1/ and p(3) > p(2). Instead we define a new function G(3) as follows. For Me Oo for which the associations p(i) > P(i)“p » i = 0, 1, 2, 3, generate a linear extension of Q, G(3)“p4 = F(3)‘ps . For all other Me Gos G(3)° is the minimal rational of the form + ,o< +4 <2, k odd, for which the 2 2 associations p(i) > P(A) Sys » i =0, 1, 2, and p(3) > G(3)*p4 do generate a linear extension of 4. This embedding of Q is shown in Fig. 2. It is clear that this embedding of Q could be inductively extended to an embedding of all of P in Poe Our last theorem generalizes these ideas. 59 Definition: Let A € Ord. We say that RK, isa x x denumerable type cardinal if x, S=2 °% e 6 is a denumerable type cardinal. By the General Continuum Hypothesis (3.11) if 2 > 0, x, is a denumerable type cardinal if and only if > is a limit ordinal which is the limit of a denumerable increasing sequence of ordinals < X . In the following theorem we assume the General Continuum Hypothesis for >X > 0. 910. Theorem: Tet ,. be a denumerable type cardinal and let P be any partial order of cardinality XN, with an imposed well-ordering, P = {p (M)iM oe ®, }. Then there exists an embedding F:P > P, of P in Py, having the property that for each p(t) eP and FS p(y) =F) e Py, AlR(u)] =, and 1 if >» = 0, IE[F(p)! < 22M KH) mat as, P, isan &,- universal partial order; also, Py has cardinality and dimension M,. Proof: 1) P, has cardinality and dimension %, by Theorem 5.7. . 2) We define subsets P(n) and P, of P for each integer n > 0 as follows. If x = 0, P(n) = { p(n) } . If 2% > 0; let »~ = lin { aA (n)in € ay} with A(n) < 2rA(n+1) for each né Gs so that Ww, = lim { O(q)iB & ao }. Then P(O) = { p(y): M< (9) } and for each integer n> 0, P(n) = { P(A): > (nat) <M < O(n) } e For all values of AX we put = U{P(r)ir <n } 3) For each integer n>Olet w(n) = {f:fe pPi) and for each piu) e P(n), nlf *p(u)) =m }. If ~ = 0, |w(n)| = 2" ana we may write w(n) = { f(nys1): 41 < 2" } where we may assume that f(nyu) <f(ny pe +1) in L,- If a> 0, | w(n) | =T1{24l pquer(a)} <n> = 2", where <n>= Et lp lep(u ) € P(n) } =D {|p |: 4 < © s(n} )? 80 that lw(n)| = 43 thus we may well-order w(n) B a(n * »(n )+ and write w(n) = {f(n,pm):u < Wo (n)44 }. 4) We define functions g(n,€):P(n) > L, for each integer n > 0 and for each € € W, as follows: a) Suppose that A =O. We put g(0,é) = £(0,0) for all E€O. 5° For integers n> O and for each € € GQ). °? let Em) = & (2 ROH) 6) ana é (nn) = n(n-1) 4 n(n+1) 2) 2 » €(n)J, so that €(n) < 2 and 1 n({n~1) i 4 5 n(n=-1) 5 €(n) = 2 x € (nyn) +r with r <2 and = & (n,n) < 2°; we put g(ns€) = f[n, € (nyn)]. These constructions correspond exactly to those of 5.8.2. . ~50 = b) Suppose that A>O. We put g(0,¢)=f[0, €(0)] for each € € Gy, where €(0)= $( Qr(o)at, 6 For integers n> O and foreach € € Wy yet € (n) = EC Wy iyyygs G ) and Clan) = OL Oy yys Sls so that €(n) < O(n jay and €(n) = On (ned 41% E(nsn) + V with v< Ww and € (nyn) < A(n-1 )+1 On ne we put g(n, €)=f[n, E(nyn)]. These construc- tions are generalizations of those in 2) above. 5) We show by induction on n thatif ne Qo and G:P > 1, is any function such that for each p(y) € Pa nlc * p(y Jl=he, then there exists an ordinal &(G) © GW) such that G = U{elr, ¥(G)]: r<n}. If X=0, Y¥(G) may be taken < 22 21), a6 ~ > 05 3(G) may be taken < Or (nat? This statement is clearly true for n=0; let n>O and assume that the statement holds for n- 1. We define a function H3P Ly > Ly by: H=GN Pa-t x Ly, - Then for each p(y) & Pa-i? nlH ‘ p( JE )1 = MM >» so that by our inductive assumption there exists i an ordinal S(H); if A=O, S(H) < 22 n(n 1), if 2 > dO, SCH) < Oyo a yyys that is, H= Uf{alr, S(H)Ier <n f. Now, G-H is a function G-H:P(n) >L, such that for each p(y) € P(n), nla - H* p(ya)] = M + so that there exists an ordinal E € Wo such that G-H=f(n,€); if ~ =0, € < 2°; af 2 > 0, < ° i J H i = ¢ x (n)4+1 We define an ordinal & by means of: if “A O, = n(n-1) x = 22 . 4 - 2 x € + 33 if 2v>O0, ¥ Oy net 44% § + Y(H). 3 n(nt1) Thus, for A=0, ¥< 2 » while for 2A > 0, &<W A(n)+1° -~51- Clearly, for r<n, g(r,¥) =glr, X(H)] while g(n, %) = f(n, €), so that G= Uf{elr, S(H]ir <n} vu ti, €)=Uf{eltr,S)ir<sn} ; and we may take &(G) = ¥. 6) Now, depending on the order relations in P, we define functions k(n, €):P(n) > L, for each integer n> O and for each € € LW by induction on ne Let n€ Oy and € € G) and suppose that we have defined functions k(r,¢€):P(r) >L, for every r <n in such a manner that for each r<n and each p(y) € P(r )> nlk(r+6)‘p(u)] = MM and that U { k(r,€):r <n } generates a linear extension of Pi.1 (with the convention that Py A). Te U{k(r,¢)ir <n } u g(n,y €) generates a linear extension of P_, we define k(n,€) = g(n,€); otherwise we define k(n, €) = FL U{k(r,@)ir <n} , Q(n)1, the function of Theorem 4.4. for the present partial order ‘J = {p(u): M ce GO }, where Q(n) =n+1 if 2» =C and Q(n) = Wy) if A> O. By induction, if Uf{elr,é)ir sn} generates a linear extension of P, then k(r,¢) =e(r,€6) for r<n. Also by induction, for each € ¢ GO, ,U{k(n,€)in € a} generates a linear extension of P. _—_—_ 7) We define functions F(a): QO, > L» for each mM € Wy by putting F(m)*e = k(n, €) ‘ p(y) for each € € Wy, y where n is the integer such that p(pa) € P(n). Clearly, by 4) and 6), each F(t) e P, ( RA), and A{F(u)] = MM. Furthermore, by 4) and 6), each F(t) €P, , and in facet, for ~A =O, II [FCs l< oo M(H +1) and for X > 0, II [FC N< Wa (n)e1° Now we can define the desired function F:P > P, simply by setting F p(y) = F(p4) for each p( KM) & P, Because of the closing remark in 6), we need only check —~ 52 = that * preserves all the non-comparabilities in P. — 8) leb ne and let GrP ~L, be any function which generates o a linear extensi Q aof P. such that for each p( pA) EPs r mLG *p( i le M . By the statement in 5), there exists an ordinal ¥(G) © G) such that G= Uf{elr, ¥(G)ler <a } e But then by the next to last sentence of 6), kiv, ¥(G)]1 = glr, 8(G)] for rsa, se that Ges U {x{rs S(Gler <n } . But now any non-comparability in P ean be realized by the extensions Uf{k[n, 8 (G, Vien € a and Ulin, s(G,)] wn & oe of two such functions G to the demain P, by Theorems 4.4. and 4.7. . Thus the function F is the desired embedding for Theorem 5.10. » 5.11. te coulé, of course, perform a process analogous to that, in Theorem 5.10. for any limit cardinal XN, 5 but we could not wake the statement of step 5) once n had passed Wo» Step 5) was rucial in proving step 8), which assures us that the function F preserves the nen=comparabilities of P and is thus an embedding of ? in FP, . For non~limit cardinals, Theorems 5.3. and 5.7. are the best results the author has been able to obtain. Thus, at this point, the existence of universal partial orders of cardinality xy remains an open question for all but the denumerable type limit cardinals. It appears to the author that. Pa is about the larysst subset of PA x? which ean be specified by a rule of formation and still be of cardinality Roe Tt. might be worth while to investigate further the properties of P 3 in particular, for non=Limit cardinals x +4? -~ 53 <- it would be interesting to determine whether Po re could be Rod? universal by settling whether the dimension of Port is Ry or x ° at i1] [2] (3] i4} [6] (7) We Ne We He REFERENCES Sierpinski, "L'hypethése généralisée du continu et 1'axiome du choix," Fundamenta Mathematicae, vol. 34 (1947), pp. 1-5. Cuesta Dutari, "Teoria decimal de los tipos de orden," Revista Matematica HispanoAmericana, vol. 3 (1943), Sierpinski, "Sur une propriété des ensembles ordonnés," Fundamenta Mathematicae, vol. 36 (1949), pp. 56-67. Hausdorff, Grundzige der Mengenlehre, Leipzig, 1914. Sepilrajn, "Sur l'extension de l'order partiel," Findamenta Mathematicae, vol. 16 (1930), ope 386-389. Dushnik and E.W. Miller, "Partially ordered sets," American Journal of Mathematics, vol. 63 (1941), pj. 600-616. Komm, "On the dimension of partially ordered sets," American Journal of Mathematics, vol. 70 (1948)5 ppe 507-520.