1.5 集合の演算

1.5.1 和集合

二つの集合$A,B$に対し，$A$か$B$の少なくとも一方に属する元をすべて集めて作った集合を， $A$と$B$の和集合，結び(union)とよび，$A\cup B$で表す．すなわち， $A\cup B:=\{x\bigm \vert x\in A \vee x\in B\}\strut$である．

和集合を表すのに記号$\cup$を最初に用いたのはGiuseppe Peano (1858-1932)である． [7]

命題 1.53  

$A:=\{x\bigm \vert P (x)\}$, $B:=\{x\bigm \vert Q (x)\}$のとき，

$$A\cup B =\{x \bigm \vert P (x) \vee Q (x)\}\strut$$

である．

証明： $a \in A \Leftrightarrow P(a) , a \in B \Leftrightarrow Q(a)\strut$ より，

$$a \in A\cup B \Leftrightarrow a \in A \vee a \in B \Leftrightarrow P(a) \vee Q(a)\strut$$

である． $\Box$

例 1.54  

$\{x\in \mathbb{R}\!\bigm \vert \!(x-2)(x-3)>0\}\strut= \{x\in \mathbb{R}\!\bigm \vert\!x < 2\}\strut\cup \{x\in \mathbb{R}\!\bigm \vert \!x > 3\}\strut$

定理 1.55   集合$A,B,C$に対し，次の関係式が成り立つ ．

1. $A\cup A=A$
2. $A\cup B=B\cup A$
3. $A\cup (B\cup C)=(A\cup B) \cup C\strut$
4. $A\subseteq A\cup B, B\subseteq A\cup B$
5. $A,B\subseteq C \rightarrow A\cup B\subseteq C$

証明： 1: $x\in A\cup A \Leftrightarrow [x\in A \vee x\in A] \Leftrightarrow x\in A\strut$

2: $x\in A\cup B \Leftrightarrow [x\in A \vee x\in B] \Leftrightarrow [x\in B \vee x\in A] \Leftrightarrow x\in B\cup A\strut$

3: $x\in A\cup (B\cup C) \Leftrightarrow [x\in A \vee x\in B \vee x\in C] \Leftrightarrow x \in (A\cup B)\cup C\strut$

4: $x\in A \rightarrow x\in A \vee x\in B$

5: $A, B \subseteq C , x \in A\cup B$とする．場合に分けて証明する．

$x\in A$が成り立つとき， $A\subseteq C$より$x\in C$である．

$x\in B$が成り立つとき， $B\subseteq C$より$x\in C$である．

いずれの場合も$x\in C$が成り立つ． $\Box$

    定理1.55 の5.の証明にあるように， $A\cup B \subseteq C$の形の命題を証明するには 場合わけを用いることが多い．具体的には，$x\in A$と$x\in B$の場合にわけて． $x\in A \rightarrow x \in C$と $x \in B \rightarrow x \in C$を示すのである．

問題 1.56   $A\subseteq B \Leftrightarrow A\cup B=B$を示せ．

1.5.2 共通部分

二つの集合$A,B$に対し，$A$か$B$のいずれにも属する元の全体からなる集合を， $A$と$B$の共通部分，交わり(intersection)とよび， $A\cap B$で表す．すなわち， $A\cap B:=\{x\bigm \vert x\in A \wedge x\in B\}\strut$である．

共通部分を表すのに記号$\cap$を最初に用いたのはGiuseppe Peano (1858-1932) である． [7]

命題 1.57  

$A:=\{x\bigm \vert P (x)\}$, $B:=\{x\bigm \vert Q (x)\}$のとき，

$$A\cap B =\{x \bigm \vert P (x) \wedge Q (x)\}\strut$$

である．

証明： $a \in A \Leftrightarrow P(a) , a \in B \Leftrightarrow Q(a)\strut$ より，

$$a \in A\cap B \Leftrightarrow a \in A \wedge a \in B \Leftrightarrow P(a) \wedge Q(a)\strut$$

である． $\Box$

例 1.58  

$\{x\in \mathbb{R}\!\bigm \vert \!(x-2)(x-3)<0\}\strut=\{x\in \mathbb{R}\!\bigm \vert\!x > 2\}\strut\cap \{x\in \mathbb{R}\!\bigm \vert \!x < 3\}\strut$

