Godel và các định lý về Tính không Hoàn hảo (I)

Godel và các định lý về Tính không Hoàn hảo (I)

Karlis Podnieks

Người dịch: Hà Hữu Nga

Epimenides (thế kỷ VI BC) là một người đảo Cret tức giận với các đồng bào của mình, đã nói rằng “Tất cả những người Crets đều là những kẻ nói dối”. Vậy thì phán đoán này là chân hay giả?

a) Nếu phán đoán của Epimenides là chân thì Epimenides cũng là một người nói dối, tức là ông ta lúc nào cũng nói dối, vì vậy phán đoán của ông về toàn bộ dân Cret là giả (và có một người Cret không nói dối). Vậy là chúng ta đã gặp phải mâu thuẫn; b) Nếu phán đoán của Epimenides là giả thì có một người Cret không phải là người nói dối. Vậy thì bản thân Epimenides có phải là một người nói dối không? Trong trường hợp này chúng ta không gặp phải mâu thuẫn.

Vì vậy ở đây không có một nghịch lý trực tiếp mà chỉ có một chuỗi những kết luận đáng kinh ngạc: nếu một người Cret nói rằng “Toàn bộ dân Cret đều nói dối” thì có một người Cret không nói dối. Tuy nhiên, hãy không cho phép một người Cret duy nhất phỉ báng toàn bộ dân Cret. Để làm điều đó, chúng ta giả định rằng Epimenides đang nói về bản thân mình: “Tôi là một kẻ dối trá”. Câu nói này là chân hay giả? a) Nếu câu nói này là chân, thì Epimenides lúc nào cũng là kẻ dối trá, và vì vậy phán đoán của ông “Tôi là một kẻ dối trá” cũng là giả. Tức là Epimenides cũng là một kẻ dối trá (và cũng tức là đôi khi ông ấy không dối trá). Vậy là chúng ta đã gặp phải mâu thuẫn. b) Nếu phán đoán của Epimenides là giả thì ông không phải là một người dối trá, tức là đôi khi ông không nói dối. Vậy là trong trường hợp đặc biệt này ông đang dối trá.

Chúng ta không mắc phải mâu thuẫn ở đây. Hơn nữa ở đây không có một nghịch lý trực tiếp, chỉ là một chuỗi các kết luận đáng kinh ngạc: nếu ai đó nói “Tôi là một kẻ dối trá”, thì ông ta không phải (luôn luôn) là một kẻ dối trá. Bước tiếp theo trong câu truyện này là theo Eubulides (thế kỷ IV BC). Ông phán đoán: “Tôi đang nói dối”. Tức là ông ta nói rằng chính lúc này ông ta đang nói dối. Vậy là chân hay giả? a) Nếu phán đoán này là chân thì Eubulides là kẻ đang nói dối (ngay lúc này!), và vì vậy phán đoán của ông phải là giả. Trong trường hợp này chúng ta gặp phải mâu thuẫn. b) Nếu phán đoán này là giả thì Eubulides không phải đang nói dối, và vì vậy phán đoán của ông ta phải là chân. Trong trường hợp này chúng ta cũng gặp phải mâu thuẫn. Vậy là chúng ta gặp phải một nghịch lý thật, Nghịch lý Kẻ nói dối nổi tiếng.

Chúng ta sẽ phải tin rằng bất kỳ một câu nào loại nh­ư “Tôi đang viết” hoặc “Tôi đang đọc” phải là chân hay giả. Tuy nhiên câu “Tôi đang nói dối” lại không thể được đánh giá là chân hay giả mà không gặp phải những mâu thuẫn. Trong suốt khoảng thời gian 2000 năm người ta đã nghĩ rằng các nghịch lý như­ vậy phải được “giải quyết” bằng việc sáng tạo ra những “qui tắc nói chính xác” thích hợp. Như­ng họ chư­a bao giờ thành công 100%, vì bất cứ “qui tắc” nào như­ vậy không chỉ luôn luôn cấm (một vài chứ không phải tất cả) những nghịch lý, mà còn cấm nhiều câu vô hại, thậm chí hữu dụng. Đối với tôi, tiềm năng sáng tạo ẩn sau các nghịch lý dường như­ thú vị hơn nhiều so với các “qui tắc nói chính xác”. “Quá trình phát triển” của Nghịch lý nói dối được mô tả ở trên đã kết thúc vào thế kỷ XIV, khi Jean Buridan phán đoán nghịch lý này bằng một hình thức tuyệt đối rõ ràng:

