Hệ tiên đề Peano

Trong logic toán học, các tiên đề Peano, còn được gọi là các tiên đề Peano – Dedekind hay các định đề Peano, là các tiên đề cho các số tự nhiên được trình bày bởi nhà toán học người Ý thế kỷ 19 Giuseppe Peano. Những tiên đề đã được sử dụng gần như không thay đổi trong nhiều nghiên cứu siêu toán học, trong đó có nghiên cứu về vấn đề cơ bản cho dù lý thuyết số là nhất quán và hoàn chỉnh.

Nhu cầu hình thức hóa số học không được đánh giá cao cho tới công trình của Hermann Grassmann, người đã chỉ ra vào những năm 1860 rằng nhiều sự thật trong số học có thể được rút ra từ những sự thật cơ bản hơn về hàm successor và phép quy nạp.^[1] Năm 1881, Charles Sanders Peirce đã lập ra một hệ tiên đề về số học số tự nhiên.^[2] Trong năm 1888, Richard Dedekind đề xuất một tiên đề khác về số học số tự nhiên, và trong năm 1889, Peano đã xuất bản một phiên bản đơn giản hóa của chúng thành một tập hợp các tiên đề trong cuốn sách của ông, Các nguyên tắc số học được trình bày bởi một phương pháp mới (tiếng Latinh: Arithmetices principia, nova methodo exposita).

Các tiên đề Peano chứa ba loại mệnh đề. Tiên đề đầu tiên khẳng định sự tồn tại của ít nhất một phần tử trong tập hợp các số tự nhiên. Bốn tiên đề tiếp theo là những mệnh đề chung về quan hệ bằng nhau; trong các phương pháp hiện đại, chúng thường không được coi là một phần của tiên đề Peano, mà là của "nền tảng logic" đằng sau nó.^[3] Ba tiên đề tiếp theo là các mệnh đề bậc nhất về số tự nhiên biểu thị các tính chất cơ bản của hàm successor. Tiên đề thứ chín – tiên đề cuối cùng, là một mệnh đề bậc hai về nguyên tắc quy nạp toán học trên các số tự nhiên. Một hệ thống bậc nhất yếu hơn gọi là số học Peano có được bằng cách thêm cụ thể các ký hiệu phép toán cộng và nhân và thay thế tiên đề quy nạp bậc hai bằng sơ đồ tiên đề bậc nhất.

Phát biểu

Khi Peano phát biểu các tiên đề của mình, ngôn ngữ của logic toán học đang ở giai đoạn sơ khai. Hệ thống ký hiệu logic mà ông tạo ra để trình bày các tiên đề đã không trở nên phổ biến, mặc dù đó là nguồn gốc của ký hiệu hiện đại cho quan hệ liên thuộc (∈, xuất phát từ kí tự ε của Peano) và bao hàm (⊃, xuất phát từ chữ 'C' đảo ngược của Peano). Peano duy trì sự phân biệt rõ ràng giữa các ký hiệu toán học và logic, điều vốn chưa phổ biến trong toán học; một sự tách biệt như vậy lần đầu tiên được giới thiệu trong cuốn Begriffsschrift bởi Gottlob Frege, xuất bản năm 1879.^[4] Peano không biết gì về công trình của Frege và xây dựng một bộ máy logic tương tự dựa trên công trình của Boole và Schröder.^[5]

Các tiên đề Peano xác định các tính chất số học của các số tự nhiên, thường được biểu diễn dưới dạng tập N hoặc ${\displaystyle \mathbb {N} .}$ Các ký hiệu không logic cho các tiên đề bao gồm ký hiệu hằng số 0 và ký hiệu hàm một biến S.

Tiên đề đầu tiên nói rằng hằng số 0 là số tự nhiên:

Bốn tiên đề tiếp theo mô tả quan hệ bằng nhau. Vì chúng đều đúng về logic trong logic bậc nhất chứa quan hệ bằng nhau, chúng không được coi là một phần của "tiên đề Peano" trong các phương pháp hiện đại.^[5]

Các tiên đề còn lại xác định các tính chất số học của các số tự nhiên. Các số tự nhiên được coi là đóng dưới một hàm "liền sau" (successor) đơn trị S.

