date-created: 2024-06-04 12:48:16 date-modified: 2024-07-10 10:01:40

Abzählbarkeit | Mengen

anchored to 112.00_anchor_overview

Wir wollen hier die Definition von Uendlichkeit verschieden betrachten, bzw. zwischen abzählbar unendlich und überabzählbar unendlich unterteilen, da wir somit dann Rückschlüsse, auf Sprachen und die Mächtigkeit dieser über einem Alphabet ziehen können.

Wdl | Grundlagen Mengenlehre

Es wurden die Grundlagen der Mengenlehre nochmals wiederholt und betrachtet, sodass die folgenden Beweise und Ideen verständlich sind.

Es benötigt ferner:

1. Abbildungen: math1_abbildungen und die Begriffe der Injektivität/Surjektivität/Bijekivität

2. Die Eigenschaft, dass $\mathbb{N}$ Unendlich ist

Es gilt, dass $\mathbb{N}$ unendlich ist (aber abzählbar unendlich).

[!Information] Beweis:

Dafür zeigen wir, dass $\forall n_0\in \mathbb{N},f:\{1,\dots ,n_0\}->\mathbb{N}$ nicht bijektiv ist.

wie gehen wir ferner vor? #card

Sei also $f:[1,2,\dots ,n_0]\to \mathbb{N}$ eine Abbildung Sei ferner $n_{max}:=\max \{f(i)\mid i\le n_0\}$ ( also der maximale Eintrag der Menge) Wir setzen jetzt folgend: $$m=n_{max}+1$$. Dann gilt ferner $m\in \mathbb{N}$ aber $m\notin \{f(1),\dots ,f(n_0)\}$ (also der aufgespannten Abbildung). –> Also ist $f$ nicht surjektiv, und daher auch nicht bijektiv (weil wir endlos viele Elemente haben!).

(Diese Idee ist zirkulär, weil sie mehr oder weniger auf den Peano-Axiomen aufbaut, die genau dafür gedacht sind/damit funktionieren).

Mächtigkeit: siehe Mengen

Exkurs | Peano Axiome

Durch Peano wird die Menge $\mathbb{N}$ folgend definiert:

1. $0\in \mathbb{N}$ (null ist auch natürlich!!!!!)
2. $\forall n(n\in \mathbb{N}⟹n^{\prime }\in \mathbb{N})$ (n’ ist der Nachfolger) (also haben alle einen Nachfolger)
3. $\forall (n\in \mathbb{N}⟹n^{\prime }\ne 0)$ (Null ist kein Nachfolger, somit linker Rand)
4. $\forall n,m(n,m\in \mathbb{N}⟹(m^{\prime }=n^{\prime }⟹m=n))$ (gleicher Nachfolger => gleiche Zahl)
5. $\forall X(0\in X\wedge \forall n(n\in \mathbb{N}⟹(n\in X⟹n^{\prime }\in X))⟹\mathbb{N}\subset X)$ (Induktionsaxiom, jeden Menge $x$, die 0 enthält, und mit jedem n auch den Nachfolger enthält, enthält auch alle natürlichen Zahlen)

Operationen auf abzählbaren Mengen

Aus den vorherigen Definitionen und Betrachtungen können wir ferner auch auf abzählbare Mengen Operationen definieren.

[!Satz] Grundoperationen auf abzählbaren Mengen

Was können wir über Abbildungen f:A->B aussagen, wenn A abzählbar ist, was wenn C subset A? Was können wir über die Vereinigung dieser sagen? #card

1. Sei $A$ höchstens abzählbar und weiter: $f:A\to B$ bijektiv. Es folgt $B$ ist auch höchsten abzählbar!
2. Sei $M$ abzählbar und $N\subseteq M$ –> Dann ist auch $N$ endlich oder abzählbar
3. Abzählbare Vereinigungen von abzählbaren Mengen sind auch abzählbar. Seien $M_1,M_2,\dots$ abzählbare Mengen. Dann ist die Vereinigung dieser auch abzählbar: ${\bigcup }_{i\in \mathbb{N}}{M}_i$
4. Seien $M_1,M_2,\dots ,M_n$ abzählbar. Dann ist auch $M_1\times M_2\times \cdots \times M_n$ abzählbar!

