Loading article…
数理論理学において、ペアノ公理（/ p i ˈ ɑː n oʊ / ; [ 1 ] [ peˈaːno ]）は、デデキント＝ペアノ公理またはペアノ公準とも呼ばれ、19 世紀のイタリアの数学者ジュゼッペ・ペアノによって提示された自然数の公理である。これらの公理は、数論が無矛盾かつ完全であるかどうかの根本的な問題の研究を含む、多くのメタ数学的研究においてほぼ変更されずに使用されてきた。
ペアノ公理によって提供される算術の公理化は、一般にペアノ算術と呼ばれます。
算術を形式化することの重要性は、 1860年代に後継演算と帰納法に関するより基本的な事実から算術の多くの事実を導き出すことができることを示したヘルマン・グラスマンの研究まで十分に認識されていませんでした。[ 2 ] [ 3 ] 1881年、チャールズ・サンダース・パースは自然数算術の公理化を提供しました。[ 4 ] [ 5 ] 1888年、リヒャルト・デデキントは自然数算術の別の公理化を提案し、1889年にペアノは、彼の著書『新しい方法によって提示された算術の原理』（ラテン語：Arithmetices principia, nova methodo exposita ）の中で、それらの簡略化されたバージョンを公理の集合として発表しました。
ペアノの公理は、その主題に応じてグループ分けすることができる。最初の公理は、自然数の集合の少なくとも１つの要素の存在を主張する。次の４つは等号に関する一般的な記述であり、現代の扱いでは、これらはペアノの公理の一部ではなく、「基礎論理」の公理として扱われることが多い。[ 6 ]次の３つの公理は、後続演算の基本的な性質を表す自然数に関する一階述語である。９番目、最後の公理は、自然数に対する数学的帰納法の原理に関する二階述語であり、この定式化は二階算術に近い。加算と乗算の演算記号を明示的に追加し、二階帰納法の公理を一階公理図式に置き換えることで、より弱い一階体系が得られる。ペアノ算術という用語は、この制限された体系を具体的に命名するために用いられることがある。
ペアノが公理を定式化した当時、数理論理学の言語はまだ黎明期にあった。公理を表すために彼が考案した論理記号体系は普及しなかったが、集合のメンバーシップを表す現代の記号（∈、これはペアノのεに由来する）の起源となった。ペアノは数学記号と論理記号を明確に区別したが、これは当時数学では一般的ではなかった。このような区別は、1879年に出版されたゴットロープ・フレーゲの『概念記号』で初めて導入された。 [ 7 ]ペアノはフレーゲの著作を知らず、ブールとシュレーダーの著作に基づいて独自に論理体系を再構築した。[ 8 ]
ペアノ公理は、通常集合Nまたはとして表される自然数の算術的性質を定義します。公理の非論理記号は、定数記号 0 と単項関数記号Sから構成される。
第一の公理は、定数0は自然数であると述べている。
ペアノの公理の原式では、「最初の」自然数として0ではなく1が使われていたが[ 9 ] 、 『Formulario mathematico』の公理には0が含まれている[ 10 ]。
次の４つの公理は等号関係を記述する。これらは等号を伴う一階述語論理において論理的に妥当であるため、現代の扱いでは「ペアノ公理」の一部とはみなされない。[ 8 ]
残りの公理は、自然数の算術的性質を定義する。自然数は、単一値の「後継」関数Sに関して閉じていると仮定する。
公理1、6、7、8は、自然数の直感的な概念の単項表現を定義します。つまり、数1はS (0)、2はS ( S (0))などと定義できます。しかし、自然数の概念がこれらの公理によって定義されていると考えると、公理1、6、7、8は、後継関数が0以外のすべての自然数を生成することを意味するものではありません。
任意の自然数は、ゼロに十分多くの回数後継数を適用することによって得られるという直感的な考え方には、帰納法の公理と呼ばれる追加の公理が必要です。
帰納法の公理は、次のような形で表現されることがある。
ペアノの原典では、帰納法の公理は二階述語論理の公理である。現在では、この二階述語論理の原理をより弱い一階述語論理の帰納法に置き換えるのが一般的である。二階述語論理と一階述語論理の定式化には重要な違いがあり、これについては後述の「 一階理論としてのペアノ算術」の節で論じる。
二階述語論理の公理を用いる場合、公理を用いて自然数体N上の加算、乗算、および全（線形）順序を直接定義することが可能です。しかし、一階述語論理ではこれは不可能であり、加算と乗算はしばしば公理として追加されます。それぞれの関数と関係は集合論または二階述語論理で構築され、ペアノ公理を用いて一意であることが示されます。
加算とは、 2つの自然数（Nの2つの要素）を別の自然数に写像する関数です。加算は再帰的に次のように定義されます。
例えば：
加法の可換性を証明するには、まず次のことを証明します。そしてそれぞれ帰納法によって両方の結果を用いて証明せよ。帰納法によって構造( N , +)は単位元 0 を持つ可換モノイドです。( N , +)は消去可能なマグマでもあり、したがって群に埋め込むことができます。Nを埋め込む最小の群は整数群です。
同様に、乗算は2つの自然数を別の自然数に写像する関数です。加算が与えられた場合、乗算は次のように再帰的に定義されます。
容易にわかるように乗法右恒等式は です。
それを示すためにまた、乗法的な左恒等式は、乗法の定義方法により帰納法の公理を必要とする。
したがって、帰納法の公理によりは、すべての自然数の乗法的な左単位元です。さらに、乗法は交換法則を満たし、加算に対して分配法則を満たすことが示されています[ 14 ] 。
したがって、は可換半環である。
自然数における通常の全順序関係 ≤ は、0 を自然数と仮定して、次のように定義できます。
この関係は加算と乗算に対して安定している。a ≤ bの場合、次のようになります。
したがって、構造( N、 +、 ·、 1、 0、 ≤)は順序付き半環です。0 と 1 の間に自然数がないため、離散順序付き半環です。
帰納法の公理は、より強い仮説を用い、順序関係「≤」を利用して、次のような形で表現されることがある。
この形式の帰納法公理は強帰納法と呼ばれ、標準的な定式化の結果ですが、多くの場合、≤ 順序についての推論に適しています。たとえば、自然数が整列していることを示すには、Nの空でない部分集合はすべて最小元を持つことになります。次のように推論できます。N の空でないXが与えられ、X には最小元がないと仮定します。
したがって、強い帰納法の原理により、すべてのn ∈ Nに対して、n ∉ Xである。したがって、X ∩ N = ∅ となり、これはX がNの空でない部分集合であることに矛盾する 。したがって、X は最小元を持つ。
ペアノ公理のモデルは、( N , 0, S )という三つ組で表されます。ここで、Nは（必然的に無限）集合、0 ∈ N、そしてS : N → Nは上記の公理を満たします。デデキントは、1888年の著書『数の本質と意味』（ドイツ語: Was sind und was sollen die Zahlen?、つまり「数とは何か、そして何に役立つのか？」）の中で、ペアノ公理の任意の2つのモデル（2階誘導公理を含む）は同型であることを証明しました。特に、ペアノ公理の2つのモデル( N A , 0 A , S A )と( N B , 0 B , S B )が与えられた場合、 f : N A → N Bという唯一の準同型 が存在し、
そしてそれは全単射である。これは、2階ペアノ公理が範疇的であることを意味する。（これは、後述するペアノ公理の1階再定式化では当てはまらない。）
ペアノ公理は、自然数の集合論的構成と、 ZFなどの集合論の公理から導き出すことができる。[ 15 ]ジョン・フォン・ノイマンによる自然数の標準的な構成は、0を空集合∅として定義し、集合上の演算子sを次のように定義することから始まる。
自然数の集合Nは、空集合を含むすべての自然数集合の共通部分として定義される。各自然数は、それより小さい自然数の集合と（集合として）等しい。
など。集合Nと 0 および後継関数s : N → Nはペアノ公理を満たす。
ペアノ算術は、いくつかの弱い集合論体系と等矛盾しない。 [ 16 ]そのような体系の1つは、無限公理をその否定に置き換えたZFCである。そのような体系のもう1つは、一般的な集合論（外延性、空集合の存在、随伴公理）に、空集合に対して成り立ち、随伴に対して成り立つ性質は、随伴に対して成り立つ限り、すべての集合に対して成り立つという公理図式を追加したものである。
ペアノ公理は圏論を用いて理解することもできる。終端対象1 Cを持つ圏Cとし、点付き単項システムの圏US 1 ( C )を次のように定義する。
すると、US 1 ( C ) が初期対象を持つ場合、Cはデデキント-ペアノ公理を満たすと言われます。この初期対象は、 Cにおける自然数対象として知られています。( N , 0, S )がこの初期対象であり、( X , 0 X , S X )が他の任意の対象である場合、一意の写像u : ( N , 0, S ) → ( X , 0 X , S X )は、次のようになります。
これはまさに 0 XとS Xの再帰的定義です。
ペアノ公理が最初に提案されたとき、バートランド・ラッセルらは、これらの公理が暗黙のうちに「自然数」の意味を定義していることに同意した。[ 17 ]アンリ・ポアンカレはより慎重で、これらの公理が自然数を定義するのは、それらが無矛盾である場合のみであると述べた。これらの公理のみから出発して、0 = 1 のような矛盾を導き出す証明がある場合、公理は無矛盾であり、何も定義していないことになる。[ 18 ] 1900 年、ダフィット・ヒルベルトは、有限的な方法のみを使用してそれらの無矛盾性を証明する問題を、彼の23 の問題の2 番目として提起した。[ 19 ] 1931 年、クルト・ゲーデルは、ペアノ算術が無矛盾であれば、そのような無矛盾性の証明はペアノ算術自体の中で形式化できないことを示す、彼の第 2 不完全性定理を証明した。 [ 20 ]
ゲーデルの定理はペアノ算術の有限的無矛盾性証明の可能性を排除すると広く主張されているが、これは有限的証明が何を意味するかによって異なる。ゲーデル自身は、ペアノ算術では形式化できない有限的方法を用いることで、ペアノ算術またはより強い体系の有限的無矛盾性証明を与える可能性を指摘しており、1958年に、ゲーデルは型理論を用いて算術の無矛盾性を証明する方法を発表した。[ 21 ] 1936年、ゲルハルト・ゲンツェンは、 ε 0と呼ばれる順序数までの超限帰納法を用いて、ペアノの公理の無矛盾性の証明を与えた。[ 22 ]ゲンツェンは次のように説明している。「本論文の目的は、初等整数論の無矛盾性を証明すること、あるいはむしろ、無矛盾性の問題をいくつかの基本原理に還元することである」。ゲンツェンの証明は、超限順序数 ε 0を有限オブジェクトで表現できるため、有限的であると言えるだろう（例えば、整数の適切な順序を記述するチューリングマシンとして、あるいはより抽象的に、適切な線形順序付けがされた有限木から構成されるものとして）。ゲンツェンの証明がヒルベルトが想定した要件を満たしているかどうかは不明である。有限的証明が具体的に何を意味するのかについての一般的に受け入れられている定義はなく、ヒルベルト自身も明確な定義を与えていない。
現代の数学者の大多数は、直観またはゲンツェンの証明のような無矛盾性証明の受容に基づき、ペアノの公理は無矛盾であると考えている。少数の哲学者や数学者（中には超有限主義を提唱する者もいる）は、ペアノの公理を受け入れることは自然数の無限集合を受け入れることと同義であるため、ペアノの公理を拒否している。特に、加算（後継関数を含む）と乗算は全数であると仮定されている。興味深いことに、ペアノの公理に似ているが、加算と乗算の代わりに減算と除算を用いる自己検証理論が存在する。これらの理論は、加算と乗算の全数に対応する文の証明を避けるように公理化されているが、それでもすべての真を証明できる。PAの定理であり、自身の一貫性を証明する一貫性のある理論（「0=1」のヒルベルト式証明の非存在として述べられる）に拡張することができる。[ 23 ]
ペアノの公理のうち、第 9 公理 (帰納公理) を除くすべては、一階述語論理の命題です。[ 24 ]加算と乗算の算術演算と順序関係も、一階述語論理の公理を用いて定義できます。上記の帰納公理は、述語 (自然数ではなく自然数の集合) を量化しているため、二階述語論理です。代替案として、一階述語論理の帰納公理図式を考えることができます。このような図式は、ペアノ算術の一階述語論理で定義可能な述語ごとに 1 つの公理を含み、二階述語論理の公理よりも弱くなります。[ 25 ]弱い理由は、一階述語論理の述語の数は可算であるのに対し、自然数の集合の数は不可算であるためです。したがって、一階述語論理で記述できない集合が存在します (実際、ほとんどの集合はこの性質を持っています)。
ペアノ算術の1階公理化には、もう一つ技術的な制約がある。2階論理では、後続演算から加算と乗算を定義することができるが、より制約の多い1階論理ではそれができない。そのため、加算と乗算はペアノ算術のシグネチャに直接含まれ、3つの演算を相互に関連付ける公理も含まれる。
以下の公理のリスト（通常の等号公理を含む）には、ロビンソン算術の 7 つの公理のうち 6 つが含まれており、この目的には十分です。[ 26 ]
この数値公理のリストに加えて、ペアノ算術には帰納法スキーマが含まれており、これは再帰的に列挙可能で決定可能な公理の集合から構成されています。ペアノ算術の言語における各式φ ( x , y 1 , ..., y k )に対して、 φの一次帰納法公理は次の文です。
どこはy 1 ,..., y kの略記です。一階帰納法スキーマには、一階帰納法公理のすべてのインスタンスが含まれます。つまり、すべての式φに対する帰納法公理が含まれます。
上記のペアノ算術の公理化では、ゼロと後継演算、加算、乗算演算の記号のみを含むシグネチャを使用します。他にも多くの異なる、しかし同等の公理化があります。そのような代替案の1つ[ 27 ]では、後継演算の代わりに順序関係記号と離散的に順序付けられた半環の言語を使用します（半環の公理1-7、順序の公理8-10、互換性の公理11-13、離散性の公理14-15）。
これらの公理によって定義される理論はPA−として知られています。また、それは不完全であり、その重要な特性の1つは、いかなる構造もこの理論を満たすには、最初のセグメント（) と同型そのセグメント内の要素は標準要素と呼ばれ、その他の要素は非標準要素と呼ばれます。
最後に、一次帰納法スキームを追加することにより、ペアノ算術PAが得られる。
ゲーデルの不完全性定理によれば、 PA理論は（矛盾がなければ）不完全である。したがって、PAの標準モデルでは真であるが、一階述語論理（FOL）の公理化の結果ではないFOLの文が存在する。ロビンソン算術のような、より弱い公理を持つ理論においても、本質的な不完全性は既に生じている。
上記の不完全性の結果（ゲーデルのFOLの完全性定理による）と密接に関連して、与えられたFOL文がペアノ算術の1階公理化の結果であるかどうかを判定するアルゴリズムは存在しないことが導かれる。したがって、 PAは決定不能な理論の一例である。決定不能性は、ヒルベルトの第10問題に対する否定的な解答により、PAの存在文に対して既に生じている。その証明は、すべての計算可能な列挙可能な集合がディオファントス集合であり、したがってPAの存在量化式（自由変数を含む）によって定義可能であることを示唆している。存在式よりも高い量化子ランク（より多くの量化子交替）を持つPAの式は表現力が高く、算術階層のより高いレベルの集合を定義する。
通常の自然数はPAの公理を満たしますが、他のモデル (「非標準モデル」と呼ばれる) も存在します。コンパクト性定理は、非標準要素の存在が一階述語論理では排除できないことを示唆しています。[ 28 ]上向きのLöwenheim–Skolem の定理は、すべての無限濃度の PA の非標準モデルが存在することを示しています。これは、同型を除いて 1 つのモデルしか持たない元の (2 階) Peano 公理には当てはまりません。[ 29 ]これは、一階システム PA が 2 階 Peano 公理よりも弱い方法の 1 つを示しています。
デデキントによるペアノ公理の圏論的証明は、 ZFCのような一階述語論理の集合論における証明として解釈すると、集合論の各モデルには、同型を除いてペアノ公理の一意なモデルが存在し、そのモデルに含まれる他のすべてのペアノ公理モデルの初期セグメントとして埋め込まれることを示している。集合論の標準モデルでは、この最小のペアノ公理モデルがペアノ公理の標準モデルとなる。しかし、非標準モデルでは、非標準モデルとなる可能性がある。この状況は、集合論の一階述語論理による形式化では避けられない。
可算非標準モデルを明示的に構成できるかどうかを問うのは自然なことである。答えは肯定であり、1933 年にSkolem がそのような非標準モデルの明示的な構成を提供した。一方、 1959 年に証明されたTennenbaum の定理は、加算または乗算演算が計算可能な PA の可算非標準モデルは存在しないことを示している。[ 30 ]この結果は、PA の可算非標準モデルの加算と乗算演算を完全に明示的に記述することが難しいことを示している。可算非標準モデルには、可能な順序型が 1 つしかない。ω を自然数の順序型、ζ を整数の順序型、ηを有理数の順序型とすると、PA の任意の可算非標準モデルの順序型はω + ζ · ηであり、これは自然数のコピーに続いて整数のコピーの密な線形順序付けとして視覚化できる。
非標準モデルMにおけるカットとは、 Mの空でない部分集合Cであって、Cが下方閉集合 ( x < yかつy ∈ C ⇒ x ∈ C ) であり、かつCが後継者に関して閉集合であるようなものである。適切なカットとは、 Mの適切な部分集合であるカットのことである。各非標準モデルには、標準自然数に対応するものを含め、多くの適切なカットが存在する。しかし、ペアノ算術の帰納法では、適切なカットを定義することはできない。アブラハム・ロビンソンが最初に証明したオーバースピル補題は、この事実を形式化したものである。
オーバースピル補題[ 31 ] — M をPA の非標準モデルとし、CをMの適切なカットとする。は、 Mの要素のタプルであり、これは算術の言語での数式であり、
すると、 MにはCのすべての要素よりも大きいcが存在し、
この記事は、PlanetMathのPAの資料を組み込んでおり、クリエイティブ・コモンズ表示-継承ライセンスの下でライセンスされています。
