离散数学 · 集合、关系、函数与基数 · 速览

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.

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

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).

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

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).

$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 := $\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}$ .

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

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