Berechenbarkeit und Kreativität (TODO)

Beweise für unendliche Mengen

TODO: Beweismöglichkeiten für abzählbare Mengen (zB.: sortieren, surjektive Abbildungen aufstellen, ...), Widerspruchsbeweise für Abzählbarkeit übersichtlich in einer Grafik darstellen!

abzählbar unendliche Mengen = Menge ist gleichmächtig zu den natürlichen Zahlen

Vorstellungsvermögen: Wenn man als Beispiel eine bijektive Abbildung zählt und bei natürlicher zahl (1 Billion) und der dazugehörigen Zahl der Vergleichsmenge (40) ankommt, dann könnte man erstmal denken, dass Vergleichsmenge weniger mächtig ist, weil 40 kleiner als 1 Billion, aber es geht um die ANZAHL DER ELEMENTE (KARDINALITÄT) BEIDER MENGEN und dahingehend sind beide gleich.

Beweis über eine surjektive Abbildung.

z.B.: Beweis, dass ganze Zahlen (Z) abzählbar unendlich sind:

1 -> 1

2 -> -1

3 -> 2

4 -> -2

5 -> 3

...

Beweis, dass gerade Zahlen (G) abzählbar unendlich sind:

1 -> 2

2 -> 4

3 -> 6

4 -> 8

...

Zudem gilt: G Teilmenge von N

Beweis, dass rationale Zahlen (Q) abzählbar unendlich sind: Sequenz (Reihenfolge) der bijektiven Abbildung zwischen N und Q kann mithilfe von Cantor'sches Diagonalverfahren 1. Art bestimmt werden.

Beweis, dass M1 vereinigt M2 abzählbar unendlich sind, wobei M1 und M2 jeweils abzählbar unendliche Mengen sind:

Möglichkeit 1: Bestimmung der Sequenz der Abbildung über Cantor' Diagonalverfahren 1. Art

Möglichkeit 2:

1 -> M1(1. Element)

2 -> M2(1. Element)

3 -> M1(2. Element)

4 -> M2(2. Element)

5 -> M1(3. Element)

...

Eine weitere Möglichkeit, um eine abzählbar unendliche Menge zu beweisen ist das Sortieren der Elemente (Wörter). Ein mögliches Sortierkriterium wäre bei einer Wortmenge die Länge der einzelnen Wörter. (längenlexikografische Ordnung)

überabzählbar unendliche Mengen:

siehe Cantor'sches Diagonalverfahren 2. Art

Idee dahinter: Man hat eine beliebige Menge an Wörtern. An dieser Menge wird die Hauptdiagonale angelegt. Anschließend wird ein neues Wort erzeugt, indem für (n, a) das Zeichen geändert wird. Die Änderung des Zeichens für das neue Wort muss dabei einer Regel erfolgen, die auf Basis des aktuellen Zeichens ein anderes Zeichen des Alphabets verwendet.

(x, y) : (Zeile, Spalte); n : durchlaufende Zeile; a : Spalte innerhalb der Hauptdiagonale

Beispiel:

A = {a, b}

Regel: wenn a -> b; wenn b -> a

z = Zeichen; w = Wort; wn = neues Wort

Auf Basis dessen kann man als Wort auch ein Zahlwort verwenden. Um zu beweisen, dass die reellen Zahlen (R) überabzählbar unendlich sind, wurde dieses Verfahren verwendet. Da von jedem Zahlwort eine Ziffer verändert wird, erhält man ein neues Zahlwort.

FRAGE: Würde man nicht aber auch immer ein unterschiedliches Zahlwort erhalten, wenn man die rationalen Zahlen auf das Cantor'sche 2. Diagonalverfahren anwendet?

Idee: Vielleicht??, aber alle rationalen Zahlen können neben der Dezimalschreibweise auch als p/q dargestellt werden, wobei sowohl p als auch q in p/q natürliche Zahlen sind.

Entscheidbarkeit

Bereich Mengen: Entscheidbarkeit, Bereich Funktionen: Berechenbarkeit