Công thức ban đầu của Peano về các tiên đề sử dụng 1 thay vì 0 là số tự nhiên "đầu tiên".^[6] Lựa chọn này là tùy ý, vì tiên đề 1 không cung cấp thêm bất kỳ thuộc tính bổ sung nào cho số 0. Tuy nhiên, vì 0 là phần tử đơn vị của phép cộng trong số học, nên hầu hết các phát biểu hiện đại của các tiên đề Peano bắt đầu từ số 0. Tiên đề 1, 6, 7, 8 định nghĩa một cách biểu diễn đơn phân của khái niệm trực quan về số tự nhiên: số 1 có thể được định nghĩa là S(0), 2 là S(S(0)), v.v. Tuy nhiên, khi xem xét khái niệm số tự nhiên được xác định bởi các tiên đề này, các tiên đề 1, 6, 7, 8 không ngụ ý rằng hàm liền sau tạo ra tất cả các số tự nhiên khác 0. Nói cách khác, chúng không đảm bảo rằng mọi số tự nhiên khác 0 phải đứng liền sau một số tự nhiên khác. Khái niệm trực quan rằng mỗi số tự nhiên có thể đạt được bằng cách tìm số liền sau từ số 0 đủ nhiều lần đòi hỏi một tiên đề bổ sung, đôi khi được gọi là tiên đề quy nạp.

Tiên đề quy nạp đôi khi được nêu ở dạng sau:

Trong công thức ban đầu của Peano, tiên đề quy nạp là một tiên đề bậc hai. Hiện nay người ta thường thay thế nguyên tắc bậc hai này bằng sơ đồ quy nạp bậc nhất yếu hơn. Có sự khác biệt quan trọng giữa các công thức bậc hai và bậc nhất, như được thảo luận trong phần § Mô hình dưới đây.

Số học

Các tiên đề Peano có thể được bổ sung bằng các phép toán cộng và nhân và quan hệ thứ tự toàn phần (hay tuyến tính) thông thường trên N. Các hàm và quan hệ tương ứng được xây dựng theo lý thuyết tập hợp hoặc logic bậc hai, và có thể được cho thấy là duy nhất bằng cách sử dụng các tiên đề Peano.

Phép cộng

Phép cộng là một hàm ánh xạ hai số tự nhiên (hai phần tử của N) sang một số khác. Nó được định nghĩa đệ quy là:

${\displaystyle {\begin{aligned}a+0&=a,&{\textrm {(1)}}\\a+S(b)&=S(a+b).&{\textrm {(2)}}\end{aligned}}}$

Ví dụ:

${\displaystyle {\begin{aligned}a+1&=a+S(0)&{\mbox{bằng định nghĩa}}\\&=S(a+0)&{\mbox{áp dụng (2)}}\\&=S(a),&{\mbox{áp dụng (1)}}\\\\a+2&=a+S(1)&{\mbox{bằng định nghĩa}}\\&=S(a+1)&{\mbox{áp dụng (2)}}\\&=S(S(a))&{\mbox{áp dụng }}a+1=S(a)\\\\a+3&=a+S(2)&{\mbox{bằng định nghĩa}}\\&=S(a+2)&{\mbox{áp dụng (2)}}\\&=S(S(S(a)))&{\mbox{áp dụng }}a+2=S(S(a))\\{\text{v.v.}}&\\\end{aligned}}}$

Cấu trúc (N, +) là một monoid giao hoán với phần tử đơn vị 0. (N, +) cũng là một magma triệt tiêu, và do đó nhúng được trong một nhóm. Nhóm nhỏ nhất nhúng N là các số nguyên.

Phép nhân

Tương tự, phép nhân là một hàm ánh xạ hai số tự nhiên sang số khác. Ngoài ra, nó được định nghĩa đệ quy là:

${\displaystyle {\begin{aligned}a\cdot 0&=0,\\a\cdot S(b)&=a+(a\cdot b).\end{aligned}}}$

Dễ dàng thấy rằng S (0) (hoặc "1", trong ngôn ngữ quen thuộc của biểu diễn thập phân) là đơn vị phải của phép nhân:

a · S (0) = a + (a · 0) = a + 0 = a

