Konstruktiver Beweis - Constructive proof

In der Mathematik ist ein konstruktiver Beweis eine Beweismethode , die die Existenz eines mathematischen Objekts demonstriert , indem eine Methode zum Erstellen des Objekts erstellt oder bereitgestellt wird. Dies steht im Gegensatz zu einem nicht konstruktiven Beweis (auch als Existenzbeweis oder reiner Existenzsatz bekannt ), der die Existenz einer bestimmten Art von Objekt ohne Beispiel beweist. Um Verwechslungen mit dem folgenden stärkeren Konzept zu vermeiden, wird ein solcher konstruktiver Beweis manchmal als wirksamer Beweis bezeichnet .

Ein konstruktiver Beweis kann sich auch auf das stärkere Konzept eines Beweises beziehen, das in der konstruktiven Mathematik gültig ist . Der Konstruktivismus ist eine mathematische Philosophie, die alle Beweismethoden ablehnt, die die Existenz von Objekten beinhalten, die nicht explizit gebaut wurden. Dies schließt insbesondere die Verwendung des Gesetzes der ausgeschlossenen Mitte , des Axioms der Unendlichkeit und des Axioms der Wahl aus und führt für einige Begriffe zu einer anderen Bedeutung (zum Beispiel hat der Begriff "oder" im Konstruktiven eine stärkere Bedeutung Mathematik als in der Klassik).

Einige nicht konstruktive Beweise zeigen, dass ein Widerspruch entsteht, wenn ein bestimmter Satz falsch ist; folglich muss der Satz wahr sein ( Beweis durch Widerspruch ). Das Prinzip der Explosion ( ex falso quodlibet ) wurde jedoch in einigen Varianten der konstruktiven Mathematik, einschließlich des Intuitionismus, akzeptiert .

Konstruktive Beweise kann als Definition zertifizierte mathematische gesehen werden Algorithmen : diese Idee im erforscht Brouwer-Heyting-Kolmogorov Interpretation der konstruktiven Logik , die Curry-Howard Korrespondenz zwischen Proofs und Programme, und solche logischen Systeme wie Pro Martin-Löf ‚s intuitionistic Typ Theorie und Thierry Coquand und Gérard Huet ‚s Kalkül der Konstruktionen .

Ein historisches Beispiel

Bis zum Ende des 19. Jahrhunderts waren alle mathematischen Beweise im Wesentlichen konstruktiv. Die ersten nichtkonstruktiven Konstruktionen erschienen mit Georg Cantors Theorie der unendlichen Mengen und der formalen Definition von reellen Zahlen .

Die erste Verwendung nichtkonstruktiver Beweise zur Lösung zuvor in Betracht gezogener Probleme scheint Hilberts Nullstellensatz- und Hilberts Basissatz zu sein . Aus philosophischer Sicht ist Ersteres besonders interessant, da es die Existenz eines genau spezifizierten Objekts impliziert.

Der Nullstellensatz festgestellt werden kann , wie folgt: Wenn es Polynome in n indeterminates mit komplexen Koeffizienten, die keine gemeinsamen Komplex haben Nullen , dann gibt es Polynome derart , dass ${\ displaystyle f_ {1}, \ ldots, f_ {k}}$${\ displaystyle g_ {1}, \ ldots, g_ {k}}$

${\ displaystyle f_ {1} g_ {1} + \ ldots + f_ {k} g_ {k} = 1.}$

Ein solcher nicht konstruktiver Existenzsatz war für die damaligen Mathematiker eine solche Überraschung, dass einer von ihnen, Paul Gordan , schrieb: "Dies ist keine Mathematik, es ist Theologie ".

25 Jahre später lieferte Grete Hermann einen Algorithmus für die Berechnung, der im engeren Sinne kein konstruktiver Beweis ist, da sie Hilberts Ergebnis verwendete. Sie bewies, dass sie, falls vorhanden, mit einem Grad von weniger als gefunden werden können . ${\ displaystyle g_ {1}, \ ldots, g_ {k},}$${\ displaystyle g_ {1}, \ ldots, g_ {k}}$${\ displaystyle 2 ^ {2 ^ {n}}}$

Dies liefert einen Algorithmus, da das Problem auf die Lösung eines linearen Gleichungssystems reduziert wird , indem die endliche Anzahl von Koeffizienten der als unbekannt betrachtet wird ${\ displaystyle g_ {i}.}$

Beispiele

Nicht konstruktive Beweise

Betrachten Sie zunächst den Satz, dass es unendlich viele Primzahlen gibt . Euclid ‚s Beweis ist konstruktiv. Ein üblicher Weg zur Vereinfachung von Euklids Beweis postuliert jedoch, dass es entgegen der Behauptung im Satz nur eine endliche Anzahl von ihnen gibt, in diesem Fall gibt es eine größte, die mit n bezeichnet wird . Dann betrachte die Zahl n ! + 1 (1 + das Produkt der ersten n Zahlen). Entweder ist diese Zahl eine Primzahl, oder alle ihre Primfaktoren sind größer als n . Ohne eine bestimmte Primzahl festzulegen, beweist dies, dass eine existiert , die entgegen dem ursprünglichen Postulat größer als n ist.

