Các định lý bất toàn của Gödel

Bách khoa toàn thư mở Wikipedia
Buớc tưới chuyển hướng Bước tới tìm kiếm

Các định lý bất toàn của Gödel là hai định lý nổi tiếng về logic toán học mô tả về giới hạn vốn có của mọi hệ thống rõ ràng chính thức có khả năng mô hình hóa số học cơ bản. Những định lý được Kurt Gödel xuất bản vào năm 1931, rất quan trọng trong logic toán học và triết học của toán học. Những định lý này rất rộng lớn nhưng không tổng quát, được diễn giải rằng mục tiêu chương trình Hilbert là để tìm một cách nhìn dứt khoát và hoàn toàn cho các tiên đề là điều không tưởng.

Định lý bất toàn đầu tiên đã xác định rằng không có hệ thống nhất quán của các tiên đề mà các định lý của nó có thể được lên danh sách trong một thủ tục hiệu quả (ví dụ như là một thuật toán) có thể chứng minh tất cả các sự thật về việc tính toán của các số tự nhiên. Đối với bất kỳ hệ thống chính thức dứt khoát nào, sẽ luôn là tình trạng về các số tự nhiên là đúng, nhưng sẽ không thể chứng minh được bằng hệ thống này. Định lý bất toàn thứ hai là mở rộng của định lý bất toàn thứ nhất, đã chứng minh hệ thống đó không thể biểu diễn được chính tính nhất quán của mình.

Sử dụng tranh luận đường chéo của Cantor, các định lý bất toàn của Gödel là hai trong số những định lý đầu tiên có sự liên hệ gần gũi về sự giới hạn của các hệ thống chính thức. Các định lý này được đi theo bởi định lý sự không xác định của Tarski bàn về sự không xác định chính thức của sự thật. Đồng thời, bằng chứng của Alonzo Church đã chứng minh rằng Entscheidungsproblem của David Hilbert là không thể giải quyết được cũng như định lý của Alan Turing cho rằng không có thuật toán nào để giải quyết các Bài toán dừng .

Hệ thống chính thức: sự hoàn hảo, sự nhất quán và sự tiên đề hóa hiệu quả[sửa | sửa mã nguồn]

Các định lý bất toàn được ứng dụng cho các hệ thống chính thức, những hệ thống có đủ sự phức tạp để biểu diễn thuật toán cơ bản của những số tự nhiên và có tính nhất quán và được tiên đề hóa một cách hiệu quả. Cụ thể là trong văn bản về logic trật tự thứ nhất, các hệ thống chính thức cũng được gọi là các lý thuyết chính thức. Nhìn chung, một hệ thống chính thức là một công cụ để suy diễn, bao gồm sự suy diễn của một trường hợp cụ thể của tiên đề với quy luật sử dụng các ký hiệu (hoặc quy luật của suy luận), cho phép rút ra một định lý mới từ các tiên đề. Một ví dụ là thuật toán Peano trật tự thứ nhất, một hệ thống mà tất cả các biến thể được sắp xếp để biểu diễn các số tự nhiên. Trong các hệ thống khác, như lý thuyết sắp đặt, chỉ một vài câu của hệ thống chính thức biểu diễn tình trạng của các số tự nhiên. Các định lý bất toàn nói về khả năng chứng minh chính thức với những hệ thống này, hơn là nói về khả năng chứng minh trong một hệ thống không chính thức.

Có một vài đặc tính mà một hệ thống chính thức có thể có, bao gồm sự hoàn toàn, sự nhất quán và sự tồn tại của sự tiên đề hóa hiệu quả. Các định lý bất toàn chỉ ra rằng hệ thống này, cái chứa một số lượng vừa đủ các tiên đề không thể chứa ba đặc tính này.

Sự tiên đề hóa hiệu quả[sửa | sửa mã nguồn]

Một hệ thống chính thức được cho là được tiên dề hóa một cách hiệu quả (hay được cho là đề hóa một cách hiệu quả) nếu như sự sắp xếp của nó đối với các định lý là bộ đệ quy.

Điều đó có nghĩa là có một chương trình tính toán mà về nguyên lý có thể liệt kê tất cả các định lý của hệ thống mà không lên danh sách bất kỳ tình trạng nào không phải là định lý. Ví dụ về lý thuyết được đề ra một cách có hiệu quả là thuật toán Peanolý thuyết sắp đặt Zermelo–Fraenkel.

Lý thuyết được biết đến là thuật toán chính xác bao gồm tất cả các tình trạng về số nguyên tiêu chuẩn trong ngôn ngữ của thuật toán Peano. Lý thuyết này nhất quán, và hoàn thiện, và bao gồm một số lượng vừa đủ các tiên đề. Tuy nhiên nó không có bộ đề quy của các tiên đề vì thế không thỏa mãn giải thuyết của định lý bất toàn.

Sự hoàn thiện[sửa | sửa mã nguồn]