Beweis | Abzählbare Vereinigungen sind abzählbar.

Das können wir durch die Idee von Kantors erstem Diagonal-Argument beweisen, da hier die Struktur bzw der Aufbau ähnlich ist und sich nach und nach durch die einzelnen Inhalte der Mengen manövrieren wird.

[!Beweis] Da jede Menge $M_i$ abzählbar ist, gibt es also eine bijektive Abbildung $f_i:\mathbb{N}\to M_i$ –> Wir können also diese Menge komplett enumerieren, als $M_i=\{f_i(1),f_i(2)\dots \}$ wodurch wir dann also diese Menge kategorisieren können. Das machen wir jetzt für jede Menge $M_i$ und können dann damit also wie bei Cantors-erstem Diagonal-Argument zeigen, dass diese Menge abzählbar unendlich ist. Wir geben jedem Ergebnis in dieser Matrix dann einfach eine Nummer (nummerieren sie also nach und nach):

Beweis | Endliche Produkte sind abzählbar:

Die obige Aussage gilt nun auch für ein endliches Produkt von Mengen, also $M_1,M_2,\dots ,M_n$ sind abzählbar, dann folgt auch $M_1\times M_2\times \cdots \times M_n$

Der Beweis dazu findet sich hier:

Kontext Sprachen | Abzählbare Unendlichkeit

Wir wollen mit den vorher erhaltenen Erkenntnissen jetzt folgern, dass die kleensche Hülle ebenfalls abzählbar unendlich ist / sein wird. Und weiter dann noch Ergebnisse für die Sprache über ein Alphabet etc.

Kleen’sche Hülle ist endlich abzählbar ( unendlich)

Das wollen wir folgend beweisen:

[!Beweis]

Wir wollen jetzt zeigen, dass die kleen’sche Hülle endlich abzählbar ist.

wie gehen wir vor? #card

Wir wissen, dass ein Alphabet $\Sigma$ mindestens einen Buchstaben $a$ enthält ( oder einen anderen). Gemäß der Definition der kleen’schen Hülle kann man sie folgend beschreiben/bilden: $a,a^2,a^3\dots ,a^k,\in {\Sigma }^{\ast }$

wir wollen jetzt eine injektive Abbildung finden, die auf ${\Sigma }^{\ast }$ abbildet: $$f:\mathbb{N}\to {\Sigma }^{\ast },f(i)=a^i$$

Finden wir sie, dann können wir sagen, dass sie abzählbar unendlich ist!

Wir wollen also eine Bijektion $f:\mathbb{N}\to {\Sigma }^{\ast }$ finden.

Dazu ordnen wir die Worte von ${\Sigma }^{\ast }$ der Länge nach und nummerieren durch: $${\Sigma }^{\ast }=\{\underset{\in (1Wort)}{\underbrace{\{\text{ Wo¨rter La¨nge 0}\}}}\cup \underset{\mid \Sigma \mid Worte}{\underbrace{\{\text{ Wo¨rter La¨nge 1}\}}}\cup \underbrace{\{\text{ Wort La¨nge 2}{\}}_{\mid \Sigma {\mid }^2\text{ Worte}}}\cup \dots \}$$

Durch diese Konstruktion haben wir die unendliche Menge in abzählbare Teilmengen aufgeteilt –> Welche wir bekanntermaßen nummerieren können.

Da sie alle vereinigt sind, erhalten wir anschließend auch eine abzählbare Menge!

Man kann jetzt aus dieser gefundenen Abbildung folgende Eigenschaften erhalten:

1. die Abbildung ist wohldefiniert: Jedes $n\in \mathbb{N}$ erhält genau ein Bild, da ${\Sigma }^{\ast }$
2. Sie ist surjektiv: Denn jedes $w\in {\Sigma }^{\ast }$ kriegt mindestens eine Nummer, weil jedes $w$ endlich lang ist und jede Teilmenge auch endlich lang ist. (denn $\Sigma$ ist ja auch endlich)
3. Sie ist auch injektiv, denn jedes $w\in {\Sigma }^{\ast }$ erhält höchstens eine Nummer, weil es nur einmal in der sortierten Liste auftritt –> Damit ist es eine bijektion und wir haben sie abzählbar “gemacht”.

