Set Theory/Cardinals

Axioms used. We work in ZF throughout this page. We do not assume the Axiom of Choice (AC) or the Axiom of Regularity unless explicitly noted. Without AC, not every set need be well-orderable; when we speak of “the” cardinal of a set as an initial ordinal, this is for well-orderable sets. All comparisons “” are meaningful in ZF. Bijections and “same size” Two sets have the same cardinality (are the same “size”) if there is a bijection between them: iff there exists a one-to-one onto function . This is an equivalence relation. For finite sets this recovers ordinary counting. For infinite sets, bijections let us compare sizes without “counting all the way.” Examples. and are equipollent via any bijection, e.g. . and are equipollent via (with ). Comparing sizes: injections and Cantor–Bernstein We write if there is an injection . We write if and . Cantor–Bernstein (Schröder–Bernstein). If and , then . Assume there are injections and . Step 1 (Reduce to the nested case via equipollence). Let . Since is injective, it restricts to a bijection with inverse defined by whenever . Hence . Because equipollence is an equivalence relation, it suffices to prove ; then transitivity gives . Therefore, replacing by we may assume from now on that . Define (injective) and . Thus and is a bijection of onto its image . Step 2 (Iterate on and ). Define descending sequences , Then and for all . Let . Then and . Step 3 (Define the candidate bijection ). Set We verify that is bijective . Claim 1 (Points in already lie in and are fixed). Since , if then , hence . By definition , so . Claim 2 (Layers map forward: ). Because , for we have Thus iff , proving the equality. Taking unions over , For , , hence . Also by definition. Therefore By the definition of on , we conclude Surjectivity. Using Claims 1–2, Injectivity. Let . If and , then since is the identity. If and , then , and injective gives . If , , then by Claim 2, while by Claim 1; these are disjoint, so . (Symmetrically for , .) Hence is injective. Together with surjectivity, is a bijection , and therefore . Cantor’s theorem and the powerset jump (Cantor.) For every set , . Let be any function. Define the “diagonal” subset We show that is not in the range of . Suppose, for a contradiction, that there exists with . Then: By definition of , we have But if , this becomes a contradiction. Hence no such exists, so . Therefore no function is surjective, so . The map is an injection , hence . Combining these, we conclude . Write for when . If , then . is a bijection. Thus for every cardinal “”. Cardinal arithmetic (well-defined operations) Given representatives , (with ): Sum: . Product: . Exponentiation: (set of all functions ). These do not depend on the particular representatives (routine bijection arguments). Some basic facts (provable in ZF by building the appropriate injections/bijections): and are associative and commutative; distributes over . , , . If then . If then . , , and for . Cardinals as initial ordinals (well-orderable sets) When a set is well-orderable, its cardinal can be taken to be the least ordinal of that size (an initial ordinal). Write cardinals as . Finite cardinals are just the natural numbers: . is the least infinite cardinal. A cardinal is a (nonzero) limit cardinal if it is not a successor cardinal. For every ordinal there exists a cardinal strictly greater than . More generally, for every set there exists an ordinal such that no injection exists; moreover, is a cardinal (an initial ordinal). Step 1 (Collect all well-orderings of subsets of as a set). Consider the class of all binary relations on , which is the set by the Axiom of Power Set. Using Separation, form the subset Thus is a set. Step 2 (Take order-types; Replacement). For each , let be the unique ordinal isomorphic to (where ). The map is functional; by the Axiom Schema of Replacement, its range is a set of ordinals. Intuitively, is the set of all ordinals that inject into (via the isomorphisms to well-ordered subsets of ). Step 3 (Define and verify its key property). Let (existence by Union; ordinals are transitive so union is supremum), and let the successor (existence by Pairing and Union). Then every ordinal satisfies , hence , so there is an injection . On the other hand , so there is no injection . Thus is the least ordinal with no injection into . Step 4 ( is an initial ordinal, hence a cardinal). Suppose, towards a contradiction, that for some . Since , there is an injection (by Step 3). Let be a bijection. Then is injective—contradicting the defining property of . Hence no ordinal is equipollent with ; i.e. is an initial ordinal (a cardinal). Step 5 (Specialize to ). For an ordinal , every injects into (the inclusion map), so and therefore . Thus there exists a cardinal strictly greater than . If is a set of cardinals and , then is a cardinal. Assume for contradiction that is equipollent to some (i.e. there is a bijection ). By the definition of , for this there exists with . Now compare sizes: Because (as ordinals), there is an injection , so . Because , there is an injection , so . Because (via ), we get and by Cantor–Bernstein, . But is a cardinal (an initial ordinal), so it cannot be equipollent to the strictly smaller ordinal —a contradiction. Therefore no such exists, and is an initial ordinal, i.e. a cardinal. Alephs and their indexing Define the increasing enumeration of all initial infinite cardinals: By abuse of notation in set theory texts, one often also writes for the initial ordinal of cardinality . (In ZF, we use this only for well-orderable sets.) The canonical well-ordering of We define a canonical well-order on pairs of ordinals. For , set iff either , or and , or , , and . Intuitively: first compare the larger coordinate, then (if tied) compare the first coordinate, then (if tied) the second. The relation above is a well-ordering of the class . Moreover, for each ordinal , the set is exactly the initial segment below . Linearity. For any two pairs, either their maxima differ (deciding ), or the maxima agree and then the first coordinates decide unless they agree again, in which case the second coordinates decide. Hence any two pairs are comparable. Well-foundedness. Let be nonempty. Consider the set of maxima , which has a least element since ordinals are well-ordered. Restrict to . Among first coordinates in choose the least ; among pairs in with first coordinate choose the least second coordinate . Then is the least element of . Initial segment at . A pair satisfies iff , i.e. iff and . Thus the initial segment below is exactly . For a pair , write , and define , where refers to the order type of well-ordered set, i. e. the unique ordinal that bijects with it. The previous theorem immediately gives: For every ordinal , . By the initial-segment identification, , hence . Remarks. is a well-ordered proper class and therefore (uniquely) order-isomorphic to . In particular, is strictly increasing: if , then . For each ordinal , because the chain has type inside (in other words, is an increasing function). Product of alephs via the canonical well-order We now give a proof that the product of an infinite aleph with itself is itself. Let . From the remark above, for every . For every (well-orderable) infinite cardinal , . Equivalently, . Assume toward a contradiction that there is a least with . Since is an ordinal strictly greater than . By definition of ordering of ordinals, we have . By the definition of order-type, there exists an isomorphism between and . Let . Using "initial segments respects isomorphisms," there is an isomorphism between the initial segment by in and the initial segment by in , meaning Choose with and . Then , so the initial segment contains a point of rank , and hence Therefore . But by minimality of , for every we must have , hence . Contradiction. Thus no such exists, and for all , i.e. . Corollary (addition and multiplication of infinite alephs). For all infinite alephs, Using disjoint union and product of well-orders, together with the idempotence , one shows that both cardinal addition and multiplication collapse to the larger factor on infinite cardinals. Notes on AC. With AC, every set is well-orderable, “cardinals” are initial ordinals for all sets, and the comparison linearly orders cardinals. Without AC, we keep all comparisons and constructions above for well-orderable sets, and we refrain from claims that require global well-ordering (e.g., that is an aleph). Worked examples and quick consequences is countable (give an explicit bijection). The set of all finite sequences of naturals is countable; so is the set of all finite subsets of a countable set. For infinite alephs, . By Cantor, ; strictly, follows from standard projection arguments (see Exercises). See also Cardinality Ordinals Zermelo-Fraenkel Axiomatic Set Theory pt:Teoria dos conjuntos/Cardinalidade