Sind die "Widerspruchsbeweise" schwächer als andere Beweise?

Auf diese MathOverflow-Frage habe ich die folgende Antwort gepostet (und es gibt dort mehrere andere interessante Antworten):

• Aus gutem Grund ziehen wir Mathematiker einen direkten Implikationsbeweis einem Widerspruchsbeweis vor, sofern ein solcher vorhanden ist. (alles andere ist gleich)

Was ist der Grund? Der Grund ist die Fruchtbarkeit des Beweises, dh unsere Fähigkeit, den Beweis zu verwenden, um weitere mathematische Schlussfolgerungen zu ziehen. Wenn wir eine Implikation (p impliziert q) direkt beweisen, nehmen wir p an und ziehen dann einige Zwischenschlüsse r ₁ , r ₂ , bevor wir schließlich q ableiten. Somit stellt unser Beweis nicht nur fest, dass p q impliziert, sondern auch, dass p r ₁ und r ₂ impliziert und so weiter. Unser Beweis hat uns zusätzliches Wissen über den Kontext von p verschafft, darüber, was sonst in jeder mathematischen Welt gelten muss, in der p gilt. So gelangen wir zu einem umfassenderen Verständnis dessen, was in den p-Welten vor sich geht.

Genauso nehmen wir beim direkten Beweis des Kontrapositivs (¬q impliziert ¬p) ¬q an, machen Zwischenschlüsse r ₁ , r ₂ und schließen schließlich auf ¬p. Somit haben wir auch festgestellt, dass ¬q nicht nur ¬p impliziert, sondern auch, dass es r ₁ und r ₂ und so weiter impliziert. Der Beweis sagt uns also, was sonst noch in Welten gelten muss, in denen q versagt. Da diese zusätzlichen Implikationen ausgedrückt werden können als (¬r ₁ impliziert q), lernen wir entsprechend viele verschiedene Hypothesen kennen, die alle q implizieren.

Diese Art von Schlussfolgerungen können den Wert des Beweises erhöhen, da wir nicht nur lernen, dass (p impliziert q), sondern auch einen ganzen Kontext darüber lernen, wie es in einer mathematischen Situation ist, in der p gilt (oder wo q versagt, oder über verschiedene Situationen, die zu q führen).

Bei reductio dagegen scheint ein Widerspruchsbeweis von (p impliziert q) wenig von diesem Mehrwert zu tragen. Wir nehmen p und ¬q an und argumentieren r ₁ , r ₂ und so weiter, bevor wir zu einem Widerspruch kommen. Die Aussagen r ₁ und r ₂ werden alle unter der widersprüchlichen Hypothese abgeleitet, dass p und ¬q, die letztlich in keiner mathematischen Situation gilt. Der Beweis hat zusätzliches Wissen über ein nicht existierendes, widersprüchliches Land geliefert. (Nutzlos!) Diese Zwischenaussagen scheinen uns also kein größeres Wissen über die p-Welten oder die q-Welten zu liefern, abgesehen von der bloßen Aussage, dass (p q) allein impliziert.

Ich glaube, dass dies der Grund dafür ist, dass manchmal, wenn ein Mathematiker einen Widerspruchsbeweis vervollständigt, die Dinge über die rohe Implikation hinaus immer noch unruhig erscheinen können, mit weniger Kontext und Wissen darüber, was vor sich geht, als dies bei einem direkten Beweis der Fall wäre.

Betrachten Sie als Beispiel für einen Beweis, bei dem wir durch einen Widerspruchsbeweis zu falschen Erwartungen geführt werden, den Satz von Euklid, dass es unendlich viele Primzahlen gibt. In einem üblichen Widerspruchsbeweis nimmt man an, dass p ₁ , ..., p _n alle Primzahlen sind . Da keiner von ihnen das Produkt-plus-Eins p ₁ ...p _n +1 teilt, folgt daraus, dass dieses Produkt-plus-Eins auch eine Primzahl ist. Dies widerspricht der Vollständigkeit der Liste. Nun erwarten viele Anfänger nach diesem Argument fälschlicherweise, dass immer dann, wenn p ₁ , ..., p _nprim sind, dann ist auch das Produkt-plus-Eins prim. Aber das ist natürlich nicht wahr, und dies wäre ein unangebrachtes Beispiel für den Versuch, mehr Informationen aus dem Beweis zu extrahieren, unangebracht, weil dies ein Beweis durch Widerspruch ist, und diese Schlussfolgerung auf der Annahme beruht, dass p 1 _, ... , p _n waren alle Primzahlen. Wenn man den Beweis jedoch als direktes Argument organisiert, das zeigt, dass immer dann, wenn p ₁ , ..., p _n Primzahlen sind, es noch eine weitere Primzahl gibt, die nicht auf der Liste steht, dann wird man zu der wahren Schlussfolgerung geführt, dass p ₁ ...p _n +1 hat lediglich einen Primteiler, der nicht auf der ursprünglichen Liste steht. (Und Michael Hardy erwähnt, dass Euklid tatsächlich das direkte Argument vorgebracht hatte.)

