Định lý về tính không đầy đủ của Gödel trong các thuật ngữ đơn giản. Sự thật thú vị và lời khuyên hữu ích

Bất kỳ hệ tiên đề toán học nào, bắt đầu từ một mức độ phức tạp nhất định, đều không nhất quán hoặc không đầy đủ về mặt nội tại.

Năm 1900, Hội nghị các nhà toán học thế giới được tổ chức tại Paris, tại đó David Hilbert (1862-1943) đã trình bày dưới dạng tóm tắt 23 bài toán quan trọng nhất, theo quan điểm của ông, những vấn đề do ông đưa ra, cần được giải quyết bởi các nhà khoa học lý thuyết. của thế kỷ XX sắp tới. Số hai trong danh sách của anh ấy là một trong những nhiệm vụ đơn giản, câu trả lời dường như hiển nhiên cho đến khi bạn tìm hiểu sâu hơn một chút. đang nói ngôn ngữ hiện đại, đó là câu hỏi: liệu toán học tự nó có đủ không? Vấn đề thứ hai của Hilbert là chứng minh một cách chặt chẽ rằng hệ thống tiên đề- các câu lệnh cơ bản được lấy trong toán học làm cơ sở mà không cần chứng minh - là hoàn hảo và đầy đủ, tức là nó cho phép bạn mô tả một cách toán học mọi thứ tồn tại. Cần phải chứng minh rằng có thể thiết lập một hệ thống tiên đề như vậy, thứ nhất, chúng sẽ nhất quán lẫn nhau, và thứ hai, người ta có thể rút ra kết luận từ chúng về sự thật hay sai của bất kỳ phát biểu nào.

Hãy lấy một ví dụ từ hình học trường học. Tiêu chuẩn Phép đo Euclidean(hình học trên mặt phẳng) có thể chứng minh vô điều kiện rằng phát biểu "tổng các góc của tam giác là 180 °" là đúng và phát biểu "tổng các góc của tam giác là 137 °" là sai. Về cơ bản, trong hình học Euclid, bất kỳ phát biểu nào là sai hoặc đúng, và câu thứ ba không được đưa ra. Và vào đầu thế kỷ 20, các nhà toán học đã ngây thơ tin rằng tình huống tương tự cần được quan sát trong bất kỳ hệ thống nhất quán về mặt logic nào.

Và sau đó vào năm 1931, một số nhà toán học đeo kính đeo mắt người Vienna, Kurt Godel đã thực hiện và xuất bản một bài báo ngắn đơn giản là làm đảo lộn toàn bộ thế giới của cái gọi là "logic toán học". Sau những phần mở đầu lý thuyết và toán học dài và phức tạp, ông thực sự đã thiết lập được những điều sau đây. Hãy lấy bất kỳ phát biểu nào như: "Giả định số 247 là không thể chứng minh được về mặt logic trong hệ tiên đề này" và gọi nó là "phát biểu A". Vì vậy, Gödel chỉ đơn giản là chứng minh tài sản tuyệt vời sau không tí nào hệ thống tiên đề:

"Nếu một tuyên bố A có thể được chứng minh, thì một tuyên bố không phải A có thể được chứng minh."

Nói cách khác, nếu có thể chứng minh tính hợp lệ của nhận định “Giả thiết 247 không phải có thể chứng minh được ”, khi đó có thể chứng minh tính hợp lệ của phát biểu“ Giả định 247 có thể chứng minh được". Tức là, quay trở lại công thức của bài toán Hilbert thứ hai, nếu hệ tiên đề đầy đủ (tức là bất kỳ phát biểu nào trong đó cũng có thể chứng minh được) thì nó không nhất quán.

Cách duy nhất để thoát khỏi tình huống này là chấp nhận một hệ thống tiên đề không hoàn chỉnh. Đó là, chúng ta phải đối mặt với thực tế rằng trong bối cảnh của bất kỳ hệ thống logic nào, chúng ta sẽ chỉ còn lại những phát biểu “loại A” rõ ràng là đúng hoặc sai - và chúng ta chỉ có thể đánh giá sự thật của chúng. ở ngoài khuôn khổ của tiên đề mà chúng tôi đã áp dụng. Nếu không có những phát biểu như vậy, thì tiên đề của chúng ta là mâu thuẫn, và trong khuôn khổ của nó chắc chắn sẽ có những công thức vừa có thể chứng minh vừa có thể bác bỏ.

Vì vậy, từ ngữ Đầu tiên,hoặc Yếu Các định lý về tính không đầy đủ của Gödel: "Bất kỳ hệ thống tiên đề chính thức nào đều chứa các giả định chưa được giải đáp." Nhưng Gödel không dừng lại ở đó, xây dựng và chứng minh thứ hai, hoặc mạnh Định lý về tính không đầy đủ của Godel: “Tính đầy đủ logic (hoặc không đầy đủ) của bất kỳ hệ thống tiên đề nào không thể được chứng minh trong khuôn khổ của hệ thống này. Để chứng minh hoặc bác bỏ nó, cần phải có thêm các tiên đề (tăng cường hệ thống). ”

Sẽ an toàn hơn nếu nghĩ rằng các định lý của Godel là trừu tượng và không liên quan đến chúng ta, mà chỉ là các lĩnh vực logic toán học cao siêu, nhưng thực tế hóa ra chúng có liên quan trực tiếp đến cấu trúc của bộ não con người. Nhà toán học và vật lý người Anh Roger Penrose (sinh năm 1931) đã chỉ ra rằng các định lý của Gödel có thể được sử dụng để chứng minh sự khác biệt cơ bản giữa não người và máy tính. Quan điểm của lý luận của anh ấy rất đơn giản. Máy tính hoạt động một cách logic chặt chẽ và không thể xác định được câu A là đúng hay sai nếu nó vượt ra ngoài phạm vi của tiên đề, và những câu như vậy, theo định lý Gödel, chắc chắn sẽ tồn tại. Một người, đối mặt với một tuyên bố A không thể chứng minh được về mặt logic và không thể bác bỏ, luôn có thể xác định được sự thật hay giả dối của nó - dựa trên kinh nghiệm hàng ngày. Ít nhất là trong này não người hoạt động tốt hơn một máy tính bị cùm bằng sạch mạch logic. Bộ não của con người có thể hiểu được toàn bộ chiều sâu của sự thật chứa đựng trong các định lý của Gödel, nhưng một chiếc máy tính thì không bao giờ có thể hiểu được. Do đó, bộ não của con người là bất cứ thứ gì ngoại trừ một máy tính. Anh ấy có khả năng đưa ra quyết định, và bài kiểm tra Turing sẽ vượt qua.

Tôi tự hỏi liệu Hilbert có biết những câu hỏi của anh ấy sẽ đưa chúng ta đi bao xa không?

Kurt Godel, 1906-78