Sprachen sind (maximal) abzählbar unendlich

Aus obiger Betrachtung, dass die kleensche Hülle abzählbar unendlich ist - und somit eine obere Grenze für die Menge der Wörter die durch ein Alphabet gebildet werden können bildet, folgt dann also, dass eine Sprache $L\subseteq {\Sigma }^{\ast }$

• weniger mächtig, als die Hülle –> endlich
• oder gleichmächtig der Hülle –> abzählbar unendlich

[!Satz] Sei $L$ eine Sprache über einem endlichen Alphabet $\Sigma$. Dann ist $L$ höchstens abzählbar unendlich.

warum folgt das? #card

Wir wissen, dass ${\Sigma }^{\ast }$ abzählbar unendlich ist und ferner $L\subseteq {\Sigma }^{\ast }$

Es folgt außerdem eine Limitierung von Turing-Maschinen:

[!Satz]

Die Menge aller Turing Maschinen ist abzählbar unendlich

wie können wir das beweisen? #card

Wir wissen, dass man eine Turing-Maschine mit einer Gödelnummer eindeutig kodieren kann, wobei wir in Codierung einer Turing-Maschine in ein Alphabet von $\{0,1\}$ kodiert haben. Ferner wissen wir, dass die dabei entstehenden Kodierungen der Form $$\{0,1{\}}^{\ast }$$ sind –>> wir haben zuvor gezeigt, dass das abzählbar unendlich sein muss!

Die Menge der Gödelnummern ist also eine Teilmenge dieser Menge.

Überabzählbare Mengen

Mit abzählbaren Mengen haben wir nicht allzu viele neue Erkenntnisse entnehmen können, wissen immernoch nicht, ob eventuell Sprachen existieren, die wir nicht verarbeiten können ( weil es keine Turing-Maschine dafür gibt(?))

WDL | $\mathbb{R}$ ist überabzählbar

[!Beweis] $\mathbb{R}$ überabzählbar

Wir wollen nochmals den Beweis betrachten, wie man herausfindet, dass die Menge der Reellen Zahlen überabzählbar unendlich ist.

Dafür betrachten wir zuerst einen Teilbereich dieser Menge $(0,1)\subseteq \mathbb{R}$ (benannt als Kontinuum).

Wir werden einen Widerspruch durchführen:

Wie gehen wir in diesem Beweis vor? Die Idee ist wichtig, für Turingmaschinen und deren Entscheidbarkeit! #card

Angenommen $\mathbb{R}$ ist abzählbar, dann können wir eine bijektive Abbildung $g:\mathbb{N}\to \mathbb{R}$ definieren, und dann also die Zahlen in einer Ordnung aufschreiben:(beispielhaft folgend:) $$\begin{array}{rlrlrlrlrl}>g(1)& =& 0,& 7& 1& 6& 2& 3& 8& 4\\ >g(1)& =& 0,& 4& 6& 3& 2& 3& 8& 4\\ >g(1)& =& 0,& 2& 6& 8& 9& 3& 1& 4\\ >⋮& & & & & & & & & \\ >g(i)& =& 0,& a_{i_1}& a_{i_2}& a_{i_3}\dots & a_{i_i}& & & \\ >& & & & & & & & & \end{array}$$ –> also einfach eine Anordnung von verschiedenen Zahlen in dem Interval

Wir können nun iterativ (also abzählbar) eine neue reelle Zahl $x$ konstruieren, indem wir einfach immer an der $i$-ten Stelle der Ordnung eine Zahl ändern. –> diese diagonal-entstehende Zahl ist ebenfalls $\in (0,1)$, aber nicht in der Ordnung gelistet. Es gilt offensichtlich: $\forall n\in \mathbb{N}:x\ne g(n)$ –> somit auch $x\notin g(\mathbb{N})$ und $g$ ist daher nicht surjektiv und nicht bijektiv.

$\mathbb{N}$ ist abzählbar unendlich. Warum können wir das da nicht machen?

$2^{\mathbb{N}}$ Ist überabzählbar

