算術の超準モデル

算術の超準モデル (英: non-standard model of arithmetic) とは、（一階）ペアノ算術のモデルのうち、通常の自然数ではない要素（超準数）を含むようなモデルのことである。それに対し、通常の自然数 N {\displaystyle \mathbb {N} } は算術の標準モデルと呼ばれる。ペアノ算術の任意のモデルは線形順序で並んでおり、 N {\displaystyle \mathbb {N} } と同型な切片を持つ。超準モデルは、その切片の外に元を持つようなモデルであると言える。 算術の超準モデルの存在を証明する方法はいくつか存在する。 コンパクト性定理を用いて超準モデルの存在を示すことができる。証明の概略は、 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 }} の存在を示すというものである。 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}}} は端点を持たない稠密全順序集合である。 ^ 坪井明人　数学基礎論サマースクール モデル理論入門 田中一之 『数の体系と超準モデル』 裳華房、2002年4月。ISBN 978-4-7853-1530-6。 - 訂正表 (PDF) Boolos, G.; Jeffrey, R. (1974), Computability and Logic, Cambridge University Press, ISBN 0-521-38923-2  Kossak, Roman; Schmerl, James H. (2006), The Structure of Nonstandard Models of Arithmetic, Oxford Logic Guides, Oxford University Press, ISBN 978-0-19-856827-8  Skolem, Th. (1934), “Über die Nicht-charakterisierbarkeit der Zahlenreihe mittels endlich oder abzählbar unendlich vieler Aussagen mit ausschliesslich Zahlenvariablen”, Fundamenta Mathematicae 23: 150-161, http://pldml.icm.edu.pl/pldml/element/bwmeta1.element.bwnjournal-article-fmv23i1p15bwm?q=bwmeta1.element.bwnjournal-number-fm-1934-23-1;14&qt=CHILDREN-STATELESS  真の算術 超準解析 モデル理論