集合の代数学

集合の代数学︵しゅうごうのだいすうがく、英: algebra of sets︶は、集合の集まりを結び・交わり・補演算といった集合演算、集合の相等関係・包含関係のような二項関係などを持つ体系として捉えたものである。集合の代数学を考えることで、集合に関する基本的な性質・法則を明らかにし、これらの演算や関係に伴って必要となる式の評価や計算の実行に関して系統的な扱いができるようになる。

はじめに

集合の代数学は、集合操作と集合関係の基本的性質を扱う。これらの性質は集合の根本的性質への洞察を提供するとともに、実用的な側面も持っている。

通常の算術における式やその計算とまったく同様に、集合に関する式や計算も複雑になりうるから、そのような式の評価や効率的な計算を自在に行うために、体系的な取り扱い方を有しているということは有効である。

算術について、演算と関係の基本性質を扱うのは初等代数学である。

例えば、加法と乗法は、結合法則、交換法則、分配法則といったよく知られた法則に従う。また、﹁—以下﹂といった関係は反射律、反対称律、推移律といった法則に従う。これらの規則は数や数の操作や関係の基本的性質を表しているだけでなく、計算を容易にするツールとしても働く。

集合の代数学は、そのような初等代数学を集合論に適用するものである。和集合、共通部分、差集合といった集合論的操作や等価性や部分性の関係に関する代数学である。集合そのものについては集合の項目や素朴集合論の項目を参照。また、集合の厳密な公理的扱いについては公理的集合論を参照。

集合の代数学の基本法則

和集合と共通部分に関する二項関係は、さまざまな恒等式を満足する。その一部には法則としての名称がある。以下で命題として証明なしで3つの規則を示す。

命題1: 任意の集合 A、B、C について、以下が成り立つ。

交換法則:
●$A\cup B=B\cup A$$A\cup B=B\cup A$
●$A\cap B=B\cap A$$A\cap B=B\cap A$
結合法則:
●$(A\cup B)\cup C=A\cup (B\cup C)$$(A\cup B)\cup C=A\cup (B\cup C)$
●$(A\cap B)\cap C=A\cap (B\cap C)$$(A\cap B)\cap C=A\cap (B\cap C)$
分配法則:
●$A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$$A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$
●$A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$$A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$
和集合と共通部分が数の加法と乗法に性質が非常によく似ている点に注意が必要である。加法や乗法と同じく、和集合や共通部分の操作は可換で結合的であり、共通部分は和集合に対して分配的である。しかし、加法や乗法と異なる点として、和集合も共通部分に対して分配的である。

次の命題では3つの特殊な集合に関する2組の規則を示している。3つの特殊な集合とは、空集合、普遍集合︵universal set︶、補集合である。

命題2: 普遍集合 Uの任意の部分集合 Aについて、以下が成り立つ。

同一性の規則︵identity laws︶:
●$A\cup \varnothing =A$$A\cup \varnothing =A$
●$A\cap U=A$$A\cap U=A$
相補性の規則︵complement laws︶:
●$A\cup A^{\mathrm {C} }=U$$A\cup A^{\mathrm {C} }=U$
●$A\cap A^{\mathrm {C} }=\varnothing$$A\cap A^{\mathrm {C} }=\varnothing$
同一性の規則︵と相補性の規則︶は、加法や乗法で 0 と1がそうであるように、∅ と Uが和集合や共通部分の単位元であることを示している。

加法や乗法とは異なり、和集合や共通部分は逆元を持たない。しかし、相補性の規則は一種の逆元的な集合の相補性の単項演算の基本的性質を示している。

以上の5組の規則︵交換、結合、分配、同一性、相補性︶が集合の代数学の基本であり、これらから全ての集合の代数学の定理が生まれる。

双対原理

「順序集合に関する双対性」も参照

上述の命題から次のような興味深いパターンが表れる。すなわち、全ての規則は組になっていて、∪ と ∩、∅ と Uを入れ替えることで相互に変換が可能である︵束に関する双対性︶。

