定义 A.3.31.
设\(A\)、\(B\)是两个集合。称映射
\begin{equation*}
R: A\times B \to \{0,1\}
\end{equation*}
为\(A\)到\(B\)的一个（二元）关系；特别地，若\(A=B\)，则映射\(R\)也称为集合\(A\)上的（二元）关系。
子节 A.3 等价关系与分类
等价关系是集合中元素对之间的一种特定类型的关系。要定义等价关系，我们需要首先明确什么是“关系”。
日常生活中的关系有很多，如人之间的师生关系、朋友关系，数字间的相等关系、大小关系等等。这些关系的共同点是通常讨论的都是两个对象，且给了两个对象后，或者这两个对象有关系、或者没有关系。将上述共同点抽象化后，可以得出数学上关系的一个定义。
举例来说，取\(A\)表示一所大学的全体在职教师，\(B\)表示该大学的全部在读学生。定义\(R: A\times B \to \{0,1\}\)，其中
\begin{equation*}
R(t,s) = \begin{cases}
1, & \text{若}s\text{上过}t\text{主讲的课；}\\
0, & \text{若}s\text{没有上过}t\text{主讲的课。}
\end{cases}
\end{equation*}
则\(R\)反应的就是这所大学师生间的授课关系。
备注 A.3.32.
定义 A.3.33.
设\(R\)是集合\(A\)上的一个二元关系。若\(R\)满足：
-
自反性：\(\forall a\in A,\ aRa\)；
则称\(R\)是集合\(A\)上的等价关系。
等价关系之所以重要，部分原因是因为它与集合的分类/划分有密切联系。
讨论问题过程中，当涉及到将一些集合作为元素去构成另一个“较大”集合时，为了区别，这个“较大”集合通常被称为集族。集族仍然是一个集合，只不过它的元素也是集合。在集族中，这些作为元素的集合是按照一个整体去进行理解的。
集合\(A\)的划分/分类通常可以用集合\(A\)的子集构成的集族来表示。设\(A\)的一个子集族\(\mathcal{P}=\{A_i\}_{i\in I}\)，其中每个\(A_i\)都是\(A\)的一个子集，若满足：
则\(\mathcal{P}\)就是集合\(A\)的一个划分/分类，集族\(\mathcal{P}\)的每一个元素就是分类后的一类。
定理 A.3.34.
证明.
先证明划分决定等价关系：设 \(\mathcal{P}= \{A_{i}\}_{i \in I}\) 是集合 \(A\) 的任意划分，即满足：
\begin{equation*}
\bigcup_{i \in I}A_{i} = A \quad \text{且}\quad i \neq j \Rightarrow A_{i} \cap A_{j} = \emptyset.
\end{equation*}
定义关系 \(\sim\) 如下：
\begin{equation*}
\forall x, y \in A, \quad x \sim y \iff \exists i \in I \text{ 使得 }x \in A_{i} \text{ 且 }y \in A_{i}.
\end{equation*}
验证 \(\sim\) 是等价关系：
-
自反性：对\(\forall x \in A\)，由于\(\mathcal{P}\)是\(A\)的一个划分，所以一定存在\(i \in I\)，使得\(x \in A_{i}\)（即每一个元素都会被分到划分后的某一类中），故 \(x \sim x\)。
-
传递性：若\(x \sim y\) 且 \(y \sim z\)，则存在 \(A_{i}, A_{j}\) 使 \(x,y \in A_{i}\) 和 \(y,z \in A_{j}\)。因为\(y \in A_{i} \cap A_{j}\) 且划分后的不同子集互不相交，所以这两个子集只能是同一个子集，即\(A_{i} = A_{j}\)。 于是\(x,z \in A_{i}\)。 即 \(x \sim z\)，传递性成立。
下面证明等价关系也可以决定一个集合的划分：设 \(\sim\) 是集合 \(A\) 上的任意一个等价关系。对每个 \(x \in A\)，定义其等价类：
\begin{equation*}
[x] = \{ y \in A \mid y \sim x \}.
\end{equation*}
令 \(\mathcal{P}= \{ [x] \mid x \in A \}\)。 接下来需要证明 \(\mathcal{P}\) 是 \(A\) 的划分：
-
覆盖性：即每一个元素都属于\(\mathcal{P}\)中都某一个子集。对\(\forall x \in A\)，由自反性 \(x \sim x\)，故 \(x \in [x]\)。因此 \(\bigcup_{x \in A}[x] = A\)。
-
互斥性：即\(\mathcal{P}\)中两个不同子集的交为空集。用反证法证明这个性质，假设存在 \(a, b \in A\) 使得 \([a] \neq [b]\) 但 \([a] \cap [b] \neq \emptyset\)。取 \(c \in [a] \cap [b]\)， 则：\begin{align*} \amp c \in [a] \Rightarrow c \sim a \Rightarrow a \sim c \quad\amp \text{(对称性)} \\ \amp c \in [b] \Rightarrow c \sim b \amp \\ \amp a \sim c \land c \sim b \Rightarrow a \sim b \quad\amp \text{(传递性)} \end{align*}则 \(\forall y \in [a]\)，有 \(y \sim a \sim b\) (由传递性) \(\Rightarrow y \sim b \Rightarrow y \in [b]\)，故 \([a] \subseteq [b]\)。 同理可证 \([b] \subseteq [a]\)。 于是 \([a] = [b]\)，与假设\([a] \neq [b]\)矛盾!
