Bedeutet das Gesetz der ausgeschlossenen Mitte syntaktische Vollständigkeit?

Question

Bedeutet das Gesetz der ausgeschlossenen Mitte syntaktische Vollständigkeit?

Logik
Mathematik
Unvollständigkeit
Nichtklassische Logik

Noldorin

Das Gesetz der ausgeschlossenen Mitte (LEM) besagt dies für jeden Vorschlag $p$ , wir haben $\vdash p \lor \lnot p$ .

Syntaktische Vollständigkeit (auch Negationsvollständigkeit genannt) besagt dies für jeden Satz $p$ , wir haben $\vdash p$ oder $\vdash \lnot p$ .

Soweit mir bekannt ist, impliziert ersteres in der klassischen Aussagenlogik letzteres (wie lässt sich dies am einfachsten begründen?). Dies ist jedoch höchst problematisch, weil es bedeuten würde, dass die kontrapositive LEM falsch ist) die klassische (Peano-)Arithmetik inkonsistent macht – das heißt, LEM kann unmöglich ein gültiges Axiom/eine gültige Regel sein.

Das erscheint mir nach dem, was ich gelesen habe, schlichtweg falsch. Also, wo habe ich meine Argumentation vermasselt? Können wir das eigentlich nicht sagen $\vdash p \lor \lnot p$ impliziert $\vdash p$ oder $\vdash \lnot p$ , zumindest nicht für die klassische Logik? Es scheint intuitiv wahr zu sein, aber da ich Schwierigkeiten habe, es formal zu rechtfertigen, liegt vielleicht hier der Fehler.

Hanul Jeon

Aussagevariable ist weder beweisbar noch widerlegbar, selbst wenn

p \lor \neg p

$p\lor \lnot p$ ist nachweisbar. Sie könnten die Vollständigkeit missverstehen.

Hanul Jeon

Soweit ich weiß, gibt es zwei Vollständigkeiten in der Logik, und sie fallen nicht zusammen. Wenn wir eine Theorie nennen

T

$T$ vollständig ist, jeder Satz (über die Sprache von

T

$T$ ) beweisbar oder widerlegbar ist

T

$T$ . Wenn wir jedoch ein logisches System sagen

L

$\mathcal{L}$ vollständig ist, bedeutet (semantische) Erfüllbarkeit impliziert (synthetische) Beweisbarkeit.

Mauro ALLEGRANZA

Die beiden Begriffe sind unterschiedlich: Die sogenannte semantische Vollständigkeit für zB Aussagenkalkül besagt, dass „wenn

φ

$\varphi$ gilt (also eine Tautologie), dann ist sie beweisbar " . Also

p \lor \neg p

$p \lor \lnot p$ als Tautologie beweisbar ist; Aber

p

$p$ ist keine Tautlogie (für alle

p

$p$ ) und damit nicht beweisbar. Die Verneinungs-Vollständigkeit besagt, dass „für jeden Satz

φ

$\varphi$ , entweder

φ

$\varphi$ oder

\neg φ

$\lnot \varphi$ ist beweisbar". Die Aussagenlogik ist wie die Logik erster Ordnung nicht negationsvollständig.

mmw

Dies ist ein entscheidender Unterschied zwischen Wahrheit und Beweisbarkeit. Ja,

ϕ \lor ψ

$\phi\lor \psi$ ist genau dann wahr, wenn mindestens einer von

ϕ

$\phi$ Und

ψ

$\psi$ ist wahr. Aber das können wir haben

ϕ \lor ψ

$\phi\lor \psi$ beweisbar sein, während keiner von beiden

ϕ

$\phi$ Und

ψ

$\psi$ ist nachweisbar. Dies sollte intuitiv sein: Sie wissen durch reine Logik, dass ich entweder sitze oder nicht sitze, aber Sie wissen weder, dass ich sitze noch dass ich nicht sitze.

mmw

Im dritten Absatz gibt es eine weitere Verwechslung zwischen Wahrheit und Beweisbarkeit. Selbst wenn angenommen wird (was nicht der Fall ist), dass die Ableitbarkeit von LEM Negationsvollständigkeit impliziert, dann würde Negationsunvollständigkeit immer noch nur implizieren, dass LEM nicht ableitbar ist. Aber die Unbeweisbarkeit von

p \lor \neg p

$p\lor \neg p$ bedeutet nicht die Beweisbarkeit von

\neg (p \lor \neg p)

$\neg (p\lor \neg p)$ . Natürlich gibt es gut untersuchte (konsistente!) Systeme, bei denen LEM nicht ableitbar ist.

Noldorin

@tetori: Ich habe mich hier speziell auf die syntaktische (Negations-) Vollständigkeit bezogen. Auf semantische Vollständigkeit kommt es nirgends an. Und tatsächlich gibt es sogar mehr als 2 Begriffe von Vollständigkeit.

