Lässt sich jeder Widerspruchsbeweis auch widerspruchsfrei zeigen?

Um zu bestimmen, was durch Widerspruch bewiesen werden kann und was nicht , müssen wir einen Beweisbegriff formalisieren. Als Notation lassen wir$\bot$einen identisch falschen Satz darstellen. Dann$\lnot A$, die Negation von$A$, ist äquivalent zu$A \to \bot$, und wir nehmen letzteres als Definition des ersteren in Bezug auf$\bot$.

Es gibt zwei logische Schlüsselprinzipien, die verschiedene Teile dessen ausdrücken, was wir "Beweis durch Widerspruch" nennen:

1. Das Prinzip der Explosion : für jede Aussage$A$, wir können nehmen "$\bot$impliziert$A$" als Axiom. Dies wird auch ex falso quodlibet genannt .

2. Das Gesetz des ausgeschlossenen Dritten : für jede Aussage$A$, wir können nehmen "$A$oder$\lnot A$“ als Axiom.

In der Beweistheorie gibt es drei bekannte Systeme:

• Die minimale Logik hat keines der beiden oben genannten Prinzipien, aber sie hat grundlegende Beweisregeln für die Manipulation logischer Verknüpfungen (außer Negationen) und Quantoren. Dieses System entspricht am ehesten dem "direkten Beweis", da es uns nicht erlaubt, eine Negation für irgendeinen Zweck einzusetzen.

• Die intuitionistische Logik umfasst die Minimallogik und das Explosionsprinzip

• Die klassische Logik umfasst die intuitionistische Logik und das Gesetz der ausgeschlossenen Mitte

Es ist bekannt, dass es Aussagen gibt, die in der intuitionistischen Logik beweisbar sind, aber nicht in der minimalen Logik, und es gibt Aussagen, die in der klassischen Logik beweisbar sind, die in der intuitionistischen Logik nicht beweisbar sind. In diesem Sinne erlaubt uns das Explosionsprinzip, Dinge zu beweisen, die ohne es nicht beweisbar wären, und das Gesetz des ausgeschlossenen Dritten erlaubt uns, Dinge zu beweisen, die wir selbst mit dem Explosionsprinzip nicht beweisen könnten. Es gibt also Aussagen, die durch Widerspruch beweisbar sind, die nicht direkt beweisbar sind.

Das Schema „Wenn$A$impliziert dann einen Widerspruch$\lnot A$gelten muss" gilt sogar in der intuitionistischen Logik, weil$\lnot A$ist nur eine Abkürzung für$A \to \bot$, und dieses Schema sagt nur "wenn$A \to \bot$Dann$A \to \bot$". Aber in der intuitionistischen Logik, wenn wir beweisen$\lnot A \to \bot$, das zeigt das nur$\lnot \lnot A$hält. Die zusätzliche Stärke der klassischen Logik besteht darin, dass das Gesetz der ausgeschlossenen Mitte dies zeigt$\lnot \lnot A$impliziert$A$, was bedeutet, dass in der klassischen Logik, wenn wir beweisen können$\lnot A$einen Widerspruch impliziert, dann wissen wir das$A$hält. Mit anderen Worten: Selbst in der intuitionistischen Logik ist die Negation der Aussage wahr, wenn eine Aussage einen Widerspruch impliziert, aber in der klassischen Logik gilt auch, dass die ursprüngliche Aussage wahr ist, wenn die Negation einer Aussage einen Widerspruch impliziert Letzteres ist in der intuitionistischen Logik nicht beweisbar und insbesondere nicht direkt beweisbar.

Wenn eine Aussage „nicht$X$„Dann ist es vollkommen in Ordnung, davon auszugehen$X$, kommen zu einem Widerspruch und schließen „nicht$X$". In vielen Fällen wird jedoch ein Widerspruchsbeweis vorgelegt, während er wirklich nicht verwendet (geschweige denn notwendig) ist. Die Begründung lautet dann wie folgt:

Beweis für$X$: Vermutlich nicht$X$. Dann ... vollständiger Beweis von$X$folgt hier ... Das ist ein Widerspruch und daher$X$.

Ein berühmtes Beispiel ist Euklids Beweis der Unendlichkeit der Primzahlen. Es wird oft wie folgt formuliert (übrigens nicht von Euklid):