Để chỉ ra rằng S(0) cũng là phần tử đơn vị trái của phép nhân cần có tiên đề quy nạp do cách định nghĩa phép nhân:

• S(0) là phần tử đơn vị bên trái của 0: S(0) · 0 = 0.
• Nếu S(0) là phần tử đơn vị bên trái của a (tức là S(0) · a = a), thì S(0) cũng là phần tử đơn vị bên trái của S(a): S(0) · S(a) = S(0) + S(0) · a = S(0) + a = a + S(0) = S(a+0) = S(a).

Do đó, bởi tiên đề quy nạp S (0) là phần tử đơn vị trái của phép nhân của tất cả các số tự nhiên. Hơn nữa, có thể chỉ ra rằng phép nhân có tính phân phối trên phép cộng:

a · (b + c) = (a·b) + (a ·c).

Do đó, (N, +, 0, ·, S(0)) là một nửa vành giao hoán.

Bất đẳng thức

Quan hệ toàn tự thông thường trên các số tự nhiên có thể được định nghĩa như sau, giả sử 0 là số tự nhiên:

Với mọi a, b ∈ N, a ≤ b khi và chỉ khi tồn tại một số c ∈ N sao cho a + c = b.

Mối quan hệ này ổn định dưới phép cộng và nhân: cho ${\displaystyle a,b,c\in \mathbf {N} }$, nếu a ≤ b, thì:

• a + c ≤ b + c và
• a · c ≤ b · c.

Do đó, cấu trúc (N, +, ·, 1, 0, ≤) là một nửa vành có thứ tự; bởi vì không có số tự nhiên trong khoảng từ 0 đến 1, nên nó là một nửa vành có thứ tự rời rạc.

Tiên đề quy nạp đôi khi được nêu ở dạng sau sử dụng giả thuyết mạnh hơn, sử dụng quan hệ thứ tự "≤":

Đối với bất kỳ vị từ φ, nếu

• φ(0) đúng, và
• cho mỗi n, k ∈ N nếu k ≤ n suy ra rằng φ(k) đúng, thì φ(S(n)) là đúng,

thì với mọi n ∈ N, φ(n) đúng.

Dạng tiên đề quy nạp này, được gọi là quy nạp mạnh, là hệ quả của cách phát biểu chuẩn mực, nhưng thường phù hợp hơn cho việc lí giải về quan hệ thứ tự ≤. Ví dụ, để chỉ ra rằng tập hợp các số tự nhiên được sắp tốt — mọi tập hợp con không rỗng của N có một phần tử nhỏ nhất, ta có thể lý giải như sau. Cho X ⊆ N không rỗng và giả sử X không có phần tử nhỏ nhất.

• Vì 0 là phần tử nhỏ nhất của N, nên 0 ∉ X
• Với mọi n ∈ N, giả sử với mọi k ≤ n, k ∉ X Khi đó S(n) ∉ X, bởi nếu không nó sẽ là phần tử nhỏ nhất của X.

Do đó, theo nguyên lý quy nạp mạnh, với mọi n ∈ N, n ∉ X Do đó, X ∩ N = ∅, mâu thuẫn với giả thiết rằng X là tập con không rỗng của N. Do đó X có phần tử nhỏ nhất.

Lý thuyết số học bậc nhất

Tất cả các tiên đề Peano ngoại trừ tiên đề thứ chín (tiên đề quy nạp) là các mệnh đề trong logic bậc nhất.^[7] Các phép toán số học của phép cộng và phép nhân và quan hệ thứ tự cũng có thể được xác định bằng các tiên đề bậc nhất. Tiên đề quy nạp có bậc hai, vì nó định lượng trên các vị từ (theo nghĩa tương đương, trên các tập hợp số tự nhiên chứ không phải trên các số tự nhiên), nhưng nó có thể được chuyển đổi thành sơ đồ tiên đề bậc nhất cho phép quy nạp. Một sơ đồ như vậy bao gồm một tiên đề cho mỗi vị ngữ định nghĩa được trong ngôn ngữ bậc nhất của số học Peano, khiến cho nó yếu hơn tiên đề bậc hai.^[8] Lý do nó yếu hơn là vì số lượng vị từ trong ngôn ngữ bậc nhất là có thể đếm được, trong khi số lượng các tập hợp số tự nhiên là không đếm được. Do đó, tồn tại các tập hợp không thể được mô tả bằng ngôn ngữ bậc nhất (trên thực tế, hầu hết các tập hợp đều có thuộc tính này).