Was ist damit gemeint??

Es wird eine Funktion definiert, welche Berechungen vornimmt und die Ausgabe-Werte aufzählt (also als Menge zurückgibt). Anhand der ausgegebenen Menge kann eine weitere Funktion (=chi-Funktion/charakteristische Funktion) entscheiden, ob ein bestimmtes Element in dieser Menge enthalten ist. Sie nimmt ein Vergleichselement/Vergleichswort w als Parameter auf. Iteriert über jedes Element der Ausgabe-Menge und gibt wahr aus, sobald w in Menge vorkam, ansonsten falsch. Ist die Ausgabe-Menge abzählbar unendlich, kann zum Iterieren der Menge Streams genutzt werden. Das Vergleichswort w kann aus der Wortmenge A* stammen, wenn man jedes mögliche Wort des Alphabets A testen will.

Beispiel:

Berechnungsfunktion: Zähle alle Primzahlen ab der Zahl n auf, gib alle Wörter der Sprache aus, gib alle Personen des Studiengangs n aus, ...

chi-Funktion: Iteriere, ob die Zahl 67 in der Primzahlmenge ab 35 enthalten ist; Iteriere, ob Max Mustermann in der Personenmenge des Studiengangs xyz enthalten ist.

Die ausgegebene Menge der Berechnungsfunktion heißt auch aufzählbar, da die Menge abzählbar und die Funktion zu dieser Menge berechenbar sein muss.

Frage: Wieso kann man mithilfe dieser charakteristischen Funktion für eine abzählbar unendliche Menge entscheiden, ob ein Element (Wort) innerhalb dieser Menge nicht vorkommt? (also die chi-Funktion false zurückgibt?)

Antwort: Weil man bei einer abzählbar unendlichen Menge die Elemente (Wörter) sortieren kann (z.B.: längenlexikografisch). Beispiel: Wenn die Menge absteigend nach Länge der Wörter sortiert sind und es in der Menge kein Wort mit der selben Länge des Vergleichsworts gibt, kann false ausgegeben werden.

semi-entscheidbare Menge: Diese charakteristische Funktion ist ähnlich zu der für entscheidbare Mengen mit dem Unterschied, dass die Funktion weiterläuft, wenn das Vergleichselement nicht gefunden wurde anstatt dass false ausgegeben wird.

Beweis, dass Halteproblem semi-entscheidbar ist:

Ansatz: Fibonacci-Zahlwörter deswegen entscheidbar, weil sortierbar

ÜA: Die Menge G der Gitterpunkte (0, 0),(0, 1), . . . einer x-y-Ebene ist aufzählbar.

bijektive Abbildung f von N auf G mithilfe von Cantor'schem Diagonalisierungsverfahren 1. Art als Sortierverfahren: (beweist Abzählbarkeit von G und G lässt sich auch aufzählen)

1 -> (0,0)

2 -> (0,1)

3 -> (1,0)

4 -> (2,0)

5 -> (1,1)

6 -> (0,2)

...

Ordnungsrelation:

Indexfunktion i(x, y) bildet (x,y) von G bijektiv auf N ab. (Beispiel: i((0,2)) -> 6)

Beweise für (Ab/Auf)-zählbarkeit, (Semi)entscheidbarkeit

Satz 1: Eine Menge M ist genau dann aufzählbar, wenn sie semi-entscheidbar ist.

Teil 1: M aufzählbar -> M semi-entscheidbar

Wir wissen, dass wir eine aufzählbare Menge M haben und wollen herausfinden, ob wir daraus eine chi-strich-Funktion erzeugen können

da für M keine "festgeschriebene" Menge vorhanden ist, sondern nur Aufzählfunktion f, kann f(0), f(1), ... anstelle für M in chi-strich-Funktion verwendet werden

Teil 2: M semi-entscheidbar -> M aufzählbar

Wir wissen, dass wir eine chi-strich-Funktion haben und wollen wissen, ob wir daraus eine aufzählbare Menge M erzeugen können. Man will also die Ausgabe von chi-strich verwenden, um zu wissen, ob ein Element von w aus A* zu M gehört.

