Cantor-Diagonalisierung < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Aufgabe 3 (Cantor Diagonalisierung).
Es seien p: [mm] \IN_{0} [/mm] x [mm] \IN_{0} \to \IN_{0} [/mm] und
s: [mm] \IN_{0} [/mm] x [mm] \IN_{0} \to \IN_{0} [/mm] x [mm] \IN_{0} [/mm] definiert durch:
p(m,n) := [mm] \summe_{i\in [1, m+n]}^{} [/mm] i+n,
[mm] s(m,n)=\begin{cases} n+1,0, & \mbox{falls} m= 0 \mbox{ } \\ m-1,n+1, & \mbox{falls} m\not= 0 \mbox{ } \end{cases}
[/mm]
für (m,n) [mm] \in \IN_{0} [/mm] x [mm] \IN_{0}. [/mm] Zeigen Sie:
a) Es gilt p(0,0) =0 und p(s(m,n))= p(m,n)+1 für alle [mm] (m,n)\in \IN_{0} [/mm] x [mm] \IN_{0}.
[/mm]
b) Es ist p: [mm] \IN_{0} [/mm] x [mm] \IN_{0} \to \IN_{0} [/mm] eine Bijektion. |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Ich kann mir unter den Voraussetzungen nicht so recht was vorstellen. ich habe mal verschiedene Werte für n,m eingesetz und mir das für p und s versucht einzuzeichnen in einen Graphen, aber daraus kann ich nichts erkennen, was mir für die Lösung in a) weiterhilft.. Es wurde uns gesagt, dass man bei a) nachrechnen muss, aber ich weiß gar nicht wo ich was für einsetzen muss darf, damit ich die Gleichheiten in a) zeigen kann.
Hat jemand vielleicht einen Tipp oder Ansatz?
|
|
| |
|
> Aufgabe 3 (Cantor Diagonalisierung).
> Es seien p: [mm]\IN_{0}[/mm] x [mm]\IN_{0} \to \IN_{0}[/mm] und
> s: [mm]\IN_{0}[/mm] x [mm]\IN_{0} \to \IN_{0}[/mm] x [mm]\IN_{0}[/mm] definiert
> durch:
> p(m,n) := [mm]\summe_{i\in [1, m+n]}^{}[/mm] i+n,
Hallo,
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]") .
Ich gehe mal davon aus, daß gemeint ist, daß man über alle natürlichen i aus dem Intervall summieren soll, also
p(m,n) [mm] :=[\summe_{i=1}^{m+n}i]+n.
[/mm]
Berechne doch jetzt mal zum besseren Verständnis der Abbildung p, was p(2,7) ergibt.
> [mm]s(m,n)=\begin{cases} \red{(}n+1,0\red{)}, & \mbox{falls} m= 0 \mbox{ } \\ \red{(}m-1,n+1\red{)}, & \mbox{falls} m\not= 0 \mbox{ } \end{cases}[/mm]
>
> für (m,n) [mm]\in \IN_{0}[/mm] x [mm]\IN_{0}.[/mm]
s ist eine Abbildung, welche Zahlenpaare auf Zahlenpaare abbildet.
z.B. ist s(0,6)=(7,0) und s(13, 4)=(12,5).
> Zeigen Sie:
> a) Es gilt p(0,0) =0 und p(s(m,n))= p(m,n)+1 für alle
> [mm](m,n)\in \IN_{0}[/mm] x [mm]%5CIN_%7B0%7D.[/mm]
Was hat man bei p(0,0)?
Nun rechne doch mal zum ersten Verständnis
p(s(3,7)) aus und vergleiche mit p(3,7)+1:
s(3,7)=???,
also ist p(s(3,7))= p(...,...)=???,
und p(3,7)+1= ...+1=???.
Danach kannst Du es dann allgemein für (m,n) versuchen - vermutlich mußt Du unterscheiden nach m=0 und [mm] m\not=0.
[/mm]
LG Angela
> b) Es ist p: [mm]\IN_{0}[/mm] x [mm]\IN_{0} \to \IN_{0}[/mm] eine
> Bijektion.
> Ich kann mir unter den Voraussetzungen nicht so recht was
> vorstellen. ich habe mal verschiedene Werte für n,m
> eingesetz und mir das für p und s versucht einzuzeichnen
> in einen Graphen, aber daraus kann ich nichts erkennen, was
> mir für die Lösung in a) weiterhilft.. Es wurde uns
> gesagt, dass man bei a) nachrechnen muss, aber ich weiß
> gar nicht wo ich was für einsetzen muss darf, damit ich
> die Gleichheiten in a) zeigen kann.
> Hat jemand vielleicht einen Tipp oder Ansatz?
>
>
|
|
|
| |
|
Vielen Dank erstmal für deine schnelle Antwort :)
Also ich hab mal das ausprobiert was du mir geraten hast:
ich weiß nicht ob es reicht, und bin mir unsicher ob es korrekt ist, wenn ich folgendes mache wenn ich p(0,0)=0 zeigen will:
Also ich setze einfach ein:
p(0,0) = [ [mm] \summe_{i =1}^{0+0} [/mm] i ]+ 0,
= [mm] \summe_{i =1}^{0} [/mm] i ]+ 0,
= ? +0
Für den zweiten Teil hab ich das mal ausprobiert mit den Zahlen die du mir genannt hast :)
Also ich habe für p(s(3,7)) zunächst s(3,7) = (2,8) berechnet.
Dann p(2,8)= [ [mm] \summe_{i =1}^{10} [/mm] i ] + 8 = 1+2+3+4+5+6+7+8+9+10+8 =63 (Ist das so richtig gerechnet? bin irgendwie verwirrt von der schreibweise meines profs :) )
Für p(3,7) +1 = [ [mm] \summe_{i =1}^{10} [/mm] i ] + 7 +1 = 63
stimmt das soweit? Auch von der schreibweise?
Und hab ich mich am allgemeinen versucht:
zunächst für m=0 :
p(s(0,n) = p(n+1,0)
= [ [mm] \summe_{i =1}^{n+1} [/mm] i ] + 0
= (1+2+....+n + (n+1) ) + 0
= (1+2+...+n) +n+1
p(0,n) )+1 =p(0,n) +1
= [ [mm] \summe_{i =1}^{n} [/mm] i ] + n +1
= (1+...+n) +n +1
= (1+...+n) +n+1
für [mm] m\not= [/mm] 0 bin ich noch am basteln..
magst du mir vielleicht schon mal eine Rückmeldung geben ob ich richtig liege?
Danke :)
|
|
|
| |
|
Hallo,
> p(0,0) = [ [$ [mm] \summe_{i =1}^{0+0} [/mm] $] i ]+ 0,
> = [ [mm] \summe_{i =1}^{0} [/mm] i ]+ 0,
> = ? +0
Beim Fragezeichen hast Du eine leere Summe, deren Summenwert definitionsgemäß =0 ist.
Die Funktionswerte hast Du richtig ausgerechnet,
und in der Rechnung für m=0 sehe ich auch keinen Fehler.
Deutliche Fortschritte also!
LG Angela
|
|
|
| |
|
Danke - das ging schnell :) Hab jetzt auch das mit m [mm] \not= [/mm] 0 fertig:
Vielen Dank, mit deinen Tipps war die Aufgabe gar nicht so schwer:)
Hast du vielleicht auch noch einen kleinen Tipp wie ich zeigen kann, dass:
p: [mm] \IN_{0} [/mm] x [mm] \IN_{0} \to \IN_{0} [/mm] eine Bijektion ist?
Also erstmal zeige surjetiv und dann injektiv. Aber mir fällts das irgendwie schwer, wie man zeigen soll, dass eine Abb. surjetiv und injektiv ist.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:43 So 07.04.2013 | | Autor: | hippias |
Vielleicht zuerst die Surjektivitaet: Wie lautet Deine Definition?
|
|
|
|
