Bijektion von P(N) nach R

28.06.2004, 18:26

SirJective

Auf diesen Beitrag antworten »

Bijektion von P(N) nach R

Die meisten von uns wissen - oder glauben uns - dass die Potenzmenge der natürlichen Zahlen gleichmächtig der Menge der reellen Zahlen ist. Aber wer von euch hat schonmal eine entsprechende Bijektion tatsächlich angegeben?

Ich will hier nicht mit dem üblichen Totschlagargument nur beweisen, dass
$\begin{align*} |\cal{P}({\bb N})| = |{\bb R}| \end{align*}$
ist (das ist leicht), sondern explizit eine Bijektion angeben.

Doch Vorsicht: Falle! geschockt

geschockt

Gruss,
SirJective

28.06.2004, 18:29

Mazze

Auf diesen Beitrag antworten »

Hm , es soll also eine eindeutige Abbildung von P(N) nach R und zurück geben. Ich frag mich grade worauf ich dann die leere menge die in P(N) enthalten ist abbilde verwirrt

verwirrt

, und von wo aus R ich auf dieses Element abbilde? Oder hab ich da was falsch verstanden? verwirrt

verwirrt

28.06.2004, 18:31

SirJective

Auf diesen Beitrag antworten »

Nein, Mazze, du hast richtig verstanden. Jeder Teilmenge von N (auch der leeren und ganz N) ist eine reelle Zahl zuzuordnen, und jede reelle Zahl (0, -1, pi) muss einer Teilmenge von N zugeordnet werden.

28.06.2004, 19:31

Mazze

Auf diesen Beitrag antworten »

Hm ich kann die reellen zahlen über eine teilmenge von P(N) beschreiben, aber das gibt der bijektion wegen keinen sinn.
Ich würde alle tupel (s,a,b) auf die jeweilige reelle zahl bilden lassen. Wenn s 0 ist wird auf negative zahlen abgebildet, wenn S 1 ist wird auf positive zahlen abgebildet. a ist der anteil vor dem komma und b der anteil nach dem komma. so ließen sich alle Brüche (auch die unendlichen) darstellen. Dieses 3er tupel würde auf imo alle reellen zahlen abbilden, wobei {0,0,0} auf die 0 abbildet.

Das problem

nicht surjektiv <=> nicht bijektiv <=> mist ^^

28.06.2004, 20:04

SirJective

Auf diesen Beitrag antworten »

Diese Funktion ist nichtmal surjektiv von der Menge der drei-Tupel {+-1} x N x N nach R.
Welches Tupel wird z.B. auf 1/3 abgebildet?

Außerdem muesstest du, um so von P(N) nach R zu kommen, erstmal eine Menge natürlicher Zahlen in ein Tupel umwandeln.

29.06.2004, 17:06

morbo

Auf diesen Beitrag antworten »

hm ... klingt nach nem interessanten problem ...

nur die tatsache dass man 1 sowohl durch 1.0000... als auch durch 0.9999... darstellen kann sollte bei einem versuch ne bijektion zu finden fuer arge probleme sorgen ...

Anzeige

29.06.2004, 23:12

SirJective

Auf diesen Beitrag antworten »

Richtig, morbo. Deshalb auch mein "Vorsicht: Falle" am Anfang.

02.07.2004, 19:07

adbmal

Auf diesen Beitrag antworten »

Bijektion von P(N) nach R
Folgendes Beispiel ist mir eingefallen:

