Set Theory/Ordinals

Finite and transfinite ordinal numbers Historical context Preliminaries Axioms used. Unless stated otherwise, we work in ZF. We do not use Choice or Regularity on this page. Replacement is used for Transfinite Recursion and the Rank/Height theorem for well-founded relations. Standard representation of ordinal numbers The definition of ordinal numbers offers little insight into their nature. In situations like this pure mathematicians create representations of the objects they wish to study. Such representations are built from familiar mathematical constructions and are equivalent to the obstruce objects. By manipulating the familiar objects in the representation, the pure mathematician may thus investigate the structure of the mysterious abstract entities. The most common representation of the ordinal numbers, due to Von Neumann, is as follows. The ordinal 0 is defined to be the empty set ; the ordinal 1 is defined to be the set , which is of course equal to . Similarly, the ordinal 2 is the set ; the ordinal 3 is the set ; the ordinal 4 is the set . Any finite ordinal is defined to be the set (or, in a rigorous notation, the successor of an ordinal α is defined as the set ). In fact this definition extends naturally to transfinite ordinals. The ordinal is the set consisting of every finite ordinal . Again, is the set ; is the set ; and so on. The ordinal (or ) is the set consisting of all finite ordinals and ordinals of the form , where is a finite ordinal. Thus . The ordinal is the first uncountable ordinal, and is the set of all countable ordinals. Definition and basic facts Definition (transitive set). A set is transitive if implies (equivalently: .) Definition (ordinal). A set is an ordinal if it is transitive and well-ordered by . Unpacking “well-ordered”. If is an ordinal, then on is a strict linear order: Irreflexive (nonreflexive): for all , . Transitive: if (all in ), then . Total on : for in , either or . And every nonempty subset of has a least element under . Lemma (subset of a well-order). If is well-ordered and , then is well-ordered (by restriction). Elements of ordinals are ordinals. If is an ordinal and , then is transitive and well-ordered by : since is transitive, , so the restriction of well-orders ; if , then and the strict-order transitivity of on gives . Successor and limit ordinals. is an ordinal; ordinals of the form are successors. An ordinal that is neither nor a successor is a (nonzero) limit ordinal. Infima and suprema of ordinals. For a nonempty class of ordinals, is an ordinal and the greatest lower bound of . For a (set) of ordinals, is an ordinal and the least upper bound of . Core facts is an ordinal. Vacuously transitive and well-ordered by . If are ordinals with , then . Let be the -least element of . Since is transitive, , i.e. (the initial segment of cut by ). But initial segments of an ordinal are exactly its elements, hence . If are ordinals, then either or . Consider . It is an ordinal (subset of either, hence well-ordered; transitive because both are). If and , then by the previous theorem and , so , impossible (irreflexivity). Hence equality with one side holds, giving comparability by inclusion. For any two different ordinals, either or . By the previous theorem, either or . If they are unequal, the proper-subset case gives membership by the first theorem; by convention means . Natural numbers and We construct the natural numbers as finite ordinals and obtain (the least infinite, least nonzero limit ordinal) from the Axiom of Infinity. Axiom (Infinity). There exists a set such that and for every , its successor also lies in . Such a set is called inductive. Lemma 1. If is inductive, then is inductive. Proof. is an ordinal and lies in ; if , then and is an ordinal, so . ■ Construction. Fix an inductive set . Let and define Lemma 2. is inductive and is the least inductive subset of . Proof. Intersection of inductive subsets of is inductive; minimality is by definition of intersection. ■ Lemma 3. . Proof. By Lemma 1, is inductive and contained in , hence . ■ is an ordinal and the least nonzero limit ordinal. If , since is an ordinal (Lemma 3) and transitive, , meaning , proving ; hence is transitive. Being a set of ordinals, it is well-ordered by . It is nonzero since . It has no greatest element because it is inductive; thus it is a limit ordinal. If is a limit ordinal, then and , so is inductive and hence . ■ First few ordinals. Define and . The finite ordinals are exactly the elements of . Then are formed by repeated successor from ; is the order-type of two -blocks in sequence, etc. Transfinite induction and recursion Transfinite Induction. Let be a class of ordinals with: (i) ; (ii) ; (iii) if is a limit ordinal and for all , then . Then . If not, let be the least ordinal not in ; each of the three cases contradicts (i)–(iii). Assume . That's an immediate contradiction to (i). Assume is a successor ordinal. Then the predecessor of is in and by (ii), , a contradiction. Now assume that is a limit ordinal. Since it is the least ordinal, any must satisfy . By (iii), it follows that . Transfinite sequences. A function with its domain an ordinal is a sequence . For ordinal-valued sequences, limits at limits are taken by suprema: . A sequence is normal if it is increasing and continuous (value at limits equals the supremum of earlier values). Transfinite Recursion (class form). There is a unique function ( is the class of all sets) such that for every ordinal , . Define iff there exists a sequence with (i) for all , and (ii) . The witnessing sequence is unique by induction on . Existence of such sequences is shown by induction on ; at limits take unions (Replacement ensures sets). Uniqueness of follows by induction. Set-length version. If is a set, an ordinal, and maps sequences in of length into , there is a unique sequence in with . Ordinal arithmetic We define operations by recursion on the second argument. Addition. . . For nonzero limit , . Multiplication. . . For nonzero limit , . Exponentiation. . . For nonzero limit , . These are normal (increasing and continuous) in the second variable. Associativity of and . For all ordinals : (i) ; (ii) . By transfinite induction on . Base is immediate. Successor: use the recursive clauses. Limit: use the induction hypothesis inside suprema and continuity. Non-commutativity. ; . Geometric picture. is the order-type of a disjoint sum “all of before all of ”; is the lexicographic product “ many levels, each a copy of ” (ordered first by level). Basic monotonicity and division facts. If then and (for ) by induction on . If there is a unique with (take the order-type of ). For any and there exist unique and with (choose maximal with ). Cantor Normal Form Cantor Normal Form. Every has a unique representation , with , , and integers . By induction on . Let be the greatest ordinal with . Divide: with ; show is finite; apply induction to . Uniqueness follows by comparing highest exponents and coefficients. Remark. The least fixed point of is . Well-founded relations A binary relation on a set is well-founded if every nonempty has an -minimal element. Any well-order is well-founded, but need not be linear. Rank and height. If is well-founded on , there is a unique function such that . The range is an initial segment of the ordinals; its supremum is the height of . Existence/uniqueness of rank. Define by induction: , , for limit . By Replacement there is a least with . If , pick an -minimal ; then all lie in , so , contradiction. Define as the least with ; then the recursion equation holds and uniqueness follows from minimal counterexample. Well-founded recursion. If is well-founded on and is any operation, there exists a unique with Exercises Prove there is no strictly decreasing sequence in a well-ordered set. Show there are arbitrarily large limit ordinals. For a normal sequence , show it has arbitrarily large fixed points. Prove distributivity and power rules: , , . Find examples witnessing failure of cancellation for or on the left/right. Define by , , and ; show . Prove the well-founded recursion theorem stated above. Zorn's Lemma and the Axiom of Choice Cardinals pt:Teoria dos conjuntos/Números ordinais