Größe von ${\Sigma }^{\ast }$ ::

part of [[112.00_anchor_overview]] predecessor was [[112.14_universal_turing_machine]]

unter der Betrachtung, dass TMs viele Sprachen abdecken können, wir dabei womöglich jedoch Sprachen haben könnten, die nicht abgedeckt werden können ( stimmt nicht ) , stellt sich die Frage, ob ${\Sigma }^{\ast }$ abzählbar unendlich ist oder nicht.

Sei $\Sigma$ ein endliches, nicht leeres Alphabet. Wie groß kann dann ${\Sigma }^{\ast }$ sein? Wir wollen es folgend beweisen:

1. $\Sigma$ enthält mindestens einen Buchstaben, als $a\in \Sigma$
2. Dann enthält die Hülle ${\Sigma }^{\ast }$ die Wörter $a,a^2,a^3\dots$
3. Also finden wir eine injektive Abbildung $f:\mathbb{N}⟶{\Sigma }^{\ast },f(u)=a^i$

${\Sigma }^{\ast }$ ist abzählbar unendlich :

Sei $\Sigma$ ein endliches Alphabet ( Beispielsweise Dezimalsystem 0-9). Dann ist die Menge (Hülle des Alphabets) ${\Sigma }^{\ast }$ abzählbar unendlich!

folgend kann man es auf diverse Weisen beweisen: Zum Einen könne man argumentieren, dass die Menge der Alphabete beschränkt ist und dadurch auch die Hülle aller möglichen Konkatenationen abzählbar unendlich sein müssen. EIn anderer Beweis : Wir müssen eine bijektive Abbildung $f:\mathbb{N}⟶{\Sigma }^{\ast }$ finden, d.h. jedem Wort aus ${\Sigma }^{\ast }$ eine Nummer geben Dazu schreiben wir die Wörter in einer Ordnung nacheinander auf. und definieren so eine Abbildung für diese.

Jede dieser Mengen ist dabei endlich. In dieser Reihenfolge numerieren wir alle Wörter durch: erst die Wörter mit der Länge 0, dann Länge 1 usw. Unter dieser Betrachtung erstellen wir ganz viele kleine Mengen, wissen, dass diese Länge der Wörter immer nur abzählbar unendlich sein wird und somit auch der Inhalt dieser Kombinationen!

Sprachen sind höchstens abzählbar ::

Sei $L$ eine Sprache über einem endlichen Alphabet. Dann ist $:$ höçhsten abzählbar. Das kommt daher, dass die Hülle selbst auch nur abzählbar ist. und wir wissen, dass $L\subset {\Sigma }^{\ast }$ also immer eine echte Teilmenge ist.

Nun betrachte man die Menge aller Turingmaschinen, können wir jede Sprache damit abdecken // bijektiv eine Abbildung zu Sprachen und Turingmaschinen aufbauen?

Satz : Menge von Turingmaschinen ::

