集合是基本的概念，不予定义，将集合理解为一个包含多个的整体.

属于 \(x\in A\) ，不属于 \(x\notin A\) .

罗素悖论： \(\{x:x\notin x\}\) .

分离模式： 设 \(X\) 是集合 ， \(\{x\in X:P(x)\}\) ；进而可以定义空集： \(\emptyset=\{x\in X:x\neq x\}\) .

包含（于） \(\supset(\subset)\) 或者 \(\supseteq(\subseteq)\) ，真包含（于） \(\supsetneq(\subsetneq)\) . 相等 \((A=B)\Leftrightarrow \forall x(x\in A\Leftrightarrow x\in B)\Leftrightarrow A\subset B\wedge B\subset A\) .

幂集 \(\mathcal{P}(A)=\{X:X\subset A\}\) . 只含有一个元素的集合称为单点集.

运算：并 \(\cup\) ；交 \(\cap\) ；差 \(A\backslash B\) （或者记作 \(A-B\) ）；如果 \(A\subset X\) ，称 \(X\backslash A\overset{def}{=}A^c\) 为 \(A\) 关于 \(X\) 的补集 ；

集合 \(A,B\) 的乘积（或笛卡尔积 Cartesian Product、卡式积，对积）. 记为： \(A\times B=\{(a,b):a\in A,b\in B\}\) . 对于有序对 \((a,b)\) 或可以记作 \(\{a,\{b\}\}\) 或 \(\{\{a\},\{a,b\} \}\) （用后者），其具有性质： \((a,b)=(c,d)\Leftrightarrow (a=c)\wedge (b=d)\) ；此外有 \(\emptyset \times A=A\times \emptyset=\emptyset\) .

并可以将乘积推广到多个集合，直积：

对称差： \(A\Delta B=(A\backslash B)\cup(B\backslash A)\) ，有结论：

分配律：

De Morgan律：

积的分配律：

用特征函数刻画集合运算：

可以用集合定义两个元素之间的关系. 设集合 \(S\subset A\times B\) . 如果 \((a,b)\in S\) 则称 \(a,b\) 之间关于存在由 \(S\) 定义的关系，记为 \(a\sim b\) 或者 \(aRb\) .

对偶关系

设 \(a,b\) 之间存在关系 \(R\) ，其由集合 \(S=\{(a,b):a\in A,b\in B\}\) 定义. 考虑集合 \(S^{op}=\{(b,a):a\in A',b\in B'\}\) ，如果 \((b,a)\in S^{op}\) ，则记由 \(S^{op}\) 定义的关系为 \(R^{op}\) ，记为 \(aR^{op}b\) .

复合关系

考虑关系 \(R,S\) ，记 \(S\circ R=\{(a,c):\exists b(aSb\wedge bRc)\}\)

映射描述的是从集合 \(X\) 到集合 \(Y\) 的一个对应关系，单射、满射和双射是特殊的映射.

此外还有一些特殊的映射： \(1_X:X\rightarrow X,x\mapsto x\) 称为 \(X\) 上的恒等映射；设 \(A\subset X,i:A\rightarrow X:x\mapsto x\) 称为 \(A\) 在 \(X\) 中的含入映射. 特征函数或指示函数：

例如，对于 \(\mathbb{Q}\subset \mathbb{R},\chi_\mathbb{Q}\) 为一特征函数，也即为Dirichlet函数.

证明： i) ：如果 \(x\in\varlimsup_{n\rightarrow \infty}A_n\) ，则 \(\forall n\geq1,x\in \bigcup_{k=n}^\infty A_n\) ， 则存在 \(k_1\geq n,x\in A_{k_1}\) ，依次类推可以得到 \(k_11\\ &1-\sqrt{x},0\leq x\leq1 \end{aligned}\right.\]

则 \(g:[0,+\infty)\rightarrow [0,+\infty)\) ，则 \(f\circ g=1_Y\) ，而 \(g\circ f\left(\frac{3}{2}\right)=\frac{1}{2}\) .

此外对于 \(f:X\rightarrow Y\) ，还可以定义 \(Y\) 的原像： \(f^{-1}(Y)=\{x\in X:f(x)\in Y\}\)

\(A\subset f^{-1}(f(A)),B\supset f(f^{-1}(B))\) .

\(f^{-1}\left(\bigcup_{\lambda \in \Lambda}A_\lambda\right)=\bigcup_{\lambda\in \Lambda}f^{-1}(A_\lambda)f^{-1}\left(\bigcap_{\lambda \in \Lambda}A_\lambda\right)=\bigcap_{\lambda\in \Lambda}f^{-1}(A_\lambda),\)

\(\left(f^{-1}(A)\right)^c=f^{-1}(A^c)\)

注意： \(f\left(\bigcap_{\lambda\in \Lambda}A_\lambda\right)\subset \bigcap_{\lambda\in \Lambda}f(A_\lambda)\)

反例以及对于 \(f\) 是单射为上式取等的充分条件

包含关系是显然的. 对于反例，可以取一非单射的 \(f\) ：

下面证明取等的充分条件为 \(f\) 为单射.

