集合代数
出典: フリー百科事典『ウィキペディア（Wikipedia）』
集合代数（しゅうごうだいすう、英: Algebra of sets）は、集合の基本特性と法則、和集合、積集合、差集合といった集合論的操作、集合の等価関係や部分集合のような二項関係を扱う代数的な演算の体系である。
目次 |
[編集] はじめに
集合代数は、集合操作と集合関係の基本的特性を扱う。これらの特性は集合の根本的性質への洞察を提供するとともに、実用的な側面も持っている。
一般的な算術や式と同様、集合に関する算術や式も複雑になりうる。従って、そのような式の体系的な扱い方や計算方法は有用である。
算術については、算術演算と関係の基本特性を扱うのは初等代数学である。
例えば、加法と乗法は、結合法則、交換法則、分配法則といったよく知られた法則に従う。また、「—以下」といった関係は反射律、反対称律、推移律といった法則に従う。これらの法則は数や数の操作や関係の基本的性質を表しているだけでなく、計算を容易にするツールとしても働く。
集合代数は、そのような初等代数学を集合論に適用するものである。和集合、積集合、差集合といった集合論的操作や等価性や部分性の関係に関する代数学である。集合そのものについては集合の項目や素朴集合論の項目を参照されたい。また、集合の厳密な公理的扱いについては公理的集合論を参照されたい。
[編集] 集合代数の基本法則
和集合と積集合に関する二項関係は、さまざまな恒等式を満足する。その一部には法則としての名称がある。以下で命題として証明なしで3つの法則を示す。
命題 1: 任意の集合 A、B、C について、以下が成り立つ:
- 交換法則:
- <math>A \cup B = B \cup A\,\!</math>
- <math>A \cap B = B \cap A\,\!</math>
- 結合法則:
- <math>(A \cup B) \cup C = A \cup (B \cup C)\,\!</math>
- <math>(A \cap B) \cap C = A \cap (B \cap C)\,\!</math>
- 分配法則:
- <math>A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\,\!</math>
- <math>A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\,\!</math>
和集合と積集合が数の加法と乗法に性質が非常によく似ている点に注意されたい。加法や乗法と同じく、和集合や積集合の操作は可換で結合的であり、積集合は和集合に対して分配的である。しかし、加法や乗法と異なる点として、和集合も積集合に対して分配的である。
次の命題では3つの特殊な集合に関する2つの法則を示している。3つの特殊な集合とは、空集合、普遍集合（Universal Set）、差集合である。
命題 2: 普遍集合 U の任意の部分集合 A について、以下が成り立つ:
- 同一性の法則（identity laws）:
- <math>A \cup \varnothing = A\,\!</math>
- <math>A \cap U = A\,\!</math>
- 相補性の法則（complement laws）:
- <math>A \cup A^C = U\,\!</math>
- <math>A \cap A^C = \varnothing\,\!</math>
同一性の法則（と相補性の法則）は、加法や乗法で 0 と 1 がそうであるように、Ø と U が和集合や積集合の単位元であることを示している。
加法や乗法とは異なり、和集合や積集合は逆元を持たない。しかし、相補性の法則は一種の逆元的な集合の相補性の単項演算の基本的特性を示している。
以上の5組の法則（交換、結合、分配、同一性、相補性）が集合代数の基本であり、これらから全ての集合代数の定理が生まれる。
[編集] 双対原理
上述の命題から次のような興味深いパターンが表れる。すなわち、全ての法則は組になっていて、∪ と ∩、Ø と U を入れ替えることで相互に変換が可能である。
これは集合代数の重要かつ強力な特性の例であり、集合の双対原理（Principle of Duality）と呼ばれ、集合に関する任意の正しい式について、その中の和集合演算と積集合演算を入れ替え、U と Ø を入れ替えた式もやはり正しいことを示している。入れ替えた後の式が入れ替え前の式と同じである場合、これらを自己双対（Self-Dual）であるという。
[編集] 和集合と積集合の法則
次の命題は、和集合と積集合に関する6つの重要な法則を示している。
命題 3: 普遍集合 U の任意の部分集合 A と B について、以下が成り立つ:
- 等冪法則（Idempotent laws）:
- <math>A \cup A = A\,\!</math>
- <math>A \cap A = A\,\!</math>
- 統治法則（Domination laws）:
- <math>A \cup U = U\,\!</math>
- <math>A \cap \varnothing = \varnothing\,\!</math>
- 吸収法則（Absorption laws）:
- <math>A \cup (A \cap B) = A\,\!</math>
- <math>A \cap (A \cup B) = A\,\!</math>
前述の通り、命題3の各法則は命題1および命題2の基本法則から導出できる。例として、以下に和集合の等冪法則の証明を示す。
証明:
| <math>A \cup A\,\!</math> | <math>=(A \cup A) \cap U\,\!</math> | 積集合の同一性の法則による |
| <math>=(A \cup A) \cap (A \cup A^C)\,\!</math> | 和集合の相補性の法則による | |
| <math>=A \cup (A \cap A^C)\,\!</math> | 積集合に対する和集合の分配法則による | |
| <math>=A \cup \varnothing\,\!</math> | 積集合の相補性の法則による | |
| <math>=A\,\!</math> | 和集合の同一性の法則による |
次の証明は、上記の和集合の等冪法則の証明と双対関係にあり、積集合の等冪法則の証明となっている。
証明:
| <math>A \cap A\,\!</math> | <math>=(A \cap A) \cup \varnothing</math> | 和集合の同一性の法則による |
| <math>=(A \cap A) \cup (A \cap A^C)\,\!</math> | 積集合の相補性の法則による | |
| <math>=A \cap (A \cup A^C)\,\!</math> | 和集合に対する積集合の分配法則による | |
| <math>=A \cap U\,\!</math> | 和集合の相補性の法則による | |
| <math>=A\,\!</math> | 積集合の同一性の法則による |
[編集] 補集合の法則
次の命題は補集合（差集合）に関する集合代数の5つの法則を示している。
命題 4: A と B が普遍集合 U の部分集合であるとき、以下が成り立つ:
- ド・モルガンの法則:
- <math>(A \cup B)^C = A^C \cap B^C\,\!</math>
- <math>(A \cap B)^C = A^C \cup B^C\,\!</math>
- 二重補集合または対合法則:
- <math>A^{CC} = A\,\!</math>
- 普遍集合と空集合の補集合の法則:
- <math>\varnothing^C = U</math>
- <math>U^C = \varnothing</math>
二重補集合の法則は自己双対であることに注意されたい。
次の命題も自己双対であり、補集合の法則を満たす集合は補集合しかないことを示している。換言すれば相補性は補集合の法則で特徴付けられる。
命題 5: A と B が普遍集合 U の部分集合であるとき、以下が成り立つ:
- 補集合の普遍性:
- <math>A \cup B = U\,\!</math> で、かつ <math>A \cap B = \varnothing\,\!</math> なら、<math>B = A^C\,\!</math> が成り立つ。
[編集] 部分集合の代数
次の命題は、部分集合に半順序が成り立つことを示している。
命題 6: 集合 A、B、C について次が成り立つ:
- 反射律:
- <math>A \subseteq A\,\!</math>
- 反対称律:
- <math>A \subseteq B\,\!</math> かつ <math>B \subseteq A\,\!</math> であることと <math>A = B\,\!</math> は等価
- 推移律:
- <math>A \subseteq B\,\!</math> で、かつ <math>B \subseteq C\,\!</math> であるなら、<math>A \subseteq C\,\!</math> が成り立つ。
次の命題は、任意の集合 S とその冪集合に包含関係の順序性、上限と下限があり、分配法則と相補性の法則からブール代数が導かれることを示している。
命題 7: 集合 A、B、C が集合 S の部分集合であるとき、以下が成り立つ:
- 下限と上限の存在:
- <math>\varnothing \subseteq A \subseteq S\,\!</math>
- 結びの存在:
- <math>A \subseteq A \cup B\,\!</math>
- <math>A \subseteq C\,\!</math> で、かつ <math>B \subseteq C\,\!</math> なら、<math>A \cup B \subseteq C\,\!</math> が成り立つ。
- 交わりの存在:
- <math>A \cap B \subseteq A\,\!</math>
- <math>C \subseteq A\,\!</math> で、かつ <math>C \subseteq B\,\!</math> なら、<math>C \subseteq A \cap B\,\!</math> が成り立つ。
次の命題は <math>A \subseteq B\,\!</math> という式を和集合や積集合や補集合を使って表現できることを示している。
命題 8: 任意の2つの集合 A と B について、以下の式は等価である:
- <math>A \subseteq B\,\!</math>
- <math>A \cap B = A\,\!</math>
- <math>A \cup B = B\,\!</math>
- <math>A - B = \varnothing</math>
- <math>B^C \subseteq A^C</math>
この命題は集合の包含関係を和集合や積集合で表せることを示しており、換言すれば包含関係の記述は公理的に冗長である。
[編集] 補集合の代数
以下の命題は補集合（差集合）に関するものである。<math>-</math> は差集合を求める演算を表す。
命題 9: 任意の普遍集合 U とその部分集合 A、B、C について、以下が成り立つ:
- <math>C - (A \cap B) = (C - A) \cup (C - B)\,\!</math>
- <math>C - (A \cup B) = (C - A) \cap (C - B)\,\!</math>
- <math>C - (B - A) = (A \cap C)\cup(C - B)\,\!</math>
- <math>(B - A) \cap C = (B \cap C) - A = B \cap (C - A)\,\!</math>
- <math>(B - A) \cup C = (B \cup C) - (A - C)\,\!</math>
- <math>A - A = \varnothing\,\!</math>
- <math>\varnothing - A = \varnothing\,\!</math>
- <math>A - \varnothing = A\,\!</math>
- <math>B - A = A^C \cap B\,\!</math>
- <math>(B - A)^C = A \cup B^C\,\!</math>
- <math>U - A = A^C\,\!</math>
- <math>A - U = \varnothing\,\!</math>
[編集] 関連項目
[編集] 外部リンク
