Die Mathe-Redaktion [Home] - Neues auf einen Blick 10.06.2023 03:10 [Neues] [Forum] [Suche] - Registrieren/Login
 
Tools
GliederungspunktLatex-Bibliographie in HTML umwandeln
Mathematik: Was hinter Diagonalbeweisen steckt
Released by matroid on Fr. 16. Mai 2014 19:36:11 [Statistics] [Comments]
Written by Algebrax - 1744 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\begingroup\) Dieser Artikel erklärt die gerade in Logik und Mengenlehre häufig verwendete Methode des Diagonalbeweises; das Ziel ist, allgemein bekannte Beweise wie den von 2^{\kappa}>\kappa ("Die Potenzmenge jeder Menge ist echt größer als diese") besser zu verstehen, da die üblichen Beweise sozusagen "von hinten aufgerollt" werden, sowie weitere interessante Anwendungen (in theoretischer Informatik sowie axiomatischer Mengenlehre) zu sehen.

[Edit]
[To the bottom]

Das "Hauptlemma"

Dieses Lemma kann als Grundlage für einfache Diagonalbeweise angesehen werden: Lemma: Es seien O,I Mengen, sodass es eine Injektion \iota:O\rightarrow I gibt. Ist dann f:O\rightarrow 2^I eine beliebige Funktion, so gibt es ein v\in 2^I mit v\notin\mathrm{im}(f). Hierbei bezeichnet 2^I die Menge aller Bitvektoren über I, d.h., Funktionen I\rightarrow 2=\{0,1\}, und \mathrm{im}(f) das Bild der Funktion f. Beweis. Wir konstruieren einen Bitvektor v, welcher nicht im Bild von f liegen kann, und erklären zuerst ausführlich die Beweisidee. Wir beachten dazu, dass zwei Vektoren genau dann verschieden sind, wenn sie sich in mindestens einer Komponente unterscheiden. Das Ziel wird also sein, v so zu wählen, dass wir für jedes o\in O eine geeignete Komponente aus I finden, sodass sich v von f(o) in dieser Komponente unterscheidet. Diese Komponente lassen wir uns von \iota vorgeben und erklären dann einfach das \iota(o)-te Bit von v als jenes Bit, welches nicht in der \iota(o)-ten Komponente von f(o) steht. Diese einzelnen Festlegungen kommen sich nicht in die Quere, weil \iota injektiv ist. Damit ist die Beweisidee erläutert und der Beweis "psychologisch" abgeschlossen. Wir wollen dennoch das Ganze ordentlich aufschreiben: Für i\in I setze v(i):=\left\{\begin{array}{cl}0, & \text{wenn}\hspace{3pt}i\notin\mathrm{im}(\iota) \\ 1-f(\iota^{-1}(i))(i) & \text{sonst}\end{array}. Wir behaupten, v liegt nicht im Bild von f. Andernfalls gäbe es nämlich ein o\in O mit v=f(o). Aber dann folgt nach Definition von v: v(\iota(o))=1-f(o)(\iota(o))\not=f(o)(\iota(o)), ein Widerspruch. Q.E.D. Wir wollen nun gar nicht lange zögern und gleich zu konkreten Anwendungen dieses Lemmas kommen.
[Edit]

Anwendungen für bekannte Resultate

Wir betrachten zuerst ein Resultat, das wohl jede(r) noch aus den Grundvorlesungen kennt: Satz: Es sei X eine beliebige Menge. Dann gibt es keine Surjektion X\rightarrow\mathcal{P}(X), wobei \mathcal{P}(X) die Potenzmenge von X bezeichnet. Beweis. Wir setzen O:=I:=X, und identifizieren Teilmengen von X=I mit Bitvektoren über I. Dann wird jede Funktion g:X\rightarrow\mathcal{P}(X) zu einer Funktion f:O\rightarrow 2^I, und es genügt zu zeigen, dass f nicht surjektiv sein kann. Das folgt aber nach dem Hauptlemma und der Tatsache, dass es eine Injektion \iota:X\rightarrow X gibt. Wählt man z.B. \iota=\mathrm{id}_X, so sieht man leicht, dass die Teilmenge von X, welche dem konstruierten Bitvektor entspricht, gerade \{x\in X\mid x\notin f(x)\} ist. Q.E.D. An diesem Beweis sieht man auch, woher der Name "Diagonalbeweis" kommt: Man kann sich die zu den Funktionswerten von f assoziierten Bitvektoren über X als Zeilen in einer (X\times X)-Matrix vorstellen. Mit \iota=\mathrm{id}_X orientiert man sich dann an der Diagonale dieser Matrix, um die zur Konstruktion des nicht im Bild liegenden Bitvektors nötigen "Sabotagen" durchzuführen. Auch Cantors zweiter Beweis für die Überabzählbarkeit von \mathbb{R} kann als eine Anwendung des Hauptlemmas angesehen werden: Satz: Die Menge \mathbb{R} der reellen Zahlen ist überabzählbar. Beweis. Angenommen, \mathbb{R} wäre doch abzählbar unendlich. Dann können wir \mathbb{R} in Form einer Folge (y_n)_{n\in\mathbb{N}} ohne Wiederholungen aufzählen, und diese Folge gibt uns auch eine Aufzählung (x_n)_{n\in\mathbb{N}} des offenen Intervalls (0,1). Wir denken uns die Elemente von (0,1) zur Basis 2 entwickelt, wobei wir uns bei den Zahlen der Form \frac{n}{2^k} mit n,k\in\mathbb{N}\setminus\{0\}, welche ja zwei Darstellungen zur Basis 2 besitzen, für jene entscheiden, in der fast alle Ziffern 0 sind. Außerdem nehmen wir o.B.d.A. an, dass x_0=\frac{1}{2} und für i\in\mathbb{N}\setminus\{0,1\} gilt: x_{i^2}=\frac{1}{2^{i^2}} (ist dies nicht der Fall, können wir es durch eine geeignete Umordnung der Folge erreichen). Wir setzen nun O:=I:=\mathbb{N} und identifizieren Zahlen aus (0,1) mit der Folge ihrer dyadischen Nachkommaziffern. Dann wird die Folge (x_n)_{n\in\mathbb{N}} zu einer Funktion f:O\rightarrow 2^I, deren Bild zu jeder Zahl aus (0,1) die entsprechende dyadische Nachkommaziffern-Folge enthält. Aber das kann nicht sein, denn führen wir die Konstruktion aus dem Beweis des Hauptlemmas mit \iota:=\mathrm{id}_{\mathbb{N}} durch, so erhalten wir einen Bitvektor über \mathbb{N}, welcher von allen aufgelisteten Bitvektoren verschieden ist und in dem nach Konstruktion weder alle Einträge 0 sind noch fast alle Einträge 1, sodass er im Bild von f vorkommen müsste, ein Widerspruch. Q.E.D.
[Edit]

Die Unentscheidbarkeit des Halteproblems

In der Rekursionstheorie beschäftigt man sich mit algorithmischen Entscheidbarkeitsfragen. Dabei muss zuerst das Konzept "Algorithmus" formalisiert werden; eine von mehreren paarweise äquivalenten solchen Formalisierungen sind Turing-Maschinen. Ohne hier auf die Details eingehen zu können, erklären wir kurz, was es es damit auf sich hat: Turing-Maschinen besitzen ein (einseitig unendliches) Arbeitsband, welches in eine unendliche Folge von Zellen unterteilt ist. Die Maschine lässt auf dem Band einen Lese- und Druckkopf hin- und herfahren, welcher die Bedruckung der Zellen ändern kann; die Symbole für die Bedruckung stammen dabei aus einem festen endlichen Alphabet, etwa \{§,\ast,0,1\}, wobei § ein spezielles Symbol ist, welches nur auf der linken Randzelle gedruckt ist, nie überschrieben wird und auch nirgends sonst gedruckt wird, und \ast das "uneigentliche Symbol", welches wir formal als Bedruckung für eigentlich unbedruckte Zellen ansehen. Die Definition wird dabei so gewählt, dass Turing-Maschinen komplett deterministische Automaten sind, d.h., wird ihnen nach dem "Hochfahren" ein bestimmter Input, also ein Wort über dem Alphabet \{0,1\} (in Form einer bestimmten Bedruckung des Arbeitsbandes) übergeben, so verläuft die Folge der Arbeitsschritte der Maschine danach stets gleich. Dabei gibt es zwei Möglichkeiten (in Abhängigkeit vom gewählten Input): Die Maschine kann nach endlich vielen Arbeitsschritten anhalten oder für immer weiterlaufen. Wir gehen im Folgenden jedoch von Maschinen aus, welche auf jedem Input halten, und zwar stets entweder mit Output 0 oder 1 (wobei der Output auf eine näher zu definierende Art aus der Bedruckung des Bandes nach dem Halten der Maschine auf dem gegebenen Input abzulesen ist); solche Maschinen nennen wir Entscheidungsmaschinen. Dabei interpretieren wir den Output 0 als Ablehnung und 1 als Annahme des Inputs. Wir nennen eine Teilmenge Q\subseteq\{0,1\}^{\ast} der Menge aller Wörter über dem Alphabet \{0,1\} (solche Q heißen auch Probleme) entscheidbar oder rekursiv, falls es eine Entscheidungsmaschine gibt, welche genau jene Inputs aus \{0,1\}^{\ast} akzeptiert, welche in Q liegen. Turing-Maschinen lassen sich stets durch eine endliche Menge an Information beschreiben (vergleichbar mit dem Quell-Code eines Computerprogramms, welcher dieses ja auch vollständig festlegt), und diese Information lässt sich in Form eines Wortes über \{0,1\} kodieren; die "String-Kodierung" zur Turing-Maschine \mathbb{A} bezeichnen wir mit \ulcorner\mathbb{A}\urcorner. Unser Hauptlemma erlaubt uns nun z.B., Folgendes zu beweisen: Lemma: Die Menge Q_0 := \{\ulcorner\mathbb{A}\urcorner \mid \mathbb{A}\hspace{3pt}\text{lehnt}\hspace{3pt}\ulcorner\mathbb{A}\urcorner\hspace{3pt}\text{ab}\}\subseteq\{0,1\}^{\ast} ist unentscheidbar. Beweis. Es sei O die Menge aller Entscheidungsmaschinen, I:=\{0,1\}^{\ast}, und wir definieren eine Funktion f:O\rightarrow 2^I,\mathbb{A}\mapsto(i\mapsto\mathbb{A}(i)), wobei für i\in I der Ausdruck \mathbb{A}(i) den Output von \mathbb{A} auf i bezeichnet. Als Injektion \iota:O\rightarrow I wählen wir die oben angedeutete String-Kodierungsfunktion. Eine Anwendung des Haupt-Lemmas liefert nun das Gewünschte. Q.E.D. Wir können auch mehrere (endlich viele) Wörter in Form eines einzelnen Wortes, aus dem die ursprünglichen Bestandteile noch "herauslesbar" sind, kodieren. Z.B. können wir für w_1,\ldots,w_n\in\{0,1\}^{\ast} definieren: [w_1,\ldots,w_n]:=w_1^{(2)}01w_2^{(2)}01\cdots w_n^{(2)}, wobei für w\in\{0,1\}^{\ast} die Notation w^{(k)} das Wort bezeichnet, welches man aus w erhält, indem man jedes Vorkommen von b\in\{0,1\} durch b^k (k-fache Konkatenation des Buchstaben b) ersetzt. Das erlaubt es uns, einer Turing-Maschine auch mehrere Informationen zugleich zu übergeben, ohne dafür auf der formalen Ebene eventuell vorher gewählte Definitionen abändern zu müssen. Insbesondere ergibt es nun Sinn, zu fragen, ob die Teilmenge \mathrm{Halt}\subseteq\{0,1\}^{\ast}, bestehend aus den Wörtern der Form [\ulcorner\mathbb{A}\urcorner,i], wobei \mathbb{A} eine Turing-Maschine und i ein Wort über \{0,1\}, auf welchem \mathbb{A} hält, bezeichnet, entscheidbar ist; intuitiv also: Gibt es einen Algorithmus, welcher für jeden Algorithmus und jeden Input für einen solchen in der Lage ist, zu entscheiden, ob dieser andere Algorithmus auf dem Input nach endlich vielen Arbeitsschritten hält? Dies nennt man das Halteproblem, und es gilt: Satz: Das Halteproblem \mathrm{Halt} ist unentscheidbar. Beweisskizze. Dies ist ausnahmsweise kein Diagonalbeweis, sondern wir führen die Aussage auf die Unentscheidbarkeit von Q_0 aus dem vorigen Lemma zurück. Es handelt sich nur um eine Beweisskizze, da wir voraussetzen, dass sich Turing-Maschinen wie der intuitive Algorithmus-Begriff verhalten, was man natürlich in dieser Allgemeinheit gar nicht beweisen kann, weil es keine exakte mathematische Behauptung ist (sondern eine These, die Church-Turing-These). Für einen formalen Beweis müsste man sich überlegen, dass man die beschriebenen intuitiven Schritte auch formal ausführen kann, wozu man eine exakte Definition von "Turing-Maschine" bräuchte. Angenommen, \mathrm{Halt} wäre entscheidbar. Dann könnten wir aber auch Q_0 entscheiden, was natürlich zu einem Widerspruch führt. Eine Entscheidungsmaschine für Q_0 könnte dann nämlich z.B. wie folgt vorgehen: Gegeben ein Input w\in\{0,1\}^{\ast}, entscheide zuerst, ob w überhaupt ein Code einer Turing-Maschine ist (die Kodierung sollte so gewählt sein, dass das möglich ist). Falls nicht, lehne ab. Falls schon, lasse eine Entscheidungsroutine für \mathrm{Halt} auf dem Input [w,w] laufen und warte, bis diese hält. Antwortet sie ablehnend, so lehne ebenfalls ab, sonst simuliere die durch w beschriebene Maschine auf dem Input w (das ist möglich; Stichwort: universelle Turing-Maschine) und warte, bis die Simulation hält, um den Output abzulesen. Ist dieser von 0 verschieden, so lehne ab, sonst akzeptiere. Q.E.D.
[Edit]

Komplexitätstheorie: Diagonalisierung gegen die Zeit

Die Methode aus dem Beweis des Hauptlemmas ist durchaus ausbaufähig, wie wir in diesem Abschnitt demonstrieren wollen. Wir wechseln nun von der Rekursions- in die Komplexitätstheorie, d.h., wir betrachten von nun an nur noch entscheidbare Probleme und die Frage ist, wie schnell (in Abhängigkeit von der Input-Länge) eine Entscheidungsmaschine für das Problem halten kann. Dabei orientieren wir uns an der Darstellung in diesem Skript. Insbesondere betrachten wir auch Mehrband-Turing-Maschinen, also Turing-Maschinen, welche mehr als ein Arbeitsband haben, mit einem Lese- und Druckkopf auf jedem Arbeitsband. Definition: Es sei \mathbb{A} eine Turing-Maschine, welche auf allen Inputs hält, t:\mathbb{N}\rightarrow\mathbb{N}. Wir sagen, \mathbb{A} ist t-zeitbeschränkt, falls für alle i\in\{0,1\}^{\ast} gilt: t_{\mathbb{A}}(i)\leq t(|i|). Hierbei bezeichnet t_{\mathbb{A}}(i) die Zahl der Arbeitsschritte, die \mathbb{A} auf i vor dem Halten ausführt und |i| die Länge des Wortes i. Mit \mathrm{TIME}(t) bezeichnen wir die Menge aller Probleme Q\subseteq\{0,1\}^{\ast}, sodass es eine Konstante c\in\mathbb{N} und eine c\cdot t-zeitbeschränkte Entscheidungsmaschine für Q gibt. Beispielsweise ist die Komplexitätsklasse \mathrm{P} definiert als die Menge aller Probleme, welche "in polynomialer Zeit entscheidbar sind", d.h., \mathrm{P} ist die Vereinigung der Mengen \mathrm{TIME}(t), wobei t alle Polynomfunktionen \mathbb{N}\rightarrow\mathbb{N} (mit natürlichen Koeffizienten) durchläuft. Wir wollen nun zeigen, dass unter bestimmten Gutartigkeitsvoraussetzungen für t:\mathbb{N}\rightarrow\mathbb{N} gilt, dass es Probleme in \mathrm{TIME}(t^6) gibt, welche nicht in \mathrm{TIME}(t) liegen. Dabei werden wir die zweite Aussage ausführlich beweisen (da es sich dabei um ein Diagonalargument handelt), und den Beweis der ersten Aussage kurz skizzieren. Zuerst noch eine Definition: Definition: Eine Funktion t:\mathbb{N}\rightarrow\mathbb{N} heißt zeitberechenbar, falls es ein c\in\mathbb{N} und eine c\cdot t-zeitbeschränkte Turing-Maschine \mathbb{A} gibt, welche t "berechnet", d.h., auf jedem Input der Form \mathrm{bin}(n), n\in\mathbb{N}, \mathrm{bin}(t(n)) ausgibt; hierbei bezeichnet \mathrm{bin}(k) für k\in\mathbb{N} die Binär-Kodierung von n, d.h., jenen String, der aus den Ziffern der dyadischen Entwicklung von n besteht. Alle aus Sicht der Zeit-Komplexitätstheorie "interessanten" Funktionen sind zeitberechenbar, z.B. alle Polynomfunktionen mit natürlichen Koeffizienten, alle Exponentialfunktionen zu natürlichen Basen, die Faktorielle-Funktion, die (auf die nächstkleinere ganze Zahl abgerundete) Logarithmus-Funktion usw. Wir werden nun zeigen: Satz: ("Schwacher Zeithierarchiesatz") Es sei t:\mathbb{N}\rightarrow\mathbb{N} zeitberechenbar und für alle n\in\mathbb{N} gelte t(n)\geq n. Dann ist \mathrm{TIME}(t^6)\setminus\mathrm{TIME}(t)\not=\emptyset. Die Bezeichnung "schwach" kommt daher, dass sich dieses Resultat wesentlich verschärfen lässt, siehe das oben angeführte Skript. Bevor wir mit dem eigentlichen Beweis (bzw. der Beweisskizze) beginnen, einige Vorüberlegungen (welche uns auf natürliche Weise zu dem Beweis führen): Wir können jede Mehrband-Turing-Maschine durch eine Turing-Maschine mit nur einem Arbeitsband ersetzen, welche das gleiche "Output-Verhalten" aufweist, d.h.: Sie hält genau auf den Inputs, auf denen die ursprüngliche Mehrband-Maschine hält, und zwar mit dem gleichen Output. Aus Sicht der Komplexitätstheorie zahlen wir dafür jedoch einen Preis: Ist die Mehrband-Maschine t-zeitbeschränkt, so ist die Einband-Maschine nur c\cdot t^2-zeitbeschränkt für eine geeignete Konstante c\in\mathbb{N}. Gibt es also zu einer Teilmenge Q\subseteq\{0,1\}^{\ast} eine \mathrm{O}(t)-zeitbeschränkte Entscheidungsmaschine \mathbb{A} (eventuell mit mehreren Arbeitsbändern; \mathrm{O} ist hier das Landau-Symbol), so gibt es eine c\cdot t^2-zeitbeschränkte Einband-Entscheidungsmaschine \mathbb{B} für Q. Wir können diese auch so "aufblähen" (intuitiv könnte man sich vorstellen, wir vergrößern den Programm-Quellcode um zusätzliche, auf das Ergebnis keinen Einfluss nehmende Schleifen), dass der zugehörige Code \ulcorner\mathbb{B}\urcorner über \{0,1\} Länge mindestens c hat, dann benötigt (nach der Annahme t(n)\geq n für alle n) diese Maschine insbesondere auf dem Input \ulcorner\mathbb{B}\urcorner höchstens t(|\ulcorner\mathbb{B}\urcorner|)^3 Arbeitsschritte. Mit dieser Überlegung haben wir nicht nur die multiplikative Konstante, welche bereits zu Beginn in der \mathrm{O}(t)-Zeitschranke für die Mehrband-Turing-Maschine enthalten war, geschlagen, wir müssen jetzt auch nur noch gegen Einband-Entscheidungsmaschinen diagonalisieren; warum dies wichtig ist, sehen wir gleich in der Beweisskizze zum schwachen Zeithierarchiesatz. Wir müssen also eine Teilmenge Q\subseteq\{0,1\}^{\ast} finden, welche zwar in Zeit \mathrm{O}(t^6) entscheidbar ist (von einer Turing-Maschine mit eventuell mehreren Arbeitsbändern), jedoch nicht in Zeit \mathrm{O}(t). Nach den Überlegungen von eben gilt das insbesondere dann, wenn es keine Einband-Maschine \mathbb{B} gibt, welche das Problem entscheidet und auf dem eigenen Code höchstens Zeit t(|\ulcorner\mathbb{B}\urcorner|)^3 benötigt. Wir orientieren uns an der Idee aus dem Beweis des Hauptlemmas: Für jede Einband-Entscheidungsmaschine \mathbb{A} wollen wir einen injektiv von \mathbb{A} abhängigen Input haben (wieder \ulcorner\mathbb{A}\urcorner), welcher uns als "Beweis" dafür dient, dass \mathbb{A} keine solche Maschine \mathbb{B} ist. Dazu setzen wir wieder O als die Menge aller Entscheidungsmaschinen fest sowie I:=\{0,1\}^{\ast}. Die Einträge der (O\times I)-Matrix, die wir nun betrachten, sind aber nicht einfach nur die jeweiligen Outputs der Entscheidungsmaschinen, sondern Paare, deren erster Eintrag der entsprechende Output und deren zweiter Eintrag die Zahl der Arbeitsschritte der Entscheidungsmaschine auf dem Input ist. Wieder werden wir zeilenweise "sabotieren": Gegeben eine Einband-Entscheidungsmaschine \mathbb{A}, betrachte den (\mathbb{A},\ulcorner\mathbb{A}\urcorner)-ten Eintrag (\mathbb{A}(\ulcorner\mathbb{A}\urcorner),t_{\mathbb{A}}(\ulcorner\mathbb{A}\urcorner)) der Matrix. ist t_{\mathbb{A}}(\ulcorner\mathbb{A}\urcorner)>|\ulcorner\mathbb{A}\urcorner|^3, so ist dies bereits Beweis genug, dass \mathbb{A} nicht die gesuchte Maschine \mathbb{B} ist, und wir müssen nichts speziell für Q festlegen; einfach, damit Q wohldefiniert ist, sagen wir, wir nehmen solche \ulcorner\mathbb{A}\urcorner stets zu Q dazu. Ist dagegen t_{\mathbb{A}}(\ulcorner\mathbb{A}\urcorner)\leq|\ulcorner\mathbb{A}\urcorner|^3, so spricht die Zeit, die \mathbb{A} auf seinem eigenen Code benötigt, nicht gegen es, und wir sabotieren wieder durch "Flippen von Bits": In diesem Fall nehmen wir \ulcorner\mathbb{A}\urcorner genau dann zu Q dazu, wenn der Output von \mathbb{A} darauf 0 ist. Zusammenfassend wird Q also zu dem folgenden Problem: Q=\{\ulcorner\mathbb{A}\urcorner\mid\mathbb{A}\hspace{3pt}\text{ist eine Einband-Entscheidungsmaschine, die}\hspace{3pt}\ulcorner\mathbb{A}\urcorner\hspace{3pt}\text{nicht in Zeit}\hspace{3pt}t(|\ulcorner\mathbb{A}\urcorner}|)^3\hspace{3pt}\text{akzeptiert.}\}. Nach Konstruktion kann Q nicht in Zeit \mathrm{O}(t) entschieden werden, jedoch in Zeit \mathrm{O}(t^6), und zwar durch Verwendung einer universellen Turing-Maschine (mit mehreren Arbeitsbändern), welche in der Lage ist, jede Einband-Turing-Maschine in quadratischer Zeit zu simulieren (so eine Maschine gibt es, o.B.). Der Input, der dieser Maschine zu übergeben ist, ist dann [\ulcorner\mathbb{A}\urcorner,t(|\ulcorner\mathbb{A}\urcorner|)^3], und dies ist nach der Zeitberechenbarkeit von t in kubischer Zeit (in der ursprünglichen Inputlänge |\ulcorner\mathbb{A}\urcorner|) berechenbar, hat also insbesondere kubische Länge in diesem Input. Die Simulation benötigt dann quadratische Zeit in dieser kubischen Länge, also sextische Zeit in der ursprünglichen Inputlänge. Q.E.D.
[Edit]