Man nimmt nur das Intervall I=[0, 1[ aus R. Eine Bijektion zwischen I und R ist z.B. x > tan(x* pi/2).
Als nächstes nimmt man die Kettenbruchecklung der Zahlen, da gibts nämlich keine störende 9er Periode, sondern verschiedene "Ziffernfolgen" repräsentieren auch verschiedene Zahlen.
Dann soll das Ganze von Anfang an im Binärsystem laufen.
R kann man also in 0-1-Folgen ausdrücken. Bei P(N) ist ja klar, wie man 0-1-Folgen aus einer Teilmenge M von N macht. (x_i = 1 wenn i \in M sonst 0)

Man könnte auch theoretisch rangehen:
Es ist leichter, eine Injektion I1 von R nach P(N) und eine Injektion I2 von P(N) nach R zu finden.

Aus I1 und I2 kann man nun eine Bijektion zusammenbasteln. Zumindest gibt es einen Satz, der besagt, dass dann eine Bijektion existiert. Und der Beweis müsste über Konstruktion zu dieser magischen Bijektion führen.

Gruß adbmal

03.07.2004, 12:12

SirJective

Auf diesen Beitrag antworten »

RE: Bijektion von P(N) nach R
Dass tan(x*pi/2) von [0,1) bijektiv nach R abbildet, glaub ich weniger, aber es man kann sehr leicht eine Bijektion von (0,1) nach R angeben (z.B. x->tan(pi*(x-1/2))), und mit wenig Aufwand eine Bijektion von [0,1) nach R (die allerdings nicht stetig ist, aber trotzdem relativ einfach).

Die Kettenbruchentwicklung ist keine schlechte Idee, aber vermutlich "ein bisschen" problematisch: Wie kommst du von der Kettenbruchentwicklung auf eine Ziffernfolge? Und wie schaffst du das umkehrbar eindeutig?

Wie unterscheidest zu z.B. die Kettenbruchentwicklungen $\begin{align*} \sqrt{3}-1 = [0;1,2,1,2,...] \end{align*}$ und $\begin{align*} \sqrt{37}-5 = [0;12,12,...] \end{align*}$ ? Gut, dieses Beispiel ist im Dezimalsystem, aber auch im Binärsystem wirst du zwischen den Kettenbruchentwicklungen $\begin{align*} (\sqrt{5}-1)/2 = [0;1,1,1,1,...]_2 \end{align*}$ und $\begin{align*} (\sqrt{13}-3)/2 = [0;11,11,...]_2 \end{align*}$ unterscheiden müssen.

Die kanonische Zuordnung von P(N) nach {0,1}^N ist klar.

Das Cantor-Bernstein-Schröder-Theorem ist das Totschlagargument, das meist verwendet wird, um die Gleichmächtigkeit zweier Mengen zu zeigen.
Dieser Satz liefert eine Bijektion, aber der Beweis ist nichtkonstruktiv, liefert also keine Darstellung der Bijektion, in die man einen Wert einsetzen und tatsächlich ausrechnen kann, was das Bild ist.

03.07.2004, 12:42

Wolfskehl

Auf diesen Beitrag antworten »

RE: Bijektion von P(N) nach R
eine frage: soll es eine bijektion zwischen dem WERT der reellen zahl und der teilmenge von N sein oder zwischen der DARSTELLUNGSart und der teilmenge von N?

wenn es um den wert geht, könnte man 1 und 0,9999 ja zusammen fassen. wenn es um die darstellung geht, würde 1 auf was anderes abgebildet als 0,9999...

im übrign gibt es dieses problem unendlich oft, auch z.b. bei 0,4999 und 0,5...

ok aber es geht um eine bijektion. d.h. die abbildung muss schon eindeutig sein. ergo muss man 0,999 und 1 schon getrennt betrachten, denn wenn man wüsste, worauf 1 abgebildet wird und dann die möglichkeit hätte, das ergebnis rückwärts auf 1 oder 0,999 abzubilden, wäre es ja nicht mehr eindeutig. es sei denn man fasst 1 und 0,9999 zusammen als reelle zahl mit dem wert 1...

03.07.2004, 12:56

Wolfskehl

Auf diesen Beitrag antworten »

RE: Bijektion von P(N) nach R
ok nehmen wir an 1 wäre was anders als 0,9999

mein vorschlag:

1. wird die reelle zahl zerlegt in die ziffern vor und nach dem komma. d.h. es gibt z.b. die 5. vor und die 8. nach dem komma.
2. wird die zahl binär dargestellt. also 10,5 wird z.b. zu 1010,1
3. man untersucht abwechselnd immer die nächste zahl vor und nach dem komma. d.h. zuerst die 1. stelle vor dem komma, dann die 1. hinter dem komma, dann die 2. vor dem komma, die 2. dahinter usw. bis beide 0 sind.
bei dem beispiel 1010,1 = 1010,100 käme dann die folge raus: 0110001 bzw. 011000100000000....(lauter nullen)
4. man schaut die wie vielte stelle 1 ist. in diesem fall wäre das die 2. die 3. und die 7. die teilmenge von N wäre hier also {2,3,7}
5. umgekehrt kann man z.b. aus der teilmege {1,3,5,6} die folge 101011 machen und das wäre 111,001 = 7,125.

oder gibts da einwände?

1 wäre dann: {1}, 0,9999 wäre die menge aller geraden natürlichen zahlen. eundeutig wäre das schon. bildet man den wert ab, würde man beide mal 1 abbilden auf {1} {1} würde man dann auf 1 abbilden und könnte das als 1 oder 0,9999 darstellen. bildet man die darstellung ab, so würde man 1 auf {1} abbilden und 0,9999 auf die menge der geraden zahlen, was umgekehrt eindeutig wäre. ein problem gäbe es nur dann, wenn man den wert von 1 und 0,9999 auf {1} abbildet und dann umgekehrt nicht sicher ist ob man {1} auf 1 oder 0,9999 abbildet aber wenn es um den WERT geht wäre das ja irrelevant oder?

03.07.2004, 13:17

Benutzer

Auf diesen Beitrag antworten »

RE: Bijektion von P(N) nach R
Hallo,

vielleicht geht es so:

1. Schritt: Definiere eine Hilfsfunktion f: P(N) --> [0,1[ kanonisch durch f(M) = Summe(k in M) 2^(-k-1) (die Null ist eine natürliche Zahl. nur um entsprechenden Flamewars vorzubeugen Big Laugh

Big Laugh

).
2. Schritt: Setze A gleich der Menge aller endlichen oder koendlichen Teilmengen von N, und
B:= P(N)\A. Dann P(N) = A u B, ausserdem ist der Schnitt von f(A) und f(B) leer und A abzählbar, ja sogar rekursiv aufzählbar, und für x!=x' beide aus B gilt f(x) != f(x'). Setze A := {M_1, M_2, M_3, ...} entsprechend der gewählten Aufzählung.
3. Schritt: Wähle eine möglichst einfache Aufzählung von f(A), und setze f(A) = {h_1, h_2,....} entsprechend. Weil f(A) gerade alle Zahlen enthält, die eine endliche Binärdarstellung besitzen, ist das nicht weiter schwierig.
4. Schritt setze g(M) := f(M), falls M in A, und g(M_i) = h_i für alle i. Wähle eine berechenbare Bijektion g': [0,1[ ---> R, und g'og tut's dann hoffentlich.

Mfg,
der weiterhin namenlose Benutzer

03.07.2004, 17:15

SirJective

Auf diesen Beitrag antworten »

Um ein mögliches Missverständnis auszuschließen, setze ich hiermit fest, dass für den Rest dieses Threads die 0 eine natürliche Zahl sei, N = {0, 1, 2, ...}.

Weiterhin schreiben wir - wenn nichts anderes dazugesagt wird - die Dezimal-, Dual- oder sonstige adische Darstellung stets ohne 9-Periode bzw. 1-Periode, verwenden also die 0-Periode. Eine Darstellung (oder auch Entwicklung), die eine 0-Periode hat, nenne ich endliche Darstellung.

@Wolfskehl:
Wie ich morbo bereits geschrieben habe, ist 1 = 0.999... und dies ist eigentlich das einzige Problem bei der Bijektion.

Zitat:

mein vorschlag:
[...]

Damit hättest du eine Injektion von der Menge der (nichtnegativen!) Dezimalbrüche in die Potenzmenge von N. (Keine Bijektion, da z.B. N nicht im Bild liegt - es gibt schließlich keine reelle Zahl mit unendlich vielen Vorkommastellen.)

Zitat:

1 wäre dann: {1}, 0,9999 wäre die menge aller geraden natürlichen zahlen. [...]
ein problem gäbe es nur dann, wenn man den wert von 1 und 0,9999 auf {1} abbildet und dann umgekehrt nicht sicher ist ob man {1} auf 1 oder 0,9999 abbildet aber wenn es um den WERT geht wäre das ja irrelevant oder?

Tja, wenn es um den Wert geht, ist 1 und 0,999... dasselbe, aber die Mengen {1} und 2N sind nicht dasselbe. Dies ist also keine Bijektion von R nach P(N).

@namenloser Benutzer:

Zitat:

1. Schritt: Definiere eine Hilfsfunktion f: P(N) --> [0,1[ kanonisch durch f(M) = Summe(k in M) 2^(-k-1) (die Null ist eine natürliche Zahl. nur um entsprechenden Flamewars vorzubeugen ).

Kleine Bemerkung (ist aber nicht tragisch): f(N) = 1, also bildet f von P(N) nach [0, 1] ab. Und das surjektiv. Würden wir nur in die Menge der Dezimalbrüche zwischen 0 und 0,999... abbilden, hätten wir unsere Bijektion. So haben wir aber noch keine (hast du auch nicht behauptet).

Zitat:

2. Schritt: Setze A gleich der Menge aller endlichen oder koendlichen Teilmengen von N, und B:= P(N)\A. Dann P(N) = A u B, ausserdem ist der Schnitt von f(A) und f(B) leer und A abzählbar, ja sogar rekursiv aufzählbar, und für x!=x' beide aus B gilt f(x) != f(x'). Setze A := {M_1, M_2, M_3, ...} entsprechend der gewählten Aufzählung.

P(N) = A u B ist klar.
f(A) n f(B) = {} ist leicht zu sehen, da f(A) gerade die Menge der reellen Zahlen zwischen 0 und 1 ist, die eine endliche Dualbruchentwicklung haben, und f(B) aus denen besteht, die eine unendliche Dualbruchentwicklung haben.
A abzählbar ist klar.
f: B -> [0,1] injektiv ist auch klar, da die Zahlen in f(B) sowieso eine eindeutige Dualbruchentwicklung haben.

So, bleibt also noch das Problem zu beheben, dass f: A -> [0,1] nicht injektiv ist, da z.B. die Mengen {1} und {2, 3, 4, 5, 6, 7,...} auf 0,5 = 0,49999... abgebildet werden.

Dazu zählen wir die Elemente von A auf.
Eine Möglichkeit ist, die endlichen Mengen lexikographisch anzuordnen und die Komplemente jeweils dahinterzusetzen:
{}, N, {0}, N\{0}, {1}, N\{1}, {0, 1}, N\{0, 1}, {2}, N\{2}, {0, 2}, N\{0, 2}, ...

Schön wäre es noch, wenn man diese Abzählung explizit angeben könnte, damit man sofort den Index z.B. der Menge {0, 4, 10} wüsste.

Zitat:

3. Schritt: Wähle eine möglichst einfache Aufzählung von f(A), und setze f(A) = {h_1, h_2,....} entsprechend. Weil f(A) gerade alle Zahlen enthält, die eine endliche Binärdarstellung besitzen, ist das nicht weiter schwierig.

Auch f(A) ist abzählbar, und wir können diese Menge aufzählen. Da f(A) aus den Zahlen mit endlicher Dualbruchentwicklung besteht, sind alle diese Zahlen rational mit einer 2-Potenz im Nenner. Eine Möglichkeit der Anordnung ist, sie lexikographisch nach Nenner und Zähler zu sortieren:
0, 1, 1/2, 1/4, 3/4, 1/8, 3/8, 5/8, 7/8, ...
Auch hier wäre eine explizite Indexangabe nützlich. In der Abbildungsrichtung von P(N) nach R brauchen wir aber eigentlich nur die Angabe, welche die n-te Zahl in dieser Liste ist (also vorgegebener Index).

Zitat:

4. Schritt setze g(M) := f(M), falls M in A, und g(M_i) = h_i für alle i.

Damit haben wir endlich eine Bijektion von P(N) nach [0,1] bestimmt.

Zitat:

Wähle eine berechenbare Bijektion g': [0,1[ ---> R, und g'og tut's dann hoffentlich.

Haben wir eine Bijektion g': [0,1] -> R, dann ist g' o g die gesuchte Abbildung.

So, wie findet man nun ein "angenehmes" g' ?
Da eine Bijektion von (0,1) nach R bereits angegeben wurde, finden wir vielleicht eine von [0,1] nach (0,1)?

Gruss,
SirJective

03.07.2004, 18:51

Wolfskehl

Auf diesen Beitrag antworten »

naja so ganz stimmt das auch nicht. es wäre immerhin eine injektion der positiven reellen zahlen in die potenzmenge von N. +pi kann ich ja auch auf eine teilmenge von N abbilden, da diese unendlich groß sein darf. um die negativen noch zu bekommen, könnte man einfach definieren, dass man für die positiven jede 2. ziffer zu einer 1 macht und bei den negativen jede 2. dazwischen.

dass es keine bijektion ist, stimmt natürlich...(leider).

und wie wäre es wenn man sowohl 1 als auch 0,9999 auf {1} abbildet? wenn es um den wert geht, wäre das ja eindeutig. der wert 1 würde auf {1} abgebildet und {1} dann auf den wert von 1, egal wie man das nun darstellt.

03.07.2004, 19:37

SirJective

Auf diesen Beitrag antworten »

Zitat:

Original von Wolfskehl
naja so ganz stimmt das auch nicht. es wäre immerhin eine injektion der positiven reellen zahlen in die potenzmenge von N.

Stimmt, Denkfehler meinerseits. Sobald wir uns auf eine Schreibung festgelegt haben, ist das eine Injektion von R+ nach P(N). Mit der "Einfädelung" einer Negativ-Kennung hast du eine Injektion von R nach P(N).

Zitat:

und wie wäre es wenn man sowohl 1 als auch 0,9999 auf {1} abbildet?

Ja, das ist eine solche Festlegung auf eine Schreibung (die ich auch vorgeschlagen habe).

Machen wir doch zwischendurch mal das Spiel, zwei Injektionen anzugeben: eine von R nach P(N) hast du bereits gegeben, und wie kommt man injektiv von P(N) nach R?

03.07.2004, 20:07

Wolfskehl

Auf diesen Beitrag antworten »

ich würde sagen: genau umgekehrt, mit der einschränkung, dass man nur auf die reellenzahlen zwischen 0 und 1 abbildet, da man sonst ja N auf eine unendlich lange reelle zahl abbilden müsste. hieße also z.b. {2,4,6} wird abgebildet auf 0.010101 in der binärdarstellung...diese abbildung wäre aber auch wiederum nicht surjektiv. aber injektiv ja schon.

03.07.2004, 23:48

SirJective

Auf diesen Beitrag antworten »

Da haben wir wieder unsere drei Probleme:

1. Es wird {0} auf dieselbe Zahl wie {1, 2, 3, 4, ...} abgebildet.
2. Wenn ich dich richtig verstanden habe, wird {0, 1} auf binär 1,1 abgebildet. Unsere Zählung müsste also mit der ersten Nachkommastelle beginnen, so dass {0, 1} auf binär 0,11 = 3/4 abgebildet wird.
3. Diese Abbildung wäre dann surjektiv nach [0, 1], aber nicht injektiv (ach das hatten wir schon).

Tip: Bilde M ab auf sum_{k in M} 3^(-k-1) ab.
Diese Abbildung ist injektiv, aber nicht surjektiv von P(N) nach R.

04.07.2004, 01:50

Wolfskehl

Auf diesen Beitrag antworten »

oder du nimmst sum_(k in m) 5^(-k-0,5)

bzw. sum_(k in M) a^(-k-1) mit a größer 2.

06.07.2004, 12:38

Shopgirl

Auf diesen Beitrag antworten »

Hallo SirJective,

der Index einer endlichen oder koendlichen Menge in deiner Liste ist leicht anzugeben.

Zitat:

Original von SirJective
Eine Möglichkeit ist, die endlichen Mengen lexikographisch anzuordnen und die Komplemente jeweils dahinterzusetzen:
{}, N, {0}, N\{0}, {1}, N\{1}, {0, 1}, N\{0, 1}, {2}, N\{2}, {0, 2}, N\{0, 2}, ...

Der Index der endlichen Menge M ist gegeben durch
$\begin{align*} I(M) = \bigsum_{k\in M} 2^{k+1} \end{align*}$ .
Das ist gerade das doppelte der Binaerzahl, die durch M ausgedrueckt wird.
Der Index des Komplements von M ist
$\begin{align*} I(\mathbb{N}\setminus M) = I(M)+1 \end{align*}$ .
Die Indizes beginnen bei 0.

Zitat:

Da f(A) aus den Zahlen mit endlicher Dualbruchentwicklung besteht, sind alle diese Zahlen rational mit einer 2-Potenz im Nenner. Eine Möglichkeit der Anordnung ist, sie lexikographisch nach Nenner und Zähler zu sortieren:
0, 1, 1/2, 1/4, 3/4, 1/8, 3/8, 5/8, 7/8, ...

Die Zahl $\begin{align*} \frac{2m+1}{2^n} \end{align*}$ mit n>0, 0 <= m < 2^(n-1) hat den Index
$\begin{align*} J(\frac{2m+1}{2^n}) = 2^{n-1} + m+1 \end{align*}$
Auch hier beginnen die Indizes bei 0 (da J(0)=0,J(1)=1,J(1/2)=2 ist).

Umgekehrt steht an der Stelle n>=2 die Zahl
$\begin{align*} a_n = \frac{2(n-2^{p(n-1)})-1}{2^{p(n-1)+1}} \end{align*}$ ,
wobei $\begin{align*} p(n) = \lfloor ld(n) \rfloor \end{align*}$ die groesste ganze Zahl mit $\begin{align*} 2^{p(n)}\leq n \end{align*}$ liefert.
Stellt man n>=2 dar als n = 2^s + t + 1, mit s>=0 und 0<=t<2^s, dann ist p(n-1) = s und n-2^s = t+1, und man erhaelt die Darstellung
$\begin{align*} a_n = \frac{2t+1}{2^{s+1}} \end{align*}$ .

06.07.2004, 19:28

Dozo

Auf diesen Beitrag antworten »

Hallo Shopgirl und alle anderen,

deine Lösung ist wahrscheinlich richtig, hab das nicht bis zum Ende nachvollziehen können. Die Sortierung von f(A) scheint mir aber irgendwie zu kompliziert.

Ich werde mal die Idee des misteriösen namenlosen Benutzers aufgreifen und versuchen das ganze expliziter auszuführen.

$\begin{align*} f: P(\mathbb{N}) -> [0,1] \end{align*}$
$\begin{align*} f(M)=\frac 1 2 \bigsum_{k\in M} {(\frac 1 2 )^k} \end{align*}$

f ist zwar surjektiv, aber nicht injektiv. Das soll jetzt verbessert werden durch den Trick von Shopgirl (leicht modifiziert). Ich definiere noch schnell A1 als die endlichen und A2 als die coendlichen Elemente von P(N). Wie gehabt ist B:=N \ (A1 u A2).

$\begin{align*} h: P(\mathbb{N}) -> [0,1] \end{align*}$
$\begin{align*} h(M)=\left{\array{\frac 1 2 f(M)&M\in A_1\\ \frac 1 2 f(\mathbb{N} \setminus M) + \frac 1 2&M\in A_2\\f(M)&M\in B}\right. \end{align*}$

h ist nun bijektiv. (hoff ich doch mal...)
Nun muss man noch von [0,1] möglichst einfach nach R kommen.

$\begin{align*} t(x)=\tan(\pi(x-\frac 1 2)) \end{align*}$
Damit kommt man von (0,1) nach R. Man muss also irgendwie noch die beiden Zahlen 0 und 1 in R unterbringen. Hab mir eben gedacht, bei den natürlichen Zahlen ist das ja ganz einfach - und die natürlichen Zahlen sind in den reellen enthalten. Also könnte man so ansetzten:

$\begin{align*} v: [0,1] -> \mathbb{R} \end{align*}$
$\begin{align*} v(x)=\left{\array{0&x=0\\1&x=1\\t(x)+2&t(x)\in \mathbb{N}\\t(x)&\text{sonst}}\right. \end{align*}$

v sollte jetzt auch bijektiv sein, so dass man die gesuchte Abbildung als

$\begin{align*} \kappa: P(\mathbb{N}) -> \mathbb{R} \end{align*}$
$\begin{align*} \kappa(M) := v(h(M)) \end{align*}$
erhält.

06.07.2004, 23:30

SirJective

Auf diesen Beitrag antworten »

Danke Shopgirl, ich hatte keine Lust, die Formeln explizit hinzuschreiben (hab sie mir nicht selbst überlegt) smile

smile

Dozo, deine Idee ist genial!

Dass v eine Bijektion ist, sehe ich ein.
Bei h muss ich noch etwas überlegen...
h(A_1) sind die endlichen Dualbrüche in [0, 1/2).
h(A_2) sind die endlichen Dualbrüche in [1/2,1).
1 liegt nicht im Bild.

Aber damit haben wir eine Bijektion von P(N) nach [0,1), so dass man nur v ein wenig modifizieren muss:
1 -> 1 lassen wir weg und die dritte Zeile wird zu
v(x) = t(x)+1 für t(x) in N

Wow, wir haben die Bijektion.
Dann lasst uns doch mal das Bild von
{},
{2},
{0,1,4,10},
{0,2,4,6,8,10,...}
und
{1,1,2,3,5,8,13,21,34,55,...}
bestimmen :P

07.07.2004, 16:01

Leopold

Auf diesen Beitrag antworten »

Hübsch, was ihr euch da ausdenkt. Kompliment!

Ich denke aber, daß noch ein paar Unebenheiten darin sind, sofern ich das alles richtig verstehe.

Ich bezeichne mit $\begin{align*} \mathbb{Q}_2 \end{align*}$ die Menge derjenigen rationalen Zahlen, deren Nenner in der vollständig gekürzten Bruchdarstellung eine Zweierpotenz ist.

Wenn ich Dozos h richtig interpretiere, dann erreicht man mit dem ersten Fall alle Elemente von $\begin{align*} [\ 0 \ ,\ \frac{1}{2}\ \) \ \cap \ \mathbb{Q}_2\ \end{align*}$ , mit dem zweiten Fall alle Elemente von $\begin{align*} [\ \frac{1}{2} \ ,\ 1 \ \) \ \cap \ \mathbb{Q}_2\ \end{align*}$ und mit dem dritten Fall die sonstigen reellen Zahlen in $\begin{align*} [\ 0 \ ,\ 1 \ \) \end{align*}$ . Nur 1 wird nicht erreicht (ich sehe es jedenfalls nicht). h ist also eine Bijektion

$\begin{align*} h: \ P(\mathbb{N}) \ -> \ [\ 0 \ ,\ 1 \ \) \end{align*}$

(Das hat alles auch schon SirJective festgestellt. Ich muß das aber immer noch einmal selbst aufschreiben, um mich hineinzudenken.)

Das ist aber nicht weiter schlimm. Denn jetzt kann man eine Bijektion

$\begin{align*} r: \ \[\ 0 \ ,\ 1 \ \) \ -> \ \(\ 0 \ ,\ 1 \ \) \end{align*}$

angeben, z.B. so:

$\begin{align*} r(x) \ = \ x+\frac{1}{2} \ , \ \ 0 \leq x < \frac{1}{2} \end{align*}$
$\begin{align*} r(x) \ = \ x-\frac{1}{4} \ , \ \ \frac{1}{2} \leq x < \frac{3}{4} \end{align*}$
$\begin{align*} r(x) \ = \ x-\frac{5}{8} \ , \ \ \frac{3}{4} \leq x < \frac{7}{8} \end{align*}$

usw. (Idee nach Kamke, Mengenlehre, Sammlung Göschen, Walter de Gruyter 1971)

etwas formaler:

$\begin{align*} r(x) \ = \ x \ - \ \(1-\frac{3}{2^{k+1}}\) \ , \ \ 1-\frac{1}{2^k} \leq x < 1-\frac{1}{2^{k+1}} \ \ mit \ einem \ k \in \{0,1,2,3,...\} \end{align*}$

Und um jetzt bijektiv nach $\begin{align*} \mathbb{R} \end{align*}$ zu kommen, gibt es viele Möglichkeiten. Am einfachsten sind vielleicht die stetigen (sogar differenzierbaren) Abbildungen

$\begin{align*} s: \ \ \(\ 0 \ , \ 1 \ \) \ -> \ \mathbb{R} \end{align*}$

$\begin{align*} s(x) \ = \ \frac{x}{1-|x|^{\alpha}} \end{align*}$

wobei $\begin{align*} \alpha \end{align*}$ eine beliebiger reeller Parameter >0 sein kann.

Edit (Korrektur):
SirJective hat mich darauf aufmerksam gemacht, daß es oben

$\begin{align*} s(x) \ = \ \frac{2x-1}{1-|2x-1|^{\alpha}} \end{align*}$

heißen muß.

08.07.2004, 09:11

SirJective

Auf diesen Beitrag antworten »

Zitat:

Original von Leopold
Ich bezeichne mit $\begin{align*} \mathbb{Q}_2 \end{align*}$ die Menge derjenigen rationalen Zahlen, deren Nenner in der vollständig gekürzten Bruchdarstellung eine Zweierpotenz ist.

Mir fällt da gerade ein, da du nun dieser Menge einen Namen gibst: Für diese Menge gibt es bereits eine übliche Schreibweise: [latex=inline]\mathbb{Z}[\frac{1}{2}][/latex]. [latex=inline]\mathbb{Q}_2[/latex] steht in der Algebra für die Menge der 2-adischen Zahlen (siehe p-adische Zahlen).

Zitat:

h ist also eine Bijektion
$\begin{align*} h: \ P(\mathbb{N}) \ -> \ [\ 0 \ ,\ 1 \ \) \end{align*}$

(Das hat alles auch schon SirJective festgestellt. Ich muß das aber immer noch einmal selbst aufschreiben, um mich hineinzudenken.)

Genau.

Zitat:

Das ist aber nicht weiter schlimm. Denn jetzt kann man eine Bijektion
$\begin{align*} r: \ \[\ 0 \ ,\ 1 \ \) \ -> \ \(\ 0 \ ,\ 1 \ \) \end{align*}$
angeben, [...]

Und um jetzt bijektiv nach $\begin{align*} \mathbb{R} \end{align*}$ zu kommen, gibt es viele Möglichkeiten. Am einfachsten sind vielleicht die stetigen (sogar differenzierbaren) Abbildungen
[...]

Ja, fast. Dein s bildet (-1,1) bijektiv nach R ab.

s: (0,1) -> R
$\begin{eqnarray*} s(x) = \frac{2x-1}{1-|2x-1|^\alpha} \end{eqnarray*}$

Da es sehr viele mehr oder weniger einfache Funktionen gibt, die (0,1) bijektiv auf R abbilden, kann man eigentlich keine bevorzugen.

Den Weg von [0,1) über (0,1) nach R bin ich bisher auch immer gegangen, finde Dozos Idee aber richtig gut:

"Verschiebe" R ein wenig, um Platz für ein weiteres Bild zu machen:
p: R -> R\{0}, p(x) = x, falls x nicht in N, p(x) = x+1, falls x in N.
Dann ist Dozos angepasste Funktion v diese:
v: [0,1) -> R, v(0) = 0, v(x) = p(t(x)) für x in (0,1).

Gruss,
SirJective

08.07.2004, 10:37

Leopold

Auf diesen Beitrag antworten »

Was du $\begin{eqnarray*} \mathbb{Q}_2 \end{eqnarray*}$ nennst, kenne ich als $\begin{eqnarray*} \Omega_2 \end{eqnarray*}$ . Aber sicher ist die Bezeichnung $\begin{eqnarray*} \mathbb{Z}[\frac{1}{2}] \end{eqnarray*}$ sinnvoller, da es sich um eine simple Ringadjunktion handelt.

08.07.2004, 13:05

SirJective

Auf diesen Beitrag antworten »

[ot] Q_2

Zitat:

Original von Leopold
Was du $\begin{eqnarray*} \mathbb{Q}_2 \end{eqnarray*}$ nennst, kenne ich als $\begin{eqnarray*} \Omega_2 \end{eqnarray*}$ .

Ui, woher? Ich kenne bisher nur Serre, Cassels, Scharlau, Lorenz, die alle Q_2 schreiben.

08.07.2004, 14:37

Leopold

Auf diesen Beitrag antworten »

der Klassiker: van der Waerden, Algebra, Band II
In Notation und Formelsprache sicher nicht aktuell, aber immer noch mein liebstes Algebra-Buch zum Nachschlagen. Es ist halt der Ursprung der modernen Algebra (nach Vorlesungen von Emmy Noether).

12.07.2004, 22:58

Irrlicht

Auf diesen Beitrag antworten »

Ich kenne $\begin{eqnarray*} \Omega_p \end{eqnarray*}$ nur als Vervollständigung des algebraischen Abschlusses von $\begin{eqnarray*} \mathbb{Q}_p \end{eqnarray*}$ , auch als $\begin{eqnarray*} \mathbb{C}_p \end{eqnarray*}$ bezeichnet.

11.11.2004, 05:43

WebFritzi

Auf diesen Beitrag antworten »

Zitat:

Original von Leopold
h ist also eine Bijektion

$\begin{align*} h: \ P(\mathbb{N}) \ -> \ [\ 0 \ ,\ 1 \ \) \end{align*}$

Wieso? Es ist doch IN in B enthalten und f(IN) = 1.

EDIT: Achso, IN ist ja eigentlich co-endlich. Aber IN\IN ist ja die leere Menge, und die ist schon in A1 enthalten. Also können wir IN aus A2 herausnehmen und B zuschreiben. Dann sind wir fertig.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »