ロビンソン算術
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} は任意の自然数とする):