Bij. N->NxN < Abbildungen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Konstruiere Bijektionen in den folgenden Fällen:
a) F1 : N → Z
b) F2 : N → {(m, n) ∈ N × N : mn = 0}
c) F3 : N → N × N
d) F4 : N → Z × Z.
N: nat. Zahlen
Z: ganze Zahlen |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo liebe Community, ich stocke gerade bei dieser Aufgabe, genauer gesagt bei der c.
Für a und b habe ich jeweils zwei stückweise definierte Abbildungen gefunden, nur scheint es mir unmöglich bzw. wenn möglich dann sehr umständlich, eine bijektive Abbildung aller natürlichen Zahlen auf ein kartesisches Produkt von natürlichen Zahlen zu finden.
Überlegt habe ich mir folgende Vorgehensweise:
0 -> 0.0
1 -> 1.0
2 -> 1.1
3 -> 0.1
4 -> 0.2
5 -> 1.2
6 -> 2.2
7 -> 2.1
8 -> 2.0
9 -> 3.0
10 -> 3.1
11 -> 3.2
12 -> 3.3
13 -> 2.3
...
Das Muster sollte jetzt klar sein.
Erst dachte ich an den Algorithmus, dass ich irgendwie Rekursiv die Lösungsmenge bilden kann, habe aber keinen Dunst wie ich z.B 2.3 aus der 13 erstellen soll bzw. wie überhaupt eine solche Abbildungsvorschrift aussehen könnte.
Ich hoffe, Ihr könnt mir irgendwie einen Denkanstoss in die richtige Richtung geben.
MfG
K.T.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:43 Mi 12.11.2014 | | Autor: | Marcel |
Hallo,
> Konstruiere Bijektionen in den folgenden Fällen:
> a) F1 : N → Z
> b) F2 : N → {(m, n) ∈ N × N : mn = 0}
> c) F3 : N → N × N
> d) F4 : N → Z × Z.
>
> N: nat. Zahlen
> Z: ganze Zahlen
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
>
> Hallo liebe Community, ich stocke gerade bei dieser
> Aufgabe, genauer gesagt bei der c.
>
> Für a und b habe ich jeweils zwei stückweise definierte
> Abbildungen gefunden, nur scheint es mir unmöglich bzw.
> wenn möglich dann sehr umständlich, eine bijektive
> Abbildung aller natürlichen Zahlen auf ein kartesisches
> Produkt von natürlichen Zahlen zu finden.
>
> Überlegt habe ich mir folgende Vorgehensweise:
> 0 -> 0.0
> 1 -> 1.0
> 2 -> 1.1
> 3 -> 0.1
> 4 -> 0.2
> 5 -> 1.2
> 6 -> 2.2
> 7 -> 2.1
> 8 -> 2.0
> 9 -> 3.0
> 10 -> 3.1
> 11 -> 3.2
> 12 -> 3.3
> 13 -> 2.3
> ...
> Das Muster sollte jetzt klar sein.
>
> Erst dachte ich an den Algorithmus, dass ich irgendwie
> Rekursiv die Lösungsmenge bilden kann, habe aber keinen
> Dunst wie ich z.B 2.3 aus der 13 erstellen soll bzw. wie
> überhaupt eine solche Abbildungsvorschrift aussehen
> könnte.
>
> Ich hoffe, Ihr könnt mir irgendwie einen Denkanstoss in
> die richtige Richtung geben.
eine Bijektion [mm] $\IN \to \IZ \times \IZ$ [/mm] habe ich
hier (klick!)
angedeutet. (Tobias hatte, glaube ich, sogar eine Berechnungsvorschrift
verlinkt - einfach mal ein wenig durchklicken und lesen).
Zu obigem: Du kannst durchaus auch Dein Muster *algorithmisch* beschreiben.
Auch damit kann man dann arbeiten, um Injektivität und Surjektivität
einzusehen.
Wie kann man sowas beschreiben? Machen wir das, was wir sehen (ob
wir eine *Rechenvorschrift* vielleicht dann auch ableiten können, sehen
wir vielleicht später):
Ich mache aber ein anderes Verfahren: Ich laufe immer, *sobald auf der
x-Achse ein neuer Punkt hergenommen werden kann*, von diesem los,
und gehe dann so lange nach oben, bis ich zum ersten mal nach links
gehen kann, ohne bereits markierte Punkte zu treffen. Dann gehe ich
nach links etc. pp.
Am Anfang nehmen wir die "ersten 4 benachbarten Punkte" beim "Quadratdurchlauf"
entgegen des Uhrzeigersinns mit, wir starten meinetwegen in (0|0).
Da das Verfahren injektiv bleiben soll, springen wir dann nicht auf (0|0) zurück,
und auch (0|1) müssen wir überspringen, deswegen kommen wir nach
0 --> (0|0)
1 --> (1|0)
2 --> (1|1)
3 --> (0|1)
zu
4 --> (1+1|0)
Jetzt kann ich zwei Punkte nach oben gehen:
5 --> (2|1)
(nach links darf ich nicht gehen, da (1|1) schon markiert)
6 --> (2|2)
und nun auch noch 2 Mal nach links:
7 --> (1|2)
8 --> (0|2)
Jetzt gehe ich wieder zu dem ersten Nichtmarkierten Punkt der x-Achse:
9 --> (3|0)
10 --> (3|1)
11 --> (3|2)
12 --> (3|3)
13 --> (2|3)
14 --> (1|3)
15 --> (0|3)
Usw. usf.
Erkennst Du die Struktur dieses Verfahrens? Schauen wir erstmal nur auf
die x-Achse:
(0|0) "trägt Nummer 0"
(1|0) "trägt Nummer 1"
(2|0) "trägt Nummer 4"
(3|0) "trägt Nummer 9"
(4|0) "trägt Nummer 16"
Man könnte also bei der Beschreibung des Verfahrens erstmal die Idee
entwickeln:
Ist $n [mm] \in \IN$ [/mm] eine Quadratzahl [mm] $n=m^2$ [/mm] mit einem $m [mm] \in \IN\,,$ [/mm] so setzen wir
$n [mm] \longmapsto (\sqrt{n}|0)=(\sqrt{m^2}|0)=(m|0)$
[/mm]
fest.
Jetzt nochmal der Blick auf die Vorgehensweise:
Nach
0 --> (0|0)
gehen wir direkt zu
1 --> (1|0).
Jetzt können wir 1 nach oben gehen, danach noch 1 nach links weiter, wir
enden also bei
3 --> (1-1|0+1)=(0|1)
Wie oben angedeutet geht es nun mit
4 --> (2|0)
weiter: Wir können nun 2 mal direkt nach oben und von da aus noch zwei
mal direkt nach links gehen, enden also bei
4+4=8 --> (0|2) [Weg: ((2|0),(2|1),(2|2),(1|2),(0|2))]
D.h.: Wenn wir an der Stelle
[mm] $m^2$ [/mm] --> (m|0)
starten, gehen wir von da aus bis zum Punkt (m|m) nach oben (wir markieren
also nach (m|0) nochmal [mm] $m\,$ [/mm] Punkte) und wenn wir an (m|m) angekommen
sind, gehen wir nochmal um m Punkte nach links
(Weg: ((m|m),(m-1|m),...,(1|m),(0|m)) ).
Erstmal so ein kleiner *Kontrollgedanken*:
Wenn die obige Überlegung stimmt, dann gilt doch wohl:
[mm] $m^2+m+m=(m+1)^2-1\,.$
[/mm]
Dies folgt, weil: Wir starten "auf der x-Achse an der Stelle [mm] $m^2$, [/mm] und können
dann m direkt drüberliegende Werte markieren, und von dem obersten
Wert davon markieren wir die m links liegenden Werte - danach hüpfen
wir auf der x-Achse zur Stelle [mm] $(m+1)^2$".
[/mm]
Dass in der Tat
[mm] $m^2+m+m=(m+1)^2-1$
[/mm]
ist - das brauchen wir nicht wirklich diskutieren, oder?
Ich beweise jetzt mal die Surjektivität dieses Verfahrens - die Injektivität
kann man durchaus mit den obigen Überlegungen begründen, meinetwegen
erkläre ich das bei Rückfrage auch nochmal ergänzend:
Sei
$(a|b) [mm] \in \IN \times \IN$ [/mm] (bei Dir ist $0 [mm] \in \IN$).
[/mm]
Setze
[mm] $x:=\max\{a,b\}\,.$
[/mm]
1. Fall: [mm] $x=a\,.$
[/mm]
Wähle
[mm] $m:=a^2\,.$
[/mm]
Dann wissen wir, dass wegen
[mm] $m=a^2$ [/mm] --> (a|0)
also
(a|0) "die Nummer [mm] $m\,$ [/mm] trägt".
Nach dem oben beschriebenen Verfahren folgt (beachte $b [mm] \le [/mm] a$)
m+b --> (a|b),
d.h. "(a|b) trägt die Nummer [mm] $m+b\,.$"
[/mm]
2. Fall: [mm] $x=b\,:$
[/mm]
Wähle
[mm] $m:=b^2\,.$
[/mm]
Dann wissen wir
$m$ --> (b|0)
[mm] $\Rightarrow$
[/mm]
$m+b$ --> (b|b)
Von da aus gehen wir (beachte $a [mm] \le [/mm] b$) noch b-a Stellen nach links:
[mm] $m+b+(b-a)\,$ [/mm] --> (b-(b-a)|b),d.h.
[mm] $b^2+2b-a\,$ [/mm] --> (a|b).
D.h. "(a|b) trägt die Nummer [mm] $b^2+2b-a$".
[/mm]
Wir testen das mal: Oben hatten wir
13 --> (2|3).
Bekommen wir aus (2|3) die 13 zurück?
Es ist a=2 und b=3. Also
x = [mm] $\max\{a,b\}=3=b\,.$
[/mm]
Wir sind im 2. Fall: Nach obiger Formel sollte also
$13 [mm] =m+2b-a=b^2+2b-a$
[/mm]
sein, mit [mm] $m=b^2=9\,.$
[/mm]
Und in der Tat:
[mm] $b^2+2b-a=9+6-2=15-2=13\,.$
[/mm]
Schauen wir auch mal
11 --> (3|2)
an: Da wir im 1. Fall sind, sollte mit
$a=3$ dann [mm] $m=a^2=9$
[/mm]
und daher
[mm] $11=a^2+b$
[/mm]
gelten: In der Tat ist
[mm] $a^2+b=3^2+2=9+2=11\,.$
[/mm]
P.S. Es kann gut sein, dass hier noch einige Verschreiber/Vertipper zu
korrigieren sind...
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:07 Do 13.11.2014 | | Autor: | Marcel |
Hallo,
spaßeshalber habe ich mal die Methode mit "Berechnungsvorschrift" (man
kann sich also vor Ablauf des Algorithmus ausgeben lassen, welche Nummer
ein Zahlenpaar trägt) in Octave programmiert.
Das Programm findet sich im Anhang. Wenn jemand Lust hat, kann er ja mal
ein gif daraus erstellen, damit man sieht, was da passiert.
Ansonsten: Octave ist freie Software! (Wer andere bevorzugt, kann sich
ja auch den Quellcode angucken und es entsprechend übersetzen - wenn
es jemand in R macht: Dann brauch' ich mir diese Mühe nicht nochmal zu
machen, denn das werde/würde ich sonst vermutlich auch noch machen!)
![[a]](/images/paperclip.gif "Dateianhänge") Abzaehlung_von_IN0xIN0.m
Gruß,
Marcel
Dateianhänge:
Anhang Nr. 1 (Typ: m) [nicht öffentlich]
|
|
|
|
