# 离散数学 · 集合、关系、函数与基数 · 速览 > Arietids Learn · 个人课程复习笔记 > 在线阅读：https://learn.arietids.net/courses/discrete-math/chapter-03-quick/ ## Sets (N518) - Core constructions by their defining equivalence: $z\in x\cup y \Leftrightarrow (z\in x \text{ or } z\in y)$; $z\in x\cap y \Leftrightarrow (z\in x \text{ and } z\in y)$; $z\in x\setminus y \Leftrightarrow (z\in x \text{ and } z\notin y)$; $y\in\mathcal{P}(x)\Leftrightarrow y\subseteq x$; $y\in\bigcup x \Leftrightarrow \exists z(z\in x \wedge y\in z)$. - $x=y \Leftrightarrow (x\subseteq y \text{ and } y\subseteq x)$ (extensionality); pair $(x,y)=(u,v)\Leftrightarrow x=u\wedge y=v$; $x\times y=\{(u,v)\mid u\in x, v\in y\}$. - Key identities (proved by double inclusion): $\mathcal{P}(A)\cap\mathcal{P}(B)=\mathcal{P}(A\cap B)$; $A=\bigcup\mathcal{P}(A)$; $A\times\bigcup B=\bigcup\{A\times X\mid X\in B\}$; monotonicity $A\subseteq B\Rightarrow \mathcal{P}(A)\subseteq\mathcal{P}(B)$ and $\bigcup A\subseteq\bigcup B$. - Method: prove $S=T$ via $S\subseteq T$ and $T\subseteq S$; prove inclusion by taking an arbitrary element and unfolding membership. ## Relations (N520) - Relation on $A$ = subset of $A\times A$; $a\,R\,b \Leftrightarrow (a,b)\in R$. Properties: reflexive $\forall a.\,aRa$; symmetric; antisymmetric $aRb\wedge bRa\Rightarrow a=b$; transitive. - Operators: $R^{-1}=\{(x,y)\mid y\,R\,x\}$; $S\circ R=\{(x,z)\mid \exists y(xRy\wedge ySz)\}$. Facts: $(S\circ R)^{-1}=R^{-1}\circ S^{-1}$; $\circ$ associative; $R\circ(S\cup T)=(R\circ S)\cup(R\circ T)$. - **Theorem 8 (characterizations)**, $I_A=\{(a,a)\}$: reflexive $\Leftrightarrow I_A\subseteq R$; symmetric $\Leftrightarrow R=R^{-1}$; transitive $\Leftrightarrow R\circ R\subseteq R$; antisymmetric $\Leftrightarrow R\cap R^{-1}\subseteq I_A$. ## Equivalence relations & partitions (N520–N525) - Equivalence relation = reflexive + symmetric + transitive; class $[a]_R=\{b\mid aRb\}$. - $aRb \Leftrightarrow [a]_R=[b]_R \Leftrightarrow [a]_R\cap[b]_R\neq\varnothing$. - Partition of $A$: nonempty, pairwise disjoint blocks with $\bigcup P=A$. Each partition induces an equivalence relation ("same block"), whose classes are exactly the blocks. ## Closures (N601) - **Transitive closure**: two equivalent definitions — (universal) smallest transitive $R'\supseteq R$; (constructive) $R^+=\bigcup_{n\in\mathbb{Z}^+}R^n$ with $R^1=R$, $R^{n+1}=R^n\circ R$. - Key lemmas: $R^n\circ R^m=R^{n+m}$; $R^+$ transitive; if $R\subseteq T$ and $T$ transitive then $R^+\subseteq T$ (induction $R^{n+1}=R^n\circ R\subseteq T\circ T\subseteq T$). - **Reflexive transitive closure**: $R^*=\bigcup_{n\in\mathbb{N}}R^n$ with $R^0=I_A$ (= add the identity). ## Functions (N601) - $F:A\to B$ is a relation that is total ($\forall x\,\exists y\,xFy$) and single-valued; $F(x)$ = the unique image. $F=G \Leftrightarrow \forall x.\,F(x)=G(x)$. - $(F\circ G)(x)=F(G(x))$. injection $f(a)=f(a')\Rightarrow a=a'$; surjection $\forall b\,\exists a.\,f(a)=b$; bijection = both. - Composition ($F:B\to C$, $G:A\to B$): $F,G$ inj $\Rightarrow F\circ G$ inj; $F,G$ surj $\Rightarrow F\circ G$ surj; $F\circ G$ inj $\Rightarrow G$ inj; $F\circ G$ surj $\Rightarrow F$ surj. Bijection $\Rightarrow F^{-1}$ bijection. ## Schröder–Bernstein (N603) - Injections $f:A\to B$, $g:B\to A$ $\Rightarrow$ a bijection $A\to B$. - Construction: $C_0=A\setminus\mathrm{ran}(g)$, $C_{n+1}=\{g(b)\mid b\in D_n\}$, $D_n=f[C_n]$; set $h=f$ on $\bigcup C_i$, $h=g^{-1}$ off it. Injectivity needs three cases (both in $\bigcup C_i$, mixed, both off). ## Equinumerosity (N603, N608) - $A\leqslant B$: injection exists; $A\approx B$: bijection exists. $\approx$ is reflexive/symmetric/transitive. - $[0,1]\approx[0,1)$; $\mathbb{N}\approx\mathbb{N}\times\mathbb{N}\approx\mathbb{Q}$; $\mathbb{N}\times\mathbb{N}\times\mathbb{N}\approx\mathbb{N}$. Products: $A\times B\approx B\times A$; $A_1\approx A_2$ and $B_1\approx B_2 \Rightarrow A_1\times B_1\approx A_2\times B_2$. - Function-space identities ($2^A=(A\to\{0,1\})$, $B^A=(A\to B)$): 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$; $(A\to\{0,1\})\approx\mathcal{P}(A)$ (indicator map); $A\approx B\Rightarrow\mathcal{P}(A)\approx\mathcal{P}(B)$. ## Countable / Uncountable (N603, N615) - Countable := $\approx\mathbb{N}$. Countable: $\mathbb{Z}$, $\mathbb{Q}$, $\mathbb{N}^k$, finite sequences/strings of naturals, integer polynomials, algebraic numbers. - **Cantor**: $X\not\approx\mathcal{P}(X)$ (diagonal $Y=\{x\mid x\notin\theta(x)\}$). $(A\to\{0,1\})\approx\mathcal{P}(A)$, so $\mathcal{P}(\mathbb{N})$, $\mathbb{N}^{\mathbb{N}}\approx 2^{\mathbb{N}}$ are uncountable. - Continuum: $\mathbb{R}\approx 2^{\mathbb{N}}\approx(0,1)\approx[0,1]$; $(\mathbb{R}\to\mathbb{R})\approx 2^{2^{\mathbb{N}}}$; continuous $\mathbb{R}\to\mathbb{R}$ functions $\approx\mathbb{R}$. ## Set theory as foundation (N617) - Everything is a set: pair $(x,y)=\{\{x\},\{x,y\}\}$ (sound by pair-equality theorem); naturals $0=\{\}$, $n+1=n\cup\{n\}$; $\mathbb{N}$ = smallest inductive set (inductive: $\varnothing\in x$, $y\in x\Rightarrow y\cup\{y\}\in x$); exists and is unique. - Addition by least $T\subseteq\mathbb{N}^3$: base $(n,0,n)$ ($n+0=n$), step $(n,m,r)\Rightarrow(n,m\cup\{m\},r\cup\{r\})$ (recursion on 2nd arg). Transitive closure similarly via least $T\subseteq A\times A\times\mathbb{N}$. - $\mathbb{Z}\approx(\mathbb{N}\times\{0,1\})\setminus\{(0,0)\}$; $\mathbb{Q}\approx$ coprime pairs $(n,m)\in\mathbb{Z}\times(\mathbb{N}\setminus\{0\})$; $\mathbb{R}$ = Dedekind cuts ($D\approx\mathbb{R}$) or Cauchy-sequence classes; $\mathbb{C}\approx\mathbb{R}\times\mathbb{R}$. ## Naive set theory's problem & fix (N617) - **Russell's paradox**: $A=\{a\mid a\notin a\}\Rightarrow A\in A\Leftrightarrow A\notin A$. - Fix = restrict comprehension to **separation** $\{a\in A\mid P(a)\}$ (a set), while bare $\{a\mid P(a)\}$ is **not** guaranteed a set. Primitives: $\varnothing$, pairing $\{x,y\}$, union $\bigcup x$, power set $\mathcal{P}(x)$. Derived as sets: $x\cup y=\bigcup\{x,y\}$, $x\cap y=\{a\in x\mid a\in y\}$, $\{x\}=\{x,x\}$, $x\times y\subseteq\mathcal{P}(\mathcal{P}(x\cup y))$.