1階述語論理の決定不可能性

メモ

次の命題を用意する．

すなわち$ \sf Qの無矛盾な拡大理論$ \mathsf{Q} + Tは決定不能．

3. 演繹定理$ T \vdash \sigma \to \pi \iff T + \sigma \vdash \pi

Lem1

$ \mathsf{Q} + Tが無矛盾となる任意の理論$ Tは決定不能である．

proof

1. $ \sf Qは有限公理化可能だから，全ての公理を$ \landで繋いだもの$ \bigwedge \mathsf{Q}は文として取れる．

2. 本質的決定不能性より任意の理論$ Tと文$ \sigmaに対し$ \mathsf{Q} + T \vdash \sigmaは決定不能

3. 演繹定理より$ \mathsf{Q} + T \vdash \sigma \iff T \vdash \bigwedge \mathsf{Q} \to \sigma

4. したがって$ Tは決定不能である

Cor

1階述語論理は決定不能である．

proof:

$ \sf Qは無矛盾とすれば$ \sf Q + \emptysetは明らかに無矛盾だから，Lem1より$ \emptysetすなわち単なる1階述語論理は決定不能である．