Các tiên đề bậc nhất của số học Peano có một hạn chế kỹ thuật khác. Trong logic bậc hai, có thể định nghĩa các phép toán cộng và nhân từ hàm liền sau, nhưng điều này không thể được thực hiện trong cấu trúc hạn chế hơn của logic bậc một. Do đó, các phép toán cộng và nhân được bao gồm trực tiếp trong signature của số học Peano và các tiên đề được đưa vào có liên quan đến ba phép toán với nhau.

Danh sách các tiên đề sau (cùng với các tiên đề thông thường về quan hệ bằng nhau), chứa sáu trong số bảy tiên đề của số học Robinson, là đủ cho mục đích này: ^[9]

• ${\displaystyle \forall x\ (0\neq S(x))}$
• ${\displaystyle \forall x,y\ (S(x)=S(y)\Rightarrow x=y)}$
• ${\displaystyle \forall x\ (x+0=x)}$
• ${\displaystyle \forall x,y\ (x+S(y)=S(x+y))}$
• ${\displaystyle \forall x\ (x\cdot 0=0)}$
• ${\displaystyle \forall x,y\ (x\cdot S(y)=x\cdot y+x)}$

Ngoài danh sách các tiên đề số này, số học Peano còn chứa sơ đồ quy nạp, bao gồm một tập hợp các tiên đề đếm được đệ quy. Đối với mỗi công thức φ(x, y₁,..., y_k) trong ngôn ngữ của Peano số học, tiên đề quy nạp bậc nhất cho φ là mệnh đề

${\displaystyle \forall {\bar {y}}((\varphi (0,{\bar {y}})\land \forall x(\varphi (x,{\bar {y}})\Rightarrow \varphi (S(x),{\bar {y}})))\Rightarrow \forall x\varphi (x,{\bar {y}}))}$

Ở đâu ${\displaystyle {\bar {y}}}$ là viết tắt của y ₁,..., y _k. Sơ đồ quy nạp bậc nhất bao gồm tất cả các dạng của tiên đề quy nạp bậc nhất, có nghĩa là, nó bao gồm các tiên đề quy nạp cho mỗi công thức φ.

Các hệ tiên đề tương đương

Có nhiều tiên đề khác nhau, nhưng tương đương, của số học Peano. Trong khi một số tiên đề, chẳng hạn như mô tả vừa mô tả, sử dụng signature chỉ có số 0 và các phép toán nhân, phép cộng, phép nhân; các hệ tiên đề khác sử dụng ngôn ngữ về nửa vành có thứ tự, và bổ sung thêm ký hiệu quan hệ thứ tự. Một hệ tiên đề như vậy bắt đầu với các tiên đề sau đây mô tả một nửa cung có thứ tự rời rạc.^[10]

