Những nỗ lực trước đây nhằm chứng minh tính phi mâu thuẫn hoặc tính đầy đủ của toán học đã sử dụng một hệ thống logic kí hiệu để tạo nên những mệnh đề về những định lí và lập luận toán học. Nói cách khác, tình trạng của toán học được kiểm tra và đảm bảo giá trị bởi một hệ thống nằm ngoài bản thân nó được gọi là “siêu-toán học”.

Phương pháp tiếp cận của Gödel là xây dựng nên một hệ thống kí hiệu toán học cho phép trình bày những mệnh đề nói về chính bản thân toán học, nhưng bản thân hệ thống ấy lại là một phần của toán học, thay vì nằm bên ngoài cái toán học mà nó trình bày. Nói ngắn gọn, Gödel đã xây dựng nên một hệ thống kí hiệu toán học thể hiện chính toán học.

Nhưng làm thế nào để xây dựng hệ thống kí hiệu đó? Và làm thế nào đề siêu-toán học có thể hợp nhất được với toán học? Gödel đã đưa ra câu trả lời cực kì tài tình. Bước đầu tiên là làm cho mọi mệnh đề toán học tương ứng với một con số. Vì số luôn luôn là một bộ phận của toán học nên bây giờ các mệnh đề của siêu-toán học nói về các định lí và các chứng minh của nó có thể quy giản thành những thao tác về số trong toán học. Cụ thể:

Bước 1

Chúng ta hãy bắt đầu bằng việc liệt kê tất cả các kí hiệu toán học cùng với tất cả các kí hiệu logic và tất cả các số trong cùng một hàng. Danh sách dưới đây là một sự trình bày hết sức giản lược nhằm giải thích ý tưởng tổng quát của việc giải quyết vấn đề.

+ - x = x y 0 1 2 3 4 5 6

Giống như trong trò chơi đếm của John và Jill, hãy đặt những số Gödel tương ứng ở bên dưới:

Nếu bạn cho tôi số Gödel bằng 4, tôi sẽ hiểu rằng đó là mã số tương ứng với dấu bằng (=), nếu số Gödel bằng 10 thì đó là mã số thay mặt cho số 3, vv.

Bước 2

Không riêng các kí hiệu và những số cá biệt mới được gán cho số Gödel tương ứng, mà ngay cả toàn bộ một công thức cũng có thể quy giản thành một số. Ví dụ, công thức 2 + 2 = 4. Công thức này sẽ liên quan với các số 9 (thay mặt cho 2), 1 (cho dấu +), 4 (cho dấu =), và 11 (cho 4). Bây giờ, chúng ta cộng các số này lại để có một số Gödel mới là 34:

9 + 1 + 9 + 4 + 11 = 34

Do đó, 34 được coi là số Gödel thay mặt cho công thức 2 + 2=4

Nhưng đến đây, chúng ta thấy rằng có chuyện bất ổn, vì 34 cũng có thể là một số Gödel dành cho công thức 3 + 1 = 4 (độc giả có thể tự kiểm tra). Như vậy theo cách làm này, số Gödel được xây dựng theo cách trên không duy nhất, và khi phải xử lí những công thức phức tạp hơn, một số Gödel có thể đại diện cho nhiều công thức khác nhau. Rõ ràng là cách làm này không đảm bảo để xác định các định lí, công thức, và chứng minh toán học một cách duy nhất.

Để giải quyết chuyện bất ổn trên, Gödel đề nghị sử dụng số nguyên tố, vì mỗi số nguyên tố, chẳng hạn như 7, 11, 13, 23, … chỉ có một cách phân tích ra thừa số duy nhất, chẳng hạn 7 = 7 x 1 (trong khi những số không phải số nguyên tố có nhiều cách phân tích khác nhau, chẳng hạn 12 = 2 x 6 hoặc 12 = 3 x 4).

Bây giờ, số Gödel tương ứng với công thức 2 + 2 = 4 sẽ được xác định theo cách mới, bằng tích của các luỹ thừa của các cơ số nguyên tố, với các số mũ lần lượt là các số Gödel tương ứng với các thành phần của công thức đã cho, cụ thể là 9, 1, 9, 4, 11. Tóm lại, số Gödel của công thức 2 + 2 = 4 là:

29 x 31 x 59 x 114 x 1311

Con số vĩ đại này là duy nhất tương ứng với một công thức duy nhất. Từ đó, Gödel có thể biểu diễn mọi kí hiệu và mọi công thức trong toán học bởi một số Gödel duy nhất.

Bước 3

Điều gì áp dụng được cho một công thức thì cùng áp dụng được cho một định lí hoặc một chứng minh. Đơn giản là hãy làm tương ứng các số Gödel cho từng kí hiệu và từng dòng của chứng minh. Từ đó sẽ xác định được số Gödel cho toàn bộ chứng minh Y. Bây giờ, có thể nói rằng định lí với số Gödel X có một chứng minh với số Gödel Y. Kí hiệu điều này là Dem (Y, X).