Diagonalisierung oberhalb der Diagonale und die Grenzen von ZFC

Wir schließen diesen Artikel mit einer weiteren Variation der ursprünglichen Diagonalmethode, diesmal mit einer Anwendung in der Mengenlehre; Interessierte finden in Kenneth Kunens "Set Theory" mehr dazu. Zuerst eine Definition: Definition: Es seien f,g:\mathbb{N}\rightarrow\mathbb{N}. (1) Wir schreiben f\leq^{\ast}g und sagen "g dominiert f", falls für fast alle (d.h., alle bis auf endlich viele) n\in\mathbb{N} gilt: f(n)\leq g(n). (2) Eine Familie \mathcal{F} von Funktionen \mathbb{N}\rightarrow\mathbb{N} heißt dominierend, falls es zu jeder Funktion f:\mathbb{N}\rightarrow\mathbb{N} eine Funktion g\in\mathcal{F} gibt, sodass f\leq^{\ast}g. (3) Mit \mathfrak{d} (englisch: "dominating number") bezeichnen wir die kleinste Kardinalzahl \kappa, sodass es eine dominierende Familie der Größe \kappa gibt. (4) Eine Familie \mathcal{F} von Funktionen \mathbb{N}\rightarrow\mathbb{N} heißt unbeschränkt, falls es keine Funktion g:\mathbb{N}\rightarrow\mathbb{N} gibt, welche alle f\in\mathcal{F} dominiert. (5) Mit \mathfrak{b} (englisch: "bounding number") bezeichnen wir die kleinste Kardinalzahl \kappa, sodass es eine unbeschränkte Familie der Größe \kappa gibt. Wir zeigen nun: Satz: Es gilt \aleph_1\leq\mathfrak{b}\leq\mathfrak{d}\leq 2^{\aleph_0}. Dabei sind alle \leq bis auf das erste trivial; für das zweite beachte, dass jede dominierende Familie auch unbeschränkt ist (wäre g eine obere Schranke im Sinne von \leq^{\ast}, so könnte die Familie g+1 nicht dominieren), und für das letzte können wir einfach \mathcal{F}:=\mathbb{N}^{\mathbb{N}} setzen; das ist trivialerweise eine dominierende Familie, und die Größe von \mathcal{F} ist nach Definition \aleph_0^{\aleph_0}, und das ist nach unten beschränkt durch 2^{\aleph_0}, aber auch nach oben beschränkt durch (2^{\aleph_0})^{\aleph_0}=2^{\aleph_0\cdot\aleph_0}=2^{\aleph_0}, also gleich 2^{\aleph_0}. Interessanter dagegen ist die Behauptung, dass eine unbeschränkte Familie notwendig überabzählbar ist. Wir zeigen dies, wie auch die Überabzählbarkeit von \mathbb{R}, indirekt, indem wir zu jeder abzählbaren Menge von Funktionen \mathbb{N}\rightarrow\mathbb{N} eine Funktion konstruieren, welche jede der angeführten Funktionen dominiert: Beweis des Satzes. Es sei also eine beliebige Folge (f_n)_{n\in\mathbb{N}} von Funktionen \mathbb{N}\rightarrow\mathbb{N} gegeben. Wiederum folgen wir einer ähnlichen Idee: Wir wollen eine Funktion g so definieren, dass wir schließlich für jedes n\in\mathbb{N} einen Beweis haben, dass g die Funktion f_n dominiert. Dieser muss in der Angabe einer koendlichen Teilmenge A_n\subseteq\mathbb{N} mit f_n(k)\leq g(k) für alle k\in A_n bestehen. Wir setzen A_n:=\{k\in\mathbb{N}\mid k\geq n\} und behaupten, dass es zu dieser Wahl von A_n so eine Funktion g gibt. Dazu fragen wir uns: Worauf müssen wir dann für ein fixes k\in\mathbb{N} bei der Definition von g(k) achten? Offenbar darauf, dass für alle n mit k\geq n gilt, dass f_n(k)\leq g(k) ist. Aber das sind nur endlich viele n (entsprechend den Einträgen auf und über der Diagonale der entsprechenden Matrix), sodass wir g(k):=\mathrm{max}\{f_n(k)\mid n\leq k\} setzen können und fertig sind. Q.E.D. Die exakten Werte von \mathfrak{b} und \mathfrak{d} sind über ZFC unentscheidbar, wie man mit Forcing zeigen kann (Stichwort: Martins Axiom).
[Edit]
\(\endgroup\)
[Show outline only]
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Write a comment

Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Mathematik :: automatisch eingefügt und unbearbeitet :
Was hinter Diagonalbeweisen steckt [von Algebrax]  
Dieser Artikel erklärt die gerade in Logik und Mengenlehre häufig verwendete Methode des Diagonalbeweises; das Ziel ist, allgemein bekannte Beweise wie den von 2^{kappa}>kappa ("Die Potenzmenge jeder Menge ist echt größer als diese") besser zu verstehen, da die üblichen Beweise sozusagen "von hinten
[Edit]
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]
 


 
 