Angenommen, es gibt nur endlich viele Primzahlen. Dann ... folgt die Konstruktion neuer Primzahlen ... Dies ist ein Widerspruch, also gibt es unendlich viele Primzahlen.

Ohne den Widerspruchsteil würden Sie mit einem vollkommen feinen Argument zurückbleiben. Aus einer endlichen Menge von Primzahlen kann nämlich eine neue Primzahl konstruiert werden.

Diese Art der Präsentation ist wirklich etwas, das Sie vermeiden sollten. Sobald Sie sich dieses Musters bewusst sind, ist es erstaunlich, wie oft Sie ihm begegnen werden, einschließlich hier auf math.se.

Es hängt etwas davon ab, ob Sie Intuitionist sind oder nicht (oder beides? oder keines von beiden? Wer weiß schon ohne das Gesetz des ausgeschlossenen Dritten ). Laut dem Wikipedia-Artikel akzeptieren sogar Intuitionisten einige Versionen dessen, was man indirekten Beweis nennen könnte, lehnen die meisten jedoch ab. Insofern wäre ein direkter Beweis vorzuziehen (und oft sogar etwas eleganter).

Ein Beispiel:

Satz. Es gibt irrationale Zahlen$a,b$so dass$a^b$ist rational.

Beweis: Angenommen$a,b\notin \mathbb Q$immer impliziert$a^b\notin \mathbb Q$. Dann$u:=\sqrt 2^{\sqrt 2}\notin \mathbb Q$Und$u^\sqrt 2=\sqrt 2^{\sqrt 2\cdot\sqrt 2}=\sqrt 2^2=2\notin \mathbb Q$- Widerspruch!

Tatsächlich würde sich ein Intuitionist darüber beschweren, dass wir kein Paar zeigen$(a,b)$mit$a,b\notin \mathbb Q$Und$a^b\in \mathbb Q$. Stattdessen zeigen wir das auch nur$(\sqrt 2,\sqrt 2)$oder$(u,\sqrt 2)$ist so ein paar. Um den oben gegebenen Beweis in einen direkten und konstruktiven Beweis umzuwandeln, müssten Sie tatsächlich eine der beiden möglichen Optionen beweisen$u\in \mathbb Q$oder$u\notin\mathbb Q$.

Siehe diesen Beitrag: Sind Beweise durch Widerspruch schwächer als andere Beweise? .
Es gibt einige wunderbare Antworten auf Ihre Frage - und sprechen direkt Ihr "Nebenbei" an: Sehen Sie insbesondere, was JDH schreibt.

Einer der Vorteile beim Konstruieren direkter Beweise für Aussagen, wenn dies machbar ist, besteht darin, dass man während des Prozesses andere nützliche Aussagen entdecken kann. Das heißt, direkte Beweise helfen, die notwendigen und hinreichenden Bedingungen zu klären, die ein Theorem wahr machen, und liefern eine Struktur, die zeigt, wie diese Bedingungen zusammenhängen und wie die Kette von Implikationen die Schlussfolgerung impliziert.

Indirekte Beweise hingegen (auch als „Widerspruchsbeweise“ bekannt) sagen uns nur, dass die Annahme eines anderen Satzes irgendwann zu einem Widerspruch führt. Aber ein solcher Beweis liefert nicht wirklich die Art von Einsicht, die aus direkten Beweisen gewonnen werden kann.

Das soll nicht heißen, dass indirekte Beweise nicht ihren Platz haben (z. B. sind sie praktisch, wenn Sie aufgefordert werden, Aussagen während einer zeitlich begrenzten Prüfung zu beweisen!). Sie helfen oft dabei, bestimmte Aussagen auf der Grundlage „auszuschließen“, dass sie gut etablierten Axiomen oder Theoremen widersprechen. Außerdem sind indirekte Beweise manchmal intuitiver als direkte Beweise. Das zum Beispiel beweisen$\sqrt{2}$ist nicht rational, einen Widerspruchsbeweis zu verwenden, ist sauber und intuitiv.

Manchmal taucht zuerst ein indirekter Beweis auf, wonach man versuchen kann, mit dem Versuch fortzufahren, einen direkten Beweis zu konstruieren, um denselben Satz zu beweisen. Das heißt, das Bereitstellen eines indirekten Beweises eines Satzes motiviert oft die Konstruktion direkter Beweise.