Nhà toán học người Áo, sau đó là người Mỹ. Sinh ra tại Brünn (Brünn, nay là Brno, Cộng hòa Séc). Ông tốt nghiệp Đại học Vienna, nơi ông vẫn là giáo viên tại Khoa Toán học (từ năm 1930 - một giáo sư). Năm 1931, ông đã công bố một định lý mà sau này được đặt tên cho ông. Là một người hoàn toàn phi chính trị, anh ấy đã vô cùng khó khăn khi sống sót sau vụ giết người bạn và nhân viên của bộ phận bởi một sinh viên Đức Quốc xã và rơi vào tình trạng trầm cảm sâu sắc, những lần tái phát đã ám ảnh anh ấy cho đến cuối đời. Trong những năm 1930, ông di cư đến Hoa Kỳ, nhưng trở về quê hương Áo và kết hôn. Năm 1940, ở đỉnh điểm của chiến tranh, ông buộc phải chạy sang Mỹ để quá cảnh qua Liên Xô và Nhật Bản. Làm việc một thời gian tại Viện Princeton nghiên cứu nâng cao. Thật không may, tâm lý của nhà khoa học không thể chịu đựng được, và ông chết đói trong một phòng khám tâm thần, từ chối ăn, vì ông tin rằng họ định đầu độc ông.

Từ lâu, tôi đã quan tâm đến định lý Gödel giật gân là gì. Và nó có ích cho cuộc sống như thế nào. Và cuối cùng tôi đã có thể tìm ra nó.

Công thức phổ biến nhất của định lý là:
"Bất kỳ hệ thống tiên đề toán học nào, bắt đầu từ một mức độ phức tạp nhất định, đều không nhất quán hoặc không hoàn chỉnh bên trong."

Tôi sẽ dịch nó sang một ngôn ngữ phi toán học của con người như thế này (tiên đề là vị trí ban đầu của một lý thuyết, được chấp nhận trong khuôn khổ của lý thuyết này là đúng mà không cần chứng minh và được sử dụng làm cơ sở để chứng minh các điều khoản khác của nó). Trong cuộc sống, tiên đề là những nguyên tắc được tuân theo bởi một con người, xã hội, hướng khoa học, Những trạng thái. Trong số các đại diện của tôn giáo, tiên đề được gọi là tín điều. Do đó, bất kỳ nguyên tắc nào của chúng ta, bất kỳ hệ thống quan điểm nào, bắt đầu từ một cấp độ nhất định, đều trở nên mâu thuẫn nội bộ hoặc không hoàn chỉnh. Để được thuyết phục về sự thật của một tuyên bố nào đó, người ta sẽ phải vượt ra khỏi hệ thống quan điểm đã cho và xây dựng một hệ thống quan điểm mới. Nhưng nó cũng sẽ không hoàn hảo. Tức là QUÁ TRÌNH KIẾN THỨC LÀ INFINITE. Thế giới không thể được biết đầy đủ cho đến khi chúng ta tiếp cận được nguồn gốc.

"... nếu chúng ta coi khả năng suy luận logic là đặc điểm chính của bộ óc con người, hoặc ít nhất là công cụ chính của nó, thì định lý Gödel trực tiếp chỉ ra những khả năng hạn chế của bộ não chúng ta. Đồng ý rằng rất khó cho một người mang dựa trên niềm tin vào sức mạnh vô hạn của tư tưởng để chấp nhận luận điểm về giới hạn của sức mạnh của nó ... Nhiều chuyên gia tin rằng các quá trình hình thức-tính toán, "theo thuyết Aristotle" cơ bản suy nghĩ logic, chỉ là một phần Ý thức con người. Lĩnh vực khác của nó, về cơ bản là “không tính toán”, chịu trách nhiệm cho những biểu hiện như trực giác, hiểu biết sâu sắc và hiểu biết sáng tạo. Và nếu nửa đầu của tâm trí nằm dưới sự hạn chế của Gödel, thì nửa sau không bị giới hạn bởi những giới hạn đó ... Nhà vật lý học Roger Penrose thậm chí còn đi xa hơn. Ông gợi ý về sự tồn tại của một số hiệu ứng lượng tử có tính chất không tính toán, đảm bảo việc thực hiện các hành vi sáng tạo của ý thức ... Đặc biệt, một trong nhiều hệ quả của giả thuyết Penrose có thể là kết luận rằng trí tuệ nhân tạo trên nền tảng của các thiết bị tính toán hiện đại, cho dù sự ra đời của máy tính lượng tử sẽ dẫn đến một bước đột phá lớn trong lĩnh vực công nghệ điện toán. Thực tế là bất kỳ máy tính nào cũng chỉ có thể mô hình hóa ngày càng chính xác công việc của hoạt động "tính toán" hình thức-logic của ý thức con người, nhưng các khả năng "phi tính toán" của trí tuệ thì không thể tiếp cận được với nó.

Một hệ quả quan trọng của định lý Gödel là kết luận rằng người ta không thể suy nghĩ theo hướng cực trị. Luôn luôn bên trong lý thuyết hiện có có một tuyên bố không thể được chứng minh hoặc không được bác bỏ. Hay nói cách khác, đối với một số tuyên bố luôn có một cặp bác bỏ nó.

Kết luận tiếp theo. Thiện và ác chỉ là 2 mặt của cùng một đồng tiền, nếu thiếu nó thì nó không thể tồn tại. Và nó xuất phát từ nguyên lý rằng trong Vũ trụ chỉ có một nguồn gốc của mọi thứ: thiện và ác, yêu và ghét, sống và chết.

Mọi tuyên bố về tính hoàn chỉnh của hệ thống đều là sai. Bạn không thể dựa vào những giáo điều, vì sớm muộn gì chúng cũng sẽ bị bác bỏ.

Theo nghĩa này, các tôn giáo hiện đại đang ở một vị trí quan trọng: các giáo điều của nhà thờ chống lại sự phát triển các ý tưởng của chúng ta về thế giới. Họ cố ép mọi thứ vào khuôn khổ của những khái niệm cứng nhắc. Nhưng điều này dẫn đến thực tế là từ Độc thần giáo, từ một nguồn duy nhất của tất cả quá trình tự nhiên họ chuyển sang tà giáo, nơi có lực lượng của thiện và lực lượng của ác, có một vị thần tốt ở đâu đó rất xa trên thiên đường, và có một ác quỷ (thần ác), người đã đặt chân lên mọi thứ từ lâu. ở trên Trái đất. Cách tiếp cận này dẫn đến sự phân chia tất cả mọi người thành bạn và thù, công bình và tội lỗi, tín đồ và dị giáo, bạn bè và kẻ thù.

Đây là một văn bản nhỏ khác tiết lộ một cách phổ biến bản chất của định lý Gödel:
"Đối với tôi, dường như định lý này mang một ý nghĩa triết học. Chỉ có thể có hai lựa chọn:

a) Lý thuyết không đầy đủ, tức là Về mặt lý thuyết, người ta có thể đặt ra một câu hỏi mà không thể đưa ra câu trả lời khẳng định hoặc phủ định từ các tiên đề / định đề của lý thuyết. Đồng thời, câu trả lời cho tất cả các câu hỏi như vậy có thể được đưa ra trong khuôn khổ của một lý thuyết toàn diện hơn, trong đó câu hỏi cũ sẽ là một trường hợp đặc biệt. Nhưng điều này lý thuyết mới sẽ có "câu hỏi chưa được trả lời" của riêng nó, v.v.