1. ${\displaystyle \forall x,y,z\ ((x+y)+z=x+(y+z))}$, tức là phép cộng có tính kết hợp.
2. ${\displaystyle \forall x,y\ (x+y=y+x)}$, tức là phép cộng có tính giao hoán.
3. ${\displaystyle \forall x,y,z\ ((x\cdot y)\cdot z=x\cdot (y\cdot z))}$, tức là phép nhân có tính kết hợp.
4. ${\displaystyle \forall x,y\ (x\cdot y=y\cdot x)}$, tức là phép nhân có tính giao hoán.
5. ${\displaystyle \forall x,y,z\ (x\cdot (y+z)=(x\cdot y)+(x\cdot z))}$, tức là phép nhân phân phối trên phép cộng.
6. ${\displaystyle \forall x\ (x+0=x\land x\cdot 0=0)}$, tức là số 0 là một phần tử đơn vị cho phép cộng và là một phần tử hấp thụ cho phép nhân (thực ra là thừa thãi ^{[chú thích 1]}).
7. ${\displaystyle \forall x\ (x\cdot 1=x)}$, tức là, một là một phần tử đơn vị cho phép nhân.
8. ${\displaystyle \forall x,y,z\ (x<y\land y<z\Rightarrow x<z)}$, tức là toán tử ' < ' mang tính bắc cầu.
9. ${\displaystyle \forall x\ (\neg (x<x))}$, tức là toán tử ' < ' là không phản xạ.
10. ${\displaystyle \forall x,y\ (x<y\lor x=y\lor y<x)}$, tức là, quan hệ thứ tự thỏa mãn luật tam phân.
11. ${\displaystyle \forall x,y,z\ (x<y\Rightarrow x+z<y+z)}$, tức là quan hệ thứ tự được bảo toàn khi cộng thêm cùng phần tử vào hai vế.
12. ${\displaystyle \forall x,y,z\ (0<z\land x<y\Rightarrow x\cdot z<y\cdot z)}$, tức là quan hệ thứ tự được bảo toàn dưới phép nhân hai vế bởi cùng một phần tử dương.
13. ${\displaystyle \forall x,y\ (x<y\Rightarrow \exists z\ (x+z=y))}$, cho hai phần tử khác nhau, phần tử lớn hơn là tổng của phần tử nhỏ hơn với một phần tử khác.
14. ${\displaystyle 0<1\land \forall x\ (x>0\Rightarrow x\geq 1)}$, tức là không và một khác nhau và không có phần tử nào nằm giữa chúng.
15. ${\displaystyle \forall x\ (x\geq 0)}$, tức là 0 là phần tử nhỏ nhất.

Lý thuyết được định nghĩa bởi các tiên đề này được gọi là PA⁻; lý thuyết PA thu được bằng cách thêm sơ đồ quy nạp bậc nhất. Một tính chất quan trọng của PA⁻ là bất kỳ cấu trúc nào ${\displaystyle M}$ thỏa mãn lý thuyết này có một đoạn mở đầu (được sắp bởi ${\displaystyle \leq }$) đẳng cấu với ${\displaystyle \mathbf {N} }$. Các phần tử trong đoạn đó được gọi là phần tử chuẩn mực, trong khi các phần tử khác được gọi là các phần tử không chuẩn mực.

Mô hình

Một mô hình của các tiên đề Peano là một bộ ba (N, 0, S), trong đó N là một tập hợp (nhất thiết là vô hạn), 0 ∈ N và S: N → N thỏa mãn các tiên đề ở trên. Dedekind đã chứng minh trong cuốn sách năm 1888 của mình, Bản chất và ý nghĩa của những con số (tiếng Đức: Was sind und was sollen die Zahlen?, tức là, "Số là gì và chúng có công dụng gì?") rằng hai mô hình bất kì của tiên đề Peano (bao gồm cả tiên đề quy nạp bậc hai) là đẳng cấu. Đặc biệt, với hai mô hình (N_A, 0_A, S_A) và (N_B, 0_B, S_B) của các tiên đề Peano, có một phép đồng hình duy nhất f: N_A → N_B thỏa mãn

${\displaystyle {\begin{aligned}f(0_{A})&=0_{B}\\f(S_{A}(n))&=S_{B}(f(n))\end{aligned}}}$

và nó là một song ánh. Điều này có nghĩa là các tiên đề Peano bậc hai là có tính phạm trù. Tuy nhiên, điều này không áp dụng với bất kỳ cách xây dựng lại bậc nhất nào của các tiên đề Peano.

Các mô hình lý thuyết tập hợp

Các tiên đề Peano có thể được rút ra từ các cấu trúc được xây dựng bởi lý thuyết tập hợp của các số tự nhiên và các tiên đề của lý thuyết tập hợp như ZF.^[11] Cấu trúc chuẩn mực của số tự nhiên, theo John von Neumann, bắt đầu từ định nghĩa 0 là tập rỗng, ∅, và một toán tử s trên các tập hợp với định nghĩa:

${\displaystyle s(a)=a\cup \{a\}}$

Tập hợp các số tự nhiên N được định nghĩa là giao của tất cả các tập đóng dưới s mà có chứa tập rỗng. Mỗi số tự nhiên bằng (dưới dạng tập hợp) với tập hợp số tự nhiên nhỏ hơn số đó:

