Note on set theory - Real Analysis

Naive set theory (朴素集合论) is the informal theory of sets developed in the 19th century by B. Bolzano, P. du Bois-Reymond, R. Dedekind, etc. The fundamental paradoxes discovered by G. Cantor and B. Russell within naive set theory brought about a fundamental revision of the foundations of mathematical logic. Axiomatic set theory is a formal theory of sets formulated by methods of Mathematical Logic, which consists of: (1) a definition of the language for formulating propositions; and (2) the principles of naive set theory expressed in this language as axioms or axiom schemes. There are other types of formal theories of sets, such as descriptive set theory and combinatorial set theory. Descriptive set theory is the study of definable sets (analytic, Borel, or coanalytic sets) and mappings in Polish spaces (spaces homeomorphic to a complete separable metric space), created in the early 20th century by E. Borel, R. Baire and H. Lebesgue.

The only primitive notion in set theory is membership, a binary relation on its universe of discourse. Membership divides the universe of discourse into several types of objects. Individual is an object with no member (aka element). Any theory of sets must have at least one individual in its universe of discourse. Class (or set class) is an object with member. Set is a class that is a member of another object. Proper class is an object that is not a member of another object. Examples of proper classes: the class $\mathrm{Set}$ of all sets; the class $\mathrm{Ord}$ of all ordinals; the class $\mathrm{Card}$ of all cardinals; the class of all groups; the class of all vector spaces.

│ individual  │         class            │		    I S PC
│ (such as Ø) │    set    │ proper class │		I  │o x x │
├─────────────┴───────────┴──────────────┤		S  │o x x │
│        universe of discourse           │		PC │o o o │

Symbols

  1. Zeroth-order objects:
    • $x, y, z$ and $a, b, c$: individuals; scalar individuals;
  2. First-order objects:
    • $X, Y, Z$ and $A, B, C$: sets of individuals; subsets;
    • $\mathbb{N, Z, F, Q, R, C}$: sets of scalars (natural numbers; integers; variable field; rational, real, and complex numbers);
    • $(x_i)_{i \in I}$ and $\{x_n\}$: tuple; sequence;
    • $\phi, \varphi, \psi$; $\omega, \alpha$; $\upsilon, \pi$; and $\chi$: mappings on a set of individuals; operator, functional or morphism; transformation, permutation; random variable;
  3. Second-order objects:
    • $A, B, C, \cdots$: matrices and linear operators;
    • $\mathcal{C, P, T, A}$, and $\Sigma$: classes of sets (variable; power set; topological structure; algebra of sets; sigma-algebra);
    • $\mu, \nu, \lambda$: measures (variables; Lebesgue);
    • $\Phi, \Psi$: function spaces;
  4. Third- and higher-order objects:
    • $\mathcal{F, U}$ and $\mathcal{L}(X,Y)$: classes of matrices (variable; unitary); space of linear operators;
    • $\tau$ and $T^{p,q}(V)$: higer-order tensor and tensor fields;
    • space of Boolean functions;
  5. Universe-level objects:
    • $\text{Set, Ord, Card}$: proper classes (sets; ordinals; cardinals);
    • $\mathfrak{C, S, T, G}$: large categories (variable; of sets, topologies, and groups);
    • $\text{Ens, Lin, Ban, Hilb}$: large categories (sets; vector, Banach, and Hilbert spaces);

Natural number is a primitive concept that any natural number has a successor. The smallest natural number is 0 in von Neumann's definition of ordinal numbers, which we adopt, and 1 in the Frege–Russell logicism program.

Axiomatic Set Theory

Types of axiomatic systems for the theory of sets:

  1. Modifying the syntax and logical rules of first-order predicate calculus:
    • Theory of types (T) [@Russell1908; @Whitehead1910];
    • New Foundations (NF) [@Quine1937];
  2. Restricting the comprehension axioms:
    • Zermelo (Z) [@Zermelo1908];
    • Zermelo-Fraenkel (ZF) [@Fraenkel1922];
    • Neumann–Bernays–Gödel (NBG; coined by Mendelson) [@Neumann1925; @Bernays1937; @Gödel1940];
  3. Non-standard logical deduction;

Relative proof-theoretic strengths of axiomatic systems: ZF ≥ Z > T; ¬ NF < T.

Z is suitable for developing arithmetic, analysis, and functional analysis and for studying cardinal numbers smaller than $\aleph_\omega$. ZF is the default axiomatic set theory, which allows the formalization of all ordinary mathematical theorems. NBG is a conservative extension of ZF in the sense that a statement about sets is provable in NBG iff it is provable in ZF. But mathematicians may favor ZF or NBG for different reasons: ZF is a first-order predicate calculus, while NBG explicitly discusses proper classes besides sets.

