集合の分割

ウィキペディア

索引トップ用語の索引ランキングカテゴリー

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/19 14:18 UTC 版)

集合を6つの部分に分割した図（オイラー図による表現）

定義

集合 X の分割 P は、X の空でない部分集合からなる集合族であり、X の個々の元 x について x ∈ A ∈ P を満たす X の部分集合 A が必ずただ一つ存在する。

X の部分集合族 P が X の分割であるためには、次が成り立つ必要がある。

P は元として空集合を持たない。
P の元の和集合は X と等しい（P は X を覆っている）。
P の任意の2つの異なる元の共通部分は空集合である（つまり P の相異なる元は互いに素である）。

数学的には、これら2つの条件を次のように表現できる。

$\emptyset \notin P$
$\bigcup P=X$
$A\cap B=\varnothing {\text{ if }}A\in P,\,B\in P,\,A\neq B$

P の元を分割の「ブロック (block)」あるいは「部分 (part)」と呼ぶ^[1]。

例

あらゆる単集合 {x} には唯一の分割 { {x} } しか存在しない。
空でない任意の集合 X について、P = {X} は X の分割の1つである。
集合 U の任意の空でない真部分集合 A について、A とその差集合からなる集合族は U の分割の1つである。
集合 { 1, 2, 3 } には5種類の分割がある。
- { {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,3}, {2} } は分割ではない（空集合を含んでいるため）。
{ {1,2}, {2, 3} } は分割ではない（2 という元が2つの部分集合に含まれているため）。
{ {1}, {2} } は {1, 2, 3} の分割ではないが（3 がどのブロックにも含まれていないため）、{1, 2} の分割としては正しい。

分割と同値関係

集合 $X$ 上の任意の同値関係 $R$ について、その同値類の集合 $X/R$ は $X$ の分割である。集合 $X$ の同値関係 $R$ からその同値類集合として $X$ の分割を得ることを、 $R$ による $X$ の類別または分類 (classification) と呼ぶ^[2]。

逆に、 $X$ の任意の分割 $P$ から $X$ 上の同値関係 $R P$ を定義することができる。すなわち、 $X$ の任意の2つの元 $x$ と $y$ が $P$ の同じブロックに属するとき、 $x ~ y$ とすれば、これは同値関係を定める。このとき、同値関係 $R P$ を分割 $P$ に付随する (associated) 同値関係という^[2]。

したがって、集合に同値関係を設定することと集合の分割は本質的に等価である^[3]。

脚注・出典

^ Brualdi, Richard A. (2004). Introductory Combinatorics (4th edition ed.). Pearson Prentice Hall. pp. 44-45. ISBN 0131001191
^ ^a ^b 松坂和夫『集合・位相入門』岩波書店、1968年。 p. 57
^ Schechter, Eric (1997). Handbook of Analysis and Its Foundations. Academic Press. p. 54. ISBN 0126227608