Bearbeiten:

Ich habe diesen Blogeintrag gefunden (Gowers's Weblog) Wann ist ein Widerspruchsbeweis notwendig ? woraus ich eine einleitende Bemerkung zitiere:

Es scheint möglich zu sein, Theoreme in drei Typen zu unterteilen: solche, bei denen es lächerlich wäre, einen Widerspruch zu verwenden, solche, bei denen es gleichermaßen sinnvolle Beweise gibt, die einen Widerspruch verwenden oder nicht verwenden, und solche, bei denen ein Widerspruch erzwungen erscheint. Aber was ordnet ein Theorem in eine dieser drei Kategorien ein?

Der Post folgt gleich mit einer netten Antwort von Terence Tao.

Ein paar Punkte aus meiner (begrenzten) Erfahrung:

• Ich liebe den Beweis durch Widerspruch und ich habe ihn in Kursen für Hochschulabsolventen verwendet, und niemand schien etwas dagegen zu haben, solange die Logik unfehlbar war.
• Für mich ist es viel einfacher, über eine Aussage im Sinne von „Was wäre, wenn das nicht wahr wäre?“ nachzudenken. Das ist normalerweise mein erster Instinkt, das macht den Beweis durch Widerspruch zur natürlichen ersten Wahl. Zum Beispiel, wenn ich gebeten würde, etwas zu beweisen wie "Beweisen Sie, dass eine nicht-singuläre Matrix eine eindeutige Inverse hat". Mein erster Instinkt wäre: "Was wäre, wenn eine nicht-singuläre Matrix 2 Inverse hätte?" und von da an folgt der Beweis sauber.
• Manchmal kommen Widersprüche jedoch nicht sauber und ein Beweis durch einfache logische Schlussfolgerungen würde wahrscheinlich 5 Zeilen dauern, während ein Widerspruch Millionen braucht. Ich könnte Sie auf bestimmte Beweise hinweisen, aber ich muss etwas graben. Wenn Sie sich jeden Beweis ansehen und versuchen, Beweis durch Widerspruch zu verwenden, werden Sie außerdem mit dem Problem konfrontiert, dass Sie manchmal Ihren beabsichtigten Widerspruch angeben, ihn aber nie verwenden. Mit anderen Worten, lösen Sie mit direktem Beweis.
• Ein weiterer Aspekt von Beweis durch Widerspruch (IMHO) ist, dass Sie wirklich alle Definitionen und ihre äquivalenten Aussagen ziemlich gut kennen müssen, um einen schönen Widerspruch zu finden. Andernfalls werden Sie am Ende mehrere Lemmas auf dem Weg beweisen, was in einem direkten Beweis sauber aussieht, aber nicht so sehr in einem Beweis durch Widerspruch, aber auch dies könnte eine persönliche Entscheidung sein.

Zusammenfassend lässt sich sagen, wenn Sie es einfacher finden, in Begriffen von „Was wäre, wenn nicht“ zu denken, dann machen Sie weiter, verwenden Sie es, aber stellen Sie sicher, dass Ihre Beweisfähigkeiten mit anderen Strategien genauso gut sind, weil$\exists$Nagel, den Sie nicht mit dem PbC-Hammer treffen können, den Sie tragen werden.

Was ist ein Widerspruchsbeweis? Das ist eigentlich ziemlich schwierig zufriedenstellend zu beantworten, aber normalerweise meinen die Leute so etwas: eine Aussage gegeben$\phi$, ein Beweis dafür$\phi$durch Widerspruch ist eine Ableitung eines Widerspruchs aus der Annahme$\lnot \phi$. Um dies zu analysieren, ist es sehr wichtig, zwischen der Aussage zu unterscheiden$\phi$und die Aussage$\lnot \lnot \phi$; die beiden Aussagen sind formal verschieden (was an der unterschiedlichen Schreibweise zu erkennen ist!), obwohl sie in der klassischen Logik immer den gleichen Wahrheitswert haben.

Lassen$\bot$Widerspruch bezeichnen. Wenn wir einen Widerspruch unter der Annahme zeigen$\lnot \phi$, was wir haben, ist ein bedingter Beweis von$\bot$aus$\lnot \phi$. Dies kann dann in einen Beweis der Aussage umgewandelt werden$\lnot \phi \to \bot$, das ist die Langform von$\lnot \lnot \phi$– mit anderen Worten, wir haben einen Beweis dafür, dass „es nicht der Fall ist$\lnot \phi$". Dies ist streng genommen kein vollständiger Beweis für$\phi$: Wir müssen noch den letzten Schritt aufschreiben$\phi$aus$\lnot \lnot \phi$. Dies ist der Streitpunkt zwischen Konstruktivisten und Nicht-Konstruktivisten: Bei der konstruktiven Interpretation von Logik$\lnot \lnot \phi$unterscheidet sich nicht nur formal von$\phi$aber auch semantisch verschieden; insbesondere lehnen Konstruktivisten das Prinzip ab$\phi$daraus abgeleitet werden kann$\lnot \lnot \phi$(obwohl sie einige begrenzte Fälle dieser Regel akzeptieren können).

Es gibt einen Fall, in dem der Beweis durch Widerspruch für Konstruktivisten (oder zumindest Intuitionisten) immer akzeptabel ist: Dies ist, wenn die Aussage$\phi$zu beweisen ist selbst von der Form$\lnot \psi$. Dies liegt daran, dass es sich um einen Satz der intuitionistischen Logik handelt$\lnot \lnot \lnot \psi$gilt genau dann wenn$\lnot \psi$. Andererseits ist es grundsätzlich auch möglich, einen „direkten“ Nachweis zu erbringen$\lnot \psi$in folgendem Sinne: Wir müssen einfach einen Widerspruch ableiten, indem wir annehmen$\psi$. Irgendwelche Beweise für$\lnot \psi$durch Widerspruch in einen "direkten" Beweis umgewandelt werden, weil man immer ableiten kann$\lnot \lnot \psi$aus$\psi$; also wenn wir durch Annahme einen Widerspruch erhalten können$\lnot \lnot \psi$, können wir sicherlich einen Widerspruch ableiten, indem wir annehmen$\psi$.

Letztendlich beinhalten beide der oben genannten Methoden, eine kontrafaktische Annahme zu treffen und einen Widerspruch abzuleiten. Es ist jedoch manchmal möglich, die Negation nach innen zu "schieben" und sogar zu eliminieren. Zum Beispiel, wenn$\phi$ist die Aussage „es existiert ein$x$so dass$\theta (x)$hält", dann$\lnot \phi$lässt sich aus der Aussage „$\theta (x)$gilt für keinen$x$". Insbesondere wenn$\theta (x)$ist selbst eine negative Aussage, sagen wir$\lnot \sigma (x)$, Dann$\lnot \phi$lässt sich aus der Aussage „$\sigma (x)$gilt für alle$x$". Somit beweist "es gibt keine$x$so dass$\sigma (x)$hält nicht " durch Anzeigen "$\sigma (x)$gilt für alle$x$" könnte als "direkterer" Beweis angesehen werden als jeder der beiden zuvor erwähnten Ansätze.

Können alle Widerspruchsbeweise in direkte Beweise umgewandelt werden? In gewissem Sinne muss die Antwort nein lauten: Die intuitionistische Logik ist bekanntlich schwächer als die klassische Logik, dh es gibt Aussagen, die Beweise in der klassischen Logik haben, aber nicht in der intuitionistischen Logik. Der einzige Unterschied zwischen klassischer Logik und intuitionistischer Logik ist das Prinzip that$\phi$ableitbar ist$\lnot \lnot \phi$, also impliziert dies (in gewisser Weise), dass es Theoreme gibt, die nur durch Widerspruch bewiesen werden können.

Was sind also die Vorteile des Beweises durch Widerspruch? Nun, es erleichtert Beweise. So sehr, dass ein Algorithmus zum automatischen Beweisen von Sätzen in der Aussagenlogik darauf basiert. Aber es hat auch seine Nachteile: Ein Widerspruchsbeweis kann verwirrender sein (weil kontrafaktische Annahmen im Umlauf sind!), und im genauen technischen Sinne ist er weniger befriedigend, weil er in der Regel nicht in konstruktiven Zusammenhängen (wieder)verwendet werden kann. Aber die meisten Mathematiker kümmern sich nicht um das letztere Problem.

Wie in der Antwort von "Inquest" erwähnt, ist es oft einfacher, einen Beweis durch Widerspruch zu finden als einen direkten Beweis. Aber nachdem Sie das getan haben, können Sie den Beweis oft vereinfachen , indem Sie ihn in einen direkten Beweis umwandeln. Es ist nicht gut, einen Beweis komplizierter erscheinen zu lassen, als er wirklich ist.

Um einen weiteren Nachteil einiger Beweise durch Widerspruch zu sehen, bedenken Sie Folgendes:

Beweis: beweisen$A$, nehme an nicht$A$. [füge hier 50 Seiten Argumentation ein] Wir haben einen Widerspruch erreicht. Deshalb$A$. Ende des Beweises

Fragen Sie sich nun: Welche der in diesen 50 Seiten bewiesenen Sätze sind falsch und konnten nur bewiesen werden, weil man sich auf die falsche Annahme verlassen hat, dass dies nicht der Fall ist$A$, und die gültig bewiesen sind, und die wahr, aber nicht gültig bewiesen sind, weil die Annahme, dass dies nicht der Fall ist$A$wurde darauf vertraut? Es ist nicht so einfach zu sagen, ohne viel mehr Arbeit. Und wenn Sie sich an einen Beweis für eine dieser Aussagen erinnern, könnten Sie fälschlicherweise denken, dass sie bewiesen wurde und daher als wahr bekannt ist. Daher könnte es viel besser sein, die Verwendung des Widerspruchsbeweises auf einige Teile dieser 50 Seiten zu beschränken, wo keine andere Methode funktioniert.

Vielleicht können Beweise der Nichtexistenz nur durch Widerspruch geführt werden. Als Beispiel möchte ich hier die verschiedenen Beweise für die Irrationalität von anführen$\sqrt{2}$, aber für die Tatsache, dass ich es gesehen habe, behauptete, dass wenn$m$,$n$ganze Zahlen sind, als$m/n$unterscheidet sich von$\sqrt{2}$um mindestens einen Betrag, der davon abhängt$n$--- Ich denke, es könnte gewesen sein$1/(3n^2)$. Hier ist ein weiteres Beispiel: Wie würde man die Nichtexistenz eines nicht-trivialen (dh$>1$) gemeinsamer Teiler von$n$Und$n+1$?

Ich habe ein Buch über Logik gesehen, in dem behauptet wird, dass ein Widerspruchsbeweis einer Nichtexistenz-Behauptung keinen "indirekten Beweis" darstellt, da die Behauptung von Natur aus negativ ist. Ich weiß nicht, wie konventionell das ist.

Ein weiteres Beispiel für einen Widerspruchsbeweis, der keine Vorstellung von einem konstruktiven Beweis liefert, ist das Argument des Strategiediebstahls . Bei bestimmten symmetrischen Spielen kann der zweite Spieler keine Gewinnstrategie haben. Wenn er es täte, könnte der erste Spieler "vorgeben", der zweite Spieler zu sein und seine Gewinnstrategie stehlen, sie ihm stehlen, ein Widerspruch.

Ein interessantes Beispiel ist das Spiel Hex . Es ist leicht zu zeigen, dass Hex nicht mit einem Unentschieden enden kann, und das Argument des Strategiediebstahls trifft darauf zu. Daher ist es ein erster Spielergewinn. Aber für symmetrisch$n$X$n$, die eigentliche Gewinnstrategie ist noch nicht bekannt. Dies ist also ein Beispiel für etwas, das durch Widerspruch und (noch) nicht konstruktiv bewiesen wurde.

Am Beweis durch Widerspruch ist nichts auszusetzen. Sie können zeigen, dass sie funktionieren, indem Sie eine Wahrheitstabelle verwenden. Am Ende ist das alles, was wirklich zählt, oder?

Soweit ich weiß, kann man nicht sicher wissen, dass etwas nicht durch einen direkten Beweis beweisbar ist. Ein Widerspruchsbeweis könnte jedoch eine einfachere Möglichkeit sein, einige Dinge zu beweisen, wie die Irrationalität bestimmter Zahlen. Zum Beispiel habe ich nie einen direkten Beweis für die Irrationalität von gesehen$\sqrt{2}$.

EDIT: Wie Carl Mummert in seiner Antwort sagte, ist der obige Teil in Kursivschrift nicht wahr. Es gibt Sätze, die nur durch Widerspruch beweisbar sind.

Ein Widerspruchsbeweis kann auch als Kontrabeweis formuliert werden . Wenn wir es wissen$Q$ist falsch, wenn wir zeigen können$P\Rightarrow Q$dann haben wir das bewiesen$P$ist falsch. Ob Sie dies als "widerspruchsfreien Beweis" ansehen oder nicht, bleibt Ihnen überlassen. In jedem Fall sind sie logisch gleichwertig.

Das ist erst einmal keine Antwort auf den Titel, sondern auf die Nebenfrage und nur ein Beispiel dafür, warum Sie einen konstruktiven Beweis einem Widerspruchsbeweis vorziehen würden. Betrachten Sie das folgende Beispiel,

Beweise das$x^2 = 1$hat eine Wurzel.

Beweis durch Widerspruch: Angenommen, das$x^2 = 1$hat keine Wurzel. Lassen$f(x) = x^2 - 1$Dann$x^2 = 1$hat genau dann eine Wurzel$f(x_0) = 0$für einige$x_0$. Nach Annahme$x^2 =1$hat keine Wurzel und daher$f(x) \neq 0$für jeden$x$. Beachten Sie, dass$f$ist stetig und$f(0) = -1$Und$f(2) = 3$. Daher gilt nach dem Zwischenwertsatz$\exists x_0$so dass$f(x_0) = 0$was ein Widerspruch ist. Deshalb,$x^2=1$hat eine Wurzel.

Konstruktiver Beweis: Für$x^2=1$dann und nur dann, wenn$x^2-1=0$iff$(x-1)(x+1)=0$. Daher z$x=\pm 1$die Gleichung ist erfüllt, nämlich die Wurzeln sind$-1$Und$1$.

Der Unterschied liegt nicht in der Länge der Beweise, sondern in den Informationen, die Sie haben. Beim konstruktiven Beweis wissen Sie, was die Wurzeln sind, aber nicht beim Beweis durch Widerspruch. Zum Beweis durch Widerspruch hätte man natürlich auch sagen können: „lasst$x_0 = 1$, Dann$x_0^2=1$das ist ein Widerspruch da$1$ist eine Wurzel." aber dann ist es keine klare Unterscheidung zwischen den beiden Arten von Beweisen.

Ich glaube, es gibt einige Beweise, die nur durch Widerspruch nachweisbar sind, und ich werde versuchen, sie logisch zu beschreiben:

Sei X eine logische Aussage, so dass: X$\rightarrow$y, wobei y ein bekannter Widerspruch ist (z. B. 2+2=5 in der normalen arithmetischen Struktur). Ohne etwas anderes von X zu wissen,$\neg$X impliziert nichts und nichts impliziert$\neg$X (und ist daher nicht beweisbar). Aber natürlich impliziert die Annahme von X einen Widerspruch, und daher$\neg$X.

Diese Form der Aussage X ist isoliert, indem sie sich nur auf sich selbst und den Widerspruch bezieht. Ich glaube jedoch, dass sie konstruiert werden können, denn es scheint, dass sie beschrieben werden können.

Abgesehen davon glaube ich nicht, dass es in echter Mathematik und Logik oder in allgemeinen Szenarien der realen Welt Aussagen dieser Form gibt, außer möglicherweise solche, die so konstruiert sind, dass sie diese Kriterien erfüllen und ansonsten bedeutungslos sind. Der Beweis der Primzahlen wurde schließlich nach meinem Verständnis widerspruchsfrei bewiesen; bis die Mathematik weiter entwickelt war, denke ich, dass die Aussage "Die Anzahl der Primzahlen ist$\infty$" war zu Euklids Zeit und wahrscheinlich noch viele Jahre danach im Grunde eine isolierte logische Aussage, da keine anderen Dinge bekannt waren, die dies implizierten, und es implizierte nichts anderes, was für seinen Beweis nützlich war.

Meine nicht mathematische Antwort.

A == Bgleich!(A != B)

Man endet immer mit einer binären Entscheidung, ist oder ist nicht . Und in jeder Sprache is = !(is not).

Aber ich denke, es ist zu einfach, um in Ordnung zu sein.

Ob ein Beweis "durch Widerspruch" ist, hängt wirklich nur von der Aussage ab, mit der Sie begonnen haben. Wenn Ihre anfängliche Aussage ist$P \rightarrow Q$, und zeigt dann das Äquivalent$\neg Q \rightarrow \neg P$ist "Widerspruchsbeweis". Aber in Wirklichkeit ist der "direkte" Beweis dafür$P \rightarrow Q$ist nur ein Beweis "durch Widerspruch" für$\neg Q \rightarrow \neg P$. Der einzige Grund, warum wir damit angefangen haben$P \rightarrow Q$anstatt$\neg Q \rightarrow \neg P$ist unsere Intuition.

Dies ist nur meine Meinung, aber denken Sie auch daran, dass es manchmal sehr wertvoll ist zu wissen, was gilt, wenn$Q$hält nicht .

Ein interessantes Beispiel dafür ist die gesamte Untersuchung der glatten Infinitesimalanalyse . Es stützt sich darauf, dass das Gesetz des ausgeschlossenen Dritten nicht gilt (dh es werden keine Beweise durch Widersprüche akzeptiert), um gültig zu sein. Wenn also alles, was durch Widerspruch beweisbar ist, auch direkt beweisbar wäre, dann könnte es keine glatte Infinitesimalanalyse geben! Schauen Sie sich Bells Buch für weitere Details an, obwohl das Wiki ein gutes Beispiel gibt.

Folgen wir Carl Mummert bei der Betrachtung der drei Hauptsysteme der Aussagenlogik und interpretieren wir die Frage noch einmal neu als

Gibt es einen Widerspruchsbeweis, der in der Klassischen Logik gültig, aber in der Minimalen Logik (bzw. Intuitionistischen Logik) ungültig ist?

Die Systeme der Minimallogik, der Intuitionistischen Logik und der Klassischen Logik sind drei Systeme der Aussagenlogik streng steigender Stärke. (Ich werde das Lehrbuch „Grundlagen der Logik und Mathematik“ von Nievergelt als Referenz verwenden, insbesondere die Abschnitte 1.1 und 4.1.) Um mit der Beantwortung dieser Frage zu beginnen, müssen wir zunächst formalisieren, was „Widerspruchsbeweis“ als logisch ist Prinzip. Betrachten wir zwei Beispiele.

Nehmen Sie zuerst den üblichen Beweis für die Unendlichkeit der Primzahlen: Angenommen$p_1, \ldots, p_N$ist die Liste aller Primzahlen. Dann ist der kleinste Primfaktor von$p_1 \cdots p_N + 1$ist größer als$p_N$. Also gibt es unendlich viele Primzahlen. Das zugrunde liegende logische Prinzip, das auf das Wort „so“ angewendet wird, ist das sogenannte Gesetz der Reductio Ad Absurdum :

Es gibt noch eine andere Art von Widerspruchsbeweis, nämlich des Pigeonhole-Prinzips: Gegeben$n$Löcher, ggf$n + 1$Tauben hineingesteckt werden, dann muss es ein Loch mit mindestens zwei Tauben geben. Der Beweis lautet also: Gäbe es kein Loch mit mindestens zwei Tauben, dann höchstens$n$Tauben wurden in die gesetzt$n$Löcher. Also wenn$n + 1$Tauben wurden in die gesetzt$n$Löcher, dann gibt es irgendein Loch mit mindestens zwei Tauben. Und das zugrunde liegende logische Prinzip beim Wort 'also' ist nun das sogenannte umgekehrte Gesetz der Kontraposition :

Ich hoffe, dass der Leser anhand dieser beiden Beispiele sieht und davon überzeugt ist, dass das, was allgemein als „Widerspruchsbeweis“ angesehen wird, entweder als das Gesetz der Reductio Ad Absurdum oder das umgekehrte Gesetz der Kontraposition formalisierbar ist, die zwei getrennte Gesetze sind gegenseitig.

Die Feinheit stellt sich nun tatsächlich ein

1. das Gesetz der Reductio Ad Absurdum gilt in der Minimallogik, in der Intuitionistischen Logik und in der Klassischen Logik.
2. Das umgekehrte Gesetz der Kontraposition gilt nicht in der Minimalen Logik (bzw. Intuitionistischen Logik). Das Hinzufügen des umgekehrten Gesetzes der Kontraposition zur minimalen Logik (bzw. intuitionistischen Logik) ergibt jedoch eine Logik, die der vollständigen klassischen Logik entspricht (siehe Anhang).

So können wir endlich zu einer Antwort auf die neu interpretierte Frage im gelben Kasten kommen. Für unser erstes Beispiel verwendet der Beweis der Unendlichkeit von Primzahlen den 'Widerspruchsbeweis' im Sinne des Gesetzes der Reductio Ad Absurdum. Dieser Beweis gilt in der Klassischen Logik, aber nach (1) auch in der Minimallogik und in der Intuitionistischen Logik. Für unser zweites Beispiel verwendet der Beweis des Pigeonhole-Prinzips jedoch einen 'Beweis durch Widerspruch' im Sinne des umgekehrten Gesetzes der Kontraposition. Obwohl dieser Beweis in der klassischen Logik gültig ist, ist er nach (2) weder in der minimalen Logik noch in der intuitionistischen Logik gültig. Wir müssen also darauf achten, jene Beweise in der klassischen Mathematik, die das Gesetz der Reductio Ad Absurdum verwenden, nicht als nicht-intuitionistisch oder nicht-minimalistisch abzulehnen,

Anhang:

Zur Bequemlichkeit des Lesers schreibe ich die Axiome dieser drei Logiksysteme nieder, wie sie Nievergelts Buch entnommen sind. Einer der Gründe, dies aufzuschreiben, ist, dass er in @Carl Mummerts Antwort ein konstantes Symbol verwendet$\bot$um das Falschum zu bezeichnen. Es ist jedoch möglich, das Falsum zu vermeiden und die Axiome der minimalen Logik, der intuitionistischen Logik und der klassischen Logik vollständig über die Sprache zu schreiben$\{\neg, \to, \vee, \wedge\}$, mit dem Symbol$\neg$für Negation das Symbol$\to$implizit das Symbol$\vee$für die Disjunktion und das Symbol$\wedge$für Konjunktion. In dieser Sprache die Verwendung eines konstanten Symbols$\bot$denn das falsum wird vermieden.

Um die Details zu geben, lassen Sie$CL^-$be besteht das System aus den folgenden zwei Axiomenschemata:

1. $P \to (Q \to P)$
2. $(P \to (Q \to R)) \to ((P \to Q) \to (P \to R))$

Dann ist Klassische Logik (CL).$CL^-$zusammen mit dem umgekehrten Gesetz der Kontraposition (S.58).

Lassen$T$bezeichnen$CL^{-}$zusammen mit den zusätzlichen fünf Axiomenschemata:

3. $(P \wedge Q) \to P$
4. $(P \wedge Q) \to Q$
5. $P \to (Q \to (P \wedge Q)$
6. $P \to (P \vee Q)$
7. $Q \to (P \vee Q)$
8. $(P \to R) \to ((Q \to R) \to ((P\vee Q) \to R))$

Dann ist Minimal Logic (ML).$T$plus das Gesetz der Reductio ad Absurdum (S.228). Und Intuitionistische Logik (IL) ist$T$zuzüglich des Sondergesetzes der Reductio Ad Absurdum --

Die Fakten sind$ML + \text{Law of Denial Of the Antecedent} \Leftrightarrow IL$(Übung 755, S.231),$ML + \text{Law of Double Negation} \Leftrightarrow CL$(Satz 653, S.229) und$IL + \text{Law of Double Negation} \Leftrightarrow CL$(Übung 754, S.231). Da das Gesetz der Reductio Ad Absurdum ein Axiom der ML ist, gilt es daher in beiden$IL$Und$CL$. Nächste,$ML$ist strikt schwächer als$IL$da das Gesetz der Leugnung des Antezedens nicht gilt in$ML$. Und auch$IL$ist strikt schwächer als$CL$da das Gesetz der doppelten Verneinung nicht gilt$IL$. Daher ist das Gesetz der doppelten Negation der Sonderfall des umgekehrten Gesetzes der Kontraposition durch Nehmen$Q = \top$als verum gilt das umgekehrte Gesetz der Kontraposition nicht$ML$noch drin$IL$.