Note on set theory - Real Analysis

## Set Theory

Naive/informal set theory. Descriptive set theory.

Axiomatic set theories:

1. Restricting the comprehension axioms:
• Zermelo (Z) system [@Zermelo1908];
• Zermelo-Fraenkel (ZF) set theory [@Fraenkel1922]: the default;
• Neumann–Bernays–Gödel (NBG) axiomatic system [@Neumann1925; @Bernays1937; @Gödel1940]: based on ZF, introducing class, having a finite number of axioms;
2. Theory of types (T);
• NF system (an attempt to overcome the stratification of concepts);
3. Non-standard logical deduction;

ZF >> Z > T; !(NF < T); A statement about sets is provable in NBG iff it is provable in ZF.

Axiom of choice implies that every set can be well ordered and can therefore be associated with an ordinal (and a cardinal). Axiom of foundation.

Proper class is a class that is not a set. Examples of proper classes: the class of all sets; the class of all ordinals; the class of all cardinals; the class of all groups; the class of all vector spaces. Infinite set.

## Set

Set $X$ is a collection of objects. Element $x$ of a set $X$ is an object in the set: $x \in X$.

Class $\mathcal{C}$ (or set class) is a collection of sets. Power set of a set is the class $\mathcal{P}(X)$ of subsets of a set $X$: $\mathcal{P}(X) = \{A : A \subset X\}$. Because a finite set of $n$ elements has $2^n$ subsets, the power set $\mathcal{P}(X)$ of a set $X$ is also denoted as $2^X$. Exponential object $Y^X$ in the category of sets is the set of all functions $f: X \mapsto Y$ between two given sets $X$ and $Y$. The power set $2^X$ of a set $X$ can be seen as the set of all functions from $X$ to a given set of two elements $2 = \{0, 1\}$.

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

### Set Relations

Subset of a set $X$ is a set $A$ whose elements are also elements of $X$: $A \subset X$ iff $x \in A \Rightarrow x \in 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 or contain another set $A$ if $A$ is a subset of $X$.

Two sets $X$ and $Y$ are equal if they are subsets of each other: $X = Y$ iff $X \subset Y$ and $Y \subset 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$ of a class $\mathcal{C}$ of sets is the set $\cup \mathcal{C}$ of elements that belong to at least one of the sets in $\mathcal{C}$: $\cup \mathcal{C} = \{x : x \in A \in \mathcal{C}\}$. The union of two sets $A$ and $B$ can be denoted as $A \cup B$.

Intersection $\cap$ of a class $\mathcal{C}$ of sets is the set $\cap \mathcal{C}$ of elements that belong to all sets in $\mathcal{C}$: $\cap \mathcal{C} = \{x : x \in A, \forall A \in \mathcal{C}\}$. The intersection of two sets $A$ and $B$ can be denoted as $A \cap B$.

Difference $\setminus$ between two sets $A$ and $B$ is the set of elements in $A$ that is not in $B$: $A \setminus B = \{x : x \in A, x \notin B\}$. Relative complement of a subset $B$ of a set $A$ is the difference between $A$ and $B$: $\complement_A B = A \setminus B$. (Absolute) complement $\complement$ of a subset $A$ in a default underlying set $X$ is the relative complement of $A$ in $X$: $\complement A = \complement_X A$. Symmetric difference $\Delta$ 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 or of two sets $X$ and $Y$ is the set of all pairs $(x, y)$ composed of elements of the two sets: $X \times Y = \{ (x, y) : x \in X, y \in Y \}$.

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 = \{ (x_i, i) : i \in I, 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\}$.

### Mapping

Mapping (in short, map) or function $f: X \mapsto Y$ from set $X$ to set $Y$ is a set of ordered pairs $(x,y)$ such that $\forall x \in X$, $\exists! y \in Y$: $(x,y) \in f$; in other definitions, the set $f$ is also called the graph of the function, and $f(x) = y$ is equivalent notation for $(x, y) \in f$. Transformation $u: X \mapsto X$ is a mapping from a set to itself. (Algebraic) operation $\omega: X^n \mapsto X$ is a mapping from a Cartesian product $X^n$ of a set to the set $X$ itself. Operator $A: X \mapsto Y$ is a function/mapping from a space $X$ to another space $Y$, especially when $X$ and $Y$ are both vector spaces; the operation commonly denoted as $Ax = y$. Functional 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_{\mathcal{K}}(A, B)$ of a category $\mathcal{K}$ is a mapping from an object $A$ in the category into another object $B$.

### 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. 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$.

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 $(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.

## Ordinal and Cardinal Numbers

Order isomorphism (序同构) between two totally ordered sets $(X, R_X)$ and $(Y, R_Y)$ is a bijection $f: X \mapsto Y$ such that $R_Y = \{ (f(x_1), f(x_2)) : (x_1, x_2) \in R_X \}$. Order type $\overline{X}$ of a totally 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 totally ordered sets $(X, R_X)$ and $(Y, R_Y)$ are order isomorphic.

Ordinal number $\alpha$ (序数; or ordinal for short), in Cantor's definition, is the order type of a well ordered set $(X, \le)$: $\alpha = \overline{X}$. In von Neumann's definition, an ordinal $\alpha$ is a set such that: (1) $x \in \alpha \Rightarrow x \subsetneq \alpha$; (2) $x, y \in \alpha \Rightarrow (x = y) \lor (x \in y) \lor (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$, which implies $\alpha = \{\beta : \beta < \alpha\}$. The class of ordinals is well ordered via $\le$, i.e. either $<$ or $=$. Binary operations: addition, $\alpha + 1 = \alpha \cup \{\alpha\}$; multiplication; exponentiation...

• So there is no largest ordinal.
• 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}$.
• For any set of ordinals $A$, there is an ordinal $B = \cup_{\alpha \in A} \{\beta : \beta \le \alpha\}$ greater than all ordinals in the set, so the collection of all ordinals $\mathrm{Ord}$ is a proper class.

In this 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 number (超限序数) is an ordinal larger than any finite ordinal. Ordinal $\omega$ is the set of all finite ordinals $\{0, \cdots\}$; ordinal $\omega_1$ is the set of all countable ordinals; ordinal $\omega_2$ is the set of all countable and $\aleph_1$ ordinals; ordinal $\omega_\omega$ is the set all finite and $\aleph_k$ ordinals, $k \in \mathbb{N}$.

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. Countably infinite set (or countable set) is a set that is equipotent to the set $\mathbb{N}$ of all natural numbers.

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. 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$; the class of cardinals is a subclass of ordinals.

Algebraic structures on cardinals. 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|$. Binary relation less than or equal to $\le$: $|X| \le |Y|$ iff $\exists Z \subset Y: |X| = |Z|$. By the Cantor–Bernstein theorem, the class of cardinals is totally ordered.

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 countable ordinalss: $\aleph_1 = |\{X: |X| = \aleph_0\}|$. Assuming the axiom of choice, for any ordinal $\alpha$, $\aleph_\alpha = \omega_\alpha$. Thus, the aleph function $\aleph$ is a bijection from the ordinals to the infinite cardinals. 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} = 2^{\aleph_0}$.