4. relations and partitions

axiom of pair formation 配对公理

For any two sets \(a,b\) there is a set \(P=\{a,b\}\) such that \(x \in P\) if and only if \(x = a\) or \(x = b\).

If \(a=b\) then \(P\) is the singleton \(\{a\}\).

The order pair \((a,b)\) is defined to the set \(\{\{a\},\{a,b\}\}\); its first component is \(a\) and its second component is \(b\).

\((a,b)=(a',b')\) if and only if \(a=a'\) and \(b=b'\).

Cartesian product 笛卡儿积

The Cartesian product of classes \(A\) and \(B\) is the class \(A \times B = \{(a,b) | a \in A,b \in B \}\)

\(A \times \emptyset = \emptyset = \emptyset \times B\)

relation 关系

A subclass \(R\) of \(A \times B\) is called a relation on \(A \times B\).

If \(f:A \rightarrow B\) is a function, the graph of \(f\) is the relation \(R=\{(a,f(a))|a \in A\}\). Since \(f\) is a function, \(R\) has the special property:

\[ \mathrm{Every\ element\ of}\ A\ \mathrm{is\ the\ first\ component\ of\ one\ and\ only\ one\ ordered\ pair\ in}\ R. \tag{14} \label{ref14} \]

Any relation \(R\) on \(A \times B\) that satisfies \(\eqref{ref14}\), determines a unique function \(f:A \rightarrow B\) whose graph is \(R\). Whenever convenient we shall think of a function as a relation satisfying \(\eqref{ref14}\).

equivalence relati on 等价关系

A relation \(R\) on \(A \times A\) is an equivalence relation on \(A\) provided \(R\) is:

\[ \mathrm{reflexive:}\ (a,a) \in R\ \mathrm{for\ all}\ a \in A; \tag{15} \label{ref15} \]

\[ \mathrm{symmetric:}\ (a,b) \in R \rightarrow (b,a) \in R; \tag{16} \label{ref16} \]

\[ \mathrm{transitive:}\ (a,b) \in R\ \mathrm{and}\ (b,c) \in R \rightarrow (a,c) \in R; \tag{17} \label{ref17} \]

If \(R\) is an equivalence relation on \(A\) and \((a,b) \in R\), we say that \(a\) is equivalent to \(b\) under \(R\) and write \(a \sim B\) or \(aRb\).

equivalence class 等价类

Let \(R(\sim)\) be an equivalence relation on \(A\). If \(a \in A\), the equivalence class of \(a\) (denoted \(\bar{a}\)) is the class of all those elements of \(A\) that are equivalent to \(a\); that is, \(\bar{a}=\{b \in A|b \sim a\}\).

quotient class 商类

The class of all equivalence classes in \(A\) is denoted \(A/R\) and called the quotient class of \(A\) by \(R\).

Since \(R\) is reflexive ,\(a \in \bar{a}\) for every \(a \in A\); hence

\[ \bar{a} \not = \emptyset,\ \mathrm{for\ every} a \in A \tag{18} \label{ref18} \]

\[ \mathrm{If}\ A\ \mathrm{is\ a\ set},\ \bigcup_{a \in A}\bar{a}=A=\bigcup_{\bar{a} \in A/R} \bar{a} \tag{19} \label{ref19} \]

\[ \bar{a} = \bar{b} \Leftrightarrow a \sim b \tag{20} \label{ref20} \]

\[ \mathrm{for}\ a,b \in A,\ \mathrm{either}\ \bar{a} \cap \bar{b} = \emptyset\ \mathrm{or}\ \bar{a}=\bar{b} \tag{21} \label{ref21} \]

partition 划分

Let \(A\) be a nonempty class and \(\{A_i|i \in I\}\) a family of subsets of \(A\) such that:

\[ A_i \not= \emptyset,\ \mathrm{for\ each}\ i\in I; \\ \bigcup_{i \in I} A_i = A; \\ A_i \cap A_j = \emptyset\ \mathrm{for\ all}\ i\not=j \in I; \]

then \(\{ A_i|i \in I \}\) is said to be a \(partition\) of \(A\).

Theorem 4.1

If \(A\) is a nonempty set, then the assignment \(R \mapsto A/R\) defines a bijection from the set \(E(A)\) of all equivalence relations on \(A\) onto the set \(Q(A)\) of all partitions of \(A\).

proof

若 \(R\) 为 \(A\) 上的一个等价关系，根据 \(\eqref{ref18},\eqref{ref19},\eqref{ref21}\) ，存在 \(A\) 上的一个划分 \(A/R\) ，使得 \(R \mapsto A/R\) 定义了一个函数 \(f: E(A) \rightarrow Q(A)\)

接下来定义 \(g:Q(A) \rightarrow E(A)\) 。若 \(S=\{ A_i | i \in I\}\) 为 \(A\) 上的一个划分，则 \(g(S)\) 定义为如下所述的等价关系：

\[ a \sim b \Leftrightarrow a \in A_i\ \mathrm{and}\ b \in A_i\ \mathrm{for\ some\ (unique)}\ i \in I. \tag{22}\label{ref22} \]

可以验证 \(g(S)\) 满足 \(\bar{a}=A_i\) for \(a \in A_i\).

易证 \(fg=1_{Q(A)}\) 且 \(gf=1_{E(A)}\)，故由 \((13)\) 可知 \(f\) 是双射的。