Noldorin

@MauroALLEGRANZA: Sicher, ich verstehe das (vielleicht hast du es @tetori erklärt?). Ich bin mir nicht sicher, wo das für die Frage relevant ist.

Noldorin

@mmw Kann LEM halten, aber nicht ableitbar sein?

Noldorin

@mmw Ich glaube auch, ich verstehe, was du mit deinem ersten Punkt meinst. Ich dachte in Begriffen der konstruktiven (zumindest intuitionistischen) Logik, wo diese Aussage über die Beweisbarkeit der Komponenten einer Disjunktion gelten muss . In der klassischen Logik gilt dies jedoch nicht unbedingt! (Ich bin mir aber nicht sicher, wo genau der entscheidende Unterschied liegt.)

Mauro ALLEGRANZA

@Noldorin - Entschuldigung für mein Beharren: die Tatsache, dass

⊢ p \lor \neg p

$\vdash p \lor \lnot p$ aber nicht

⊢ p

$\vdash p$ oder

⊢ \neg p

$\vdash \lnot p$ liegt gerade an der Solidität und Vollständigkeit der klassischen Prop-Logik. Wenn

⊢ p

$\vdash p$ oder

⊢ \neg p

$\vdash \lnot p$ , das bedeutet, dass entweder

p

$p$ oder

\neg p

$\lnot p$ ist eine Tautologie , die nicht ist , wie bereits in der Antwort und den Kommentaren gesagt.

Noldorin

@MauroALLEGRANZA: Ah, danke für die Klarstellung. Wenn

p

$p$ ist aber sicher ein Satz

⊢ p \lor \neg p

$\vdash p \lor \lnot p$ impliziert

⊢ p

$\vdash p$ oder

⊢ \neg p

$\vdash \lnot p$ . (Übrigens sehe ich keine Antwort von Ihnen, nur ein paar Kommentare.)

Noldorin

Ich denke, meine Verwirrung hier kommt von der Verschmelzung von "Sätzen" und "Sätzen" ... Ich bin mir immer noch nicht sicher über den genauen Unterschied, wohlgemerkt.

Mauro ALLEGRANZA

@Noldorin - Nochmal NEIN . Betrachten Sie die Logik erster Ordnung: klar

⊢ \forall x P (x) \lor \neg \forall x P (x)

$\vdash \forall x P(x) \lor \lnot \forall x P(x)$ doch keins

⊢ \forall x P (x)

$\vdash \forall x P(x)$ noch

⊢ \neg \forall x P (x)

$\vdash \lnot \forall x P(x)$ , denn die beiden letzten Sätze sind nicht gültig und somit (wieder der Vollständigkeit halber ) nicht beweisbar.

Noldorin

Wie seltsam! Ich bin so an intuitionistische Logik gewöhnt, wo Sie dies schließen können, kein Problem.

Noldorin

Ich denke, das Obige liegt daran, dieses Problem aus der Perspektive des natürlichen Abzugs zu betrachten, wenn es einen Beweis dafür gibt

A \lor B

$A \lor B$ dann muss ein Nachweis vorliegen

A

$A$ oder ein Nachweis

B

$B$ irgendwo oben. Das ist in der intuitionistischen Logik. Aber mit dem LEM, in der klassischen Logik, denke ich, dass dieses Argument nicht funktioniert, weil

A \lor B

$A \lor B$ über das LEM und nicht direkt abgeleitet werden könnten. Rechts?

Antworten (2)

Bedeutet das Gesetz der ausgeschlossenen Mitte syntaktische Vollständigkeit?