b) Hoàn chỉnh, nhưng mâu thuẫn. Bất kỳ câu hỏi nào cũng có thể được trả lời, nhưng một số câu hỏi có thể được trả lời bằng cả có và không cùng một lúc.

Các lý thuyết khoa học thuộc loại đầu tiên. Chúng nhất quán, nhưng điều đó có nghĩa là chúng không mô tả tất cả mọi thứ. Không thể có "cuối cùng" lý thuyết khoa học. Bất kỳ lý thuyết nào cũng không đầy đủ và không mô tả điều gì đó, ngay cả khi chúng ta chưa biết nó là gì. Người ta chỉ có thể tạo ra nhiều lý thuyết hơn và toàn diện hơn. Đối với cá nhân tôi, đây là một lý do để lạc quan, bởi vì nó có nghĩa là sự tiến bộ của khoa học sẽ không bao giờ dừng lại.

"Thiên Chúa toàn năng" thuộc loại thứ hai. Chúa toàn năng là câu trả lời cho mọi câu hỏi. Và điều này tự động có nghĩa là nó dẫn đến sự phi lý hợp lý. Nghịch lý như "đá nặng" có thể được phát minh theo lô.

Nói chung là, kiến thức khoa học là đúng (nhất quán), nhưng tại bất kỳ thời điểm nào không mô tả tất cả mọi thứ. Đồng thời, không có gì ngăn cản việc đẩy ranh giới của cái đã biết đến vô tận, ngày càng xa hơn và sớm hay muộn thì bất kỳ điều gì chưa biết cũng được biết đến. Tôn giáo tuyên bố với Mô tả đầy đủ thế giới "ngay bây giờ", nhưng nó tự động không chính xác (vô lý). "

Tại một thời điểm, khi tôi mới bắt đầu cuộc sống trưởng thành Tôi đã lập trình. Và có một nguyên tắc như vậy: nếu sửa nhiều chương trình thì phải viết lại chương trình đó. Nguyên tắc này, theo tôi, tương ứng với định lý Godel. Nếu chương trình trở nên phức tạp hơn, nó sẽ trở nên không nhất quán. Và nó sẽ không hoạt động đúng.

Một ví dụ khác từ cuộc sống. Chúng ta đang sống trong thời đại mà các quan chức nói rằng nguyên tắc tồn tại chính phải là luật. Đó là, hệ thống luật pháp. Nhưng ngay khi pháp luật trở nên phức tạp hơn và việc xây dựng quy tắc phát triển mạnh mẽ, các luật bắt đầu mâu thuẫn với nhau. Những gì chúng ta đang thấy bây giờ. Bạn không bao giờ có thể tạo hệ thống pháp lý, mà sẽ quy định tất cả các khía cạnh của cuộc sống. Mặt khác, nó sẽ công bằng cho tất cả mọi người. Bởi vì những hạn chế trong hiểu biết của chúng ta về thế giới sẽ luôn bộc lộ ra ngoài. Và quy luật của con người đến một lúc nào đó sẽ bắt đầu mâu thuẫn với quy luật của vũ trụ. Chúng tôi hiểu nhiều điều bằng trực giác. Cũng bằng trực giác, chúng ta phải đánh giá hành động của người khác. Chỉ cần nhà nước có hiến pháp là đủ. Và dựa vào các điều khoản của hiến pháp này, để điều chỉnh các quan hệ trong xã hội. Nhưng sớm hay muộn, hiến pháp sẽ phải được thay đổi.

SỬ DỤNG là một ví dụ khác về sự sai lầm trong các ý tưởng của chúng tôi về khả năng của con người. Chúng tôi đang cố gắng kiểm tra khả năng tính toán của não bộ trong một kỳ thi. Nhưng khả năng trực quan ở trường đã không còn được phát triển. Nhưng con người không phải là một biorobot. Không thể tạo ra một hệ thống tính điểm có thể tiết lộ tất cả những khả năng vốn có trong một người, trong ý thức, trong tiềm thức và tâm hồn của anh ta.

Gần 100 năm trước, Gödel đã có một bước tiến đáng kinh ngạc trong việc tìm hiểu các quy luật của vũ trụ. Và chúng tôi vẫn chưa thể sử dụng điều này, coi định lý này là chuyên biệt cao bài toán cho một nhóm hẹp gồm những người giải quyết một số chủ đề trừu tượng trong vòng kết nối của riêng họ. Cùng với lý thuyết lượng tử và những lời dạy của Chúa Kitô, định lý Gödel giúp chúng ta thoát khỏi sự giam cầm của những giáo điều sai lầm, để vượt qua cuộc khủng hoảng vẫn còn tồn tại trong thế giới quan của chúng ta. Và thời gian đã hết.

Một trong những định lý đã biết logic toán học, may mắn và không may mắn cùng một lúc. Trong này cô ấy giống như lý thuyết đặc biệt Thuyết tương đối của Einstein. Một mặt, hầu như mọi người đều đã nghe nói gì đó về họ. Mặt khác, theo cách hiểu phổ biến, lý thuyết của Einstein, như bạn đã biết, "nói mọi thứ trên đời đều là tương đối". Và định lý không đầy đủ của Gödel (sau đây gọi là TGN), trong một công thức dân gian gần như tự do, "chứng minh rằng có những điều không thể hiểu được đối với tâm trí con người". Và vì vậy một số cố gắng điều chỉnh nó như một lý lẽ chống lại chủ nghĩa duy vật, trong khi những người khác thì ngược lại, chứng minh với sự trợ giúp của nó rằng không có Chúa. Thật buồn cười không chỉ là cả hai bên không thể đúng cùng một lúc, mà cả bên này lẫn bên kia đều không bận tâm tìm ra thực tế, định lý này nói lên điều gì.

Vậy thì sao? Dưới đây tôi sẽ cố gắng "trên ngón tay" để nói về nó. Tất nhiên, giải trình của tôi sẽ không khắt khe và trực quan, nhưng tôi sẽ yêu cầu các nhà toán học không đánh giá tôi nghiêm khắc. Có thể đối với những người không chuyên về toán học (mà thực ra tôi cũng thuộc nằm lòng) sẽ có điều gì đó mới mẻ và hữu ích trong những gì được kể dưới đây.

Toán học logic quả thực là một môn khoa học khá phức tạp, và quan trọng nhất là không quen thuộc lắm. Nó đòi hỏi các thao tác cẩn thận và nghiêm ngặt, trong đó điều quan trọng là không được nhầm lẫn giữa điều đã thực sự được chứng minh với thực tế là "nó đã rõ ràng". Tuy nhiên, tôi hy vọng rằng để hiểu được “dàn ý chứng minh TGN” sau đây, người đọc chỉ cần có kiến ​​thức về toán học / khoa học máy tính, kỹ năng tư duy logic và thời gian 15-20 phút.