これは集合の代数学の重要かつ強力な性質の例であり、集合の双対原理︵principle of duality︶と呼ばれ、集合に関する任意の正しい式について、その中の和集合演算と共通部分演算を入れ替え、U と ∅ を入れ替えた式もやはり正しいことを示している。入れ替えた後の式が入れ替え前の式と同じである場合、これらを自己双対︵self-dual︶であるという。

和集合と共通部分の追加規則

次の命題は、和集合と共通部分に関する6つの重要な法則を示している。

命題3: 普遍集合 Uの任意の部分集合 Aと Bについて、以下が成り立つ。

等冪法則︵idempotent laws︶:
●$A\cup A=A$$A\cup A=A$
●$A\cap A=A$$A\cap A=A$
統治法則︵domination laws︶:
●$A\cup U=U$$A\cup U=U$
●$A\cap \varnothing =\varnothing$$A\cap \varnothing =\varnothing$
吸収法則︵absorption laws︶:
●$A\cup (A\cap B)=A$$A\cup (A\cap B)=A$
●$A\cap (A\cup B)=A$$A\cap (A\cup B)=A$
前述の通り、命題3の各法則は命題1および命題2の基本法則から導出できる。例として、以下に和集合の等冪法則の証明を示す。

証明:

$A\cup A$	$=(A\cup A)\cap U$	共通部分の同一性の規則による
	$=(A\cup A)\cap (A\cup A^{\mathrm {C} })$	和集合の相補性の規則による
	$=A\cup (A\cap A^{\mathrm {C} })$	共通部分に対する和集合の分配法則による
	$=A\cup \varnothing$	共通部分の相補性の規則による
	$=A$	和集合の同一性の規則による

次の証明は、上記の和集合の等冪法則の証明と双対関係にあり、共通部分の等冪法則の証明となっている。

証明:

$A\cap A$	$=(A\cap A)\cup \varnothing$	和集合の同一性の規則による
	$=(A\cap A)\cup (A\cap A^{\mathrm {C} })$	共通部分の相補性の規則による
	$=A\cap (A\cup A^{\mathrm {C} })$	和集合に対する共通部分の分配法則による
	$=A\cap U$	和集合の相補性の規則による
	$=A$	共通部分の同一性の規則による

補集合の追加規則

次の命題は補集合に関する集合の代数学の5つの規則を示している。

命題4: Aと Bが普遍集合 Uの部分集合であるとき、以下が成り立つ。

ド・モルガンの法則:
●$(A\cup B)^{\mathrm {C} }=A^{\mathrm {C} }\cap B^{\mathrm {C} }$$(A\cup B)^{\mathrm {C} }=A^{\mathrm {C} }\cap B^{\mathrm {C} }$
●$(A\cap B)^{\mathrm {C} }=A^{\mathrm {C} }\cup B^{\mathrm {C} }$$(A\cap B)^{\mathrm {C} }=A^{\mathrm {C} }\cup B^{\mathrm {C} }$
二重補集合または対合法則:
●$A^{\mathrm {CC} }=A$$A^{\mathrm {CC} }=A$
普遍集合と空集合の補集合の規則:
●$\varnothing ^{\mathrm {C} }=U$$\varnothing ^{\mathrm {C} }=U$
●$U^{\mathrm {C} }=\varnothing$$U^{\mathrm {C} }=\varnothing$
二重補集合の規則は自己双対であることに注意。

次の命題も自己双対であり、補集合の規則を満たす集合は補集合しかないことを示している。換言すれば相補性は補集合の規則で特徴付けられる。

命題5: Aと Bが普遍集合 Uの部分集合であるとき、以下が成り立つ。

補集合の普遍性:

• $A\cup B=U$ で、かつ $A\cap B=\varnothing$ なら、$B=A^{\mathrm {C} }$ が成り立つ。

包含の代数学