“Toàn bộ những phán đoán về lá (folium) này đều giả”*. [Lưu ý: Chỉ có duy nhất một phán đoán này về "lá (folium) này"]. Và Buridan ngày nay sẽ nói đơn giản hơn:

p: p là giả.

Nếu p là chân, thì p phải là giả. Nếu p là giả thì p phải là chân.

Ghi chú: Buridan còn lừng danh với tư­ cách là tác giả của câu truyện con lừa nổi tiếng, một con vật đói đến chết vẫn đứng ở một khoảng cách không thay đổi giữa hai bó cỏ giống hệt nhau mà không thể tìm ra “những lập luận đầy đủ” để chọn một trong hai bó. Đối với những người tin rằng “các qui tắc nói đúng” không cho phép các phán đoán tự qui chiếu vào bản thân chúng, vào thế kỷ XIV, Albert von Sachsen đã đề xuất các nghịch lý sau: .

p1: p2 là giả,

p2: p1 là chân.

q1: q2 là giả,

q2: q3 là chân,

q3: q1 là giả.

Ngày nay, theo các ví dụ này, các nhà toán học có thể sáng tạo ra rất nhiều nghịch lý…Bạn hãy tự thử xem sao.

Chúng ta hãy thử “chấp nhận” Nghịch lý Nói dối bằng cách triển khai việc phân loại các phán đoán chỉ là chân hay giả: a) Các phán đoán chân; b) Các phán đoán giả; c) Các phán đoán không có giá trị-chân. Giờ ta xem xét phát đoán dưới đây:

q: q là giả hoặc q không có giá trị chân.

a) Nếu q là chân, thì cả q cũng là giả hoặc q không có giá trị chân, tức là q không chân - Chúng ta gặp phải một mâu thuẫn. b) Nếu q là giả, thì q là chân - Chúng ta gặp phải một mâu thuẫn. c) Nếu q không có giá trị chân, thì q là chân - Chúng ta gặp phải một mâu thuẫn. Vì vậy phân loại khai triển của chúng ta về các phán đoán là không hoàn hảo. Phán đoán q ở trên được gọi là

Nghịch lý Nói dối Mở rộng.

Theo một nghĩa nào đó thì Nghịch lý nói dối là một nghịch lý logic hai giá trị thông thường, và q là một nghịch lý của logic ba giá trị. Hãy công thức hóa một nghịch lý tương tự của logic bốn giá trị…vv. Chúng ta sẽ đi xa đến đâu theo con đ­ường này? Chi tiết lịch sử xin xem: N. I. Styazhkin. Sự hình thành Logic Toán. Nhà xuât bản Khoa học Moscow 1967, tiếng Nga, bản tiếng Anh: Styazhkin, N. I. History of Mathematical Logic from Leibniz to Peano. MIT Press, Cambridge, MA, 1969).

Nghịch lý Curry: Ý tưởng về nghịch lý sau do Haskell B. Curry đề xuất năm 1942 –trong quan niệm của chúng ta p: nếu p là chân thì q là chân (tức là p chỉ rõ phán đoán “nếu p, thì q”). Không đọc phần lý giải ở dưới. Hãy thử tự bạn phân tích lấy. Giải thích. p là chân hay giả? Nếu p là giả thì “nếu p, thì q” là chân, tức là p là chân. Nếu p là chân, thì “nếu p, thì q” hàm ý là q là chân. Vì vậy chúng ta đã chứng minh rằng q là chân. q là gì? Một xác quyết võ đoán! “Trần gian là vô giá trị!” – nh­ư bạn có thể đọc thêm trong bài viết Nghịch lý Curry – Curry’s Paradox trong Stanford Encyclopedia of Philosophy.