Đơn giản hóa phần nào, TGN khẳng định như vậy là đủ ngôn ngữ khó có những tuyên bố không có cơ sở. Nhưng trong cụm từ này, hầu hết mọi từ đều cần giải thích.

Hãy bắt đầu bằng cách cố gắng tìm ra bằng chứng là gì. Hãy xem một số bài toán trường học trong số học. Ví dụ, hãy để yêu cầu chứng minh tính đúng đắn của công thức không phức tạp sau: "" (Tôi nhắc bạn rằng ký hiệu được đọc là "cho bất kỳ" và được gọi là "định lượng phổ quát"). Nó có thể được chứng minh bằng cách biến đổi giống hệt nhau, chẳng hạn như thế này:

Việc chuyển đổi từ công thức này sang công thức khác xảy ra theo một số các quy tắc đã biết. Chẳng hạn, quá trình chuyển đổi từ công thức thứ 4 sang công thức thứ 5 xảy ra, bởi vì mọi số đều bằng chính nó - đó là tiên đề của số học. Và toàn bộ quy trình chứng minh, do đó, chuyển công thức thành giá trị boolean TRUE. Kết quả có thể là FALSE - nếu chúng ta bác bỏ một số công thức. Trong trường hợp này, chúng tôi sẽ chứng minh sự phủ định của nó. Có thể hình dung một chương trình (và những chương trình như vậy thực sự được viết ra) sẽ chứng minh những mệnh đề như vậy (và phức tạp hơn) mà không cần sự can thiệp của con người.

Hãy nêu điều tương tự một cách chính thức hơn một chút. Giả sử chúng ta có một tập hợp bao gồm các chuỗi ký tự của một số bảng chữ cái và có các quy tắc mà tập hợp con của cái gọi là các câu lệnh- nghĩa là các cụm từ có ý nghĩa về mặt ngữ pháp, mỗi cụm từ đều đúng hoặc sai. Chúng ta có thể nói rằng có một hàm phù hợp với các câu lệnh từ một trong hai giá trị: TRUE hoặc FALSE (nghĩa là ánh xạ chúng tới một tập Boolean gồm hai phần tử).

Hãy gọi một cặp như vậy - một tập hợp các câu lệnh và một hàm từ đến - "ngôn ngữ của tuyên bố". Lưu ý rằng theo nghĩa hàng ngày, khái niệm ngôn ngữ có phần rộng hơn. Ví dụ, cụm từ tiếng Nga "Chà, lại đây!" là không đúng và không sai, nghĩa là, theo quan điểm của lôgic toán học, nó không phải là một phát biểu.

Đối với những gì sau đây, chúng ta cần khái niệm về một thuật toán. Tôi sẽ không đưa ra định nghĩa chính thức của nó ở đây - điều này sẽ dẫn chúng ta sang một bên khá xa. Tôi sẽ giới hạn bản thân trong những việc không chính thức: "thuật toán"- chuỗi hướng dẫn rõ ràng này ("chương trình"), phía sau số giới hạn các bước chuyển đổi dữ liệu đầu vào thành đầu ra. Phần in nghiêng về cơ bản là quan trọng - nếu chương trình bị treo trên một số dữ liệu ban đầu, thì nó không mô tả thuật toán. Để đơn giản và áp dụng cho trường hợp của chúng ta, người đọc có thể coi rằng thuật toán là một chương trình được viết bằng bất kỳ ngôn ngữ lập trình nào mà anh ta biết, đối với bất kỳ dữ liệu đầu vào nào từ một lớp nhất định, được đảm bảo hoàn thành công việc của nó với kết quả Boolean.

Hãy để chúng tôi tự hỏi: có "thuật toán chứng minh" cho mọi hàm không (hay nói ngắn gọn là "suy luận") tương đương với hàm này, tức là, dịch mỗi câu lệnh thành chính xác cùng một giá trị boolean với nó? Ngắn gọn hơn, câu hỏi tương tự có thể được xây dựng như sau: có phải mọi hàm đều nằm trên một tập các mệnh đề tính toán được? Như bạn đã có thể đoán, theo hiệu lực của TGN rằng không, không phải bất kỳ - có những hàm không thể tính toán thuộc loại này. Nói cách khác, không phải mọi phát biểu đúng đều có thể được chứng minh.

Rất có thể câu nói này sẽ gây ra phản đối nội bộ cho bạn. Điều này là do một số trường hợp. Đầu tiên, khi chúng ta được dạy toán học trường học, sau đó đôi khi có ấn tượng sai về sự đồng nhất gần như đầy đủ của các cụm từ "định lý là đúng" và "có thể chứng minh hoặc xác minh định lý". Nhưng nếu bạn nghĩ về nó, nó không rõ ràng chút nào. Một số định lý được chứng minh khá đơn giản (ví dụ, bằng cách liệt kê một số lượng nhỏ các phương án), và một số định lý rất khó. Ví dụ, hãy xem xét Định lý cuối cùng nổi tiếng của Fermat:

bằng chứng của nó đã được tìm thấy chỉ ba thế kỷ rưỡi sau công thức đầu tiên (và nó còn lâu mới có cơ sở). Cần phải phân biệt giữa sự thật của một tuyên bố và khả năng chứng minh của nó. Nó không theo bất cứ nơi nào mà không có tuyên bố đúng, nhưng không thể chứng minh (và không hoàn toàn có thể kiểm chứng).

Lập luận trực quan thứ hai chống lại TGN tinh vi hơn. Giả sử chúng ta có một số phát biểu không thể chứng minh được (trong khuôn khổ của suy luận này). Điều gì ngăn cản chúng ta chấp nhận nó như một tiên đề mới? Do đó, chúng tôi sẽ hơi phức tạp hóa hệ thống chứng minh của mình, nhưng điều này không quá khủng khiếp. Lập luận này sẽ hoàn toàn đúng nếu có một số hữu hạn mệnh đề không thể chứng minh được. Trong thực tế, điều sau có thể xảy ra - sau khi xác định một tiên đề mới, bạn sẽ vấp phải một phát biểu mới không thể chứng minh được. Hãy coi nó như một tiên đề khác - bạn sẽ vấp phải điều thứ ba. Và như vậy quảng cáo infinitum. Họ nói rằng Actuctica sẽ ở lại chưa hoàn thiện. Chúng tôi cũng có thể thực hiện các biện pháp mạnh mẽ để thuật toán chứng minh kết thúc sau một số bước hữu hạn với một số kết quả cho bất kỳ câu lệnh nào của ngôn ngữ. Nhưng đồng thời, anh ta sẽ bắt đầu nói dối - dẫn đến sự thật cho những tuyên bố không chính xác, hoặc dối trá - đối với những người trung thành. Trong những trường hợp như vậy, người ta nói rằng suy luận mâu thuẫn. Vì vậy, một công thức nữa của TGN nghe có vẻ như thế này: “Có những ngôn ngữ mệnh đề mà phép suy diễn nhất quán hoàn toàn là không thể” - do đó tên của định lý.