Die meisten Logiker halten Widerspruchsbeweise für gleichermaßen gültig, einige Leute sind jedoch Konstruktivisten / Intuitionisten und halten sie nicht für gültig.

( Bearbeiten: Dies ist nicht ganz richtig, wie in den Kommentaren erklärt. Nur bestimmte Beweise durch Widerspruch sind aus konstruktivistischer Sicht problematisch, nämlich diejenigen, die "A" beweisen, indem sie "nicht A" annehmen und einen Widerspruch erhalten. Nach meiner Erfahrung das ist normalerweise genau die Situation, die Leute meinen, wenn sie "Beweis durch Widerspruch" sagen.)

Ein möglicher Grund dafür, dass die konstruktivistische Sichtweise einen gewissen Sinn ergibt, ist, dass Aussagen wie die Kontinuumshypothese unabhängig von den Axiomen sind, also ist es ein bisschen seltsam zu behaupten, dass sie entweder wahr oder falsch ist, in gewissem Sinne ist sie beides nicht.

Dennoch ist der Konstruktivismus eine relativ ungewöhnliche Position unter Mathematikern/Logikern. Es gilt jedoch nicht als völlig verrückt oder übertrieben. Glücklicherweise können in der Praxis die meisten Beweise durch Widerspruch in konstruktivistische Begriffe übersetzt werden, und tatsächliche Konstruktivisten sind ziemlich geschickt darin. Der Rest von uns macht sich also meistens nicht die Mühe, sich über dieses Problem Gedanken zu machen, und denkt, es sei das Problem der Konstruktivisten.

Um A zu beweisen, nehmen wir an, nicht A.

[Hier 10-seitiges Argument einfügen.]

Welche der auf den vorangehenden 10 Seiten bewiesenen Behauptungen sind falsch, weil sie aus der (nun als falsch bewiesenen) Annahme abgeleitet wurden, dass nicht A? Welche sind wahr, können aber nicht als gültig bewiesen angesehen werden, weil die Beweise auf der falschen Annahme beruhten, dass nicht A? Und welche wurden gültig bewiesen, da ihre Beweise nicht auf dieser Annahme beruhten? Es kann schwer zu sagen sein. Und wenn Sie unterwegs gesehen haben, dass eine Behauptung bewiesen wurde, denken Sie vielleicht, dass sie als wahr bekannt ist.

Auf diese Weise kann ein Widerspruchsbeweis bestenfalls verwirrend sein.

Manchmal möchten Sie vielleicht nicht nur wissen, dass etwas existiert , Sie möchten vielleicht auch wissen, wie man es tatsächlich findet (und damit zusammenhängende Fragen, wie z. B. wie schnell Sie es finden können). Beweise durch Widerspruch sind nicht konstruktiv, während direkte Beweise typischerweise konstruktiv in dem Sinne sind, dass sie tatsächlich eine Antwort konstruieren.

Beispielsweise erfolgt der Beweis, dass es unendlich viele Primzahlen gibt, meist durch Widerspruch. Sie können es jedoch zu einem direkten Beweis machen, der das stärkere Ergebnis liefert, dass die n-te Primzahl kleiner als e^{e^n} ist. (Dies ist eine gute Übung, um sie selbst zu erarbeiten, aber Sie finden sie auch als Prop 1.1.3 in meiner Abschlussarbeit und wahrscheinlich an vielen anderen Stellen.)

Fast immer ist der direkte Beweis verständlicher, kürzer und hilfreicher!