Aufrufzähler 1744
 
Aufrufstatistik des Artikels
Insgesamt 34 externe Seitenaufrufe zwischen 2014.06 und 2021.12 [Anzeigen]
DomainAnzahlProz
http://google.de2161.8%61.8 %
https://google.com720.6%20.6 %
https://google.de38.8%8.8 %
http://google.ru25.9%5.9 %
http://isearch.avg.com12.9%2.9 %

Häufige Aufrufer in früheren Monaten
Insgesamt 27 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2014-2017 (15x)http://google.de/url?sa=t&rct=j&q=
2020-2021 (7x)https://google.com/
201511-11 (5x)http://google.de/url?sa=t&source=web&cd=8&rct=j&q=diagonalbeweis


[Top of page]



"Mathematik: Was hinter Diagonalbeweisen steckt" | 4 Comments
The authors of the comments are responsible for the content.

Re: Was hinter Diagonalbeweisen steckt
von: Algebrax am: Fr. 16. Mai 2014 19:52:50
\(\begingroup\)Wie ich sehe, zeigt es die Titel, die ich den einzelnen Abschnitten gegeben habe, nicht an. Könnte mir bitte jemand sagen, wie man das korrigieren kann? Mit lieben Grüßen, Alex\(\endgroup\)
 

Re: Was hinter Diagonalbeweisen steckt
von: Ex_Mitglied_477 am: Mo. 19. Mai 2014 22:14:30
\(\begingroup\)Du mußt die Titel von Hand dazuschreiben. Für eine Trennlinie, falls gewünscht, könntest Du $\hline$ verwenden. \(\endgroup\)
 