ZF's universe of discourse consists of one individual, i.e. "the empty set", and sets; The empty set $\emptyset$ is not a notion for any concrete individual but rather the individual of set theory construct, i.e. $\{\}$, so that the intersection of any two sets without a common member is the empty set. ZF redefines set to include the empty set so that all objects in its universe are sets. NBG's universe of discourse consists of ZF's universe and proper classes. ZF and NBG deal with only one individual to achieve simplicity and elegance, with the justification that if ZF is consistent, so are the corresponding systems of set theory with any finite or infinite number of individuals.

Formal Language

The formal language of an axiomatic set theory consists of: (1) an alphabet including primitive notions in set theory, e.g. set and membership $\in$, and symbols from mathematical logic, e.g. equality $=$; and (2) rules for forming and rewriting admissible expressions. The alphabet consists of: variables, common names of objects, e.g. $x, y, z$; predicates $\in$ and $=$; definite description operator $℩$; quantifiers $\forall$ and $\exists$; boolean connectives $\lnot$, $\land$, and $\lor$; propositional connectives $\rightarrow$ and $\leftrightarrow$; and precedence grouping $()$. Expressions are grouped into terms (names of objects) and formulas (propositions); formulas are often denoted as capital letters, e.g. $A, B$. Notation symbol $\Leftrightarrow$ is often used to define additional expressions.

Attitudes towards equality: 1. The identity in the underlying logic (logical truths), whose basic properties are reflexivity, symmetry, transitivity, substitutivity; 2. The second primitive relation in set theory, besides membership, taking the properties of logical equality as axioms and theorems; 3. A definition such that the properties of logical equality are provable. Membership congruence, a definition of equality, is a binary relation on sets such that every set which contains one of them contains also the other and every element contained in one of them is also contained in the other: $x = y \Leftrightarrow \forall w (w \in x \leftrightarrow w \in y) \land$ $\forall z (x \in z \leftrightarrow y \in z)$.

Common notations. Subset, $A \subset B \Leftrightarrow \forall x (x \in A \rightarrow x \in B)$. Empty set, $\emptyset \Leftrightarrow ℩ x \forall y \lnot y \in x$. Set of all terms satisfying a formula, $\{x : A(x)\} \Leftrightarrow ℩ z \forall x (x \in z \leftrightarrow A(x))$. Set of two (or unordered pair), $\{x, y\} \Leftrightarrow \{z : z = x \lor z = y\}$. Set of one, $\{x\} \Leftrightarrow \{x, x\}$. Ordered pair, $(x, y) \Leftrightarrow \{\{x\}, \{x, y\}\}$. Union, $x \cup y \Leftrightarrow \{z : z \in x \lor z \in y\}$. Intersection, $x \cap y \Leftrightarrow \{z : z \in x \land z \in y\}$. Union of members, $\cup x \Leftrightarrow \{z : \exists v(z \in v \land v \in x)\}$. Power set, $\mathcal{P}(x) \Leftrightarrow \{y : y \subset x\}$. Cartesian product, $x \times y \Leftrightarrow \{z : \exists u v (z = (u, v) \land u \in x \land v \in y\}$. Predicate on sets, $\mathrm{Set}(x) \Leftrightarrow \exists w (w \in x) \land \exists y (x \in y)$. Predicate on mappings, $\mathrm{Fnc}(w) \Leftrightarrow \exists v (w \subset v \times v)$ $\land \forall u v_1 v_2 ((u, v_1) \in w \land (u, v_2) \in w \rightarrow v_1 = v_2)$. Value of a mapping $w$ at an element $x$, $w'x \Leftrightarrow ℩ y (x, y) \in w$. Image of a set $x$ under a mapping $w$, $w''x \Leftrightarrow \{y : \exists z (z \in x \land (z, y) \in w)\}$. Set of terms as the values of a mapping at terms satisfying a formula, $\{w'x : A(x)\} \Leftrightarrow w''\{x : A(x)\}$.

Axiomatic Systems

Table: Axioms of (A, Z, and ZF) (Axiom schemes have suffix 's' in their number.)

