IN x IN gleichmächtig IN < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Man beweise, dass
[mm] \IN\times \IN [/mm] und [mm] \IN [/mm] gleichmächtig sind, indem man zeige, dass durch
[mm] (k,l)->2^{k-1}* [/mm] (2l-1) |
Hallo!
Kann mir jemand sagen, ob die Aufgabe so richtig ist und wie es weiter geht?
Mein Beweis:
Injektivität:
z.z. [mm] Vx,a\in\IN: [/mm] f(x)=f(a) => x=a
seien [mm] x,a\el\ \IN [/mm]
es gelte: f(x)=f(a)
die bedeutet:
[mm] 2^{x-1} [/mm] (2x-1) = [mm] 2^{a-1} [/mm] (2a-1)
<=> [mm] 2^x [/mm] *(1/2) [mm] *2x-2^{x-1} [/mm] = [mm] 2^a*(1/2) [/mm] * [mm] 2a-2^{a-1}
[/mm]
<=> [mm] 2^x [/mm] *x [mm] -2^{x-1} [/mm] = [mm] 2^a*x´-2^{a-1}
[/mm]
<=> [mm] 2^x *(x-(1/2))=2^a [/mm] *(a-(1/2))
Daraus erkennt man: x=a (oder?)
Surjektivität:
z.z. Bild(f)= [mm] \IN
[/mm]
Da mit f eine Bijektion von
[mm] \IN\times \IN [/mm] auf [mm] \IN [/mm] definiert ist, ist
Bild (f) [mm] \subset \IN [/mm] schon bewiesen.
Bleibt zu zeigen:
Bild (f) [mm] \supset \IN
[/mm]
(Errinnerung:
Bild (f) = [mm] \{y\el\ Feld (f)|\exists\ x\el\ Def(f): f(x)=y\})
[/mm]
[mm] n\in\ \IN
[/mm]
z.z.
[mm] n\in\ \{y|\exists\ x\el\ def(f) : f(x)=y\} [/mm]
d.h.
E [mm] k,l\in\ \IN [/mm] : f(k,l)=n
ges. [mm] k,l\in\ \IN [/mm] : f(k,l)=n
d.h. [mm] 2^{k-1}*(2l-1) [/mm] =n
<=> [mm] 2^k [/mm] *(1/2)*2l - [mm] 2^k [/mm] *(1/2) =n
<=> [mm] 2^k [/mm] *l - [mm] 2^k [/mm] *(1/2) =n
<=> [mm] 2^k* [/mm] (l-(1/2) )=n
Wie geht es jetzt weiter? Was muss ich machen?
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:
http://matheplanet.com
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:05 Di 20.06.2006 | | Autor: | Walde |
Hi pretty-face,
dein Injektivitätsbeweis, ist nicht ganz richtig, wie ich meine. Du hast ja eine Abbildung von [mm] \IN\times\IN\to\IN, [/mm] d.h. eine Funktion dessen Urbilder 2 Komponenten haben. Du solltest daher nicht mir f(x)=f(a) ansetzen, sondern mit [mm] f(k_1,l_1)=f(k_2,l_2) [/mm] und dann [mm] (k_1,l_1)=(k_2,l_2) [/mm] zeigen, also [mm] k_1=k_2 [/mm] und [mm] l_1=l_2.
[/mm]
Ansonsten ist dein Post etwas schwer zu lesen, weil irgendeine Formatierung nicht funktioniert hat (irgendas mit fed-Code), bitte korrigiere das doch noch (falls deine Frage dann noch nicht beantwortet sein sollte).
Für die Surjektivität muss man sich ein [mm] n\in\IN [/mm] vorgeben und zeigen, dass es [mm] k_n,l_n \in\IN [/mm] gibt, so dass [mm] f(k_n,l_n)=n
[/mm]
Da braucht es eine Fallunterscheidung:
Falls n ungerade, d.h . n hat die Form n=2m+1, [mm] m=0,1,\ldots
[/mm]
Dann wähle [mm] k_n=1 [/mm] und [mm] l_n=m+1 [/mm] :
[mm] f(1,m+1)=2^0*(2(m+1)-1)=2m+2-1=2m+1=n
[/mm]
Falls n gerade ist, kann man es in Primfaktoren der Form [mm] 2^x*y, [/mm] mit ungeradem y zerlegen.
Kommst du dann allein weiter? Kannst dann ja die Frage auf beantwortet stellen, ich habs aus versehen als Mitteilung gemacht.
L G walde
|
|
|
| |
|
Mein Vorschlag:
1.Injektivität
z.z. [mm] Vx,a\in\IN: [/mm] f(k,l)=f(a,b) => k=a [mm] \wedge [/mm] l=b
seien [mm] k,l,a,b\el\ \IN
[/mm]
es gelte: f(k,l)=f(a,b)
die bedeutet:
[mm] 2^{k-1} [/mm] (2l-1) = [mm] 2^{a-1} [/mm] (2b-1)
<=> [mm] 2^k [/mm] *(1/2) [mm] *2l-2^{k-1} [/mm] = [mm] 2^a*(1/2) [/mm] * [mm] 2b-2^{a-1}
[/mm]
<=> [mm] 2^k [/mm] *l [mm] -2^{k-1} [/mm] = [mm] 2^a*b-2^{a-1}
[/mm]
<=> [mm] 2^k*(l-(1/2))=2^a [/mm] *(b-(1/2))
Aber wie weiter?
2.Surjektivität:
z.z. Bild(f)= [mm] \IN
[/mm]
Da mit f eine Bijektion von
[mm] \IN\times \IN [/mm] auf [mm] \IN [/mm] definiert ist, ist
Bild (f) [mm] \subset \IN [/mm] schon bewiesen.
Bleibt zu zeigen:
Bild (f) [mm] \supset \IN
[/mm]
(Errinnerung:
Bild (f) = [mm] \{y\el\ Feld (f)|\exists\ x\el\ Def(f): f(x)=y\})
[/mm]
[mm] n\in\ \IN
[/mm]
z.z.
[mm] n\in\ \{y|\exists\ x\el\ def(f) : f(x)=y\}
[/mm]
d.h.
E [mm] k,l\in\ \IN [/mm] : f(k,l)=n
ges. [mm] k,l\in\ \IN [/mm] : f(k,l)=n
1.Fall: n ist ungerdae, n:=2m+1, [mm] m\in\ \IN
[/mm]
Wähle k=1 und l=m+1. also:
[mm] f(1,m+1)=2^0\cdot{}(2(m+1)-1)=2m+2-1=2m+1=n
[/mm]
2.Fall: n ist gerade, [mm] n:=2^x [/mm] *y [mm] \wedge [/mm] y ist ungerage und [mm] y\in\ \IN
[/mm]
Setze: x:=k-1 und y:=2l-1.
Daraus folgt:
[mm] 2^{k-1}* [/mm] (2l-1)= [mm] 2^x [/mm] *y =n.
Richtig so? Und wie beweise ich die Injektivität zu ende?
LG
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:08 Mi 21.06.2006 | | Autor: | Walde |
> Hallo walde,
> danke dass du dir die Zeit genommen hast, dir mein Problem anzukucken
> und mir eine gute Idee für eine Lösung gegeben hast. Kuck nochmal
> bitte, ob mein Surjektivitätsbeweis so richtig ist. Und vielleicht hast du
> noch einen Tipp für die Injektiviät, da komme nicht weiter.
Gern geschehen pretty-face,
bei der Surjektivität brauchst du wirklich nur den Teil, wo du dir ein n vorgibst und zeigst, dass es Zahlenpaare gibt, für die f(k,l)=n gilt, dann hast du gezeigt, dass ganz [mm] \IN [/mm] getroffen wird. Das stimmt bei dir so weit.
Der Teil mit
> Da mit f eine Bijektion von
> [mm] \IN\times\IN [/mm] auf [mm] \IN [/mm] definiert ist, ist
> Bild (f) [mm] \subset\IN [/mm] schon bewiesen.
ist so eh falsch, denn du sollst ja erst zeigen, dass f eine Bijektion ist.
Bei der Injektivität:
[mm] 2^k\cdot{}(l-(1/2))=2^a*(b-(1/2)) [/mm]
[mm] \gdw 2^{k-a}*(2l-1)=2b-1
[/mm]
aus k=a folgt sofort b=l, es muss also k=a gezeigt werden.
Falls k>a steht links eine durch 2 Teilbare Zahl. Rechts steht aber eine ungerade Zahl. Widerspruch.
Falls k<a steht bei
[mm] \gdw (2l-1)=(2b-1)*2^{a-k}
[/mm]
rechts eine gerade und links eine ungerade Zahl. Widerspruch.
Daraus folgt k=a
L G walde
|
|
|
| |
|
Vielen Dank!
Jetzt hab ich`s kappiert!
|
|
|
|
