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. Die hier wiedergegebene Version geht auf Goodman und Myhill zurück. Man spricht daher auch vom Satz von Goodman-Myhill. Manche Autoren sprechen aber auch einfach vom Satz von Diaconescu.
Formulierung des Satzes Bearbeiten
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
Bedeutung für den Intuitionismus Bearbeiten
In der intuitionistischen Mathematik wird eine Oder-Aussage nur dann akzeptiert, wenn man einen Beweis für oder einen Beweis für hat. Eine Begründung für ohne zu wissen, welche der Aussagen nun wahr ist, wird abgelehnt. Der Satz vom ausgeschlossenen Dritten (LEM) behauptet, dass für jede Aussage 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 lässt sich jedoch 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. 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 Bearbeiten
Der kurze Beweis ist intuitionistisch sehr interessant und soll daher kurz besprochen werden.
Man betrachte zu einer beliebigen Aussage die mittels Aussonderungsaxiom definierten Teilmengen von
die definitionsgemäß bewohnt sind. Nach dem Paarmengenaxiom existiert die Menge .
Nach dem Auswahlaxiom gibt es eine auf definierte Funktion
mit und . Es gilt , da , und .
Nach Definition der Mengen und bedeutet das
und daher, per Distributivität,
Aus folgt : Angenommen gälte, so wäre und somit
was widerspricht. Insgesamt ergibt das wie gewünscht.
Da die Aussage beliebig war, ist damit der Satz vom ausgeschlossenen Dritten aus dem Auswahlaxiom hergeleitet.
Bemerkungen zum Beweis Bearbeiten
Die Definition der Mengen und mutet auf den ersten Blick ungewöhnlich an, da die Aussage nichts mit zu tun hat. Das spielt aber bei der Anwendung des Aussonderungsaxioms keine Rolle. Ist wahr, dann sind die definierenden Bedingungen von und für und erfüllt und beide Mengen sind gleich . Ist falsch, dann ist und . Wenn wir aber nicht wissen, ob oder gilt, dann wissen wir nicht, ob 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 , und sind aber nach intuitionistischen Begriffen nicht endlich, sondern lediglich endlich aufzählbar. Endlich heißt eine Menge, die gleichmächtig zu für eine natürliche Zahl ist, wohingegen für endlich aufzählbare Mengen lediglich eine endliche Obergrenze existieren muss, sprich, es gibt eine natürliche Zahl , sodass sich 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.
Einzelnachweise Bearbeiten
- R. Diaconescu: Axiom of choice and complementation, Proc. Amer. Math. Soc. 1975, Band 51, Seiten 175–178
- N. D. Goodman, J. Myhill: Choice Implies Excluded Middle, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 1978, Band 24, Seite 461
- Jörg Neunhäuserer: Einführung in die Philosophie der Mathematik, Springer-Verlag 2019, ISBN 978-3-662-59554-1, Seite 102
- Der Satz von Diaconescu-Goodman-Myhill im Proof Wiki
- Der Satz von Diaconescu-Goodman-Myhill auf nLab