划分

划分
术语名称	划分
英语名称	partition of a set
别名	分划

集合的划分(partition of a set)指对一个集合，几个不重复、不遗漏其中元素的非空子集所构成的集合。

定义

对集合 [math]\displaystyle{ A }[/math] ，若有集合 [math]\displaystyle{ P = \{ A_1, A_2, \dots, A_n \} }[/math] 满足：

1. 非空：[math]\displaystyle{ A_i \neq \varnothing }[/math]
2. 覆盖：[math]\displaystyle{ \bigcup_{i=1}^n A_i = A }[/math]
3. 不交：[math]\displaystyle{ \forall i \forall j ((A_i \in P \land A_j \in P \land i \neq j) \rightarrow A_i \cap A_j = \varnothing) }[/math]

则称 [math]\displaystyle{ P }[/math] 是 [math]\displaystyle{ A }[/math] 的一个划分（partition）。

注意：部分说法不一致。有些定义中要求 [math]\displaystyle{ A }[/math] 非空，有些定义中不要求 [math]\displaystyle{ A_i }[/math] 非空。

覆盖条件隐性地要求了子集关系。

性质

一个集合的划分和这个集合上的等价关系等价。属于划分中的某个集合本身是一种等价关系，等价关系所规定的等价类也一定是这个集合的划分。

特例

对任意非空集合 [math]\displaystyle{ A }[/math] ，集合 [math]\displaystyle{ \{ A \} }[/math] 总是其一个划分，称为平凡划分(trivial partition)。

对于空集 [math]\displaystyle{ \varnothing }[/math] ，仅存在一个划分 [math]\displaystyle{ \varnothing }[/math] （注意不是 [math]\displaystyle{ \{\varnothing\} }[/math]）。因为没有任何非空子集，所以划分中当然也不存在任何元素。

对非空集合 [math]\displaystyle{ A }[/math] 及其非空真子集 [math]\displaystyle{ B }[/math] ， [math]\displaystyle{ \{B, A \setminus B \} }[/math] 就是一个划分。

等价关系
等价	划分
结构	等价类、setoid、商集、自然映射