こんにちは！ケンけんです。この記事は、集合に関する問題をいろいろ提示・証明を与えるものです。
勉強に役立ててください。
必要知識：集合(NST-8~NST-13)
以降の集合はすべて普遍集合$U$の中で考えます。
はじめに
集合の調べ方は、次の通りです。
- 「$X \subset Y$」は$X$の任意の元が$Y$の元であること
- 「$X=Y$」は$X \subset Y$と$Y \subset X$であること
この問題集の中では、論理記号「$\Rightarrow$」や「$\iff$」を用いることもあります。
しかし、証明を書く、解答を書くと言う点ではあまり命題論理の記号を使わないようにします。許されるのは集合の記号「$\in , \subset ,=$」ぐらいです。なので、なるべく上2つの記号を使わないように書くよう心がけます。つまり次のように記号を言い換えていきます。
- $\wedge$＝「かつ」
- $\vee$=「または」
- $\Rightarrow$=「ならば」
どうしても使った方がきれいに書ける場合は、「一行使って行替えして記述」や”「」”でくくって明記するといいと思われます。どうしても言葉で書きたい場合は、記号を上のように読み替えるといいでしょう。
また、集合の一致「$=$」は同値関係、集合の包含関係は「半順序関係」であることは認めます。
空集合は、論理では恒偽命題による集合としてであったがこれは従来の元を持たない集合として考えてよい。従って、「$X=\emptyset$」と示したい場合は$x \in X$の存在を仮定して矛盾を導く「背理法」も有効です。
共通部分の問題
$X,Y,Z,W$を集合とする. このとき, 以下の主張が成り立つ.
- $X \cap Y \subset X , Y$,
- $X \cap Y=X \iff X \subset Y$,
- $X \subset Y,Z \Rightarrow X \subset Y \cap Z$,
- $(X \subset Y) \wedge (Z \subset W) \Rightarrow X \cap Z \subset Y \cap W$,
- $(X \cap Y) \cap Z=X \cap (Y \cap Z)$,
- $X \cap Y=Y \cap X$,（共通部分の可換律）
- $X \cap U=X$,
- $X \cap \emptyset=\emptyset$.
1. $x \in X \cap Y$を取ると, 「$(x \in X) \wedge (x \in Y)$」は真である.
従って, $x \in X$から「$X \cap Y \subset X$」,「 $x \in Y$」から$X \cap Y \subset Y$である.
2. 1.より$X \cap Y \subset Y$である.
$X=X \cap Y$から, $X \subset Y$である.
逆に, $X \subset Y$のとき「$ x\in X \Rightarrow (x \in X) \wedge (x \in Y)$」が常に真でる.
従って, 「$x \in X$ならば$x \in X \cap Y$」であり$X \subset X \cap Y$である.
逆の包含は, 1.より明らかである.
3. $X \in X$を取ると, 「$X \subset Y$から$x \in Y$, 「$X \subset Z$から$x \in Z$」である.
従って, $(x \in Y)$かつ$(x \in Z)$より$x \in Y \cap Z$である.
以上から, $X \subset Y \cap Z$である.
4. $x \in X \cap Z$を取ると, $x \in X \subset Y$かつ$x \in Z \subset W$である.
従って, $x \in Y$かつ$x \in W$より$x \in Y \cap W$で$X \cap Z \subset Y \cap W$ある.
5. 論理積の結合律より「$x \in (X \cap Y) \cap Z \iff x \in X \cap (Y \cap Z)$」である.
従って, $(X \cap Y) \cap Z=X \cap (Y \cap Z)$である.
$x \in X \cap (Y \cap Z)$に対して, $(X \cap Y) \cap Z \subset X \cap (Y \cap Z)$である.
逆の包含関係も同様に示される.
6. 論理積の可換律より, 「$x \in X \cap Y \iff x \in Y \cap X$」である.
従って, $X \cap Y = Y \cap X$である.
逆の包含は先の同値から明らかである.
7. $X \subset U$から2.を利用し$X \cap U =X$である.
8. $\emptyset$はすべての$U$の集合の部分集合より$\emptyset \subset X$である.
2.より$\emptyset \cap X =\emptyset $である.
$\square$
和集合の問題
$X,Y,Z,W$を集合とする. このとき, 以下の主張が成り立つ.
- $X,Y \subset X \cup Y$,
- $X \cup Y=X \iff Y \subset X$,
- $X,Y \subset Z \Rightarrow X \cup Y \subset Z$,
- $(X \subset Y) \wedge (Z \subset W) \Rightarrow X \cup Z \subset Y \cup W$,
- $(X \cup Y) \cup Z=X \cup (Y \cup Z)$,
- $X \cup Y=Y \cup X$,（和集合の可換律）
- $X \cup U=U$,
- $X \cup \emptyset =X$.
1. 「$x \in X \Rightarrow (x \in X) \vee (x \in Y)$」より$x \in X \cup Y$である.
$Y$も同様である.
2. 1.より$Y \subset X \cup Y =X$だから$Y \subset X$である.
逆に$Y \subset X$のとき, $x \in X \cup Y$を取る.
このとき, 「$(x \in X) \vee (x \in Y)$」が真である.
$Y \subset X$から$x \in Y$ならば$x \in X$より$x \in X$となる.
従って, $X \cup Y \subset X$であり逆の包含は1.から明らかである.
3. $x \in X \cup Y$を取ると, $x \in X \subset Z$または$x \in Y \subset Z$である.
従って, $x \in Z$であり$X \cup Y \subset Z$である.
4. $x \in X \cup Z$を取ると, $x \in X \subset Y$または$x \in Z \subset W$である.
従って, $x \in Y$または$x \in W$より$x \in Y \cup W$である.
以上から, $X \cup Z \subset Y \cup W$である.
5. 論理和の結合律より「$x \in (X \cup Y) \cup Z \iff x \in X \cup (Y \cup Z)$」である.
従って, $(X \cup Y) \cup Z=X \cup (Y \cup Z)$である.
6. 論理和の可換律より, 「$x \in X \cup Y \iff x \in Y \cup X$」である.
従って, $X \cup Y = Y \cup X$である.
7. $X \subset U$から2.を利用し,$U \cup X = U$である.
8. $\emptyset \subset X$から2.を利用し, $X \cup \emptyset =X$である.
$\square$
補集合の問題
$X,Y,Z$を集合とする. このとき, 以下の主張が成り立つ.
- $X \subset Y \iff Y^{c} \subset X^{c}$,
- $X^{c}=U \iff X=\emptyset$,
- $X^{c}=\emptyset \iff X=U$,
1. $X \subset Y$を仮定すると$x \in X \rightarrow x \in Y$である.
対偶より,「$x \notin Y \Rightarrow x \notin X$」である.
従って, 「$x \in Y^{c} \Rightarrow x \in X^{c}$」であり$Y^{c} \subset X^{c}$である.
$Y^{c} \subset X^{c}$を仮定した場合, 「$x \notin Y \Rightarrow x \notin X$」の対偶を考えれば十分である.
2.と3.はNST-11の考察より明らかである.
$\square$
2つ以上の演算を使った問題
$X,Y,Z,W$を集合とする. このとき, 以下の主張が成り立つ.
- $(X \cap Y) \cup Z=(X \cup Z) \cap (Y \cup Z)$,
- $(X \cup Y ) \cap Z=(X \cap Z) \cup (Y \cap Z)$,
- $(X \cap Y)^{c}=X^{c} \cup Y^{c}$,
- $(X \cup Y)^{c}=X^{c} \cap Y^{c}$,
- $X \cap Y^{c}=\emptyset \iff X \subset Y$,
- $(X^{c})^{c}=X$,（二重否定）
- $X \cup X^{c}=U$,
- $X \cap X^{c}=\emptyset$.
1. 「$x \in (X \cap Y) \cup Z \iff ((x \in X) \wedge (x \in Y)) \vee (x \in Z)$」である.
命題論理の分配律より, 次の同値命題を得る.
$((x \in X) \wedge (x \in Y)) \vee (x \in Z) \Leftrightarrow ((x \in X)\vee (x \in Z)) \wedge ((x \in Y ) \vee (x \in Z))$.
従って, 次の同値によって$(X \cap Y) \cup Z=(X \cup Z) \cap (Y \cup Z)$である.
$x \in (X \cap Y) \cup Z \Leftrightarrow (x \in X \cup Z) \cap (x \in Y \cup Z) \Leftrightarrow x \in (X \cup Z) \cap (Y \cup Z)$.
2. 1.と同様に命題論理より,$(X \cup Y ) \cap Z=(X \cap Z) \cup (Y \cap Z)$が成り立つ.
$((x \in X) \vee (x \in Y)) \wedge (x \in Z) \Leftrightarrow ((x \in X)\wedge (x \in Z)) \vee ((x \in Y ) \wedge (x \in Z))$.
3.と4.は,命題論理のドモルガンの法則を利用する.
3.について「$x \notin X \cap Y \Leftrightarrow (x \notin X) \cup (x \notin Y)$」から従う.
4.について「$x \notin X \cup Y \Leftrightarrow (x \notin X) \cap (x \notin Y)$」から従う.
5. $X \cap Y^{c}=\emptyset$を仮定し,$x \in X$を取る.
仮定から,$x \notin Y^{c}$から$x \in Y$であるため$X \subset Yである$.
$X \subset Y$を仮定し, $x \in X \cap Y^{c}$を取る.
$x \in Y^{c}$より$x \notin Y$だが, $x \in X \subset Y$に矛盾する.
従って, $X \cap Y^{c}=\emptyset$である.
6. 2重否定の恒真命題から「$x \in (X^{c})^{c}\Leftrightarrow x \notin X^{c} \Leftrightarrow x \in X$」である.
従って,$(X^{c})^{c}=X$である.
7. $X =\{x \in U|P(x)\}$と表すと,$x \in U$に対して$P(x) \vee \neg(P(x))$は恒真命題である.
従って,$X \cup X^{c}=\{x \in U|P(x) \vee \neg(P(x))\}$から$U \subset X \cup X^{c}$である.
逆の包含は, $X, X^{c} \subset U$から命題2の1.から成り立つ.
8. 命題3の3.から$(X \cup X^{c})^{c}=\emptyset$である.
また, 命題4の4.から$\emptyset=(X \cup X^{c})^{c}=X^{c} \cap (X^{c})^{c}$である.
従って, 命題1の6.と命題4.の6.から$\emptyset =(X \cup X^{c})^{c}=X \cap X^{c}$である.
$\square$
おわりに
今回は、共通部分・和集合・補集合の一般性質を問題として証明も与えました。こうして証明を見ると、いかに集合が命題論理の下で成り立っているかがわかります。特にドモルガンの法則や補集合の補集合などは、命題論理からすぐに従います。証明が、怪しい場合は一度恒真命題に戻って真偽を確認すると集合の一致などがすぐにわかるようになると思われます。
以上、ケンけんでした。
関連記事
同値命題と恒真命題について
