势与可数集

对于一个集合$A$$A$,如果它是由有限个元素组成的,则称$A$$A$为有限集合,简称有限集。

对于一个有限集$A$$A$来说,通常把$A$$A$中不同元素的个数称为$A$$A$的势,用$|A|$$|A|$来表示。

若$A$$A$中包含$m$$m$个不同元素,记$|A|=m$$|A|=m$,也称$A$$A$为$m$$m$元集。

例如：$A=\{1,2,3,a,b,c\}$$A=\{1,2,3,a,b,c\}$, $|A|=6$$|A|=6$, $A$$A$是6元集。

不是有限集合的集合称为无限集合,简称无限集。

设有集合$A$$A$与$B$$B$，如果存在一个从$A$$A$到$B$$B$的双射函数$f:A\to B$$f:A{\rightarrow}B$，那么称$A$$A$与$B$$B$等势（Equinumerous）, 记作$A\sim B$$A{\sim}B$.

求证:（Galileo）自然数集$N$$N$与非负偶数集$M$$M$等势。

证明： $N$$N$与$M$$M$之间存在一个双射函数: $f(n)=2n$$f(n) = 2n$ 所以$N\sim M$$N{\sim}M$.

求证：自然数集$N$$N$与整数集$Z$$Z$是等势的。

证明： 将$N$$N$和$Z$$Z$的元素按下列顺序排列,可以得到一一对应关系: $N:01234\cdots n\cdots$$N:0\,\,1\,\,2\,\,3\,\,4\,\,{\cdots}\,\,n\,\,{\cdots}$ $Z:0-11-22\cdots f(n)\cdots$$Z :\,\,0\,\,-1\,\,1\,\,-2\,\, 2\,\,{\cdots}\,\,f(n)\,\,{\cdots}$ 其中

显然$f$$f$是双射函数,因此$N\sim Z$$N{\sim}Z$.

设$R$$R$是实数集合,$S$$S$是$R$$R$的子集, 且$S=\{x|x\in R,0<x<1\}$$S = \{ x | x {\in}R , 0 <x<1 \}$, 试证明$S\sim R$$S{\sim}R$.

证明：令 $f:S\to R$$f:S{\rightarrow}R$

$f(x)=tg(\pi x-\frac{\pi }{2})$$f(x) = tg({\pi}x-\tfrac{\pi}{2})$ $(0<x<1)$$(0<x<1)$

显然，$f$$f$的值域是$R$$R$，且$f$$f$是双射函数，所以$S\sim R$$S{\sim}R$.

或令$f:R\to S$$f:R{\rightarrow}S$,

$f(x)=\frac{1}{\pi }t{g}^{-1}x+\frac{1}{2}$$f(x) =\tfrac{1}{\pi}tg^{-1}x + \tfrac{1}{2}$ $(-\mathrm{\infty }<x<\mathrm{\infty })$$( -\infty<x<\infty)$，$f$$f$的值域是$S$$S$. 显然$f$$f$是双射函数，所以$S\sim R$$S{\sim}R$.

定理:集合族上的等势关系是一个等价关系。

证明:设集合族为$S$$S$, $R=\{⟨A,B⟩|A,B\in S\wedge A\sim B\}.$$R=\{{\langle}A,B{\rangle}|A,B{\in}S{\wedge}A{\sim}B\}.$

(1)对于任意$A\in S$$A{\in}S$，必有$A\sim A$$A{\sim}A$，所以$⟨A,A⟩\in R$${\langle}A,A{\rangle}{\in}R$.

(2)对于任意$A,B\in S$$A,B{\in}S$，若$⟨A,B⟩\in R$${\langle}A,B{\rangle}{\in}R$，即$A\sim B$$A{\sim}B$，则必有$B\sim A$$B{\sim}A$，所以$⟨B,A⟩\in R$${\langle}B,A{\rangle}{\in}R$.

(3)对于任意$A,B,C\in S$$A,B,C{\in}S$，若$⟨A,B⟩,⟨B,C⟩\in R$${\langle}A,B{\rangle},{\langle}B,C{\rangle}{\in}R$，即$A\sim B$$A{\sim}B$且$B\sim C$$B{\sim}C$，则必有$A\sim C$$A{\sim}C$，即$⟨A,C⟩\in R$${\langle}A,C{\rangle}{\in}R$.

求证：自然数集合$N$$N$是无限集合。

证明：设$m$$m$是$N$$N$中的任意元素, $f$$f$是任意从$N_m=\{1,2,3,\cdots ,m\}$$N_m= \{1,2,3,{\cdots},m\}$到$N$$N$的函数。

$f:\{1,2,3,\cdots ,m\}\to N$$f :\{1,2,3,{\cdots},m\} {\rightarrow} N$

设$k=1+max\{f(1),f(2),\cdots ,f(m)\}$$k = 1 + max\{ f(1),f(2),{\cdots} ,f(m) \}$

显然，$k\in N$$k{\in}N$.

但对每一个$x\in \{1,2,\cdots ,m\}$$x{\in}\{1,2,{\cdots} ,m\}$,有$f(x)\ne k$$f(x) {\neq} k$,

因此$f$$f$不是满射的,所以$f$$f$不是双射函数。

因为$m$$m$和$f$$f$都是任意的,故$N$$N$是无限集合。