Bổ đề Tự qui chiếu

Liệu có thể hình thức hóa các nghịch lý ở những phần đã trình bày trư­ớc bằng một lý thuyết hình thức nh­ư PA không? Nếu bạn muốn tái cấu trúc Nghịch lý Nói dối, thì bạn phải xây dựng một công thức Q “xác quyết” rằng “PA chứng minh cho ￢Q: Q: PA chứng minh cho ￢Q. Bạn làm thế nào để bắt ép một công thức “xác quyết” các thuộc tính riêng của nó? Hơn nữa, bạn làm thế nào để bắt một công thức “nói” về các công thức? Thông thường, các công thức số học cấp một “nói” về các số tự nhiên. Để bắt các công thức này “nói” về bản thân chúng, chúng ta cần phải đưa ra một cách thức mã số nào đó cho các công thức.

Trư­ớc hết chúng ta hãy ấn định một cách liệt kê nào đó cho các biểu tượng cơ bản của PA (chúng ta hãy tạo ra những cái tên biến số qua mô thức sau: x, xa, xaa, xaaa…):

x	a	0	1	+	*	'=	(	)	￢	'∧'	'∨'	→	∃	∀
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14

Giờ đây mỗi công thức có thể được biểu hiện như­ là một dãy các con số tự nhiên. Chẳng hạn công thức x=xa+1+1 có thể được thể hiện là 0, 6, 0, 1, 4, 3, 4, 3. Bằng cách sử dụng hàm beta Godel β-function (Phần 3.3), mỗi dãy số tự nhiên có thể được thể hiện bằng hai con số. Chẳng hạn mã của công thức x=xa+1+1 sẽ bao gồm hoặc hai số m, n nh­ư sau:

β(m, n, 0)=10 (độ dài của công thức);

β(m, n, 1)=0; β(m, n, 2)=6; β(m, n, 3)=7; β(m, n, 4)=0; β(m, n, 5)=1;

β(m, n, 6)=4; β(m, n, 7)=3; β(m, n, 8)=7; β(m, n, 9)=4; β(m, n, 10)=3.

Từ Phần 3.3. chúng ta biết rằng vẫn tồn tại hai số. Như­ bước vừa rồi, chúng ta có thể biểu diễn cặp (m, n) bằng một số đơn k, chẳng hạn bằng:

k = (m+n)²+m.

Bài tập 5.3. cho biết làm cách nào để khôi phục m và n từ một k đã cho.

Vì vậy chúng ta có thể thể hiện mỗi PA-công thức F bằng một số tự nhiên đơn. Chúng ta hãy biểu thị định bằng F đậm thuật ngữ PA tương thích với con số này, và chúng ta hãy gọi nó là số Goedel của F. (Đó là ý tưởng của Goedel dùng để thể hiện các công thức bằng các con số, vì vậy tạo ra khả năng thảo luận về các công thức bằng ngôn ngữ số học). Khi có một công thức F, chúng ta có thể tính được số Goedel F của nó và khi có số F, chúng ta có thể khôi phục được F.

L­ưu ý: Ngày nay ý tưởng về việc mã hóa các công thức bằng số d­ường như­ là hoàn toàn thông thường (chỉ là “một cách mã hóa khác” trong nhiều cách được sử dụng trong computer mỗi giây). Tuy nhiên vào năm 1930, khi Goedel lần đầu tiên sáng tạo ra cách mã hóa nh­ư vậy, thì đó có lẽ là một trong những ý tưởng khó khăn nhất của cách chứng minh về tính chất không hoàn hảo nổi tiếng của ông. Giờ đây chúng ta lấy hai PA-công thức C(x) và B. Chúng ta có thể coi công thức C(B) như­ một xác quyết “công thức B có thuộc tính C”. Nếu chúng ta có thể chứng minh bằng PA rằng B ↔ C(B), thì chúng ta có thể nói rằng B “xác quyết” rằng nó có thuộc tính C.

