思考の論理入門の授業メモ14

全称量化子は議論領域が有限ならば、∧(連言)で結べば表せる

つまり全称量化子が力を発揮するのは、議論領域が無限の領域の場合

全称量化子は無限の領域を扱える

例題1

(∀x)(Fx→Gx),Fa⊢Ga

1 (∀x)(Fx→Gx) 前提

2 Fa 前提

1 Fa→Ga 1 ∀除去

1,2 Ga 2,3,→除去

例題2

(∀x)(Fx→Gx),(∀x)(Gx→Hx)⊢Fa→Ha

1 (∀x)(Fx→Gx) 前提

2 (∀x)(Gx→Hx) 前提

3 Fa 仮定

1 Fa→Ga 1∀除去

2 Ga→Ha 2∀除去

1,3 Ga 1,3,→除去

1,2,3 Ha 5,6,→除去

1,2 Fa→Ha 3-7,→導入

問題2

(∀y)Fy⊢Fb

1 (∀y)Fy 前提

1 Fb 1,∀除去

(∀x)(Fx→Gx),(∀y)Fy⊢Ga

1 (∀x)(Fx→Gx) 前提

2 (∀y)Fy 前提

1 Fa→Ga 1,∀除去

2 Fa 2,∀除去

1,2 Ga 3,4,→除去

(∀x)(Fx→Gx),¬Gb⊢¬Gb

1 (∀x)(Fx→Gx) 前提

2 ¬Gb 前提

3 Fb 仮定

1 Fb→Gb 1,∀除去

1,3 Gb 1,3,→除去

1,2,3 ⊥ 2,5,¬除去

1,2 ¬Fb 3-6,¬導入

∀導入

At⊢(∀x)Ax

具体的なものを一つ持ってきて証明を行うが、その個体の具体的性質に依存しないように示す

tは自由変数

∀導入の条件

Atの前提に個体定項tが使われていない

使われているっていうのはBt⊢Atみたいになっていること

Btはtの性質を使ってしまっている

束縛変数がAtの中に現れていない

二重束縛を防ぐ

Atのイメージは

Aa,Ab,Ac,Ad,Ae,………という無限の文もしくはその連言

例題3

(∀x)(Fx→Gx),(∀x)(Gx→Hx)⊢(∀x)(Fx→Hx)

例題2とほとんど同じ感じ

1 (∀x)(Fx→Gx) 前提

2 (∀x)(Gx→Hx) 前提

3 Fa 仮定

1 Fa→Ga 1,∀除去

2 Ga→Ha 2,∀除去

1,3 Ga 1,3,→除去

1,2,3 Ha 5,6,→除去

1,2 Fa→Ha 3-7,→導入

1,2 (∀x)(Fx→Hx) 8,∀導入

1,2にはaは現れていない(変項条件を満たす)

問題3

(∀x)Fx∧(∀x)(Fx→ Gx)⊢(∀y)Gy

1 (∀x)Fx∧(∀x)(Fx→ Gx) 前提

1 (∀x)Fx 1,∧除去

1 (∀x)(Fx→ Gx) 1,∧除去

1 Fa 2,∀除去

1 Fa→Ga 3,∀除去

1 Ga 3,4,→除去

1 (∀y)Gy 6,∀導入

条件を満たしている

(∀x)(Fx→(∀y)Gy)⊢(∀x)(∀y)(Fx→Gy)

1 (∀x)(Fx→(∀y)Gy) 前提

2 Fa 仮定

1 Fa→(∀y)Gy 1,∀除去

1,2 (∀y)Gy 2,3,→除去

1,2 Gb 4,∀除去

1 Fa→Gb 2-5,→導入

1 (∀y)(Fa→Gy) 6,∀導入

条件を満たす

1 (∀x)(∀y)(Fx→Gy) 7,∀導入

条件を満たす

存在量化子の導入

At⊢(∃x)Ax