Đôi khi được gọi là "Định lý Gödel" là tuyên bố rằng bất kỳ lý thuyết nào cũng chứa đựng những vấn đề không thể giải quyết được trong khuôn khổ của chính lý thuyết đó và đòi hỏi sự tổng quát hóa của nó. Theo một nghĩa nào đó, điều này đúng, mặc dù công thức như vậy che khuất vấn đề hơn là làm rõ nó.

Tôi cũng lưu ý rằng nếu chúng ta đang nói về các chức năng thông thường hiển thị bộ số thực vào nó, thì "tính không thể tính toán được" của hàm sẽ không làm bất kỳ ai ngạc nhiên (chỉ cần đừng nhầm lẫn giữa "hàm tính toán được" và "số có thể tính toán" - đây là những thứ khác nhau). Bất kỳ đứa trẻ nào cũng biết rằng, trong trường hợp của một hàm, bạn phải rất may mắn với lập luận để quá trình tính toán biểu diễn thập phân chính xác của giá trị của hàm này kết thúc trong một số bước hữu hạn. Và rất có thể bạn sẽ tính toán nó bằng cách sử dụng một chuỗi vô hạn và phép tính này sẽ không bao giờ dẫn đến kết quả chính xác, mặc dù nó có thể đến gần nó như bạn muốn - đơn giản vì giá trị của sin của hầu hết các đối số là không hợp lý. TGN chỉ đơn giản cho chúng ta biết rằng ngay cả trong số các hàm có đối số là chuỗi và có giá trị bằng 0 hoặc một, các hàm không tính toán được, mặc dù được sắp xếp theo một cách hoàn toàn khác, cũng tồn tại.

Đối với những gì sau đây, chúng tôi mô tả ngôn ngữ số học chính thức". Hãy xem xét một lớp chuỗi văn bản có độ dài hữu hạn, bao gồm các chữ số Ả Rập, các biến (chữ cái Bảng chữ cái Latinh), lấy giá trị tự nhiên, dấu cách, ký tự các phép tính toán học, bình đẳng và bất bình đẳng, định lượng (“tồn tại”) và (“cho bất kỳ”) và, có lẽ, một số ký hiệu khác (số lượng và thành phần chính xác của chúng không quan trọng đối với chúng tôi). Rõ ràng là không phải tất cả các dòng như vậy đều có nghĩa (ví dụ: "" là vô nghĩa). Tập hợp con của các biểu thức có nghĩa từ lớp này (nghĩa là các chuỗi đúng hoặc sai về mặt số học thông thường) sẽ là tập các câu lệnh của chúng ta.

Ví dụ về các câu lệnh số học chính thức:

vân vân. Bây giờ chúng ta hãy gọi một "công thức với một tham số tự do" (FSP) là một chuỗi sẽ trở thành một câu lệnh nếu một số tự nhiên được thay thế vào nó dưới dạng tham số này. Ví dụ về FSP (có tham số):

vân vân. Nói cách khác, FSP tương đương với các hàm của một đối số tự nhiên có giá trị Boolean.