Aussagevariable ist weder beweisbar noch widerlegbar, selbst wenn $p\lor \lnot p$ ist nachweisbar. Sie könnten die Vollständigkeit missverstehen.
Soweit ich weiß, gibt es zwei Vollständigkeiten in der Logik, und sie fallen nicht zusammen. Wenn wir eine Theorie nennen $T$ vollständig ist, jeder Satz (über die Sprache von $T$ ) beweisbar oder widerlegbar ist $T$ . Wenn wir jedoch ein logisches System sagen $\mathcal{L}$ vollständig ist, bedeutet (semantische) Erfüllbarkeit impliziert (synthetische) Beweisbarkeit.
Die beiden Begriffe sind unterschiedlich: Die sogenannte semantische Vollständigkeit für zB Aussagenkalkül besagt, dass „wenn $\varphi$ gilt (also eine Tautologie), dann ist sie beweisbar " . Also $p \lor \lnot p$ als Tautologie beweisbar ist; Aber $p$ ist keine Tautlogie (für alle $p$ ) und damit nicht beweisbar. Die Verneinungs-Vollständigkeit besagt, dass „für jeden Satz $\varphi$ , entweder $\varphi$ oder $\lnot \varphi$ ist beweisbar". Die Aussagenlogik ist wie die Logik erster Ordnung nicht negationsvollständig.
Dies ist ein entscheidender Unterschied zwischen Wahrheit und Beweisbarkeit. Ja, $\phi\lor \psi$ ist genau dann wahr, wenn mindestens einer von $\phi$ Und $\psi$ ist wahr. Aber das können wir haben $\phi\lor \psi$ beweisbar sein, während keiner von beiden $\phi$ Und $\psi$ ist nachweisbar. Dies sollte intuitiv sein: Sie wissen durch reine Logik, dass ich entweder sitze oder nicht sitze, aber Sie wissen weder, dass ich sitze noch dass ich nicht sitze.
Im dritten Absatz gibt es eine weitere Verwechslung zwischen Wahrheit und Beweisbarkeit. Selbst wenn angenommen wird (was nicht der Fall ist), dass die Ableitbarkeit von LEM Negationsvollständigkeit impliziert, dann würde Negationsunvollständigkeit immer noch nur implizieren, dass LEM nicht ableitbar ist. Aber die Unbeweisbarkeit von $p\lor \neg p$ bedeutet nicht die Beweisbarkeit von $\neg (p\lor \neg p)$ . Natürlich gibt es gut untersuchte (konsistente!) Systeme, bei denen LEM nicht ableitbar ist.
@tetori: Ich habe mich hier speziell auf die syntaktische (Negations-) Vollständigkeit bezogen. Auf semantische Vollständigkeit kommt es nirgends an. Und tatsächlich gibt es sogar mehr als 2 Begriffe von Vollständigkeit.
@MauroALLEGRANZA: Sicher, ich verstehe das (vielleicht hast du es @tetori erklärt?). Ich bin mir nicht sicher, wo das für die Frage relevant ist.
@mmw Ich glaube auch, ich verstehe, was du mit deinem ersten Punkt meinst. Ich dachte in Begriffen der konstruktiven (zumindest intuitionistischen) Logik, wo diese Aussage über die Beweisbarkeit der Komponenten einer Disjunktion gelten muss . In der klassischen Logik gilt dies jedoch nicht unbedingt! (Ich bin mir aber nicht sicher, wo genau der entscheidende Unterschied liegt.)
@Noldorin - Entschuldigung für mein Beharren: die Tatsache, dass $\vdash p \lor \lnot p$ aber nicht $\vdash p$ oder $\vdash \lnot p$ liegt gerade an der Solidität und Vollständigkeit der klassischen Prop-Logik. Wenn $\vdash p$ oder $\vdash \lnot p$ , das bedeutet, dass entweder $p$ oder $\lnot p$ ist eine Tautologie , die nicht ist , wie bereits in der Antwort und den Kommentaren gesagt.
@MauroALLEGRANZA: Ah, danke für die Klarstellung. Wenn $p$ ist aber sicher ein Satz $\vdash p \lor \lnot p$ impliziert $\vdash p$ oder $\vdash \lnot p$ . (Übrigens sehe ich keine Antwort von Ihnen, nur ein paar Kommentare.)
Ich denke, meine Verwirrung hier kommt von der Verschmelzung von "Sätzen" und "Sätzen" ... Ich bin mir immer noch nicht sicher über den genauen Unterschied, wohlgemerkt.
@Noldorin - Nochmal NEIN . Betrachten Sie die Logik erster Ordnung: klar $\vdash \forall x P(x) \lor \lnot \forall x P(x)$ doch keins $\vdash \forall x P(x)$ noch $\vdash \lnot \forall x P(x)$ , denn die beiden letzten Sätze sind nicht gültig und somit (wieder der Vollständigkeit halber ) nicht beweisbar.
Wie seltsam! Ich bin so an intuitionistische Logik gewöhnt, wo Sie dies schließen können, kein Problem.
Ich denke, das Obige liegt daran, dieses Problem aus der Perspektive des natürlichen Abzugs zu betrachten, wenn es einen Beweis dafür gibt $A \lor B$ dann muss ein Nachweis vorliegen $A$ oder ein Nachweis $B$ irgendwo oben. Das ist in der intuitionistischen Logik. Aber mit dem LEM, in der klassischen Logik, denke ich, dass dieses Argument nicht funktioniert, weil $A \lor B$ über das LEM und nicht direkt abgeleitet werden könnten. Rechts?

Benutzer21820 · Answer 1

Ich nehme an, Sie kennen die Antwort auf Ihre eigene Frage inzwischen bereits, aber der Vollständigkeit halber ...

