Was ist die Intuition hinter der Verwendung des Gesetzes der ausgeschlossenen Mitte in der natürlichen Deduktion?

Das Gesetz der ausgeschlossenen Mitte ähnelt einer Fallanalyse (z. B. bei einer alternierenden Reihe die Fälle gerade, ungerade). In diesem Fall ist die Intuition hinter dem Gesetz des ausgeschlossenen Dritten, dass einer der Fälle trivial ist: ¬φ ⊢ ∃x. (φ → ψ)

Wie üblich ist jeder der Fälle einfacher als die ursprüngliche Frage. Dies gilt insbesondere hier: Da der obige Fall trivial ist, bleibt nur der andere Fall zu zeigen, so dass Sie insgesamt eine Hypothese (dh φ) kostenlos erhalten, die Sie in Ihrer Schlussfolgerung verwenden können.

Gemäß der obigen Antwort von @Sudix ist die Intuition hinter der Verwendung des Gesetzes der ausgeschlossenen Mitte im Beweis von:

$(φ → ∃x ψ) ⊢ ∃x (φ → ψ)$

ist eine "Fallanalyse" anzuwenden.

(i) Angenommen, das$φ$gilt nicht, dh annehmen$¬φ$.

Das bedeutet (durch die Wahrheitstabelle für den Konditional ) dass$φ → ψ$ist WAHR und damit auch$∃x (φ → ψ)$ist wahr.

(ii) Nehmen Sie nun an, dass$φ$gilt, dh annehmen$φ$.

Wir wissen, dass die Prämisse$(φ → ∃x ψ)$gilt, und das bedeutet (wiederum durch die Wahrheitstabelle für den Konditional ) dass auch$∃x ψ$ist WAHR, dh das$ψ$ist für einige WAHR$x$.

Daher,$φ → ψ$ist für einige WAHR$x$, dh$∃x (φ → ψ)$ist wahr.

Ich würde es nicht so sehr einen „Trick“ nennen, sondern eher eine gute „Strategie“, und mit der Zeit, wenn Sie immer mehr dieser Beweise machen, werden Sie anfangen, die Zeiten zu erkennen, in denen Sie das Gesetz von anwenden Ausgeschlossene Mitte wäre gut zu verwenden ... und auf welche Aussage zu verwenden.

Ich möchte auch darauf hinweisen, dass, nur weil ein Beweis mit dem Gesetz des ausgeschlossenen Dritten funktioniert, das nicht bedeutet, dass Sie das Gesetz des ausgeschlossenen Dritten brauchen . Mit anderen Worten, Sie sollten nicht das Gefühl haben, dass Sie den Beweis nicht vervollständigen könnten, wenn Sie nicht daran gedacht hätten, Excluded Middle zu verwenden.

Tatsächlich können Sie in diesem Fall auch einen Widerspruchsbeweis durchführen:

Für eine Anschauung könnte man sich ein Beispiel oder Modell des Gesetzes vom ausgeschlossenen Dritten vorstellen , zB die Menge aller Teilmengen$P(X)$eines Satzes$X$wenn es um a geht$\phi$der Satz$P_\phi:=\{x\in X | \phi(x) \}$aller Elemente$x$In$X$wofür$\phi(x)$ist wahr und interpretierend$\neg \phi$als Ergänzung$(P_\phi)^c:=\{x\in X|x\not\in P_\phi\}$, darüber hinaus$\land$wird interpretiert als$\cap$Und$\lor$als$\cup$(Dies ist auch das Standardbeispiel einer Booleschen Algebra ).

Diese Struktur gehorcht dem Gesetz des ausgeschlossenen Dritten , weil in dieser Struktur für alle$A\in P(X)$das hält es$X=A\cup A^c$, also irgendein Element$x\in X$ist entweder drin$A$oder es ist in der Ergänzung$A^c$.

Übrigens gehorcht nicht jede Struktur dem Gesetz des ausgeschlossenen Dritten, zB ist eine Heyting-Algebra im Allgemeinen kein Modell des Gesetzes des ausgeschlossenen Dritten. Ein Standardbeispiel einer Heyting-Algebra ist zB die Menge der offenen Teilmengen eines topologischen Raums (mit$\neg$interpretiert als innerer Teil des Komplements ).