Ist das Gegenteil einer wahren Aussage immer beweisbar?

Nov 21 2020

Es fiel mir sehr schwer, das Gegenteil einer einfachen Aussage der Elementarzahlentheorie zu beweisen, und je mehr ich darüber nachdenke, desto mehr glaube ich, dass es auf diese Weise unter Verwendung von Beweisverfahren (die wir als gültig akzeptieren) möglicherweise nicht nachweisbar ist. Ich weiß, dass es wahre Aussagen gibt, die nicht beweisbar sind, aber ich bin mir nicht sicher, wie sehr sie damit zusammenhängen. Ich habe von etwas über Modelle gehört oder ein Modell der Zahlentheorie gesagt: NT. Gibt es Verallgemeinerungen von Arten wahrer Aussagen, die wir in der Zahlentheorie auf bestimmte Weise beweisen können, auf andere jedoch nicht?

Antworten

2 Z.A.K. Nov 21 2020 at 10:59

Wie andere in den Kommentaren bemerkt haben, öffnet die Verwendung des Adjektivs true eine Dose Würmer: Wahrheit hat eine technische Definition in der Semantik und kollidiert mit ziemlicher Sicherheit mit der Frage, die Sie stellen möchten. Insbesondere müssen wahre Dinge nicht beweisbar sein, Punkt.

Lassen Sie mich stattdessen eine beweistheoretische Frage stellen, die (glaube ich) der Frage nahe kommt, die Sie stellen möchten:

Ich habe es geschafft, eine Implikation zu beweisen $A \rightarrow B$, aber ich konnte es nur tun, indem ich das Kontrapositiv nahm $\neg B \rightarrow \neg A$und das zu beweisen. Kann ich in einer solchen Situation immer einen direkteren Beweis dafür finden?$A \rightarrow B$ das beinhaltet nicht die Einnahme von Kontrapositiven?

Basierend auf Ihrer Frage sagt Ihnen Ihr Bauchgefühl, dass dies nicht der Fall sein muss, und Ihr Bauchgefühl ist korrekt. Manchmal müssen Sie für jeden Beweis einer Aussage Kontrapositive einnehmen.

Bevor ich erkläre, warum, muss ich einige Dinge in Bezug auf die beweistheoretische Terminologie erklären. Um Beweise genau zu untersuchen, müssen wir zuerst definieren, was wir unter Beweis verstehen. Es gibt eine Vielzahl solcher Definitionen, sogenannte Beweissysteme (deduktive Systeme).

Einige Beweissysteme definieren obskure oder extrem eingeschränkte Argumentationsformen, wie z. B. pädagogisches Denken, bei denen Sie explizite Beispiele nennen müssen, bevor Sie abstrakte Konzepte einführen. oder ethisches Denken, bei dem Sie zwischen zulässigen und verbotenen Aussagen unterscheiden müssen. Unterschiedliche Beweissysteme können unterschiedliche Theoreme beweisen. Aber auch zwei Beweissysteme, die dieselben Sätze beweisen, können sich erheblich voneinander unterscheiden: Ein Satz kann mehrere Beweise in einem System haben, aber nur einen Beweis in einem anderen System. Beweistheoretiker können bei Bedarf neue deduktive Systeme entwickeln , ähnlich wie ein Gruppentheoretiker neue Gruppen aufbauen würde, um technische Situationen zu veranschaulichen oder (Gegen-) Beispiele für mathematische Vermutungen und Fragen zu liefern.

Angesichts dieser Unterschiede sollte klar sein, dass wir im Voraus ein Beweissystem reparieren müssen, um etwas Sinnvolles zu sagen. Von nun an werde ich mich auf ein bestimmtes Beweissystem konzentrieren: den natürlichen Abzug von Gentzen und Prawitz. Der natürliche Abzug liefert ein strenges Substrat für die Art von Beweis, an der Sie wahrscheinlich interessiert sind: mathematische Beweise, wie sie in einem gewöhnlichen Mathematiklehrbuch oder Zeitschriftenartikel akzeptiert würden.