Re: Was hinter Diagonalbeweisen steckt
von: Martin_Infinite am: Sa. 24. Mai 2014 22:52:29
\(\begingroup\)Mir ist erst mit arXiv:math/0305282 klargeworden, was wirklich hinter allen Diagonalargumenten steckt: Lawveres Fixpunktsatz.\(\endgroup\)
 

Re: Was hinter Diagonalbeweisen steckt
von: Algebrax am: Mo. 26. Mai 2014 15:16:48
\(\begingroup\)Danke für eure Kommentare, cis und Martin_Infinite! @Martin: Ich finde es interessant, dass ein affirmatives Resultat wie Lawveres Fixpunktsatz ("Es gibt einen Fixpunkt.") ebenfalls als Grundlage für Diagonalbeweise, die ja normalerweise für negative Resultate ("Es gibt kein Objekt mit einer bestimmten Eigenschaft.") verwendet werden, angesehen werden kann. Übrigens: Der Beweis für den Fixpunktsatz aus $n$Lab ist von "syntaktischer" Natur (finde einen Ausdruck, der bei geeigneter Substitution zu einem gewünschten Ergebnis führt), wie Diagonalbeweise üblicherweise auch präsentiert werden; ich habe mich in diesem Artikel bewusst für eine "semantische" Herangehensweise entschieden, weil ich diese intuitiver finde (was aber natürlich Geschmackssache ist). Mit lieben Grüßen, Alex\(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]