Wir wollen noch eine wichtige Sprache betrachten, die wir gleich betrachten müssen:

[!Definition]

Wir möchten folgende Sprache betrachten: $$2^{\mathbb{N}}=\{0,1{\}}^{\mathbb{N}}=\{(a_i{)}_{i\in \mathbb{N}\mid a_i\in \{0,1\}}\}$$ Sie stellt also alle möglichen binären Strings dar.

Wir wollen jetzt zeigen, dass sie überabzählbar ist!

wie können wir das beweisen? #card

Angenommen wir könnten $2^{\mathbb{N}}$ abzählen. Das heißt, es gibt eine bijektive Abbildung $g:\mathbb{N}\to 2^{\mathbb{N}}$. Wir können dafür, wie [hier](#WDL%20%20ist%20überabzählbar) die Ordnung aufschreiben und dann zeigen, dass es nicht bijektiv ist! $$\begin{array}{rlrlrlrl}>g(1)& =& 1& 0& 0& 1& 1& 1\dots \\ >g(2)& =& 0& 1& 0& 0& 1& 0\dots \\ >g(3)& =& 0& 0& 1& 0& 1& 1\dots \\ >⋮>g(i)& =& a_{i_1}& a_{i_2}\cdots >& & & & \end{array}$$ Auch hier können wir diese Ordnung wieder zerstören: Wir konstruieren iterativ ( also etwa abzählbar) eine neue Folge $a=(a_i{)}_{i\in \mathbb{N}}$ wobei dabei dann $$a_i=\{\begin{array}{ll}>0& \text{ falls }{g}_{ii}=1\\ >1& \text{ falls }{g}_{ii}=0>\end{array}$$ ->> Also anhand der Einträge in der Ordnung und immer der $i$-ten Eintragun bauen wir noch einen neuen Binär-String auf. Aufgrund der Konstruktion kann dieser zuvor gar nicht existiert haben (weil selbst wenn alles bis auf eine Stelle übereinstimmt, nehmen wir ja von diesem Wort die $i$te Stelle und invertieren sie einfach! –> neues Wort gefunden!)

Dann ist also diese neue Folge $a\in 2^{\mathbb{N}}$ aber $\forall n\in \mathbb{N}:a\ne g(n)$ –> damit ist sie nicht surjektiv

Erkenntnis

[!Important]

Wir haben hier gesehen, dass beide Beweise grundsätzlich gleich aufgebaut sind, aber in verschiedenen Basen auftreten.

Abstrakt gesagt können wir hier annehmen, dass etwa $2^{\mathbb{N}}$ “fast identisch” zu $U=[0,1]\subseteq \mathbb{R}\}$ ist. Denn:

• jede Zahl in $U$ kann als Binärfolge dargestellt werden $0,10111,1010101001\dots$
• Jede Binärfolge identifiziert eine Zahl in $U$
• damit beschreiben wir also “quasi den gleichen Raum”
• –> Probleme bilden Perioden, wie $0,1010\overline{1}$ denn $0,101\overline{1}=0,101\overline{0}$ (netterweise haben wir nur abzählbar viele davon!) –> damit kann man sie quaasi einfach abzählbar rausstreichen

Indikatorfunktion $2^{\mathbb{N}}$

[!Definition]

Wir können jetzt sagen, dass $2^{\mathbb{N}}$ eine Indikatorfunktion einer abzählbaren Menge ist.

warum, wie können wir das zeigen? was ist der Indikatorvektor #card

