Problem z wyliczeniem formuł

Question

Pozwolić $P_0, P_1, P_2, ...$ być wyliczeniem wszystkich formuł logicznych z jedną wolną zmienną $n$(policzalne, ponieważ są skończonymi ciągami policzalnego alfabetu). Pozwolić$Q(n) \iff \lnot P_n(n)$. Dla każdego$n$, $Q$ nie jest $P_n$ ponieważ się nie zgadzają $n$. Ale$Q$jest logiczną formułą, więc powinno być w wyliczeniu ...

Co się dzieje?

Answer 1

Sprowadza się to do tego, co następuje: jaka jest dokładna definicja „formuły logicznej”? Chodzi o to, że chociaż$Q$ który opisałeś jest zdecydowanie „znaczący”, jest w pewnym sensie bardziej złożony niż którykolwiek z elementów $P_i$s. Kiedy ustalimy precyzyjne pojęcie „formuły logicznej” i wyliczimy taką, np. „Formułę pierwszego rzędu w języku arytmetyki”, uporządkowaną leksykograficznie za pomocą jakiegoś rozsądnego uporządkowania na odpowiednich symbolach, odpowiadające$Q$ okaże się nie dające się wyrazić formułą w tym szczególnym sensie.

Konkretny przykład tego, jak to się rozgrywa, można znaleźć np. W twierdzeniu Tarskiego o nieokreśloności . Porównaj to z podobnymi „paradoksami ekspresji”: paradoksem Berry'ego, paradoksem Richarda i paradoksem Grellinga.

Answer 2

Ważne jest, aby odróżniać ciągi reprezentujące prawidłowe formuły od samych formuł.

Zobacz następujące:

• Paradoks Richarda (paradoks i wyjaśnienie)
• Twierdzenie Tarskiego o nieokreślalności (nie ma sposobu, aby zakodować prawdziwość ciągu formuły w spójnym systemie logicznym)
• Twierdzenie Godla o niezupełności (można udowodnić , ale to różni się od prawdy)