Der entscheidende Punkt ist, dass syntaktische Vollständigkeit eine Eigenschaft eines formalen Systems ist $S$ vom Metasystem aus gesehen . Nur weil $S \vdash p \lor \neg p$ bedeutet das nicht $S \vdash p$ oder $S \vdash \neg p$ . Das Vorherige " $\lor$ " ist ein Symbol in der Sprache des formalen Systems, während letzteres "oder" ein Teil der Sprache des Metasystems ist. Sie fallen nämlich nur semantisch zusammen $M \vDash p \lor \neg p$ iff $M \vDash p$ oder $M \vDash \neg p$ Wenn $M$ ist eine Struktur und $p$ ist ein Satz vorbei $M$ . Aber wenn es verschiedene Modelle von $S$ die sich in einem Satz nicht einig sind $p$ , Und $S$ ist Sound, dann unbedingt $S$ kann nicht beweisen $p$ und kann es nicht beweisen $\neg p$ , seit was auch immer $S$ beweist muss für jedes Modell von wahr sein $S$ .

Ja, aber trotzdem danke für die Klarstellung. Wie ich es verstehe, $\vdash p \lor \neg p$ impliziert $\vdash p$ oder $\vdash \neg p$ für ein gegebenes $p$ , in jedem System konstruktiver Logik.
@Noldorin: Es ist nicht nur für konstruktive Logik. Es ist für jedes formale System, das PA interpretieren kann $^-$ , einschließlich starker klassischer Mengentheorien wie ZFC oder starker Typtheorien wie MLTT oder schwacher arithmetischer Theorien wie Q. Aber wenn ich mich nicht irre, erfüllt die intuitionistische Logik erster Ordnung dies $\vdash p \lor \neg p$ iff $\vdash p$ oder $\vdash \neg p$ , denn die einzige Möglichkeit, eine Disjunktion abzuleiten, ist die Einführungsregel, da die intuitionistische Logik die Eliminierung doppelter Negationen oder LEM verbietet und das Explosionsprinzip nur unter unmöglichen (nicht beweisbaren) Annahmen angewendet werden kann.
@Noldorin: Ich habe plato.stanford.edu/entries/logic-intuitionistic überprüft und meine Behauptung ist korrekt; Suchen Sie nach "(DP)" für die Disjunktionseigenschaft der intuitionistischen Logik. =)
Ich verstehe. Was ist $PA^-$ , eine Variante der Peano-Arithmetik? Ich nehme an, obwohl Sie ZFC sagen, muss es immer noch in einem konstruktiven Umfeld sein, sonst würde es dem widersprechen, was Sie und andere oben gesagt haben. :)
@ Noldorin: PA $^-$ ist hier beschrieben . Und nein, ZFC ist vollständig ZFC, aber ich habe Ihren Kommentar falsch verstanden, da "nicht impliziert". Haha! Ich habe also tatsächlich gesagt, dass jedes formale System, das die klassische Arithmetik interpretieren kann, die Disjunktionseigenschaft nicht erfüllt. Danke, dass du meinen Lesefehler aufgefangen hast!
Danke, @user21820 Ich bin wieder im Chat. Ich werde meine früheren Kommentare hier löschen und später darauf zurückkommen, um auch diesen zu löschen.

Andre Nicolas · Answer 2

Es gibt viele Sätze der klassischen Aussagenlogik, die weder beweisbar noch widerlegbar sind. Das einfachste ist $p$ , Wo $p$ ist ein Angebotsschreiben.

Das ist kein Satz, da es eine freie Variable hat. Es ist eine offene Formel.

Bedeutet das Gesetz der ausgeschlossenen Mitte syntaktische Vollständigkeit?

Noldorin

Hanul Jeon

Hanul Jeon

Mauro ALLEGRANZA

mmw

mmw

Noldorin

Noldorin

Noldorin

Noldorin

Mauro ALLEGRANZA

Noldorin

Noldorin

Mauro ALLEGRANZA

Noldorin

Noldorin

Antworten (2)

Benutzer21820

Noldorin

Benutzer21820

Benutzer21820

Noldorin

Benutzer21820

Noldorin

Noldorin

binWarum

Andre Nicolas

Noldorin

Relative Stärke und propositionale Ununterscheidbarkeit von nicht-distributiven Verbänden

Warum wird akzeptiert, dass Gödel in seinen Unvollständigkeitssätzen eine selbstreferenzielle Aussage verwendet?

Kann ZFC die Zahlentheorie entscheiden?

Was versucht der Autor hier zu erklären?

Kann ZFC eine Wahrheitstheorie für die Arithmetik liefern und die arithmetische Wahrheit ausdrücken?

Entscheidbarkeit der Riemann-Hypothese vs. der Goldbach-Vermutung

Woher wissen wir, dass wir nicht versehentlich von Nicht-Standard-Ganzzahlen sprechen?

Semantik für minimale Logik

Entscheidbarkeit und „Wahrheitswert“

Ist dies ein Beispiel für die Unvollständigkeit der PA erster Ordnung?