求证：区间[0,1]与区间(0,1)等势。

证明：设集合$A=\{0,1,1/2,\cdots ,1/n,\cdots \}$$A=\{0,1,1/2,{\cdots},1/n,{\cdots}\}$， 显然，$A\subseteq [0,1]$$A\subseteq[0,1]$.

定义$f:[0,1]\to (0,1)$$f:[0,1]\rightarrow(0,1)$，使得:

则$f$$f$是双射函数。

所以，区间[0,1]与区间(0,1)等势。

定义：与自然数集合的子集等势的集合称可数集。可数集可以是有限集。不是可数集的无限集合称不可数集。

例：$A=\{1,4,9,16,\cdots ,n^2,\cdots \}$$A=\{1,4,9,16,{\cdots},n^2,{\cdots}\}$ $B=\{3,12,27,\cdots ,3n^2,\cdots \}$$B=\{3,12,27,{\cdots},3n^2,{\cdots}\}$ $C=\{1,1/2,1/3,\cdots ,1/n,\cdots \}$$C=\{1,1/2,1/3,{\cdots},1/n,{\cdots}\}$ 都是可数集。

而$R$$R$、[0,1]是不可数集。

定理：$A$$A$为无限可数集合的充要条件是$A$$A$可以排列成： $A=\{a_0,a_1,a_2,\cdots ,a_n,\cdots \}$$A=\{a_0,a_1,a_2,{\cdots},a_n,{\cdots}\}$.

证明：(充分性)如果$A$$A$​可以排列成上述形式，那么将$A$$A$​的元素$a_n$$a_n$​与足标$n$$n$​对应，就得到$A$$A$​与$N$$N$​之间一一对应关系$n\leftrightarrow a_n$$n {\leftrightarrow} a_n$​，即$A$$A$​与$N$$N$​等势，故$A$$A$​是无限可数集。

(必要性)若$A$$A$是无限可数集,则在$A$$A$与$N$$N$之间存在一一对应关系$f$$f$,由$f$$f$得到$n$$n$的对应元素$a_n$$a_n$: $f(n)\to a_n$$f(n){\rightarrow}a_n$ 即$A$$A$可写成$\{a_0,a_1,a_2,\cdots ,a_n,\cdots \}$$\{a_0,a_1,a_2,{\cdots},a_n,{\cdots}\}$的形式。

定理：任意无限集必含可数子集。

证明：设$A$$A$为无限集合, 从$A$$A$中取出一个元素$a_0$$a_0$.

由于$A$$A$是无限的,不会因为取出$a_0$$a_0$而成为空集。 所以,可从$A-\{a_0\}$$A-\{a_0\}$中取出元素$a_1$$a_1$.

同样$A-\{a_0,a_1\}$$A-\{a_0,a_1\}$也是非空集, 又可从中取出元素$a_2,\cdots$$a_2,{\cdots}$.

如此继续下去,就得到$A$$A$的可数子集: $\{a_0,a_1,\cdots ,a_n\cdots \}.$$\{a_0,a_1,{\cdots},a_n{\cdots}\}.$

定理：任意无限可数集必与其某一真子集等势。

证明:设$M$$M$为无限可数集,则$M$$M$必含有无限可数子集 $A=\{a_0,a_1,\cdots ,a_n,\cdots \},$$A=\{a_0,a_1,{\cdots},a_n,{\cdots}\},$ 设$B=M-A$$B=M-A$,$C=M-\{a_0\}$$C=M-\{a_0\}$, 显然$C\subset M$$C{\subset}M$.

现构造$f:M\to C$$f:M{\rightarrow}C$,使得

这个$f$$f$是双射的,所以$M\sim C$$M{\sim}C$.

定理：可数个两两不相交的可数集合的并集,仍然是一可数集。

证明：设可数个可数集分别是 $S_1=\{a_{11},a_{12},a_{13},\cdots ,a_{1n},\cdots \}$$S_1=\{a_{11},a_{12},a_{13},{\cdots},a_{1n},{\cdots}\}$ $S_2=\{a_{21},a_{22},a_{23},\cdots ,a_{2n},\cdots \}$$S_2=\{a_{21},a_{22},a_{23},{\cdots},a_{2n},{\cdots}\}$ $S_3=\{a_{31},a_{32},a_{33},\cdots ,a_{3n},\cdots \}$$S_3=\{a_{31},a_{32},a_{33},{\cdots},a_{3n},{\cdots}\}$ $\cdots$${\cdots}$ 令$S=S_1\cup S_2\cup S_3\cup \cdots$$S=S_1{\cup}S_2{\cup}S_3{\cup}{\cdots}$, 对$S$$S$的元素按以下方式排列:

在上述排列中, 由左上端开始, 其每一斜线上的每一元素的两下标之和都相同, 分别为:$2,3,4,\cdots$$2,3,4,{\cdots}$​, 各斜线上元素的个数分别为:$1,2,3,4,\cdots$$1,2,3,4,{\cdots}$, 故$S$$S$的元素可排列成:$a_{11},a_{21},a_{12},a_{31},a_{22},a_{13},\cdots ,$$a_{11},a_{21},a_{12},a_{31},a_{22},a_{13},{\cdots},$​ 它仍然是一可数集。