Betrachten wir nun den Satz "Es gibt irrationale Zahlen und solche, die rational sind ." Dieser Satz kann sowohl mit einem konstruktiven als auch mit einem nicht konstruktiven Beweis bewiesen werden. ${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle a ^ {b}}$

Der folgende Beweis von 1953 von Dov Jarden wird seit mindestens 1970 häufig als Beispiel für einen nicht konstruktiven Beweis verwendet:

CURIOSA
339. Ein einfacher Beweis, dass eine Potenz einer irrationalen Zahl zu einem irrationalen Exponenten rational sein kann. ist entweder rational oder irrational. Wenn es rational ist, ist unsere Aussage bewiesen. Wenn es irrational ist, beweist unsere Aussage.      Dov Jarden Jerusalem
${\ displaystyle {\ sqrt {2}} ^ {\ sqrt {2}}}$${\ displaystyle ({\ sqrt {2}} ^ {\ sqrt {2}}) ^ {\ sqrt {2}} = 2}$

Im Detail:

• Denken Sie daran, dass dies irrational und 2 rational ist. Betrachten Sie die Nummer . Entweder ist es rational oder es ist irrational. ${\ displaystyle {\ sqrt {2}}}$ ${\ displaystyle q = {\ sqrt {2}} ^ {\ sqrt {2}}}$
• Wenn es rational ist, dann ist der Satz wahr, mit und beiden sind . ${\ displaystyle q}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle {\ sqrt {2}}}$
• Wenn es irrational ist, dann ist der Satz wahr, mit Sein und Sein , seitdem ${\ displaystyle q}$${\ displaystyle a}$${\ displaystyle {\ sqrt {2}} ^ {\ sqrt {2}}}$${\ displaystyle b}$${\ displaystyle {\ sqrt {2}}}$

${\ displaystyle \ left ({\ sqrt {2}} ^ {\ sqrt {2}} \ right) ^ {\ sqrt {2}} = {\ sqrt {2}} ^ {({\ sqrt {2}} \ cdot {\ sqrt {2}})} = {\ sqrt {2}} ^ {2} = 2.}$

Im Kern ist dieser Beweis nicht konstruktiv, weil er sich auf die Aussage "Entweder q ist rational oder irrational" stützt - eine Instanz des Gesetzes der ausgeschlossenen Mitte , die innerhalb eines konstruktiven Beweises nicht gültig ist. Der nicht konstruktive Beweis konstruiert kein Beispiel a und b ; es gibt lediglich eine Reihe von Möglichkeiten (in diesem Fall zwei sich gegenseitig ausschließende Möglichkeiten) und zeigt, dass eine von ihnen - aber nicht welche - das gewünschte Beispiel liefern muss.

Wie sich herausstellt, ist dies aufgrund des Gelfond-Schneider-Theorems irrational , aber diese Tatsache ist für die Richtigkeit des nicht konstruktiven Beweises irrelevant. ${\ displaystyle {\ sqrt {2}} ^ {\ sqrt {2}}}$

Konstruktive Beweise

Ein konstruktiver Beweis des obigen Satzes über irrationale Kräfte von Irrationalen würde ein tatsächliches Beispiel geben, wie zum Beispiel:

${\ displaystyle a = {\ sqrt {2}} \ ,, \ quad b = \ log _ {2} 9 \ ,, \ quad a ^ {b} = 3 \ ,.}$

Die Quadratwurzel von 2 ist irrational und 3 ist rational. ist auch irrational: Wenn es gleich wäre , dann wäre nach den Eigenschaften der Logarithmen 9 ⁿ gleich 2 ^m , aber das erstere ist ungerade und das letztere ist gerade. ${\ displaystyle \ log _ {2} 9}$${\ displaystyle m \ over n}$

Ein wesentlicheres Beispiel ist der Graph-Minor-Satz . Eine Konsequenz dieses Theorems ist, dass ein Graph auf den Torus gezeichnet werden kann, wenn und nur wenn keiner seiner Minderjährigen zu einer bestimmten endlichen Menge von " verbotenen Minderjährigen " gehört. Der Beweis für die Existenz dieser endlichen Menge ist jedoch nicht konstruktiv, und die verbotenen Minderjährigen sind nicht tatsächlich spezifiziert. Sie sind noch unbekannt.

Brouwersche Gegenbeispiele

