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 (个体), atom, or urelement (基本元素) is an object with no member. 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}$: tuple, sequence;
• $\phi, \varphi, \psi$; $\omega, \alpha$; $\upsilon, \pi$; and $\mathcal{X}$: 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}$: classes of sets (variable; power set; topological structure; algebra of sets);
• $\Sigma$ and $\Phi, \Psi$: sigma-algebra; function spaces;
• $\mu, \nu, \lambda$: measures (variables; Lebesgue);
• $L^p_\mu(X)$: normed space of p-th power absolutely Lebesgue integrable functions;
• $\mathcal{C}^k(X,Y), \mathcal{C}^k(X)$: vector spaces of k-times continuously differentiable mappings / scalar-valued functions;
• $X^∗, X^\#$: algebraic dual (linear functionals) of vector space; dual (continuous linear functionals) of topological vector space;
4. Third- and higher-order objects:
• $\mathcal{L}(X,Y)$; $\mathcal{F, U}$; $\mathcal{P}^2$: vector spaces of linear operators; classes of matrices (variable; unitary); vector space of Boolean functions;
• $\tau$ and $T^{p,q}(V)$: higer-order tensor and tensor fields;
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];
• von 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 consisting of 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 includes one of them also includes the other and every element included in one of them is also included 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 (or singleton), $\{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 consists of 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 (成员; aka element 元素) of a set, especially an individual; 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$.

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

### 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 (并) $\cup \mathcal{C}$ (of members) 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 (交) $\cap \mathcal{C}$ (of members) 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)$.

Product set or Cartesian product $\times$ 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 Cartesian product of two sets $X$ and $Y$ can be denoted as $X \times Y$. Cartesian power $X^n$ of a set $X$ is the Cartesian 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.

A collection $\mathcal{C}$ of sets is disjoint (不交) if these sets have no common element: $\forall A, B \in \mathcal{C}, A = B \lor A \cap B = \emptyset$. Disjoint union (不交并) $\sqcup \mathcal{C}$ is the union of a collection of disjoint nonempty sets. Partition (划分) of a set is a collection of disjoint nonempty subsets whose union is the set. Abstract disjoint union $\sqcup$ (or discriminated union) of an indexed family $\{A_i : i \in I\}$ of sets is the set of elements in each set retaining their index: $\sqcup_i A_i := \{ (x, i) : i \in I \land x \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. Correspondence can be written as a mapping to a power set: $R: X \mapsto \mathcal{P}(Y)$; sometimes it is also written as $R: X \rightrightarrows Y$. 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\}$.

### Relation

Binary relation $R$ on a set $X$ is a correspondence on the set: $R \subset X \times X$. n-ary relation (n元关系) or n-place relation $R$ on a set $X$ is a subset of the n-th Cartesian power of the set: $R \subset X^n$. A relation is reflexive (自反) if $\mathrm{Id} \subset R$; symmetric if $R = R^T$; antisymmetric if $R \cap R^T \subset \mathrm{Id}$; transitive (传递) if $x R y, y R z \Rightarrow x R z$. Equivalence relation $\sim$ is a relation that is reflexive, symmetric, and transitive. Equivalence relation generated by a relation is the smallest equivalence relation that includes the relation: $\cap \{\sim : R \subset \sim\}$. Equivalence class $[ x ]$ of an element $x$ in a set $X$ w.r.t. an equivalence relation $\sim$ is the subset of all elements satisfying the relation with the element: $[ x ] = \{y \in X : y \sim x\}$. Any two equivalence classes are either equal or disjoint. Quotient (商) $X/\sim$ of a set by an equivalence relation is the collection of all equivalence classes in the set determined by the relation: $X/\sim = \{ [ x ] : x \in X \}$. The quotient of a set by any equivalence relation is a partition of the set. Set of class representatives is a subset formed by choosing exactly one element from each equivalence class of the underlying set w.r.t. an equivalence relation: $f: (X/\sim) \mapsto X$, $\sim \circ f = \text{Id}$.

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$. Zorn's lemma: A partially ordered set has a maximal element if every chain in the set has an upper bound. 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 bound/Least upper bound, infimum/supremum $\inf A$ / $\sup A$, or meet/join (交/并) $\wedge A$ / $\vee A$ of a non-empty subset 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 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$. Interval in a topological space is closed by definition; we may use "open interval" to refer to the set defined by strict inequalities, and use "closed interval" to call an interval. Lexicographic order (字典序) of (a subset of) the Cartesian 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 Cartesian 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 $\min X$ / $\max X$ of a totally ordered set $(X, \le)$ is its greatest/least element, if exists: $\max X := \top(X)$, $\min X := \bot(X)$. 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 or map $\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$. Function $\phi: X \mapsto \mathbb{F}^n$ often means a mapping to (a product space of) a field. 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 power of a set to the set itself. Morphism (态射) $\alpha \in H_{\mathfrak{C}}(A, B)$ of a category $\mathfrak{C}$ is a mapping from object $A$ to object $B$ in the category.

For a mapping $\phi: X \mapsto Y$: its graph (图像) is $\phi$, or $\Gamma(\phi)$, as a subset of $X \times Y$; its domain (定义域) is $X$; codomain (陪域), $Y$; 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\}$; range (值域) or image is the image $\phi(X)$ of the domain, thus a subset of the codomain; 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\}$; level set (等值集) $f^{-1}(c)$ at $c \in Y$ is the preimage of a singleton $\{c\}$; restriction to a subset $A \subset X$ of the domain, $\phi|_A := \{(x, y) : x \in A, y = \phi(x)\}$; an extension to a superset $W \supset X$ of the domain, $\psi: W \mapsto Z, \phi \subset \psi$. 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\}$.