Bổ đề Tự qui chiếu: Nếu một PA-công thức C(x) chứa chính xác một biến số tự do, thì người ta có thể xây dựng một PA-công thức B đóng đến mức: PA chứng minh: B ↔ C(B). L­ưu ý: Trong các cuốn sách giáo khoa, bổ đề này cũng được gọi là Bổ đề Chéo hóa hoặc là Bổ đề Điểm-Cố định.

Chứng minh. Chúng ta hãy giới thiệu cái gọi là hàm thay thế sub(x, y). Chúng ta xác định giá trị sub(x, y) nh­ sau: nếu x là số Goedel của một công thức F(u, v, w,…) nào đó, thì chúng ta thay thế thuật ngữ-số y cho tất cả những biến số tự do của F, tức là chúng ta có được công thức F(y, y, y,…), thì chúng ta tính số Goedel n của nó, và đặt sub(x, y) = n. Nếu x không phải là số Goedel của một công thức thì chúng ta đặt sub(x, y) = 0.

Không nghi ngờ gì nữa, sub(x, y) là một hàm có thể tính toán. Cho x và y, tr­ước hết chúng ta xác định là số x của một công thức nào đó hoặc không. Nếu không, hàm của chúng ta sẽ quay về 0. Nếu có thì chúng ta khôi phục được công thức, thay thế y cho toàn bộ các biến số tự do của nó và quay trở về với số của công thức đã đạt được. Không có vấn đề mã hóa chư­ơng trình này, chẳng hạn, bằng Pascal (đó sẽ là một công việc mở rộng, như­ng không phải là một công việc khó). Một công việc đôi chút buồn tẻ là mã hóa chư­ơng trình của sub(x, y) cho một máy Turing. Chúng ta sẽ không làm công việc này ở đây, bằng cách sử dụng luận đề Church thay thế: một hàm bất kỳ d­ường như­ có thể tính toán có thể được mã hóa cho một máy Turing thích hợp.

Vì vậy chúng ta giả định rằng chúng ta đã có một máy Turing tính sub(x, y). Bằng cách sử dụng thuật toán từ cách chứng minh của định lý Biểu diễn (phần 3.3) chúng ta có hể xây dựng một PA-công thức SUB(x, y, z) sao cho thay cho tất cả k, m, n: nếu sub(k, m) = n, thì

a) PA chứng minh cho SUB(k, m, n),  b) PA chứng minh cho: ￢(z=n) → ￢SUB(k, m, z).

Bước đầu tiên. Có hai công thức SUB(x, y, z) và C(x) chúng ta hãy giới thiệu công thức sau C₁(x): C(sub(x, x)). Hoặc chính xác hơn (vì chúng ta không có biểu tượng hàm sub bằng PA):

Az(SUB(x, x, z) → C(z)).

Ý tưởng chính ở đây là lặp x trong sub! Giờ đây cái gì được “xác quyết” trong công thức C₁(x)? Về nghĩa đen, đó là: “Hãy lấy số x, phục hồi từ x công thức F_x(u, v, w,...) khi có số này, thay x (tức là tự thân số F_x) cho tất cả các biến số tự do của F_x, sau đó bạn sẽ có được công thức F_x (x, x, x,...) có thuộc tính C”.

Bước thứ hai. Chúng ta hãy cố áp dụng thao tác này vào bản thân công thức C₁(x)! Tức là nếu k là số của C₁(x) thì chúng ta hãy chỉ thị bằng B công thức C₁(k). Cái gì là “xác quyết” của B? Nếu bạn có được công thức khi có số k (tức là công thức C₁(x)), và thay số k của nó cho x, thì bạn sẽ có được một công thức (thực tế là công thức C₁(k), tức là công thức B) có thuộc tính C”. Vì vậy B xác quyết: “Tôi có thuộc tính C!”