Die Menge aller TM ist abzählbar (unendlich) Dies können wir unter Betrachtung der [[112.14_universal_turing_machine#Gödelnummer einer TM :|Gödelnummer]] beweisen, denn wir haben jeder möglichen Turingmaschine eine eindeutige Bezeichnung, mittels der Gödelnummer, gegeben und sie somit abzählbar unendlich beschrieben. Es gibt eine bijektive Abbildung, die so definiert ist, dass zu jeder Turingmaschine eine einzige Gödelnummer existiert

weitere Betrachtung : Potenzmengen ::

$\mathbb{R}$ ist überabzählbar unendlich, revisit [[math1_Mengen#Gleichheit zweier Mengen ::|Mengen]] for further informationA Wir können weiterhin die Potenzmenge betrachten: Die Menge $2^{\mathbb{N}}:=\{0,1{\}}^{\mathbb{N}}:=\{(a_i{)}_{i\in \mathbb{N}}|a_i\in \{0,1\}\}$ ist überabzählbar, denn: Wir können einen Diagonaltrick anwenden und eine Funktion definieren: $g:\mathbb{N}⟶2^{\mathbb{N}}$ Sei dann : $g(1)=0100110\dots$ $g(2)=1101110\dots$ etc. Wir betrachten dann ferner: $a=(a_i{)}_{i\in \mathbb{N}}$ mit $a_i\left[\begin{array}{c}1\text{falls die i-te Ziffer von}g(i)=0\\ 0\text{falls die i-te Ziffer von }g(i)=1\end{array}\right]$–> $a\notin g(\mathbb{N})$ , demnach können wir g als nicht surjektiv beschreiben und zeigen!

Wo liegt die Gemeinsamkeit von Mengen $2^{\mathbb{N}}$ und dem Intervall $[0,1]\subset \mathbb{R}$ ?

Wir können alle Zahlen aus der Menge $[0,1]$ als eine Binärfolge darstellen. Damit bekommen wir ungefähr eine Bijektion erschaffen, müssen nur aufpassen mit periodischen Zahlen, wie $0,01\bar{1}$

$2^{\mathbb{N}}$ als Indikatorfunktion einer abzählbaren Menge :: Definieren wir sie folgend:: Sei $M$ eine abzählbare Menge: $M=\{m_1,m_2,m_3,\dots \}$ Betrachten wir nun alle Teilmengen $U\subset M$, dann haben wir die Möglichkeit jede Teilmenge durch einen Indikatorvektor darzustellen: $1_U(i):=\left(\begin{array}{c}1,\text{falls}{m}_i\in U,\\ 0\text{sonst}\end{array}\right)$ Also Beispiel definieren wir $U=\{m_1,m_2,m_4,m_7\dots \}$ und weiter können wir dann die Indikatorvektoren bestimmen: $1_U=(1,0,1,1,0,0,1,0,0\dots )$ Wir haben also überabzählbare viele Teilmengen von M zur Verfügung stehen!

Aus dieser Erkentnis können wir nun noch folgern:

Potenzmengen sind mächtiger ::

Sei $M$ eine beliebige Menge und $\mathcal{P}(M)=\{U|U\subseteq M\}$ ihre Potenzmenge. Betrachten wir logisch, dann muss die Potenzmenge größer als die Ursprüngliche Menge sein, weil sie mindestens jedes Element aus M beinhalten muss ( wenn wir jedes Element als seine eigene Menge definieren) und weiterhin mit der Fragmentierung der Menge $M$ noch weitere Teilmengen generiert erden und wir so Mehr Elemente in unserer Menge erhalten!. Wir folgern: Es gibt keine surjektive Abbildung $e:M⟶\mathcal{P}(M)$

Die Potenzmenge ist also immer echt mächtiger als die Menge selbst, wie obig als Konzept bereits beschrieben.

Diesen Zustand kann man nun auch beweisen, dafür nehmen wir eine surjektive Abbildung an :

Beweis:: Angenommen es existiert eine Abbildung : $e:=M⟶\mathcal{P}(M)$ und diese ist surjektiv.

Also Diagramm dargestellt: ![[Pasted image 20230511134657.png]]

Wir betrachten jetzt eine konzeptuelle Teilmenge $A:=\{m\in M|m\notin e(m)\}\subset M$ Wir wissen, dass aus der Definition $e(m)$ eine Element der Potenzmenge sein muss, und somit eigentlich auch eine Teilmenge $E\subset M$ sein muss.

$A$ wird quasi als ein Komplementmenge beschrieben, die nur die Elemente beinhaltet, wo die Bezeichnung/das Argument aus dem Urbild nicht in der Zielmenge enthalten ist.

Weil wir $A$ wie obig definiert haben, müssen bzw können wir daraus folgern, dass diese Teilmenge möglicherweise leer sein könnte, aber dennoch eine Teilmenge von $M$ ist. Das heißt es gilt auch : $A\in \mathcal{P}(M)$. Da die Abbildung $e$ surjektiv ist, muss es also auch $m_0\in M$ geben, mit der Beschreibung $e(m_0)=A$ also eine Teilmenge entspricht genau unserer erzeugten Teilmenge!

Die Frage kommt auf, ist die Menge $m_0$ dann selbst in $A$ oder nicht?

Wir können resultieren:

1. Falls $m_0\in A⟹$ dann nach folgt nach der Definition von $A:m_0/e(m_0)=A$
2. Falls $m_0\notin A⟹$ dann folge aus der Definition : $m_0\in e(m_0)=A$ Beide Aussagen stehen im Widerspruch zueinander, weil sie nicht in der Menge sein kann, obwohl sie in der Menge ist.

Wir folgern aus dieser Betrachtung :: $⟹$ Potenzmengen sind mächtiger

Konsequenz aus Potenzmengen, die Mächtiger sind:

Es gibt nach vorheriger Betrachtung beliebig viele Stufen einer unendlichkeit. Denn wir können beliebig oft Potenzmengen von vorhandenen Mengen definieren. Also gilt hier dann : $\mathbb{N}<\mathcal{P}(\mathbb{N})<\mathcal{P}(\mathcal{P}(\mathbb{N}))<\dots$

Weiteres findet man dann zu Ordinalzahlen und weiteren Aussagen der Mengenlehre

Aus diesen Konsequenzen können wir nun eine Folgerung für Alphabete und Sprachen ziehen:

Menge aller Sprachen über $\{0,1\}$ überabzählbar :

Sei $\Sigma$ ein endliches Alphabet ( Menge von Buchstaben, die endlich ist! ). Dann ist die Menge aller Sprachen $L$ über $\Sigma$ überabzählbar groß. Beweis dieser Aussage:: Nach Definition ist eine Sprache $L$ eine Teilmenge von ${\Sigma }^{\ast }$. Wir haben schon gesehen, dass ${\Sigma }^{\ast }$ abzählbar unendlich ist. Wir können die Wörter also durch einen abzählbar langen Indikatorvektor beschreiben, wovon wir schon wissen, dass es von ihnen $2^{\mathbb{N}}$ gibt –> sie also Überabzählbar unendlich sind.

${\Sigma }^{\ast }$ ist abzählbar während $2^{\mathbb{N}}$ eine unendliche Menge von Zeichen betrachtet und somit unendlich ist .

Nicht-triviale Sprachen:

Sie $L$ eine Sprache, deren Wörter nur aus Codes von TMs bestehen: Also beschrieben mit: $L\subset \{w\in \{0,1{\}}^{\ast }|w\text{ ist Code einer TM}\}$

Wir nennen die Sprache $L$ dann nicht-trivial, wenn gilt #card

• $L\ne \varnothing$

Es muss TMs geben, deren Code in L enthalten ist!

• $L/-\{w\in \{0,1{\}}^{\ast }|w\text{ ist Code einer TM}\}$

Es gibt TMs, deren Code nicht in L enthalten ist.

the next topic will focus on languages, and rather they are recursively nameable ( rekursiv aufzählbar) or not. [[theo2_SprachenNichtRekursiv]]