算術の超準モデルの存在を証明 する方法はいくつか存在する。
コンパクト性定理による方法 コンパクト性定理 を用いて超準モデルの存在を示すことができる。証明の概略は、 c {\displaystyle c} を新たな定数として、ペアノの公理系 P A {\displaystyle \mathrm {PA} } に { n < c : n = 1 , 2 , 3 , . . . } {\displaystyle \{n<c:n=1,2,3,...\}} という形の無限 個の公理 を付け加えた公理系 P A ∗ {\displaystyle \mathrm {PA} ^{\ast }} を考え、コンパクト性定理により P A ∗ {\displaystyle \mathrm {PA} ^{\ast }} を満たすモデル N ∗ {\displaystyle \mathbb {N} ^{\ast }} の存在を示すというものである[1] 。 P A ∗ {\displaystyle \mathrm {PA} ^{\ast }} はペアノの公理系を拡張したものであるため、当然ペアノの公理を満たしている。また通常の自然数では定数 c {\displaystyle c} をいかように解釈しても P A ∗ {\displaystyle \mathrm {PA} ^{\ast }} を満たすようにはできないため、 c {\displaystyle c} は超準数であり、 N ∗ {\displaystyle \mathbb {N} ^{\ast }} は超準モデルとなる。
P A ∗ {\displaystyle \mathrm {PA} ^{\ast }} にコンパクト性定理を適用するには、その任意の有限部分 T {\displaystyle T} がモデルを持つことを示せばよい。 T {\displaystyle T} は P A {\displaystyle \mathrm {PA} } の部分集合に n 1 < c , n 2 < c , … , n m < c {\displaystyle n_{1}<c,n_{2}<c,\ldots ,n_{m}<c} ( n 1 < n 2 < ⋯ < n m {\displaystyle n_{1}<n_{2}<\cdots <n_{m}} )という有限個の公理を付け加えた形をしているため、 c {\displaystyle c} の解釈を n m + 1 {\displaystyle n_{m}+1} と定めれば、自然数 N {\displaystyle \mathbb {N} } が T {\displaystyle T} のモデルになっていることが言える。
ゲーデルの不完全性定理による方法 不完全性定理 により、標準モデルでは真であるがペアノの公理系においては決定不能 であるような文(ゲーデル文) G {\displaystyle G} が存在する。このとき、完全性定理 より、ペアノの公理系 P A {\displaystyle \mathrm {PA} } に ¬ G {\displaystyle \lnot G} を加えた公理系にモデルが存在する。標準モデルで G {\displaystyle G} は真なので、このモデルは超準モデルでなければいけない。このように、 ¬ G {\displaystyle \lnot G} を満たすことは、そのモデルが超準的である為の十分条件となる。しかし、これは必要条件ではない。いかなるゲーデル文 G {\displaystyle G} に対しても、 G {\displaystyle G} が真であるようなあらゆる濃度のモデルが存在する。
算術が無矛盾であると仮定すれば、算術に ¬ G {\displaystyle \lnot G} を付け加えたものもまた無矛盾である。しかし、 ¬ G {\displaystyle \lnot G} は算術が矛盾していることを意味するのだから、結果得られた算術の体系は ω-無矛盾にはならない(なぜなら、 ¬ G {\displaystyle \lnot G} は偽であり、したがって ω-無矛盾性に反する)。
超積による方法 算術の超準モデルを構成するもうひとつの方法は超積 に基づくものである。典型的な構成では自然数列全体の成す集合 N N {\displaystyle \mathbb {N} ^{\mathbb {N} }} を用いる。2つの列が同一視されるのは、それらがある固定された非単項超フィルター に属す添字集合の上で一致するときである。このようにして得られた半環 は算術の超準モデルとなる。これは超自然数 と同一視出来る。
超積モデルは非可算となることが知られている。このことを見るには N {\displaystyle \mathbb {N} } の無限直積から超積モデルへの単射を構成すればよい。他方でレーヴェンハイム-スコーレムの定理 により、算術の可算な超準モデルが存在しなければならない。構成法の一つとして(ヘンキン構成 )を用いた方法がある。
・定理
算術の超準モデルの順序構造は、ある端点を持たない稠密全順序集合 Q {\displaystyle {\mathcal {Q}}} を用いて、 N ⊕ Z × Q {\displaystyle \mathbb {N} \oplus \mathbb {Z} \times {\mathcal {Q}}} と表せる。
特に、可算超準モデルの場合、上の表示において、 Q {\displaystyle {\mathcal {Q}}} は可算となるので、端点を持たない稠密全順序の理論(DLO)の可算(範疇性 )より、 Q {\displaystyle {\mathcal {Q}}} は Q {\displaystyle \mathbb {Q} } と同型となる。したがって可算超準モデルの順序構造は N ⊕ Z × Q {\displaystyle \mathbb {N} \oplus \mathbb {Z} \times \mathbb {Q} } と表せる。
・証明
いま M {\displaystyle M} を算術の超準モデルとする。 M {\displaystyle M} は N {\displaystyle \mathbb {N} } を含んでいるものと見做せる。ペアノ算術では、各自然数 n {\displaystyle n} に対して、
∀ x ( ⋀ k = 0 n ( x ≠ n ) → n < x ) {\displaystyle \forall x\left(\bigwedge _{k=0}^{n}(x\neq n)\to n<x\right)} が証明可能である。したがって M {\displaystyle M} に於いて真である。このことから M {\displaystyle M} は N {\displaystyle \mathbb {N} } の後ろに無限大元からなる部分を繋げたような順序構造をしていることが分かる。すなわち、順序集合として M = N ⊕ ( M ∖ N ) {\displaystyle M=\mathbb {N} \oplus (M\setminus \mathbb {N} )} が成り立つ。
次に M ′ = M ∖ N {\displaystyle M'=M\setminus \mathbb {N} } の順序構造を調べる。いま M ′ {\displaystyle M'} 上の二項関係
x E y ⟺ x − y ∈ Z {\displaystyle xEy\iff x-y\in \mathbb {Z} } (つまりある自然数 n {\displaystyle n} に対して x = y + n {\displaystyle x=y+n} または y = x + n {\displaystyle y=x+n} )を考える。これは同値関係となる。各々の同値類は
[ x ] = { x + n | n ∈ Z } {\displaystyle \left[x\right]=\{x+n|n\in \mathbb {Z} \}} の形をしていることが分かる。商集合 Q = M ′ / E {\displaystyle {\mathcal {Q}}=M'/E} 上の二項関係を
[ x ] ≪ [ y ] ⟺ x < y and y − x ∈ M ′ {\displaystyle \left[x\right]\ll \left[y\right]\iff x<y{\text{ and }}y-x\in M'} で定めると、これはwell-defined であって、全順序 となることが分かる。このとき、 M ′ {\displaystyle M'} の2元 u , v {\displaystyle u,v} について、 u < v {\displaystyle u<v} であることと、次の条件は同値である:
[ u ] = [ v ] {\displaystyle \left[u\right]=\left[v\right]} であって、 u = x + n , v = x + m {\displaystyle u=x+n,v=x+m} と書いたとき n < m {\displaystyle n<m} ;もしくは [ u ] ≪ [ v ] {\displaystyle \left[u\right]\ll \left[v\right]} したがって M ′ {\displaystyle M'} の順序は Z × Q {\displaystyle \mathbb {Z} \times {\mathcal {Q}}} 上の(逆辞書式順序 )となっている。
最後に Q {\displaystyle {\mathcal {Q}}} の順序構造を調べる。任意の x ∈ M ′ {\displaystyle x\in M'} に対して [ x ] ≪ [ 2 x ] {\displaystyle \left[x\right]\ll \left[2x\right]} が成り立つ。任意の元は偶数または奇数であることはペアノ算術で証明できる。よって x {\displaystyle x} はある y ∈ M {\displaystyle y\in M} によって x = 2 y , 2 y + 1 {\displaystyle x=2y,2y+1} のいずれかの形に表せる。またこのとき y ∈ M ′ {\displaystyle y\in M'} であり、 [ y ] ≪ [ x ] {\displaystyle \left[y\right]\ll \left[x\right]} が成り立つ。したがって Q {\displaystyle {\mathcal {Q}}} は端点(最大元と最小元)を持たない。次に x , y ∈ M ′ {\displaystyle x,y\in M'} について [ x ] ≪ [ y ] {\displaystyle \left[x\right]\ll \left[y\right]} と仮定する。 x + y {\displaystyle x+y} は偶数または奇数だから、ある z ∈ M {\displaystyle z\in M} によって x + y = 2 z , 2 z + 1 {\displaystyle x+y=2z,2z+1} のいずれかの形に表せる。いずれにしても z ∈ M ′ {\displaystyle z\in M'} であり、 [ x ] ≪ [ z ] ≪ [ y ] {\displaystyle \left[x\right]\ll \left[z\right]\ll \left[y\right]} が成り立つ。すなわち Q {\displaystyle {\mathcal {Q}}} は稠密である。
以上より、 M = N ⊕ Z × Q {\displaystyle M=\mathbb {N} \oplus \mathbb {Z} \times {\mathcal {Q}}} であり、 Q {\displaystyle {\mathcal {Q}}} は端点を持たない稠密全順序集合である。