集合劃分

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

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

定義

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

等價的說,X的子集的集合PX的劃分,如果

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

P的元素有時叫作劃分的部分[1]

例子

  • 所有單元素集合{x}都有唯一一個劃分,就是{ {x} }。
  • 對於任何集合XP = {X}是X的一個劃分。
  • 空集有唯一一個劃分,就是沒有塊的劃分。
  • 對於集合U的任何非空真子集AA和它的補集一起是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的一個成員包含xy二者。「等價關係」和「劃分」的概念因此本質上是等價的。[2]

註解

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

引用

參見