Hệ tiên đề Peano

Giuseppe 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ăn bản như việc liệu lý thuyết số có nhất quán và hoàn chỉnh hay không.

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ơn dưới dạng 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 (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 lí thuyết 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ác ký hiệu phép toán cộng và nhân một cách tường minh 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à đã tái dựng lại bộ máy logic của ông ấy 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 phi 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:

1. 0 là một 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]

1. Với mọi số tự nhiên x, x = x. Tức là, quan hệ bằng nhau có tính phản xạ.
2. Với mọi số tự nhiên x và y, nếu x = y, thì y = x. Tức là, quan hệ bằng nhau có tính đối xứng.
3. Với mọi số tự nhiên x, y và z, nếu x = y và y = z, thì x = z. Tức là, quan hệ bằng nhau có tính bắc cầu.
4. Với mọi a và b, nếu b là một số tự nhiên và a = b, thì a cũng là một số tự nhiên. Tức là, tập số tự nhiên là đóng dưới quan hệ bằng nhau.

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.

1. Với mọi số tự nhiên n, S(n) là một số tự nhiên. Tức là, tập số tự nhiên là đóng dưới S.
2. Với mọi số tự nhiên m và n, m = n khi và chỉ khi S(m) = S(n). Tức là, S là một ánh xạ.
3. Với mọi số tự nhiên n, S(n) = 0 là sai. Tức là, không tồn tại số tự nhiên nào mà số liền sau là 0.

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.

1. Nếu K là một tập hợp thỏa mãn:
   • 0 thuộc K, và
   • với mỗi số tự nhiên n, n thuộc K suy ra S(n) thuộc K,
   thì K chứa mọi số tự nhiên.

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

