BuK/IIm11/Studenten/sistluet

Wiki-Quelltext dieser Seite.

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

{| border="0" cellpadding="5" cellspacing="0"
|-
|| $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:'''
[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 <tt>(Felix Nitsche, Stefan Lüttke)</tt>

ÜA: Wie viele berechenbare charakteristische Funktionen gibt es?
Hinweis: Potenzmenge unendlicher Mengen

Lösung:

[[Bild:Sistluet_AStern1.png]]

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)