Nhưng có thể xảy ra trường hợp chuỗi chứng minh Y nào đó lại phủ định định lí X. G0del kí hiệu trường hợp này là ~Dem (Y, X). Dễ dàng nhận thấy rằng nếu có thể chứng minh cả Dem (Y, X) lẫn ~Dem (Y, X) cùng tồn tại thì toán học sẽ là mâu thuẫn.

Bước 4

Chúng ta đã đi rất xa tới chỗ thấy rằng có thể quy toàn bộ các định lí toán học và các chứng minh của nó về một loạt số Gödel. Tuy nhiên, chúng ta vẫn chưa chứng tỏ rằng làm thế nào mà một hệ logic có thể thực sự tự nói về chính bản thân nó. Cần phải có một bước xoay chuyển tiếp tục trong vòng xoáy logic.

Giả sử chúng ta xét một trong các yếu tố cơ bản của toán học, rằng các số có thể tiếp tục nối tiếp nhau mãi mãi sao cho mọi số y sẽ có một số X kế tiếp thay thế. Các nhà toán học thích phát biểu điều này dưới dạng sau đây: “Tồn tại một số x nào đó, sao cho x là số kế vị của y”. Viết mệnh đề này dưới dạng công thức như sau:

(∃x)(x = sy) (1)

Số y có số Gödel bằng 6, như đã thể hiện trong bảng liệt kê ở bước 1. Hơn nữa, toàn bộ công thức (1) sẽ có một số Gödel của riêng nó, có thể tính được như bất kì số Gödel nào khác. Gọi số Gödel của (1) là M.

Thay M ngược trở lại vào vị trí y của công thức (1) ta có:

(∃x)(x = sM) (2)

Công thức (2) có the phát biểu như sau: “Tồn tại một số x sao cho nó là số kế vị của M”. Như đã biết, M là một số Gödel nhưng cũng đồng thời là một số số học, chẳng có gì khác với số 6 (thay mặt cho y).

Giống như mọi công thức khác, công thức (2) cũng tương ứng với một số Gödel có thể tính được. Nhưng có một cách thứ hai để tính số Gödel này. Chúng ta có thể tính nó theo cách để sao cho siêu-toán học có thể phản ánh toán học bên trong toán học.

Giả sử chúng ta viết mệnh đề sau đây: “Tồn tại một công thức nhận được từ công thức tương ứng với số Gödel bằng M (công thức (1)) bằng cách thay M cho biến tương ứng với số Gödel bằng 6 (biến y)”. Gọi mệnh đề này là (a).

Mệnh đề (a) không có gì mập mờ. Đó là một mệnh đề có thể diễn đạt bằng kí hiệu logic sao cho số Gödel của nó có thể tính được. Gọi số đó là N. Nói cách khác, mệnh đề (a) và công thức (2) là những hình ảnh phản xạ lẫn nhau - toán học và siêu-toán học phản xạ lẫn nhau trong cùng một hệ thống.

Sau khi đạt được kết quả này - phản ánh những mệnh đê siêu-toán học bên trong bản thân toán học - Gödel có thể tiếp tục xây dựng mệnh đề sau đây: “Công thức tương ứng với so Gödel Z không thể chứng minh được”. Gọi mệnh đê này là mệnh đề (b).

Nói cách khác, Gödel đã thiết lập nên một mệnh đề dạng “Tôi không thể chứng minh được” hoặc “Tôi không thể được chứng minh”.

Gödel nêu thêm hai lập luận. Trước hết, ông chứng minh rằng mặc dù mệnh đề (b) không thể chứng minh được bên trong hệ thống của nó, tuy nhiên nó là một mệnh đề đúng. Nói cách khác, ông đã chứng minh tính đúng đắn của mệnh đề “Toán học là không đầy đủ” (bất toàn).

Thứ hai, ông chứng minh sự đồng thời tồn tại của hai mệnh đề Dem (Y, X) và ~Dem (Y, X), ngụ ý rằng toán học là mâu thuẫn.

Điều ông chứng minh là ở chỗ, nếu thực tế mệnh đề (b) có thể chứng minh được, thì cũng có thể suy ra rằng phủ định của mệnh đề (b) cùng có thể chứng minh được. Có nghĩa là hai mệnh đề đối lập có thể đồng thời chứng minh được. Nhưng nêu mệnh đề (b) chứng minh được thì điều này có nghĩa rằng toán học là đầy đủ - có nghĩa là mọi mệnh đề đều có thể chứng minh được. Do đó, Gödel đi tới kết luận thứ hai: “Nếu toán học là đầy đủ - nghĩa là nếu mệnh đề (b) chứng minh được - thì nó sẽ mẫu thuẫn”.