Welche Sätze der klassischen Mathematik lassen sich ohne Anwendung des Satzes vom ausgeschlossenen Dritten nicht beweisen?

Nur zur Klarstellung: Die Ablehnung der Ausgeschlossenen Mitte durch die Intuitionisten bedeutet nicht , sie anzunehmen$\lnot (A \lor \lnot A)$für alle$A$! Einige Fälle von Ausgeschlossener Mitte sind akzeptabel, nämlich diejenigen, für die wir beides beweisen können $A$ oder $\lnot A$.

In diesem Sinne sind zwei Standardbeispiele für klassische Sätze, die intuitionistisch nicht gültig sind

Trichotomie Für jeden$x\in\mathbb{R}$genau eine der folgenden gilt:$x < 0$oder$x = 0$oder$x > 0$.

Oder ein besonderer Fall:$x = 0 \lor x \neq 0$.

Zwischenwertsatz If$f:[a, b]\to\mathbb{R}$ist stetig und$f(a) < m < f(b)$für einige$m \in\mathbb{R}$, dann existiert a$c\in (a,b)$so dass$f(c) = m$.

(Der Beweis des Intermediate Value Theorem stützt sich möglicherweise nicht offensichtlich auf die ausgeschlossene Mitte, aber er stützt sich auf die Eigenschaft der kleinsten oberen Grenze für$\mathbb{R}$was auch von Intuitionisten abgelehnt wird.)

Intuitionistisch zu diagnostizieren, was mit ihnen "falsch" ist, ist etwas subtiler, als darauf hinzuweisen, wo sie Excluded Middle verwenden. Was normalerweise getan wird, ist zu zeigen, dass diese Theoreme einen inakzeptablen Fall von ausgeschlossenem Mittel implizieren und daher zurückgewiesen werden müssen.

Für die Trichotomie konstruiert man ein "schwaches Gegenbeispiel". Lassen$G(n) \equiv \text{"}2n+4 \text{ is the sum of two primes"}$für$n \in \mathbb{N}$(einschließlich 0). Wir definieren dann die folgende Reihenfolge:

$$a_n = \begin{cases} 2^{-n} & \text{if }(\forall k\leq n)G(k);\\ 2^{-k} & \text{if } k \leq n \text{ is the first number such that } \lnot G(k);\end{cases}$$

Das Prädikat$G(n)$ist entscheidbar: für jeden$n$, eine endliche Rechnung wird zeigen, ob$G(n)$hält bzw$\lnot G(n)$. Somit$(a_n)_{n\in\mathbb{N}}$ist eine wohldefinierte Folge. Außerdem können wir beweisen, dass es Cauchy ist: für jeden$N\in\mathbb{N}$, berechnen$G(N)$. Wenn das stimmt, dann$|a_n - a_m| < 2^{-N}$für alle$n,m > N$; wenn falsch, dann gibt es a$k < N$so dass$a_n = 2^{-k}$für alle$n>k$, So$|a_n - a_m| = 0 < 2^{-N}$für alle$n,m > N$. Deshalb,$(a_n)_n$definiert eine echte reelle Zahl, nennen Sie sie$a$.

Beachten Sie, dass nirgendwo im Beweis, dass$(a_n)_n$ist eine Cauchy-Folge (oder sogar eine Folge), habe ich die Tatsache, dass entweder verwendet$G(n)$gilt für alle $n\in\mathbb{N}$oder es schlägt bei einigen fehl$n$. Ich habe das nur für irgendetwas angenommen $n$,$G(n)\lor\lnot G(n)$. Dies ist intuitiv akzeptabel, da wir (im Prinzip) alle Primzahlen kleiner als überprüfen könnten$n$um ein Paar zu finden, dessen Summe ist$n$oder durch Erschöpfung beweisen, dass es ein solches Paar nicht gibt.

Das behaupte ich$a$ist ein (schwaches) Gegenbeispiel zu Trichotomys Folgerung: Aus der Definition geht klar hervor, dass

