日記2

自然演繹を積極的に用いたい．

定理2.7(ド・モルガンの法則)

福田拓生『集合への入門(無限をかいま見る)』培風館 2018

ド・モルガンの法則　20項

$∀x［x∈\mathbb{N}→∀x［x∈\mathbb{N}→∃x［x∈\mathbb{N}∧x=a］］］$

$x=［i,n］_{\mathbb{N}}$ 　(二重∀-除去)　s.t.　 $i:=1$

$A,B,C,A_1,A_2,......,A_n：1つの集合$

とする．このとき，次の等式が成立する．

(ⅰ)　 $C-(A∪B)=(C-A)∩(C-B)$

(ⅱ)　 $C-(A∩B)=(C-A)∪(C-B)$

(ⅲ)　 $C-(\bigcup_{i=1}^{n}A_i)=\bigcap_{i=1}^{n}(C-A_i)$

(ⅳ)　 $C-(\bigcap_{i=1}^{n}A_i)=\bigcup_{i=1}^{n}(C-A_i)$

(証明)

(ⅰ)について

$P:=C-(A∪B)$

$Q:=(C-A)∩(C-B)$

と置く．

$∀x［x∈P→∀x［x∈P→∃x［x∈P∧x=a］］］$

$x=［a］_P$ 　(二重∀-除去)　s.t.　

(ア)　 $a∈P→a∈Q$

(イ)　 $a∈P←a∈Q$

を示す．

(ア)に関して

0,1　　(1)　 $a∈P$ 　　仮定

i.e.　 $a∈C∧￢(a∈A∨a∈B)$

0,1　　(2)　 $a∈C$ 　　1.∧-除去

0,1　　(3)　 $a∈C∨a∈A$ 　　2.∨-導入

4　　 (4)　 $￢(a∈A)$ 　　仮定

0,1,4　 (5)　 $a∈C$ 　　3,4.三段論法

0,1,4　 (6)　 $a∈C∧￢(a∈A)$ 　　4,5.∧-導入

i.e.　 $a∈C-A$

7　　 (7)　 $￢(a∈B)$ 　　仮定

0,1,4,7 (8)　 $a∈C∧￢(a∈B)$ 　　5,7.∧-導入

i.e.　 $a∈C-B$

0,1,4,7 (9)　 $a∈C-A∧a∈C-B$ 　　6,8.∧-導入

i.e.　 $a∈(C-A)∩(C-B)$

0,1,4　 (10)　 $a∈P→a∈Q$ 　　1-9.→-導入

　　　 (11)　 $a∈P→a∈Q$ 　　3-10.∨-除去

　　　 (12)　 $x∈P→x∈Q$ 　　11.二重∀-導入

(イ)に関して

$∀x［x∈Q→∀x［x∈Q→∃x［x∈Q∧x=a］］］$

$x=［a］_Q$ 　(二重∀-除去)　s.t.

0,1　　(1)　 $a∈Q$ 　　仮定

i.e.　 $a∈C∧￢(a∈A)∧a∈C∧￢(a∈B)$

0,1　　(2)　 $a∈C$ 　　1.∧-除去

3　　 (3)　 $a∈A∪B$ 　　仮定

i.e.　 $a∈A∨a∈B$

0,1　　(4)　 $￢(a∈A)$ 　　1.∧-除去

0,1,3　 (5)　 $a∈B$ 　　3,4.三段論法

0,1　　(6)　 $￢(a∈B)$ 　　1.∧-除去

0,1,3　 (7)　 $\perp$ 　　5,6.￢-除去

0,1　　(8)　 $￢(a∈A∪B)$ 　　3-7.￢-導入

0,1,3　 (9)　 $a∈C∧￢(a∈A∪B)$ 　　3,8.∧-導入

i.e.　 $a∈C-(A∪B)$

0,1　　(10)　 $a∈Q→a∈P$ 　　1-9.→-導入

　　　 (11)　 $a∈Q→a∈P$ 　　3-10.∨-除去

　　　 (12)　 $x∈Q→x∈P$ 　　11.二重∀-導入

(ⅱ)も同様に示される．

(ⅲ)について

$P:=C-(\bigcup_{i=1}^{n}A_i)$

$Q:=\bigcap_{i=1}^{n}(C-A_i)$

と置く．このとき

(ア)　 $P→Q$

(イ)　 $Q→P$

を示す．

(ア)に関して

$∀x［x∈P→∀x［x∈P→∃x［x∈P∧x=a］］］$

$x=［a］_P$ 　(二重∀-除去)　s.t.　

$a∈P→a∈Q$

を示す．

0,1　　(1)　 $a∈P$ 　　仮定

0,1　　(2)　 $a∈C$ 　　1.∧-除去

0,1　　(3)　 $a∈C∨a∈A$ 　　2.∨-導入

4　　 (4)　 $￢(a∈A)$ 　　仮定

0,1,4　 (5)　 $a∈C$ 　　3,4.三段論法

6　　 (6)　 $￢(a∈Q)$ 　　仮定

0,1　　(7)　 $￢(\bigcup_{i=1}^{n}A_i)$ 　　1.∧-除去

8　　 (8)　 $a∈\displaystyle\bigcup_{i=1}^{n}A_i$ 　　仮定

0,1,8　 (9)　 $\perp$ 　　7,8.￢-除去

0,1,6　 (10)　 $￢￢(a∈Q)$ 　　6-8.￢-導入

0,1,6　 (11)　 $a∈Q$ 　　10.DN規則

0,1　　(12)　 $a∈P→a∈Q$ 　　1-11.→-導入

　　　 (13)　 $a∈P→a∈Q$ 　　3-12.∨-除去

　　　 (14)　 $x∈P→x∈Q$ 　　13.二重∀-導入

(イ)に関しても同様．

(ⅳ)も同様．▢