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.

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: Die 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:

Definitionen und Beweise

Übungen

Vorlesung 3 BuK/IIm21/Vorlesung 3 Hildebrand