In der Mathematik kann man eine mathematische Theorie mit verschiedenen Sätzen von Axiomen konstruieren. Das kann wirklich nützlich sein. Als Mathematiker das Axiom paralleler Linien in der euklidischen Geometrie ignorierten, führte dies zu nicht-euklidischen Geometrien, die in der Einsteinschen Physik wirklich wichtig wurden.

Ein Axiom der Logik ist das Gesetz vom ausgeschlossenen Dritten, das im Grunde besagt, dass eine Aussage entweder wahr oder falsch ist. Dies bedeutet, dass jeder Satz, der vollständig von diesem Axiom abhängt, nicht gültig ist für mathematische Theorien, die sich entscheiden, das Axiom zu ignorieren.

Ein Beweis durch Widerspruch verwendet das Axiom direkt; wenn die Konsequenz falsch ist, dann ist der Antecent falsch, dann ist die Umkehrung der Konsequenz wahr (weil sie entweder wahr oder falsch sein muss). Wenn der Satz auf konstruktive Weise bewiesen werden kann, hängt er nicht vom Gesetz des ausgeschlossenen Dritten ab und gilt in Theorien, die das Gesetz nicht verwenden.

Das scheint zunächst eine dumme Frage zu sein – schließlich soll ein mathematischer Beweis kein Beweis und damit unbestreitbar sein. Aber natürlich brauchen wir Annahmen, um irgendetwas zu beweisen, und einige Leute sind mit den allgemein von Mathematikern verwendeten Axiomen nicht einverstanden. Ich habe nicht viel Wissen über diese Ansicht, aber ich bin sicher, dass sie Theoreme haben, die zeigen, dass widerspruchsähnliche Beweise (angesichts ihrer Axiome) unter bestimmten Bedingungen gültig sind. Ich würde empfehlen, dem zu folgen, was alle anderen tun, und "Widerspruchsbeweise" als gleichermaßen gültig zu behandeln, es sei denn, Sie haben die Sicht des Konstruktivismus untersucht und entscheiden, dass sie richtig sind.

Ob sie eindeutiger sind, hängt vom tatsächlichen Beweis ab. Manchmal ist der klarste Weg, einen Beweis zu führen, von den Annahmen auszugehen und zu sehen, was sie wirklich sagen und warum dies zu einem Widerspruch führen wird. Der anschaulichste Beweis hängt von den Umständen ab.

Der Widerspruchsbeweis ist genauso logisch gültig wie jeder andere Beweis. Wenn Sie sich nicht sicher sind, denke ich, dass es hilfreich sein könnte, genau zu überlegen, was ein Beweis durch Widerspruch beinhaltet.
Angenommen, wir haben eine Reihe von Aussagen$\Gamma$, und das$\Gamma\cup\{(\neg\phi)\}$ist nicht konsistent. Das heißt, die Aussage$\neg\phi$widerspricht etwas in$\Gamma$. (Mit anderen Worten, wir nahmen an$\phi$war falsch und erreichte einen Widerspruch.) Sagen Sie, dass die Aussage war$\psi$. Dann$\Gamma\cup\{(\neg\phi)\}\vdash\psi$Und$\Gamma\cup\{(\neg\phi)\}\vdash \neg\psi$. Aus dem Explosionsprinzip schließen wir darauf$\Gamma\cup\{(\neg\phi)\}\vdash\phi$. (Wir können jede Aussage beweisen, also beweisen wir$\phi$.
Durch Ableitung wissen wir das$\Gamma\vdash(\neg\phi\Rightarrow\phi)$.
Die meisten logischen Systeme erster Ordnung haben ein Axiom, das uns gibt$((\neg\phi\Rightarrow\phi)\Rightarrow\phi$. Ich hoffe, Sie können sich ohne Probleme davon überzeugen, dass dies wahr ist.
Dies ergibt$\Gamma\vdash\phi$.
Wir begannen mit der Idee, dass die Negation der Aussage$\phi$mit Ihrem Arbeitssatz von Axiomen und Theoremen nicht vereinbar war$\Gamma$, und kam daher zu dem Schluss$\Gamma$beweist$\phi$.

Natürlich gibt es mehr als eine Möglichkeit, etwas zu beweisen. Andere Methoden können oft intuitiver oder eleganter sein oder zu anderen nützlichen Ergebnissen führen. Das unterscheidet sich jedoch von „schwächer“. Widerspruchsbeweis ist vollkommen stichhaltig.