${\displaystyle {\begin{aligned}0&=\emptyset \\1&=s(0)=s(\emptyset )=\emptyset \cup \{\emptyset \}=\{\emptyset \}=\{0\}\\2&=s(1)=s(\{0\})=\{0\}\cup \{\{0\}\}=\{0,\{0\}\}=\{0,1\}\\3&=s(2)=s(\{0,1\})=\{0,1\}\cup \{\{0,1\}\}=\{0,1,\{0,1\}\}=\{0,1,2\}\end{aligned}}}$

và cứ thế. Tập N cùng với 0 và hàm kế tiếp s: N → N thỏa mãn các tiên đề Peano.

Số học Peano có sự nhất quán tương đương với một số hệ thống yếu của lý thuyết tập hợp.^[12] Một ví dụ là hệ thống ZFC với tiên đề vô cùng được thay thế bằng phủ định của nó. Một ví dụ khác bao gồm lý thuyết tập hợp tổng quát (ngoại diên, sự tồn tại của tập hợp rỗng và tiên đề về tập phụ thêm) được bổ sung thêm một sơ đồ tiên đề nói rằng một thuộc tính đúng với tập rỗng và đúng với tập phụ thêm bất cứ khi nào nó đúng với phần phụ thêm thì đúng với tất cả các tập hợp.

Diễn giải trong lý thuyết phạm trù

Các tiên đề Peano cũng có thể được hiểu bằng lý thuyết phạm trù. Đặt C là một phạm trù với đối tượng đầu cuối 1_C và định nghĩa phạm trù của các hệ thống đơn phân nhọn, US₁(C) như sau:

• Các đối tượng của US₁(C) là bộ ba (X, 0_X, S_X) trong đó X là đối tượng của C và 0_X: 1_C → X và S_X: X → X là một C-cấu xạ.
• Một cấu xạ φ: (X, 0_X, S_X)→ (Y, 0_Y, S_Y)là một C-cấu xạ φ: X → Y với φ 0_X = 0_Y và φ S_X = S_Y φ

Sau đó, C được cho là thỏa mãn các tiên đề Peano của Dedekind, nếu US₁(C) có một đối tượng mở đầu; đối tượng mở đầu này được gọi là đối tượng số tự nhiên trong C. Nếu (N, 0, S) là đối tượng mở đầu này và (X, 0_X, S_X) là bất kỳ đối tượng nào khác, thì ánh xạ duy nhất u: (N, 0, S) → (X, 0_X, S_X) là

${\displaystyle {\begin{aligned}u0&=0_{X},\\u(Sx)&=S_{X}(ux).\end{aligned}}}$

Đây chính xác là định nghĩa đệ quy của 0_X và S_X.

Mô hình không chuẩn mực

Mặc dù các số tự nhiên thông thường thỏa mãn các tiên đề của PA, nhưng cũng có các mô hình khác (được gọi là " mô hình không chuẩn mực "); định lý compact cho thấy rằng sự tồn tại của các phần tử không chuẩn mực là không thể loại trừ được trong logic thứ nhất.^[13] Định lý Löwenheim–Skolem đi lên cho thấy rằng có những mô hình PA không chuẩn mực cho tất cả các số đếm vô hạn. Điều này không áp dụng với hệ tiên đề Peano nguyên gốc (bậc hai), mô hình của nó là duy nhất sai khác đẳng cấu.^[14] Điều này minh họa một mặt mà hệ thống PA bậc một yếu hơn hệ tiên đề Peano bậc hai.

Khi được diễn giải như một định lý trong lý thuyết tập hợp bậc nhất, chẳng hạn như ZFC, định lí phạm trù của Dedekind cho PA cho thấy mỗi mô hình của lý thuyết tập hợp có một mô hình duy nhất của các tiên đề Peano, cho đến đẳng cấu, là một phân đoạn ban đầu của tất cả các mô hình PA khác có trong mô hình lý thuyết tập hợp đó. Trong mô hình chuẩn của lý thuyết tập hợp, mô hình PA nhỏ nhất này là mô hình chuẩn của PA; tuy nhiên, trong một mô hình không chuẩn mực của lý thuyết tập hợp, nó có thể là một mô hình không chuẩn mực của PA. Tình trạng này không thể tránh được với bất kỳ cách hình thức hóa bậc nhất nào của lý thuyết tập hợp.

