集合
集合
問題《ド・モルガンの法則》
集合 $U$ の部分集合 $X$ に対して, $U$ に関する $X$ の補集合を $\bar X$ で表す.
このとき, $U$ の部分集合 $A,$ $B$ に対して
\[\begin{aligned}
\overline{A\cup B} &= \bar A\cap\bar B, \\
\overline{A\cap B} &= \bar A\cup\bar B
\end{aligned}\]
が成り立つ.
証明
命題論理におけるド・モルガンの法則
\[\begin{aligned}
\overline{p\text{ または }q} &\iff \bar p\text{ かつ }\bar q, \\
\overline{p\text{ かつ }q} &\iff \bar p\text{ または }\bar q
\end{aligned}\]
($\bar s$ は $s$ の否定を表す) から従う.
問題《集合の包含関係の特徴付け》
$U$ を集合とし, $A,$ $B$ をその部分集合とする.
- (i)
- $A \subset B$
- (ii)
- $A\cup B = B$
- (iii)
- $A\cap B = A$
解答例 1
(i) $\Longrightarrow$ (ii) を示すため, (i) つまり $x \in A$ $\Longrightarrow$ $x \in B$ を仮定する.
$B \subset A\cup B$ は無条件に成り立つから, $A\cup B \subset B$ を示せばよいが, これは
から従う.
(ii) $\Longrightarrow$ (i) を示すため, (ii) を仮定する. このとき, $A \subset A\cup B$ かつ $A\cup B \subset B$ から, $A \subset B$ が成り立つ.
よって, (i) $\iff$ (ii) が成り立つ.
(i) $\iff$ (iii) は,
から従う.
| $x \in A\cup B$ | $\iff$ $x \in A$ または $x \in B$ |
| $\ \,\Longrightarrow\ \,$ $x \in B$ または $x \in B$ | |
| $\iff$ $x \in B$ |
(ii) $\Longrightarrow$ (i) を示すため, (ii) を仮定する. このとき, $A \subset A\cup B$ かつ $A\cup B \subset B$ から, $A \subset B$ が成り立つ.
よって, (i) $\iff$ (ii) が成り立つ.
(i) $\iff$ (iii) は,
| $A \subset B$ | $\iff$ $\bar A \supset \bar B$ |
| $\iff$ $\bar A\cup\bar B = \bar A$ ($\because$ (i) $\iff$ (ii)) | |
| $\iff$ $\overline{\bar A\cup\bar B} = \overline{\bar A}$ | |
| $\iff$ $\overline{\bar A}\cap\overline{\bar B} = \overline{\bar A}$ ($\because$ ド・モルガンの法則) | |
| $\iff$ $A\cap B = A$ |
解答例 2
(i) $\Longrightarrow$ (iii) を示すため, (i) つまり $x \in A$ $\Longrightarrow$ $x \in B$ を仮定する.
$A\cap B \subset A$ は無条件に成り立つから, $A \subset A\cap B$ を示せばよいが, これは
から従う.
(iii) $\Longrightarrow$ (i) を示すため, (iii) を仮定する. このとき, $A \subset A\cap B$ かつ $A\cap B \subset B$ から, $A \subset B$ が成り立つ.
よって, (i) $\iff$ (iii) が成り立つ.
(i) $\iff$ (ii) は,
から従う.
| $x \in A$ | $\iff$ $x \in A$ かつ $x \in A$ |
| $\ \,\Longrightarrow\ \,$ $x \in A$ かつ $x \in B$ | |
| $\iff$ $x \in A\cap B$ |
(iii) $\Longrightarrow$ (i) を示すため, (iii) を仮定する. このとき, $A \subset A\cap B$ かつ $A\cap B \subset B$ から, $A \subset B$ が成り立つ.
よって, (i) $\iff$ (iii) が成り立つ.
(i) $\iff$ (ii) は,
| $A \subset B$ | $\iff$ $\bar A \supset \bar B$ |
| $\iff$ $\bar A\cap\bar B = \bar B$ ($\because$ (i) $\iff$ (iii)) | |
| $\iff$ $\overline{\bar A\cap\bar B} = \overline{\bar B}$ | |
| $\iff$ $\overline{\bar A}\cup\overline{\bar B} = \overline{\bar B}$ ($\because$ ド・モルガンの法則) | |
| $\iff$ $A\cup B = B$ |
解答例 3
解答例 1, 2 の前半のように, (i) $\iff$ (ii), (i) $\iff$ (iii) を別々に示す.
参考
$U$ を集合, $A_1,$ $\cdots,$ $A_n$ をその部分集合とし, $A,$ $B,$ $C,$ $D$ を $A_1,$ $\cdots,$ $A_n$ と $\cup,$ $\cap$ で表された集合とする.
- $A$ の表示において $\cup,$ $\cap$ を互いに入れ替えて得られる集合を $A$ の「双対」(dual) と呼び, $A^*$ で表す. この $A^*$ は $A_1,$ $\cdots,$ $A_n$ をそれぞれ $\overline{A_1},$ $\cdots,$ $\overline{A_n}$ に置き換えて補集合をとった集合に等しいことが「第 $1$ 双対原理」(first duality principle) として知られている.
- $A \subset B$ ならば $B^* \subset A^*$ の成り立つことが「第 $2$ 双対原理」(second duality principle) として知られている.
- $A,$ $B$ の包含関係に関する命題 $p$ と $C,$ $D$ の包含関係に関する命題 $q$ に対して, $A,$ $B,$ $C,$ $D$ をその「双対」に置き換えて包含関係を逆にした命題をそれぞれ $p^*,$ $q^*$ で表すとき, $(p \Longrightarrow q)$ ならば $(q^* \Longrightarrow p^*)$ が成り立つ. これも一種の「双対原理」と呼べる.