A mapping $\phi: X \mapsto Y$ is injective (单射), or one-to-one, if distinct arguments have distinct values: $x \ne x' \implies \phi(x) \ne \phi(x')$; or $\phi^{-1}(\phi(x)) = \{x\}$. It is surjective (满射), or onto its codomain, if its range equals its codomain: $f(X) = Y$; or $\phi(\phi^{-1}(y)) = y$. It is bijective (双射) if it is both injective and surjective. Left inverse / right inverse $g: Y \mapsto X$ of a map $f: X \mapsto Y$ is a map whose composition is the identity map on the domain / codomain: $g \circ f = \text{Id}_X$ / $f \circ g = \text{Id}_Y$. Inverse (逆映射) of a map is both a left inverse and a right inverse. The inverse of a map, if exists, is unique. A map is an injection / surjection / bijection if and only if it has a left / right / - inverse.

Identity map $\mathrm{Id}_X$ on a set $X$ is the transformation $\mathrm{Id}_X := \{(x, x) : x \in X\}$ that maps each element to itself. Inclusion map $\iota: A \mapsto X$ of a subset of a set is the map that equals the identity map on the subset: $\iota = \mathrm{Id}_A$. Constant map is a map whose range is a singleton: $f(X) = \{c\}$. Permutation (置换) $\pi$ is a bijective 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 (adjacent) transpositions.

Indexed family or family (族) $(x_\alpha)_{\alpha \in A}$ of elements of a set $X$ is a mapping $x: A \mapsto X$. For an indexed family, its domain is called its index set (索引集), its range is denoted as $\{x_\alpha\}_{\alpha \in A}$. Component (成分) or term (项) $x_\alpha$ of an indexed family is the element $(\alpha, x)$ of the mapping $x$, where $\alpha$ is its index (指标) and $x$ is its value. Kronecker delta $\delta^i_j$ for indices $i, j \in I$ is a symbol for whether the indices are equal: $\delta: I^2 \mapsto \{0, 1\}$; $\delta^i_j = 1$ iff $i = j$. Ordered n-tuple (n元组) or finite sequence $(x_i)_{i=1}^n$ is an indexed family whose index set is the natural number $n$, seen as an ordinal number. Inifinite sequence (序列) $(x_i)_{i \in \mathbb{N}}$ is an indexed family whose index set is the set of natural numbers. Doubly infinite sequence $(x_i)_{i \in \mathbb{Z}}$ is an indexed family whose index set is the set of integers. Subsequence $(x_{i_j})_{j \in \mathbb{N}}$ of a sequence is a composition $x \circ i$ of the sequence with an increasing sequence $(i_j)_{j \in \mathbb{N}}$ of natural numbers. Partial sum $s_n$ of order $n$ of a sequence in a group is the sum of its first $n$ terms: $s_n := \sum_{i=1}^n x_i$. Series (级数) or infinite sum $\sum_{i=1}^\infty x_i$ in a group is the sequence of partial sums of a sequence in the group: $\sum_{i=1}^\infty x_i = (\sum_{i=1}^n x_i)_{i \in \mathbb{N}}$. The terms of the underlying sequence of a series is sometimes called the terms of the series. The study of series is equivalent to the study of sequences.

Canonical projection $\pi_i: \prod_{i \in I} X_i \mapsto X_i$ from a product set $\prod_{i \in I} X_i$ to the i-th component $X_i$ is the surjection defined by $\pi_i(x) = x_i$. Component map $f_i$ of a map $f: X \mapsto \prod_{i \in I} Y_i$ to a product set is the composition of a canonical projection with the map: $f_i = \pi_i \circ f$. Canonical injection $\iota_i: A_i \mapsto \sqcup_i A_i$ of a member set $A_i$ to the disjoint union of an indexed family of sets is the injection defined by $\iota_i(x) = (x, i)$.

## 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 ω 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 α-sequence, of elements of a set $X$ is a mapping $x: \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_i)_{i \in \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\}$. Predecessor (前驱序数) 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_i)_{i \in \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_i)_{i \in \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}$.