初等數(shù)學(xué)O 集合論基礎(chǔ) 第二節(jié) 映射與集合的勢

這一節(jié)的目標(biāo)是基于映射建立比較集合“大小”的工具——集合的勢(cardinality)，也被稱為集合的基數(shù)，這個(gè)工具是自然數(shù)的基數(shù)理論的基礎(chǔ)。

---

定義0.6 映射 $X,Y$是兩個(gè)非空集合，稱$f:X\to Y$是一個(gè)映射，如果
$$?x\in X,?!y\in Y,f(x)=y$$

稱$X$為原像空間，$Y$為像空間，$f(X)$是值域，$f^{?1}(A)$是集合$A$的拉回(pre-image)，$?A?f(X)$
$$\begin{gathered} f(X)=\{y\in Y:?x\in X,f(x)=y\} \\ {f}^{?1}(A)=\{x\in X:f(x)=y,y\in A\} \end{gathered}$$

根據(jù)值域與拉回的定義，我們可以直接獲得下面的恒等式
$$f^{?1}(f(X))=X$$

用逐個(gè)元素的方式表述單射、滿射、雙射：

稱$f:X\to Y$是一個(gè)單射，如果
$$?x_1,x_2\in X,x_1=x_2?f(x_1)=f(x_2)$$

稱$f:X\to Y$是一個(gè)滿射，如果
$$?y\in Y,?x\in X,f(x)=y$$

稱$f:X\to Y$是一個(gè)雙射，如果$f$既是單射也是滿射，或者說
$$?y\in Y,?!x\in X,f(x)=y$$

用集合的方式表述單射、滿射、雙射：
稱$f:X\to Y$是一個(gè)單射，如果
$$f(X)?Y$$

稱$f:X\to Y$是一個(gè)滿射，如果
$$f^{?1}(Y)?X$$

稱$f:X\to Y$是一個(gè)雙射，如果$f$既是單射也是滿射，或者說
$$Y=f(X)$$

---

定義0.7 集合的勢
如果$n$是一個(gè)有限的數(shù)，假設(shè)$f:X\to \{1,2,?,n\}$是一個(gè)雙射，我們就稱集合$X$的勢為$n$，也就是集合$X$有$n$個(gè)元素，記為$|X|=n$

注 按這個(gè)定義我們只能處理有限個(gè)元素的集合，為了這個(gè)工具使用范圍更廣，我們需要擴(kuò)充我們的工具箱，這就需要借助映射對(duì)勢進(jìn)行公理化定義。

定義0.8 勢的大小關(guān)系
考慮映射$f:X\to Y$，如果

$f$是一個(gè)單射，則$|X|\le |Y|$

$f$是一個(gè)滿射，則$|X|\ge |Y|$

$f$是一個(gè)雙射，則$|X|=|Y|$

評(píng)注0.2 集合的大小關(guān)系有很多種定義方式，比如集合的包含關(guān)系就是一種比較集合“大小”的方法，再比如集合的勢也是比較集合“大小”的方法，具體采用什么方法比較兩個(gè)集合取決于我們想要保留的元素的“屬性”。如果我們用集合的包含關(guān)系定義集合的“大小”，那么被比較大小的兩個(gè)集合一定有部分元素是同質(zhì)的，所以才會(huì)出現(xiàn)包含關(guān)系；如果我們用集合的勢定義集合的大小關(guān)系，那么被比較大小的兩個(gè)集合的元素本身的屬性就被摒棄了，剩下的只是元素作為“計(jì)數(shù)工具”的性質(zhì)，比如一個(gè)集合中的元素是貓、另一個(gè)集合中的元素是老鼠，那么在用勢比較集合大小時(shí)，貓和老鼠的各種理化生屬性都被我們忽略了，最后剩下的計(jì)數(shù)作用意味著一只貓表示1，一只老鼠也表示1。所以勢這種工具更加抽象化、公理化，這也是為什么基于勢可以進(jìn)一步定義出自然數(shù)的概念的原因。

---

下面介紹勢的一些簡單性質(zhì)。
定理0.2 $$|X|\le |Y|?|Y|\ge |X|$$

