# 离散数学 · 集合、关系、函数与基数 > Arietids Learn · 个人课程复习笔记 > 在线阅读：https://learn.arietids.net/courses/discrete-math/chapter-03/ ## Notation Used in These Notes Symbols used throughout these notes: | Symbol | Meaning | |---|---| | $x \in y$ / $x \notin y$ | membership / non-membership | | $x \subseteq y$ | subset (for any $z$, $z\in x \Rightarrow z\in y$) | | $x \cup y$, $x \cap y$, $x \setminus y$ | union, intersection, set difference | | $\varnothing$ | the empty set | | $\mathcal{P}(x)$ | power set | | $\bigcup x$ | general (big) union | | $x \times y$ | Cartesian product | | $a\,R\,b$ | $(a,b)\in R$ (relation notation) | | $R^{-1}$, $S\circ R$ | inverse relation, composite relation | | $[a]_R$ | equivalence class of $a$ under $R$ | | $A \leqslant B$ | $A$ is dominated by $B$: there is an **injection** $A\to B$ | | $A \approx B$ | $A$ is **equinumerous** to $B$: there is a **bijection** $A\to B$ | | $A \not\approx B$ | $A$ is not equinumerous to $B$ | | $B^A = (A\to B)$, $2^A=(A\to\{0,1\})$, $A^2=A\times A$ | function-space / product shorthand | --- ## 1. Naive Set Theory (朴素集合论) ### 1.1 Basic constructions - An element of a set can itself be a set. - **Membership**: $x\in y$ means "$x$ is an element of $y$". - **Equality (extensionality)**: $x=y$ iff for any $z$, $z\in x \Leftrightarrow z\in y$. - **Subset**: $x\subseteq y$ iff for any $z$, if $z\in x$ then $z\in y$. - $x=y$ iff $x\subseteq y$ and $y\subseteq x$. - **Union**: $z\in x\cup y \Leftrightarrow z\in x \text{ or } z\in y$. - **Intersection**: $z\in x\cap y \Leftrightarrow z\in x \text{ and } z\in y$. - **Set-theoretic difference**: $z\in x\setminus y \Leftrightarrow z\in x \text{ and } z\notin y$. - **Empty set**: $\varnothing$ satisfies "for any $z$, $z\notin\varnothing$". - **Enumerated set**: $x\in\{a_1,a_2,a_3\} \Leftrightarrow x=a_1 \text{ or } x=a_2 \text{ or } x=a_3$. - **Set-builder**: $x\in\{y \mid y^2-3y+2=0\} \Leftrightarrow x^2-3x+2=0$. - **Power set (幂集)**: $y\in\mathcal{P}(x) \Leftrightarrow y\subseteq x$. - **General union**: $y\in\bigcup x \Leftrightarrow$ there exists $z$ such that $z\in x$ and $y\in z$. - **Indexed union**: $y\in\bigcup_{i=0}^{+\infty} x_i \Leftrightarrow$ there exists $i\in\mathbb{N}$ such that $y\in x_i$. - **Indexed intersection**: $y\in\bigcap_{i=0}^{+\infty} x_i \Leftrightarrow$ for any $i\in\mathbb{N}$, $y\in x_i$. - **Ordered pairs**: $(x,y)$. - **Equality of pairs**: $(x,y)=(u,v) \Leftrightarrow x=u \text{ and } y=v$. - **Cartesian product**: $x\times y = \{(u,v)\mid u\in x \text{ and } v\in y\}$. ### 1.2 Example 1 — monotonicity of $\mathcal{P}$, $\bigcup$ and $A=\bigcup\mathcal{P}(A)$ Claims: (a) if $A\subseteq B$ then $\mathcal{P}(A)\subseteq\mathcal{P}(B)$; (b) if $A\subseteq B$ then $\bigcup A\subseteq\bigcup B$; (c) $A=\bigcup\mathcal{P}(A)$. - **(a) Method**: take an arbitrary element $X\in\mathcal{P}(A)$, so $X\subseteq A$; since $A\subseteq B$, $X\subseteq B$, hence $X\in\mathcal{P}(B)$. - **(b) Method**: take $x\in\bigcup A$; there is $Y\in A$ with $x\in Y$; since $A\subseteq B$, $Y\in B$, so $x\in\bigcup B$. - **(c) Method**: $(\subseteq)$ for $x\in A$, the singleton $\{x\}\subseteq A$ so $\{x\}\in\mathcal{P}(A)$, and $x\in\{x\}$ gives $x\in\bigcup\mathcal{P}(A)$. $(\supseteq)$ for $x\in\bigcup\mathcal{P}(A)$ there is $Y\in\mathcal{P}(A)$ with $x\in Y$; $Y\subseteq A$ so $x\in A$. - **Transferable pattern**: prove set equality $S=T$ by the two inclusions $S\subseteq T$ and $T\subseteq S$; prove an inclusion by taking an arbitrary element and unfolding the membership definitions. ### 1.3 Example 2 — $\mathcal{P}$ over $\cap$, and $\times$ over $\bigcup$ Claims: (a) $\mathcal{P}(A)\cap\mathcal{P}(B)=\mathcal{P}(A\cap B)$; (b) $A\times\bigcup B = \bigcup\{A\times X \mid X\in B\}$. - **(a)** $(\subseteq)$ $X\in\mathcal{P}(A)\cap\mathcal{P}(B)$ gives $X\subseteq A$ and $X\subseteq B$, so every $a\in X$ lies in $A\cap B$, hence $X\subseteq A\cap B$, i.e. $X\in\mathcal{P}(A\cap B)$. $(\supseteq)$ $X\subseteq A\cap B$ gives $X\subseteq A$ and $X\subseteq B$. - **(b)** $(\subseteq)$ for $(a,x)\in A\times\bigcup B$, $x\in\bigcup B$ gives some $X\in B$ with $x\in X$, so $(a,x)\in A\times X$; the key step is $A\times X\in\{A\times X\mid X\in B\}$, hence $(a,x)\in\bigcup\{A\times X\mid X\in B\}$. $(\supseteq)$ reverse: an element of the big union lies in some $A\times X$ with $X\in B$, write it as $(a,x)$ with $a\in A$, $x\in X\subseteq\bigcup B$. --- ## 2. Binary Relations ### 2.1 Definition - **Definition**: subsets of $A\times B$ are **binary relations from $A$ to $B$**; subsets of $A\times A$ are also called **binary relations on $A$**. - **Notation**: write $a\,R\,b$ for $(a,b)\in R$. ### 2.2 Properties of a relation $R$ on $A$ - **reflexive on $A$** (自反性): $\forall a\in A.\ (a\,R\,a)$. - **symmetric** (对称性): $\forall a,b\in A.\ \text{if } a\,R\,b \text{ then } b\,R\,a$. - **antisymmetric** (反对称性): $\forall a,b\in A.\ \text{if } a\,R\,b \text{ and } b\,R\,a \text{ then } a=b$. - **transitive** (传递性): $\forall a,b,c\in A.\ \text{if } a\,R\,b \text{ and } b\,R\,c \text{ then } a\,R\,c$. ### 2.3 Operators - **Inverse**: if $R\subseteq A\times B$, then $R^{-1}=\{(x,y)\in B\times A \mid y\,R\,x\}$. - **Composition**: if $R\subseteq A\times B$ and $S\subseteq B\times C$, then $S\circ R := \{(x,z)\in A\times C \mid \exists y\,(x\,R\,y \wedge y\,S\,z)\}$. - **Theorem 6**: $(R^{-1})^{-1}=R$; $(S\circ R)^{-1}=R^{-1}\circ S^{-1}$; $R\circ(S\circ T)=(R\circ S)\circ T$ (associativity). - **Theorem 7**: $R\circ(S\cup T)=(R\circ S)\cup(R\circ T)$. - **Theorem 8 (characterizations)**, with $I_A:=\{(a,b)\in A\times A\mid a=b\}$: - $R$ reflexive on $A$ iff $I_A\subseteq R$. - $R$ symmetric iff $R=R^{-1}$. - $R$ transitive iff $R\circ R\subseteq R$. - $R$ antisymmetric iff $R\cap R^{-1}\subseteq I_A$. --- ## 3. Equivalence Relations, Classes, and Partitions ### 3.1 Equivalence relations and classes - **Definition**: $R\subseteq A\times A$ is an **equivalence relation on $A$** if it is reflexive, symmetric, and transitive. - **Equivalence class**: for an equivalence relation $R$ on $A$ and $a\in A$, $[a]_R:=\{b\in A\mid a\,R\,b\}$; $a$ is a **representative element** of $[a]_R$. - **Theorem 11**: for an equivalence relation $R$ and $a,b\in A$, $\ a\,R\,b \Leftrightarrow [a]_R=[b]_R$. - $(\Rightarrow)$ for any $c$, $c\in[a]_R \Leftrightarrow a\,R\,c \Leftrightarrow b\,R\,c \Leftrightarrow c\in[b]_R$ (middle step uses $a\,R\,b$ with symmetry+transitivity). - $(\Leftarrow)$ by reflexivity $b\in[b]_R=[a]_R$, hence $a\,R\,b$. - **Theorem 12**: for an equivalence relation $R$ and $a,b\in A$, $\ a\,R\,b \Leftrightarrow [a]_R\cap[b]_R\neq\varnothing$. - $(\Rightarrow)$ $a\,R\,b$ gives $[a]_R=[b]_R$, and $a\in[a]_R$ so the (equal) class is nonempty. - $(\Leftarrow)$ if $c\in[a]_R\cap[b]_R$, then $a\,R\,c$ and $b\,R\,c$, so $[a]_R=[c]_R=[b]_R$, hence $a\,R\,b$. ### 3.2 Partitions - **Partition**: $P\subseteq\mathcal{P}(A)$ is a **partition of $A$** if (i) $\forall B\in P.\ B\neq\varnothing$; (ii) $\forall B,B'\in P.\ \text{if } B\neq B' \text{ then } B\cap B'=\varnothing$ (pairwise disjoint); (iii) $\bigcup P=A$. - **Theorem 2 (partition $\Rightarrow$ equivalence relation)**: if $P$ is a partition of $A$, then $R=\{(a,b)\in A\times A\mid \exists B\in P.\ a\in B \text{ and } b\in B\}$ is an equivalence relation on $A$, and $P$ is exactly the set of all equivalence classes of $R$, i.e. $P=\{[a]_R\mid a\in A\}$. - reflexive: each $a\in A$ lies in some $B\in P$ (since $\bigcup P=A$), so $a\,R\,a$. - symmetric: from the symmetric form of $R$'s definition. - transitive: $a\,R\,b$ and $b\,R\,c$ give blocks $B_1,B_2\in P$ with $a,b\in B_1$ and $b,c\in B_2$; blocks of a partition are identical or disjoint, and $b\in B_1\cap B_2$ forces $B_1=B_2$, so $a\,R\,c$. - $P=\{[a]_R\}$: each block $B\in P$ is nonempty, pick $a\in B$, then $B=[a]_R$; conversely each $a\in A$ lies in some block $B$ and $[a]_R=B$. --- ## 4. Closures: Transitive and Reflexive-Transitive ### 4.1 Transitive closure (传递闭包) - **Definition 1 (universal/order-theoretic form)**: for a relation $R$ on $A$, $R'$ is the transitive closure of $R$ if (i) $R\subseteq R'$; (ii) $R'$ is transitive; (iii) for every $T$, if $R\subseteq T$ and $T$ is transitive, then $R'\subseteq T$. (I.e. $R'$ is the **smallest** transitive relation containing $R$.) - **Definition 2 (constructive form)**: $R^n$ is the $n$-fold composition of $R$, and $R^+$ is the transitive closure: - $R^1 \triangleq R$; - $R^{n+1} \triangleq R^n\circ R$; - $R^+ \triangleq \bigcup_{n\in\mathbb{Z}^+} R^n$. - Remark (原文): the textbook writes $R^*$, but it should generally be written $R^+$. - **Theorem 3**: the two definitions above are equivalent. Supporting lemmas: - **Lemma 4 (monotonicity of $\circ$)**: if $R_1\subseteq R_1'$ and $R_2\subseteq R_2'$, then $R_1\circ R_2\subseteq R_1'\circ R_2'$. - **Lemma 5**: if $R_n\subseteq T$ for every $n$, then $\bigcup_n R_n\subseteq T$ (stated for an arbitrary indexed family $\{R_n\}$; later instantiated with $R_n=R^n$). - **Lemma 6**: $R\subseteq R^+$. - **Lemma 7**: $R^n\circ R^m = R^{n+m}$. - **Lemma 8**: $R^+$ is transitive. Proof: $a\,R^+\,b$ and $b\,R^+\,c$ give $n,m$ with $a\,R^n\,b$ and $b\,R^m\,c$; then $a\,R^{n+m}\,c$ (Lemma 7), so $a\,R^+\,c$. - **Lemma 9**: if $R\subseteq T$ and $T$ is transitive, then $R^+\subseteq T$. Proof by induction: $R^1\subseteq T$; if $R^n\subseteq T$ then $R^{n+1}=R^n\circ R\subseteq T\circ T\subseteq T$ (transitivity); hence $R^+=\bigcup_{n\in\mathbb{Z}^+}R^n\subseteq T$. - **Lemma 10**: there is at most one least relation that is a superset of $R$ and is transitive. - Adding these lemmas together proves Theorem 3. ### 4.2 Reflexive transitive closure (自反传递闭包) - **Definition 11 (universal form)**: $R'$ is the reflexive transitive closure of $R$ if (i) $R\subseteq R'$; (ii) $R'$ transitive; (iii) $R'$ reflexive; (iv) for every $T$, if $R\subseteq T$, $T$ transitive and $T$ reflexive, then $R'\subseteq T$. (原文该普遍形用 $R'$ 记闭包,构造形 $R^*$ 见 Definition 12。) - **Definition 12 (constructive form)**: $R^0\triangleq I_A=\{(a,a)\mid a\in A\}$, and $R^*\triangleq\bigcup_{n\in\mathbb{N}}R^n$ (so the index starts at $0$, adding the identity for reflexivity). - **Theorem 13**: the two definitions of the reflexive transitive closure are equivalent. --- ## 5. Functions ### 5.1 Definition - **Definition (function)**: a relation $F\subseteq A\times B$ is a **function** from $A$ into $B$ iff (i) $\forall x\in A.\ \exists y.\ (x\,F\,y)$ (totality), and (ii) $\forall x\forall y\forall y'.\ (\text{if } x\,F\,y \text{ and } x\,F\,y' \text{ then } y=y')$ (single-valuedness). $A$ is the **domain**, $B$ the **codomain**. - **Notation**: write $F:A\to B$ for a function from $A$ into $B$; $F(x)$ is the unique element with $(x,F(x))\in F$. - **Theorem 17 (function extensionality)**: for $F,G:A\to B$, $\ F=G \Leftrightarrow \forall x\in A.\ F(x)=G(x)$. - **Theorem 18 (composition is a function)**: for $F:B\to C$ and $G:A\to B$, $F\circ G$ is a function and $(F\circ G)(x)=F(G(x))$ for all $x\in A$. ### 5.2 Special classes of functions For $f:A\to B$: - **one-to-one / injection (单射)**: $\forall a,a'\in A.\ \text{if } f(a)=f(a') \text{ then } a=a'$. - **onto / surjection (满射)**: $\forall b\in B.\ \exists a\in A.\ f(a)=b$. - **bijection (one-to-one correspondence, 双射)**: both an injection and a surjection. - **Theorem 20 (composition)**, for $F:B\to C$, $G:A\to B$: - $F,G$ injections $\Rightarrow F\circ G$ injection. - $F,G$ surjections $\Rightarrow F\circ G$ surjection. - $F\circ G$ injection $\Rightarrow G$ injection (only the inner map is forced). - $F\circ G$ surjection $\Rightarrow F$ surjection (only the outer map is forced). - **Theorem 21**: if $F:A\to B$ is a bijection, then $F^{-1}\subseteq B\times A$ is also a bijection. --- ## 6. The Schröder–Bernstein Theorem - **Theorem 1 (Schröder–Bernstein)**: if $f:A\to B$ and $g:B\to A$ are both injections, then there is a bijection from $A$ into $B$. - **Key construction** (the transferable idea — "back-and-forth chasing through $g$'s non-image"): - $C_0=\{a\in A\mid \forall b\in B.\ g(b)\neq a\}$ — the elements of $A$ outside the range of $g$. - $D_0=\{f(a)\mid a\in C_0\}$. - $C_1=\{a\in A\setminus C_0 \mid \forall b\in B\setminus D_0.\ g(b)\neq a\}$; one shows $C_1=\{g(b)\mid b\in D_0\}$. - $D_1=\{f(a)\mid a\in C_1\}$, and in general $C_{n+1}=\{a\in A\setminus\bigcup_{i=0}^n C_i \mid \forall b\in B\setminus\bigcup_{i=0}^n D_i.\ g(b)\neq a\}$, $D_{n+1}=\{f(a)\mid a\in C_{n+1}\}$, with $C_{n+1}=\{g(b)\mid b\in D_n\}$. - Define $$ h(a)=\begin{cases} f(a), & a\in\bigcup_{i=0}^{\infty} C_i\\ b \text{ s.t. } g(b)=a, & a\in A\setminus\bigcup_{i=0}^{\infty} C_i\end{cases} $$ - **Why $h$ is a bijection**: - injection (three cases): both in the $\bigcup C_i$ branch — then $f(a_1)=f(a_2)$ so $a_1=a_2$ ($f$ injective); mixed branch — if $a_1\in A\setminus\bigcup_i C_i$ and $a_2\in C_n$, then $f(a_2)\in D_n$ and $g(f(a_2))\in C_{n+1}$, so $a_1=g(h(a_1))=g(h(a_2))=g(f(a_2))\in C_{n+1}$, a contradiction (so no collision across branches); both in the complement branch — then $g(h(a_1))=a_1$ and $g(h(a_2))=a_2$ give $a_1=a_2$. - surjection: if $b\in D_n$ there is $a\in C_n$ with $f(a)=b$; if $b\in B\setminus\bigcup_i D_i$, set $a=g(b)$, which must lie in $A\setminus\bigcup_i C_i$ (otherwise $a\in C_n$ forces $b\in D_n$, contradiction), and then $h(a)=b$. --- ## 7. Equinumerosity and Cardinal Comparison ### 7.1 Definitions - **Domination**: $A\leqslant B$ if there exists an **injection** from $A$ into $B$. - **Equinumerosity**: $A\approx B$ if there exists a **bijection** from $A$ into $B$. ### 7.2 Basic facts - **Theorem 4**: $[0,1]\approx[0,1)$. Proof 1: by Schröder–Bernstein. Proof 2: explicit bijection $f(x)=x/2$ if $x\in\{1,\tfrac12,\tfrac14,\tfrac18,\dots\}$, and $f(x)=x$ otherwise (shift the dyadic chain to drop the endpoint $1$). - **Theorem 5**: $\mathbb{N}\approx\mathbb{N}\times\mathbb{N}$. - **Theorem 6 ($\approx$ behaves like an equivalence relation)**: $A\approx A$; if $A\approx B$ then $B\approx A$; if $A\approx B$ and $B\approx C$ then $A\approx C$. - **Theorem 7 (products)**: $A\times B\approx B\times A$; if $A_1\approx A_2$ and $B_1\approx B_2$ then $A_1\times B_1\approx A_2\times B_2$. - constructions: $F(a,b)=(b,a)$ is the swap bijection; for the second part, bijections $f:A_1\to A_2$, $g:B_1\to B_2$ give $h(x,y)=(f(x),g(y))$. - **Corollary 8**: $\mathbb{N}\approx\mathbb{Q}$ and $\mathbb{N}\times\mathbb{N}\times\mathbb{N}\approx\mathbb{N}$. - via $\mathbb{N}\leqslant\mathbb{Q}\leqslant\mathbb{Z}^+\times\mathbb{Z}\approx\mathbb{N}\times\mathbb{N}\approx\mathbb{N}$, and $(\mathbb{N}\times\mathbb{N})\times\mathbb{N}\approx\mathbb{N}\times\mathbb{N}\approx\mathbb{N}$ (Schröder–Bernstein turns the $\leqslant$-chain into $\approx$). ### 7.3 Equinumerosity of function spaces (N608) **Theorem 1** collects the function-space identities (here $(A\to B)$ is the set of all functions from $A$ to $B$): - if $A_1\approx A_2$ and $B_1\approx B_2$, then $(A_1\to B_1)\approx(A_2\to B_2)$; - if $A_1\leqslant A_2$ and $B_1\leqslant B_2$, then $(A_1\to B_1)\leqslant(A_2\to B_2)$ when $B_2\neq\varnothing$; if $B_2=\varnothing$, this conclusion also holds except in the edge case $A_1=\varnothing$ and $A_2\neq\varnothing$. - **currying**: $((A\times B)\to C)\approx(A\to(B\to C))$; - **pairing**: $(A\to B\times C)\approx(A\to B)\times(A\to C)$; - $(\{0,1\}\to A)\approx A\times A$; - if $A\approx B$, then $\mathcal{P}(A)\approx\mathcal{P}(B)$; - $(A\to\{0,1\})\approx\mathcal{P}(A)$. Proof techniques (the transferable bijection constructions): - relabel domain/codomain by $H(h)=g\circ h\circ f^{-1}$ (uses $f,g$ bijections). - for the $\leqslant$ version with $B_2\neq\varnothing$, pick $b\in B_2$ and extend outside $f[A_1]$, using injectivity of $f$ (well-definedness) and $g$ (injectivity of $H$); the $B_2=\varnothing$ case must be checked separately as above. - currying via $H(f)(a)(b)=f(a,b)$; pairing via $H(f,g)(a)=(f(a),g(a))$; $(\{0,1\}\to A)\approx A\times A$ via $H(f)=(f(0),f(1))$; power-set monotonicity ($A\approx B$ by a bijection $f$ $\Rightarrow \mathcal{P}(A)\approx\mathcal{P}(B)$) via $H(X)=\{f(a)\mid a\in X\}$; and $(A\to\{0,1\})\approx\mathcal{P}(A)$ via the indicator map $H(f)=\{a\in A\mid f(a)=1\}$. - **Notation**: $A^2:=A\times A$, $A^3:=A\times A\times A$, …; $2^A:=(A\to\{0,1\})$ and $B^A:=(A\to B)$. --- ## 8. Countable Sets - **Definition**: a set $A$ is **countable** if it is equinumerous to $\mathbb{N}$ ($A\approx\mathbb{N}$). - **Example 10 (countable sets)**: $\mathbb{N}$; $\mathbb{Z}^+$; $\mathbb{Z}$; $\{n\in\mathbb{N}\mid n \text{ is even}\}$; $\mathbb{N}\times\mathbb{N}$; $\mathbb{N}\times\mathbb{N}\times\mathbb{N}$; $\mathbb{Q}$. - **Theorem 11**: the set of finite sequences of natural numbers is countable. - **Corollary 12**: each of the following is countable — the set of strings (of finite length); the set of integer arithmetic expressions; the set of polynomials with integer coefficients (整系数多项式); the set of algebraic numbers (代数数,整系数多项式的根). --- ## 9. Uncountable Sets and Cantor's Theorem - **Theorem 1 (Cantor's Theorem)**: for any set $X$, $\ X\not\approx\mathcal{P}(X)$. - **Proof by contradiction (Cantor's diagonal argument)**: suppose $\theta:X\to\mathcal{P}(X)$ is a bijection. Define $Y:=\{x\in X\mid x\notin\theta(x)\}\in\mathcal{P}(X)$. Let $y$ be the unique element with $\theta(y)=Y$. Then $y\in Y \Rightarrow y\notin\theta(y)=Y$, and $y\notin Y \Rightarrow y\in\theta(y)=Y$ — contradiction. - **Theorem 2**: $(A\to\{0,1\})\approx\mathcal{P}(A)$. Proof: $F(f)=\{a\in A\mid f(a)=1\}$ is a bijection (injective because $f$ is determined by which points map to $1$; surjective because any $X\subseteq A$ is hit by its indicator function). - **Corollary 3**: $\mathcal{P}(\mathbb{N})$ is uncountable; $(\mathbb{N}\to\{0,1\})$ is uncountable. - **Theorem 4**: the set of infinite sequences of natural numbers is uncountable. - Proof: an infinite sequence of naturals is a function $\mathbb{N}\to\mathbb{N}$, and $2^{\mathbb{N}}\leqslant\mathbb{N}^{\mathbb{N}}\leqslant(2^{\mathbb{N}})^{\mathbb{N}}\approx 2^{\mathbb{N}\times\mathbb{N}}\approx 2^{\mathbb{N}}$, so $\mathbb{N}^{\mathbb{N}}\approx 2^{\mathbb{N}}$ is uncountable. - **Theorem 5**: $\mathbb{R}\approx 2^{\mathbb{N}}$. - **Corollary 6**: $(0,1)\approx[0,1]\approx 2^{\mathbb{N}}$. - **Theorem 7**: $(\mathbb{R}\to\mathbb{R})\approx 2^{2^{\mathbb{N}}}$. - Proof: $\mathbb{R}^{\mathbb{R}}\approx(2^{\mathbb{N}})^{2^{\mathbb{N}}}\approx 2^{\mathbb{N}\times 2^{\mathbb{N}}}$, and $2^{2^{\mathbb{N}}}\leqslant 2^{\mathbb{N}\times 2^{\mathbb{N}}}\leqslant 2^{2^{\mathbb{N}}\times 2^{\mathbb{N}}}\approx 2^{(2^{\mathbb{N}})^2}\leqslant 2^{(2^{\mathbb{N}})^{\mathbb{N}}}\approx 2^{2^{\mathbb{N}\times\mathbb{N}}}\approx 2^{2^{\mathbb{N}}}$. - **Theorem 8**: the set of continuous functions from $\mathbb{R}$ into $\mathbb{R}$ is equinumerous with $\mathbb{R}$. --- ## 10. Set Theory as a Mathematical Foundation ### 10.1 Ordered pairs as sets - **Definition 1 (ordered pairs as sets)**: $(x,y)$ can be encoded as $\{\{x\},\{x,y\}\}$. - The encoding is sound because of: - **Theorem 2**: for any sets $x,y,u,v$, if $\{\{x\},\{x,y\}\}=\{\{u\},\{u,v\}\}$ then $x=u$ and $y=v$. ### 10.2 Natural numbers as sets - **Example 3 (natural numbers as sets)**: each natural number is encoded as the set of all smaller ones. | $n$ | as a set | $=\{0,\dots,n-1\}$ | |---|---|---| | $0$ | $\{\}$ | $\{\}$ | | $1$ | $\{\{\}\}$ | $\{0\}$ | | $2$ | $\{\{\},\{\{\}\}\}$ | $\{0,1\}$ | | $3$ | $\{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\}$ | $\{0,1,2\}$ | - **Definition 4 (inductive set)**: a set $x$ is **inductive** iff $\varnothing\in x$ and $\forall y(\text{if } y\in x \text{ then } y\cup\{y\}\in x)$. - **Definition 5 ($\mathbb{N}$)**: $\mathbb{N}$ is the **smallest inductive set**: (i) $\mathbb{N}$ is inductive; (ii) for any inductive set $x$, $\mathbb{N}\subseteq x$. - **Theorem 6 (existence of $\mathbb{N}$)**: there exists a set $x$ that is inductive and is contained in every inductive set. - **Theorem 7 (uniqueness of $\mathbb{N}$)**: any two sets that are inductive and contained in every inductive set are equal. ### 10.3 Defining natural-number arithmetic - **Definition 8 (addition)**: the sum of $n,m\in\mathbb{N}$ is $r$ iff $(n,m,r)\in T$, where $T\subseteq\mathbb{N}\times\mathbb{N}\times\mathbb{N}$ is the **least** set such that - $\forall n.\ ((n,0,n)\in T)$ — base case $n+0=n$; - $\forall n\forall m\forall r.\ (\text{if } (n,m,r)\in T, \text{ then } (n,\, m\cup\{m\},\, r\cup\{r\})\in T)$ — successor step on the **second** argument (using $m\cup\{m\}$ as $m+1$, i.e. $n+(m+1)=(n+m)+1$). ### 10.4 Defining transitive closures (as sets) - **Definition 9**: for any relation $R$ on $A$ (i.e. $R\subseteq A\times A$), write $(a,b)\in R^n$ iff $(a,b,n)\in T$, where $T\subseteq A\times A\times\mathbb{N}$ is the least set such that - $\forall a\forall b\,(\text{if } a\,R\,b, \text{ then } (a,b,1)\in T)$; - $\forall n\forall a\forall b\forall c\,(\text{if } a\,R\,b \text{ and } (b,c,n)\in T, \text{ then } (a,c,n\cup\{n\})\in T)$. - **Definition 10**: for any relation $R$ on $A$, $R^+=\bigcup_{n\in\mathbb{Z}^+}R^n$ is the set $\{(a,b)\in A\times A\mid \exists n((a,b,n)\in T)\}$, obtained by the axiom of separation from the $T$ above. ### 10.5 Establishing $\mathbb{Z}$, $\mathbb{Q}$ and $\mathbb{R}$ in set theory - $\mathbb{Z}\approx(\mathbb{N}\times\{0,1\})\setminus\{(0,0)\}$, so $\mathbb{Z}$ can be defined accordingly. - $\mathbb{Q}\approx\{(n,m)\in\mathbb{Z}\times(\mathbb{N}\setminus\{0\})\mid n \text{ and } m \text{ are coprime to each other}\}$, so $\mathbb{Q}$ can be defined accordingly. - **Definition 11 (Dedekind cut)**: $(X,Y)\in\mathcal{P}(\mathbb{Q})\times\mathcal{P}(\mathbb{Q})$ is a Dedekind cut of rationals if $X\neq\varnothing$; $Y\neq\varnothing$; $X\cap Y=\varnothing$; $X\cup Y=\mathbb{Q}$; $\forall x\in X.\ \forall y\in Y.\ (x - **Theorem 12**: if $D$ is the set of Dedekind cuts of rationals, then $D\approx\mathbb{R}$; so $\mathbb{R}$ can be defined accordingly. - Alternative construction of $\mathbb{R}$ via Cauchy sequences: - **Definition 13 (Cauchy sequence)**: $l:\mathbb{N}\to\mathbb{Q}$ is a Cauchy sequence if for any rational $\varepsilon>0$ there exists $N$ such that for any $m,n>N$, $|l(n)-l(m)|<\varepsilon$. - **Definition 14**: $R_C=\{(l_1,l_2)\mid \text{for any rational } \varepsilon>0 \text{ there exists } N \text{ such that for any } n>N,\ |l_1(n)-l_2(n)|<\varepsilon\}$ is a relation between Cauchy sequences of rationals. - **Theorem 15**: $R_C$ is an equivalence relation on Cauchy sequences of rationals. - **Theorem 16**: $\mathbb{R}\approx\{[l]_{R_C}\mid l \text{ is a Cauchy sequence of rationals}\}$. - Finally, since $\mathbb{C}\approx\mathbb{R}\times\mathbb{R}$, $\mathbb{C}$ can be defined accordingly. --- ## 11. Problems of Naive Set Theory and Their Fixing ### 11.1 Russell's paradox - Consider $A=\{a\mid a\notin a\}$. Then $\forall x(x\in A \Leftrightarrow x\notin x)$, so $A\in A \Leftrightarrow A\notin A$ — a contradiction. ### 11.2 Fixing the problems — primitive constructions of sets - **Definition 17 (primitive constructions)**: - **Separation**: for any set $A$ and property $P$, $\{a\in A\mid P(a)\}$ is a set, with $\forall x(x\in\{a\in A\mid P(a)\} \Leftrightarrow x\in A \text{ and } P(x))$. - For an arbitrary property $P$, $\{a\mid P(a)\}$ is **not** guaranteed to be a set (this is what blocks Russell's paradox). - $\varnothing$ is a set, $\forall x(x\notin\varnothing)$. - **Pairing**: for any sets $x,y$, $\{x,y\}$ is a set, $\forall z(z\in\{x,y\} \Leftrightarrow z=x \text{ or } z=y)$. - **Union**: for any set $x$, $\bigcup x$ is a set, $\forall y(y\in\bigcup x \Leftrightarrow \exists z(z\in x \text{ and } y\in z))$. - **Power set**: for any set $x$, $\mathcal{P}(x)$ is a set, $\forall y(y\in\mathcal{P}(x) \Leftrightarrow y\subseteq x)$. - **Theorem 18**: $x\cup y$ is a set, since $x\cup y=\bigcup\{x,y\}$. - **Theorem 19**: $x\cap y$ is a set, since $x\cap y=\{a\in x\mid a\in y\}$. - **Theorem 20**: $\{x\}$ is a set, since $\{x\}=\{x,x\}$. - **Corollary 21**: $0=\{\}$, $1=\{\{\}\}$, $2=\{\{\},\{\{\}\}\}$ are all sets; and if $x$ is a set, $x\cup\{x\}$ is also a set. - **Theorem 22**: $x\times y$ is a set, since $x\times y=\{a\in\mathcal{P}(\mathcal{P}(x\cup y))\mid \exists u\in x\,\exists v\in y.\ a=\{\{u\},\{u,v\}\}\}$.