Satz von Diaconescu-Goodman-Myhill

Der Satz v​on Diaconescu-Goodman-Myhill, benannt n​ach Radu Diaconescu, N. D. Goodman u​nd J. Myhill, i​st ein Satz a​us der mathematischen Logik, d​er zeigt, d​ass der Satz v​om ausgeschlossenen Dritten a​us dem Auswahlaxiom hergeleitet werden kann. Der ursprüngliche Beweis v​on R. Diaconescu a​us dem Jahre 1975 behandelte d​ie Situation i​n Topoi.[1] Die h​ier wiedergegebene Version g​eht auf Goodman u​nd Myhill zurück.[2] Man spricht d​aher auch v​om Satz v​on Goodman-Myhill. Manche Autoren sprechen a​ber auch einfach v​om Satz v​on Diaconescu.

Formulierung des Satzes

Vor d​em Hintergrund d​er intuitionistischen Zermelo-Fraenkel-Mengenlehre f​olgt aus d​em Auswahlaxiom d​er Satz v​om ausgeschlossenen Dritten.

Das Auswahlaxiom w​ird üblicherweise m​it AC (engl. axiom o​f choice) bezeichnet u​nd der Satz v​om ausgeschlossenen Dritten m​it LEM (engl. law o​f the excluded middle). Damit lautet d​er Satz v​on Diaconescu-Goodman-Myhill i​n Kurzform

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

Bedeutung für den Intuitionismus

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 behauptet, dass ${\displaystyle A\lor \neg A}$ für jede Aussage ${\displaystyle A}$ wahr ist. Intuitionistisch wäre das die Absurdität, dass man für jede Aussage belegen kann, ob sie wahr ist oder ob ihre Negation wahr ist. Daher verzichtet man in der intuitionistischen Logik auf den Satz vom ausgeschlossenen Dritten, allerdings ohne dessen Falschheit zu behaupten, man verwendet ihn einfach nicht.

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.

Beweis des Satzes

Der k​urze Beweis i​st intuitionistisch s​ehr interessant u​nd soll d​aher kurz besprochen werden.[4][5]

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

${\displaystyle U=\{x\in \{0,1\}\mid x=0\lor A\}\subset \{0,1\}}$    und    ${\displaystyle V=\{x\in \{0,1\}\mid x=1\lor A\}\subset \{0,1\}}$,

die definitionsgemäß bewohnt sind, also Elemente haben. Nach dem Paarmengenaxiom existiert ${\displaystyle \{U,V\}}$, und nach dem Auswahlaxiom gibt es eine auf ${\displaystyle \{U,V\}}$ definierte Funktion ${\displaystyle f}$ mit ${\displaystyle f(U)\in U}$ und ${\displaystyle f(V)\in V}$. 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}$.

Beide Fälle der Disjunktion führen zu ${\displaystyle \lnot A\lor A}$:

• Im Fall ${\displaystyle f(U)=0\land f(V)=1}$ gilt ${\displaystyle \lnot A}$ und somit ${\displaystyle \lnot A\lor A}$, denn, angenommen ${\displaystyle A}$, ist ${\displaystyle U=V}$ und somit ${\displaystyle 0=f(U)=f(V)=1}$, was ${\displaystyle 0\neq 1}$ widerspricht.
• Im Fall, dass ${\displaystyle A}$ gilt, gilt natürlich auch ${\displaystyle \lnot A\lor A}$.

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

Bemerkungen zum Beweis

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. Sollten wir von irgendwoher wissen, dass ${\displaystyle A}$ gilt, dann sind offenbar die definierenden Bedingungen von ${\displaystyle U}$ und ${\displaystyle V}$ immer erfüllt, das heißt beide Mengen sind gleich ${\displaystyle \{0,1\}}$. Sollten wir von irgendwoher wissen, dass ${\displaystyle A}$ falsch ist, dann ist offenbar ${\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 lernt man, dass man für endliche Mengen auch ohne Auswahlaxiom eine Auswahlfunktion finden kann. Es stellt sich daher die Frage, ob wir überhaupt das Auswahlaxiom anwenden mussten, denn ${\displaystyle U}$, ${\displaystyle V}$ und ${\displaystyle \{U,V\}}$ sind ja endlich. In klassischer Logik ist das richtig, aber intuitionistisch sind diese Mengen nicht endlich. Endlichkeit einer Menge bedeutet, dass wir eine natürliche Zahl ${\displaystyle n}$ und einen Beweis der Gleichmächtigkeit der Menge zu ${\displaystyle n=\{0,\ldots ,n-1\}}$ vorweisen können. Das ist hier aber nicht gegeben, denn wir können nicht sagen, ob ${\displaystyle U}$ gleichmächtig zu 1 ist, und wir können auch nicht sagen, ob ${\displaystyle U}$ gleichmächtig zu 2 ist. Das gilt genauso für ${\displaystyle V}$ und ${\displaystyle \{U,V\}}$. Daher sind diese Mengen intuitionistisch nicht endlich und wir mussten auf das Auswahlaxiom zurückgreifen.

Einzelnachweise

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