全称判断について(部分集合の例)

$\mathbb{N}：自然数全体の集合$

$\mathbb{Z}：整数全体の集合$

$x,y,z,......：1つの束縛変数$

$a,b,c,......：1つの自由変数$

とする．このとき

$\mathbb{N}⊂\mathbb{Z}$

が成立する．

(証明の方針)

　一階述語論理で $\mathbb{N}$ が $\mathbb{Z}$ に包まれることを示したい．そのために

$∀x∈\mathbb{N}$ 　 $x∈\mathbb{N}　⇒　x∈\mathbb{Z}$

を示す．すなわち

すべての自然数 $x$ に対して $x∈\mathbb{Z}$

をいう．すなわち

$\vdash∀x［x∈\mathbb{N}→x∈\mathbb{Z}］$

を示したい．

$\vdash∀x［x∈\mathbb{N}→x∈\mathbb{Z}］$

1　　(1)　 $∀x［x∈\mathbb{N}→x∈\mathbb{Z}］$ 　　前提

1　　(2)　 $a∈\mathbb{N}→a∈\mathbb{Z}$ 　　1. ∀-除去

3　　(3)　 $a∈\mathbb{N}$ 　　仮定

1,3　 (4)　 $a∈\mathbb{Z}$ 　　2,3. →-除去

1　　(5)　 $a∈\mathbb{N}→a∈\mathbb{Z}$ 　　3-4. →-導入

1　　(6)　 $∀x［x∈\mathbb{N}→x∈\mathbb{Z}］$ 　　1,5. ∀-導入

(証明)

　前提

$∀x［x∈\mathbb{N}→x∈\mathbb{Z}］$

に対して∀-除去を適用する．このとき

$a∈\mathbb{N}→a∈\mathbb{Z}$

である．いま， $a∈\mathbb{N}$ を仮定①すると→-除去から

$a∈\mathbb{Z}$ 　　②

を得る．そして，仮定①と②について→-導入により

$a∈\mathbb{N}→a∈\mathbb{Z}$ 　③

が成立する．ここで，③に係る仮定はないので，∀-導入により

$∀x［x∈\mathbb{N}→x∈\mathbb{Z}］$

が示された．▢

$∀x［x∈\mathbb{N}］\vdash ∀x［x∈\mathbb{N}→x∈\mathbb{Z}］$

1　　(1)　 $∀x［x∈\mathbb{N}］$ 　前提

1　　(2)　 $a∈\mathbb{N}$ 　1. ∀-除去

3　　(3)　 $a∈\mathbb{Z}$ 　仮定

1　　(4)　 $a∈\mathbb{N}→a∈\mathbb{Z}$ 　2-3. →-導入

1　　(5)　 $∀x［x∈\mathbb{N}→x∈\mathbb{Z}］$ 　1,4. ∀-導入

日記2