II. Eine gründliche Einführung in die natürliche Deduktion zu schreiben, geschweige denn eine, die in eine Math.SE-Antwort passt, ist eine erhebliche Herausforderung, so sehr, dass ich es nicht einmal versuchen werde. Wenn Sie mathematische Beweise lesen und schreiben können, sind Sie in der Lage, natürliche Ableitungen zu verstehen. Möglicherweise können Sie anhand der folgenden Informationen lernen, wie es funktioniert. Wenn Sie jedoch alle Regeln kennenlernen und besser verstehen möchten, gibt es viele Tutorials, YouTube-Videos und unzählige Lehrbücher zu diesem Thema. Ich persönlich empfehle die ersten drei Kapitel von Jan von Platons Elementen des logischen Denkens .

Natürliche Deduktion hat viele Inferenzregeln, die alle dem arbeitenden Mathematiker vertraut sind. Diese Inferenzregeln zeigen Ihnen, wie Sie aus vorhandenen Beweisen neue Beweise erstellen. Jeder Konnektiv (Konjunktion$\wedge$, Disjunktion $\vee$, Implikation $\rightarrow$, Verneinung $\neg$) und Quantifizierer (universell $\forall$existenziell $\exists$) ist mit einer oder mehreren sogenannten Einführungsregeln und einer Eliminierungsregel ausgestattet. Beispiele:

