和集合

Definition 4.2.1.1 (和集合).

2つの集合 $A, B$ が与えられたとき、 $A$ の元と $B$ の元をすべて集めて得られる集合

$A \cup B = {x ∣ x \in A \lor x \in B}$

を $A$ と $B$ の和集合という。

記号 $\cup$ は結び、join、cupなどと呼ばれる。たとえば、 $A$ を正の偶数全体の集合、 $B$ を正の奇数全体の集合とすると、 $A \cup B = N$ 。

基本的な性質

包含関係

Proposition 4.2.1.1 (和集合の包含関係).

$A \subset A \cup B, B \subset A \cup B$

Proposition 4.2.1.1 (和集合の包含関係) の証明

$x \in A$ とする。 Definition 4.2.1.1 (和集合) から、 $x \in A \cup B$ を満たす。 $\forall_{x} (x \in A \to x \in A \cup B)$ が正しいから、Definition 4.1.1 (部分集合) より、 $A \subset A \cup B$ が示された。

同様に、 $x \in B$ から $x \in A \cup B$ が従い、 $B \subset A \cup B$ 。 $□$

上位集合閉包

Proposition 4.2.1.2 (和集合の上位集合閉包).

$A \subset C, B \subset C \to A \cup B \subset C$

Proposition 4.2.1.2 (和集合の上位集合閉包) の証明

$x \in A \cup B$ とする。 Definition 4.2.1.1 (和集合) から、 $x \in A$ または $x \in B$ が従う。 $x \in A$ のとき、 $A \subset C$ から $x \in C$ を満たす。同様に、 $x \in B$ のとき、 $x \in C$ を満たす。 $x \in A \cup B \to x \in C$ が正しいから、Definition 4.1.1 (部分集合) より、 $A \subset C, B \subset C \to A \cup B \subset C$ が示された。 $□$

Proposition 4.2.1.1 (和集合の包含関係) より、 $A \cup B$ は $A$ と $B$ をどちらも含む。また、Proposition 4.2.1.2 (和集合の上位集合閉包) より、 $A$ も $B$ も含む任意の集合は、 $A \cup B$ を含む。したがって、 $A \cup B$ は、 $A, B$ の両方を含む最小の集合であると言える。

冪等律

Proposition 4.2.1.3 (和集合の冪等律).

$A \cup A = A$

Proposition 4.2.1.3 (和集合の冪等律) の証明

$x \in A \cup A$ とする。 Definition 4.2.1.1 (和集合) より、 $x \in A$ または $x \in A$ が従う。よって、 $x \in A \cup A \to x \in A$ から、 $A \cup A \subset A$ 。また、 $x \in A \to x \in A \cup A$ から、 $A \subset A \cup A$ 。したがって、 $A \cup A = A$ 。 $□$

交換律

Proposition 4.2.1.4 (和集合の交換律).

$A \cup B = B \cup A$

Proposition 4.2.1.4 (和集合の交換律) の証明

$x \in A \cup B$ とする。 Definition 4.2.1.1 (和集合)より、 $x \in A$ または $x \in B$ が従う。

$x \in A$ のとき、 $x \in A \to x \in B \cup A$ 。

$x \in B$ のとき、 $x \in B \to x \in B \cup A$ 。

よって、 $x \in A \cup B \to x \in B \cup A$ であるから、 $A \cup B \subset B \cup A$ 。

同様に、 $x \in B \cup A$ とすると、 $x \in B \cup A \to x \in A \cup B$ が従う。よって、 $B \cup A \subset A \cup B$ 。

したがって、 $A \cup B = B \cup A$ 。 $□$

結合律

Proposition 4.2.1.5 (和集合の結合律).

$(A \cup B) \cup C = A \cup (B \cup C)$

Proposition 4.2.1.5 (和集合の結合律) の証明

$x \in (A \cup B) \cup C$ とおく。 Definition 4.2.1.1 (和集合)より、 $x \in A \cup B$ または $x \in C$ が従う。

$x \in A$ または $x \in B$ または $x \in C$

$\to x \in A$ または $x \in (B \cup C)$

$\to x \in A \cup (B \cup C)$

よって、 $(A \cup B) \cup C \subset A \cup (B \cup C)$ が示せた。

同様に、 $x \in A \cup (B \cup C)$ とおくと、 $x \in (A \cup B) \cup C$ が従うから、 $(A \cup B) \cup C \supset A \cup (B \cup C)$ が示せた。

したがって、 $(A \cup B) \cup C = A \cup (B \cup C)$ が示された。 $□$

結合律の一般化

Proposition 4.2.1.6 (和集合の結合律の一般化).

一般に、 $n$ 個の集合 $A_{1}, A_{2}, \dots, A_{n}$ があるとき、 $A_{1} \cup A_{2} \cup \dots \cup A_{n}$ という表現のどこにどのような順序で括弧をつけても、結果として得られる集合は同じ