Hiển nhiên là có câu hỏi liệu một mô hình không chuẩn mực đếm được có thể được xây dựng rõ ràng hay không. Vào năm 1933, Skolem khẳng định là có thể khi đưa ra một cấu trúc rõ ràng của một mô hình phi tiêu chuẩn như trên. Mặt khác, định lý của Tennenbaum, đã được chứng minh vào năm 1959, cho thấy rằng không có mô hình PA không chuẩn mực đếm được nào trong đó phép cộng hoặc nhân là có thể tính toán được.^[15] Kết quả này cho thấy rất khó để làm rõ ràng hoàn toàn trong việc mô tả các phép cộng và nhân của một mô hình PA không chuẩn mực có thể đếm được. Chỉ có một kiểu số đếm khả dĩ cho một mô hình không chuẩn mực có thể đếm được. Cho ω là kiểu thứ tự của các số tự nhiên, ζ là kiểu thứ tự của các số nguyên, và η là kiểu thứ tự của số hữu tỉ, kiểu thứ tự của bất cứ mô hình không chuẩn mực đếm được của PA là ω + ζ·η có thể hình dung như một bản sao của các số tự nhiên theo sau là một thứ tự tuyến tính dày đặc của các bản sao của các số nguyên.

Overspill

Một lát cắt trong mô hình không chuẩn mực M là tập con khác rỗng C của M sao cho C đóng theo chiều xuống (x < y và y ∈ C ⇒ x ∈ C) và C đóng dưới hàm kế tiếp. Một lát cắt thực sự là một lát cắt là tập con thực sự của M. Mỗi mô hình không chuẩn mực có nhiều lát cắt thực sự, bao gồm một mô hình tương ứng với các số tự nhiên chuẩn mực. Tuy nhiên, sơ đồ quy nạp trong số học Peano ngăn không cho bất kì lát cắt thực sự nào có thể được định nghĩa. Bổ đề overspill, lần đầu tiên được chứng minh bởi Abraham Robinson, hình thức hóa điều này.

Bổ đề Overspill^[16] Gọi M là mô hình không chuẩn của PA và cho C là một phép cắt M thích hợp. Giả sử rằng ${\displaystyle {\bar {a}}}$ là một bộ các phần tử của M và ${\displaystyle \phi (x,{\bar {a}})}$ là một công thức trong ngôn ngữ số học sao cho

${\displaystyle M\vDash \phi (b,{\bar {a}})}$ với mọi b ∈ C.

Khi đó có một c trong M lớn hơn mọi phần tử của C sao cho

${\displaystyle M\vDash \phi (c,{\bar {a}}).}$

Tính nhất quán

Khi các tiên đề Peano lần đầu tiên được đề xuất, Bertrand Russell và những người khác đã đồng ý rằng các tiên đề này ngầm định nghĩa những gì chúng ta muốn nói là "số tự nhiên".^[17] Henri Poincaré thận trọng hơn, nói rằng chúng chỉ định nghĩa số tự nhiên nếu chúng nhất quán; nếu có một bằng chứng bắt đầu chỉ từ những tiên đề này và tạo ra mâu thuẫn như 0 = 1, thì các tiên đề không nhất quán và không định nghĩa bất cứ điều gì.^[18] Năm 1900, David Hilbert đặt ra vấn đề chứng minh tính nhất quán của chúng chỉ sử dụng phương pháp hữu hạn như vấn đề thứ hai trong số hai mươi ba vấn đề của ông ấy.^[19] Năm 1931, Kurt Gödel đã chứng minh định lý không hoàn chỉnh thứ hai của mình, điều này cho thấy một định lý nhất quán như vậy không thể được hình thức hóa bởi chính số học Peano.^[20]