Tuy nhiên không nên cố gắng đi theo lập luận trên hơn hai lần. Nó có thể gây ra những vấn đề về sức khỏe – Bổ đề Tự qui chiếu là một loại định lý điểm-cố định!. Giờ đây, để hoàn thành việc chứng minh, chúng ta phải chứng minh bằng PA rằng B ↔ C(B).

1. Chúng ta hãy chứng minh bằng PA rằng B → C(B). Chúng ta hãy giả sử B, tức là C₁(k), hoặc

Az(SUB(k, k, z) → C(z)).            (1)

Vì sub(k, k)= B, nên:

PA chứng tỏ: SUB(k, k, B), và PA chứng tỏ: ￢(z=k) → ￢SUB(k, k, z).          (2)

Vì vậy, z trong (1) bằng B, và chúng ta đạt được C(B). Định lý Diễn dịch thực hiện phần còn lại: PA chứng tỏ: B → C(B).

2. Chúng ta hãy chứng tỏ bằng PA rằng C(B) → B. Chúng ta hãy giả định C(B). Sau đó chúng ta có SUB(k, k, B) → C(B). Thêm (2) vào đó, và bạn sẽ có Az(SUB(k, k, z) → C(z)), và đây chính xác là công thức B. Định lý Diễn dịch làm nốt phần còn lại: PA chứng tỏ: C(B) → B.

Vậy là đối với một thuộc tính bất kỳ nào của các công thức chúng ta đều có thể xây dựng một công thức “xác quyết” cái mà nó có thuộc tính này.

Kurt Goedel đã sáng tạo ra lập luận được sử dụng trong việc chứng minh Bổ đề Tự qui chiếu để chứng minh định lý về tính chất không hoàn hảo nổi tiếng của ông vào năm 1930. Tuy nhiên ông đã không hình thức hóa Bổ đề Tự qui chiếu nh­ư một phán đoán tổng quát. Trong những ghi chú sau này, ông qui phán đoán đó vào Rudolf Carnap (xem các bản copies tất cả những bài viết có liên quan trong Davis 1965).

Định lý về tính không hoàn hảo của Goedel

Hình như­ Bổ đề Tự qui chiếu cho phép hình thức hóa nghịch lý Kẻ nói dối bằng PA. Bằng cách ấy, tính chất mâu thuẫn của PA sẽ được chứng minh? Phiên bản hình thức của nghịch lý Kẻ nói dối sẽ là một công thức L xác quyết “PA chứng minh ￢L”. Sau đó ￢L sẽ xác quyết "PA không chính minh ￢L". Vì vậy thay cho L chúng ta có thể sử dụng một công thức G xác quyết “PA không thể chứng minh G” (tức là “Tôi không thể được chứng minh bằng PA”). Phiên bản này của nghịch lý Kẻ nói dối đã được sử dụng trong phép chứng minh nguyên gốc của Goedel. Vì vậy chúng ta hãy đi theo truyền thống. Chúng ta có thể diễn đạt công thức của Goedel:

G: PA không thể chứng minh G

từ Bổ đề Tự qui chiếu, nếu chúng ta có một công thức PR(x) xác quyết “công thức số x có thể được chứng minh bằng PA”. Thực tế, bằng cách áp dụng bổ đề này vào công thức ￢PR(x) chúng ta sẽ đạt được công thức G như­ sau

PA chứng minh: G ↔ ￢PR(G),

tức là G sẽ tương đư­ơng với “PA không thể chứng minh G”. Vậy thì tr­ước hết chúng ta hãy xây dựng công thức PR(x). Mỗi cách chứng minh (bằng PA) là một dãy công thức. Thay thế toàn bộ các công thức bằng các số Goedel của chúng, điều đó đảo ngư­ợc mỗi cách chứng minh thành một dãy các số tự nhiên. Bạn có thể mã hóa dãy này bằng một số đơn (bằng cách sử dụng các kỹ thuật đã đề cập). Chúng ta hãy gọi số này là số chứng minh Goedel. Cho một số tự nhiên y, bạn có thể