# Axiom(s) of Formal Expression Interpretation
1 Extensionality $\forall x (x \in y \leftrightarrow x \in z) \rightarrow y = z$ Sets are equal if they have the same members.
2s Comprehension $\exists y \forall x (x \in y \leftrightarrow A(x))$, where $A$ has no $y$. Any proposition defines a set (whose members are all that meet the proposition).
2.1 Pairing $\exists y \forall x (x \in y \leftrightarrow x = w \lor x = z)$ Any set of two exists.
2.2 Union $\exists y \forall x (x \in y \leftrightarrow \exists w (x \in w \land w \in z)$ Any union of members exists.
2.3 Power set $\exists y \forall x (x \in y \leftrightarrow x \subset z)$ Any power set exists.
2.4s Separation $\exists y \forall x (x \in y \leftrightarrow x \in z \land A(x))$ Any proposition defines a set within another.
2.5s Replacement $\exists y \forall x (x \in y \leftrightarrow \exists v (v \in z \land x = ℩ t A(v,t)))$ Any definable mapping maps a set to a set.
3 Infinity $\exists z (\emptyset \in z \land \forall u (u \in z \rightarrow u \cup \{u\} \in z))$ Natural numbers define a set.
4 Foundation $\forall x (\lnot x = \emptyset \rightarrow \exists y (y \in x \land y \cap x = \emptyset))$ Any non-empty set has a minimal member.
5 Choice $\forall z \exists w (\mathrm{Fnc}(w) \land \\ \quad \forall x (\lnot x = \emptyset \land x \in z \rightarrow w' x \in x))$ It is possible to choose one member from each of many non-empty sets simultaneously, if the latter form a set.

The principles of naive set theory can be expressed as: A1, axiom of extensionality (外延公理), and A2s, axiom scheme of comprehension (内涵/概括公理模式). Russell's paradox shows that these two axioms implicit in naive set theory are self-contradictory: let $A$ be $\lnot x \in x$, then $\forall x (x \in y \leftrightarrow \lnot x \in x)$ implies $y \in y \leftrightarrow \lnot y \in y$, which is a contradiction. The proposition that "a term is not an member of itself" is almost universally true, so it describes any term. But if the collection of all terms is also a term, then it is an member of itself, which contradicts the assumption.

Z includes axioms A1, A2.1-4s, A3-5. ZF adds axiom scheme A2.5s, proposed by Fraenkel, to the axioms of Z.

NBG can be formulated with the following steps: (1) restrict all quantifiers in ZF axioms to sets, i.e. replace $A$ with $\mathrm{Set}(x) \rightarrow A$ in formulas $\forall x A$ and $\exists x A$; (2) add the class comprehension axiom scheme: $\exists X \forall x (x \in X \leftrightarrow A(x))$; "Any proposition (with no bound class variable or definite description) defines a class"; (3) add the limitation of size principle as an axiom: $\lnot \exists y (x \in y) \leftrightarrow |x| = |\mathrm{Set}|$; "Proper classes are classes equinumerous to the class of all sets." The axioms of NBG implies the (global) axiom of choice: $\exists X (\mathrm{Fnc}(X) \land \forall x (\lnot x = \emptyset \rightarrow X' x \in x))$; "There is a choice function defined on the class of all nonempty sets." The class comprehension axiom scheme may be replaced with a finite number of class comprehension axioms, using the eight Gödel class construction functions.

Set

Now we set up a convention of notation for most articles of this wiki, which is slightly different from that for axiomatic set theory: lowercase letter $x$ denotes a member of a set, especially individuals; uppercase letter $X$ denotes a set; calligraphic letter $\mathcal{C}$ denotes a class whose members are sets.

Exponential object $Y^X$ in the category of sets is the set of all mappings $\phi: X \mapsto Y$ between two given sets $X$ and $Y$. The power set $\mathcal{P}(X)$ of a set $X$ can be seen as the set of all mappings $\phi: X \mapsto 2$ from $X$ to a given set of two elements $2 = \{0, 1\}$, so $\mathcal{P}(X)$ is sometimes also denoted as $2^X$.

Space $(X, \cdots)$ is a set with certain mathematical structures (algebraic, topological, measure).

Set Relations

Primitive relation: membership $\in$. A set $X$ is said to contain an object $x$ if $x$ is a member of $X$.

Equality $=$, as defined by membership congruence.

Subset $A$ of a set $X$: $A \subset X$. Superset of a set $X$ is a set $Y$ of which $X$ is a subset: $Y \supset X$ iff $X \subset Y$. A set $X$ is said to include another set $A$ if $A$ is a subset of $X$. Proper subset or strict subset of a set $X$ is a subset $A$ of $X$ which is not equal to $X$: $A \subsetneq X$ iff $A \subset X$ but not $X \subset A$. Proper superset or strict superset of a set $X$ is a set $Y$ of which $X$ is a proper subset: $Y \supsetneq X$ iff $X \subsetneq Y$.

Set Operations

Union (of members) $\cup \mathcal{C}$ of a class $\mathcal{C}$ of sets is the set of elements that belong to at least one of the sets in $\mathcal{C}$. Union of two sets $A$ and $B$ is denoted as $A \cup B$.

Intersection (of members) $\cap \mathcal{C}$ of a class $\mathcal{C}$ of sets is the set of elements that belong to all sets in $\mathcal{C}$: $\cap \mathcal{C} := \{x : A \in \mathcal{C} \implies x \in A\}$. Intersection of two sets $A$ and $B$ is denoted as $A \cap B$.

Difference $A \setminus B$ between two sets $A$ and $B$ is the set of elements in $A$ that are not in $B$: $A \setminus B := \{x : x \in A \land x \notin B\}$. Relative complement $\complement_A B$ of a set $B$ that is a subset of $A$ is the difference between $A$ and $B$: $\complement_A B := A \setminus B$. (Absolute) Complement $\complement A$ of a set $A$ included in a default underlying set $X$ is the relative complement of $A$ in $X$: $\complement A := \complement_X A$. Symmetric difference $A \Delta B$ of two sets $A$ and $B$ is the set of elements in either $A$ or $B$, but not both: $A \Delta B := (A \setminus B) \cup (B \setminus A) = (A \cup B) \setminus (A \cap B)$.

Direct product $\times$, Cartesian product, or product set of a class $\{X_i : i \in I\}$ of sets indexed by a well-ordered set $(I, \le)$ is the set of all tuples $(x_i)_{i \in I}$ of elements of the sets: $\prod_{i \in I} X_i := \{ (x_i)_{i \in I} : x_i \in X_i \}$. The direct product of two sets $X$ and $Y$ can be denoted as $X \times Y$. Cartesian power $X^n$ of a set $X$ is the direct product of $n$ copies of the set: $X^n := \prod_{i=1}^n X$; Cartesian square $X^2$ of a set $X$ is its second Cartesian power.

Disjoint union $\sqcup$ (or discriminated union) of an indexed class $\{A_i : i \in I\}$ of sets is the set of elements in each set retaining their index: $\sqcup_i A_i := \{ (i, x_i) : i \in I \land x_i \in A_i \}$.

Correspondence

Correspondence $(R, X, Y)$ between two sets $X$ and $Y$ is a subset $R \subset X \times Y$ of their Cartesian product. Correspondence generalizes the concept of mapping and binary relation. Involution $R^\sharp$, inverse $R^{-1}$, or transpose $R^T$ of a correspondence $(R, X, Y)$ is the correspondence $(R^\sharp, Y, X)$ consisting of all switched pairs $(y, x)$ in $R$: $R^\sharp := \{(y, x) : (x, y) \in R\}$.

Binary Relation

Binary relation $R$ is a correspondence on a set $X$: $R \subset X \times X$. ($n$-place or $n$-ary) relation $R$ on a set $X$, $n \in \mathbb{N}$, is a subset $R \subset X^n$ of the $n$-th Cartesian power of the set.

Partial order on a set $X$ is a binary relation $\le$ (less than or equal to) on the set that satisfies: (1) reflexivity: $x \le x$; (2) anti-symmetry: $x \le y, y \le x \Rightarrow x = y$; (3) transitivity: $x \le y, y \le z \Rightarrow x \le z$. Partially ordered set or poset $(X, \le)$ is a set $X$ with a partial order $\le$. Any subset of a partially ordered set is also a partially ordered set. Chain of a partially ordered set $(X, \le)$ is a totally ordered subset $(A, \le)$. Antichain of a partially ordered set $(X, \le)$ is an incomparable subset $(A, \le)$: $\{(x, y) : x \le y, x, y \in A\} = \emptyset$. Length/Width of a partially ordered set $(X, \le)$ is the largest size of its chains/antichains. Minimal/Maximal element of a partially ordered set $(X, \le)$ is an element $x$, if exists, no greater/less than any other element: $\nexists y \in X: (y, x) \in R$; for the latter, $\nexists y \in X: (x, y) \in R$. Least/Greatest element, bottom/top $\bot$ / $\top$, or zero/unit $0$ / $1$ of a partially ordered set $(X, \le)$ is the element, if exists, less/greater than all other elements: $\forall x \in X, (\bot, x) \in R$; for the latter, $\forall x \in X, (x, \top) \in R$. Lower/Upper bound of a non-empty subset $A$ of a partially ordered set $(X, \le)$ is an element $x$, if exists, less/greater than or equal to all elements of the subset: $\forall a \in A, x \le a$; for the latter, $\forall a \in A, a \le x$. Lower/Upper cone $A^\bigtriangleup$ / $A^\bigtriangledown$ of a non-empty subset $A$ of a partially ordered set $(X, \le)$ is the set of all its lower/upper bounds: $A^\bigtriangleup := \{x : \forall a \in A, x \le a\}$; for the latter, $A^\bigtriangledown := \{x : \forall a \in A, a \le x\}$. Greatest lower/Least upper bound, infimum/supremum $\inf A$ / $\sup A$, or meet/join $\wedge A$ / $\vee A$ of a non-empty subset $A$ of a partially ordered set $(X, \le)$ is the greatest/least element, if exists, of its lower/upper cone: $\inf A := \top(A^\bigtriangledown)$; for the latter, $\sup A := \bot(A^\bigtriangleup)$. Interval or segment $[a, b]$ between two elements $a$ and $b$ of a partially ordered set $(X, \le)$ is the set of all elements greater than or equal to $a$ and less than or equal to $b$: $[a, b] := \{x : a \le x \le b\}$; equivalently, it is the intersection of the upper cone of $a$ and the lower cone of $b$: $[a, b] = \{a\}^\bigtriangleup \cap \{b\}^\bigtriangledown$. Interval $[a, b]$ has infimum $a$ and supremum $b$. Lexicographic order of (a subset of) the direct product $\prod_{m \in M} A_m$ of a well-ordered class $\{(A_m, \le)\}_{m \in (M, \le)}$ of partially ordered sets is the partial order $\le$ such that $(a_m)_{m \in M} < (b_m)_{m \in M}$ iff $\exists n \in M$: $\forall m \in M, m < n, a_m = b_m$, $a_n < b_n$; lexicographic product is a direct product with lexicographic order.

Total order of a set $X$ is a partial order on the set that satisfies the comparability condition (aka trichotomy law): $\forall a, b \in X$, $a \le b$ or $b \le a$; or equivalently, $R \cup R^\sharp = A \times A$. Totally ordered set or chain $(X, \le)$ is a set $X$ with a total order $\le$. Any subset of a totally ordered set is also a totally ordered set. Maximum/Minimum of a totally ordered set $(X, \le)$ is its greatest/least element, if exists. A totally ordered set cannot have a maximal/minimal element that is not its maximum/minimum.

Well-ordered set is a totally ordered set $(X, \le)$ such that every nonempty subset of $X$ has a minimum. Any subset of a well-ordered set is also a well-ordered set. Finite totally ordered sets are well-ordered. The set of integers $\mathbb{Z}$ with the total order $\le$ is not a well-ordered set. The lexicographic product of a finite collection of well-ordered sets is well-ordered. By axiom of choice, every set can be well-ordered.

Mapping

Mapping (in short, map) or function $\phi: X \mapsto Y$ from set $X$ to set $Y$ is a subset of $X \times Y$ such that $\forall x \in X$, $\exists! y \in Y$: $(x,y) \in \phi$; a mapping is equipotent with its domain, $|\phi| = |X|$; in other definitions, $\phi(x) = y$ is an equivalent notation for $(x, y) \in \phi$. Transformation $\upsilon: X \mapsto X$ is a mapping from a set to itself. (Algebraic) operation $∗: X^n \mapsto X$ is a mapping from a Cartesian product $X^n$ of a set to the set $X$ itself. Operator $\omega: X \mapsto Y$ is a mapping from a space $X$ to another space $Y$, especially when $X$ and $Y$ are both vector spaces; its application to a vector is commonly denoted as $\omega x = y$. Functional $\alpha: X \mapsto \mathbb{F}$ is an operator from a vector space $X$ of functions to a scalar field $\mathbb{F}$, usually $\mathbb{R}$ or $\mathbb{C}$. Morphism $\alpha \in H_{\mathfrak{C}}(A, B)$ of a category $\mathfrak{C}$ is a mapping between objects $A$ and $B$ in the category.

For a mapping $\phi: X \mapsto Y$: its domain is $X$; codomain, $Y$, graph, $\phi$; value at an element $x \in X$ of the domain, $\phi(x)$ such that $(x, \phi(x)) \in \phi$; image of a subset $A \subset X$ of the domain, $\phi(A) := \{y : \exists x \in A, (x, y) \in \phi\}$; image $\phi(X)$ of the domain is also alled the image or range of the function; preimage (or inverse image) of a subset $B \subset Y$ of the codomain, $\phi^{-1}(B) := \{x : \exists y \in B, (x, y) \in \phi\}$; extension to a superset $W \supset X$ of the domain, $\psi: W \mapsto Z, \phi \subset \psi$; restriction to a subset $A \subset X$ of the domain, $\phi|A := \{(x, y) : x \in A, y = \phi(x)\}$. Composition $\circ$ of two mappings $\phi: X \mapsto Y$ and $\psi: Y \mapsto Z$ is the mapping $\psi \circ \phi := \{(x, z) : \exists y \in Y, (x, y) \in \phi, (y, z) \in \psi\}$.

Sequence $\{x_n\}$ of elements of a set $X$ is a mapping $\{x_n\}: \mathbb{N} \mapsto X$. Term $x_n$ of a sequence $\{x_n\}$ is an element of the mapping: $x_n := (n, x) \in f$, where $n$ is its index and $x$ is its value. Series $\sum_{n \in \mathbb{N}} x_n$ is a pair $(\{x_n\}, \{s_n\})$ consisting of a sequence $\{x_n\}$ of elements of a topological vector space $(X, +, d(\cdot, \cdot))$ and the sequence $\{s_n\}$ where $s_n := \sum_{i=1}^n x_i$. For a series $(\{x_n\}, \{s_n\})$, $x_n$ is its $n$-th term and $s_n$ is its partial sum of order $n$. The study of series is equivalent to the study of sequences.

Identity map $1_X$ or $\mathrm{id}_X$ on a set $X$ is the transformation $1_X := \{(x, x) : x \in X\}$ that maps each element to itself. Permutation $\pi$ is a one-to-one transformation. Transposition $(i, j)$ is a permutation that displaces only two elements $i$ and $j$. Symmetric group $S(X)$ on a set $X$ is the group consisting of the set of all permutations on $X$ and the composition operation $\circ$. The symmetric group of a finite set of $n$ elements is denoted as $S_n$. The symmetric groups of equipotent sets are isomorphic: $S(X) \cong S(|X|)$. The cardinal of a symmetric group on a set equals the factorial of the cardinal of the set: $|S(X)| = |X|!$. Finitary symmetric group $SF(X)$ on a set $X$ is the subgroup of $S(X)$ consisting of the set of all permutations on $X$ that displace only a finite number of elements. Any finitary permutation can be written as a composition of transpositions.

Ordinal and Cardinal Numbers

The problem of equivalence classes of infinite sets, first considered by Cantor during 1871--1883.

Order Isomorphism and Ordinal Numbers

Order isomorphism (序同构) between two partially ordered sets $(X, R_X)$ and $(Y, R_Y)$ is an order-preserving bijection $\phi: X \mapsto Y$: $R_Y = \{ (\phi(x_1), \phi(x_2)) : (x_1, x_2) \in R_X \}$. Order type $\overline{X}$ of a partially ordered set $(X, R_X)$, in Cantor's notation, is the property associated with classes of order isomorphic sets such that: $\overline{X} = \overline{Y}$ iff the partially ordered sets $(X, R_X)$ and $(Y, R_Y)$ are order isomorphic. Ordinal number $\alpha$ (序数; or ordinal for short) is the order type of a well-ordered set $(X, \le)$: $\alpha := \overline{X}$ [@Cantor1883]. In von Neumann's definition [@von-Neumann1923], an ordinal $\alpha$ is a set such that: (1) $x \in \alpha \Rightarrow x \subsetneq \alpha$; (2) $x, y \in \alpha \Rightarrow (x = y)$, $(x \in y)$, or $(y \in x)$; and (3) $\forall A \subsetneq \alpha, \exists x \in \alpha : x \cap A = \emptyset$. From this definition, we know that: the empty set is an ordinal; any element of an ordinal is an ordinal.

Algebraic structures on ordinals. Binary relations: equal to, $\alpha = \beta$ iff there are well-ordered sets $X$ and $Y$ such that $\overline{X} = \alpha$, $\overline{Y} = \beta$, and $\overline{X} = \overline{Y}$; less than, $\alpha < \beta$ iff $\exists \gamma \in \beta: \alpha = \gamma$. The class $\mathrm{Ord}$ of ordinals is well-ordered via $\le$, i.e. either $<$ or $=$. Binary operations (lexicographic order applies): addition, $\overline{X} + \overline{Y} := \overline{X \sqcup Y}$, (associative, commutative with identity $0 := \overline{\emptyset}$); multiplication, $\overline{X} \times \overline{Y} := \overline{X \times Y}$, (associative, commutative with identity $1 := \overline{\{\emptyset\}}$, left distributive with addition); exponentiation (via transfinite induction), $\alpha^0 := 1$, $\alpha^\beta := \alpha^{\beta - 1} \times \alpha$, and $\alpha^\lambda := \lim_{\beta < \lambda} \alpha^\beta$, where $\beta$ is not a limit ordinal and $\lambda$ is a limit ordinal other than $0$.

The class of ordinals. The order relation defined on ordinals implies that each ordinal is the set of all ordinals less than it: $\alpha = \{\beta : \beta < \alpha\}$. In von Neumann's representation, ordinal 0 is the empty set $\emptyset = \{\}$; ordinal 1 is the set of one ordinal (the empty set) $\{\emptyset\}$; ordinal n, $n \in \mathbb{N}$, is the set of $n$ ordinals $\{0, \cdots, n-1\}$. Written in pure set notation (braces and commas only), the finite ordinal $n$ would have $2^n$ pairs of braces. Transfinite ordinal (超限序数) is an ordinal larger than any finite ordinal. Ordinal $\omega$ is the set of all finite ordinals, $\omega := \{0, \cdots\}$. For any set of ordinals $A$, there is an ordinal $\gamma = \cup_{\alpha \in A} \{\beta : \beta \le \alpha\}$ greater than all ordinals in the set, so the class $\mathrm{Ord}$ of all ordinals is a proper class.

Indexing by ordindals. Transfinite sequence of order type $\alpha$, aka $\alpha$-sequence, of elements of a set $X$ is a mapping $\{x_\alpha\}: \alpha \mapsto X$. As a special case, an (infinite) sequence is an $\omega$-sequence. Any well-ordered set $(X, \le)$ can be uniquely indexed by the bijective $\alpha$-sequence, $\alpha = \overline{X}$, such that $\alpha(x) = \overline{\{y : y < x\}}$. Countably infinite set (or countable set) is a set that can be indexed by an $\omega$-sequence. Transfinite induction (超限归纳法) [@Hausdorff1906] is a method to prove a well-ordered set $\{P_\alpha\}$ of propositions, by showing: (1) $P_0$ is true; (2) if $\{P_\beta : \beta < \alpha\}$ is true, then $P_\alpha$ is true. As a special case, mathematical induction is transfinite induction on an $\omega$-sequence of propositions. By transfinite induction, every well-ordered set is order isomorphic to exactly one ordinal. Because an ordinal is a well-ordered set, every ordinal represents the order type of the class of well-ordered sets order isomorphic to it. Thus, the ordinal of an ordinal is itself: $\alpha = \overline{\alpha}$.

Classification of ordinals. Successor of an ordinal $\alpha$ is the ordinal $\alpha + 1 := \alpha \cup \{\alpha\}$. Predesessor of an ordinal $\alpha$, if exists, is the ordinal $\beta$ such that $\beta + 1 = \alpha$. Limit ordinal $\lambda$ is an ordinal that has no predesessor. For example, $0$ and $\omega$ are limit ordinals. Any ordinal $\alpha$ has a unique representation $\alpha = \lambda + n$, where $\lambda$ is a limit ordinal and $n \in \mathbb{N}$ is a finite ordinal. Limit of a transfinite sequence $\{x_\alpha\}$ is the least of the ordinals greater than all terms in the sequence: $\lim_{\beta < \alpha} x_\beta := \min \{\gamma : \gamma > x_\beta, \forall \beta < \alpha\}$. Cofinal ordinal to a limit ordinal $\lambda$ is an ordinal $\mu$ that is the limit of an ascending $\lambda$-sequence: $\mu = \lim_{\alpha < \lambda} x_\alpha$; apparently, $\mu \ge \lambda$. Cofinality $\mathrm{cf}(\alpha)$ of an ordinal $\alpha$ is the least limit ordinal that $\alpha$ is cofinal to: $\mathrm{cf}(\alpha) := \min \{\lambda : \exists \{x_\lambda\}, \lim_{\beta < \lambda} x_\beta = \alpha\}$; this means $\mathrm{cf}: \mathrm{Ord} \mapsto \mathrm{LimOrd}$ is a mapping from the class of ordinals to the class of limit ordinals. For example, $\mathrm{cf}(0) = 0$, $\mathrm{cf}(\omega) = \omega$, $\mathrm{cf}(\omega_n) = \omega_n$, $\mathrm{cf}(\omega_\omega) = \omega$. Regular ordinal is an limit ordinal that is its own cofinality: $\lambda = \mathrm{cf}(\lambda)$. Singular ordinal is an ordinal that is not regular.

Equipotence and Cardinal Numbers

Equipotence (等势), equipollence, or equinumerosity is an equivalence relation on the class of sets such that two sets satisfy this relation if there is a bijection between them. Cardinal number (基数; or cardinal for short), cardinality, or power (势) $|X|$ of a set $X$ is the property associated with classes of equipotent sets such that: $|X| = |Y|$ iff the sets $X$ and $Y$ are equipotent. The class of cardinals is a subclass of ordinals.

Algebraic structures on cardinals. Binary relation: less than or equal to, $|X| \le |Y|$ iff $\exists Z \subset Y: |X| = |Z|$. By the Cantor–Bernstein theorem, the class of cardinals is totally ordered. Binary operations: addition (associative, commutative), $|X| + |Y| := |X \sqcup Y|$; multiplication (associative, commutative; distributive w.r.t. addition), $|X| \times |Y| := |X \times Y|$; exponentiation, $|Y|^{|X|} := |Y^X|$.

The class of cardinals. The cardinality of a finite set is a natural number. Aleph numbers are the cardinality of infinite well-ordered sets. Aleph null $\aleph_0$ is the cardinality of the set of natural numbers: $\aleph_0 := |\mathbb{N}|$. $\aleph_1$ is the cardinality of the set of ordinals with cardinality no greater than $\aleph_0$: $\aleph_1 := |\{\alpha: |\alpha| \le \aleph_0\}|$. By transfinite induction, the class of aleph numbers can be indexed by ordinals: $\{\aleph_\alpha\}_\alpha$, where $\aleph_\alpha := |\{\beta: |\beta| < \aleph_\alpha\}|$. The collection of all cardinals $\mathrm{Card} := \mathbb{N} \cup \{\aleph_\alpha\}_{\alpha}$ is a proper class. Cardinality of the continuum $\mathfrak{c}$ is the cardinality of the set of real numbers: $\mathfrak{c} := |\mathbb{R}|$. It can be shown that $\mathfrak{c} = \alpha^{\omega}$ for all $2 \le \alpha \le \mathfrak{c}$. The following sets all have cardinality $\mathfrak{c}$: $T_\infty$, $(0,1)$, $[0,1]$, $\mathbb{R} \setminus \mathbb{A}$, $\mathbb{R} \setminus \mathbb{Q}$, $\mathbb{R}$, $\mathbb{R}^n$, $\mathbb{R^N}$, $C^0(\mathbb{R})$, $\mathcal{T}_{\mathbb{R}^n}$, $\mathcal{B}_{\mathbb{R}}$. Continuum hypothesis (CH) [@Cantor1878]: There is no cardinal between $\omega$ and $\mathfrak{c}$, the cardinalities of the countable and the continuum; i.e., $\aleph_1 = \mathfrak{c}$. Generalized continuum hypothesis (GCH): There is no cardinal between an aleph number and its power; i.e. $\aleph_{\alpha + 1} = 2^{\aleph_\alpha}$. CH is independent of ZF: ZF+CH is consistent under some model [@Godel1938], and so is ZF+¬CH [@Cohen1963]; more generally, for all $\alpha$ that is not a limit ordinal of countable cofinality, ZF+$\aleph_\alpha = 2^{\aleph_0}$ is consistent under some model, see e.g. [@Kunen2011].

Relating ordinals and cardinals. Initial ordinal $\omega(\aleph_\alpha)$ of cardinality $\aleph_\alpha$ is the least ordinal with cardinality $\aleph_\alpha$: $\omega(\aleph_\alpha) := \min_{|\beta| = \aleph_\alpha} \beta$. By transfinite induction, the class of initial ordinals can be indexed by ordinals: $\{\omega_\alpha\}_\alpha$, where $\omega_\alpha = \omega(\aleph_\alpha)$. For example, $\omega_0 = \omega$. Initial ordinal $\omega_\alpha$ whose index is $0$ or a non-limit ordinal is regular; in general, initial ordinal $\omega_\lambda$ whose index is a limit ordinal is singular. Weakly inaccessible ordinal is a limit ordinal-indexed initial ordinal $\omega_\lambda$ that is regular. ZF set theory cannot prove that there is any weakly inaccessible ordinal other than $\omega$. Assuming the axiom of choice, the cardinal of a set $X$ is the least ordinal $\alpha$ such that $X$ and $\alpha$ are equipotent, $|X| = \min_{|\alpha| = |X|} \alpha$, then we have: (1) cardinals are the ordinals that are their own cardinals, $\mathrm{Card} = \{\alpha : \alpha = |\alpha|\}$; (2) $\omega(\aleph_\alpha) = \aleph_\alpha$, and thus $\omega_\alpha = \aleph_\alpha$, which means aleph numbers and initial ordinals are identical.

Relations among some proper classes: $\mathrm{PO} \supsetneq \mathrm{TO} \supsetneq \mathrm{WO} \supsetneq \mathrm{Ord} \supsetneq \mathrm{Card}$; $\mathrm{TfOrd} \supsetneq \mathrm{TfLimOrd} \supsetneq \mathrm{TfCard} \supsetneq \mathrm{TfRegOrd}$. Mappings between some proper classes: $|X|: [X] \mapsto \mathrm{Card}$; $\overline{X}: \mathrm{PO} \mapsto \mathrm{PO}$. Surjective mappings between some proper classes: $\overline{X}: \mathrm{WO} \mapsto \mathrm{Ord}$; $|X|: \mathrm{Ord} \mapsto \mathrm{Card}$.


🏷 Category=Analysis