定理 1.59   集合$A,B,C$に対し，次の関係式が成り立つ．

1. $A\cap A=A$
2. $A\cap B=B\cap A$
3. $A\cap (B\cap C)=(A\cap B) \cap C\strut$
4. $A\cap B\subseteq A, A\cap B \subseteq B$
5. $C\subseteq A, B \rightarrow C\subseteq A\cap B$
6. $A\subseteq B \Leftrightarrow A\cap B=A$

証明： 証明は定理1.55の証明と同様にできる． $\Box$

問題 1.60   定理1.59を証明せよ．

$A\cap B =\varnothing$のとき，$A$と$B$は互いに素(mutually disjoint)であるとよばれる．

1.5.3 和集合と共通部分の関係

定理 1.61   集合$A,B,C$に対し，次の関係式が成り立つ．

1. $A\cup (B\cap C)=(A\cup B)\cap (A\cup C)\strut$
2. $A\cap (B\cup C)=(A\cap B)\cup (A\cap C)\strut$
3. $A\cup (A\cap B)=A\strut$    ,     $A\cap (A\cup B)=A\strut$

問題 1.62   定理1.61を証明せよ．

問題 1.63   $A \subseteq B \subseteq C \Leftrightarrow A\cup B=B\cap C$を示せ．

1.5.4 差集合

二つの集合$A,B$に対し，$A$に属する元で$B$に属さないものの全体からなる集合を， $A$から$B$を引いた差集合(difference)とよび，$A-B$（あるいは $A\backslash B\strut$）で表す． すなわち， $A- B:=\{x\bigm \vert x\in A \wedge x\notin\strut B\}\strut$である．

定義より $A-B\subseteq A, (A-B)\cap B=\varnothing\strut$が常に成り立つ．

問題 1.64   $(A-B)\cup (A\cap B)=A\strut$を示せ．

命題 1.65  

$A:=\{x\bigm \vert P (x)\}$, $B:=\{x\bigm \vert Q (x)\}$のとき，

$$A- B =\{x \bigm \vert P (x) \wedge \neg Q (x)\}\strut$$

である．

証明： $a \in A-B \Leftrightarrow a \in A \wedge a \notin\strut B \Leftrightarrow P(a) \wedge \neg Q(a)$より明らか． $\Box$

命題 1.66  

$A\subseteq C$ かつ $D\subseteq B$ならば $A-B \subseteq C-D$

証明： $x \in A-B$とする． $x \in A \wedge x \notin\strut B$である．このとき， $A\subseteq C$より$x\in C$であり， $D\subseteq B$より $x \notin\strut D$である． 従って， $x \in C \wedge x \notin\strut D$，すなわち$x \in C-D$である． $\Box$

問題 1.67   $A\subseteq B \Leftrightarrow A-B=\varnothing$であることを示せ．

問題 1.68   $A-(A-B)=A\cap B\strut$を示せ．

問題 1.69   $A,B\subseteq X$とする． $A\cap B=\varnothing \Leftrightarrow A \subseteq X-B$を示せ．

問題 1.70   $(A-C)\subseteq (A-B)\cup (B-C)\strut$を示せ．

定理 1.71 (ド・モルガンの法則)   集合$A,B,C$に対し，次の関係式が成り立つ．

1. $A-(B\cup C)=(A-B)\cap (A-C)\strut$
2. $A-(B\cap C)=(A-B)\cup (A-C)\strut$

証明： $1$:

$\phantom{ \Leftrightarrow }x \in A-(B\cup C)\strut$

$\Leftrightarrow x \in A \wedge x \notin\strut (B\cup C)$

$\Leftrightarrow x \in A \wedge [ x \notin\strut B \wedge x \notin\strut C]$

$\Leftrightarrow [x \in A \wedge x \notin\strut B ] \wedge [x \in A \wedge x \notin\strut C]$

$\Leftrightarrow x \in A-B \wedge x \in A-C$

$\Leftrightarrow x \in (A-B)\cap (A-C)\strut$

$2$:

$\phantom{ \Leftrightarrow }x \in A-(B\cap C)\strut$

$\Leftrightarrow x \in A \wedge x \notin\strut (B\cap C)$

$\Leftrightarrow x \in A \wedge [ x \notin\strut B \vee x \notin\strut C]$

$\Leftrightarrow [x \in A \wedge x \notin\strut B ] \vee [x \in A \wedge x \notin\strut C]$

