集合の分割

数学において、集合の分割とは、その要素を空でない 部分集合にグループ化することであり、すべての要素が 1 つの部分集合に含まれるようにします。

集合上のすべての同値関係は、この集合の分割を定義し、すべての分割は同値関係を定義します。同値関係または分割を備えた集合は、型理論と証明理論では通常、セットイドと呼ばれることがあります。

集合Xの分割とは、 Xの空でない部分集合の集合であり、X内のすべての要素xはこれらの部分集合の1つに正確に含まれる^[2]（つまり、部分集合は空でない互いに素な集合である）。

同様に、集合族 PがXの分割であるためには、以下の条件がすべて満たされなければならない: ^[3]

• 族P には空集合(つまり)が含まれません。${\displaystyle \emptyset \notin P}$
• P内の集合の和集合はXに等しい(つまり)。P 内の集合はX を網羅する、あるいはカバーすると言われる。集合的に網羅的な事象およびカバー (位相)も参照。${\displaystyle \textstyle \bigcup _{A\in P}A=X}$
• P内の任意の 2 つの異なる集合の共通部分は空です (つまり) 。Pの要素は、互いに素であるか、または相互に排他的であると言われます。相互排他性も参照してください。${\displaystyle (\forall A,B\in P)\;A\neq B\implies A\cap B=\emptyset }$

内の集合は、分割のブロック、部分、またはセルと呼ばれます。 ^[4] の場合、を含むセルを で表します。つまり、は を含むセルを表す表記法です。 ${\displaystyle P}$${\displaystyle a\in X}$${\displaystyle a}$${\displaystyle [a]}$${\displaystyle [a]}$${\displaystyle P}$${\displaystyle a}$

あらゆる分割は上の同値関係、つまり任意の に対して の場合に限り が成り立つ関係と同一視できます(つまり の場合に限り が成り立つ)。この表記は、同値関係が分割から構築できるという考えを思い起こさせます。逆に、あらゆる同値関係は分割と同一視できます。これが、非公式に「同値関係は分割と同じである」と言われることがある理由です。P が与えられた同値関係 と同一視される分割である場合、 と書く人もいます。この表記は、分割は集合Xをセルに分割したものであるという考えを示唆しています。この表記はまた、同値関係から分割を構築できるという考えを思い起こさせます。 ${\displaystyle P}$${\displaystyle X}$${\displaystyle \sim_{\!P}}$${\displaystyle a,b\in X}$${\displaystyle a\sim_{\!P}b}$${\displaystyle a\in [b]}$${\displaystyle b\in [a]}$${\displaystyle \sim_{\!P}}$${\displaystyle \sim}$${\displaystyle P=X/{\sim}}$

が有限である場合、のランクはです。 ${\displaystyle P}$${\displaystyle |X|-|P|}$${\displaystyle X}$

• 空集合には、 という 1 つのパーティションが正確に存在します。(注: これはパーティションであり、パーティションのメンバーではありません。)${\displaystyle \emptyset}$${\displaystyle \emptyset}$
• 空でない任意の集合Xに対して、P = { X } はXの分割であり、これを自明分割と呼びます。
  • 特に、すべてのシングルトン セット{ x } には、正確に 1 つのパーティション、つまり { { x } } があります。
• 集合Uの任意の空でない真部分集合 Aに対して、集合Aとその補集合はUの分割、つまり { A , U ∖ A } を形成します。
• セット {1, 2, 3} には次の 5 つのパーティション (項目ごとに 1 つのパーティション) があります。
  • { {1}, {2}, {3} }、1 | 2 | 3 と表記されることもあります。
  • { {1, 2}, {3} }、または 1 2 | 3。
  • { {1, 3}, {2} }、または 1 3 | 2。
  • { {1}, {2, 3} }、または 1 | 2 3。
  • { {1, 2, 3} }、または 123 (数字と混同されないコンテキストの場合)。
• 以下は{1, 2, 3}の分割ではありません。
  • { {}, {1, 3}, {2} } は、その要素の 1 つが空集合であるため、(どの集合の) 分割でもありません。
  • { {1, 2}, {2, 3} } は、要素 2 が複数のブロックに含まれているため、(どのセットでも) パーティションではありません。
  • { {1}, {2} } は、どのブロックにも 3 が含まれていないため、{1, 2, 3} のパーティションではありませんが、{1, 2} のパーティションです。

集合X上の任意の同値関係について、その同値類の集合はXの分割である。逆に、Xの任意の分割Pから、 xとy がP内の同じ部分にあるときにx ~ yと設定することによって、X上の同値関係を定義できる。したがって、同値関係と分割の概念は本質的に同値である。^[5]

選択公理は、集合X の任意の分割に対して、分割の各部分から正確に 1 つの要素を含む X の部分集合が存在することを保証します。これは、集合上の同値関係が与えられた場合、すべての同値類から 標準的な代表要素を選択できることを意味します。

集合Xの分割α は、 Xの分割ρの細分化です。αのすべての要素が ρ の何らかの要素のサブセットである場合、 αはρより細かく、 ρ はαより粗いと言います。非公式には、これはα がρのさらなる細分化であることを意味します。その場合、 α ≤ ρと書きます。

