Surjektion zeigen < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:10 Mi 10.07.2013 | | Autor: | ne1 |
| Aufgabe | | Zeige, dass $f: [mm] \IN \times \IN \rightarrow \IN, [/mm] f(x,y) = [mm] 2^x(2y+1)-1$ [/mm] surjektiv. |
Ich habe zwar die Lösung und in der Lösung steht, dass man ein beliebiges $n [mm] \in \IN$ [/mm] nimmt. Sei $x$ ein größte natürliche Zahl, so dass [mm] $2^x [/mm] | (n+1)$. Den letzten Satz verstehe ich nicht. Ich kann z. B. $n = 10$ nehmen. Dann habe ich [mm] $2^x [/mm] | 11$, aber es gibt kein $x [mm] \in \IN$, [/mm] so dass [mm] $2^x [/mm] | 11$.
|
|
| |
|
Hallo,
für die Aufgabe ist IMO noch wichtig zu klären, was [mm] \IN [/mm] sein soll. Wenn die natürlichen Zahlen hier wie in der Zahlentheorie üblich mit 1 beginnen, funktioniert das allerdings mit der Surjektivität nicht.
Ansonsten (für [mm] 0\in\IN) [/mm] reicht es dir hier völlig, die Fälle x=0 und x=1 zu bertachten, da brauchst du dir keinerlei Gedanken zu Teilbarkeit o.ä. machen. Spiele das einfach mal durch: halte x=0 fest und zähle y hoch, das gleiche für x=1.
Gruß, Diophant
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:38 Mi 10.07.2013 | | Autor: | ne1 |
Natürlich war hier [mm] $\IN [/mm] =: [mm] \IN_0$ [/mm] gemeint.
OK, super Idee, aber wozu $x=1$ nachdem ich $x=0$ gemacht habe?
Ich nehme ein beliebiges $n [mm] \in \IN$. [/mm] Jetzt definiere ich mir $x=0$ und [mm] $y=\bruch{n}{2}$ [/mm] also [mm] $f(0,\bruch{n}{2}) [/mm] = n$. Richtig?
|
|
|
| |
|
Hallo,
> Natürlich war hier [mm]\IN =: \IN_0[/mm] gemeint.
>
> OK, super Idee, aber wozu [mm]x=1[/mm] nachdem ich [mm]x=0[/mm] gemacht
> habe?
Du hast das nicht durchgespielt oder? 
>
> Ich nehme ein beliebiges [mm]n \in \IN[/mm]. Jetzt definiere ich mir
> [mm]x=0[/mm] und [mm]y=\bruch{n}{2}[/mm] also [mm]f(0,\bruch{n}{2}) = n[/mm]. Richtig?
Nein, denn wenn n beliebig ist, kann man schwerlich y=n/2 setzen. Rechne doch mal durch, welche Werte dir die Funktion für x=0 liefert. Welche fehlen dir jetzt noch? Bekommst du die alle mit x=1? Wenn ja, warum?
Gruß, Diophnat
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:39 Mi 10.07.2013 | | Autor: | ne1 |
Ich nehme ein beliebiges gerades $n [mm] \in \IN$ [/mm] und definiere $x = 0$ und $y = [mm] \bruch{n}{2}$ [/mm] (jetzt ist $y [mm] \in \IN$). $f(0,\bruch{n}{2}) [/mm] = n$. Hab also $0,2,4,...$.
Analog kann ich $x=1$ und $y = [mm] \bruch{n-1}{4}$ [/mm] betrachten (für ungerade $n$ und $n > 4$) und kriege $1,5,9,14,...$.
Es fehlen mir noch $3,7,11...$.
Meiner Meinung nach gibt es keine Surjektion, weil $7 = [mm] 2^x [/mm] (2y+1) -1$, d.h. $8 = [mm] 2^x [/mm] (2y-1)$. [mm] $2^x \in \{1,2,4,8,...\} [/mm] =:A$ und $2y+1 [mm] \in \{1,3,5,7,...\} [/mm] =: B$ und es gibt kein $a [mm] \in [/mm] A$ und $b [mm] \in [/mm] B$, so dass $a [mm] \cdot [/mm] b = 8$.
|
|
|
| |
|
Hallo,
Zu deinem obigen Einwand:
[mm] 8=2^3=2^3*1=2^3*(2*0+1)
[/mm]
Vielleicht machst du dir einmal eine Tabelle mit den Funktionswerten für Paare kleiner Zahlen x,y. Dann siehst du vielleicht klarer, was da passiert und weshalb das ganze surjektiv ist.
Man kann es auch recht einfach einsehen. Man betrachtet die Gleichung
[mm] n+1=2^x*(2y+1)
[/mm]
und unterscheidet die Fälle
-n+1 ist ungerade
-n+1 ist gerade
Für beide Fälle ist IMO leicht einzusehen, dass die Faktorisierung auf der rechten Seite möglich sein muss. Im Fall von n+1 ungerade eben [mm] 2^0=1 [/mm] und (2y+1)=n+1 mit y=n/2.
Versuche dich mal an dem anderen Fall.
Gruß, Diophant
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 02:01 Do 11.07.2013 | | Autor: | ne1 |
> Hallo,
>
> Zu deinem obigen Einwand:
>
> [mm]8=2^3=2^3*1=2^3*(2*0+1)[/mm]
Selbstverständlich. War ein Fehler von mir.
> Man kann es auch recht einfach einsehen. Man betrachtet die
> Gleichung
>
> [mm]n+1=2^x*(2y+1)[/mm]
>
> und unterscheidet die Fälle
>
> -n+1 ist ungerade
> -n+1 ist gerade
>
> Für beide Fälle ist IMO leicht einzusehen, dass die
> Faktorisierung auf der rechten Seite möglich sein muss. Im
> Fall von n+1 ungerade eben [mm]2^0=1[/mm] und (2y+1)=n+1 mit y=n/2.
>
> Versuche dich mal an dem anderen Fall.
>
>
> Gruß, Diophant
Für $n$ gerade ist wie schon geschrieben $x = 0$ und $y = n/2$.
Für $n = 1,5,9,...$, $x=1$ und $y = [mm] \bruch{n-1}{4}$.
[/mm]
$n = 3,7,11,...$ ist aber sehr unregelmäßig:
$f(2,0) = 3$
$f(3,0) = 7$
$f(3,1) = 11$
$f(4,0) = 15$
$f(2,2) = 19$.
|
|
|
| |
|
Hallo ne1,
> > Hallo,
> >
> > Zu deinem obigen Einwand:
> >
> > [mm]8=2^3=2^3*1=2^3*(2*0+1)[/mm]
> Selbstverständlich. War ein Fehler von mir.
>
> > Man kann es auch recht einfach einsehen. Man betrachtet die
> > Gleichung
> >
> > [mm]n+1=2^x*(2y+1)[/mm]
> >
> > und unterscheidet die Fälle
> >
> > -n+1 ist ungerade
> > -n+1 ist gerade
> >
> > Für beide Fälle ist IMO leicht einzusehen, dass die
> > Faktorisierung auf der rechten Seite möglich sein muss. Im
> > Fall von n+1 ungerade eben [mm]2^0=1[/mm] und (2y+1)=n+1 mit y=n/2.
> >
> > Versuche dich mal an dem anderen Fall.
> >
> >
> > Gruß, Diophant
> Für [mm]n[/mm] gerade ist wie schon geschrieben [mm]x = 0[/mm] und [mm]y = n/2[/mm].
>
> Für [mm]n = 1,5,9,...[/mm], [mm]x=1[/mm] und [mm]y = \bruch{n-1}{4}[/mm].
>
> [mm]n = 3,7,11,...[/mm] ist aber sehr unregelmäßig:
> [mm]f(2,0) = 3[/mm]
> [mm]f(3,0) = 7[/mm]
> [mm]f(3,1) = 11[/mm]
> [mm]f(4,0) = 15[/mm]
> [mm]f(2,2) = 19[/mm].
>
So funktioniert Mathematik nicht. Du rechnest da mechanisch irgendwelches Zeugs herunter ohne darüber nachzudenken, was du tust.
Wenn man die Tabelle vernünftig aufstellt, dann kann man schön sehen, dass jeder Wert mindestens einmal vormommen muss (BTW: gehört hier auch noch dazu, auf Injektivität zu untersuchen)?
Darum noch einmal (mach doch mal, was man dir rät  ): untersuche die Gleichung
[mm] n+1=2^x(2y+1)
[/mm]
für die Fälle (n+1) ungerade bzw. (n+1) gerade. Zeige für beide Fälle, dass jeweils für jedes n eine Faktorisierung der Formn auf der rechten Seite existiert. Mache dir dabei zu Nutze, dass du mit dem Faktor (2y+1) jede ungerade natürliche Zahl erzeugen kannst.
Und rechne nicht blindlings, sondern denke ein wenig über den Sinn der Aufgabe nach.
Gruß, Diophant
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:31 Do 11.07.2013 | | Autor: | ne1 |
>(BTW: gehört hier auch noch dazu, auf Injektivität zu untersuchen)?
Ja, habe ich aber schon gemacht.
Ehrlich gesagt, verstehe ich es nicht ganz. Du hast mir zuerst gesagt, dass es für die Aufgabe reicht die Fälle $x=0$ und $x=1$ zu untersuchen. Danach stellen wir fest, dass wir für $n = 7$, $x = 3$ benötigen...
|
|
|
| |
|
Hallo,
> >(BTW: gehört hier auch noch dazu, auf Injektivität zu
> untersuchen)?
> Ja, habe ich aber schon gemacht.
>
> Ehrlich gesagt, verstehe ich es nicht ganz. Du hast mir
> zuerst gesagt, dass es für die Aufgabe reicht die Fälle
> [mm]x=0[/mm] und [mm]x=1[/mm] zu untersuchen.
Das war vielleicht etwas unglücklich formuliert. Sagen wir so: mir hat das ausgereicht, um mir das Prinzip klarzumachen. Weil ich so etwas nicht mit irgendwelchen vorgekauten Algorithmen angehe, sondern ich habe mir überlegt, was genau die Funktion 'macht'. Und es ist ja auch müßig, darüber zu diskutieren, was schon geraten wurde.
> Danach stellen wir fest, dass
> wir für [mm]n = 7[/mm], [mm]x = 3[/mm] benötigen...
Es zieht sich wie ein roter Faden durch den Thread, dass du die Dinge, die man (in dem Fall ich) dir geraten hat, nicht beachtest.
Man kann sich durch das Hochzählen von x und y klar machen, dass für alle geraden n x=0 gelten muss (weshalb?). Jetzt schaut man sich am Beispiel x=1 an, was da passiert, wenn wir y hochzählen. Der Funktioswert steigt beim Inkrementieren von y dabei jeweils um [mm] 2^x [/mm] an, und so wie die 'Startwerte' für y=0 jeweils liegen, muss dabei jede enstehende Lücke irgenwann aufgefüllt werden.
Formal ist es viel einfacher:
[mm] (n+1)=2^x*(2y+1) [/mm] ; [mm] n,x,y\in\IN
[/mm]
Die Gleichung gilt immer in dem Sinne, dass zu jedem n ein Paar (x,y) existiert, welches die Gleichung erfüllt. Ist n+1 ungerade, so muss x=0 gelten. Da man mit 2y+1 jede beliebige ungerade natürliche Zahl erzeugen kann, folgt die Behauptung. Ist n+1 gerade und eine Zweierpotenz, so ist y=0. Ist n+1 gerade aber keine Zweierpotenz, dann gibt es eine ungerade Zahl 2y+1 mit 2y+1|n+1.
Ist dir das jetzt klar?
Und ganz ehrlich: ich gebe gerne Antworten in diesem Forum. Ich gehe dabei auch nach bestem Wissen und Gewissen vor. Ich mache das aber freiwillig und muss von daher keinerlei Garantien für die Richtigkeit meiner Antworten abgeben. Außerdem bin ich der Überzeugung, dass das Nachdenken über die Aufgabe trotz Forum und Antworten zunächst einmal eine Bringschuld der Fragesteller ist.
Gruß, Diophant
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:58 Do 11.07.2013 | | Autor: | ne1 |
>Ist n+1 gerade aber keine Zweierpotenz, dann gibt es eine ungerade Zahl 2y+1 mit 2y+1|n+1.
Das war der Entscheidende Satz der mir gefehlt hat. Danke.
|
|
|
|
