Ý tưởng của chứng minh là xây dựng một biểu thức cho biết nó
sự không thể chứng minh được của chính mình. Việc xây dựng này có thể được thực hiện trong ba giai đoạn:
Giai đoạn đầu tiên là thiết lập sự tương ứng giữa số học hình thức và một tập hợp các số nguyên (Goedelization);
Giai đoạn thứ hai là xây dựng một số tính chất đặc biệt mà người ta chưa biết liệu nó có phải là một định lý của số học hình thức hay không;
Giai đoạn thứ ba là thay thế x của một số nguyên nhất định liên kết với chính nó, tức là thay thế tất cả bằng các số này
Giai đoạn đầu tiên. Gedelization của số học hình thức
Số học chính thức có thể được số học hóa (tức là Godelized) như sau: mỗi định lý của nó gắn liền với một số nhất định. Tuy nhiên, vì mọi số cũng là một định lý, nên mọi định lý, một mặt, có thể được coi là một định lý của số học hình thức, mặt khác, là một định lý trên tập hợp các định lý của số học hình thức, tức là, như một metatheorem tương ứng với việc chứng minh một định lý nào đó.
Vì vậy, chúng ta có thể kết luận rằng hệ thống số học hình thức cũng chứa đựng siêu hệ thống của chính nó.
Bây giờ chúng tôi sẽ trình bày kết quả thu được một cách cụ thể và chi tiết hơn.
Đầu tiên, chúng ta có thể liên kết với mỗi ký hiệu và số học hình thức một ký hiệu mã đặc biệt, được gọi là trong trường hợp này số Godel
Thứ hai, chúng tôi liên kết từng chuỗi ký hiệu với cùng một số Gödel bằng cách sử dụng một số hàm thành phần. Đặt vị trí biểu thị chuỗi ký hiệu hình thành.
Thứ ba (và điều này rất cần thiết), mỗi chứng minh của một chuỗi tiên đề và quy tắc thay thế (hoặc quy tắc thay thế) được liên kết với một số biểu thị chuỗi định lý được sử dụng trong chứng minh.
Do đó, mọi phép chứng minh trong số học hình thức đều tương ứng với một số nhất định - số Gödel của nó Mọi suy luận trong số học hình thức đều được chuyển thành các phép tính trên một tập hợp. số tự nhiên.
Vì vậy, thay vì thao tác với các ký hiệu, định lý và chứng minh, bạn có thể sử dụng
phép tính trên tập hợp số nguyên. Ví dụ, bất kỳ biểu thức nào như sau: "có thể chứng minh được bằng số học hình thức" giờ đây tương ứng với một số nhất định, mà chúng ta sẽ ký hiệu là
Hãy để chúng tôi xây dựng vị trí sau đây.
Siêu số học hình thức được chứa trong tập hợp các số tự nhiên và chính tập hợp đó được chứa trong cách diễn giải số học hình thức.
Tình huống này với số học hình thức gợi nhớ đến tình huống với ngôn ngữ tự nhiên: xét cho cùng, không có gì ngăn cản chúng ta sử dụng nó để hình thành các khái niệm và quy tắc cơ bản trong đó.
Việc lựa chọn hàm đúng cho phép chuyển đổi rõ ràng từ A sang, tức là gán hai số khác nhau cho hai số bằng chứng khác nhau. Ví dụ, người ta có thể chọn các số Gödel theo cách sao cho mỗi ký hiệu của bảng chữ cái số học hình thức tương ứng với số nguyên tố của chính nó, chẳng hạn như được minh họa trong Bảng. 3.2.
Bảng 3.2
Mỗi công thức (bao gồm các ký tự thay đổi từ 1 đến lần lượt được mã hóa bởi một chuỗi bao gồm ký tự đầu tiên số nguyên tố, tức là số
số nguyên tố ở đâu
Ngược lại, cách chứng minh, tức là dãy công thức sẽ được mã hóa theo cách tương tự với số
Và ngược lại, nhờ phương pháp xây dựng số này, có thể bắt đầu từ một số nhất định bằng cách phân tách nó thành thừa số nguyên tố(do tính duy nhất của việc phân tích các số tự nhiên thành tích lũy thừa của các số nguyên tố) trả về số mũ, tức là các ký hiệu nguyên thủy của số học hình thức theo hai bước. Tất nhiên, đây chủ yếu chỉ là lý thuyết vì số lượng nhanh chóng trở nên quá lớn.
để chúng có thể bị thao túng. Tuy nhiên, cần lưu ý rằng khả năng cơ bản của hoạt động này là cần thiết.
Ví dụ. Cho một số T, tương ứng với một số chứng minh và biểu diễn tích của các số nguyên tố:
Việc khai triển này có nghĩa là việc chứng minh định lý bao gồm hai giai đoạn: một giai đoạn tương ứng với số 1981027125 253, và giai đoạn thứ hai tương ứng với số 1981027125 211. Phân tích từng số này thành thừa số nguyên tố, chúng ta có được
Từ bảng mã hóa bảng chữ cái của số học hình thức (Bảng 3.2), chúng ta thấy rằng số Gödel của chúng ta cho hai số này
chứng minh sau đây sẽ tương ứng:
Từ công thức theo công thức
Do đó, trong siêu số học, giá trị của số ban đầu thu được từ số học hình thức.
Giai đoạn thứ hai. Bổ đề Godel
Mỗi số T đi kèm với một chứng minh tương ứng với một định lý có thể chứng minh được bằng số học hình thức. Số học hình thức “Goedelized” được gọi là số học hình thức số học hóa. Vì mọi tiên đề và mọi quy tắc của số học hình thức số học đều tương ứng với một số phép tính số học, sau đó bằng cách sử dụng một thử nghiệm có hệ thống, có thể xác định liệu số đã cho T chứng minh một định lý nào đó Các số T trong trường hợp này tạo thành một cặp số liên hợp. Biểu thức và là liên hợp” Có thể trình bày trong chính số học hình thức số học. Điều này có nghĩa là có một số Gödel thể hiện tuyên bố này bằng kỹ thuật số.
Chúng ta đã đạt tới điểm tới hạn của chứng minh của Gödel. Giả sử A là một biểu thức số học hình thức được số học hóa có chứa một số biến tự do. Thay vào đó, bạn có thể thay thế một số thuật ngữ. Đặc biệt, bạn có thể thay thế biểu thức A bằng chính biểu thức A. Trong trường hợp này, biểu thức số A thực hiện đồng thời hai chức năng. nhiều vai trò khác nhau(xem cách xây dựng ở trên
Cantor và Richard): cùng lúc biểu hiện đúngđể thay thế và thuật ngữ kết quả. Chúng ta sẽ biểu thị sự thay thế đặc biệt này là Vì vậy, công thức có nghĩa là số đó là số Gödel thu được bằng cách thực hiện phép thay thế - cho biểu thức A:
Sau đó Gödel xây dựng một biểu thức (không biết đó là định lý hay phi định lý) để đưa vào đó sự thay thế này. Biểu thức trông như thế này:
Giai đoạn thứ ba. Thay người cuối cùng
Trong số học hình thức số học, biểu thức này được biểu diễn dưới dạng số. Gọi E là số Gödel của nó. Vì biểu thức chứa một biến tự do nên chúng ta có quyền thực hiện phép thay thế - thay thế số E và biểu thị - phép thay thế E:
Chúng ta biểu thị biểu thức thứ hai này bằng a và số Gödel của nó là E. Chúng ta hãy giải thích biểu thức e.
Giải thích đầu tiên. Không có cặp nào như vậy mà các điều sau đây đồng thời đúng: một mặt, T là số chứng minh số học của định lý được số học bởi chính nó, mặt khác, sẽ có sự thay thế. cùng một phép biến đổi như những biến đổi khác, nó có thể được biểu diễn dưới dạng thuật ngữ và ký hiệu mã của chúng - số Gödel và do đó, một số như vậy tồn tại. Vậy thì có thể số T không tồn tại.
Giải thích thứ hai. Không có cách chứng minh số học nào cho định lý T mà sẽ là sự thay thế của E. Vì vậy, nếu không có bằng chứng thì đó là vì bản thân nó không phải là một định lý. Điều này dẫn đến cách giải thích thứ ba.
Cách hiểu thứ ba. Một biểu thức mà số Gödel là -thay thế E không phải là một định lý của số học hình thức số học. Nhưng đây chính là chỗ mâu thuẫn, vì theo cách xây dựng, chính nó là sự thay thế cho E và theo cách xây dựng, con số này không có gì khác ngoài chính con số E. Từ đây tuân theo cách giải thích cuối cùng về e.
Tôi thừa nhận rằng tôi đã đọc chính ý tưởng xem xét câu hỏi về sự tồn tại của Chúa từ khía cạnh này từ Anatoly Aleksandrovich Wasserman:
http://ru.wikipedia.org/wiki/%D0%90%D0%BD%D0%B0%D1%82%D0%BE%D0%BB%D0%B8%D0%B9_%D0%90%D0 %BB%D0%B5%D0%BA%D1%81%D0%B0%D0%BD%D0%B4%D1%80%D0%BE%D0%B2%D0%B8%D1%87_%D0%92 %D0%B0%D1%81%D1%81%D0%B5%D1%80%D0%BC%D0%B0%D0%BD#.D0.A0.D0.B5.D0.BB.D0.B8. D0.B3.D0.B8.D0.BE.D0.B7.D0.BD.D1.8B.D0.B5_.D0.B2.D0.B7.D0.B3.D0.BB.D1.8F.D0. B4.D1.8B
Nhưng tôi muốn phát triển ý tưởng này và mô tả nó chi tiết hơn một chút.
Trong tôn giáo (cũng như trong phi tôn giáo) có một tiên đề nhất định về xây dựng. Ít nhất là ở lý tưởng, nếu đây không chỉ là niềm tin mù quáng mà là sự lựa chọn có ý thức và sáng suốt. Chẳng hạn, một tiên đề của vật lý có thể coi là “có thể nhận biết được thiên nhiên thông qua lý trí và kết luận logic, mọi định luật vật lý đều giống nhau ở mọi điểm trong không gian và ở mọi thời điểm”. Ví dụ, tiên đề của tôn giáo có thể được coi là câu nói “Chúa tồn tại và là nguyên nhân đầu tiên của vạn vật”. Nói cách khác, chắc chắn rằng tất cả các chi tiết và nhánh khác nhau có thể được quy giản thành một số tuyên bố quan trọng, không thể chứng minh được, chính là những tiên đề đó.
Hãy xem xét từ những vị trí này niềm tin tôn giáo. Tiên đề quan trọng nhất của tôn giáo: “Chúa tồn tại và là nguyên nhân đầu tiên của vạn vật”.
Bây giờ chúng ta hãy nhớ một trong những điều quan trọng nhất định lý toán học, định lý Godel.
http://elementy.ru/trefil/21142
Định lý Gödel yếu: "Bất kỳ hệ tiên đề hình thức nào cũng chứa các giả định chưa được giải quyết" hoặc "nếu một hệ tiên đề hoàn chỉnh thì nó không nhất quán."
Định lý mạnh mẽ của Gödel: "Tính đầy đủ (hoặc không đầy đủ) về mặt logic 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 hay bác bỏ nó, cần có các tiên đề bổ sung (củng cố hệ thống)."
Hãy nhớ lại một số định nghĩa. Một hệ tiên đề được coi là hoàn chỉnh nếu bất kỳ phát biểu nào được xây dựng cho một hệ tiên đề nhất định đều có thể chứng minh được (nghĩa là nó đúng hoặc sai). Một giả định chưa được giải quyết là một tuyên bố mà cả sự thật và giả của nó đều không thể được chứng minh, nghĩa là tuyên bố đó không thể chứng minh được về mặt logic. Một hệ tiên đề là mâu thuẫn nếu một và cùng một mệnh đề có thể được chứng minh là vừa đúng vừa sai.
Từ định lý Gödel, suy ra rằng nếu khái niệm về Chúa được đưa vào một hệ tiên đề, thì hệ thống này chưa hoàn chỉnh, tức là có những hậu quả (hiện tượng) không thể chứng minh được, nghĩa là chúng có thể tồn tại hoặc không tồn tại, điều này là không thể chứng minh được.
Nhưng điều này mâu thuẫn với hai quy định sau (chọn điều nào thuyết phục nhất): thiên nhiên không chứa đựng những hiện tượng có thể được coi là vừa tồn tại vừa không tồn tại; Quan điểm thứ hai nói rằng, theo định nghĩa, Chúa là nguyên nhân sâu xa của mọi thứ, do đó, Chúa dẫn đến sự tồn tại của một số sự vật (tuyên bố) hoặc dẫn đến sự không tồn tại của chúng, việc đề cập đến Chúa có thể chứng minh hoặc bác bỏ bất kỳ tuyên bố nào. Điều này mâu thuẫn với tính không hoàn chỉnh của hệ thống.
Hoặc nếu không. Nếu chúng ta đưa khái niệm Chúa vào hệ tiên đề và cho rằng nó hoàn chỉnh (bất kỳ phát biểu nào trong một hệ tiên đề hoàn chỉnh đều có thể chứng minh được), thì theo định lý Gödel, một hệ tiên đề như vậy sẽ mâu thuẫn, tức là sẽ có hiện tượng về điều đó người ta có thể chứng minh rằng chúng vừa tồn tại vừa không tồn tại.
Không có ích gì khi đưa Chúa vào một hệ thống tiên đề mâu thuẫn, vì nó mâu thuẫn, tức là nó chứa đựng những hiện tượng có thể được chứng minh là tồn tại và không tồn tại, như đã nêu, mâu thuẫn với bản chất và khái niệm về Chúa.
Cuối cùng, nếu khái niệm về Chúa không được đưa vào hệ thống tiên đề, thì nó không thể được coi là cơ sở cơ bản của vũ trụ, từ đó mọi vật tồn tại đều tuân theo, điều này về cơ bản mâu thuẫn với định nghĩa về Chúa.
Để có giá trị của bằng chứng này, cần phải thừa nhận tính hợp lệ của các định luật logic toán học (logic mệnh đề + phép tính vị từ), giúp thiết lập các quy luật về hệ quả, sự thật, tính giả, tính không nhất quán, tính nhất quán của các mệnh đề và các quy luật khác. thuộc tính và mối quan hệ giữa các câu lệnh.
Nếu chúng ta cho rằng logic toán học không thể áp dụng được cho việc nghiên cứu câu hỏi về sự tồn tại của Chúa, thì hậu quả sẽ là không thể nghiên cứu câu hỏi này với sự trợ giúp của lý luận, với sự trợ giúp của lý trí. Nói cách khác, lý trí nhất quán luôn đưa ra câu trả lời phủ định cho câu hỏi về sự tồn tại của Thiên Chúa.
Cuối cùng thì điều gì sẽ xảy ra... tất nhiên, bất kỳ người nào thậm chí có lý trí dù là nhỏ nhất cũng nhận ra tính hợp lệ của các quy luật logic, điều đó có nghĩa là anh ta luôn đi đến kết luận rằng Chúa theo định nghĩa về “nguyên nhân của vạn vật” không tồn tại . Tất nhiên, một người không có lý trí cho rằng Chúa chỉ có thể được biết đến với sự trợ giúp của cảm xúc (chứ không phải lý trí), có thể nói như vậy, nhưng không có cách nào để thuyết phục người khác về điều này; Hơn nữa, khái niệm về Thiên Chúa là một khái niệm được lý trí hình thành. Người ta đề xuất làm thế nào để chuyển khái niệm lý trí thành cảm giác, và thậm chí theo cách mà nó có thể được truyền đạt cho người khác, vẫn chưa rõ ràng. Một lần nữa, ngay cả một người có lý trí cũng sẽ nói rằng điều này là không thể: chuyển khái niệm trừu tượng của lý trí thành cảm giác và cảm nhận nó.
Cuối cùng, có một lựa chọn khác: “Thiên Chúa không phải là nguyên nhân đầu tiên của mọi sự”. Khi đó những mâu thuẫn như vậy không nảy sinh, tuy nhiên, đây là sự suy yếu đáng kể về vị thế của tôn giáo, vì chính việc Chúa tạo ra mọi thứ, rằng Chúa là khởi đầu của mọi sự khởi đầu, đó là nền tảng cho nhiều tuyên bố về tôn giáo và biện minh trong các tranh chấp.
tái bút Điều đáng chú ý nữa là một điều tò mò, thú vị đối với các nhà vật lý. TRONG định nghĩa này Chúa không nói gì về tính hợp lý của Ngài. Nghĩa là, người ta có thể thêm “Chúa là nguyên nhân hợp lý của vạn vật”, nhưng đây là một định nghĩa thu hẹp, ban đầu không cần thiết để chứng minh. Nếu không có trí thông minh, khái niệm “thần” có thể dễ dàng bị thay thế bằng “điểm kỳ dị và vụ nổ lớn- nguyên nhân của mọi thứ tồn tại." Và câu trả lời sẽ giống nhau: điểm kỳ dị và vụ nổ lớn không phải là nguyên nhân sâu xa của mọi thứ tồn tại.
Thực hiện một sự trừu tượng lớn hơn nữa, chúng ta có thể nói rằng không một hiện tượng hay nguyên nhân nào có thể là nguyên nhân sâu xa của vạn vật, tức là về nguyên tắc, nguyên nhân sâu xa không tồn tại. Lập luận trong khuôn khổ của bất kỳ tiên đề nào, người ta có thể đi đến kết luận rằng nguyên nhân sâu xa của mọi thứ không tồn tại. Nói một cách rất đơn giản, cho dù chúng ta hiểu vũ trụ một cách cơ bản đến đâu, các câu hỏi vẫn luôn mang tinh thần: “Vụ nổ lớn đến từ đâu, điểm kỳ dị đến từ đâu, vũ trụ đang dao động đến từ đâu, từ đâu đến”. đa vũ trụ đến từ đâu, tại sao vũ trụ luôn tồn tại?” vân vân. Về nguyên tắc, nguyên nhân sâu xa của mọi thứ không thể được tìm thấy; nó không nằm trong bất kỳ đối tượng, hiện tượng hay khái niệm nào. Vì vậy, đối với một người, điều này tương đương với sự vắng mặt của nó. Về mặt lý thuyết, người ta có thể giả định sự tồn tại của một người quan sát bên ngoài vũ trụ của chúng ta, người sẽ trả lời câu hỏi mọi thứ đến từ đâu (cùng một tiên đề bổ sung đó, một phần mở rộng trong định lý Gödel), nhưng khi đó câu hỏi sẽ đặt ra là người quan sát bên ngoài, người của anh ta ở đâu? vũ trụ và nguyên nhân sâu xa của tất cả những điều này đều bắt nguồn từ đó.
Sinh thái của cuộc sống. Khoa học và khám phá: Định lý Bất toàn của Gödel, một trong những định lý nổi tiếng nhất của logic toán học, vừa may mắn vừa không may mắn. Ở điểm này cô ấy giống với lý thuyết đặc biệt Thuyết tương đối của Einstein. Một mặt, hầu hết mọi người đều đã nghe điều gì đó về họ. Từ một cách giải thích khác, lý thuyết của Einstein “cho rằng mọi thứ trên thế giới đều là tương đối”.
Định lý Gödel về sự bất toàn, một trong những định lý nổi tiếng nhất của logic toán học, vừa là may mắn vừa là không may mắn. Ở điểm này nó tương tự như thuyết tương đối đặc biệt của Einstein.
Một mặt, hầu hết mọi người đều đã nghe điều gì đó về họ. Mặt khác, theo cách hiểu phổ biến Lý thuyết của Einstein, như đã biết, " nói rằng mọi thứ trên thế giới đều là tương đối" MỘT Định lý bất toàn của Gödel(sau đây gọi tắt là TGN), theo cách diễn đạt dân gian tự do gần giống nhau, “ chứng tỏ có những điều con người không thể hiểu được».
Và vì vậy một số người đang cố gắng áp dụng nó như một lập luận chống lại việc chửi thề chủ nghĩa duy vật , trong khi những người khác, ngược lại, chứng minh với sự giúp đỡ của nó, rằng không có Chúa . Điều buồn cười không chỉ là cả hai bên đều không thể đúng cùng một lúc, mà còn ở chỗ cả bên này lẫn bên kia đều không bận tâm tìm hiểu xem định lý này thực sự phát biểu điều gì.
Vậy thì sao? Dưới đây tôi sẽ cố gắng nói với bạn về nó “trên ngón tay”. Tất nhiên, bài thuyết trình của tôi sẽ không chặt chẽ và trực quan, nhưng tôi sẽ yêu cầu các nhà toán học đừng đánh giá tôi một cách khắt khe. Có thể đối với những người không phải là nhà toán học (trong thực tế, tôi là một trong số đó), sẽ có điều gì đó mới mẻ và hữu ích trong những gì được mô tả dưới đây.
Logic toán học thực sự 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 những hành động cẩn thận và nghiêm ngặt, trong đó điều quan trọng là không nhầm lẫn giữa những gì đã thực sự được chứng minh với những gì “đã rõ ràng”. Tuy nhiên, tôi hy vọng rằng để hiểu được “đề cương chứng minh TGN” sau đây, người đọc chỉ cần có kiến thức về toán/khoa học máy tính phổ thông, các kỹ năng tư duy logic và thời gian 15-20 phút.
Để đơn giản hóa phần nào, TGN tuyên bố rằng có đủ ngôn ngữ phức tạp có những tuyên bố không thể chứng minh được. Nhưng trong cụm từ này hầu như mọi từ đều cần giải thích.
Hãy bắt đầu bằng việc cố gắng tìm hiểu chứng minh là gì. Chúng ta hãy giải một số bài toán số học ở trường. Ví dụ: giả sử bạn cần chứng minh tính đúng đắn của công thức đơn giản sau: “∀x(x−1)(x−2)−2=x(x−3)” (để tôi nhắc bạn rằng ký hiệu ∀ được đọc “cho bất kỳ” và được gọi là “bộ định lượng phổ quát”). Bạn có thể chứng minh điều đó bằng cách biến đổi nó giống hệt như thế này:
∀x(x−1)(x−2)−2=x(x−3)
∀xx2−3x+2−2=x2−3x
∀xx2−3x–x2+3x=0
∀x0=0
ĐÚNG VẬY
Việc chuyển đổi từ công thức này sang công thức khác xảy ra theo những quy tắc nổi tiếng nhất định. Ví dụ, 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ó - đây là một tiên đề của số học. Và do đó, toàn bộ quy trình chứng minh sẽ chuyển công thức sang giá trị Boolean TRUE. Kết quả cũng có thể là LIE - nếu chúng ta bác bỏ một số công thức. Trong trường hợp này, chúng ta sẽ chứng minh sự phủ nhận của nó. Người ta có thể tưởng tượng một chương trình (và những chương trình như vậy thực sự đã được viết) sẽ chứng minh những tuyên bố tương tự (và phức tạp hơn) mà không cần sự can thiệp của con người.
Hãy nói điều tương tự một cách trang trọng 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 để từ các chuỗi này chúng ta có thể chọn một tập hợp con S cái gọi là câu - 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 P gán các câu lệnh từ S một trong hai giá trị: TRUE hoặc FALSE (nghĩa là ánh xạ chúng tới tập Boolean B gồm hai phần tử).
Hãy gọi cặp này- tập hợp các câu lệnh S và hàm P từ >S đến B - "ngôn ngữ của tuyên bố". Lưu ý rằng trong ý 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 “ Hãy đến đây!"không đúng cũng không sai, nghĩa là, theo quan điểm của logic toán học, nó không phải là một tuyên bố.
Đối với những gì tiếp theo, chúng ta cần khái niệm về một thuật toán. Tôi sẽ không đưa ra một định nghĩa chính thức về nó ở đây - điều đó sẽ khiến chúng ta lạc lối khá xa. Tôi sẽ giới hạn bản thân ở mức không chính thức: “thuật toán” là một chuỗi các hướng dẫn rõ ràng (“chương trình”), trong đó số cuối cùng bước chuyển dữ liệu đầu vào thành kết quả.
Những gì in nghiêng về cơ bản là quan trọng - nếu chương trình lặp lại 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 vào trường hợp của chúng tôi, người đọc có thể coi 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, mà đố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ó tạo ra kết quả Boolean.
Chúng ta hãy tự hỏi: với mỗi hàm P đều có một “thuật toán chứng minh” (hay nói ngắn gọn là “ suy diễn"), tương đương với hàm này, tức là chuyển đổi từng câu lệnh thành đúng giá trị Boolean giống với nó? Câu hỏi tương tự có thể được trình bày ngắn gọn hơn: Có phải mọi hàm trên một tập hợp các câu lệnh đều có thể tính toán được không?
Như bạn đã đoán, từ tính hợp lệ của TGN thì không, không phải mọi hàm - có những hàm không thể tính toán được thuộc loại này. Nói cách khác, Không phải mọi tuyên bố đúng đều có thể được chứng minh.
Rất có thể câu nói này sẽ gây ra sự phản kháng nội tâm trong bạn. Điều này là do một số trường hợp. Thứ nhất, khi chúng ta được dạy toán học thì đôi khi có ấn tượng sai lầm về sự đồng nhất gần như hoàn chỉnh của các cụm từ “Định lý X là đúng” và “Định lý X có thể được chứng minh hoặc kiểm chứng”.
Tuy nhiên, nếu bạn nghĩ về nó, điều này không hề 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 thử một số ít phương án), trong khi những định lý khác lại rất khó. Ví dụ, chúng ta hãy nhớ lại câu chuyện vĩ đại nổi tiếng Định lý Fermat:
không có như vậy tự nhiên x,y,z và n>2, xn+yn=zn,
bằng chứng về điều này chỉ được tìm thấy ba thế kỷ rưỡi sau công thức đầu tiên (và nó còn lâu mới cơ bản). VỚI Người ta 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ó. Không có bất kỳ khẳng định nào đúng nhưng không thể chứng minh được (và không thể kiểm chứng đầy đủ).
Lập luận trực quan thứ hai chống lại TGN tinh tế hơn. Giả sử chúng ta có một số loại tuyên bố 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? Vì vậy, chúng tôi sẽ làm phức tạp hệ thống bằng chứng của mình một chút, nhưng điều này không đáng sợ.
Lập luận này sẽ hoàn toàn đúng nếu có một số hữu hạn các phát biểu không thể chứng minh được. Trong thực tế, những điều sau đây có thể xảy ra: sau khi đưa ra một tiên đề mới, bạn tình cờ gặp một tuyên bố mới không thể chứng minh được. Nếu bạn chấp nhận nó như một tiên đề khác, bạn sẽ vấp phải tiên đề thứ ba. Và cứ thế đến vô tận.
Họ nói rằng khoản khấu trừ sẽ vẫn chưa đầy đủ. Chúng ta cũng có thể buộc thuật toán chứng minh hoàn thành trong một số bước hữu hạn với một số kết quả cho bất kỳ cách phát âm 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ố sai, hoặc nói dối - đối với những người chung thủy.
Trong những trường hợp như vậy họ nói rằng việc suy luận là mâu thuẫn. Do đó, một công thức khác của TGN có vẻ như thế này: “ Có những ngôn ngữ mệnh đề không thể thực hiện được quá trình suy diễn nhất quán hoàn chỉnh." - do đó có tên của định lý.
Đôi khi được gọi là “định lý Gödel”, phát biểu nói 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 phải khái quát hóa nó. Theo một nghĩa nào đó thì điều này đúng, mặc dù cách diễn đạt này có xu hướng che khuất vấn đề hơn là làm rõ nó.
Tôi cũng sẽ lưu ý rằng nếu chúng ta đang nói về các hàm quen thuộc ánh xạ một tập hợp số thực vào đó, thì tính chất “không tính toán được” của hàm sẽ không làm 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 được”. ” - đây là những thứ khác nhau).
Kurt Godel
Bất kỳ học sinh nào cũng biết rằng, trong trường hợp hàm sinx, bạn phải rất may mắn với lập luận để quá trình tính toán chính xác biểu diễn số thập phân Giá trị của hàm này kết thúc ở một số bước hữu hạn.
Nhưng rất có thể bạn sẽ tính toán nó bằng một chuỗi vô hạn và phép tính này sẽ không bao giờ dẫn đến một kết quả chính xác, mặc dù nó có thể đến gần như bạn muốn - đơn giản vì giá trị 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 1, cũng có những hàm không thể tính toán được, mặc dù chúng có cấu trúc hoàn toàn khác.
Với những mục đích sâu hơn, chúng ta sẽ mô tả “ngôn ngữ của số học hình thức”. Hãy xem xét một lớp các 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), nhận giá trị tự nhiên, dấu cách, ký tự các phép tính số học, đẳng thức và bất đẳng thức, các bộ định lượng ∃ (“tồn tại”) và ∀ (“đối với 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ụ: “12=+∀x>” 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 theo quan điểm của số học thông thường) sẽ là tập hợp các câu lệnh của chúng ta.
Ví dụ về các câu lệnh số học hình thức:
1=1
2×2=5
∃xx>3
∀y∀zy×z>y+ z
vân vân. Bây giờ, hãy gọi “công thức có 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 đó làm tham số này. Ví dụ về FSP (với tham số x):
x=0
2×2=x
∃yx+y>x
vân vân. Nói cách khác, FSP tương đương với các hàm đối số tự nhiên có giá trị Boolean.
Chúng ta hãy biểu thị tập hợp tất cả các FSP bằng chữ F. Rõ ràng là nó có thể được sắp xếp theo thứ tự (ví dụ: đầu tiên chúng ta 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, tiếp theo là các công thức hai chữ cái, v.v.; điều đó không quan trọng cho chúng tôi biết thứ tự sẽ diễn ra theo bảng chữ cái nào). Do đó, bất kỳ FSP nào cũng tương ứng với số k của nó trong danh sách có thứ tự và chúng ta sẽ ký hiệu nó là Fk.
Bây giờ chúng ta chuyển sang sơ đồ chứng minh TGN theo công thức sau:
Đối với ngôn ngữ mệnh đề của số học hình thức, không có hệ thống suy diễn nhất quán hoàn chỉnh.
Chúng ta sẽ chứng minh điều đó bằng phản chứng.
Vì vậy, hãy giả sử rằng một hệ thống suy diễn như vậy tồn tại. Chúng ta hãy mô tả thuật toán phụ trợ A sau đây, gán giá trị Boolean cho số tự nhiên k như sau:
1. Tìm công thức thứ k trong danh sách F
2. Thay số k vào đó làm đối số.
3. Chúng tôi áp dụng thuật toán chứng minh của mình cho tuyên bố kết quả (theo giả định của chúng tôi là nó tồn tại), chuyển nó thành TRUE hoặc FALSE.
4. Áp dụng phủ định logic cho kết quả thu được.
Nói một cách đơn giản, thuật toán mang lại giá trị TRUE khi và chỉ khi kết quả của việc thay thế số của chính nó vào FSP trong danh sách của chúng tôi đưa ra một tuyên bố sai.
Ở đây chúng ta đến chỗ duy nhất mà tôi yêu cầu người đọc tin lời tôi.
Rõ ràng là, theo giả định ở trên, bất kỳ FSP nào từ F đều có thể được liên kết với một thuật toán chứa số tự nhiên ở đầu vào và giá trị Boolean ở đầu ra.
Điều ngược lại ít rõ ràng hơn:
Bổ đề: Bất kỳ thuật toán nào chuyển đổi một số tự nhiên thành giá trị Boolean đều tương ứng với một FSP nào đó từ tập F.
Việc chứng minh bổ đề này đòi hỏi, ở mức tối thiểu, một định nghĩa chính thức, thay vì 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ó khá hợp lý.
Trên thực tế, các thuật toán được viết bằng ngôn ngữ thuật toán, trong số đó có những từ kỳ lạ, chẳng hạn như Brainfuck, bao gồm tám từ một ký tự, tuy nhiên, bất kỳ thuật toán nào cũng có thể được thực hiện. Sẽ thật kỳ lạ nếu ngôn ngữ phong phú hơn của các công thức số học hình thức mà chúng tôi mô tả hóa ra lại kém hơn - mặc dù, không nghi ngờ gì nữa, nó không phù hợp lắm cho lập trình thông thường.
Vượt qua nơi trơn trượt này, chúng tôi nhanh chóng đi đến đích.
Vì vậy, ở trên chúng tôi đã mô tả Thuật toán A. Theo bổ đề mà tôi yêu cầu bạn tin, có một FSP tương đương. Nó có một số số trong danh sách F - chẳng hạn như n. Chúng ta hãy tự hỏi, Fn(n) là gì? Hãy để đây là SỰ THẬT. Khi đó, theo cách xây dựng của thuật toán A (và do đó có hàm tương đương Fn), điều này có nghĩa là kết quả của việc thay thế số n vào hàm Fn là SAI.
Điều ngược lại được kiểm tra theo cách tương tự: từ Fn(n)=FALSE nó dẫn đến Fn(n)=TRUE. Chúng ta đã đi đến một mâu thuẫn, có nghĩa là giả định ban đầu là sai. Vì vậy, không có hệ thống suy diễn nhất quán hoàn chỉnh cho số học hình thức. Q.E.D.
Ở đây thật thích hợp để nhớ lại Epimenides, người như đã biết, đã tuyên bố rằng tất cả người Crete đều là những kẻ nói dối, bản thân ông cũng là người Crete. Trong một cách trình bày ngắn gọn hơn về tuyên bố của ông (được gọi là “nghịch lý kẻ nói dối”) có thể được phát biểu như sau: “ tôi đang nói dối" Chính xác là một tuyên bố như vậy, bản thân nó đã tuyên bố là sai lầm, mà chúng tôi đã sử dụng để làm bằng chứng.
Tóm lại, tôi muốn lưu ý rằng TGN không tuyên bố đ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ỷ lệ của hai số nguyên (hãy nhớ rằng câu lệnh này có một bằng chứng rất tao nhã đã hơn hai nghìn năm tuổi?).Và nghiệm của đa thức với hệ số hữu tỷ không phải tất cả các số đều như vậy . Và bây giờ hóa ra 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 chứng minh được đưa ra là dành cho số học hình thức, nhưng dễ dàng thấy rằng TGN có thể áp dụng được 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 xác định một ngôn ngữ như sau:
"Bất kỳ cụm từ nào tiếng Trung Trong trích dẫn của đồng chí Mao Trạch Đông là đúng, nếu không có thì là sai”.
Sau đó, thuật toán chứng minh nhất quán và đầy đủ tương ứng (người ta có thể gọi nó là “suy diễn giáo điều”) trông giống như sau:
“Lật qua sách trích dẫn của Đồng chí Mao Trạch Đông cho đến khi tìm được câu nói mình cần tìm. Nếu tìm được thì đúng, còn nếu sách báo giá hết mà không tìm thấy thì đó là sai ”.
Điều cứu chúng ta ở đây là bất kỳ cuốn sách 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 được cho ngôn ngữ của các phát biểu mang tính 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?được xuất bản
Bất kỳ hệ tiên đề toán học nào bắt đầu từ một mức độ nhất định sự phức tạp là mâu thuẫn nội bộ hoặc không đầy đủ.
Năm 1900, Hội nghị 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 luận văn 23 vấn đề quan trọng nhất, theo ý kiến của ông, mà các nhà lý thuyết của thế kỷ XX sắp tới phải giải quyết. Số hai trong danh sách của anh ấy là một trong số đó nhiệm vụ đơn giản, câu trả lời có vẻ hiển nhiên cho đến khi bạn tìm hiểu sâu hơn một chút. Nói ngôn ngữ hiện đại, đó là câu hỏi: toán học có tự cung tự cấp được không? Nhiệm vụ thứ hai của Hilbert tập trung vào nhu cầu chứng minh một cách chặt chẽ rằng hệ tiên đề - những mệnh đề cơ bản được chấp nhận 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 người ta 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ể định nghĩa một hệ thống tiên đề sao cho trước hết chúng sẽ nhất quán với nhau và thứ hai, từ đó có thể rút ra kết luận về tính đúng hay sai của bất kỳ tuyên bố 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 Euclide tiêu chuẩn (hình học trên mặt phẳng), có thể chứng minh một cách chắc chắn rằng câu “tổng các góc của một tam giác là 180°” là đúng và câu “tổng các góc của một tam giác là 137” °” là sai. Về cơ bản mà nói, trong hình học Euclide, bất kỳ phát biểu nào cũng có thể sai hoặc đúng và không có lựa chọn thứ ba. 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ũng xảy ra 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 nhà toán học người Vienna đeo kính Kurt Gödel đã xuất bản một bài báo ngắn làm đảo lộn toàn bộ thế giới gọi là “logic toán học”. Sau những lời mở đầu lý thuyết và toán học dài và phức tạp, ông đã thiết lập được những điều sau đây theo đúng nghĩa đen. Hãy lấy bất kỳ tuyên bố nào như: “Giả định số 247 trong hệ thống tiên đề này là không thể chứng minh được về mặt logic” và gọi nó là “tuyên bố A”. Vì vậy, Gödel chỉ cần chứng minh điều sau tài sản tuyệt vời bất kỳ hệ tiên đề nào:
“Nếu câu A có thể được chứng minh thì câu không-A có thể được chứng minh.”
Nói cách khác, nếu tính đúng đắn của khẳng định “giả định 247 là không thể chứng minh được” có thể được chứng minh thì tính đúng đắn của khẳng định “giả định 247 là có thể chứng minh được” cũng có thể được chứng minh. Nghĩa là, quay trở lại cách trình bày bài toán thứ hai của Hilbert, nếu một hệ tiên đề hoàn chỉnh (nghĩa là bất kỳ phát biểu nào trong đó đều có thể được chứng minh) thì đó là mâu thuẫ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 đầy đủ. Nghĩa là, chúng ta phải chấp nhận một thực tế là 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 câu 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ổ tiên đề mà chúng ta có được chấp nhận. Nếu không có những tuyên bố như vậy, thì các tiên đề của chúng ta mâu thuẫn nhau, và trong khuôn khổ của nó chắc chắn sẽ có những công thức có thể vừa được chứng minh vừa bị bác bỏ.
Vì vậy, việc xây dựng định lý đầu tiên, hay định lý yếu, không đầy đủ của Gödel: “Bất kỳ hệ thống tiên đề hình thức nào cũng chứa đựng các giả định chưa được giải quyết”. Nhưng Gödel không dừng lại ở đó, ông đã xây dựng và chứng minh định lý thứ hai, hay định lý mạnh, về tính bất toàn của Gödel: “Tính đầy đủ (hoặc không đầy đủ) về mặt logic của bất kỳ hệ tiên đề nào đều không thể được chứng minh trong khuôn khổ của hệ thống này. Để chứng minh hay bác bỏ nó, cần có thêm các tiên đề (củng cố hệ thống).”
Sẽ an toàn hơn nếu nghĩ rằng các định lý của Gödel có bản chất trừu tượng và không liên quan đến chúng ta mà chỉ là những lĩnh vực logic toán học cao siêu, nhưng trên 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ý học người Anh Roger Penrose (sn. 1931) đã chỉ ra rằng các định lý Gödel có thể được sử dụng để chứng minh sự tồn tại sự khác biệt cơ bản giữa bộ não con người và máy tính. Ý nghĩa lý luận của ông rất đơn giản. Máy tính hoạt động một cách logic và không thể xác định câu A là đúng hay sai nếu nó vượt ra ngoài các tiên đề, và những câu như vậy, theo định lý Gödel, chắc chắn 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à không thể bác bỏ về mặt logic như vậy, luôn có thể xác định sự thật hay giả của nó - dựa trên kinh nghiệm hàng ngày. Ít nhất là trong chuyện này bộ não con người vượt trội hơn một máy tính bị ràng buộc bởi thuần túy mạch logic. Bộ não con người có khả năng hiểu được toàn bộ chiều sâu sự thật chứa đựng trong các định lý của Gödel, nhưng bộ não máy tính thì không bao giờ có thể làm được. Vì vậy, bộ não con người không khác gì một chiếc máy tính. Anh ta có khả năng đưa ra quyết định và kiểm tra Turing sẽ vượt qua thành công.
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 GÖDEL
Kurt Godel, 1906–78
Nhà toán học người Áo, sau đó là người Mỹ. Sinh ra ở 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 khoa toán (từ năm 1930 - giáo sư). Năm 1931, ông công bố một định lý mà sau này mang tên ông. Là một người thuần túy phi chính trị, anh ta đã phải trải qua một khoảng thời gian vô cùng khó khăn với vụ sát hại bạn mình và đồng nghiệp cùng khoa bởi một sinh viên Đức Quốc xã và rơi vào trạng thái trầm cảm sâu sắc, những cơn tái phát ám ảnh anh ta đến hết cuộc đời. Vào những năm 1930, ông di cư sang Mỹ nhưng lại 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 trốn sang Mỹ để quá cảnh qua Liên Xô và Nhật Bản. Ông đã làm việc một thời gian tại Viện Nghiên cứu Cao cấp Princeton. 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 trong bệnh viện tâm thần vì đói, không chịu ăn vì tin rằng họ sẽ đầu độc ông.
| Bình luận: 0 |
Mô hình khoa học phát triển như thế nào trong khoa học tự nhiên? Những thứ hàng ngày tích lũy hoặc kinh nghiệm khoa học, các cột mốc quan trọng của nó được xây dựng cẩn thận dưới dạng các định đề và tạo thành nền tảng của mô hình: một tập hợp các tuyên bố được tất cả những người làm việc trong khuôn khổ mô hình này chấp nhận.
Anatoly Wasserman
Năm 1930, Kurt Gödel đã chứng minh hai định lý, được dịch từ ngôn ngữ toán học sang ngôn ngữ của con người, có nghĩa gần đúng như sau: Bất kỳ hệ thống tiên đề nào đủ phong phú để được sử dụng để định nghĩa số học sẽ không đầy đủ hoặc mâu thuẫn. Không hệ thống hoàn chỉnh- điều này có nghĩa là trong hệ thống có thể đưa ra một tuyên bố không thể được chứng minh hoặc bác bỏ bằng hệ thống này. Nhưng Thiên Chúa, theo định nghĩa, là nguyên nhân cuối cùng của mọi nguyên nhân. Từ quan điểm toán học, điều này có nghĩa là việc đưa ra tiên đề về Chúa làm cho toàn bộ tiên đề của chúng ta trở nên hoàn chỉnh. Nếu có một Chúa, thì bất kỳ tuyên bố nào cũng có thể được chứng minh hoặc bác bỏ, bằng cách này hay cách khác, đề cập đến Chúa. Nhưng theo Gödel, hệ thống tiên đề hoàn chỉnh chắc chắn là mâu thuẫn. Nghĩa là, nếu chúng ta tin rằng Chúa tồn tại, thì chúng ta buộc phải đi đến kết luận rằng trong tự nhiên có thể xảy ra mâu thuẫn. Và vì không có mâu thuẫn nào, nếu không thì toàn bộ thế giới của chúng ta sẽ sụp đổ vì những mâu thuẫn này, nên chúng ta phải đi đến kết luận rằng sự tồn tại của Chúa không thể tương thích với sự tồn tại của tự nhiên.
Sosinsky A. B.
Định lý Gödel, cùng với việc phát hiện ra thuyết tương đối, cơ học lượng tử và DNA, thường được coi là lớn nhất thành tựu khoa học Thế kỷ XX. Tại sao? Bản chất của nó là gì? Ý nghĩa của nó là gì? Những câu hỏi này trong bài giảng của mình là một phần của dự án “ Bài giảng công khai"Polit.ru" tiết lộ Alexey Bronislavovich Sosinsky, nhà toán học, giáo sư tại Đại học Độc lập Moscow, cán bộ của Huân chương Học thuật Cộng hòa Pháp, người đoạt Giải thưởng Chính phủ Nga trong lĩnh vực giáo dục năm 2012. Đặc biệt, một số công thức khác nhau của nó đã được đưa ra, ba cách tiếp cận chứng minh nó đã được mô tả (Kolmogorov, Chaitin và Gödel), và ý nghĩa của nó đối với toán học, vật lý, khoa học máy tính và triết học.
Uspensky V. A.
Bài giảng được dành cho phiên bản cú pháp của Định lý Bất toàn của Gödel. Chính Gödel đã chứng minh phiên bản cú pháp bằng cách sử dụng một giả định mạnh hơn tính nhất quán, cụ thể là cái gọi là tính nhất quán omega.
Uspensky V. A.
Bài giảng học hè « Toán học hiện đại", Dubna.
về chủ đề: “Định lý của Chúa”
Kurt Godel
Kurt Gödel là chuyên gia hàng đầu về 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ĩ và là trợ lý giáo sư vào năm 1933–1938. Sau Anschluss, ông di cư sang Hoa Kỳ. Từ 1940 đến 1963 Gödel làm việc tại Viện Princeton nghiên cứu cao hơn. Gödel - tiến sĩ danh dự của Đại học Yale và Harvard, thành viên Học viện Quốc gia Khoa học Hoa Kỳ và Hiệp hội Triết học Hoa Kỳ.
Năm 1951, Kurt Gödel được trao giải cao nhất giải thưởng khoa học Hoa Kỳ - Giải thưởng Einstein. Trong một bài viết dành riêng cho sự kiện này, một nhà toán học lớn khác của thời đại chúng ta, John von Neumann, đã viết: “Đóng góp của Kurt Gödel cho logic hiện đại thực sự rất to lớn. Đây không chỉ là một tượng đài. Đây là một cột mốc quan trọng ngăn cách hai thời đại... Không hề phóng đại, có thể nói rằng công trình của Gödel đã thay đổi hoàn toàn 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 Gödel trong logic toán học cũng cho thấy rằng tác giả của chúng về cơ bản đã đặt nền móng cho toàn bộ các phần của khoa học này: lý thuyết mô hình (1930; cái gọi là định lý về tính đầy đủ 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 “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 quy giản một số loại câu của logic cổ điển thành những câu tương tự mang tính trực giác của chúng, điều này đặt ra nền tảng cho việc sử dụng 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 hình thức (1932–1933; dẫn đến khả năng quy giản số học cổ điển thành số học trực giác, cho thấy tính nhất quán của số học thứ nhất so với số học thứ hai), lý thuyết về thuật toán và hàm đệ quy (1934; định nghĩa về khái niệm hàm đệ quy tổng quát, đóng vai trò vai trò quyết định một mặt, trong việc thiết lập tính không thể giải được bằng thuật toán của một số vấn đề quan trọng nhất trong toán học. Và trong việc thực hiện các bài toá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; chứng minh 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ả quan trọng nhất 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ý bất toàn của Gödel
Giới thiệu
Năm 1931, tại một trong những nước Đức tạp chí khoa học một bài báo tương đối nhỏ xuất hiện với tiêu đề khá đáng sợ “Về những mệnh đề chính thức không thể quyết định được của Nguyên lý 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 đến 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 trình này đóng một vai trò quyết định trong lịch sử logic và toán học. Trong quyết định Đại học Harvard về việc trao cho Gödel một giải thưởng danh dự tiến sĩ(1952), bà được coi là một trong 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 có ý nghĩa gì đối với hầu hết các nhà toán học. Được nhắc đến trong tựa đề của nó, Principia Mathematica là một luận thuyết đồ sộ gồm ba tập của Alfred North Whitehead và Bertrand Russell về logic toán học và các nền tảng của toán học; làm quen với chuyên luận này không có nghĩa là một điều kiện cần thiết Vì công việc thành công trong hầu hết các ngành toán học. Sự quan tâm đến các vấn đề được đề cập 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, lý luận mà Gödel đưa ra trong các chứng minh của ông là rất bất thường vào thời đó. Để hiểu đầy đủ về chúng đòi hỏi phải có sự thông thạo đặc biệt về chủ đề 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ý bất toàn thứ nhất
Định lý bất toàn đầu tiên của Gödel rõ ràng là kết quả quan trọng nhất trong logic toán học. Nghe có vẻ như thế này:
Đối với một lý thuyết hình thức và có thể tính toán nhất quán tùy ý, trong đó các phát biểu số học cơ bản có thể được chứng minh, thì một phát biểu số học thực sự có thể được xây dựng, nhưng tính đúng đắn của nó không thể được chứng minh trong khuôn khổ lý thuyết. Nói cách khác, bất kỳ hoàn toàn lý thuyết hữu ích, đủ để biểu diễn số học, không thể vừa nhất quán vừa đầy đủ.
Ở đây từ “lý thuyết” có nghĩa là “ tập vô hạn“các phát biểu, một số trong đó được cho là đúng mà không cần bằng chứng (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ừ các tiên đề, và do đó được cho là (đã được chứng minh) là đúng. Cụm từ “có thể chứng minh được về mặt lý thuyết” có nghĩa là “có thể rút ra từ các tiên đề và nguyên hàm của lý thuyết (ký hiệu hằng số của bảng chữ cái) bằng cách sử dụng logic tiêu chuẩn (thứ tự đầu tiên). 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ố quy trình (thuật toán) cơ học nào đó có thể xây dựng một tuyên bố dựa trên các tiên đề, nguyên hàm và logic bậc nhất. “Số học cơ bản” bao gồm các phép tính cộng và nhân trên các số tự nhiên. Tuyên bố đúng nhưng không thể chứng minh được thường được gọi là "chuỗi Gödel" đối với một lý thuyết nhất định, nhưng có vô số tuyên bố khác trong lý thuyết có cùng đặc tính: không thể chứng minh được trong lý thuyết về sự thật.
Giả định rằng một lý thuyết có thể tính toán được có nghĩa là về nguyên tắc có thể thực hiện được 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 trong một thời gian dài tùy ý, có thể lên đến vô cùng) sẽ tính ra 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ể thu được một cách hiệu quả từ danh sách đó.
Định lý bất toàn đầu tiên có tựa đề "Đị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ể giải quyết được 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ó nghe như sau:
“Kết luận chung về sự tồn tại của các mệnh đề không thể quyết định được là:
Định lý VI .
Đối 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 cũng không (v thế hệ r), không ¬( v thế hệ r)không thuộc về Flg (k)(v ở đâu BIẾN MIỄN PHÍ r ) ».
chỉ định Flgđến từ anh ấy. Folgerungsmenge- nhiều trình tự, thế hệđến từ anh ấy. Khái quát hóa– khái quát hóa.
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ể chứng minh được." Nếu như G có thể được chứng minh trong khuôn khổ của lý thuyết, thì trong trường hợp này 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ẽ mâu thuẫn. Nhưng nếu G không thể chứng minh được thì nó đúng và do đó lý thuyết này chưa đầy đủ (phát biểu G không thể suy ra được trong đó).
Đây là lời giải thích bằng tiếng Anh đơn giản ngôn ngữ tự nhiên, và do đó không hoàn toàn nghiêm ngặt về mặt toán học. Để đưa ra một bằng chứng chặt chẽ, Gödel đã đánh số các phát biểu bằng số tự nhiên. Trong trường hợp này, lý thuyết mô tả số cũng thuộc tập hợp các mệnh đề. Trong trường hợp này, các câu hỏi về tính chứng minh của các mệnh đề có thể được trình bày dưới dạng các câu hỏi về tính chất của các số tự nhiên, phải tính toán được nếu lý thuyết hoàn chỉnh. Trong những thuật ngữ này, phát biểu của Gödel nói rằng không có con số nào với một số một tài sản nhất định. Một con số có tính chất này sẽ là bằng chứng cho sự không nhất quán của lý thuyết. Nếu con số như vậy tồn tại thì lý thuyết không nhất quán, trái với giả định ban đầu. Vì vậy, giả sử rằng lý thuyết này là nhất quán (như được giả định trong tiền đề của định lý), hóa ra con số như vậy không tồn tại và tuyên bố của Gödel là đúng, nhưng trong khuôn khổ lý thuyết thì không thể chứng minh được điều đó ( do đó lý thuyết là không đầy đủ). Một điểm khái niệm quan trọng là cần phải giả định rằng lý thuyết này là nhất quán để tuyên bố tuyên bố của Gödel là đúng.
Định lý bất toàn thứ hai của Gödel
Định lý bất toàn thứ hai của Gödel được phát biểu như sau:
Đối với bất kỳ lý thuyết T nào có thể đếm được đệ quy chính thức (nghĩa là được tạo ra một cách hiệu quả), bao gồm các phát biểu chân lý số học cơ bản và các phát biểu có thể chứng minh hình thức nhất định, lý thuyết này T bao gồm một khẳng định về tính tự nhất quán khi và chỉ khi lý thuyết T không nhất quán.
Nói cách khác, tính nhất quán của một lý thuyết đủ phong phú không thể được chứng minh bằng lý thuyết này. Tuy nhiên, có thể hóa ra là 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 là về tính nhất quán của lý thuyết thứ hai này, v.v.
Dùng định lý này để chứng minh rằng hoạt động thông minh Nó không phụ thuộc vào tính toán, nhiều người đã thử. Ví dụ, vào năm 1961, nhà logic học nổi tiếng John Lucas đã nghĩ ra một chương trình tương tự. Lý luận của anh ấy hóa ra khá dễ bị tổn thương - tuy nhiên, anh ấy đặt ra nhiệm vụ rộng rãi hơn. Roger Penrose có một cách tiếp cận hơi khác, được phác thảo hoàn toàn trong cuốn sách, “từ đầu”.
Thảo luận
Hệ quả của các định lý ảnh hưởng đến triết lý toán học, đặc biệt là những hình thức luận sử dụng logic hình thứcđể xác định các nguyên tắc của bạn. Chúng ta có thể phát biểu lại định lý bất toàn thứ nhất như sau: “ không thể tìm được một hệ tiên đề bao quát có thể chứng minh được Tất cả sự thật toán học, và không một lời nói dối nào" Mặt khác, xét về mặt hình thức chặt chẽ, việc cải cách này không có ý nghĩa đặc biệt, vì nó giả định các khái niệm “sự thật” và “sai” được định nghĩa theo nghĩa tuyệt đối hơn là theo nghĩa tương đối cho từng hệ thống cụ thể.