$\Leftrightarrow x \in A-B \vee x \in A-C$

$\Leftrightarrow x \in (A-B)\cup (A-C)\strut$ $\Box$

問題 1.72   次を示せ．

1. $(A\cup B)-C=(A-C)\cup (B-C)\strut$
2. $(A\cap B)-C=(A-C)\cap (B-C)\strut$
3. $(A-B)\cap C = (A\cap C)-B\strut$
4. $(A-B)\cup C \supseteq (A\cup C)-B\strut$

問題 1.73   $(A-B)\cup C \subseteq (A\cup C)-B\strut$は必ずしも成り立たない． 反例を挙げよ．

$(A-B)\cup (B-A)\strut$を$A$と$B$の対称差とよび， $A\triangle B\strut$で表す．

定理 1.74   集合$A,B,C$に対し，次の関係式が成り立つ．

1. $A\triangle B=B\triangle A\strut$
2. $A\triangle (B\triangle C)=(A\triangle B)\triangle C\strut$
3. $A\triangle \varnothing =A\strut$
4. $A\triangle A=\varnothing\strut$
5. $A\triangle B=\varnothing \Leftrightarrow A=B\strut$

証明： 1,3,4は定義より明らか．5も問題1.67より明らか． 2を示す．

$$A\triangle (B\triangle C)=(A-(B\cup C))\cup (B-(C\cup A))\cup (C-(A\cup B)) \cup (A\cap B\cap C)$$

を（左辺を定義にしたがってがんばって計算して）示せば，右辺の式で$A$と$C$を入れ換えても同じ集合を 表わすから， $A\triangle (B\triangle C)= C\triangle (B\triangle A)\strut$である．1より $A\triangle B=B\triangle A\strut$ でさらに $C\triangle (B\triangle A)=(B\triangle A)\triangle C\strut$であるから $A\triangle (B\triangle C)=(A\triangle B)\triangle C\strut$である． $\Box$

問題 1.75   $A\triangle (A\triangle B)=B\strut$を示せ．

問題 1.76  

$$A\triangle (B\triangle C)=(A-(B\cup C))\cup (B-(C\cup A))\cup (C-(A\cup B)) \cup (A\cap B\cap C)\strut$$

を示せ．

問題 1.77   $A\triangle B=C\triangle D\strut$ならば， $A\triangle C=B\triangle D\strut$であることを示せ． （ヒント：ごりごり計算してもできるが，定理 1.74の2と5を使うとエレガントにできる．）

一般に与えられた集合$X$の元や$X$の部分集合のみを考察の対象にするとき， $X$を全体集合，全集合(universal set)とよぶ．全体集合として$X$を考えているとき， $X-A$を$A$の（$X$に関する）補集合(complement)とよび，$A^{c}$で表す．ド・モルガンの法則より次の定理が成り立つ．

定理 1.78 (ド・モルガンの法則)   全体集合を$X$とするとき，集合$A,B$に対し，次の関係式が成り立つ．

1. $(A\cup B)^{c}=A^{c}\cap B^{c}\strut$
2. $(A\cap B)^{c}=A^{c}\cup B^{c}\strut$

証明： $(A\cup B)^{c}=X-(A\cup B),(A\cap B)^{c}=X-(A\cap B), A^{c}=X-A, B^{c}=X-B$ であるから，定理 1.71より定理が導かれる． $\Box$

問題 1.79   全体集合を$X$とするとき，集合$A,B$に対し次の関係が成り立つことを示せ．

$$A\cap B=\varnothing \Leftrightarrow A \subseteq B^{c} \Leftrightarrow B \subseteq A^{c}$$

1.5.5 直積集合

二つの集合$A,B$に対し，$A$の元$a$と$B$の元$b$を一つの組にして $(a,b)\strut$で表すことにする¹³． このような組のことを順序対(ordered pair)とよぶ． $(a,b)\strut$において，$a$を第１成分，$b$を第２成分とよぶ．順序対の相等は

$(a,b)=(c,d)\strut$ $\stackrel{\mathrm{def}}{ \Leftrightarrow }\strut$ $a=c \wedge b=d$

により定義¹⁴する．平面上の点の$xy$座標は，順序対の例である．$A$の元と$B$の元から作られる 順序対の全体を$A\times B$で表し，$A$と$B$の直積(direct product)とよぶ．