$$a = 0 \iff (\forall n\in\mathbb{N})G(n),$$ So $$a = 0 \lor a \neq 0 \iff (\forall n\in\mathbb{N})G(n) \lor \lnot(\forall n\in\mathbb{N})G(n).$$ Die rechte Seite der letzten Äquivalenz ist ein "problematisches" Beispiel für Ausgeschlossene Mitte: Sie behauptet (intuitionistisch), dass die Goldbach-Vermutung entweder bewiesen oder widerlegt ist. Während ich dies schreibe, bleibt die Goldbach-Vermutung offen, daher ist es nicht intuitiv gültig zu behaupten: Goldbach-Vermutung$\lor$ $\lnot$(Goldbach-Vermutung). Daraus folgt, dass wir nicht behaupten können$a = 0 \lor a \neq 0$.

Der Zwischenwertsatz erleidet ein ähnliches Schicksal, obwohl man (intuitionistisch) beweisen kann

Intuitionistischer Zwischenwertsatz. Wenn$f:[a, b]\to\mathbb{R}$ist stetig und$f(a) < m < f(b)$für einige$m \in\mathbb{R}$, dann für alle$\varepsilon > 0$es existiert ein$c\in (a,b)$so dass$|f(c) - m| < \varepsilon$.

Auch wenn wir nicht alle Theoreme „retten“ können, die unter Verwendung von „Excluded Middle“ bewiesen werden ( z. B. indem wir Beweise finden, die „Excluded Middle“ umgehen), können wir oft analoge Theoreme beweisen, die „nahe genug“ und klassisch äquivalent sind – obwohl nicht intuitionistisch äquivalent!

Es gibt einige andere gängige Theoreme, die wir nicht ohne ein gewisses Maß an klassischer Logik beweisen können (die aber konstruktive Analoga haben).

Analyse

Beispielsweise können die folgenden zwei Theoreme in der konstruktiven Logik nicht bewiesen werden:

Die reellen Zahlen der Cauchy-Folge bilden einen vollständigen metrischen Raum.

Die Cauchy-Folge und Dedekind-Cut-Definitionen der reellen Zahlen sind äquivalent.

Um die beiden obigen Tatsachen zu beweisen, genügt es, das „sehr schwache Wahlprinzip“ anzunehmen. Dieses sehr schwache Wahlprinzip besagt: Angenommen, das$P$Und$Q$sind Prädikate auf$\mathbb{N}$. Wenn$\forall n \in \mathbb{N}, P(n) \lor Q(n)$, dann gibt es eine Funktion$f : \mathbb{N} \to \{0, 1\}$so dass für alle$n \in \mathbb{N}$, Wenn$f(n) = 0$Dann$P(n)$, und wenn$f(n) = 1$Dann$Q(n)$. Diese Tatsache ist mit klassischer Logik leicht zu beweisen - definieren$f(n) = 0$Wenn$P(n)$, Und$1$ansonsten. Viele Konstruktivisten gehen von diesem Axiom aus (oder einer stärkeren Version wie der zählbaren Wahl). Die drei Hauptschulen des Konstruktivismus - Bishop's School, Markov's School und Brouwer's School - gehen alle von einer Version zählbarer Wahlmöglichkeiten aus, die stark genug ist, um das Obige zu implizieren.

Weitere Beispiele sind der Zwischenwertsatz (siehe Antwort von ryan221b) und der Mittelwertsatz. Es gibt eine ungefähre Version des Mittelwertsatzes; Soweit ich das beurteilen kann, scheint es das oben erwähnte sehr schwache Wahlprinzip zu erfordern.

Zum Schluss noch ein Kicker: Ohne klassische Logik ist es unmöglich zu beweisen

Nicht alle Funktionen$\mathbb{R} \to \mathbb{R}$sind kontinuierlich.

Es entspricht vollkommen der konstruktiven Logik, dass alle diese Funktionen stetig sind – tatsächlich kann jede solche Funktion, die konstruktiv definiert werden kann, konstruktiv als stetig bewiesen werden.

Kardinalität

Ein weiteres Beispiel für ein nicht konstruktiv beweisbares Theorem ist das Schröder-Bernstein-Theorem, das besagt, dass bei einer Injektion$A \to B$und eine Spritze$B \to A$, kann man eine Bijektion zwischen finden$A$Und$B$. Dieser Satz entspricht tatsächlich dem Gesetz der ausgeschlossenen Mitte!

Die Tatsache, dass jede Teilmenge einer endlichen Menge endlich ist, entspricht Excluded Middle (tatsächlich entspricht sogar die Aussage, dass jede Teilmenge einer 1-Element-Menge endlich ist, Excluded Middle).

