初等數學O 集合論基礎 第四節 二元關系、等價類與運算

這一講的目標是在非空集合上定義關系與運算，我們學過的常見的關系有大小關系、整除關系、同余關系等；常見的運算有四則運算、乘方運算、開方運算等，但這一講要做的事情是給出關系與運算的更抽象的定義，使在任意集合上定義關系與運算變得可能。

之所以要引入關系與運算是因為前三講介紹的工具大部分都是處理集合運算的，而能夠處理集合元素的工具只有序關系，為了讓集合論起更大的作用，我們需要擴充能夠處理集合元素的工具箱。

---

在正式引入關系與運算前，我們先介紹一個重要的工具——笛卡爾積(Cartesian Product)。
定義0.13 笛卡爾積（或稱為直積）
假設$X,Y$是兩個非空集合，定義它們的笛卡爾積為
$$X\times Y=\{(x,y):x\in X,y\in Y\}$$

假設$\{X_i{\}}_{i=1}^n$是有限個非空集合，定義它們的笛卡爾積為
$$\prod _{i=1}^n{X}_i=\{x=(x_1,x_2,?,x_n):x_i\in X_i,i=1,?,n\}$$

比如$X=Y=\mathbb{R}$，即$X,Y$都是一根數軸，則$X\times Y={\mathbb{R}}^2$，也就是$X\times Y$就成了平面直角坐標系。

評注0.6
i) 集合的笛卡爾積與原集合之間自然就存在一個映射${\pi }_i:{\prod }_{i=1}^n{X}_i\to X_i$，滿足
$${\pi }_i(x)=x_i$$

顯然這個映射是一個單射，通常我們稱這個映射為projection，因為它就是$n$維直角坐標系中的點向第$i$個軸的投影。比如在平面直角坐標系中，
$${\pi }_x((x,y))=x,{\pi }_y((x,y))=y$$

分別表示平面直角坐標系中的點到$x$軸、$y$軸的投影。在數學分析與實分析中，這個映射是非常有用的。

ii）我們回顧一下第三講選擇公理的敘述，一列非空集合的笛卡爾積也是非空集合。對于
$$\prod _{i=1}^n{X}_i=\{x=(x_1,x_2,?,x_n):x_i\in X_i,i=1,?,n\}$$

這個集合非空說明至少存在一個$x\in {\prod }_{i=1}^n{X}_i$， $x=(x_1,x_2,?,x_n)$，因此在每一個非空集合中，都可以選出一個元素$x_i$。看上去這個結果很顯然，既然都是非空集合了，那集合里肯定至少要有一個元素，所以肯定可以選出一個來，這也是為什么我們接受它是一個公理的原因。之所以需要這樣一個公理是為了回答羅素悖論，感興趣的讀者可以自行查閱。

---

定義0.14 二元關系(Binary relation)

假設$X,Y$是兩個非空集合，$R?X\times Y$
$$R=\{(x,y):x\in {\pi }_x(R),y\in {\pi }_y(R)\}$$

我們稱$?(x,y)\in R$, $x$與$y$之前存在某種二元關系，記為$xRy$。

比如$X=Y=\mathbb{R}$，考慮小于等于這種二元關系，$xRy=x\le y$，則顯然
$$R=\{(x,y):x\in \mathbb{R},y\in \mathbb{R},x\le y\}$$

也就是下圖中紅色的區域：

有一些特殊的二元關系：

$?\in X\times Y$表示空關系；

$X\times Y$表示全完全關系；

$\{(x,y):x=y\}$表示恒等關系；

下面定義的等價關系也是一類特殊的二元關系

定義0.15 等價關系
$X$是非空集合，$R?X\times X$表示一個二元關系，稱$R$是一個等價關系，如果$?x,y,z\in R$

自反性：$xRx$

對稱性：$xRy?yRx$

傳遞性：$xRy,yRz?xRz$

如果$R$是等價關系，我們通常用$x～y$來表示$xRy$

例0.7 恒等關系是一個等價關系。
證
方法：用集合表示二元關系

假設$X$是非空集合，
$$R=\{(x,x):x\in X\}?X$$

驗證$R$滿足等價關系的三個條件。

自反性，顯然$(x,x)\in R$；
對稱性，如果$(x,y)\in R$，則$y=x$，因此$(y,x)=(x,x)\in R$
傳遞性，如果$(x,y),(y,z)\in R$, 則$y=x,z=y?z=x$，因此$(z,x)=(x,x)\in R$。

---

等價關系有一個非常重要的作用，對集合進行分割，我們先介紹分割的含義，然后再說明如何用等價關系分割集合。

定義0.16 分割
假設$X$是一個非空集合，如果存在$\{D_i{\}}_{i=1}^n$使得
$$X=\underset{i=1}{\overset{n}{?}}{D}_i$$

則$\{D_i{\}}_{i=1}^n$是$X$的一個分割。

定理0.8 假設非空集合$X$的勢$|X|$有限，$\{D_i{\}}_{i=1}^n$是$X$的一個分割，則
$$|X|=\sum _{i=1}^n|D_i|$$

注 這個定理非常顯然，可以用容斥原理直接獲得。

