IN x IN abzählbar < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 08:41 Di 06.11.2007 | | Autor: | epsilon1 |
| Aufgabe | Zeigen Sie, dass [mm] \IN [/mm] x [mm] \IN [/mm] abzählbar ist. Betrachten Sie dazu die Funktion
f : [mm] \IN^2 [/mm] -> [mm] \IN [/mm] mit (m,n) [mm] \mapsto \bruch{1}{2} [/mm] (n+m)(n+m+1)+n. |
Hi.
Ich bin am verzweifeln mit einer Logikaufgabe.
Ich muss nun also zeigen, dass die angegeben Funktion injektiv und surjektiv ist. Ich habe mich mal an der Injektivität versucht, bin aber gescheitert.
Seien a,b,c,d [mm] \in \IN [/mm] mit f(a,b) = f(c,d). Dann gilt 1/2 (a+b)(a+b+1)+a = 1/2 (c+d)(c+d+1)+c. Wenn man das nun ausmultipliziert, müsste man ja drausschließen können, dass a=c und b=d. Doch leider sehe ich das noch nicht, dass das gilt.
Kann mir also vielleicht jemand auf die Sprünge helfen? Wäre wirklich klasse.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:27 Di 06.11.2007 | | Autor: | statler |
Guten Morgen!
> Zeigen Sie, dass [mm]\IN[/mm] x [mm]\IN[/mm] abzählbar ist. Betrachten Sie
> dazu die Funktion
> f : [mm]\IN^2[/mm] -> [mm]\IN[/mm] mit (m,n) [mm]\mapsto \bruch{1}{2}[/mm]
> (n+m)(n+m+1)+n.
> Ich bin am verzweifeln mit einer Logikaufgabe.
Das ist schlecht und schlägt auf den Magen.
> Ich muss nun also zeigen, dass die angegeben Funktion
> injektiv und surjektiv ist. Ich habe mich mal an der
> Injektivität versucht, bin aber gescheitert.
Bei euch gehört anscheinend die Null zu den natürlichen Zahlen.
> Seien a,b,c,d [mm]\in \IN[/mm] mit f(a,b) = f(c,d). Dann gilt 1/2
> (a+b)(a+b+1)+a = 1/2 (c+d)(c+d+1)+c. Wenn man das nun
> ausmultipliziert, müsste man ja drausschließen können, dass
> a=c und b=d. Doch leider sehe ich das noch nicht, dass das
> gilt.
Wenn du deine Abb. für n+m = a = konstant untersuchst, dann kann n von 0 bis a laufen und mit etwas Umformung siehst du, daß die Abb. die Zahlen von [mm] \bruch{1}{2}(a^{2} [/mm] + a) + 0 bis +a darstellt. Hier ist die Abbildung schon mal injektiv, es gibt a+1 Argumente und ebensoviele Bilder. Was passiert jetzt z. B. für n+m = a+1? Von wo bis wo gehen hier die Bilder? Vielleicht kommst du mit diesem Hinweis jetzt selbst weiter?
Gruß aus HH-Harburg
Dieter
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:52 Di 06.11.2007 | | Autor: | epsilon1 |
Hallo.
Danke für die rasche Antwort, aber deinen Ansatz habe ich noch nicht so richtig verstanden.
Also ich habe gelernt, dass man sich quasi die Elemente hernimmt, beliebige und die Bilder gleichsetzt und dann muss man ein wenig herum experimentieren und kommt dann drauf, dass die Elemente gleich sind. Doch so richtig klappt das hier nicht.
Könntest du mir vielleicht mal deinen Gedankengang hinter diesem Ansatz verraten, da ich eigentlich überhaupt nicht verstehe, was du da eigentlich machst....
Tut mir leid.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:09 Di 06.11.2007 | | Autor: | statler |
> Danke für die rasche Antwort, aber deinen Ansatz habe ich
> noch nicht so richtig verstanden.
Also: Das Bild soll jetzt mal n heißen, und gesucht ist das Urbild (x,y). (Wir wollen zeigen, daß es höchstens eins gibt.) Dazu suche ich mir die Zahl a, so daß n [mm] \ge \bruch{1}{2}(a^{2} [/mm] + a), aber < [mm] \bruch{1}{2}((a+1)^{2} [/mm] + a+1) ist. Nach dem, was ich mir vorher überlegt habe, gibt es genau eine solche. Dann berechne ich die Differenz n - [mm] \bruch{1}{2}(a^{2} [/mm] + a), das wird mein gesuchtes x. Und y ist dann a-x. Überleg dir, daß es dieses (x,y) tut, also auf n abgebildet wird. Und daß es das einzige ist, geht aus meinen vorigen Überlegungen hervor. Du hast jetzt die Umkehrabb., also injektiv und surjektiv auf einen Schlag erledigt.
Vielleicht wird es durch ein Bsp. klarer, nimm n = 100 und such nach diesem Rezept das Urbild.
Gruß
Dieter
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:19 Di 06.11.2007 | | Autor: | epsilon1 |
Hallo.
Ich habe das jetzt mal mit dem Beispiel n=100 versucht.
Sei n=100. Dann soll gelte
100 >= [mm] 1/2(a^2 [/mm] + a)
50 >= [mm] a^2 [/mm] + a
100 <= [mm] 1/2((a+1)^2 [/mm] + a + 1)
50 <= [mm] (a+1)^2 [/mm] + a + 1
50 <= [mm] a^2 [/mm] + 2a + 1 + a + 1
48 <= [mm] a^2 [/mm] + 3a
Hier raus ergibt sich nun a = 6.
Berechne nun die Differenz.
100 - [mm] 1/2(6^2 [/mm] + 6)
= 100 - 1/2(42)
= 100 - 21
= 79 = x
y = a - x
y = -73
Dies ist ein Widerspruch zur Annahme, dass x,y [mm] \in \IN. [/mm] Kann es sein, dass y = x - a sein soll?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:27 Di 06.11.2007 | | Autor: | statler |
> Hallo.
>
> Ich habe das jetzt mal mit dem Beispiel n=100 versucht.
>
> Sei n=100. Dann soll gelte
> 100 >= [mm]1/2(a^2[/mm] + a)
> 50 >= [mm]a^2[/mm] + a
statt 50 muß das 200 heißen ...
Dieter
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:36 Di 06.11.2007 | | Autor: | epsilon1 |
Hi.
Stimmt. Also ich habe das ganze jetzt korrigiert und komme dann auf x=9 und y=4.
Diese Ergebnisse machen ja prinzipiell Sinn. Doch wie zeige ich jetzt, dass dies das einzige Paar ist, dass auf 100 abbildet?
Ebenso ist die Frage, arum jedes Element aus [mm] \IN [/mm] genau einmal getroffen wird.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:47 Di 06.11.2007 | | Autor: | statler |
Hi!
> Stimmt. Also ich habe das ganze jetzt korrigiert und komme
> dann auf x=9 und y=4.
![[ok]](/images/smileys/ok.gif "[ok]")
> Diese Ergebnisse machen ja prinzipiell Sinn. Doch wie
> zeige ich jetzt, dass dies das einzige Paar ist, dass auf
> 100 abbildet?
>
> Ebenso ist die Frage, arum jedes Element aus [mm]\IN[/mm] genau
> einmal getroffen wird.
Die Antwort auf beide Fragen steht schon da. Bei einem Paar, das auf 100 geht, muß die Summe der Komponenten 13 sein, weil 12 zu klein ist und 14 zu groß. Das geht aus meinem ersten Beitrag hervor, und ich möchte gerne, daß du das selbst erkennst. Ebenso geht daraus hervor, daß die 1. Komponente 9 sein muß. Versuch doch bitte mal, dir das selbst zurechtzulegen und hier einzustellen. Ich traue dir das zu, und der Lerneffekt ist größer  .
Dieter
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:08 Di 06.11.2007 | | Autor: | epsilon1 |
Ich versuche dann mal einen Beweis zu starten, auch wenn ich den ziemlich wischiwaschi finde.
Sei n [mm] \in \IN [/mm] mit n = Bild(f). Seien x,y [mm] \in \IN [/mm] mit f(x,y) = n. Finde nun ein a [mm] \in \IN [/mm] mit n >= 1/2 [mm] (a^2 [/mm] + a) und n <= 1/2 ((a + [mm] 1)^2 [/mm] + a + 1). Da a [mm] \in \IN [/mm] existiert genau ein a, welches beide Ungleichungen erfüllt, da (a-1) zu klein und (a+1) zu groß ist. Setze nun x = [mm] n-1/2(a^2 [/mm] + a) und y = a-x. Da man für jedes n [mm] \in \IN [/mm] genau ein [mm] a\in\IN [/mm] findet, ist dieses Paar (x,y) nun auf n abgebildet worden. Somit ist f injektiv und surjektiv und damit ist [mm] \IN [/mm] x [mm] \IN [/mm] abzählbar.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:56 Di 06.11.2007 | | Autor: | statler |
Mahlzeit!
> Ich versuche dann mal einen Beweis zu starten, auch wenn
> ich den ziemlich wischiwaschi finde.
>
> Sei n [mm]\in \IN[/mm] mit n = Bild(f). Seien x,y [mm]\in \IN[/mm] mit f(x,y)
> = n. Finde nun ein a [mm]\in \IN[/mm] mit n >= 1/2 [mm](a^2[/mm] + a) und n
> <= 1/2 ((a + [mm]1)^2[/mm] + a + 1). Da a [mm]\in \IN[/mm] existiert genau
> ein a, welches beide Ungleichungen erfüllt, da (a-1) zu
> klein und (a+1) zu groß ist. Setze nun x = [mm]n-1/2(a^2[/mm] + a)
> und y = a-x. Da man für jedes n [mm]\in \IN[/mm] genau ein [mm]a\in\IN[/mm]
> findet, ist dieses Paar (x,y) nun auf n abgebildet worden.
> Somit ist f injektiv und surjektiv und damit ist [mm]\IN[/mm] x [mm]\IN[/mm]
> abzählbar.
Mein Vorschlag:
Zunächst formen wir etwas um:
f(x,y) = [mm] \bruch{1}{2}(x+y)(x+y+1) [/mm] + x = [mm] \bruch{1}{2}((x+y)^{2} [/mm] + (x+y)) + x
Für x+y = a = konstant durchläuft f(x,y) die Zahlen von [mm] \bruch{1}{2}((x+y)^{2} [/mm] + (x+y)) = [mm] \bruch{1}{2}(a^{2} [/mm] + a) (für x = 0) bis [mm] \bruch{1}{2}((x+y)^{2} [/mm] + (x+y)) + a = [mm] \bruch{1}{2}(a^{2} [/mm] + a) + a (für x = a). Das sind a+1 aufeinanderfolgende natürliche Zahlen, die letzte ist die größte.
Die gleiche Betrachtung gilt entsprechend für x+y = a+1, und wir untersuchen mal eben die Zahlen, die durch diese (x,y) dargestellt werden, insbesondere die erste. Das wäre mit den gleichen Überlegungen [mm] \bruch{1}{2}((a+1)^{2} [/mm] + (a+1)), und wenn wir das ausrechnen, erkennen wir, daß es der unmittelbare Nachfolger der letzten aus dem vorigen Absatz ist wegen [mm] [\bruch{1}{2}(a^{2} [/mm] + a) + a] + 1 = [mm] \bruch{1}{2}((a+1)^{2} [/mm] + (a+1)).
Also sind die natürlichen Zahlen die disjunkte Vereinigung der Intervalle
[ [mm] \bruch{1}{2}(a^{2} [/mm] + a), [mm] \bruch{1}{2}((a+1)^{2} [/mm] + (a+1)) )
Das heißt, jedes n liegt in genau einem dieser Intervalle. Und damit ist x+y klar durch a bestimmt. Und wegen der umgeformten Definitionsgleichung für f(x,y) ist doch auch eindeutig bestimmt, welches x ich nehmen muß. Und damit auch y!
In Summe: Jedes n hat ein Urbild, und die Umkehrabb. haben wir hergeleitet. Bestimme erst a, dann x, dann y.
Gruß
Dieter
|
|
|
|