1. Nếu φ là một vị từ sao cho:
   • φ(0) đúng, và
   • với mọi số tự nhiên n, φ(n) đúng bao hàm rằng φ(S(n)) cũng đúng,
   thì φ(n) đúng với mọi số tự nhiên n.

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à tập hợp 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ệ thứ tự toàn phần 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ố (Đứ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ó tính 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 (tiên đề quảng tính 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ý bất 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

• Cổng thông tin Triết học
• Cổng thông tin Toán học

• 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

1. "${\displaystyle \forall x\ (x\cdot 0=0)}$" có thể được chứng minh từ các tiên đề khác (trong logic bậc nhất) như sau. Thứ nhất, ${\displaystyle x\cdot 0+x\cdot 0=x\cdot (0+0)=x\cdot 0=x\cdot 0+0}$ bởi luật phân phối và phần tử đơn vị trên phép cộng. Thứ hai, ${\displaystyle x\cdot 0=0\lor x\cdot 0>0}$ theo tiên đề 15. Nếu ${\displaystyle x\cdot 0>0}$ thì ${\displaystyle x\cdot 0+x\cdot 0>x\cdot 0+0}$ bởi phép cộng với cùng một phần tử và tính giao hoán, và vì thế ${\displaystyle x\cdot 0+0>x\cdot 0+0}$ bằng phép thay thế, mâu thuẫn với tính không phản xạ. Vậy ${\displaystyle x\cdot 0=0}$.

Tham khảo

Trích dẫn

1. Grassmann 1861.
2. Peirce 1881, Shields 1997
3. van Heijenoort 1967, tr. 94.
4. van Heijenoort 1967, tr. 2.
5. ^ van Heijenoort 1967, tr. 83.
6. Peano 1889, tr. 1.
7. Partee, Ter Meulen & Wall 2012, tr. 215.
8. Harsanyi (1983).
9. Mendelson 1997, tr. 155.Lỗi sfn: không có mục tiêu: CITEREFMendelson1997 (trợ giúp)
10. Kaye 1991, tr. 16–18.
11. Suppes 1960, Hatcher 1982Lỗi harv: không có mục tiêu: CITEREFHatcher1982 (trợ giúp)
12. Tarski & Givant 1987, Section 7.6.
13. Hermes 1973, VI.4.3, presenting a theorem of Thoralf Skolem
14. Hermes 1973, VI.3.1.
15. Kaye 1991, Section 11.3.
16. Kaye 1991, tr. 70ff..
17. Fritz 1952, p. 137An illustration of 'interpretation' is Russell's own definition of 'cardinal number'. The uninterpreted system in this case is Peano's axioms for the number system, whose three primitive ideas and five axioms, Peano believed, were sufficient to enable one to derive all the properties of the system of natural numbers. Actually, Russell maintains, Peano's axioms define any progression of the form ${\displaystyle x_{0},x_{1},x_{2},\ldots ,x_{n},\ldots }$ of which the series of the natural numbers is one instance.
18. Gray 2013, p. 133So Poincaré turned to see whether logicism could generate arithmetic, more precisely, the arithmetic of ordinals. Couturat, said Poincaré, had accepted the Peano axioms as a definition of a number. But this will not do. The axioms cannot be shown to be free of contradiction by finding examples of them, and any attempt to show that they were contradiction-free by examining the totality of their implications would require the very principle of mathematical induction Couturat believed they implied. For (in a further passage dropped from S&M) either one assumed the principle in order to prove it, which would only prove that if it is true it is not self-contradictory, which says nothing; or one used the principle in another form than the one stated, in which case one must show that the number of steps in one's reasoning was an integer according to the new definition, but this could not be done (1905c, 834).
19. Hilbert 1902.
20. Gödel 1931.
21. Gödel 1958
22. Gentzen 1936
23. Willard 2001.

Nguồn

• Davis, Martin (1974). Computability. Notes by Barry Jacobs. Courant Institute of Mathematical Sciences, New York University.
• Dedekind, Richard (1888). Was sind und was sollen die Zahlen? [What are and what should the numbers be?] (PDF). Vieweg. Bản gốc (PDF) lưu trữ ngày 20 tháng 10 năm 2016. Truy cập ngày 4 tháng 7 năm 2016.
  • Two English translations:
    • Beman, Wooster, Woodruff (1901). Essays on the Theory of Numbers (PDF). Dover.
    • Ewald, William B. From Kant to Hilbert: A Source Book in the Foundations of Mathematics. Oxford University Press. tr. 787–832. ISBN 9780198532712.
• Fritz, Charles A., Jr. (1952). Bertrand Russell's construction of the external world.
• Gentzen, Gerhard (1936). Reprinted in English translation in his 1969 Collected works, M. E. Szabo, ed. “Die Widerspruchsfreiheit der reinen Zahlentheorie”. Mathematische Annalen. 112: 132–213. doi:10.1007/bf01565428.
• Gödel, Kurt (1931). See On Formally Undecidable Propositions of Principia Mathematica and Related Systems for details on English translations. “Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I” (PDF). Monatshefte für Mathematik. 38: 173–198. doi:10.1007/bf01700692.
• Gödel, Kurt (1958). Reprinted in English translation in 1990. Gödel's Collected Works, Vol II. Solomon Feferman et al., eds. “Über eine bisher noch nicht benützte Erweiterung des finiten Standpunktes”. Dialectica. Oxford University Press. 12: 280–287. doi:10.1111/j.1746-8361.1958.tb01464.x.
• Grassmann, Hermann (1861). “Lehrbuch der Arithmetik” [A tutorial in arithmetic] (PDF). Enslin.
• Gray, Jeremy (2013). “The Essayist”. Henri Poincaré: A scientific biography. Princeton University Press. tr. 133. ISBN 0-691-15271-3.
• Harsanyi, John C. (1983). “Mathematics, the empirical facts and logical necessity”. Erkenntniss. 19: 167 ff. doi:10.1007/978-94-015-7676-5_8.
• Hatcher, William S. (2014) [1982]. The Logical Foundations of Mathematics. Elsevier. ISBN 978-1-4831-8963-5. Derives the Peano axioms (called S) from several axiomatic set theories and from Thể loại theory.
• Hermes, Hans (1973). Introduction to Mathematical Logic. Hochschultext (Springer-Verlag). Springer. ISBN 3540058192. ISSN 1431-4657.
• Hilbert, David (1902). Winton, Maby biên dịch. “Mathematische Probleme” [Mathematical Problems]. Bulletin of the American Mathematical Society. 8: 437–479. doi:10.1090/s0002-9904-1902-00923-3.
• Kaye, Richard (1991). Models of Peano arithmetic. Oxford University Press. ISBN 0-19-853213-X.
• Landau, Edmund (1965). Grundlagen Der Analysis. Derives the basic number systems from the Peano axioms. English/German vocabulary included. AMS Chelsea Publishing. ISBN 978-0-8284-0141-8.
• Mendelson, Elliott (2009). Introduction to Mathematical Logic (ấn bản thứ 5). Taylor & Francis. ISBN 9781584888765.
• Partee, Barbara; Ter Meulen, Alice; Wall, Robert (2012). Mathematical Methods in Linguistics. Springer. ISBN 978-94-009-2213-6.
• Peirce, C. S. (1881). “On the Logic of Number”. American Journal of Mathematics. 4: 85–95. doi:10.2307/2369151. JSTOR 2369151. MR 1507856.
• Shields, Paul (1997). “3. Peirce's Axiomatization of Arithmetic”. Trong Houser, Nathan; Roberts, Don D.; Van Evra, James (biên tập). Studies in the Logic of Charles Sanders Peirce. Indiana University Press. tr. 43–52. ISBN 0-253-33020-3.
• Suppes, Patrick (1960). Axiomatic Set Theory. Dover. ISBN 0-486-61630-4. Derives the Peano axioms from ZFC
• Tarski, Alfred; Givant, Steven (1987). A Formalization of Set Theory without Variables. AMS Colloquium Publications. 41. American Mathematical Society. ISBN 978-0-8218-1041-5.
• van Heijenoort, Jean (1967). From Frege to Godel: A Source Book in Mathematical Logic, 1879–1931. Harvard University Press. ISBN 9780674324497.
  • Contains translations of the following two papers, with valuable commentary:
    • Dedekind, Richard (1890). Letter to Keferstein. On p. 100, he restates and defends his axioms of 1888. tr. 98–103.
    • Peano, Giuseppe (1889). Arithmetices principia, nova methodo exposita [The principles of arithmetic, presented by a new method]. An excerpt of the treatise where Peano first presented his axioms, and recursively defined arithmetical operations. tr. 83–97.
• Willard, Dan E. (2001). “Self-verifying axiom systems, the incompleteness theorem and related reflection principles” (PDF). The Journal of Symbolic Logic. 66 (2): 536–596. doi:10.2307/2695030. MR 1833464. Bản gốc (PDF) lưu trữ ngày 9 tháng 11 năm 2020. Truy cập ngày 25 tháng 4 năm 2020.

Đọ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ản gốc lưu trữ ngày 26 tháng 10 năm 2022. Truy cập ngày 25 tháng 4 năm 2020. Bình luận về công trình của Dedekind.