Xの分割集合上のこの「より細かい」関係は半順序である（したがって「≤」という表記が適切である）。各要素集合には最小の上限（「結合」）と最大の下限（「出会う」）があるため、格子を形成し、より具体的には（有限集合の分割の場合）幾何学的かつ超可解な格子である。^{[6] [7] 4要素集合の}分割格子には15個の要素があり、左側の ハッセ図に表されている。

パーティション α と ρ の交わりと結合は次のように定義されます。交わりと は、ブロックがαのブロックとρのブロックの交差であるパー​​ティションですが、空集合は除きます。言い換えると、 のブロックは、互いに素でないαのブロックとρのブロックの交差です。結合を定義するには、 AとBが素でない場合、 A ~ BによってαのブロックAとρのブロックBの関係を形成します。すると、 は、各ブロックC がこの関係で接続されたブロックの族の和集合であるパー​​ティションになります。 ${\displaystyle \alpha \wedge \rho }$${\displaystyle \alpha \wedge \rho }$ ${\displaystyle \alpha \vee \rho }$${\displaystyle \alpha \vee \rho }$

幾何学的格子とマトロイドの同値性に基づくと、有限集合の分割のこの格子は、マトロイドの基本集合が格子の原子、すなわち、シングルトン集合の分割と 1 つの 2 要素集合で構成されるマトロイドに対応します。これらの原子分割は、完全グラフの辺と 1 対 1 で対応します。原子分割の集合のマトロイド閉包は、それらすべての中でもっとも細かい共通粗大化です。グラフ理論の用語で言えば、それは完全グラフの頂点を、与えられた辺の集合によって形成されるサブグラフの接続成分に分割することです。このように、分割の格子は、完全グラフの グラフィック マトロイドの平面の格子に対応します。${\displaystyle n-2}$

もう 1 つの例は、同値関係の観点からパーティションの改良を示しています。Dが標準的な 52 枚のカードのデッキのカード セットである場合、D上の同じ色関係(~ _Cで表すことができます) には、セット {赤いカード} と {黒いカード} の 2 つの同値クラスがあります。~ _Cに対応する 2 部分パーティションには、同じスーツの関係 ~ _Sを生成する改良があり、これには 4 つの同値クラス {スペード}、{ダイヤモンド}、{ハート}、および {クラブ} があります。

対応する同値関係 ~ を持つ集合N = {1, 2, ..., n }の分割は、次の特性を持つ場合、交差しません。 Nの4 つの要素a、b、c、dで、 a < b < c < dがa ~ cおよびb ~ d を満たす場合、a ~ b ~ c ~ dです。この名前は、次の同値な定義に由来しています。 Nの要素 1、2、...、nが、正n角形のn頂点として(反時計回りの順序で) 描かれていると想像してください。分割は、各ブロックを多角形 (その頂点がブロックの要素) として描画することで視覚化できます。分割が交差しないのは、これらの多角形が交差しない場合に限ります。

有限集合の交差しない分割の格子は、すべての分割の格子のサブセットを形成しますが、2 つの格子の結合演算が一致しないため、サブ格子にはなりません。

非交差分割格子は自由確率論における役割のため重要視されるようになりました。

n要素の集合の分割の総数はベル数 B _nである。最初のいくつかのベル数は、 B ₀ = 1、 B ₁ = 1、B ₂ = 2、B ₃ = 5、B ₄ = 15、B ₅ = 52、およびB _{6 = 203 である（} OEISのシーケンスA000110 ）。ベル数は、再帰を満たします。

${\displaystyle B_{n+1}=\sum _{k=0}^{n}{n \choose k}B_{k}}$

指数関数を生成する関数を持つ

${\displaystyle \sum _{n=0}^{\infty }{\frac {B_{n}}{n!}}z^{n}=e^{e^{z}-1}.}$

ベル数は、ベル三角形を使用して計算することもできます。ベル三角形 では、各行の最初の値は前の行の末尾からコピーされ、後続の値は、その位置の左側の数と左上の数の 2 つの数を加算することによって計算されます。ベル数は、この三角形の両側に沿って繰り返されます。三角形内の数字は、特定の要素が最大のシングルトンであるパー​​ティションをカウントします。

n要素の集合を正確にk 個（空でない）の部分に分割する分割数のことを、第二種スターリング数 S ( n , k ) といいます。

n元集合の交差しない分割の数はカタラン数である。

${\displaystyle C_{n}={1 \over n+1}{2n \choose n}.}$

ウィキメディア・コモンズには、パーティションの設定に関連するメディアがあります。

• 正確なカバー
• ブロックデザイン
• クラスター分析
• パーティショントピックのリスト
• 積層（トポロジー）
• MECE原則
• 部分同値関係
• パーティション代数
• パーティションの細分化
• 点有限集合
• セット分割による押韻構成
• 弱い順序付け（順序付きセット分割）

• Brualdi, Richard A. (2004)。『Introductory Combinatorics (第 4 版)』。Pearson Prentice Hall。ISBN 0-13-100119-1。
• シェクター、エリック（1997）。分析とその基礎のハンドブック。アカデミックプレス。ISBN 0-12-622760-8。