Sự sắp xếp các tiên đề là hoàn thiện nếu như, đối với bất kỳ trường hợp nào trong ngôn ngữ của tiên đề, tình trạng đó hoặc sự phủ nhận nó là chưgns minh được đối với các tiên đề. Đây là một lưu ý thích đáng trong định lý bất toàn thứ nhất của Gödel. Không nên nhầm lẫn với sự hoàn thiện về ngữ nghĩa học với ý nghĩa là sự sắp xếp của các tiên đề chứng minh tất cả phép lặp thừa ngữ nghĩa của ngôn ngữ được sử dụng đến. Trong định lý hoàn thiện, Gödel đã chứng minh rằng logc trật tự thứ nhất là hoàn thiện về mặt ngữ nghĩa. Nhưng nó không hoàn thiện về mặt cú pháp, bởi vì có rất nhiều câu có thể diễn đạt trong ngôn ngữ của logic trật tự thứ nhất, điều này không thể được chứng minh hay không được chứng minh chỉ từ các tiên đề của logic.

Trong một hệ thống logic, sẽ là vô lý nếu kỳ vọng vào sự hoàn thiện cú pháp. Nhưng trong một hệ thống của toán học, những nhà tư tưởng như Hilbert tin rằng đó chỉ là vấn đề thời gian để tìm cách tiên đề hóa cho phép chứng minh hoặc không chứng minh (bằng phủ nhận của nó) mọi công thức toán học.

Một hệ thống chính thức có thể không hoàn thiện về mặt cú pháp, chẳng hạn như là logic về mặt tổng quát. Hoặc có thể không hoàn thiện đơn giản là vì không phải tất cả các tiên đề cần thiết được khám phá hay thêm vào. Ví dụ, hình học Euclid với định đề song song là không hoàn thiện, bởi vì có vài tình trạng trong hình học này không thể chưgns minh bằng các tiên đề đang tồn tại. Tương tự như vậy, lý thuyết về trật tự tuyến tính dày đặc không hoàn thiện, nhưng trở nên hoàn thiện với một tiên đề bổ sung cho rằng sẽ không có điểm kết thúc trong trật tự này. Giả thuyết continuum là một tinh trạng trong ngôn ngữ của lý thuyết sắp đặt Zermelo–Fraenkel, nó không thể được chứng minh với lý thuyết này. Vì vậy, lý thuyết sắp đặt Zermelo–Fraenkel là không hoàn thiện. Trong trường hợp này, không có một đề xuất hiển nhiên nào cho một định đề giải quyết được vấn đề.

Lý thuyết về thuật toán Peano trật tự thứ nhất là nhất quán, có một trật tự vô hạn đệ quy các tiên đề, và có thể lập mã thuật toán đầy đủ cho giả thuyết của định lý bất toàn. Vì thế, bằng định lý bất toàn thứ nhất, thuật toán Peano là không hoàn thiện. Định lý đã cho một ví dụ rõ ràng về một tình trạng của thuật toán không thể được chứng minh hay không được chứng minh trong thuật toán Peano. Thêm vào đó, tình trạng này là đúng trong hệ thống bình thường và. Đồng thời sự mở rộng nhất quán và không được nhất quán một cách hiệu quả của thuật toán Peano có thể là hoàn thiện.

Sự nhất quán[sửa | sửa mã nguồn]

Trật tự các tiên đề là nhất quán nếu như không có tình trạng nào mà nó và phủ nhận của nó là chứng minh được bằng các tiên đề và ngược là không chứng minh được.

Thuật toán Peano là nhất quán có thể chứng minh được bằng lý thuyết sắp đặt Zermelo–Fraenkel, nhưng không thể chứng minh được bằng chính nó. Tương tự như vậy với trường hợp của lý thuyết sắp đặt Zermelo–Fraenkel. nhưng lý thuyết này và "điều cơ bản không tới được" chứng minh lý thuyết là nhất quán bởi vì nếu κ là một điều chính yếu thì Vκ đặt trong vụ trụ von Neumann là một mô hình của lý thuyết nói trên. Và một lý thuyết nhất quán khi và chỉ khi nó có một mô hình.

Nếu có một lý thuyết biến tất cả các tình trạng trong thuật toán Peano như là các tiên đề, thì lý thuyết đó là hoàn thiện, và có một hệ đệ quy các tiên đề và có thể mô tả phép cộng và phép nhân. Tuy nhiên, nó không nhất quán.

Một ví dụ của lý thuyết không nhất quán là từ các nghịch lý, vốn là kết quả của lược đồ tiên đề của sự hiểu biết không hạn chế, được giả định trong lý thuyết sắp xếp.

Về việc áp dụng định lý bất toàn trong các lĩnh vực khác[sửa | sửa mã nguồn]

