sistluet

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} ...

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: http://www.mathepedia.de/Ueberabzaehlbar_unendlich.aspx

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) = 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_2(2,y), F_2(2,y)+y+1) F_2 = F_1(F_2(2,2), F_2(2,2)+2+1) ; y=2 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) y=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) y=0 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_0(F_1(2,y), F_1(2,y)+y+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) y=2 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_05, 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)