Kardinalzahlen/Mächtigkeit < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 09:11 Mi 22.05.2013 | | Autor: | Lu- |
| Aufgabe | Zeigen Sie
[mm] |\IN| [/mm] = [mm] |\IQ|
[/mm]
(Sie können Cantor-Schröder-Bernstein verwenden, nicht in formaler Mengenlehre ZFC sondern in "Alltagsmathematik") |
Hallo, ich scheitere bei einer (relativ einfachen) Aufgabe.
-) [mm] |\IQ| \ge |\IN| [/mm] mit f(n)=n eine Injektion
-) [mm] |\IQ| \le |\IN|
[/mm]
Kam ich nicht wirklich weiter. Hab im Internet nachgeschaut und da steht:
s [mm] \in \IQ: [/mm] s= p/q mit p [mm] \in \IZ [/mm] und q [mm] \in \IN [/mm] ohne 0 ggT(p,q)=1
g(p/q)= [mm] \begin{cases} (|p|,|q|), & \mbox{für } p/q \ge 0 \\(2|p|,2|q|), & \mbox{für } p/q <0 \end{cases}
[/mm]
J [mm] \circ [/mm] g : [mm] \IQ [/mm] -> [mm] \IN [/mm] injektiv als Zusammensetzung injektiver Funktionen wobei J die Cantorsche Paarungsfunktion ist.
Nun, ich wäre nie auf das g draufgekommen.. Wie kann man da von selbst draufkommen? Warum gilt Injektivität beim Betrag?
Seien s,a [mm] \in \IQ [/mm] d.h. s= p/q, a=r/t mit ggT(p,q)=1 und ggT(r,t)=1
Angenommen: g(p/q)= g(r/t)
ZZ.: s= a d.h. p=r [mm] \wedge [/mm] q=t
Fall 1: p/q [mm] \ge [/mm] 0 [mm] \wedge [/mm] r/t [mm] \ge [/mm] 0
(|p| , |q| )= (|r|, |t| )
<=>|p|=|r| , |q|=|t|
p/q [mm] \ge [/mm] 0 <=> p [mm] \ge [/mm] 0 (da q [mm] \in \IN)
[/mm]
r/t [mm] \ge [/mm] 0 <=> r [mm] \ge [/mm] 0 (da t [mm] \in \IN)
[/mm]
<=> p=r, q=t
Fall 2: p/q < 0 [mm] \wedge [/mm] r/t < 0
(2|p| ,2 |q| )= (2|r|, 2|t| )
<=>|p|=|r| , |q|=|t|
-p=-r <=> p=r
q=t
Fall 3: p/q [mm] \ge [/mm] 0 [mm] \wedge [/mm] r/t < 0
(|p| , |q| )= (2|r|, 2|t| )
<=> |p|=2|r|, |q| = 2 |t|
<=> p=-2r, q= 2t
???
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 03:04 Do 23.05.2013 | | Autor: | tobit09 |
Hallo Lu-,
> -) [mm]|\IQ| \ge |\IN|[/mm] mit f(n)=n eine Injektion
[mm] $f\colon\IN\to\IQ$. [/mm] ![[ok]](/images/smileys/ok.gif "[ok]")
> -) [mm]|\IQ| \le |\IN|[/mm]
> Kam ich nicht wirklich weiter. Hab im
> Internet nachgeschaut und da steht:
>
> s [mm]\in \IQ:[/mm] s= p/q mit p [mm]\in \IZ[/mm] und q [mm]\in \IN[/mm] ohne 0
> ggT(p,q)=1
> g(p/q)= [mm]\begin{cases} (|p|,|q|), & \mbox{für } p/q \ge 0 \\(2|p|,2|q|), & \mbox{für } p/q <0 \end{cases}[/mm]
>
> J [mm]\circ[/mm] g : [mm]\IQ[/mm] -> [mm]\IN[/mm] injektiv als Zusammensetzung
> injektiver Funktionen wobei J die Cantorsche
> Paarungsfunktion ist.
>
> Nun, ich wäre nie auf das g draufgekommen.. Wie kann man
> da von selbst draufkommen? Warum gilt Injektivität beim
> Betrag?
Idee ist, eine injektive Abbildung [mm] $g\colon\IQ\to\IN\times\IN$ [/mm] zu basteln. Die Elemente von [mm] $\IQ$ [/mm] sind ja, wenn man sie als gekürzte Brüche mit Nenner $>0$ schreibt, quasi spezielle Zahlenpaare. Da liegt es nahe, den Elementen von [mm] $\IQ$ [/mm] dieses Zahlenpaar zuzuordnen. Ein Problem tritt dabei auf: Der Zähler könnte negativ sein. Für diesen Fall ist nun die Idee, den entsprechenden Elementen von [mm] $\IQ$ [/mm] Paare natürlicher Zahlen zuzuordnen, die keinem gekürzten Bruch entsprechen. Da bietet sich z.B. $(2|p|,2q)$ für p/q mit p [mm]\in \IZ[/mm] und q [mm]\in \IN[/mm] ohne 0 an. Anstelle der 2 hätte man auch jede beliebige natürliche Zahl [mm] $\ge2$ [/mm] nehmen können. Das Entscheidende ist, dass das Zahlenpaar keinem gekürzten Bruch entspricht.
> Seien s,a [mm]\in \IQ[/mm] d.h. s= p/q, a=r/t mit ggT(p,q)=1 und
> ggT(r,t)=1
Und [mm] $q,t\in\IN\setminus\{0\}$ [/mm] willst du sicherlich annehmen.
> Angenommen: g(p/q)= g(r/t)
> ZZ.: s= a d.h. p=r [mm]\wedge[/mm] q=t
>
> Fall 1: p/q [mm]\ge[/mm] 0 [mm]\wedge[/mm] r/t [mm]\ge[/mm] 0
> (|p| , |q| )= (|r|, |t| )
> <=>|p|=|r| , |q|=|t|
> p/q [mm]\ge[/mm] 0 <=> p [mm]\ge[/mm] 0 (da q [mm]\in \IN)[/mm]
> r/t [mm]\ge[/mm] 0 <=> r [mm]\ge[/mm]
> 0 (da t [mm]\in \IN)[/mm]
> <=> p=r, q=t
>
>
> Fall 2: p/q < 0 [mm]\wedge[/mm] r/t < 0
> (2|p| ,2 |q| )= (2|r|, 2|t| )
> <=>|p|=|r| , |q|=|t|
> -p=-r <=> p=r
> q=t
> Fall 3: p/q [mm]\ge[/mm] 0 [mm]\wedge[/mm] r/t < 0
> (|p| , |q| )= (2|r|, 2|t| )
> <=> |p|=2|r|, |q| = 2 |t|
> <=> p=-2r, q= 2t
> ???
Also haben p und q den gemeinsamen Teiler 2 und somit [mm] $\operatorname{ggT}(p,q)\not=1$. [/mm] Dieser Fall kann also glücklicherweise nicht eintreten.
Viele Grüße
Tobias
|
|
|
|