In der konstruktiven Mathematik kann eine Aussage durch Angabe eines Gegenbeispiels widerlegt werden , wie in der klassischen Mathematik. Es ist jedoch auch möglich, ein Brouwer'sches Gegenbeispiel anzugeben, um zu zeigen, dass die Aussage nicht konstruktiv ist. Diese Art von Gegenbeispiel zeigt, dass die Aussage ein Prinzip impliziert, von dem bekannt ist, dass es nicht konstruktiv ist. Wenn konstruktiv bewiesen werden kann, dass eine Aussage ein Prinzip impliziert, das nicht konstruktiv beweisbar ist, kann die Aussage selbst nicht konstruktiv beweisbar sein.

Zum Beispiel kann gezeigt werden, dass eine bestimmte Aussage das Gesetz der ausgeschlossenen Mitte impliziert. Ein Beispiel für ein Brouwer'sches Gegenbeispiel dieses Typs ist der Satz von Diaconescu , der zeigt, dass das vollständige Axiom der Wahl in Systemen der konstruktiven Mengenlehre nicht konstruktiv ist , da das Axiom der Wahl das Gesetz der ausgeschlossenen Mitte in solchen Systemen impliziert. Das Gebiet der konstruktiven Umkehrmathematik entwickelt diese Idee weiter, indem es verschiedene Prinzipien in Bezug auf "wie nicht konstruktiv" klassifiziert und zeigt, dass sie verschiedenen Fragmenten des Gesetzes der ausgeschlossenen Mitte entsprechen.

Brouwer lieferte auch "schwache" Gegenbeispiele. Solche Gegenbeispiele widerlegen jedoch keine Aussage; sie zeigen nur, dass derzeit kein konstruktiver Beweis für die Aussage bekannt ist. Ein schwaches Gegenbeispiel beginnt mit einem ungelösten mathematischen Problem wie Goldbachs Vermutung , bei dem gefragt wird, ob jede gerade natürliche Zahl größer als 4 die Summe zweier Primzahlen ist. Definieren Sie eine Folge a ( n ) rationaler Zahlen wie folgt:

${\ displaystyle a (n) = {\ begin {case} (1/2) ^ {n} & {\ mbox {wenn jede gerade natürliche Zahl im Intervall}} [4, n] {\ mbox {die Summe ist von zwei Primzahlen}}, \\ (1/2) ^ {k} & {\ mbox {if}} k {\ mbox {ist die am wenigsten gerade natürliche Zahl im Intervall}} [4, n] {\ mbox { Das ist nicht die Summe von zwei Primzahlen}} \ end {case}}}$

Für jeden n , der Wert von einem ( n kann) durch erschöpfende Suche bestimmt werden, und so eine ist eine gut definierte Sequenz, konstruktiv. Da darüber hinaus ein eine Cauchy - Folge mit einer festen Rate der Konvergenz, eine konvergiert zu einem gewissen reellen Zahl α, nach der üblichen Behandlung der reellen Zahlen in konstruktiver Mathematik.

Mehrere Tatsachen über die reelle Zahl α können konstruktiv bewiesen werden. Wenn es jedoch aufgrund der unterschiedlichen Bedeutung der Wörter in der konstruktiven Mathematik einen konstruktiven Beweis dafür gibt, dass "α = 0 oder α ≠ 0" ist, würde dies bedeuten, dass es einen konstruktiven Beweis für Goldbachs Vermutung gibt (im ersteren Fall) oder ein konstruktiver Beweis dafür, dass Goldbachs Vermutung falsch ist (im letzteren Fall). Da ein solcher Beweis nicht bekannt ist, darf die zitierte Aussage auch keinen bekannten konstruktiven Beweis haben. Es ist jedoch durchaus möglich, dass Goldbachs Vermutung einen konstruktiven Beweis hat (da wir derzeit nicht wissen, ob dies der Fall ist). In diesem Fall hätte die zitierte Aussage auch einen konstruktiven Beweis, wenn auch einen, der derzeit unbekannt ist. Die hauptsächliche praktische Verwendung schwacher Gegenbeispiele besteht darin, die "Härte" eines Problems zu identifizieren. Zum Beispiel zeigt das gerade gezeigte Gegenbeispiel, dass die zitierte Aussage "mindestens so schwer zu beweisen" ist wie Goldbachs Vermutung. Schwache Gegenbeispiele dieser Art hängen oft mit dem begrenzten Prinzip der Allwissenheit zusammen .

Siehe auch

• Konstruktivismus (Philosophie der Mathematik)
• Errett Bishop - Autor des Buches "Grundlagen der konstruktiven Analyse".
• Existenzsatz § 'Reine' Existenz ergibt sich
• Nichtkonstruktive Algorithmus-Existenzbeweise
• Probabilistische Methode

Verweise

Weiterführende Literatur

Externe Links

• Schwache Gegenbeispiele von Mark van Atten, Stanford Encyclopedia of Philosophy