sistluet
Aus ProgrammingWiki
Themenbereich 2
Aufgabe 6
Zeigen Sie, dass $\mathbb{R}$ überabzählbar unendlich ist.
Hinweis: Es reicht schon aus zu zeigen, dass es im Intervall [0, 1] überabzählbar unendlich viele reelle Zahlen gibt.
Lösung:
Methode: Indirekter Beweis
Annahme: $\mathbb{R}$ ist abzählbar unendlich.
Wenn dem so ist,
dann kann man die reelen Zahlen nacheinander auflisten.
$n_{1} = 0,$ $n_{11}$ $n_{12}$ $n_{13}$ $n_{14} ... $
$n_{2} = 0,$ $n_{21}$ $n_{22}$ $n_{23}$ $n_{24} ... $
$n_{3} = 0,$ $n_{31}$ $n_{32}$ $n_{33}$ $n_{34} ... $
$.$
$.$
$.$
$n_{i} = 0,$ $n_{i1}$ $n_{i2}$ $n_{i3}$ $n_{i4} ... $
$.$
$.$
$.$
Konstruktion einer Zahl $x$ mit $x \in [0 ; 1]$, die nicht in der Menge vorkommen kann:
$x = 0,$ $x_{1}$ $x_{2}$ $x_{3}$ $x_{4} ...$
| $n_{1}$ | $\bf n_{11}$ | $n_{12}$ | $n_{13}$ | $n_{14}$ | $...$ | $...$ |
| $n_{2}$ | $n_{21}$ | $\bf n_{22}$ | $n_{23}$ | $n_{24}$ | $...$ | $...$ |
| $n_{3}$ | $n_{31}$ | $n_{32}$ | $\bf n_{33}$ | $n_{34}$ | $...$ | $...$ |
| $n_{4}$ | $n_{41}$ | $n_{42}$ | $n_{43}$ | $\bf n_{44}$ | $...$ | $...$ |
| $...$ | $...$ | $...$ | $...$ | $...$ | $...$ | $...$ |
| $x$ | $x_{1} $ | $x_{2}$ | $x_{3} $ | $x_{4}$ | $\bf x_{5}$ | $...$ |
wobei $x_{i} = (n_{ii} +1)$ $mod 10$ sein soll. Durch diese Definition wird ersichtlich, dass man immer eine Zahl $x$ findet, die nicht innerhalb $\mathbb{R}$ ist.
Wenn es immer eine Zahl $x$ gibt, die nicht in der Menge ist, dann ist $\mathbb{R}$ auch nicht abzählbar unendlich und damit überabzählbar unendlich.
Quelle: [1]
Warum gilt $0,\bar{9} = 1$?
(a) Es Gilt: $\frac{1}{3}$ wird als $0,\bar{3}$ in Dezimalschreibweise dargestellt.
(b) Desweiteren gilt: $0,\bar{9} = 0,\bar{3}*3$.
Wenn (a) und (b) gelten, so gilt auch: $0,\bar{9} = \frac{1}{3} * 3 = 1$
Themenbereich 3
Aufgabe 1 (Felix Nitsche, Stefan Lüttke)
ÜA: Wie viele berechenbare charakteristische Funktionen gibt es? Hinweis: Potenzmenge unendlicher Mengen
Lösung:
Die Wortmenge $A^*$ ist abzählbar unendlich. Für Jede der überabzählbar unendlich vielen Teilmengen $M$ (entspricht Wörtern) gibt es eine Funktion $\chi_{M}$ die entweder $true$ oder $false$ zurückgibt, was dazu führt das es ebenfalls überabzähbar unendlich viele Funktionen $\chi_{M}$ definiert werden können. Da es aber nur abzählbar unendlich viele Prozeduren gibt kann es auch nur abzählbar unendlich viele berechenbare Funktionen $\chi_{M}$.
Sudanfunktion
$F_{0} = x + y$
$F_{n+1} (x,0) = x$
$F_{n+1} (x,y+1) = F_{n}(F_{n+1} (x,y), F_{n+1}(x,y)+y+1)$
$x = 2$
$y = 3$
$F_{0} = 5$
$F_{1} = F_{0}(F_{1}(2,2), F_{1}(2,2)+2+1)$
$F_{1} = F_{0}(F_{0}(F_{1}(2,1), F_{1}(2,1)+1+1), F_{1}(2,2)+2+1)$
$F_{1} = F_{0}(F_{0}(F_{1}(2,1), F_{1}(2,1)+1+1), F_{0}(F_{1}(2,1), F_{1}(2,1)+1+1)+2+1)$
$F_{1} = F_{0}(F_{0}(F_{0}(F_{1}(2,0), F_{1}(2,0)+0+1), F_{0}(F_{1}(2,0), F_{1}(2,0)+1+1), F_{0}(F_{0}(F_{1}(2,0), F_{1}(2,0)+1+1), F_{0}(F_{1}(2,0), F_{1}(2,0)+1+1)+1+1)+2+1)$
$F_{1} = F_{0}(F_{0}(F_{0}(2, 2+0+1), F_{0}(2, 2+0+1)), F_{0}(F_{0}(2, 2+0+1), F_{0}(2, 2+0+1)+1+1)+2+1)$
$F_{1} = F_{0}(F_{0}(5, 5), F_{0}(5, 5+1+1)+2+1)$
$F_{1} = F_{0}(10, 12+2+1)$
$F_{1} = 25$
$F_{2} = F_{1}(F_{2}(2,2), F_{2}(2,2)+2+1)$
$F_{2} = F_{1}(F_{1}(F_{2}(2,1), F_{2}(2,1)+1+1), F_{1}(F_{2}(2,1), F_{2}(2,1)+1+1)+2+1)$
$F_{2} = F_{1}(F_{1}(F_{1}(F_{2}(2,0), F_{2}(2,0)+0+1), F_{1}(F_{2}(2,0), F_{2}(2,0)+0+1)+1+1), F_{1}(F_{1}(F_{2}(2,0), F_{2}(2,0)+0+1), F_{1}(F_{2}(2,0), F_{2}(2,0)+0+1)+1+1)+2+1)$
$F_{2} = F_{1}(F_{1}(F_{1}(2, 3), F_{1}(2, 3)+1+1), F_{1}(F_{1}(2, 3), F_{1}(2, 3)+1+1)+2+1)$
$F_{2} = F_{1}(F_{1}(F_{0}(F_{1}(2,2), F_{1}(2,2)+2+1), F_{0}(F_{1}(2,2), F_{1}(2,2)+2+1)+1+1), F_{1}(F_{0}(F_{1}(2,2), F_{1}(2,2)+2+1), F_{0}(F_{1}(2,2), F_{1}(2,2)+2+1)+1+1)+2+1)$
$F_{2} = F_{1}(F_{1}(F_{0}(F_{0}(F_{1}(2,1), F_{1}(2,1)+1+1), F_{0}(F_{1}(2,1), F_{1}(2,1)+1+1)+2+1), F_{0}(F_{0}(F_{1}(2,1), F_{1}(2,1)+1+1), F_{0}(F_{1}(2,1), F_{1}(2,1)+1+1)+2+1)+1+1), F_{1}(F_{0}(F_{0}(F_{1}(2,1), F_{1}(2,1)+1+1), F_{0}(F_{1}(2,1), F_{1}(2,1)+1+1)+2+1), F_{0}(F_{0}(F_{1}(2,1), F_{1}(2,1)+1+1), F_{0}(F_{1}(2,1), F_{1}(2,1)+1+1))+2+1)+1+1)+2+1)$
$F_{2} = F_{1}(F_{1}(F_{0}(F_{0}(F_{0}(F_{1}(2,0), F_{1}(2,0)+0+1), F_{0}(F_{1}(2,0), F_{1}(2,0)+0+1)+1+1), F_{0}(F_{0}(F_{1}(2,0), F_{1}(2,0)+0+1), F_{0}(F_{1}(2,0), F_{1}(2,0)+0+1)+1+1)+2+1), F_{0}(F_{0}(F_{0}(F_{1}(2,0), F_{1}(2,0)+0+1), F_{0}(F_{1}(2,0), F_{1}(2,0)+0+1)+1+1), F_{0}(F_{0}(F_{1}(2,0), F_{1}(2,0)+0+1), F_{0}(F_{1}(2,0), F_{1}(2,0)+0+1)+1+1)+2+1)+1+1), F_{1}(F_{0}(F_{0}(F_{0}(F_{1}(2,0), F_{1}(2,0)+0+1), F_{0}(F_{1}(2,0), F_{1}(2,0)+0+1)+1+1), F_{0}(F_{0}(F_{1}(2,0), F_{1}(2,0)+0+1), F_{0}(F_{1}(2,0), F_{1}(2,0)+0+1)+1+1)+2+1), F_{0}(F_{0}(F_{0}(F_{1}(2,0), F_{1}(2,0)+0+1), F_{0}(F_{1}(2,0), F_{1}(2,0)+0+1)+1+1), F_{0}(F_{0}(F_{1}(2,0), F_{1}(2,0)+0+1), F_{0}(F_{1}(2,0), F_{1}(2,0)+0+1)+1+1))+2+1)+1+1)+2+1)$
$F_{2} = F_{1}(F_{1}(F_{0}(F_{0}(F_{0}(2, 2+0+1), F_{0}(2, 2+0+1)+1+1), F_{0}(F_{0}(2, 2+0+1), F_{0}(2, 2+0+1)+1+1)+2+1), F_{0}(F_{0}(F_{0}(2, 2+0+1), F_{0}(2, 2+0+1)+1+1), F_{0}(F_{0}(2, 2+0+1), F_{0}(2, 2+0+1)+1+1)+2+1)+1+1), F_{1}(F_{0}(F_{0}(F_{0}(2, 2+0+1), F_{0}(2, 2+0+1)+1+1), F_{0}(F_{0}(2, 2+0+1), F_{0}(2, 2+0+1)+1+1)+2+1), F_{0}(F_{0}(F_{0}(2, 2+0+1), F_{0}(2, 2+0+1)+1+1), F_{0}(F_{0}(2, 2+0+1), F_{0}(2, 2+0+1)+1+1))+2+1)+1+1)+2+1)$
$F_{2} = F_{1}(F_{1}(F_{0}(F_{0}(F_{0}(2, 3), F_{0}(2, 3)+1+1), F_{0}(F_{0}(2, 3), F_{0}(2, 3)+1+1)+2+1), F_{0}(F_{0}(F_{0}(2, 3), F_{0}(2, 3)+1+1), F_{0}(F_{0}(2, 3), F_{0}(2, 3)+1+1)+2+1)+1+1), F_{1}(F_{0}(F_{0}(F_{0}(2, 3), F_{0}(2, 3)+1+1), F_{0}(F_{0}(2, 3), F_{0}(2, 3)+1+1)+2+1), F_{0}(F_{0}(F_{0}(2, 3), F_{0}(2, 3)+1+1), F_{0}(F_{0}(2, 3), F_{0}(2, 3)+1+1))+2+1)+1+1)+2+1)$
$F_{2} = F_{1}(F_{1}(F_{0}(F_{0}(5, 5+1+1), F_{0}(5, 5+1+1)+2+1), F_{0}(F_{0}5, 5+1+1), F_{0}(5, 5+1+1)+2+1)+1+1), F_{1}(F_{0}(F_{0}(5, 5+1+1), F_{0}(5, 5+1+1)+2+1), F_{0}(F_{0}(5, 5+1+1), F_{0}(5, 5+1+1))+2+1)+1+1)+2+1)$
$F_{2} = F_{1}(F_{1}(F_{0}(F_{0}(5, 7), F_{0}(5, 7)+2+1), F_{0}(F_{0}(5, 7), F_{0}(5, 7)+2+1)+1+1), F_{1}(F_{0}(F_{0}(5, 7), F_{0}(5, 7)+2+1), F_{0}(F_{0}(5, 7), F_{0}(5, 7))+2+1)+1+1)+2+1)$
$F_{2} = F_{1}(F_{1}(F_{0}(12, 12+2+1), F_{0}(12, 12+2+1)+1+1), F_{1}(F_{0}(12, 12+2+1), F_{0}(12, 12)+2+1)+1+1)+2+1)$
$F_{2} = F_{1}(F_{1}(F_{0}(12, 15), F_{0}(12, 15)+2), F_{1}(F_{0}(12, 15), F_{0}(12, 12)+3)+2)+3)$
$F_{2} = F_{1}(F_{1}(27, 27+2), F_{1}(27, 24+3)+2)+3)$
$F_{2} = F_{1}(F_{1}(27, 29), F_{1}(27, 27)+2)+3)$
$.$
$.$
$.$
laut einer Berechnung ist das ergebins wohl in der Gegend von $5,74 · 10^{24}$ [2]