a) Xác định xem y có phải là một số dãy công thức nào đó hay không; b) Nếu có, thì bạn có thể khôi phục được dãy đó; c) Khi có dãy công thức bạn có thể kiểm tra xem liệu đó có phải là một phép chứng minh bằng PA không. Trong một PA-chứng minh mỗi công thức phải là một tiên đề của PA, hoặc một tiên đề logic, hoặc nó phải được dẫn xuất từ những công thức nào đó trước của phép chứng minh bằng cách sử dụng một trong những qui tắc suy luận logic. Vì vậy điều khẳng định sau đây dư­ờng như­ có thể tính toán được:

prf(x, y) = "y là một số-chứng minh của công thức số x".

Theo luận đề của Church chúng ta có thể cấu trúc một máy Turing kiểm tra chính xác giá trị chân của prf(x, y) cho x và y tùy ý. Sau đó theo định lý Biểu diễn (phần 3.3) chúng ta có thể cấu trúc một PA-công thức PRF(x, y) thể hiện hàm mệnh đề prf(x, y).

Giờ đây chúng ta lấy công thức ∃yPRF(x, y) làm công thức xác quyết “công thức số x có thể được chứng minh bằng PA”. Bằng cách áp dụng Bổ đề Tự qui chiếu vào công thức ￢∃yPRF(x, y), chúng ta được công thức G của Goedel nh­ư sau:

PA chứng minh: G ↔ ￢∃yPRF(G, y).           (1)

Tức là G có nghĩa "PA không chứng minh G".

Chúng ta hãy thử kiểm tra xem xác quyết của G là chân hay giả.

1. Trư­ớc hết chúng ta hãy giả định rằng PA chứng minh G, và k là số của chứng minh này. Vậy là prf(G, k) là chân, và vì vậy

PA chứng minh: PRF(G, k),

PA chứng minh: EyPRF(G, y),

PA chứng minh: ￢G

(xem (1)). Vì vậy nếu chúng ta có một PA-chứng minh của G, thì chúng ta có thể cũng xây dựng được một PA-chứng minh của ￢G, tức là PA sẽ là mâu thuẫn. Có phải PA không mâu thuẫn? Tôi không biết. Tuy nhiên nếu nó không mâu thuẫn thì G không thể được chứng minh bằng PA.

2. Giờ đây chúng ta hãy giả định rằng ngư­ợc lại - PA chứng minh ￢G. Thì PA cũng chứng minh ￢∃yPRF(G, y) (xem (1)). Về mặt trực giác, ￢∃yPRF(G, y) có nghĩa là có tồn tại PA-chứng minh của G, tức là có vẻ là PA cũng mâu thuẫn trong trường hợp này?

Tuy nhiên chúng ta phải cẩn thận: nếu PA chứng minh ￢∃yPRF(G, y), vậy có phải là điều đó có nghĩa là bằng việc thay thế cho y một bằng y một tất cả các số 0, 1, 2, 3,... , và kiểm tra mỗi trường hợp, chúng ta sẽ tìm được cách chứng minh G?

Có lẽ chúng ta sẽ nghĩ nh­ư vậy, như­ng chúng ta không thể chứng minh được rằng trường hợp này là như­ vậy. Nếu bằng phương pháp thay thế và kiểm tra vừa đề cập ở trên, chúng ta sẽ thực sự tìm được một cách chứng minh của G, sau đó PA sẽ được chứng minh là mâu thuẫn. Tuy nhiên sẽ là gì nếu chúng ta không bao giờ tìm được một cách chứng minh của G? Sau đó chúng ta sẽ không có mâu thuẫn trực tiếp trong PA. Tuy nhiên, chúng ta sẽ có một tình huống không thỏa mãn: có một công thức C(y) (cụ thể là PRF(G, y)) như­ sau:

a) PA chứng minh: ∃yC(y),

b) Cho mỗi k, PA chứng minh: ￢C(k).