Ký hiệu tập hợp tất cả các FSP bằng chữ cái. Rõ ràng là nó có thể được sắp xếp (ví dụ, đầu tiên chúng tôi viết ra các công thức một chữ cái được sắp xếp theo thứ tự bảng chữ cái, sau đó là các công thức hai chữ cái, v.v. Do đó, bất kỳ FSP nào tương ứng với số của nó trong danh sách được sắp xếp và chúng tôi sẽ ký hiệu nó.

Bây giờ chúng ta hãy chuyển sang một bản phác thảo của chứng minh TGN trong công thức sau:

• Đối với ngôn ngữ mệnh đề của số học chính thức, không có phép suy diễn nhất quán hoàn toàn.

Chúng tôi sẽ chứng minh bằng mâu thuẫn.

Vì vậy, hãy giả sử rằng một suy luận như vậy tồn tại. Hãy mô tả thuật toán bổ trợ sau đây gán giá trị boolean cho một số tự nhiên như sau:

Nói một cách đơn giản, thuật toán cho kết quả là giá trị TRUE nếu và chỉ khi kết quả của việc thay thế vào FSP số của chính nó trong danh sách của chúng ta cho một tuyên bố sai.

Ở đây chúng ta đến nơi duy nhất mà tôi sẽ yêu cầu người đọc giữ lời cho nó.

Rõ ràng, theo giả định trên, bất kỳ FSP nào từ đều có thể được liên kết với một thuật toán chứa một số tự nhiên ở đầu vào và giá trị Boolean ở đầu ra. Ít rõ ràng hơn là ngược lại:

Việc chứng minh bổ đề này ít nhất sẽ yêu cầu một định nghĩa chính thức, không phải trực quan, về khái niệm thuật toán. Tuy nhiên, nếu bạn nghĩ về nó một chút, nó là khá chính đáng. Thật vậy, các thuật toán được viết bằng các ngôn ngữ thuật toán, trong số đó có những thuật toán kỳ lạ như, ví dụ, Brainfuck, bao gồm tám từ một ký tự, trong đó, bất kỳ thuật toán nào cũng có thể được thực hiện. Sẽ là lạ nếu ngôn ngữ phong phú hơn của các công thức số học chính thức mà chúng tôi đã mô tả lại trở nên kém hơn - mặc dù, không nghi ngờ gì nữa, nó không phù hợp lắm với lập trình thông thường.

Sau khi vượt qua nơi trơn trượt này, chúng tôi nhanh chóng đi đến cuối cùng.

Vì vậy, chúng tôi đã mô tả thuật toán ở trên. Theo bổ đề mà tôi yêu cầu bạn tin rằng, tồn tại một FSP tương đương. Nó có một số con số trong danh sách - giả sử. Chúng ta hãy tự hỏi mình, vấn đề là gì? Hãy để nó là SỰ THẬT. Sau đó, theo cấu trúc của thuật toán (và do đó hàm tương đương với nó), điều này có nghĩa là kết quả của việc thay một số vào hàm là FALSE. Điều ngược lại được kiểm tra theo cùng một cách: từ FALSE đến TRUE. Chúng tôi đã đi đến một mâu thuẫn, có nghĩa là giả định ban đầu là sai. Do đó, đối với số học chính thức, không có phép suy diễn nhất quán hoàn toàn. Q.E.D.

Ở đây, thật thích hợp để nhớ lại Epimenides (xem bức chân dung trong tiêu đề), như bạn đã biết, đã tuyên bố rằng tất cả người Cretan đều là kẻ nói dối, bản thân anh ta là người Cretan. Trong một công thức ngắn gọn hơn, tuyên bố của anh ta (được gọi là "nghịch lý nói dối") có thể được xây dựng thành: "Tôi đang nói dối." Đó chính xác là một tuyên bố như vậy, chính nó đã tuyên bố sự giả dối của nó, mà chúng tôi đã sử dụng để làm bằng chứng.

Kết luận, tôi muốn lưu ý rằng TGN không tuyên bố bất cứ điều gì đặc biệt đáng ngạc nhiên. Rốt cuộc, mọi người từ lâu đã quen với thực tế là không phải tất cả các số đều có thể được biểu diễn dưới dạng tỉ số của hai số nguyên (hãy nhớ rằng, câu nói này đã có một bằng chứng rất thanh lịch là hơn hai nghìn năm tuổi?). Và các căn của đa thức với hệ số hữu tỉ cũng không phải là tất cả các số. Và bây giờ hóa ra rằng không phải tất cả các hàm của một đối số tự nhiên đều có thể tính toán được.

Bản phác thảo của bằng chứng được đưa ra là dành cho số học chính thức, nhưng không khó để thấy rằng THN cũng áp dụng cho nhiều ngôn ngữ mệnh đề khác. Tất nhiên, không phải tất cả các ngôn ngữ đều như vậy. Ví dụ: hãy định nghĩa một ngôn ngữ như sau:

• "Bất kỳ cụm từ nào người Trung Quốc là một câu nói đúng nếu nó có trong cuốn sách trích dẫn của đồng chí Mao Tạ Đình Tùng, và là không chính xác nếu nó không được chứa trong đó.

Sau đó, thuật toán chứng minh hoàn chỉnh và nhất quán tương ứng (nó có thể được gọi là "suy luận giáo điều") trông giống như sau:

• “Lật lại cuốn sách trích dẫn của đồng chí Mao Tse Tung cho đến khi bạn tìm thấy câu nói mà bạn đang tìm kiếm. Nếu nó được tìm thấy, thì nó là sự thật, và nếu cuốn sách trích dẫn đã qua mà không tìm thấy câu lệnh, thì nó là sai.

Ở đây chúng tôi được cứu bởi thực tế rằng bất kỳ trích dẫn nào rõ ràng là hữu hạn, vì vậy quá trình "chứng minh" chắc chắn sẽ kết thúc. Vì vậy, TGN không thể áp dụng cho ngôn ngữ của những phát biểu giáo điều. Nhưng chúng ta đang nói về những ngôn ngữ phức tạp, phải không?

Thẻ: Thêm thẻ

09sen

Bất kỳ hệ tiên đề toán học nào, bắt đầu từ một mức độ phức tạp nhất định, đều không nhất quán hoặc không đầy đủ về mặt nội tại.

Năm 1900, Hội nghị các nhà Toán học Thế giới được tổ chức tại Paris, nơi David Gilbert(David Hilbert, 1862–1943) đã nêu ra dưới dạng luận văn 23 quan trọng nhất, theo ý kiến ​​của ông, các nhiệm vụ mà các nhà lý thuyết của thế kỷ 20 sắp tới phải giải quyết. Thứ hai trong danh sách của anh ấy là một trong những vấn đề đơn giản dường như hiển nhiên cho đến khi bạn tìm hiểu sâu hơn một chút. Theo thuật ngữ hiện đại, câu hỏi đặt ra là: liệu tự thân toán học có đủ không? Nhiệm vụ thứ hai của Hilbert được rút gọn thành sự cần thiết phải chứng minh một cách chặt chẽ rằng hệ thống tiên đề - những phát biểu cơ bản được lấy trong toán học làm cơ sở mà không cần chứng minh - là hoàn hảo và đầy đủ, tức là nó cho phép mô tả toán học về mọi thứ tồn tại. Cần phải chứng minh rằng có thể thiết lập một hệ thống tiên đề như vậy, thứ nhất, chúng sẽ nhất quán lẫn nhau, và thứ hai, người ta có thể rút ra kết luận từ chúng về sự thật hay sai của bất kỳ phát biểu nào.

Hãy lấy một ví dụ từ hình học trường học. Trong phép đo phẳng tiêu chuẩn Euclide (hình học trên một mặt phẳng), có thể chứng minh vô điều kiện rằng phát biểu "tổng các góc của một tam giác là 180 °" là đúng và phát biểu "tổng các góc của một tam giác là 137 ° " là sai. Về cơ bản, trong hình học Euclid, bất kỳ phát biểu nào là sai hoặc đúng, và câu thứ ba không được đưa ra. Và vào đầu thế kỷ 20, các nhà toán học đã ngây thơ tin rằng tình huống tương tự cần được quan sát trong bất kỳ hệ thống nhất quán về mặt logic nào.

Và sau đó vào năm 1931, một số nhà toán học đeo kính đeo mắt người Vienna Kurt Gödel- đã chụp và xuất bản một bài báo ngắn đơn giản là lật ngược toàn bộ thế giới của cái gọi là "logic toán học". Sau những phần mở đầu lý thuyết và toán học dài và phức tạp, ông thực sự đã thiết lập được những điều sau đây. Hãy lấy bất kỳ phát biểu nào như: "Giả định số 247 là không thể chứng minh được về mặt logic trong hệ tiên đề này" và gọi nó là "phát biểu A". Vì vậy, Gödel chỉ đơn giản là chứng minh tính chất tuyệt vời sau đây của bất kỳ hệ tiên đề nào:

"Nếu một tuyên bố A có thể được chứng minh, thì một tuyên bố không phải A có thể được chứng minh."

Nói cách khác, nếu có thể chứng minh tính hợp lệ của tuyên bố “Giả định 247 là không thể dự phòng”, thì cũng có thể chứng minh tính hợp lệ của tuyên bố “Giả định 247 là có thể chứng minh được”. Tức là, quay trở lại công thức của bài toán Hilbert thứ hai, nếu hệ tiên đề đầy đủ (tức là bất kỳ phát biểu nào trong đó cũng có thể chứng minh được) thì nó không nhất quán.

Cách duy nhất để thoát khỏi tình huống này là chấp nhận một hệ thống tiên đề không hoàn chỉnh. Đó là, chúng ta phải đối mặt với một thực tế rằng trong bối cảnh của bất kỳ hệ thống logic nào, chúng ta vẫn sẽ có những phát biểu “loại A” rõ ràng là đúng hoặc sai - và chúng ta chỉ có thể đánh giá sự thật của chúng bên ngoài khuôn khổ của tiên đề mà chúng ta có. con nuôi. Nếu không có những phát biểu như vậy, thì tiên đề của chúng ta là mâu thuẫn, và trong khuôn khổ của nó chắc chắn sẽ có những công thức vừa có thể chứng minh vừa có thể bác bỏ.

Vì vậy, công thức của định lý đầu tiên, hoặc định lý yếu, không đầy đủ của Gödel là: "Bất kỳ hệ thống tiên đề chính thức nào đều chứa các giả định chưa được giải đáp". Nhưng Gödel không dừng lại ở đó, xây dựng và chứng minh định lý thứ hai hoặc định lý không đầy đủ mạnh mẽ của Gödel: “Tính hoàn chỉnh lôgic (hoặc tính không đầy đủ) của bất kỳ hệ tiên đề nào không thể được chứng minh trong khuôn khổ của hệ thống này. Để chứng minh hoặc bác bỏ nó, cần có thêm các tiên đề (tăng cường hệ thống).

Sẽ an toàn hơn nếu nghĩ rằng các định lý của Godel là trừu tượng và không liên quan đến chúng ta, mà chỉ là các lĩnh vực logic toán học cao siêu, nhưng thực tế hóa ra chúng có liên quan trực tiếp đến cấu trúc của bộ não con người. Nhà toán học và vật lý người Anh Roger Penrose (sinh năm 1931) đã chỉ ra rằng Định lý Gödel có thể được sử dụng để chứng minh sự tồn tại của những khác biệt cơ bản giữa não người và máy tính. Quan điểm của lý luận của anh ấy rất đơn giản. Máy tính hoạt động một cách logic chặt chẽ và không thể xác định được câu A là đúng hay sai nếu nó vượt ra ngoài phạm vi của tiên đề, và những câu như vậy, theo định lý Gödel, chắc chắn sẽ tồn tại. Một người, đối mặt với một tuyên bố A không thể chứng minh được về mặt logic và không thể bác bỏ, luôn có thể xác định được sự thật hay giả dối của nó - dựa trên kinh nghiệm hàng ngày. Ít nhất ở điểm này, bộ não của con người vượt trội hơn một chiếc máy tính bị trói buộc bởi các mạch logic thuần túy. Bộ não của con người có thể hiểu được toàn bộ chiều sâu của sự thật chứa đựng trong các định lý của Gödel, nhưng một chiếc máy tính thì không bao giờ có thể hiểu được. Do đó, bộ não của con người là bất cứ thứ gì ngoại trừ một máy tính. Anh ấy có thể đưa ra quyết định và bài kiểm tra Turing sẽ vượt qua.

về chủ đề: "LÝ THUYẾT CỦA GODEL"

Kurt Gödel

Kurt Gödel là chuyên gia giỏi nhất trong logic toán học- sinh ngày 28 tháng 4 năm 1906 tại Brunn (nay là Brno, Cộng hòa Séc). Ông tốt nghiệp Đại học Vienna, nơi ông bảo vệ luận án tiến sĩ, là phó giáo sư năm 1933–1938. Sau vụ Anschluss, ông di cư đến Hoa Kỳ. Từ năm 1940 đến năm 1963 Gödel làm việc tại Viện Princeton những nghiên cứu cao hơn. Gödel, Tiến sĩ Danh dự từ Đại học Yale và Harvard, Nghiên cứu sinh Học viện quốc gia Khoa học của Hoa Kỳ và Hiệp hội Triết học Hoa Kỳ.

Năm 1951, Kurt Gödel đã được trao giải thưởng khoa học cao nhất của Hoa Kỳ, Giải thưởng Einstein. Trong một bài báo dành riêng cho sự kiện này, một trong những nhà toán học vĩ đại nhất của thời đại chúng ta, John von Neumann, đã viết: “Sự đóng góp của Kurt Gödel cho logic hiện đại thực sự rất hoành tráng. Đây không chỉ là một tượng đài. Đây là một dấu mốc tách biệt hai thời đại ... Có thể nói không ngoa rằng công trình của Gödel đã thay đổi căn bản chính chủ đề logic với tư cách là một khoa học.

Thật vậy, ngay cả một danh sách khô khan về những thành tựu của Godel trong logic toán học cũng cho thấy tác giả của chúng về cơ bản đã đặt nền móng cho toàn bộ phần của khoa học này: lý thuyết về mô hình (1930; cái gọi là định lý về tính hoàn chỉnh của phép tính vị từ hẹp, cho thấy, nói một cách đại khái, sự đầy đủ của các phương tiện của "logic hình thức" để chứng minh tất cả các câu đúng được diễn đạt bằng ngôn ngữ của nó), logic xây dựng (1932–1933; dẫn đến khả năng giảm một số loại câu của logic cổ điển thành các đối tác trực giác của chúng, mà đặt nền tảng cho việc sử dụng một cách có hệ thống các "hoạt động ngâm" cho phép giảm thiểu các hệ thống logic nhau), số học chính thức (1932–1933; kết quả về khả năng giảm số học cổ điển thành số học trực quan, cho thấy theo một nghĩa nào đó tính nhất quán của phương pháp thứ nhất so với phương pháp thứ hai), lý thuyết về thuật toán và hàm đệ quy (1934; định nghĩa khái niệm về một hàm đệ quy tổng quát, đã chơi Vai trò quyết định trong việc thiết lập tính không thể giải được theo thuật toán của chuỗi vấn đề quan trọng một mặt toán học. Và trong việc thực hiện các vấn đề logic và toán học trên máy tính điện tử - mặt khác), lý thuyết tập hợp tiên đề (1938; bằng chứng về tính nhất quán tương đối của tiên đề lựa chọn và giả thuyết liên tục của Cantor từ các tiên đề của lý thuyết tập hợp, đánh dấu sự khởi đầu của bộ truyện kết quả chính về tính nhất quán tương đối và tính độc lập của các nguyên tắc lý thuyết tập hợp).

Định lý về tính không đầy đủ của Godel

Giới thiệu

Năm 1931, tại một trong những tạp chí khoa học một bài báo tương đối ngắn xuất hiện với tiêu đề khá khó khăn "Về các mệnh đề chính thức không thể quyết định của các nguyên tắc toán học và các hệ thống liên quan". Tác giả của nó là một nhà toán học 25 tuổi từ Đại học Vienna, Kurt Gödel, người sau này làm việc tại Viện Nghiên cứu Cao cấp Princeton. Công việc này đã đóng một vai trò quyết định trong lịch sử của logic và toán học. Trong quyết định đại học Harvard trao bằng tiến sĩ danh dự cho Gödel (1952), bà được mô tả là một trong những thành tựu lớn nhất logic hiện đại.

Tuy nhiên, tại thời điểm xuất bản, không có tên tác phẩm của Gödel. Cả nội dung của nó đều không nói lên điều gì đối với hầu hết các nhà toán học. Được đề cập trong tiêu đề của nó, Principia Mathematica là luận thuyết ba tập đồ sộ của Alfred North Whitehead và Bertrand Russell về logic toán học và nền tảng của toán học; quen thuộc với luận thuyết không có nghĩa là Điều kiện cần thiết vì công việc thành công trong hầu hết các nhánh của toán học. Mối quan tâm đến các vấn đề được giải quyết trong công trình của Gödel luôn là mối quan tâm của một nhóm rất nhỏ các nhà khoa học. Đồng thời, các lập luận do Gödel đưa ra trong các chứng minh của ông ấy rất khác thường so với thời của họ. Để hiểu đầy đủ về chúng đòi hỏi một kiến ​​thức chuyên biệt về chủ đề này và sự quen thuộc với tài liệu dành cho những vấn đề rất cụ thể này.

Định lý về tính không đầy đủ đầu tiên

Định lý về tính không đầy đủ đầu tiên của Gödel dường như là kết quả quan trọng nhất trong logic toán học. Nó giống như thế này:

Đối với một lý thuyết tính toán và hình thức nhất quán tùy ý, trong đó các mệnh đề số học cơ bản có thể được chứng minh, một mệnh đề số học đúng có thể được xây dựng mà chân lý không thể được chứng minh trong khuôn khổ của lý thuyết. Nói cách khác, bất kỳ lý thuyết hoàn toàn hữu ích nào đủ để biểu thị số học đều không thể vừa nhất quán vừa hoàn chỉnh.

Ở đây từ "lý thuyết" có nghĩa là " tập hợp vô hạn»Phát biểu, một số trong số đó được cho là đúng mà không cần chứng minh (những phát biểu như vậy được gọi là tiên đề), trong khi những phát biểu khác (định lý) có thể được suy ra từ tiên đề, và do đó được giả định (chứng minh) là đúng. Cụm từ "có thể chứng minh trong lý thuyết" có nghĩa là "có thể suy ra từ các tiên đề và nguyên thủy của lý thuyết (các ký hiệu không đổi của bảng chữ cái) bằng cách sử dụng logic tiêu chuẩn (bậc nhất)." Một lý thuyết là nhất quán (nhất quán) nếu không thể chứng minh được một tuyên bố mâu thuẫn trong đó. Cụm từ "có thể được xây dựng" có nghĩa là có một số thủ tục cơ học (thuật toán) có thể xây dựng một câu lệnh dựa trên tiên đề, nguyên hàm và logic bậc nhất. "Số học cơ bản" là sự hiện diện của các phép toán cộng và nhân trên các số tự nhiên. Mệnh đề đúng nhưng không thể chứng minh được thường được gọi cho một lý thuyết đã cho là "dãy Gödel", nhưng có vô số mệnh đề khác trong lý thuyết có cùng tính chất là không thể chứng minh được trong lý thuyết.

Giả định rằng lý thuyết có thể tính toán được có nghĩa là về nguyên tắc có thể triển khai một thuật toán máy tính ( chương trình máy tính) mà (nếu được phép tính toán trong thời gian dài tùy ý, lên đến vô hạn) tính toán một danh sách tất cả các định lý của lý thuyết. Trên thực tế, chỉ cần tính danh sách các tiên đề là đủ và tất cả các định lý có thể được suy ra một cách hiệu quả từ danh sách đó.

Định lý về tính không đầy đủ đầu tiên được đặt tên là "Định lý VI" trong bài báo năm 1931 của Gödel. Về các mệnh đề chính thức không thể quyết định trong Principia Mathematica và các hệ thống liên quan I. Trong bản ghi âm gốc của Gödel, nó có vẻ như thế này:

“Kết luận chung về sự tồn tại của các mệnh đề không thể quyết định là:

Định lý VI .

Với mọi lớp đệ quy ω-nhất quán k CÔNG THỨC có đệ quy DẤU HIỆU r như vậy mà không (v Gen r), cũng không ¬( v Gen r)không thuộc về Flg (k)(v ở đâu BIẾN ĐỔI MIỄN PHÍ r ) ».

Chỉ định Flgđến từ anh ta. Folgerungsmenge- tập hợp các trình tự, Genđến từ anh ta. sự khái quát- sự khái quát.

Nói một cách đại khái, tuyên bố của Gödel G khẳng định: "sự thật G không thể được chứng minh. " Nếu G có thể được chứng minh bên trong lý thuyết, khi đó lý thuyết sẽ chứa một định lý mâu thuẫn với chính nó, và do đó lý thuyết sẽ không nhất quán. Nhưng nếu G không thể chứng minh được, sau đó nó là đúng, và do đó lý thuyết là không đầy đủ (tuyên bố G không được suy luận trong đó).

Lời giải thích này là thông thường tiếng mẹ đẻ, và do đó không hoàn toàn khắt khe về mặt toán học. Để cung cấp một bằng chứng chặt chẽ, Gödel đã đánh số các tuyên bố với số tự nhiên. Trong trường hợp này, lý thuyết mô tả các con số cũng thuộc về tập hợp các mệnh đề. Các câu hỏi về khả năng cung cấp của các mệnh đề có thể được trình bày trong trường hợp này dưới dạng câu hỏi về tính chất của số tự nhiên phải tính được nếu lý thuyết đầy đủ. Về những thuật ngữ này, tuyên bố của Gödel nói rằng không có con số nào với một số thuộc tính xác định. Một con số với tính chất này sẽ là bằng chứng cho sự mâu thuẫn của lý thuyết. Nếu tồn tại một con số như vậy thì lý thuyết là không phù hợp, đi ngược lại với giả thiết ban đầu. Vì vậy, giả sử rằng lý thuyết là nhất quán (như tiền đề của định lý cho thấy), hóa ra không có con số như vậy, và phát biểu của Gödel là đúng, nhưng điều này không thể được chứng minh trong khuôn khổ của lý thuyết (do đó lý thuyết là không đầy đủ ). Một lưu ý quan trọng về khái niệm là người ta phải giả định rằng một lý thuyết nhất quán để tuyên bố phát biểu của Gödel là đúng.

Định lý về tính không đầy đủ thứ hai của Gödel

Định lý về tính không đầy đủ thứ hai của Gödel như sau:

Đối với bất kỳ lý thuyết T nào có thể liệt kê một cách đệ quy chính thức (nghĩa là, được tạo ra một cách hiệu quả), bao gồm các câu lệnh chân lý số học cơ bản và một số câu lệnh xác thực chính thức, lý thuyết này T bao gồm một tuyên bố về tính nhất quán của nó nếu và chỉ khi lý thuyết T là không nhất quán.

Nói cách khác, sự nhất quán là đủ lý thuyết phong phú không thể được chứng minh bằng lý thuyết này. Tuy nhiên, nó có thể hóa ra rằng tính nhất quán của một lý thuyết cụ thể có thể được thiết lập bằng một lý thuyết hình thức khác, mạnh mẽ hơn. Nhưng sau đó câu hỏi đặt ra về tính nhất quán của lý thuyết thứ hai này, v.v.

Nhiều người đã cố gắng sử dụng định lý này để chứng minh rằng hoạt động thông minh không thể bị giảm xuống các phép tính. Ví dụ, vào năm 1961, nhà logic học nổi tiếng John Lucas đã đưa ra một chương trình tương tự. Lý luận của anh ta hóa ra khá dễ bị sai sót - tuy nhiên, anh ta đặt ra nhiệm vụ rộng hơn. Roger Penrose có một cách tiếp cận hơi khác một chút, được trình bày trong cuốn sách hoàn toàn, "từ đầu".

Thảo luận

Hệ quả của các định lý ảnh hưởng đến triết học toán học, đặc biệt là những định lý sử dụng Logic chính thứcđể xác định các nguyên tắc của họ. Người ta có thể diễn đạt lại định lý về tính không đầy đủ đầu tiên như sau: không thể tìm thấy một hệ thống tiên đề toàn diện có thể chứng minh tất cả các sự thật toán học, và không phải là một lời nói dối". Mặt khác, từ quan điểm của hình thức chặt chẽ, sự cải tổ này không có nhiều ý nghĩa, vì nó giả định các khái niệm "đúng" và "sai" được định nghĩa theo nghĩa tuyệt đối, thay vì theo nghĩa tương đối cho mỗi. hệ thống cụ thể.