上一节：等价关系及等价类

下一节：第二类 Stirling 数

离散数学笔记收录在：离散数学笔记目录

划分的定义

1处：子集族C指的是以集合A的子集为元素构成的集合C。

2处：如果，我感觉这里的如果总是很怪，它的意思是满足条件(1)、(2)、(3)的子集族C可以成为A的划分。

举个例子，假设A=\{1,2,3\}，则

商集A/R为A的一个划分，这个是比较显然的。

一个例子

(1)、E_A,I_A,R_{ij}都是E_A上的等价关系。E_A,I_A,R_{ij}各自商集的元素分别有1,n,n-1个。为了简便起见，不妨让A=\{1,2,3,4\},则关系E_A下的商集为\{\{1,2,3,4\}\}，关系I_A下的商集为\{\{1\},\{2\},\{3\}, \{4 \} \} 。假设a_i=1,a_j=2，则R_{ij}下的商集为\{\{1,2\},\{3\},\{4\}\}。\varnothing不是等价关系，因为它不满足自反性。

(2)、等价关系共5个：

\begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{pmatrix}, \begin{pmatrix} 1 & 1 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 1 \\ \end{pmatrix}, \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \\ \end{pmatrix}, \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 1 & 1 \\ \end{pmatrix}, \begin{pmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \\ \end{pmatrix} \\

其对应的商集分别为

\{\{1\},\{2\},\{3\} \}， \{\{1，2\},\{3\} \}，\{\{1,3\},\{2\}\}，\{\{1\},\{2，3\} \}，\{\{1,2,3\}\}。

由上面的题目，引发如下思考，对于有限集合A而言，假定其有n个元素，则

第1个问题：

A下有多少个等价关系 ？这个问题暂时不好回答，先跳过。

一个等价关系可以构建等价类，那么构建得到的等价类是唯一的吗？

这个答案是唯一的。首先需要说明这个小题目的意思是，在某个等价关系R下，是否构成类似于{1},{2},{3} 或 \{1，2\},\{3\}这样的不同等价类。

我们从反证法说明是唯一的。

考虑有限集合A，等价关系R下有不同的等价类方式B_1,B_2，在B_1下的等价类是C_1,\dots,C_s，在B_2下的等价类是D_1,\dots,D_t。

由于B_1,B_2方式不同，则必然存在B_1下的一个等价类C_i和B_2下的一个等价类D_j，满足C_i \ne D_j且C_i \cap D_j \ne \varnothing。取x \in C_i \cap D_j，既然C_i \ne D_j，不失一般性，必然存在y \in C_i, y \notin D_j（y \in D_j, y \notin C_i是类似的）。由于x \in C_i且y \in C_i,则x \cong y，又x \in D_j，则y \in D_j，这与y \notin D_j形成矛盾。由此可知一个等价关系下构建的等价类方式唯一。

证毕！

补充说明：由于B_1,B_2方式不同，则必然存在B_1下的一个等价类C_i和B_2下的一个等价类D_j，