Một số lập luận phản biện và lập luận tương tự (analogy) đôi khi đưa ra các định lý không hoàn chỉnh để hỗ trợ các giả thuyết có chủ đề vượt ra ngoài phạm vi áp dụng của các định lý là toán họclogic. Ví dụ như chủ đề Nguồn gốc vũ trụTiến hóa, để củng cố cho thần học, một số sự hiểu lầm những định lý này dẫn đến khả năng tồn tại những vấn đề không thể giải thích cặn kẽ bằng logic khoa học - chúng có thể là căn cứ để "chứng minh" một thế lực mà sự tồn tại vượt ngoài phạm vi logic và là cơ sở cho thuyết Tạo hóa (Creationism); hay trong để chống lại chủ nghĩa hiện thực trong triết học.[1]

Tuy nhiên thực tế đa số lập luận trên là siêu hình, và xuất phát từ việc không hiểu rõ rằng hệ logic áp dụng phải là hệ chính thức (xem định nghĩa ở trên) chứ không phải là toàn bộ mọi hệ logic và mọi lĩnh vực. Lí do có thể là họ quy chụp, nhầm lẫn hoặc thừa nhận một mệnh đề phát biểu không chính xác giả thiết của các định lý; và một số tác giả uy tín đã có bình luận trái chiều về việc mở rộng phạm vi áp dụng và giải thích, lập luận như vậy, bao gồm: Torkel Franzén (2005); Panu Raatikainen (2005); Jean Bricmont (1999); và Ophelia BensonJeremy Stangroom (2006). Một số sách của các tác giả trên cũng hướng dẫn cách hiểu chính xác.

Bricmont và Stangroom (2006, trang 10), ví dụ, trích dẫn từ những bình luận của Rebecca Goldstein về sự khác biệt rõ ràng giữa chủ nghĩa Platon mà Gödel thừa nhận và những tư tưởng chống chủ nghĩa hiện thực mà đôi khi có trong những ý tưởng của ông đưa ra. Sokal và Bricmont (1999, trang 187) chỉ trích Régis Debray trong việc ông ta đã áp dụng định lý trong bối cảnh xã hội học; tuy vậy sau đó Debray đã phản biện rằng việc sử dụng này của ông ta chỉ là phép ẩn dụ chứ không có ý định áp dụng sai (sđd.).

Xem thêm[sửa | sửa mã nguồn]

Tham khảo[sửa | sửa mã nguồn]

Các tác phẩm của Gödel[sửa | sửa mã nguồn]

  • Kurt Gödel, 1931, "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I", Monatshefte für Mathematik und Physik, v. 38 n. 1, pp. 173–198.
  • —, 1931, "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I", in Solomon Feferman, ed., 1986. Kurt Gödel Collected works, Vol. I. Oxford University Press, pp. 144–195. ISBN 978-0195147209. The original German with a facing English translation, preceded by an introductory note by Stephen Cole Kleene.
  • —, 1951, "Some basic theorems on the foundations of mathematics and their implications", in Solomon Feferman, ed., 1995. Kurt Gödel Collected works, Vol. III, Oxford University Press, pp. 304–323. ISBN 978-0195147223.

Bản dịch các tác phẩm của Gödel khi ông còn sống[sửa | sửa mã nguồn]

  • B. Meltzer (translation) and R. B. Braithwaite (Introduction), 1962. On Formally Undecidable Propositions of Principia Mathematica and Related Systems, Dover Publications, New York (Dover edition 1992), ISBN 0-486-66980-7 (pbk.) This contains a useful translation of Gödel's German abbreviations on pp. 33–34. As noted above, typography, translation and commentary is suspect. Unfortunately, this translation was reprinted with all its suspect content by
  • Stephen Hawking editor, 2005. God Created the Integers: The Mathematical Breakthroughs That Changed History, Running Press, Philadelphia, ISBN 0-7624-1922-9. Gödel's paper appears starting on p. 1097, with Hawking's commentary starting on p. 1089.
  • Martin Davis editor, 1965. The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable problems and Computable Functions, Raven Press, New York, no ISBN. Gödel's paper begins on page 5, preceded by one page of commentary.
  • Jean van Heijenoort editor, 1967, 3rd edition 1967. From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931, Harvard University Press, Cambridge Mass., ISBN 0-674-32449-8 (pbk). van Heijenoort did the translation. He states that "Professor Gödel approved the translation, which in many places was accommodated to his wishes." (p. 595). Gödel's paper begins on p. 595; van Heijenoort's commentary begins on p. 592.
  • Martin Davis editor, 1965, ibid. "On Undecidable Propositions of Formal Mathematical Systems." A copy with Gödel's corrections of errata and Gödel's added notes begins on page 41, preceded by two pages of Davis's commentary. Until Davis included this in his volume this lecture existed only as mimeographed notes.

Tác phẩm của các tác giả khác[sửa | sửa mã nguồn]

Những cuốn sách về các định lý[sửa | sửa mã nguồn]

Tác phẩm gồm nhiều tác giả[sửa | sửa mã nguồn]

Liên kết ngoài[sửa | sửa mã nguồn]