集合劃分

在數學中，集合X的劃分是把X分割到覆蓋了X的全部元素而又不重疊的「部分」或「塊」或「單元」中。更加形式的說，這些「單元」對於被劃分的集合是既全無遺漏又互斥的。

把一個集合劃分成6塊的歐拉圖表示。

定義

集合X的劃分是X的非空子集的集合，使得每個X的元素x都只包含在這些子集的其中一個內。

等價的說，X的子集的集合P是X的劃分，如果

1. P的元素都不是空集。（註：某些定義不需要這個要求）
2. P的元素的併集等於X。（我們稱P的元素覆蓋X。）
3. P的任何兩個元素的交集為空。（我們稱P的元素是兩兩不相交。）

P的元素有時叫作劃分的塊或部分。^[1]

例子

• 所有單元素集合{x}都有唯一一個劃分，就是{ {x} }。
• 對於任何集合X，P = {X}是X的一個劃分。
• 空集有唯一一個劃分，就是沒有塊的劃分。
• 對於集合U的任何非空真子集A，A和它的補集一起是U的一個劃分。
• 如果我們不使用前面定義中的公理1，則上述例子可以推廣為任何（空和非空）子集與它的補集一起是一個劃分。
• 集合{ 1, 2, 3 }有五個劃分。
  • { {1}, {2}, {3} }，有時標示為1/2/3。
  • { {1, 2}, {3} }，有時標示為12/3。
  • { {1, 3}, {2} }，有時標示為13/2。
  • { {1}, {2, 3} }，有時標示為1/23。
  • { {1, 2, 3} }，有時標示為123。
• 注意
  • 如果我們使用了前面定義中的公理1，則{ {}, {1,3}, {2} }不是一個劃分（因為它包含空集）；否則它是{1, 2, 3}的一個劃分。
  • { {1, 2}, {2, 3} }不是（任何集合的）一個劃分，因為元素2包含在多於一個不同的子集中。
  • { {1}, {2} }不是{1, 2, 3}的一個劃分，因為沒有塊包含3；但它是{1, 2}的一個劃分。

劃分和等價關係

如果給定在集合X上的一個等價關係，則所有等價類的集合形成X的一個劃分。反過來說，如果給定在X上的一個劃分P，我們可以在X上定義等價關係~，使得x ~ y當且僅當存在P的一個成員包含x和y二者。「等價關係」和「劃分」的概念因此本質上是等價的。^[2]

註解

1. Brualdi, pp. 44-45
2. Schechter, p. 54

引用

• Brualdi, Richard A. Introductory Combinatorics 4th edition. Pearson Prentice Hall. 2004. ISBN 0131001191. 引文格式1維護：冗餘文本 (link)
• Schechter, Eric. Handbook of Analysis and Its Foundations. Academic Press. 1997. ISBN 0126227608.

參見

• 等價關係
• 等價類