用势（cardinality）衡量两个集合的大小，考虑集合 \(A,B\) ，如果 \(A\) 与 \(B\) 等价（存在双射），则记 \(\lvert A\rvert=\lvert B\rvert\) ；如果 \(A\) 与 \(B\) 的一个子集等价，则记 \(\lvert A\rvert\leq \lvert B\rvert\) . 在此基础上，如果 \(B\) 不与 \(A\) 中的任何一个子集等价，则记 \(\lvert A\rvert\frac{1}{n}\}\) #imcomplete-whatever

\(\mathbb{N},\mathbb{Z},\mathbb{Q},\mathbb{N}\times \mathbb{N},\mathbb{Z}\times \mathbb{Z}\) 等都是可数集. 例如： \(\mathbb{Q}\) ，考虑 \(A_n=\{\frac{m}{n}\:m\geq1\},A_n\sim \mathbb{N}\) . 从而 \(\mathbb{Q}^+=\bigcup_{n\geq1}A_n\sim \mathbb{N}\) 同理 \(\mathbb{Q}^-\sim \mathbb{N}\) 从而 \(\mathbb{Q}\sim \mathbb{N}\)（因为 \(\mathbb{Q}\) 不是有限集）.

考虑到 \(A\cup B=A\cup (B\backslash A)\) . 设 \(C=B\backslash A\) ， \(A\cap C=0\) ， \(C\subset B\) 为至多可数集，因为 \(A\) 是无限集，所以存在 \(A_1\subset A\) 为可数集，从而 \(A_1\cup C\) 为可数集，因此 \((A_1\cup C)\sim A_1\) ，又显然 \((A-A_1)\sim (A-A_1)\) ，且 \((A_1\cup C)\cap (A-A_1)=\emptyset,(A_1)\cap (A-A_1)=\emptyset\) ，从而不难构造双射，进而有 \(A\cup C=(A-A_1)\cup (A_1\cup C)=(A\cup C)\sim A=(A-A_1)\cup A_1\) .

进而有下推论：

之前已经证明了 \(\mathbb{R}\) 中的所有开区间等价. 从而对于 \([a,b]=(a,b)\cup \{a,b\}\) 由 \(\{a,b\}\) 为至多可数集即可推出其与 \((a,b)\) 等价，同理等价于 \([a,b),(a,b]\) . ^RAllEqual

阿列夫数

\(\lvert \mathbb{N}\rvert=\aleph_0\)

\(\lvert\mathcal{P}(\mathbb{N})\rvert=2^{\aleph_0}\)

其中 \(2^{\aleph_0}=\{0,1\}^{\mathbb{N}}\) 表示所有 \(\mathbb{N}\rightarrow\{0,1\}\) 的函数的集合.

\(\lvert \mathcal{P}(\mathcal{P}(\mathbb{N}))\rvert=2^{2^{\aleph_0}}\) .

证明：任取 \(x_1,x_2\) ，设映射