Mặc dù người ta cho rằng định lý của Gödel loại trừ khả năng chứng minh tính nhất quán hữu hạn cho số học Peano, nhưng điều này phụ thuộc vào ý nghĩa chính xác của một định lý hữu hạn. Chính Gödel đã chỉ ra khả năng đưa ra một định lý nhất quán hữu hạn về số học Peano hoặc các hệ thống mạnh hơn bằng cách sử dụng các phương pháp hữu hạn không hình thức hóa được trong số học Peano, vào năm 1958, Gödel đã xuất bản một phương pháp chứng minh tính nhất quán của số học sử dụng lý thuyết kiểu.^[21] Năm 1936, Gerhard Gentzen đã đưa ra một định lý về tính nhất quán của các tiên đề của Peano, sử dụng quy nạp siêu hạn cho tới một số thứ tự gọi là ε₀.^[22] Gentzen giải thích: "Mục đích của bài viết hiện tại là chứng minh tính nhất quán của lý thuyết số cơ bản hay nói đúng hơn là rút gọn câu hỏi về tính nhất quán về các nguyên lí cơ bản nhất định". Định lí của Gentzen được cho là có tính hữu hạn, vì số thứ tự siêu hạn ε₀ có thể được mã hóa bằng các đối tượng hữu hạn (ví dụ, như một máy Turing mô tả một trật tự phù hợp trên các số nguyên, hoặc trừu tượng hơn là bao gồm các cây hữu hạn, được sắp xếp tuyến tính phù hợp). Việc định lí của Gentzen có đáp ứng các yêu cầu mà Hilbert đã hình dung hay không vẫn chưa rõ ràng: không có định nghĩa được chấp nhận chung về nghĩa chính xác của định lý hữu hạn là gì, và bản thân Hilbert không bao giờ đưa ra một định nghĩa chính xác.

Đại đa số các nhà toán học đương đại tin rằng các tiên đề của Peano là nhất quán, dựa vào trực giác hoặc chấp nhận một định lý nhất quán như định lý của Gentzen. Một số ít các nhà triết học và toán học, trong số họ cũng ủng hộ chủ nghĩa hữu hạn cực đoan, từ chối các tiên đề của Peano vì việc chấp nhận các tiên đề cũng có nghĩa là chấp nhận tập hợp vô hạn của các số tự nhiên. Ví dụ như, phép cộng (bao gồm cả hàm liền sau) và phép nhân được coi là toàn ánh. Kì lạ là, tồn tại các lý thuyết tự kiểm chứng tương tự như PA nhưng có phép trừ và phép chia thay vì phép cộng và phép nhân, mà được tiên đề hóa theo cách để tránh chứng minh các mệnh đề tương ứng với tính toàn xạ của cộng và nhân, nhưng vẫn có thể chứng minh tất cả định lý đúng lớp ${\displaystyle \Pi _{1}}$ của PA, và vẫn có thể được mở rộng thành một lý thuyết nhất quán chứng minh tính nhất quán của chính nó (rằng không tồn tại một định lí "0 = 1" theo kiểu Hilbert).^[23]

Xem thêm

• Nền tảng của toán học
• Định lý Frege
• Định lý Goodstein
• Chủ nghĩa logic cách tân
• Mô hình số học không chuẩn mực
• Định lý Paris–Harrington
• Số học Presburger
• Số học Robinson
• Số học bậc hai
• Lý thuyết số đánh máy

Chú thích

Tham khảo

Trích dẫn

Nguồn

Đọc thêm

• Raymond M. Smullyan (ngày 19 tháng 9 năm 2013). The Godelian Puzzle Book: Puzzles, Paradoxes and Proofs. Courier Corporation. ISBN 978-0-486-49705-1.

Liên kết ngoài

• Murzi, Mauro. “Henri Poincaré”. Internet Encyclopedia of Philosophy. Bản gốc lưu trữ ngày 2 tháng 2 năm 2004. Truy cập ngày 25 tháng 4 năm 2020. Gồm có một cuộc tranh luận về nhận xét của Poincaré về các tiên đề Peano.
• Podnieks, Karlis (ngày 25 tháng 1 năm 2015). “3. First Order Arithmetic”. What is Mathematics: Gödel's Theorem and Around. tr. 93–121.
• Hazewinkel, Michiel biên tập (2001), “Peano axioms”, Bách khoa toàn thư Toán học, Springer, ISBN 978-1-55608-010-4
• “Peano arithmetic”. PlanetMath.

• Weisstein, Eric W., "Peano's Axioms" từ MathWorld.
• Burris, Stanley N. (2001). “What are numbers, and what is their meaning?: Dedekind”. Bình luận về công trình của Dedekind.