Đây không phải là một mâu thuẫn “trực tiếp” mà chúng ta phải chứng minh ∀y￢C(y). Chúng ta có một cách chứng minh tách biệt của ￢C(y) cho mỗi giá trị đặc biệt của y. Vậy thì bạn có thể thay thế dãy vô tận này của PA-chứng minh đặc biệt bằng một PA-chứng minh đơn (hữu hạn!) của ∀y￢C(y) không? Tôi thì không. Và Goedel cũng không thể. Ông buộc phải đưa ra khái niệm w-mẫu thuẫn (mâu thuẫn yếu hoặc omega-mâu thuẫn) để chỉ định tình huống không thỏa mãn trên.

Định lý Bất hoàn hảo của Goedel (cho PA).

Người ta có thể xây dựng một PA-công thức G đóng như­ sau: a) Nếu PA chứng minh G, thì PA là mâu thuẫn; b) Nếu PA chứng minh ￢G, thì PA là mâu thuẫn yếu. Tại sao định lý này lại được coi là một trong những kết quả cách mạng nhất trong logic toán?

Hãy lấy F là một công thức đóng của một lý thuyết hình thức T nào đó. Nếu không phải F cũng không phải ￢F có thể được chứng minh bằng cách sử dụng các tiên đề của T thì F được gọi là không thể giải được bằng T (hoặc T- không thể giải được). Tức là F tiên đoán một thuộc tính “tuyệt đối xác định” nào đó của các “đối tượng” của T, như­ng tiên đoán này có thể không được chứng minh, cũng không bị bác bỏ. Một lý thuyết bao gồm các công thức không thể giải được thì được gọi là lý thuyết không hoàn hảo. Vì vậy thuật ngữ “định lý không hoàn hảo” được thể hiện: nếu PA là mâu thuẫn yếu, thì PA là không hoàn hảo. 

Tuy nhiên không nên nghĩ rằng chúng ta đã chứng minh được tính chất không hoàn hảo của PA. Chúng ta có thể chứng minh tính không thể giải được của công thức G của Goedel chỉ sau khi chúng ta đã chứng minh được rằng PA là không-mâu thuẫn yếu. Đến đây chúng ta mới chỉ chứng minh được rằng PA là không hoàn hảo: PA vừa là mâu thuẫn yếu, hoặc không hoàn hảo. Tức là khi phát triển PA, chúng ta rõ ràng đụng chạm phải một mâu thuẫn yếu, hoặc một vấn đề về số tự nhiên không thể giải quyết được bằng cách sử dụng các tiên đề của PA. (Một trong những vấn đề nh­ư vậy có thể được thể hiện bằng công thức G của Goedel. Nó chỉ có vẻ là G bận bịu với tính chất có thể chứng minh của riêng nó, cuối cùng thì với t­ư cách một PA-công thức đóng G xác quyết một thuộc tính nào đó của các số tự nhiên!)

Trong biên bản thảo luận của Carnap 15 tháng Giêng 1931 với nhóm Schlick có ghi bằng tiếng Đức: "Gödel stellt dem gegenüber fest, das die von ihm angegebene unentscheidbare Formel wirklich konstruierbar ist. Ihr Inhalt ist finit wie der des Goldbachschen oder Fermatschen Satzes." “Godel đã đưa ra một phản chứng, được bản thân ông cụ thể hóa thành một công thức không thể xác định, thực sự lại mang tính suy diễn. Nội dung của nó cũng hữu hạn chẳng khác gì nội dung của Goldbach hoặc Định lý Cuối cùng của Fermat” (trích theo Mancosu [1999]).

Nếu các tiên đề của chúng ta không hoàn hảo, chúng ta có thể cố cải thiện chúng. Có lẽ chúng ta đã đánh mất những tiên đề thiết yếu nào đó? Chúng ta hãy thêm những tiên đề này vào PA, và chúng ta sẽ đạt được … một lý thuyết hoàn hảo?

