一階述語論理による自然数論の形式化である「ペアノ算術(Peano arithmetic)」とは異なります。
ペアノの公理(ペアノのこうり、英: Peano axioms) とは、自然数の全体を特徴づける公理である。ペアノの公準(英: Peano postulates)あるいはデデキント=ペアノの公理(英: Dedekind-Peano axioms)とも呼ばれる[1][2]。1891年にイタリアの数学者ジュゼッペ・ペアノにより定式化された。
ペアノの公理を起点にして、初等算術と整数・有理数・実数・複素数の構成などを実際に展開してみせた古典的な書物に、1930年に出版されたランダウによる『解析学の基礎』(Grundlagen Der Analysis)がある。 集合 ? と定数 0 と関数 Sと集合Eに関する次の公理をペアノの公理という[3][注 1]。 このとき ? の元を自然数といい、自然数 n に対して自然数 S(n) をその後者 (successor)[注 2]という。 これらの公理は互いに独立であり、いずれも残りから導くことはできない[5]。 ペアノの公理から 2 + 2 = 4 や 2 ? 2 = 4 のような「定理」を証明するには 2 = S(S(0)) などの項を導入したり、加法 + や乗法 ? の存在や性質を示したりする必要がある。たとえば Henle (1986, pp. 17, 18, 103, 104) を見よ。 次の主張を回帰定理(recursion theorem)という[6]。 集合 X に属する元 x と写像 g: X → X が与えられたとき f ( 0 ) = x , f ∘ S = g ∘ f {\displaystyle f(0)=x,\ f\circ S=g\circ f} を満たす写像 f : N → X {\displaystyle f\colon \mathbb {N} \to X} が一意的に存在する。 たとえば X = ? のとき写像 f は初項が x の漸化式により定義される数列に他ならない。回帰定理はこのような再帰的に定義される写像の存在と一意性を数学的帰納法の原理により保証する。 集合 ?^ と定数 0^ と関数 S^ がペアノの公理を満たすとき組 (?^, 0^, S^) をペアノ構造(Peano structure)という。ペアノ構造は同型を除いてただ一つに定まる[注 4]、つまりペアノの公理は範疇的(categorical)であることがわかる。 一方で後述するペアノ算術はレーヴェンハイム=スコーレムの定理から超準モデルをもつので範疇的ではない。 現代数学において標準的な数学の対象はすべて集合として実現されている。集合論における自然数の標準的な構成法としては N := ⋂ { x ∣ ∅ ∈ x ∧ ∀ y [ y ∈ x → y ∪ { y } ∈ x ] } {\displaystyle \mathbb {N} :=\bigcap \{\,x\mid \emptyset \in x\land \forall y[y\in x\to y\cup \{y\}\in x]\,\}} 0 := ∅ {\displaystyle 0:=\emptyset } S ( x ) := x ∪ { x } {\displaystyle S(x):=x\cup \{x\}} がある[注 5]。これらの集合は存在して、ペアノの公理を満たすことが確かめられる。 このとき具体的な自然数は のようになる。この構成法はジョン・フォン・ノイマンによる[8]。 自然数の集合が定義されたとき、その構成と自然数上での帰納法から、自然数上の算術や順序を定めることができる。 自然数の加法は次のように再帰的に定義される。 n + 0 = n {\displaystyle n+0=n} n + S ( m ) = S ( n + m ) {\displaystyle n+S(m)=S(n+m)} 自然数の乗法は次のように再帰的に定義される。 n ⋅ 0 = 0 {\displaystyle n\cdot 0=0} n ⋅ S ( m ) = n ⋅ m + n {\displaystyle n\cdot S(m)=n\cdot m+n} 自然数の順序は次のように定義される。ある k について n + k = m {\displaystyle n+k=m} が成り立つとき n ≤ m {\displaystyle n\leq m} と定義する。 また n ? m かつ n ≠ m のとき n < m と定義する。 非論理記号として定数記号 0 と関数記号 S, +, ? と述語記号 < をもつ等号つき一階述語論理の形式言語上で、以下の公理によって定まる理論をペアノ算術(Peano arithmetic)あるいは PA という[9](形式言語や公理の選び方には本質的に同じものが色々とある。)。 自然数の標準モデル ? において真である Σ1 閉論理式はペアノ算術から証明ができること(PA の Σ1 完全性)が知られている[10]。 一方でゲーデルの第一不完全性定理によりペアノ算術からは証明も反証もできない命題が存在する。有名な例としてはグッドスタインの定理やパリス=ハーリントンの定理がある。
公理
0 ∈ ?
任意の n ∈ ? について S(n) ∈ ?
任意の n ∈ ? について S(n) ≠ 0
任意の n, m ∈ ? について n ≠ m ならば S(n) ≠ S(m)
任意の E ⊆ ? について 0 ∈ E かつ任意の n ∈ ? について n ∈ E → S(n) ∈ E ならば E = ?
回帰定理
範疇性
集合論的な構成
0 = ∅ = { } {\displaystyle 0=\emptyset =\{\}}
1 := S ( 0 ) = { 0 } = { { } } {\displaystyle 1:=S(0)=\{0\}=\{\{\}\}}
2 := S ( 1 ) = { 0 , 1 } = { { } , { { } } } {\displaystyle 2:=S(1)=\{0,1\}=\{\{\},\{\{\}\}\}}
3 := S ( 2 ) = { 0 , 1 , 2 } = { { } , { { } } , { { } , { { } } } } {\displaystyle 3:=S(2)=\{0,1,2\}=\{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\}}
加法
乗法
順序
ペアノ算術
∀ n ¬ [ S ( n ) = 0 ] {\displaystyle \forall n\lnot [S(n)=0]}
∀ n ∀ m [ S ( n ) = S ( m ) → n = m ] {\displaystyle \forall n\forall m[S(n)=S(m)\to n=m]}
∀ n [ n + 0 = n ] {\displaystyle \forall n[n+0=n]}
∀ n ∀ m [ n + S ( m ) = S ( n + m ) ] {\displaystyle \forall n\forall m[n+S(m)=S(n+m)]}
∀ n [ n ⋅ 0 = 0 ] {\displaystyle \forall n[n\cdot 0=0]}
∀ n ∀ m [ n ⋅ S ( m ) = n ⋅ m + n ] {\displaystyle \forall n\forall m[n\cdot S(m)=n\cdot m+n]}
∀ n ¬ [ n < 0 ] {\displaystyle \forall n\lnot [n<0]}
∀ n ∀ m [ [ n < S ( m ) ] ↔ [ n < m ] ∨ [ n = m ] ] {\displaystyle \forall n\forall m[[n<S(m)]\leftrightarrow [n<m]\lor [n=m]]}
[ φ ( 0 ) ∧ ∀ n [ φ ( n ) → φ ( S ( n ) ) ] ] → ∀ n [ φ ( n ) ] {\displaystyle [\varphi (0)\land \forall n[\varphi (n)\to \varphi (S(n))]]\to \forall n[\varphi (n)]}
Size:33 KB
出典: フリー百科事典『ウィキペディア(Wikipedia)』
担当:undef