證明
$?$: $|X|\le |Y|$說明存在$f:X\to Y$，且$f$是單射，取$x_0\in X$，定義$g:Y\to X$滿足
$$g(y)=\{\begin{array}{l}{x}_0,y\in Y?f(X)\\ f^{?1}(y),y\in f(X)\end{array}$$

顯然$g$是一個(gè)滿射，因此$|Y|\ge |X|$。

$?$: $|Y|\ge |X|$說明存在$g:Y\to X$，且$g$是滿射，因此集列$\{g^{?1}(\{x\}):x\in X\}$中的元素非空且無交，我們從$g^{?1}(\{x\})$中任取一個(gè)元素，記為$a_x$，并構(gòu)造映射$f:X\to Y$滿足$f(x)=a_x,?x\in X$，顯然$f$是一個(gè)單射，因此$|X|\le |Y|$。
證畢

定理0.3 對(duì)任意集合$X,Y$，要么$|X|\le |Y|$，要么$|X|\ge |Y|$

定理0.4 Schroeder-Bernstein定理 對(duì)任意集合$X,Y$，如果$|X|\le |Y|$并且$|X|\ge |Y|$，則$|X|=|Y|$
證明
如果$|X|\le |Y|$并且$|X|\ge |Y|$，則存在$f:X\to Y$, $g:Y\to X$是單射，根據(jù)單射的集合定義，$f(X)?Y$，于是我們可以把$Y$分成兩部分，
$$Y=f(X)?(Y?f(X))$$

另外，$g$也是單射，因此$g(Y)?X$，我們可以把$X$分為三部分
$$X=g(f(X))?g(Y?f(X))?(X?g(Y))$$

基于這個(gè)發(fā)現(xiàn)我們可以定義一個(gè)映射$h:X\to Y$，滿足
$$h(x)=\{\begin{array}{l}f(x),x\in g(f(X))?(X?g(Y))\\ g^{?1}(x),x\in g(Y?f(X))\end{array}$$

則$h$是一個(gè)雙射，所以$|X|=|Y|$。
證畢

評(píng)注0.3

• 證明勢的大小關(guān)系依據(jù)定義0.8，要證明$|X|\le |Y|$，只需要構(gòu)造一個(gè)$X\to Y$的映射并說明它是單射即可，其他情況類似，因?yàn)榘凑斩x，我們需要驗(yàn)證這樣的映射的存在性，一般而言說明存在性的方法就是做構(gòu)造性證明。
• 定理0.2充分性的證明實(shí)際上用到了選擇公理，它保證對(duì)任何$g^{?1}(\{x\})$，我們可以選擇出一個(gè)元素作為某個(gè)映射的像，另外，要讓定理充分性的證明更加嚴(yán)謹(jǐn)，我們還需要說明$f$是一個(gè)良定義，也就是不管我們從$g^{?1}(\{x\})$中選擇的是$a_x$還是$b_x$，$f$都是一個(gè)映射。關(guān)于良定義的驗(yàn)證我們?cè)诮榻B了二元關(guān)系與等價(jià)類之后再引入。
• 定理0.3的證明需要用到序關(guān)系，所以此處暫時(shí)略去證明。
• 這三個(gè)定理給后面自然數(shù)的基數(shù)理論中建立自然數(shù)的大小關(guān)系提供了基礎(chǔ)。

---

下面介紹一種有趣的集列——冪集(power set)。

定義0.9 冪集
假設(shè)$X$是一個(gè)非空集合，稱它的所有子集構(gòu)成的集列為它的冪集，記為$\mathcal{P}(X)$，即
$$\mathcal{P}(X)=\{E:E?X\}$$

定理0.5 對(duì)任意非空集合
$$|X|<|\mathcal{P}(X)|$$

當(dāng)$X$元素個(gè)數(shù)有限，或者說當(dāng)$|X|=n$時(shí)，$|\mathcal{P}(X)|=2^n$。

證明

第一部分：說明存在$X\to \mathcal{P}(X)$的不是滿射的單射，考慮$f:X\to \mathcal{P}(X)$滿足
$$f(x)=\{x\}$$

顯然$f$是單射但不是滿射，因此$$|X|<|\mathcal{P}(X)|$$

第二部分：假設(shè)$X$有$n$個(gè)元素，則$X$有$2^n$個(gè)子集，所以$|\mathcal{P}(X)|=2^n$，這個(gè)結(jié)論并不能簡單地推廣到無窮個(gè)元素的情況，我們會(huì)在介紹到自然數(shù)的時(shí)候開始逐步引入無窮的概念。

---

最后我們介紹一些拉回(pre-image)的運(yùn)算性質(zhì)。

定理0.6假設(shè)$f:X\to Y$是一個(gè)映射，$\{E_i{\}}_{i=1}^n$是一個(gè)集列，$?i\in \{1,?,n\}$，$E_i?Y$，則下面的結(jié)論成立

$f^{?1}({?}_{i=1}^n{E}_i)={?}_{i=1}^n{f}^{?1}(E_i)$

$f^{?1}({?}_{i=1}^n{E}_i)={?}_{i=1}^n{f}^{?1}(E_i)$

$f^{?1}(E_i^C)=(f^{?1}(E_i){)}^C,?i\in \{1,?,n\}$

證明
這三個(gè)結(jié)論的證明方法就是上一講介紹的證明集合相等的方法，套路比較固定。

i）$?y\in f^{?1}({?}_{i=1}^n{E}_i)$, $?x\in {?}_{i=1}^n{E}_i$, $f(x)=y$，因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$x\in {?}_{i=1}^n{E}_i$，$?i\in \{1,?,n\}$, $x\in E_i$，于是$y\in f^{?1}(E_i)?{?}_{i=1}^n{f}^{?1}(E_i)$。

ii）$?y\in f^{?1}({?}_{i=1}^n{E}_i)$, $?x\in {?}_{i=1}^n{E}_i$, $f(x)=y$，因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$x\in {?}_{i=1}^n{E}_i$，$?i\in \{1,?,n\}$, $x\in E_i$，于是$?i\in \{1,?,n\},y\in f^{?1}(E_i)?y\in {?}_{i=1}^n{f}^{?1}(E_i)$。

iii）$?y\in f^{?1}(E_i^C)$, 不存在$x\in E_i$, 使得$f(x)=y$，于是$y\in /f^{?1}(E_i)$，那么$y\in (f^{?1}(E_i){)}^C$。

總結(jié)

以上是生活随笔為你收集整理的初等数学O 集合论基础 第二节 映射与集合的势的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。