集合劃分
![本頁使用了標題或全文手工轉換](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/e/e5/Set_partition.svg/220px-Set_partition.svg.png)
在數學中,集合X的劃分是把X分割到覆蓋了X的全部元素而又不重疊的「部分」或「塊」或「單元」中。更加形式的說,這些「單元」對於被劃分的集合是既全無遺漏又互斥的。
定義
集合X的劃分是X的非空子集的集合,使得每個X的元素x都只包含在這些子集的其中一個內。
等價的說,X的子集的集合P是X的劃分,如果
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]
註解
引用
- Brualdi, Richard A. Introductory Combinatorics 4th edition. Pearson Prentice Hall. 2004. ISBN 0131001191.
- Schechter, Eric. Handbook of Analysis and Its Foundations. Academic Press. 1997. ISBN 0126227608.