ド・モルガンの法則の数学的帰納法による証明

K大理学部に進んだ友人が、レポート課題としてド・モルガンの法則の証明を課されていた。

そういえば一度も証明したことないなあ、と自省しつつ、この際なので証明してみる。

明らかに数学的帰納法向きの問題なので実際に数学的帰納法 *1を用いて証明した。(案の定)新規性は全くないようである。試しにde morgan inductionとか検索してみればいかに有り触れているかわかる。

◆ド・モルガンの法則*2

任意の集合 $A_i (i=1,2,\cdots,n,n \geq 2)$ について、 $\displaystyle \bigcup_{i=1}^n A_i ^c=( \bigcap_{i=1}^n A_i) ^c ~~ \land ~~ \bigcap_{i=1}^n A_i ^c=( \bigcup_{i=1}^n A_i) ^c$ が成立する。

◆証明

以下、全体集合を一般に $U$ とおく。

[I] $n=2$ の場合

　(ベン図から明らかであるが、念のため簡単に証明を述べる。)

　 $U$ の要素を $x$ とすると、

　 $x \in A_1^c \cup A_2^c \Leftrightarrow x \in A_1^c \lor x \in A_2^c \Leftrightarrow x \in (A_1 \cap A_2)^c$ 　 $\displaystyle \therefore \bigcup_{i=1}^2 A_i ^c=( \bigcap_{i=1}^2 A_i) ^c$

　 $x \in A_1^c \cap A_2^c \Leftrightarrow x \in A_1^c \land x \in A_2^c \Leftrightarrow x \in (A_1 \cup A_2)^c$ 　 $\displaystyle \therefore \bigcap_{i=1}^2 A_i ^c=( \bigcup_{i=1}^2 A_i) ^c$

　したがって、 $n=2$ で成立する。 $\cdots (a)$

[II] $n=k+1 (k \in \mathbb{N},k \geq 2)$ の場合

　 $n=k$ での成立、すなわち $\displaystyle \bigcup_{i=1}^k A_i ^c=( \bigcap_{i=1}^k A_i) ^c ~~ \land ~~ \bigcap_{i=1}^k A_i ^c=( \bigcup_{i=1}^k A_i) ^c \cdots (\star)$ を仮定する。

　このもとで、

　 $\displaystyle \bigcup_{i=1}^{k+1} A_i^c= (\bigcap_{i=1}^k A_i )^c \cup A_{k+1}^c ~~ (\because (\star) ~) =( \bigcap_{i=1}^{k+1} A_i) ^c ~~ (\because (a) ~)$

　 $\displaystyle \bigcap_{i=1}^{k+1} A_i ^c=( \bigcup_{i=1}^k A_i) ^c \cap A_{k+1}^c~~ (\because (\star) ~) = ( \bigcup_{i=1}^{k+1} A_i) ^c ~~ (\because (a) ~)$

　であるから、 $n=k$ で成立するならば、 $n=k+1$ でも成立する。 $\cdots (b)$

$(a),(b)$ より、任意の $n$ に対し、 $\displaystyle \bigcup_{i=1}^n A_i ^c=( \bigcap_{i=1}^n A_i) ^c \land \bigcap_{i=1}^n A_i ^c=( \bigcup_{i=1}^n A_i) ^c$ が成立することが示された。

◆コメント

一発目の記事なので小手調べである。非常に簡単。

*1:なお、ド・モルガン(数学者)は数学的帰納法の厳密化・定式化にも貢献している。

*2:何故ド・モルガンの"定理"でないのかよく分からない。

666 feet under

R.I.P. what was in my skull

ド・モルガンの法則の数学的帰納法による証明