集合族

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

数学集合論関連分野における集合族(しゅうごうぞく、: family of sets)は集合の「あつまり」である。ここで「集合の集合」といわず「集合のあつまり」としているのは、文脈によっては集合族が同じ集合をいくつも重複して持つ場合(しばしば添字付けられた族 (indexed family of sets) として扱われる)があったり[1][2][3]、別の文脈では集合でない真の (proper class) となる場合があるなどの理由による。

特に与えられた集合 Ω の部分集合のみを考えるとき、Ω の部分集合からなる集合は Ω部分集合族Ω 上の集合族あるいは集合系ドイツ語版などと呼ぶ。グラフ理論の文脈では集合系はハイパーグラフとも呼ばれる[4]:27

また、自然数で添字付けられた(あるいは可算な)集合族は特に集合列ドイツ語版と呼ぶ(族 (数学)および列 (数学)の項も参照)。

定義[編集]

添字付けられた集合族
任意の集合 I を添字集合とする添字付けられた集合族とは、任意の iI に対して集合 Ai が割り当てられた {Ai}iI を言う。十分大きな集合(たとえば普遍集合Ω を取れば、写像 I𝒫(Ω); iAi として記述することもできる。
部分集合族
全体集合 Ω が与えられたとき、Ω 上の集合族とは Ω冪集合 𝒫(Ω) の部分集合のことを言う。即ち、Ω 上の集合族 S はその任意の元が Ω の部分集合となる集合である。

集合族 S が特定の集合演算(合併交叉補集合など)に関して閉じている (closed) あるいは安定 (stable) であるまたは完備 (complete) であるとは、S の任意の元にその演算を施した結果が必ずまた S の元となっていることを言う。しばしば集合族は、それが何らかの演算に関して閉じていることを示す修辞を付けて呼ばれる。例えば

  • 乗法的 (-完備, π-系):
  • 加法的 (-完備):
  • σ-乗法的:
  • σ-加法的:
  • -完備:
  • 補完備:

可算無限回の合併で閉じている集合族を σ-系、可算無限回の交叉で閉じている集合族を δ-系と呼ぶこともある。

[編集]

  • 集合 S冪集合 P(S)S 上の集合族である。
  • 集合 Sk-元部分集合全体の成す集合 S(k)S 上の集合族である。
  • 集合 S = {a,b,c,1,2} 上の(多重集合あるいは添字付けられた族としての)集合族の例をとして F = {A1, A2, A3, A4} (A1 = {a,b,c}, A2 = {1,2}, A3 = {1,2}, A4 = {a,b,1} で与える。
  • 順序集合の全体 Ord はそれ自身集合とならない真の類であり、その意味で「大きい」集合族である。
LaTeX1 Kopie.png

集合族のクラス[編集]

  • 部分集合族 A が有限交叉について閉じているとき π-系英語版であるといい、π-系が空集合を含むとき乗法族、さらに可算交叉について閉じているとき δ-系ドイツ語版(δ-乗法族)であるという。任意濃度の交叉で閉じているものは閉包族ドイツ語版と呼ぶ[注釈 1]。また、乗法族が包含関係を持つ任意の二つの集合に対し、一方から有限回の非交和を行って他方へ達する列を持つとき集合半環という。
  • A が(有限)和と(有限)交叉について閉じているとき、集合束ドイツ語版あるいはという。A が空集合でなく(あるいは空集合を元として含み)、和と差について閉じている(あるいは同じことだが対称差と交叉について閉じている)場合に限って集合環と呼ぶ場合もある。さらに可算交叉について閉じていれば δ-集合環、可算和について閉じていれば σ-集合環という。また、これらが全体集合を含むならば代数あるいはという。δ-集合体は σ-集合体である。
  • A が空集合を含み、有限合併および補について閉じているとき加法族、特に有限加法族であるという。さらに可算合併について閉じているならば σ-加法族あるいは完全加法族という。集合族 A が加法族であることは集合体であることと等価であり、同様に完全加法族は σ-集合体の別名である。任意濃度の合併について閉じているならば開核族ドイツ語版と呼ぶ[注釈 2]
  • 単調族は包含関係に関する単調列の極限について閉じている集合族
  • ディンキン族(d-族、δ-族)は全体集合を含み、包含関係を持つ集合同士の差について閉じていて、可算増大列の極限について閉じている。λ-系は全体集合を含み、補について閉じていて、可算非交和について閉じている。この二つは同じ概念を定める。ディンキン族定理ドイツ語版は乗法族の生成するディンキン族が同じく生成する完全加法族に一致することを述べるもので測度論において有用である。
  • 層族はそれに属する任意の集合 A, BAB または AB または AB ≠ ∅ の何れか一つのみを満たす。
  • ブール環
  • スパーナ族英語版あるいは独立集合系は、各集合がその集合族に属する自分自身以外の集合を含むことがない集合族を言う。スパーナの定理英語版はスパーナ族の大きさの最大値を評価する。
  • ヘリー族英語版は空でない交叉を持つ任意の極小部分族の大きさが下に有界であるような族を言う。ヘリーの定理は有界な次元のユークリッド空間における凸集合族がヘリー族を成すことを主張する。
  • フレシェフィルタードイツ語版
  • マトロイド
  • 集合フィルター
  • 集合の分割
  • (位相空間)の開集合系閉集合系近傍系
  • (有界型空間)の有界集合系
  • (一様空間)の近縁系
  • ボレル集合族は位相の生成する σ-加法族で、測度論において重要である。
  • 無向グラフ
  • ツェルメロ系ドイツ語版

性質[編集]

  • Ω 上の任意の添字付けられた部分集合族は、それが重複する元を持たないならば、それ自身冪集合 P(Ω) の部分集合である。
  • 重複元を持たない任意の部分集合族は、それ自身集合全体の成す真の類 V宇宙)の部分類である。
  • フィリップ・ホール英語版によるホールの結婚定理は、空でない集合の(元の重複を許す)有限族が完全代表系英語版 (system of distinct representatives) を持つための必要十分条件を与える。

関連概念[編集]

数学の特定の分野の中には集合族と同値な数学的対象を扱うものもある。そういったものは特定の種類の対象からなる集まりとして記述することができる。

  • ハイパーグラフあるいは集合系ドイツ語版 (set system) は頂点ハイパー辺の集合の組で、これらは何れも任意の集合を取り得る。ハイパーグラフのハイパー辺の全体は集合族を成す。また任意の集合族をその族の合併を頂点集合とするハイパーグラフとして解釈することができる。
  • 抽象単体的複体英語版は、線分・三角形・四面体および高次の単体を面と面で合わせることで得られる単体的複体の組合せ論的抽象化である。抽象単体的複体において各単体は単にその頂点集合として表される。重複を持たない任意の有限集合族で、その族に属する任意の集合の部分集合が全てもとの族に属するようなものは抽象単体的複体を成す。
  • 接続構造英語版は、「点」の集合・「直線」の集合および「接続関係」と呼ばれる(勝手な)二項関係の組である。接続関係は各「点」がどの「直線」上にあるかを特定する。接続構造を集合族として特定することができ(相異なる直線が全く同じ点集合を含むこともある)、「点」からなるどのような集合も各「直線」に属する。また任意の集合族をこの方法で接続構造として解釈することができる。
  • 二値ブロック符号は全て同じ長さの 0 および 1 からなる文字列となっているような符号語からなる。符号語の各対が大きなハミング距離を持つとき、誤り訂正符号に用いられる。各符号語を 1 のある位置の集合と見做せば、ブロック符号を集合族として記述することもできる。

関連項目[編集]

[編集]

注釈[編集]

  1. ^ X の部分集合からなる空な族の交わり(空積)は全体集合 X と見なす規約により、閉包族は乗法族となる
  2. ^ 空な族の合併(空和)は空集合と見なす規約により、開核族は空集合を含む

出典[編集]

  1. ^ Brualdi 2010, p. 322.
  2. ^ Roberts & Tesman 2009, p. 692.
  3. ^ Biggs 1985, p. 89.
  4. ^ Korte, Bernhard; Vygen, Jens (2009), Combinatorial Optimization: Theory and Algorithms (2nd ed.) . 日本語訳: B.コルテ; J.フィーゲン 『組合せ最適化: 理論とアルゴリズム』 (2版)。ISBN 978-4-431-10021-8https://books.google.com/books?id=7OfUJPqwyKwC&pg=PA27&dq=%22%E3%83%8F%E3%82%A4%E3%83%91%E3%83%BC%E3%82%B0%E3%83%A9%E3%83%95%22 

参考文献[編集]

  • Biggs, Norman L. (1985), Discrete Mathematics, Oxford: Clarendon Press, ISBN 0-19-853252-0 
  • Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Upper Saddle River, NJ: Prentice Hall, ISBN 0-13-602040-2 
  • Roberts, Fred S.; Tesman, Barry (2009), Applied Combinatorics (2nd ed.), Boca Raton: CRC Press, ISBN 978-1-4200-9982-9 

外部リンク[編集]