Sei dafür $M$ eine abzählbare Menge $M=\{m_1,m_2,\dots \}$ -> Wir betrachten nun alle Teilmengen $U\subset M$: Dann können wir jede Teilmenge $U$ durch einen Indikatorvektor darstellen: $$1_U(i)=\{\begin{array}{ll}>1& \text{ wenn }{m}_i\in U\\ >0& \text{ sonst}>\end{array}$$ –> Also wenn wir eine Menge betrachten, dann gehen wir alle endlich abzählbaren Einträge der Obermenge $M$ hier, durch und können dann für jedes Element ( was ja abzählbar unendlich viele sind und somit $\mid N\mid =|M\mid$ und somit dann $2^{\mid M\mid =\mathbb{N}}$!!!!!) eine Aussage treffen.

Dadurch haben wir für eine Teilmenge gesagt, was hineingehört, aber da wir eben abzählbar unendliche Einträge vergleichen, ist die Abbildung überabzählbar unendlich.

[!Attention] Folgerung

Eine abzählbare Menge halt also überabzählbar viele Teilmengen Die Darstellung von Sequenzen von 0 und 1.

Mit dieser Teilmenge können wir eine Teilmenge einer abählbaren Menge darstellen. –> Diese Funktion stellt dabei eine Kodierung der Inhalte der Teilmenge da. Also gibts eine Bijektion zwischen der überabzählbaren Funktion $a^{\mathbb{N}}$ in eine Teilmenge einer abzählbar unendlichen Menge

Diagonalisierung | Verallgemeinertes Beweisen von (Über)abzählbar

Wir haben das Diagonalisieren zuvor schonmal betrachtet, um etwa zu zeigen, dass $\mathbb{R}$ überabzählbar ist. Jetzt wollen wir die Mächtigkeit von zwei Mengen $A,B$ damit vergleichen

[!Definition] Mächtigkeit vergleichen

Gegeben seien zwei Mengen $A,B$, die wir auf ihre Mächtigkeit vergleichen möchten.

Wenn sie endliche Mengen sind, ist es einfach, denn wir können zählen, für unendliche geht das nicht.

–> Wir wollen durch eine Bijektion dennoch eine Aufzählbarkeit und somit einen Vergleich beider ermöglichen:

wie gehen wir bei einer Bijektion hier dann vor? #card

Wir können das 1 Diagonalargument nochmal verwenden: -> Um zu zeigen, dass eine Produktmenge abzählbar ist, suchen wir eine Bijektion zu $\mathbb{N}$, indem wir die Elemente des Produktes beider Mengen in einer Tabelle sortieren und dann nach und nach durchzählen. –> Dabei treten Zahlen doppelt auf, die wir dann überspringen:

Wollen wir jetzt beweisen, dass zwei Mengen überabzählbar sind, nutzen wir ein vorheriges Konzept nochmal:

[!Beweis] Beweisen, dass $A$ überabzählbar

Wir wollen zeigen, dass eine Menge überabzählbar ist.

wie gehen wir vor? #card

Um zu zeigen, dass eine Menge überabzählbar ist, zweigen wir, dass es keine solche Bijektion geben kann. Dazu listen wir wieder die Werte in einer möglichen Ordnung auf –> und nehmen an, dass sie abzählbar ist - und können dann zeigen, dass ein weiteres Element konstruieren kann.

Das neue Elemente konstruieren wir folgend:

• Wir gehen diagonal durch die Liste der Elemente und konstruieren ein Element aus der Zielmenge, dass kein Urbild hat (weil es nicht “bedacht wurde”) $$\begin{array}{rlrlrlrl}>g(1)& =& 1& 0& 0& 1& 1& 1\dots \\ >g(2)& =& 0& 1& 0& 0& 1& 0\dots \\ >g(3)& =& 0& 0& 1& 0& 1& 1\dots \\ >⋮>g(i)& =& a_{i_1}& a_{i_2}\cdots >& & & & \end{array}$$

etwa wie hier

Kontext zu | Sprachen und Überabzählbarkeit

Da die kleensche Hülle abzählbar unendlich ist, aber wir für eine Sprache- die eine Teilmenge ist - dann diese überabzählbare Funktion anwenden und sie somit abzählen können, folgt, dass es überabzählbar endliche Sprachen über eine endliche Menge eines Alphabets gibt.

–> Weiterhin foglt daraus jetzt weiter:

[!Attention]

Für alle endlichen Alphabete $\Sigma$ gibt es Sprachen $L\in {\Sigma }^{\ast }$ die von keiner Turingmaschine erkannt werden können

wie könnten wir das ungefähr beweisen? #card

Wir haben gesehen, dass die Menge von Turing-Maschinen abzählbar ist, und dass $\{0,1{\}}^{\ast }=2^{\mathbb{N}}$ überabzählbar ist. –> Es gibt also keine surjektive Abbildung von der Menge der Turing-Maschinen auf die Menge der Sprachen.

Formaler Beweis:

Es gilt zu beweisen:

Für alle endlichen Alphabete $\Sigma$ gibt es Sprachen $L\subset {\Sigma }^{\ast }$ , die von keiner Turingmaschine erkannt werden können.

Beweis: Wir betrachten o.B.d.A ein Alphabet $\Sigma =\{0,1\}$

1. ${\Sigma }^{\ast }$ wie zuvor: ist sie abzählbar unendlich

Weiterhin: Jede Turing-Maschine kann in eine Gödelnummer $⟨M⟩$ übersetzt werden. -> Die Gödelnummer sind eine unendliche, echte Teilmgen von ${\Sigma }^{\ast }$ und somit auch abzählbar!

Jetzt ist die Menge aller Binärfolgen $2^{\mathbb{N}}$ überabzählbar (wie zuvor bewiesen). Dann sei jetzt $\mathcal{L}$ die Menge aller Sprachen über $\Sigma$: Für jedes $A\in \mathcal{L}$ können wir eine charakteristische Folge ${\mathcal{X}}_A$ bilden, die angibt, welche Worte aus ${\Sigma }^{\ast }$ in $A$ sind (also es geht jeden Eintrag von $\Sigma$ durch und gibt entweder 1/0 an!): Es folgt daraus: $$\begin{array}{rlrlrlrlrlrl}{\Sigma }^{\ast }& =& \{& \epsilon ,& 0,& 1,& 00,& 01,& 10& 11,& 000,& \dots \}\\ A& =& \{& & 0,& & 00,& 01,& & & 000& \dots \}\\ {\mathcal{X}}_A& =& \{& 0,& 1,& 0,& 1,& 1,& 0,& 0,& 1,& \dots \}\end{array}$$ (also sie gibt genau das an, was sich drin befindet und was nicht).

Wir wissen: $f:\mathcal{L}\to 2^{\mathbb{N}},f(A)={\mathcal{X}}_A$ ist injektiv und surjektiv (also bijektiv) –> damit haben wir auf die Sprache abgezählt und sie ist somit überabzählbar. Somit dann auch $\mathcal{L}$!

[!Attention] Folgerung Die Menge aller Sprachen ist also echt mächtiger, als die Menge aller Turingmaschinen.

Was kann man daraus für Sprachen folgern? #card

Es muss also Sprachen geben, die von keiner Turingmaschine erkannt werden!

[!Feedback] Abzählbarkeit einer Sprache vs aufzählbarkeit

worin sehen wir den großen Unterschied zwischen Abzählbarkeit und Aufzählbarkeit? –> Wie kann man diese Attribute zeigen / verneinen? #card

Jede Sprache $L\subseteq {\Sigma }^{\ast }$ ist abzählbar (wir können also jedes Wort in der Sprache aufzählen und diesem eine Zahl geben)

rekursiv aufzählbar hingegen beschreibt, dass wir eine TM bauen kann, die die Sprache entscheiden kann

• Sie akzeptiert Wörter $\in L$
• und es gibt einen Drucker der jedes Wort angibt

Damit haben wir zwei unterschiedliche Punkte!

rekursiv aufzählbar wird garantieren, dass jedes Wort $\in L$ irgendwann mal ausgegeben wird –> dabei ist keine Reihenfolge relevant, wir wollen einfach alle akzeptierten Wörter ausgeben ( somit können auch die eewig rechnenden irgendwann ausgegeben werden) (Hierbei ist wichtig, dass man etwa einfach alle Eingaben parallel ausführt!)

Und abzählbar gibt uns eine Möglichkeit, dass wir jedes Wort betrachten und darüber eine Aussage treffen können! –> Also wir wissen anschließend was $\in L$ und was nicht $\in L$ –> weil wir alles durchgehen und entscheiden können!

Das sind zwei unterschiedliche Aspekte!

[!Definition] Zeigen von Aufzählbarkeit

#card

Wir können eine TM und auch Drucker verwenden, um zu zeigen, dass eine Sprache rekursiv aufzählbar ist.

Folgerungen | weitere Betrachtung

Es gibt nun auch überabzählbare Dinge: 112.16_nicht_erkennbar_entscheidbar