次の命題は、部分集合に半順序が成り立つことを示している。

命題6: 集合 A、B、C について次が成り立つ。

反射律:
●$A\subseteq A$$A\subseteq A$
反対称律:
●$A\subseteq B$$A\subseteq B$ かつ $B\subseteq A$$B\subseteq A$であることと $A=B$$A=B$は等価

推移律:
●$A\subseteq B$$A\subseteq B$ で、かつ $B\subseteq C$$B\subseteq C$であるなら、$A\subseteq C$$A\subseteq C$ が成り立つ。

次の命題は、任意の集合 Sとその冪集合に包含関係の順序性、上限と下限があり、分配法則と相補性の規則からブール代数が導かれることを示している。

命題7: 集合 A、B、C が集合 Sの部分集合であるとき、以下が成り立つ。

下限と上限の存在:
●$\varnothing \subseteq A\subseteq S$$\varnothing \subseteq A\subseteq S$
結びの存在:
●$A\subseteq A\cup B$$A\subseteq A\cup B$
●$A\subseteq C$$A\subseteq C$ で、かつ $B\subseteq C$$B\subseteq C$なら、$A\cup B\subseteq C$$A\cup B\subseteq C$ が成り立つ。

交わりの存在:
●$A\cap B\subseteq A$$A\cap B\subseteq A$
●$C\subseteq A$$C\subseteq A$ で、かつ $C\subseteq B$$C\subseteq B$なら、$C\subseteq A\cap B$$C\subseteq A\cap B$ が成り立つ。

次の命題は $A\subseteq B$$A\subseteq B$という式を和集合や積集合や補集合を使って表現できることを示している。

命題8: 任意の2つの集合 Aと Bについて、以下の式は等価である。

●$A\subseteq B$$A\subseteq B$
●$A\cap B=A$$A\cap B=A$
●$A\cup B=B$$A\cup B=B$
●$A-B=\varnothing$$A-B=\varnothing$
●$B^{\mathrm {C} }\subseteq A^{\mathrm {C} }$$B^{\mathrm {C} }\subseteq A^{\mathrm {C} }$
この命題は集合の包含関係を和集合や共通部分で表せることを示しており、換言すれば包含関係の記述は公理的に冗長である。

差集合の代数学

以下の命題は差集合に関するいくつかの恒等式が並べてある。− は差集合を求める演算を表し、$\bullet ^{\mathrm {C} }$$\bullet ^{\mathrm {C} }$ は　$\bullet$$\bullet$ の補集合を表す。

命題9: 任意の普遍集合 Uとその部分集合 A、B、C について、以下が成り立つ。

• $C-(A\cap B)=(C-A)\cup (C-B)$
• $C-(A\cup B)=(C-A)\cap (C-B)$
• $C-(B-A)=(A\cap C)\cup (C-B)$
• $(B-A)\cap C=(B\cap C)-A=B\cap (C-A)$
• $(B-A)\cup C=(B\cup C)-(A-C)$
• $A-A=\varnothing$
• $\varnothing -A=\varnothing$
• $A-\varnothing =A$
• $B-A=A^{\mathrm {C} }\cap B$
• $(B-A)^{\mathrm {C} }=A\cup B^{\mathrm {C} }$
• $U-A=A^{\mathrm {C} }$
• $A-U=\varnothing$

関連項目

• 論理演算
• ブール代数
• 集合代数

参考文献

• Stoll, Robert R.; Set Theory and Logic, Mineola, N.Y.: Dover Publications (1979) ISBN 0-486-63829-4. "The Algebra of Sets", pp 16—23
• Courant, Richard, Herbert Robbins, Ian Stewart, What is mathematics?: An Elementary Approach to Ideas and Methods, Oxford University Press US, 1996. ISBN 978-0-19-510519-3. "SUPPLEMENT TO CHAPTER II THE ALGEBRA OF SETS"

外部リンク

• Operations on Sets at ProvenMath