Satz von Diaconescu-Goodman-Myhill

Der Satz von Diaconescu-Goodman-Myhill, benannt nach Radu Diaconescu, N. D. Goodman und J. Myhill, ist ein Satz aus der mathematischen Logik, der zeigt, dass der Satz vom ausgeschlossenen Dritten aus dem Auswahlaxiom hergeleitet werden kann. Der ursprüngliche Beweis von R. Diaconescu aus dem Jahre 1975 behandelte die Situation in Topoi.^[1] Die hier wiedergegebene Version geht auf Goodman und Myhill zurück.^[2] Man spricht daher auch vom Satz von Goodman-Myhill. Manche Autoren sprechen aber auch einfach vom Satz von Diaconescu.

Vor dem Hintergrund der intuitionistischen Zermelo-Fraenkel-Mengenlehre folgt aus dem Auswahlaxiom der Satz vom ausgeschlossenen Dritten.

Das Auswahlaxiom wird üblicherweise mit AC (engl. axiom of choice) bezeichnet und der Satz vom ausgeschlossenen Dritten mit LEM (engl. law of the excluded middle). Damit lautet der Satz von Diaconescu-Goodman-Myhill in Kurzform

${\displaystyle \mathrm {AC} \Rightarrow \mathrm {LEM} }$.

In der intuitionistischen Mathematik wird eine Oder-Aussage ${\displaystyle A\lor B}$ nur dann akzeptiert, wenn man einen Beweis für ${\displaystyle A}$ oder einen Beweis für ${\displaystyle B}$ hat. Eine Begründung für ${\displaystyle A\lor B}$ ohne zu wissen, welche der Aussagen nun wahr ist, wird abgelehnt. Der Satz vom ausgeschlossenen Dritten (LEM) behauptet, dass ${\displaystyle A\lor \neg A}$ für jede Aussage ${\displaystyle A}$ gilt. Die intuitionistische Logik verwendet LEM nicht als Axiom, aber auch nicht seine Negation. Das heißt, sie lässt die Frage offen. Für bestimmte Aussagen ${\displaystyle A}$ lässt sich jedoch ${\displaystyle A\lor \neg A}$ beweisen (eine solche Aussage heißt entscheidbar).

Der Satz von Diaconescu-Goodman-Myhill zeigt daher, dass das Auswahlaxiom für einen Intuitionisten nicht akzeptabel sein kann.^[3] Allerdings wird das Auswahlaxiom auch ganz unabhängig von diesem Satz abgelehnt, denn es behauptet die Existenz gewisser Funktionen, ohne diese vorweisen zu können.

Der kurze Beweis ist intuitionistisch sehr interessant und soll daher kurz besprochen werden.^[4][5]

Man betrachte zu einer beliebigen Aussage ${\displaystyle A}$ die mittels Aussonderungsaxiom definierten Teilmengen von ${\displaystyle \{0,1\}}$

${\displaystyle U=\{\,x\in \{0,1\}\;|\;A\lor (x=0)\,\}\subseteq \{0,1\}}$ und ${\displaystyle V=\{\,x\in \{0,1\}\;|\;A\lor (x=1)\,\}\subseteq \{0,1\}}$,

die definitionsgemäß bewohnt sind. Nach dem Paarmengenaxiom existiert die Menge ${\displaystyle \{U,V\}}$.

Nach dem Auswahlaxiom gibt es eine auf ${\displaystyle \{U,V\}}$ definierte Funktion

${\displaystyle f\colon \{U,V\}\to U\cup V=\{0,1\}}$

mit ${\displaystyle f(U)\in U}$ und ${\displaystyle f(V)\in V}$. Es gilt ${\displaystyle U\cup V=\{0,1\}}$, da ${\displaystyle 0\in U}$, ${\displaystyle 1\in V}$ und ${\displaystyle U,V\subseteq \{0,1\}}$.

Nach Definition der Mengen ${\displaystyle U}$ und ${\displaystyle V}$ bedeutet das

${\displaystyle (f(U)=0\lor A)\land (f(V)=1\lor A)}$

und daher, per Distributivität,

${\displaystyle (f(U)=0\land f(V)=1)\lor A}$.

Aus ${\displaystyle f(U)=0\land f(V)=1}$ folgt ${\displaystyle \neg A}$: Angenommen ${\displaystyle A}$ gälte, so wäre ${\displaystyle U=V}$ und somit

${\displaystyle 0=f(U)=f(V)=1}$,

was ${\displaystyle 0\neq 1}$ widerspricht. Insgesamt ergibt das ${\displaystyle A\lor \neg A}$ wie gewünscht.

Da die Aussage ${\displaystyle A}$ beliebig war, ist damit der Satz vom ausgeschlossenen Dritten aus dem Auswahlaxiom hergeleitet.

Die Definition der Mengen ${\displaystyle U}$ und ${\displaystyle V}$ mutet auf den ersten Blick ungewöhnlich an, da die Aussage ${\displaystyle A}$ nichts mit ${\displaystyle x\in \{0,1\}}$ zu tun hat. Das spielt aber bei der Anwendung des Aussonderungsaxioms keine Rolle. Ist ${\displaystyle A}$ wahr, dann sind die definierenden Bedingungen von ${\displaystyle U}$ und ${\displaystyle V}$ für ${\displaystyle x=0}$ und ${\displaystyle x=1}$ erfüllt und beide Mengen sind gleich ${\displaystyle \{0,1\}}$. Ist ${\displaystyle A}$ falsch, dann ist ${\displaystyle U=\{0\}}$ und ${\displaystyle V=\{1\}}$. Wenn wir aber nicht wissen, ob ${\displaystyle A}$ oder ${\displaystyle \neg A}$ gilt, dann wissen wir nicht, ob ${\displaystyle \{U,V\}}$ aus einem oder aus zwei Elementen besteht.

In der Mengenlehre lässt sich in intuitionistischer Logik für endliche bewohnte Mengen auch ohne Auswahlaxiom eine Auswahlfunktion angeben, die involvierten Mengen ${\displaystyle U}$, ${\displaystyle V}$ und ${\displaystyle \{U,V\}}$ sind aber nach intuitionistischen Begriffen nicht endlich, sondern lediglich endlich aufzählbar. Endlich heißt eine Menge, die gleichmächtig zu ${\displaystyle \{0,\ldots ,n-1\}}$ für eine natürliche Zahl ${\displaystyle n\in \mathbb {N} }$ ist, wohingegen für endlich aufzählbare Mengen lediglich eine endliche Obergrenze existieren muss, sprich, es gibt eine natürliche Zahl ${\displaystyle n}$, sodass sich ${\displaystyle \{0,\ldots ,n-1\}}$ surjektiv auf die Menge abbilden lässt. Die Begriffe sind in klassischer Logik äquivalent, müssen intuitionistisch aber unterschieden werden. Für endlich aufzählbare Mengen lässt sich allgemein intuitionistisch ohne Auswahlaxiom keine Auswahlfunktion finden.

1. ↑ R. Diaconescu: Axiom of choice and complementation, Proc. Amer. Math. Soc. 1975, Band 51, Seiten 175–178
2. ↑ N. D. Goodman, J. Myhill: Choice Implies Excluded Middle, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 1978, Band 24, Seite 461
3. ↑ Jörg Neunhäuserer: Einführung in die Philosophie der Mathematik, Springer-Verlag 2019, ISBN 978-3-662-59554-1, Seite 102
4. ↑ Der Satz von Diaconescu-Goodman-Myhill im Proof Wiki
5. ↑ Der Satz von Diaconescu-Goodman-Myhill auf nLab