不完全性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/01 08:09 UTC 版)
Qにおいて加法の交換法則 ∀ x ∀ y ( x + y = y + x ) {\displaystyle \forall x\forall y(x+y=y+x)} が証明不能であることを証明する。これによりQが不完全であることを示せる。それにはQのモデルで加法の交換法則が不成立であるようなものを構成すればよい。まずドメインとして N ∪ { a , b } {\displaystyle \mathbb {N} \cup \{a,b\}} を取る。ここで a , b {\displaystyle a,b} は相異なる不定元である。関数記号の解釈は N {\displaystyle \mathbb {N} } 上では通常通りに定める。ただし a , b {\displaystyle a,b} に対しては次のように定める。まず後者関数の解釈を S a = b {\displaystyle Sa=b} S b = a {\displaystyle Sb=a} で定める。この解釈のもとで(Q1)–(Q3)を満たす。あとは(Q4)–(Q7)を満たすように加法と乗法を適当に解釈すればよい。例えば加法は次のように解釈する（ここで n {\displaystyle n} は任意の自然数とする）： a + n = { a if n ≡ 0 mod 2 b if n ≡ 1 mod 2 {\displaystyle a+n={\begin{cases}a&{\mbox{if }}n\equiv 0\mod 2\\b&{\mbox{if }}n\equiv 1\mod 2\end{cases}}} b + n = { b if n ≡ 0 mod 2 a if n ≡ 1 mod 2 {\displaystyle b+n={\begin{cases}b&{\mbox{if }}n\equiv 0\mod 2\\a&{\mbox{if }}n\equiv 1\mod 2\end{cases}}} n + a = a {\displaystyle n+a=a} n + b = b {\displaystyle n+b=b} a + a = a {\displaystyle a+a=a} a + b = b {\displaystyle a+b=b} b + a = a {\displaystyle b+a=a} b + b = b {\displaystyle b+b=b} その他、積を定義することによりQのモデルが得られるが、ここでは加法の交換法則が成立しない。例えば a + b = b ≠ a = b + a {\displaystyle a+b=b\neq a=b+a} である。したがって健全性定理によりQにおいては加法の交換法則が証明できない。
※この「不完全性」の解説は、「ロビンソン算術」の解説の一部です。
「不完全性」を含む「ロビンソン算術」の記事については、「ロビンソン算術」の概要を参照ください。
- 不完全性のページへのリンク