Wenn Sie einen Beweis haben $A$ und du hast einen Beweis von $A \rightarrow B$, dann haben Sie es geschafft, das zu beweisen $B$ gilt (Implikationseliminierung).
Wenn Sie einen Beweis dafür haben $A \wedge B$ (($A$ und $B$) hält, dann haben Sie es geschafft, das zu beweisen $B$ gilt (Konjunktionseliminierung, rechts).
Wenn Sie einen Beweis dafür haben $A \wedge B$ hält, dann haben Sie es geschafft, das zu beweisen $A$ gilt (Konjunktionseliminierung, links).
Wenn Sie einen Beweis dafür haben $A$ gilt, und Sie haben einen Beweis dafür $B$ hält, dann haben Sie es geschafft, das zu beweisen $A \wedge B$ gilt (Konjunktion Einführung).
Wenn Sie einen Beweis haben, der mit "Angenommen $A$... "und endet mit" ... also $B$", dann haben Sie es geschafft, die bedingte Aussage zu beweisen $A \rightarrow B$ (Implikationseinführung).
Wenn Sie einen Beweis haben, der mit "Angenommen $A$... "und endet mit" was ein Widerspruch ist ", dann haben Sie es geschafft, die Negation zu beweisen $\neg A$ (Negation Einführung).
usw...

Über diese gewöhnlichen Regeln hinaus gibt es drei spezielle Regeln:

Wenn Sie einen Beweis dafür haben $\neg\neg A$ hält, dann haben Sie es geschafft, das zu beweisen $A$ gilt (Double Negation Elimination).
Sie haben immer einen Beweis dafür $A \vee \neg A$ (Gesetz der ausgeschlossenen Mitte).
Wenn Sie einen Beweis dafür haben $\neg B \rightarrow \neg A$, dann haben Sie es geschafft, das zu beweisen $A \rightarrow B$ (kontrapositiver Beweis).

Wenn Sie eine dieser Regeln zu den normalen Regeln des natürlichen Abzugs hinzufügen , können Sie die beiden anderen beweisen. Wenn Sie beispielsweise das Gesetz der ausgeschlossenen Mitte als Inferenzregel hinzufügen, können Sie jeden Fall der Eliminierung der doppelten Negation nachweisen. Am wichtigsten für uns ist, dass Sie den kontrapositiven Beweis verwenden können, um jeden Fall der Eliminierung der doppelten Negation zu beweisen. Wir können diesen Hilfsbeweis verwenden:

Nehme an, dass $\neg A$ hält.
Nehme an, dass $\neg\neg A$ hält.
Von 1 und 2 haben wir einen Widerspruch.
Von 2-3 haben wir $\neg\neg\neg A$ durch Negation Einführung.
Von 1-4 haben wir $\neg A \rightarrow \neg\neg\neg A$ durch implizite Einführung.
Ab 5 haben wir $\neg\neg A \rightarrow A$ durch kontrapositiv.

Stellen Sie sich vor, wir haben einen Beweis dafür $\neg\neg A$. Unser Hilfsbeweis gibt uns$\neg\neg A \rightarrow A$Die Implikationseliminierung gibt uns also einen Beweis dafür $A$. Wie ich bereits behauptet habe, können Sie den Beweis durch kontrapositive Inferenzregel zusammen mit den gewöhnlichen Regeln verwenden, um jeden Fall der Eliminierung der doppelten Negation zu beweisen.

Das natürliche Abzugssicherungssystem, das alle gewöhnlichen Einführungs- und Eliminierungsregeln, aber keine der drei Sonderregeln enthält, wird als intuitionistische oder konstruktive natürliche Ableitung bezeichnet. Wir nennen das System manchmal auch eine der Sonderregeln (meistens die Eliminierung der doppelten Negation aus technischen Gründen). Klassische natürliche Deduktion. Es ist eine bekannte Tatsache, dass$\neg\neg A \rightarrow A$ist in Intuitionistic Natural Deduction nicht nachweisbar. Also im wahrsten Sinne des Wortes,$\neg\neg A \rightarrow A$ ist nicht nachweisbar, ohne Kontrapositive oder eine der beiden anderen gleichwertigen Folgerungsregeln zu verwenden.

III. Wenn Sie die Axiome der Elementarzahlentheorie in ein Intuitionistic Natural Deduction-Beweissystem einfügen, erhalten Sie eine mathematische Theorie namens Heyting Arithmetic . Denken Sie daran: Nur weil ein allgemeines logisches Prinzip ohne Einnahme von Kontrapositiven nicht nachweisbar ist, folgt daraus nicht, dass keine Instanz ohne Einnahme von Kontrapositiven nachweisbar ist! ZB beweist Heyting Arithmetik$\neg\neg t = 0 \rightarrow t = 0$ für eine beliebige Anzahl $t$.

Die Heyting-Arithmetik unterscheidet sich jedoch in vielerlei Hinsicht von der üblichen (Peano) Elementararithmetik. Insbesondere beweist Heyting Arithmetic nicht Folgendes:

Für jedes Polynom $P$ Bei ganzzahligen Koeffizienten gibt es ganze Zahlen $n$ so dass für alle $x$, $|P(n)| \leq |P(x)|$. [2]

Dies gibt eine Antwort auf eine der schwächeren Formulierungen Ihrer Frage: Jeder Beweis des obigen Theorems erfordert, dass Sie irgendwo in seinem Beweis Kontrapositive (oder ein gleichwertiges Prinzip) verwenden .

Ich werde nicht auf Details eingehen, aber ein beweistheoretisches Ergebnis von De Jongh [1] ermöglicht es uns, eine stärkere Formulierung zu beantworten: Wir können auch explizite zahlentheoretische Aussagen erhalten $A,B$ so dass die Heyting-Arithmetik die Implikation beweist $\neg B \rightarrow \neg A$, aber nicht die Implikation $A \rightarrow B$.

Sie könnten eine noch stärkere Frage stellen: Finden Sie explizite zahlentheoretische Aussagen $A,B$ so dass jeder (ausreichend normalisierte) Beweis von $A \rightarrow B$ enthält einen Beweis von $\neg B \rightarrow \neg A$selbst als Subproof. Viel Glück damit: es klingt sehr sehr schwierig :)

[1] De Jongh, DHJ: Die Maximalität des intuitionistischen Prädikatenkalküls in Bezug auf Heytings Arithmetik tech. rep., Treffen der Vereinigung für symbolische Logik, Manchester UK, 1969