Wenn wir statt chi-Strich eine chi-Funktion hätten, könnten wir jedes Wort w aus der Wortmenge A* in die chi-Funktion als Parameter eingeben und im Falle einer TRUE-Ausgabe das Wort w in die Menge M hinzufügen und bei einem FALSE dieses Wort w ignorieren.

Bei chi-Strich ist es schwieriger, da anstelle von FALSE chi-strich hält.

Möglichkeit nach Vorlesungsfolie: Erstellen einer Paarungsfunktion (x = Elementnummer x aus A*, y = Abbruch nach Zeit y), welche für jedes (x, y) die Ausgabe z einzigartig codiert.

TODO: Herleitung (x und y aus z) nochmal anschauen und verinnerlichen

FRAGE: Alternative Möglichkeit: Anstelle von Paarungsfunktion wird eine Paar-Tabelle aufgestellt (Key = Wort aus A*, Value = Abbruch nach Zeit <value>). Sobald ein Wort w aus A* in mit chi-Strich getestet wird, wird für dieses w aus der Paar-Tabelle die Zeit entnommen. Die Aufzählfunktion f nimmt also ein Wort w aus A* entgegen, entnimmt für w die Zeit aus der Tabelle und testet bis zu dieser Zeit. Wenn bis zu dieser Zeit TRUE ausgegeben wird, wird w in die Menge M aufgelistet???</value>

Satz 2:

Jede Teilmenge einer (beliebigen) abzählbaren Menge ist abzählbar, aber

FALSCH ist: Jede Teilmenge einer (beliebigen) aufzählbaren Menge ist aufzählbar.

Teil 1: M Teilmenge von M2; M2 abzählbar; M abzählbar?

Im Grunde ist "M Teilmenge von M2" schon der Beweis, weil wenn M2 abzählbar ist, dann ist die Teilmenge M auch abzählbar.

Wenn es zwischen N und M2 mindestens eine Surjektion gibt, dann gibt es diese auch zwischen N und M. (siehe Mengenbild auf Vorlesungsfolie 4 S. 23)

FRAGE für 26.4: Man kann hier als Teilmenge auch eine Random-Menge nehmen, die keine Sortierung hat

Teil 2: M Teilmenge von M2; M2 aufzählbar; M aufzählbar?

FRAGE

Ich würde anders beweisen und bekomme im Gegensatz zur Vorlesungsfolie auch raus, dass M aufzählbar ist:

Hat man eine Aufzählfunktion f(start, end) für die Menge M2, können für start und end die Grenzen der Teilmenge M angegeben werden. Die in f enthaltene Rechenvorschrift ist die gleiche wie ohne Angabe der Grenzen -> somit ist f auch für M berechenbar. Die Abzählbarkeit wurde in Teil 1 bereits bewiesen.

Antwort zu dieser Möglichkeit: Durch exakte Eingrenzung zwischen start und end hätte man endliche Menge. Man kann aber nicht von endlicher Menge auf unendlicher Menge schließen.

FRAGE

Abseits meiner Herangehensweise verstehe ich von der Vorlesungsfolie auch die Aussage nicht, dass aus der Aufzählbarkeit einer Menge nur die Semi-Entscheidbarkeit folgt. Wenn eine Menge M aufzählbar ist, dann ist sie auch abzählbar - d.h. man kann die Menge M (z.B.: längenlexikografisch aufsteigend) sortieren. Bei der Entscheidung, ob das Wort w zur Menge M gehört, kann sofort mit FALSE geantwortet werden, sobald das Wort w in der sortierten Wortmenge A* nicht mehr gefunden werden kann (weil z.B. bereits alle Wörter mit der Wortlänge 3 gefunden worden sind und w eine Länge von 3 hat)

FRAGE für 26.4: Reicht das als Beweis aus?

Antwort: Die Teilmenge M aus M2 kann eine zufällig gewählte Teilmenge sein und muss daher nicht sortierbar sein.