例0.8 我們用幾何分布介紹一下分割。古典概型認為某個事件的概率等于這個事件包含的基本事件數除以基本事件總數。用$X$表示所有可能的基本事件的集合，則$X$中的元素表示基本事件，$|X|$表示基本事件總數。用集合$A$表示某個事件，$A?X$，$|A|$表示這個事件包含的基本事件數。根據古典概型的含義，事件$A$的概率為
$$P=\frac{|A|}{|X|}$$

現在我們討論一個問題，假設我們拋擲一枚質地均勻的硬幣，用$A_k$表示在第$k$次拋擲時第一次數字朝上，那么我們應該如何根據古典概型計算$A_k$的概率？按照上面的討論，我們需要計算
$$P=\frac{|A_k|}{|X|}$$

假設$x_i=1$表示第$i$次拋擲時數字朝上
$$\begin{gathered} X=\{(x_1,x_2,?,x_n,?):x_i\in \{0,1\},?n\ge 1\} \\ {A}_k=\{(x_1,?,x_k,?):x_j=0,?j<k,x_k=1\} \end{gathered}$$

這個基本事件全體說明有可能我們會投擲無窮次硬幣才會得到一次數字朝上，這種可能性導致$|X|$一定是無窮，這樣的話要用古典概型處理這個問題就很困難了，因為我們還沒有定義無窮以及一個數除以無窮。因此我們考慮對$X$做分割，事實上$\{A_k{\}}_{k=1}^{\infty }$就是$X$的一個分割：
$$X=\underset{k=1}{\overset{\infty }{?}}{A}_k$$

讀者可以自行驗證這個結果。因此
$$P=\frac{|A_k|}{{\sum }_{j=1}^{\infty }|A_j|}$$

這就是正式導出幾何分布的思路。

---

等價關系可以提供一種構造分割的方法，這種方法是通過等價關系導出的等價類來實現的。

定義0.16 等價類
假設$X$是非空集合，$～$是$X$上的一個等價關系，稱$[x]$是一個等價類
$$[x]=\{y\in X:x～y\}$$

評注0.7
i) 根據這個定義，$x$的等價類就是$X$中所有與$x$等價的元素的集合。

ii）我們需要說明$[x]$這個記號是良定義的，即$?z～x$, $[z]=[x]$，也就是要說明等價類的符號可以用等價類中任何一個元素表示。
$[z]?[x]$：$?y\in [z]$, $y～z$，因為$z～x$，根據傳遞性，$y～x$，因此$y\in [x]$；

$[x]?[z]$：$?y\in [x]$, $y～x$，因為$z～x$，根據傳遞性，$y～z$，因此$y\in [z]$；

因此$?z～x$, $[z]=[x]$，即$[x]$這個記號是良定義的。

iii）不同的兩個等價類不相交，假設$x$與$y$不等價 ($x?y$)，則$[x]\cap [y]=?$。一種說明兩個集合不相交的方法是說明$?z\in [x]$, $z\in /[y]$：
用反證法，假設$z\in [y]$，則$z～y$，又因為$z\in [x]$，即$z～x$，根據傳遞性，$x～y$，這與$x$與$y$不等價矛盾。所以$[x]\cap [y]=?$。

定理0.9 假設$X$是一個非空集合，$～$是一個等價關系，則存在$X$的子集$S$滿足
$$\begin{gathered} S=\underset{F\in \mathcal{F}}{?}F \\ \mathcal{F}=\{F:?x,y\in F,x?y\} \end{gathered}$$

也就是說$S$是"最大的"包含的元素的互不等價的$X$的子集，使得
$$X=\underset{s\in S}{?}[s]$$

這個結果的意思是$X$可以分解為$～$定義的所有等價類的無交并。這個結果比較顯然，因為$X$中的元素一定屬于某個等價類，而不同的等價類交集為空。

例0.9 基于等價類分割集合。
考慮整數集$\mathbb{Z}$，假設等價關系$～$表示關于3的余數相同，讀者可以自行驗證這個是等價關系，則基于這個等價關系我們可以定義三個等價類：
$$\begin{gathered} [0]=\{z\in \mathbb{Z}:?n\in \mathbb{Z},z=3n\} \\ [1]=\{z\in \mathbb{Z}:?n\in \mathbb{Z},z=3n+1\} \\ [2]=\{z\in \mathbb{Z}:?n\in \mathbb{Z},z=3n+2\} \end{gathered}$$

根據定理0.9，
$$\mathbb{Z}=[0]?[1]?[2]$$

這個結果說明我們可以把所有的整數分為三類，能被3整除的，被3除余1的，被3除余2的。

---

最后我們定義一下二元運算。

定義0.17 二元運算
假設$X$是一個非空集合，稱定義在$X\times X$上的映射$f$是一個二元運算；如果$f(X\times X)?X$，就稱二元運算$f$在$X$上封閉。

比如$X=\mathbb{Z}$，定義整數的加法為
$$\begin{gathered} f:\mathbb{Z}\times \mathbb{Z}\to \mathbb{Z} \\ f(x,y)=x+y \end{gathered}$$

顯然加法是一個二元運算，并且在整數集上封閉。我們也可以定義整數的乘法，

$$\begin{gathered} g:\mathbb{Z}\times \mathbb{Z}\to \mathbb{Z} \\ g(x,y)=xy \end{gathered}$$

顯然乘法是一個二元運算，并且在整數集上封閉。

總結

以上是生活随笔為你收集整理的初等数学O 集合论基础 第四节 二元关系、等价类与运算的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。