自分で書いた証明は証明になっていなかったのでチャッピーに教えてもらった。仮定を適用できる範囲が自分が思っていたより広かった。

Proposition 4.2.1.6 (和集合の結合律の一般化) の証明

任意の括弧の付け方をした式 $E_{k} = A_{1} \cup A_{2} \cup \dots \cup A_{k}$ は、常に集合 $A_{1} \cup \dots \cup A_{k}$ に等しいと仮定する。

任意の括弧付き表現 $E_{k + 1}$ は $1 \leq r \leq k$ の下で、必ず $B = A_{1} \cup \dots \cup A_{r}$ と $C = A_{r + 1} \cup \dots \cup A_{k + 1}$ を用いて、次のように表せる。

$E_{k + 1} = B \cup C$

仮定より、 $B = A_{1} \cup \dots \cup A_{r}$ と $C = A_{r + 1} \cup \dots \cup A_{k + 1}$ が成立するから、 Proposition 4.2.1.5 (和集合の結合律)より、 $E_{k + 1}$ は括弧の付け方によらず結果は同じ集合となる。

したがって、Proposition 4.2.1.6 (和集合の結合律の一般化)は数学的帰納法よりすべての $n$ で成り立つ。 $□$

結合律の一般化が成り立つので、括弧を省略して次のように表してよい。

$A_{1} \cup A_{2} \cup \dots \cup A_{n} = i = 1 ⋃ n A_{i}$

包含と和集合の同値命題

Proposition 4.2.1.7 (包含と和集合の同値命題).

$A \subset B \Leftrightarrow A \cup B = B$

Proposition 4.2.1.7 (包含と和集合の同値命題) の証明

$A \subset B$ ならば、 $A \subset B$ かつ $B \subset B$ であるから、 Proposition 4.2.1.2 (和集合の上位集合閉包)より、 $A \cup B \subset B$ 。また、Proposition 4.2.1.1 (和集合の包含関係)より、 $B \subset A \cup B$ 。よって、 $A \cup B = B$ が成り立つ。

また、 $A \cup B = B$ ならば、Proposition 4.2.1.1 (和集合の包含関係)より、 $A \subset A \cup B$ であるから、 $A \subset B$ 。よって、 $A \subset B$ が成り立つ。

したがって、Proposition 4.2.1.7 (包含と和集合の同値命題)は示された。 $□$

単調性

Proposition 4.2.1.8 (和集合の単調性).

$A \subset B \to A \cup C \subset B \cup C$

Proposition 4.2.1.8 (和集合の単調性) の証明

Proposition 4.2.1.7 (包含と和集合の同値命題)より、 $A \subset B \Leftrightarrow A \cup B = B$ 。また、 $A \cup B = B$ ならば、Proposition 4.2.1.1 (和集合の包含関係)より、 $A \subset A \cup B = B$ 。 Proposition 4.2.1.5 (和集合の結合律)より、 $A \cup C \subset A \cup B \cup C = B \cup C$ 。

したがって、 $A \subset B \to A \cup C \subset B \cup C$ が示された。

チャッピーがもっと賢い証明を教えてくれた。自分が書いた証明は嘘ではないけど冗長っぽい。

Proposition 4.2.1.8 (和集合の単調性) の証明②

Proposition 4.2.1.1 (和集合の包含関係)から、 $C \subset B \cup C$ 。また仮定から、 $A \subset B \subset B \cup C$ 。

Proposition 4.2.1.2 (和集合の上位集合閉包)より、 $A \cup C \subset B \cup C$ となり、示された。

かしこ！全く思いつかなかった。

恒等律

Proposition 4.2.1.9 (和集合の恒等律).

$\emptyset \cup A = A$

Proposition 4.2.1.9 (和集合の恒等律) の証明

Proposition 4.2.1.5 (和集合の結合律)より、示したい命題を $\emptyset \cup \emptyset \cup A = \emptyset \cup A$ に同値変形する。また、Proposition 4.2.1.3 (和集合の冪等律)より、 $\emptyset \cup \emptyset = \emptyset$ 。よって、示したい命題は $\emptyset \cup A = \emptyset \cup A$ に同値変形できるが、これは自明。

したがって、 $\emptyset \cup A = A$ を示せた。

教科書を読んでいたら Proposition 4.2.1.7 (包含と和集合の同値命題)を使っても示せることが書かれていた。結構感動した。

Proposition 4.2.1.9 (和集合の恒等律) の証明②

任意の集合 $A$ に対して、 $\emptyset \subset A$ であるから、 Proposition 4.2.1.7 (包含と和集合の同値命題)より、 $\emptyset \subset A \Leftrightarrow \emptyset \cup A = A$ 。よって示された。

note.momee.mt