Thật không may là điều này lại không thể. Chứng minh của Goedel vẫn có giá trị cho bất cứ sự khai triển nào của PA. Một sự khai triển của PA dù chỉ là một lý thuyết hình thức T nào đó (bằng ngôn ngữ của PA). Tức là bằng định nghĩa, hàm logic: prf_T(x, y) = "y là một T-chứng minh-số của công thức số x” phải là có thể tính toán được (một lý thuyết được gọi là hình thức khi và chỉ khi chúng ta có một thao tác “cơ giới” cho việc kiểm tra tính chất chính xác của phép chứng minh bằng lý thuyết này). Vì vậy chúng ta có thể xây dựng một công thức PRF_T(x, y) thể hiện hàm logic bằng PA. Chúng ta hãy lại áp dụng Bổ đề Tự qui chiếu, và chúng ta sẽ có một công thức đóng G_T nh­ sau: PA chứng minh: G_T ↔ ￢∃yPRF_T (G_T, y), tức là G_T "xác quyết" tính không thể chứng minh của riêng nó bằng T.

Hãy chứng minh rằng nếu T là một mở rộng của PA (tức là nếu T có thể chứng minh toàn bộ các định lý của PA), thì: a) Nếu T chứng minh G_T, thì T là mâu thuẫn; b) Nếu T chứng minh ￢G_T, thì T là mâu thuẫn yếu (w-inconsistent). Vì vậy phương pháp Goedel cho phép chứng minh rằng một hệ tiên đề hoàn hảo của một số số học tự nhiên là không thể: bất cứ hệ nào như­ vậy cũng đều mâu thuẫn yếu, hoặc là không đủ để giải quyết một số vấn đề số tự nhiên.

_____________________________________

Nguồn: Podnieks, Karlis 1997. What is Mathematics: Godel's Theorem and Around, University of Latvia, Institute of Mathematics and Computer Science.

Tác giả: Tiến sĩ Kārlis Podnieks nghiên cứu toán học tại Đại học Latvia 1966-71. Năm 1979, ông nhận bằng tiến sĩ toán học, Trung tâm Tin học của Viện Hàn lâm Khoa học Liên Xô ở Moscow. Ban đầu, ông chủ yếu quan tâm nghiên cứu cơ sở của toán học. Năm 1980, ông chuyển sang các khía cạnh lý thuyết và thực tiễn của việc tính toán, bao gồm lập trình máy tính, thiết kế cơ sở dữ liệu, hệ thống thông tin, phát triển công cụ đồ họa để mô hình hóa quá trình kinh doanh. Tuy vậy, ông vẫn tiếp tục viết về các cơ sở triết học của toán học, và tác phẩm của ông đều nổi tiếng vì cái nhìn sâu sắc, hài hước và độc đáo. Ông trở thành giáo sư công nghệ thông tin tại trường Đại học Latvia năm 2005.

Ghi chú của người dịch: Còn nhớ ngày xưa, từ Khoa sử ở Mễ Trì, lọ mọ lên Thượng Đình học trộm toán của thầy Vinh, thầy Quốc, thầy Châu...v.v. Cuối những năm 1970 - đầu 1980, tuy đã ra trường, đi làm, nhưng thực chất là "thất nghiệp tại chỗ làm", đầu quân với thầy Nguyễn Hoàng Phương, mỗi tháng đóng 1 đồng để thuê Hội trường Lê Thánh Tông, cùng Dũng, Sinh, Thảo (Khoa Lý) học mót toán, và nghe giảng miễn phí mấy thứ kinh hoàng khác của Thầy. Toán thì miễn bàn, nhưng riêng về mấy thứ kinh hoàng thì mấy thằng bạn khoa Lý phê như chan tương, còn mấy đứa khoa xã hội thì ca ngợi lên tận mây xanh. 

* Lá đại số tiêu biểu với Folio của Descartes là một đường cong được xác định bằng phương trình x³ + y³ – 3 axy = 0. Phán đoán này có dạng lá kép ở gốc và đường tiệm cận x + y + a = 0. Dạng đối xứng là y = x. Nguyên lý Buridan Folio, Con lừa Buridan là dạng y = x.