$$A\times B:=\{(a,b)\bigm \vert a\in A \wedge b\in B\}\strut$$

$A\times B$と$B\times A$は異なるものであることに注意せよ．また，任意の集合$A$に対して， $\varnothing\times A=A\times\varnothing =\varnothing$とする．

例 1.80  

$A:=\{1,2,3\}\strut, B:=\{1,2\}\strut$とすると， $A\times B = \{(1,1),(1,2),(2,1),(2,2),(3,1),(3,2)\}\strut$である．

例題 1.81   任意の集合$A,B,C$に対し， $A\times (B\cup C)=(A\times B)\cup (A\times C)\strut$が成り立つことを示せ．

解： 1.32より、任意の $a\in A , b\in B\strut$に対し、

$$(a,b)\in A\times (B\cup C) \Leftrightarrow (a,b) \in (A\times B)\cup (A\times C)\strut$$

を示せば良い。

$(a,b)\in A\times (B\cup C)\strut$

$\Leftrightarrow a \in A \wedge b \in B\cup C\strut$

$\Leftrightarrow a \in A \wedge [b \in B \vee b \in C]\strut$

$\Leftrightarrow [a \in A \wedge b \in B] \vee [a \in A \wedge b \in C]\strut$

$\Leftrightarrow [(a,b)\in A\times B ] \vee [(a,b)\in A\times C ]\strut$

$\Leftrightarrow (a,b) \in (A\times B)\cup (A\times C)\strut$ $\Box$

問題 1.82   任意の集合$A,B,C$に対し，次の関係が成立することを示せ．

1. $A\times (B\cap C)=(A\times B)\cap (A\times C)\strut$
2. $(B\cup C)\times A=(B\times A)\cup (C\times A)\strut$
3. $(B\cap C)\times A=(B\times A)\cap (C\times A)\strut$
4. $A=B\cap C$ならば $A\times A=(B\times B)\cap (C\times C)\strut$

問題 1.83   $A=B\cup C$ならば $A\times A=(B\times B)\cup (C\times C)\strut$は正しいか．正しければ証明し，間違っているならば 反例をあげよ．

問題 1.84   順序対の定義では，順序対 $(a,b)\strut$は，$a$と$b$を形式的に順序つけて並べたものと考えている． そうではなくて，順序対 $(a,b)\strut$を$a$と$b$から作られる特別の集合と考えることもできる． $(a,b):=\{\{a,b\}\strut,\{a\}\strut\}\strut$とおくと，

$$(a,b)=(c,d) \Leftrightarrow a=c \wedge b=d\strut$$

が成り立つ．これを示せ．

順序対の概念を， $(a,b,c)\strut$や $(a,b,c,d)\strut$のような３つ組や４つ組などに拡張することで， 集合$A,B,C$の直積 $A\times B\times C$，集合$A,B,C,D$の直積 $A\times B\times C\times D$ などを定義することができる．また， $A\times A , A\times A \times A , A\times A \times A \times A ,\cdots$ を $A^2 , A^3 , A^4 ,\cdots \strut$で表すことにする．

1.5.6 べき集合

集合$A$の部分集合をすべて集めてできる集合を，$A$のべき集合(power set)とよび， ${\cal P}(A)\strut$で表す． $X\in {\cal P}(A) \Leftrightarrow X\subseteq A\strut$である．

例 1.85  

集合 $A:=\{1,2,3\}\strut$のべき集合 ${\cal P}(A)\strut$は，

$${\cal P}(A)=\{\varnothing , \{1\}\strut,\{2\}\strut,\{3\}\strut,\{1,2\}\strut,\{2,3\}\strut,\{1,3\}\strut,\{1,2,3\}\strut\}\strut$$

である．

定理 1.86   $A$の元の個数が$n$個であるとき，$A$のべき集合 ${\cal P}(A)\strut$は$2^n$個の元をもつ．

証明： $A=\{1,2,3,\cdots ,n\}\strut$としても一般性を失わわない¹⁵．このとき，$A$の部分集合の取り方は $1$を含むか含まないか，$2$を含むか含まないか，$3$を含むか含まないか，$\cdots$，$n$を含むか含まないか で決まるから，その総数は $\underbrace{2\times 2\times 2\times\cdots 2}_{n}=2^n$である． $\Box$