Die Tatsache, dass jede Menge, deren Elemente endlich aufgezählt werden können, endlich ist, ist auch äquivalent zu Ausgeschlossenem Mittel (tatsächlich genügt es, Mengen der Form zu betrachten$\{x_1, x_2\}$).

Noch deutlicher, ohne das Gesetz der ausgeschlossenen Mitte kann man die Existenz einer injektiven Funktion nicht ausschließen$\mathbb{N}^\mathbb{N} \to \mathbb{N}$. Dies wirft wirklich die ganze Idee von "Kardinalität als Größe" aus dem Fenster.

Algebra

Viele Ergebnisse in der Algebra beruhen auf dem Auswahlaxiom. Da dieses Axiom wiederum Excluded Middle beweist, sind diese Ergebnisse nicht konstruktiv. Beispiele für solche Sätze sind, dass jeder Vektorraum eine Basis hat oder dass jeder Ring ungleich Null ein maximales Ideal hat.

Andere Beispiele, die dem ausgeschlossenen Mittel entsprechen, umfassen

• $\mathbb{Z}$ist ein prinzipieller Idealbereich
• Jeder Unterraum einer endlichdimensionalen$\mathbb{R}$-Vektorraum ist endlichdimensional
• Jeder Quotient einer endlichdimensionalen$\mathbb{R}$-Vektorraum ist endlichdimensional

Andere nicht beweisbare Aussagen, die schwächer sind als ausgeschlossene Mitte, aber immer noch nicht bewiesen werden können, umfassen

• Jeden$\mathbb{R}$-Matrix kann in zeilenreduzierte Stufenform gebracht werden
• Jedes Quadrat$\mathbb{R}$-matrix ist entweder invertierbar oder nicht

Ein Großteil der Algebra ist jedoch konstruktiv. Zum Beispiel gilt eine Identität für alle Gruppen (oder alle Ringe oder alle Monoide usw.) genau dann, wenn sie aus den Gruppenaxiomen konstruktiv bewiesen werden kann.

Zahlentheorie + Berechenbarkeitstheorie

Es gibt tatsächlich eine ganze Reihe von Aussagen in der Zahlentheorie, die unter klassischer und konstruktiver Logik gleichermaßen beweisbar sind. Insbesondere alle intuitionistisch$\Pi_2$Aussage ist genau dann konstruktiv beweisbar, wenn sie klassisch beweisbar ist. A$\Pi_2$Aussage ist eine, die formuliert werden kann als$\forall m \exists n P(n, m)$, wobei alle Quantoren in vorkommen$P$sind begrenzt (was bedeutet, dass sie die Form haben$\forall a \leq b$oder$\exists a \leq b$). Dazu gehören viele offene Probleme wie die Primzahlzwillingsvermutung, die$3n + 1$Vermutung, die Goldbach-Vermutung, die Landau-Vermutung, die Schinzel-Hypothese, die Legendre-Vermutung, die schwache Bunyakovsky-Vermutung,$P \neq NP$, und mehr.

Allerdings gibt es einige Aussagen, die nicht konstruktiv beweisbar sind.

Für jede unäre primitive rekursive Funktion$f : \mathbb{N} \to \mathbb{N}$, entweder gibt es einige$n$so dass$f(n) = 0$, oder für alle$n$,$f(n) \neq 0$.

Nicht alle Funktionen$f : \mathbb{N} \to \mathbb{N}$sind berechenbar.

Eigentlich jede Funktion$\mathbb{N} \to \mathbb{N}$was konstruktiv definierbar ist, kann auch konstruktiv als berechenbar nachgewiesen werden.

Nun, was meinst du mit "Theorem der klassischen Mathematik"? Die Antwort wird sich ändern, je nachdem, wie Sie sie definieren.

Wenn Sie zum Beispiel eine Theorie erster Ordnung über eine Sprache mit einem Prädikatssymbol haben$P$das hat überhaupt keine Axiome. Dann$\forall x\ ( P(x) \lor \neg P(x) )$ist ein Theorem, aber in der intuitionistischen Logik nicht beweisbar.

Nehmen Sie als wichtigeres Beispiel irgendein formales System$S$. Dann "$S$ist konsistent bzw$S$ist inkonsistent." ist ein klassisch gültiger Satz, aber nicht intuitiv beweisbar. Wenn man also keine klassische Logik hat, ist man nicht in der Lage, intuitiv wahre Tatsachen anzugeben.