Vấn đề với liệt kê công thức

Question

Để cho $P_0, P_1, P_2, ...$ là một bảng liệt kê tất cả các công thức logic với một biến miễn phí $n$(đếm được vì chúng là các chuỗi hữu hạn của một bảng chữ cái có thể đếm được). Để cho$Q(n) \iff \lnot P_n(n)$. Bất cứ gì$n$, $Q$ không phải $P_n$ bởi vì họ không đồng ý về $n$. Nhưng$Q$là một công thức logic vì vậy nó phải được liệt kê ...

Chuyện gì vậy?

Answer 1

Điều này sẽ đi xuống phần sau: định nghĩa chính xác của "công thức logic là gì?" Vấn đề là mặc dù$Q$ bạn đã mô tả chắc chắn là "có ý nghĩa", nó phức tạp hơn theo một nghĩa nào đó so với bất kỳ $P_i$S. Khi chúng ta chốt lại một khái niệm chính xác về "công thức logic" và một cách liệt kê như vậy, ví dụ: "công thức bậc nhất trong ngôn ngữ số học" được sắp xếp theo thứ tự từ vựng thông qua một số thứ tự hợp lý trên các ký hiệu liên quan,$Q$ hóa ra sẽ không thể diễn đạt được bằng một công thức theo nghĩa cụ thể đó.

Để có một ví dụ cụ thể về cách điều này diễn ra, hãy xem ví dụ: định lý bất khả phân của Tarski . Và so sánh điều này với "nghịch lý biểu hiện" tương tự: nghịch lý Berry, nghịch lý Richard và nghịch lý Grelling.

Answer 2

Điều quan trọng là phải phân biệt giữa các chuỗi đại diện cho các công thức hợp lệ và chính các công thức đó.

Xem phần sau:

• Nghịch lý của Richard (nghịch lý và lời giải thích)
• Định lý không xác định được của Tarski (không có cách nào để mã hóa chân lý của một chuỗi công thức trong một hệ thống logic nhất quán)
• Định lý tính không đầy đủ của Godel (khả năng chứng minh có thể được mã hóa, nhưng điều đó khác với sự thật)