Dasselbe gilt für M als Teilmenge von A*. A* ist zwar längenlexikografisch sortierbar, M kann aber auch eine zufällig gewählte Teilmenge aus A* sein.

TODO: ...

Satz 3: Wenn die Menge M entscheidbar ist, dann ist M aufzählbar. Die Umkehrung dieses Satzes gilt nicht!

Teil 1: M entscheidbar -> M aufzählbar?

chi-Funktion für M existiert

FRAGE für 26.4: Frage nach Abzählbarkeit wichtig? Ist M abzählbar (gibt es für M eine Surjektion zwischen N und M/ist M sortierbar)? M ist abzählbar, da chi nur mit abzählbaren Mengen arbeiten kann.

Warum kann chi nur mit abzählbaren Mengen arbeiten? Da man bei überabzählbar unendlichen Mengen nicht wissen kann, ob w aus A* auch in M enthalten ist. Bei abzählbar unendlichen Mengen kann man mithilfe einer Ordnung/Sortierung u.a. darüber entscheiden, dass w nicht mehr in M vorkommen kann.

Gibt es eine Aufzählfunktion f für Menge M? Da es eine charakteristische (Chi)-Funktion im Verhältnis zur bildbaren Wortmenge A* gibt, gibt es eine Aufzählfunktion f. Man kann also jedes Wort w von A* in chi eingeben und sobald WAHR rauskommt, wird w in die Menge M hinzugefügt.

Teil 2: M aufzählbar -> M entscheidbar?

FRAGE

siehe Problem unter Satz 2 Teil 2, dass ich nicht verstehe, warum aus Aufzählbarkeit nur Semi-Entscheidbarkeit folgt.

Satz 4: Eine Menge M aus A* ist entscheidbar genau dann, wenn M und A* \ M (Komplementmenge) aufzählbare Mengen sind.

Teil 1: M entscheidbar -> M und A* \ M aufzählbar

Es existiert eine chi-Funktion für M.

Zur Aufzählbarkeit:

Ist M abzählbar? M ist abzählbar, da chi nur mit abzählbaren Mengen arbeiten kann.

Hat M eine Aufzählfunktion f? Da es eine charakteristische (Chi)-Funktion im Verhältnis zur bildbaren Wortmenge A* gibt, gibt es eine Aufzählfunktion f. Man kann also jedes Wort w von A* in chi eingeben und sobald WAHR rauskommt, wird w in die Menge M hinzugefügt.

Ist A* \ M abzählbar? Ja, da die Wortmenge A* längenlexikografisch geordnet werden kann und M auch abzählbar ist, wodurch die Komplementmenge gebildet werden kann.

Hat A* \ M eine Aufzählfunktion g? Ja, da die Wortmenge A* längenlexikografisch geordnet berechnet werden kann und da M aufzählbar ist, ist auch das Komplement A* \ M aufzählbar.

Teil 2:

Wenn M und A* \ M aufzählbare Mengen sind, dann ist M eine entscheidbare Menge.

M ist abzählbar (es existiert eine surjektive Abbildung zwischen N und M)

Es existiert eine Aufzählfunktion für M.

A* \ M ist abzählbar (es existiert eine surjektive Abbildung zwischen N und M)

Es existiert eine Aufzählfunktion für A* \ M.

Existiert eine Chi-Funktion für M? Ja, da M aufzählbar ist. (wird sich mit der Aussage von vorhin widersprechen -> deswegen wollte ich nochmal nachfragen)

Definitionen und Beweise

aufzählbar: abzählbar (FRAGE für 26.4: nur auf Wortmenge A* bezogen???) und berechenbar

abzählbar: Surjektion zwischen N und M vorhanden

berechenbar: es existiert Funktion f, die zu M führt

semi-entscheidbar: es existiert chi-strich-Funktion

entscheidbar: es existiert eine chi-Funktion

Übungen

Vorlesung 3 BuK/IIm21/Vorlesung 3 Hildebrand

Vorlesung 4 BuK/IIm21/Vorlesung 4 Hildebrand