其中 \(d_1,d_2\) 分别为 \(d(x,x_1),d(x,x_2)\) ， \(d\) 为欧式距离度量. 如果若 \(f(x)=f(x'),x\neq x'\) 即 \(d_1=d_1',d_2=d_2'\) ，则 \(x,x'\) 为以 \(x_1\) 为圆心的圆与以 \(x_2\) 为圆心的圆的交上. 又因为空间中的两个圆或者重合，或者至多相交两个点. 由圆心 \(x_1\neq x_2\) 可知这两个圆不可能重合，从而至多相交两个点，如果如果只相交于一个点，则 \(x=x'\) ，矛盾，因此只可能是相交于两个点. 定义映射 \(g:E\rightarrow \{0,1\}\) ，并且满足若 \(\exists x,x':f(x)=f(x'),g(x)+g(x')=1\) ，若不存在 \(x,x':f(x)=f(x'),g(x)=0\) ，从而建立了 \(E\) 到 \(F=\{(d_1,d_2,g(x):x\in E\}\subset\mathbb{Q}\times \mathbb{Q}\times \mathbb{Q}\) 的一个双射. 对于任意的 \(y=(h_1,h_2,h_3)\in F\) ，首先由 \((h_1,h_2)\) 对应于 \(E\) 中至多两个点，至少一个点，并且由 \(h_3\) 可以确定 \(E\) 中的唯一点，所以该映射为满射；其次由构造规则可知该映射为单射. 综上 \(E\) 至多可数.

证明：在下面已经证明了有限 \(n\) 元数列（只有有限个数非 \(0\) ）是可数集. 对于任意有理系数多项式，可将其对应于一有限的 \(\mathbb{Q}\) 上的数列，并进一步映射为有限 \(n\) 元数列：

\(\(a_0+a_1x+a_2x^2+\cdots+a_nx^n+0x^{n+1}+\cdots\)\) 将其映射为 \(m_0,n_0,m_1,n_1,\cdots,m_n,n_n,0,\cdots\) ，记该映射为 \(\mathcal{L}\) ，其中 \((m_i,n_i)=1,a_i=\frac{m_i}{n_i}\) 或者 \(m_i=n_i=0\) 若 \(a_i=0\) ，因此对于多项式 \(f(x),g(x)\) ，如果 \(f(x)=g(x)\) ，则 \(a_i=b_i,\cdots\) ，显然 \(\mathcal{L}\) 是双射.

记全体有理系数多项式 \(\mathcal{F}\) ，则 \(\mathcal{L}(\mathcal{F})=\bigcup_{k\geq1}\{m_0,n_0,\cdots,m_k,n_k,\cdots:m_k,n_k\neq 0\}\) ，显然 \({m_0,n_0,\cdots,m_k,n_k,\cdots:m_k,n_k\neq 0\}\) 为有限个正整数集的积从而可数，而可数个可数集的并仍然为可数集，所以 \(\mathcal{L}(\mathcal{F})\) 可数，从而 \(\mathcal{F}\) 可数.

（或者，直接将 \(\mathcal{F}\) 对应于可数个 \(\mathbb{Q}\) 的乘积.）

前面讨论的可数集具有的势是一种特殊的势，一般称 \(A\sim \mathbb{N}\) ，则 \(\lvert A\rvert=a\) . 对于与 \(\{1,2,\cdots,n\}\) 等价的集合 \(A\) ，记 \(\lvert A\rvert=n\) ，下面考虑的是 \(\mathbb{R}\) 的势.

证明：反证：假设 \([0,1]=\{a_n\}_{n\geq1}\) ，取不包含 \(a_1\) 的闭区间 \(A_1\) ，满足 \(l(A_1)\leq \frac{1}{2}\) ，在 \(A_1\) 中取不包含 \(a_2\) 的闭区间 \(A_2:l(A_2)\leq \frac{1}{2^2}\) ，依次类推，从而得到闭区间套： \(\(A_1\supset A_2\supset \cdots \supset A_n\supset \cdots\)\) ，从而有 \(a=\bigcap_{n\geq1}A_n\) ， \(a\notin \{a_n\}_{n\geq1}=[0,1]\) 矛盾.

称与 \([0,1]\) 等价的集合具有连续统势. 或记作 \(\lvert A\rvert=c\) . 由上结论，可以得到 \(\mathbb{R}\) 中的所有区间均具有连续统势.

下面进一步讨论具有连续统势的集合. 首先引入n元数列：由 \(0,1,\cdots,n-1\) 组成的数列. 有限n元数列则包含有限个不为 \(0\) 的项，无限n元数列则有无限个不为 \(0\) 的项.

特别的， \(2\) 元数列可以视为对于某一集合进行指示函数的结果，例如 \(\mathbb{Q}\times \mathbb{Q}\) 的一个子集 \(A\) 可以被表示为二元数列 \(\chi_A(\mathbb{Q})\) ，相当于 \(\chi_A(\mathbb{N})\) ，从而可以建立 \(\mathcal{P}(\mathbb{Q},\mathbb{Q})\) 到二元数列全体的一个双射. 下面讨论一般的 \(n\) 元数列.

首先考虑有限 \(n\) 元数列全体 \(B\) ，该集合显然是至多可数集（可数个至多可数集）. 下面考虑无限 \(n\) 元数列全体 \(C\) .

考虑集合 \((0,1]\) ，对于任意 \(x\in(0,1]\) ，首先将 \((0,1]\) 分成 \(\{(\frac{k-1}{n},\frac{k}{n}]\}_{1\leq k\leq n}\) ，随后取 \(k_1-1:x\in (\frac{k_1-1}{n},\frac{k_1}{n}]\) ，下面对于 \((\frac{k_1-1}{n},\frac{k_1}{n}]\) 进行相同的划分，然后取 \(k_2,\cdots,k_n,\cdots\) ，从而建立了从 \((0,1]\) 到 \(C\) 的映射，并且有 \(x=\sum\limits_{i=1}^{\infty}\frac{k_i-1}{n^i}\)

首先证明 \(f\) 为单射：若 \(x\neq x'\) ，则存在 \(M\) ，当 \(m>M\) 时有 \(\frac{1}{n^m} x}f(r),f^{-}(x)=\sup_{r0,E\cap(x-\delta,x+\delta)\) 不可数的 \(x\) 的全体是不可数集.

证明： 两个命题的证明很类似：

对于第一个命题，用反证法即可，最终矛盾在于 \(E=\bigcup_{x\in E}[E\cap (r_x,R_x)]\) 是至多可数集.

对于第二个命题，假设满足条件的 \(x\) 的全体 \(X\) 为至多可数集. 设 \(I\subset \mathbb{N},X=\{x_i\}_{i\in I}\) ，则考虑 \(E-X\) ，从而对于任意的 \(x'\in E-X\) ，存在 \(\delta_{x'}>0\) ， \(E\cap(x'-\delta_{x'},x'+\delta_{x'})\) 为可数集. 并且可知 \(\forall x\in X,x\notin(x'-\delta_{x'},x'+\delta_{x'})\) ，而 \(E\backslash X=\bigcup_{x'\in E\backslash X}E\cap(x'-\delta_{x'},x'+\delta_{x'})\) 一定是不可数集合，又显然对于任意的 \((x'-\delta_{x'},x'+\delta_{x'})\) ，一定存在有理数 \(r_{x'}