Problem beim Aufzählen von Formeln

Question

Lassen $P_0, P_1, P_2, ...$ sei eine Aufzählung aller logischen Formeln mit einer freien Variablen $n$(zählbar, da es sich um endliche Zeichenfolgen eines zählbaren Alphabets handelt). Lassen$Q(n) \iff \lnot P_n(n)$. Für jeden$n$, $Q$ ist nicht $P_n$ weil sie sich nicht einig sind $n$. Aber$Q$ist eine logische Formel, also sollte es in der Aufzählung sein ...

Was ist los?

Answer 1

Dies wird auf Folgendes hinauslaufen: Was ist die genaue Definition der "logischen Formel"? Der Punkt ist, dass obwohl die$Q$ Sie haben beschrieben, dass es definitiv "bedeutungsvoll" ist, es ist in gewissem Sinne komplexer als jedes andere $P_i$s. Wenn wir einen genauen Begriff der "logischen Formel" und eine Aufzählung solcher, z. B. "Formel erster Ordnung in der Sprache der Arithmetik", festlegen, die lexikographisch über eine vernünftige Reihenfolge der beteiligten Symbole geordnet ist, wird die entsprechende$Q$ wird sich als nicht durch eine Formel in diesem speziellen Sinne ausdrückbar herausstellen.

Ein konkretes Beispiel dafür finden Sie beispielsweise in Tarskis Undefinierbarkeitssatz . Und vergleichen Sie dies mit ähnlichen "Paradoxien des Ausdrucks": Berrys Paradoxon, Richards Paradoxon und Grellings Paradoxon.

Answer 2

Es ist wichtig, zwischen Zeichenfolgen, die gültige Formeln darstellen, und den Formeln selbst zu unterscheiden.

Siehe folgendes:

• Richards Paradoxon (das Paradoxon und eine Erklärung)
• Tarskis Undefinierbarkeitssatz (es gibt keine Möglichkeit, die Wahrheit einer Formelzeichenfolge in einem konsistenten logischen System zu kodieren)
• Gödels Unvollständigkeitssatz (Beweisbarkeit kann kodiert werden, aber das unterscheidet sich von der Wahrheit)