17.07.201917.07.2019 von Stefan Hartmann

Aufgabe 4

(i) Gibt es eine bijektive Abbildung ${\mathbb N} \to {\mathbb Z}$ ?

(ii) Gibt es für $n \in {\mathbb N}$ eine bijektive Abbildung ${\mathbb N} \to {\mathbb N} \times \{1,\ldots,n\}$ ?

(iii) Gibt es eine bijektive Abbildung ${\mathbb N} \to {\mathbb N}\times {\mathbb N}$ ?

(iv) Gibt es eine bijektive Abbildung ${\mathbb N} \to {\mathbb Q}$ ?

21

Hinterlasse einen Kommentar

Mitglied

Maja1111

i) Sei $X \in \mathbb{N}$ und $Y \in \mathbb{Z}$ . Bei $f(x) = (-1)^x * x$ gibt es eine bijektive Abbildung von $\mathbb{N}$ nach $\mathbb{Z}$ unter der Bedingung, dass es für alle $y \in Y$ genau ein $x \in X$ mit $f(x) = y$ gibt.

Autor

Stefan Hartmann

Erst einmal müsste es $X={\mathbb N}$ und $Y = {\mathbb Z}$ heißen und nicht mit dem Element-Zeichen. Eigentlich brauchst du das aber auch nicht hinzuschreiben. Nun zu deiner eigentlichen Lösung. Denk nochmal genau nach. Bijektiv heißt insbesondere surjektiv. Es müsste also für alle $y \in {\mathbb Z}$ ein $x\in {\mathbb N}$ geben mit $f(x)=(-1)^x*x=y$ . Insbesondere müsste es also zu $y=1$ ein $x\in {\mathbb N}$ geben mit $f(x)=(-1)^x*x=1$ . Kann es ein solches $x\in {\mathhb N}$ geben? Wenn nein, warum genau nicht? Kannst du deine Abbildung vielleicht etwas modifizieren, so dass sie auch surjektiv und insgesamt bijektiv wird? Die grundsätzliche Idee ist ja gut! Was soll passieren? Die $0$ soll auf die $0$ abgebildet werden (beim Bosch zählt ja die $0$ zu den natürlichen Zahlen dazu), die $1$ auf die $-1$ , die $2$ auf die $1$ , die $3$ auf die $-2$ und die $4$ auf die $2$ usw. Im Grunde reicht das so schon. Aber du willst die Funktion ja explizit angeben. Wie kann man das erreichen? Tipp: Es gibt die sogenannte Gaußklammer $g(x)=\lfloor x\rfloor$ . Google den Begriff mal und versuche sie einzusetzen, um deine Funktion geeignet zu „basteln“. 😊

Mitglied

Maja1111

> dass alle übrigen denkbaren Werte für
> x nicht 1 ergeben können, brauche ich
> vermutlich nicht näher auszuführen).

Zunächst hattest du auch $x=-1$ eingesetzt, was gar nicht geht, da deine Funktion auf $\mathbb{N}$ definiert ist. Aber unabhängig davon: Doch, das müsste man im Mathestudium machen. Es ist aber einfach wegen

$f(0)=0 \ne 1$

und

$|f(x)|=|(-1)^x\cdot x|=|x|>1$ für alle $x>1$

klar.

Mitglied

Maja1111

Jetzt habe ich versehentlich vergessen, das ganze in die Gaußklammern zu setzen und eine Änderung ist leider auch nicht mehr möglich…

Autor

Stefan Hartmann

Liebe Maja,

das stimmt fast, aber noch nicht ganz. Leider ist bei dir $g(0)=0$ und $g(1)=0$ , also ist deine Funktion nicht injektiv. Wie kann man das retten? Schreib die Funktion bitte auch nochmal hin mit den Gaußklammern, damit ich sehe, ob das Minuszeichen in der Gaußklammer steht oder außerhalb.

Aber sehr gute Idee von dir!

Autor

Stefan Hartmann

Ich habe deinen Lösungsversuch aus Versehen überschrieben, tut mir leid. 😕 Kannst du die Funktion bitte nochmal hinschreiben, und dabei meine Hinweise beachten und dann auch mit den Gaußklammern?

Mitglied

Maja1111

Die ursprüngliche Lösung war $-\lfloor (x-1)/2 \rfloor$ für x ungerade und $\lfloor x/2 \rfloor$ für x gerade.
Mein Verbesserungsvorschlag wäre nun $-\lfloor ((x-1)/2)-1 \rfloor$ für x ungerade.

Autor

Stefan Hartmann

Die zweite Funktion kann nicht richtig sein, da sowohl 1 als auch 2 auf 1 abgebildet werden:

$-\lfloor ((1-1)/2)-1\rfloor =-\lfloor -1 \rfloor = 1$ .

Aber die erste Funktion ist fast richtig und man braucht die Gaußklammern für diese Darstellung mit Fallunterscheidung dann gar nicht. Richtig ist:

$f(x)=-(x+1)/2$ , wenn $x$ ungerade,
$f(x)=x/2$ , wenn $x$ gerade.

Mitglied

Maja1111

Sei $X = \mathbb{N}$ und $Y = \mathbb{N} \times \{ 1,2,...,n \}$ . Man bilde $1 \mapsto (1,1)$ , $2 \mapsto (1,2)$ , $3 \mapsto (1,3)$ , $n \mapsto (1,n)$ ab.
injektiv zz.: $f(x) = f(y) \Rightarrow x = y$
surjektiv zz.: $f(Y) = X$
da injektiv und surjektiv erfüllt sind, ist die Abbildung bijektiv.

Autor

Stefan Hartmann

Grundsätzlich richtig, aber es fehlt noch einiges an Argumenten. Erst einmal solltest du die Abbildung genauer angeben. Aufgrund deiner Darstellung ist beispielsweise nicht klar, worauf $n+1$ abgebildet wird. Wenn man es in „Pünktchen-Form“ angibt, also mit $\dots$ , müsstest du schon ein paar mehr Punkte beschreiben, insbesondere solche, deren Bilder als erste Komponente nicht $1$ haben. 😊 Außerdem muss man noch beachten (das hatte ich selbst vergessen 🙈), dass im Bosch die natürlichen Zahlen bei $0$ beginnen, man also auch ein Bild der $0$ angeben muss, also $0\mapsto (0,1), 1 \mapsto (0,2)$ usw. Noch schöner wäre es, wenn man die Abbildung explizit angeben könnte. Das geht hier sogar relativ einfach: Jedes $m \in \mathbb{N}$ lässt sich (Division mit Rest) in der Form $m= k\cdot n + r$ schreiben, mit $k\in \mathbb{N}$ und $r\in \mathbb{N}$ , $0\le r<n$ . Hast du eine Idee, auf welches Element aus $\mathbb{N} \times \{1,2,\ldots,n\}$ dann $m$ abgebildet wird?

Autor

Stefan Hartmann

Damit kannst du dann auch wirklich zeigen, dass die Abbildung injektiv und surjetiv ist. Vorsicht: Deine Definition von „surjektiv“ ist nicht korrekt. Richtig lautet sie: Für alle $y\in Y$ gibt es ein $x\in X$ mit $f(x)=y$ . Hier also: Für alle $(y_1,y_2) \in \mathbb{N} \times \{1,2,\ldots,n\}$ gibt es ein $x\in \mathbb{N}$ mit $f(x)=(y_1,y_2)$ . Dieses $x$ ist hier sehr einfach anzugeben, wenn du dir die Abbildung anschaust. Man kann es nach Konstruktion direkt hinschreiben. Die Injektivität folgt aus der Tatsache, dass die Division mit Rest eindeutig ist. Vielleicht schreibst du alles mal sauber auf – oder versuchst es – und dann schauen wir weiter. 😊

Mitglied

Maja1111

Sei $X = \mathbb{N}$ und $Y = \mathbb{N} \times\{ 1,2,...,n \}$ . Man bilde $0 \to (0,1)$ , $1 \to (0,2)$ , $2 \to (0,3)$ , ……, $n \to (0,n+1)$ , $n+1 \to (0,n+2)$ ab.
injektiv zz.: $f(x) = f(y) \Rightarrow x = y$
surjektiv zz.: für alle $(y_1, y_2) \in \mathbb{N} \times\{ 1,2,...,n \}$ gibt es ein $x \in \mathbb{N}$ mit $f(x) = (y_1, y_2)$ . Hier müsste $x = y_2$ sein.
Explizit angegeben lautet die Funktion: Jedes $m \in \mathbb{N}$ lässt sich (Division mit Rest) in der Form $m = k*n+r$ schreiben, mit $k \in \mathbb{N}$ und $r \in \mathbb{N}$ , $0 \leq r < n$ . Wir bilden dann $m\mapsto(k,r) \in\mathbb{N} \times \{ 1,2,...,n \}$ . erfüllt sind, ist die Abbildung bijektiv.

Autor

Stefan Hartmann

Zunächst musst du das Zeichen für das kartesische Produkt als „backslash times“ angeben. Dann solltest du dir noch einmal klar machen, was $\mathbb{N} \times \{1,2,\ldots,n\}$ bedeutet. Es ist die Menge aller Paare $(x,y)$ , wobei das $x$ eine beliebige natürliche Zahl ist und $y$ eine natürliche Zahl zwischen $1$ und $n$ ist. Daran siehst du schon, dass deine Abbildung nicht richtig sein kann, denn du bildest $n$ auf $(0,n+1)$ ab und das ist in der Menge $\mathbb{N} \times \{1,2,\ldots,n\}$ ja gar nicht enthalten. Weiterhin kann die Abbildung ja niemals surjektiv sein, wenn die ersten Komponente immer gleich $0$ ist. Denk dran: Du musst alle Elemente aus $\mathbb{N} \times \{1,2,\ldots,n\}$ treffen! Im Grunde habe ich dir die Abbildung schon fast verraten. Du musst ein $m\in \mathbb{N}$ nehmen und dieses auf ein Element aus $\mathbb{N} \times \{1,2,\ldots,n\}$ abbilden. Dazu teilst du $m$ durch $n$ mit Rest: $m=k\cdot n+ r$ . Ist dir klar, was das genau bedeutet, dieses Teilen mit Rest? Und weißt du auch, dass diese Darstellung eindeutig ist? Wie kann man daraus denn nun die gewünschte Abbildung basteln? Und von der kannst du dann zeigen, dass sie bijektiv ist. Versuche es bitte noch einmal. 😊

Mitglied

Maja1111

Sei $X = \mathbb{N}$ und $Y = \mathbb{N} * \{ 1,2,...,n \}$ . Man bilde $0 \to (0,1)$ , $1 \to (1,2)$ , $2 \to (2,3)$ , …….., $n-1 \to (n-1,n)$ .
injektiv zz.: $f(x) = f(y) \Rightarrow x = y$
surjektiv zz.: für alle $(y1, y2) \in \mathbb{N} * \{ 1,2,...,n \}$ gibt es ein $x \in \mathbb{N}$ mit $f(x) = (y1, y2)$ . Hier müsste $x = y1$ sein.
Explizit angegeben lautet die Funktion: Jedes $m \in \mathbb{N}$ lässt sich (Division mit Rest) in der Form $m = k*n+r$ schreiben, mit $k \in \mathbb{N}$ und $r \in \mathbb{N}$ , $0 kleiner gleich r \textless n$ . Dabei wird auf … aus $\mathbb{N} * \{ 1,2,...,n \}$ dann $m$ abgebildet. (was es jetzt mit Teilen mit Rest auf sich hat ist mir klar, und auch, dass diese eindeutig ist, aber dennoch weiß ich nicht, wie man daraus eine Abbildung basteln soll)
da injektiv und surjektiv erfüllt sind, ist die Abbildung bijektiv.

Autor

Stefan Hartmann

Liebe Maja, danke. Die Abbildung kann so immer noch nicht richtig sein. Warum? Aus mehreren Gründen: Erst einmal ist nicht klar, wohin die Elemente , abgebildet werden sollten. Setzt man deine Reihe logisch fort, müsste beispielsweise auf abgebildet werden, und das liegt gar nicht in . Außerdem kann die Abbildung nicht surjektiv sein. Im Bild deiner Abbildung liegen ja nur Punkte, deren zweite Komponente um den Wert 1 größer ist als die erste Komponente. Es gibt aber in viel mehr Punkte (beispielsweise die, bei der die zweite Komponente sogar kleiner ist als die erste Komponente). Wie die Abbildung aussehen muss, ist irgendwie klar. Man geht die Punkte aus systematisch durch: usw. Im Grunde ist die Aufgabe damit gelöst, denn wir haben die Menge abgezählt und damit eine bijektive Abbildung zu angegeben. Ich wollte aber, dass du auch eine explizite Abbildungsvorschrift hinschreibst, um den Beweis von Injektiviät und Surjektivität zu üben und allgemein ein paar Techniken. Wie macht man das nun? Wir müssen bei gegebenem , , jedem ein Element zuordnen. Dazu verwenden wir die Division mit Rest: Für alle gibt es (Division mit Rest) eindeutig bestimmte natürliche Zahlen und mit , wobei . Nun definieren wir: . Zunächst ist klar,… Read more »

Mitglied

Maja1111

Also die Abbildung selbst kann ich nun nachvollziehen.
Was mir weitaus weniger klar ist, ist wie man auf $(q, r) \in \mathbbN * \{1,...,n\}$ .
Ist die Funktion von $f(m)$ einfach so gegeben, bzw. Wie würde man darauf kommen und auch auf die Formel der Division mit Rest allgemein?
Außerdem verstehe ich nicht, warum zuerst $(q, r+1)$ zu $(q', r'+1)$ verschieden ist, aber dann im Folgeschritt gleichgesetzt werden darf.
Alles Übrige konnte ich soweit nachvollziehen ☺️

Autor

Stefan Hartmann

Nun, die Funktion ist nicht gegeben, man muss sie sich schon überlegen. 😉 Aber wie kommt man darauf? Zunächst muss man sich überlegen, dass man ja einfach nur eine Abzählung von finden muss, und da wählte man die natürlichste: , , … , , , , … , , , , … , , … So, und nun überlegt man sich, wo so eine Abzählung vorkommt, dass die erste Komponente irgendwas sein kann, beliebig groß, und die zweite Komponente immer zwischen und wandert. Und da fällt einem die Division mit Rest ein. Allerdings fängt die bei an. Also muss man noch „+1“ rechnen. Dann überlegt man sich, wie dann die Zahl sein muss, durch die ich teile. Weil ich ja in der zweiten Komponente bis gehe, aber ja immer 1 addieren muss (damit die 0 auf die 1 geht, wie bereits gesagt), muss ich durch teilen, denn bei der Division durch bleiben die Reste , , … , . Wenn ich dann „+1“ rechne, komme ich auf die gewünschten , , … , . Zu deiner zweiten Frage: Niemand sagt, dass und unterschiedlich sind. Du musst dir noch einmal ganz genau klar machen, was injektiv heißt. Die Definition ist: Für… Read more »

Webmaster

Leona

Für mich ist noch fragwürdig wie die Funktion fortgesetzt wird.

Mitglied

Maja1111

iv)
Die Abbildung von $\mathbb{N}$ $->$ $\mathbb{Q}$ lautet: $1->0$ , $2->1$ , $3->(-1)$ , $4->1/2$ , $5->-1/2$ , $6->2$ , $7->(-2)$ , $8->3$ ,……. .
Wir haben nun die Menge $Y$ abgezählt und damit eine bijektive Abbildung zu $X$ angegeben.

Webmaster

Leona

Liebe Maja,
ich glaube, dass du die Abbildung etwas länger auschreiben müsstest, damit wirklich klar wäre wie es weitergeht. Ich gebe gerne zu, dass es sehr schwierig ist hier eine konkrete Abbildung hinzuschreiben.
Hast du dir ein Bild mit den Elementen von $\mathbb{Q}$ gemalt und die Abzählung eingezeichnet?
Ich würde mir tatsächlich noch ein paar Sätze Begründung wünschen, dass diese Abbildung surjektiv ist. Ich bin tatsächlich nicht überzeugt, dass diese Abbildung injektiv ist. Das fällt dir aber bestimmt auf, wenn du etwas mehr zu der Abbildung aufschreibst.

Tatsächlich, wäre es vermutlich gut, wenn du dir die Aufgabenstellung nochmal anguckst. Es ist nicht immer notwendig etwas zu konstruieren, um dessen Existenz zu beweisen. Vielleicht findest du (mit Hilfe der Abbildung, die du gegeben hast oder aus den vorangegangenen Aufgaben) stichhaltige Gründe, warum es eine Bijektion geben muss (dieman aber vielleicht nicht konkret angeben kann oder will).
Liebe Grüße
Leona

Webmaster

Leona

(ii) Wir definieren $f:\mathbb{N}\to\mathbb{N}\times \{1,\ldots,n\}$ durch
$f(k)=(\lfloor \frac {k}{n}\rfloor, (k\text{ mod } n)+1)$ .
Für $x\in\mathbb{R}_{\geq 0}$ bezeichnen wir mit $\lfloor x\rfloor$ den ganzzahligen Anteil von $x$ , d.h. $\lfloor x\rfloor\in\mathbb{N}$ mit $0\leq x-\lfloor x\rfloor< 1$ .

Diese Funktion $f$ ist bijektiv. Wir beginnen mit surjektiv.
Sei $(m,l)\in \mathbb{N}\times\{1,\ldots,n\}$ beliebig. Wir müssen nun ein $j\in\mathbb{N}$ finden, sodass $f(j)=(m,l)$ gilt. Sei $j=m\cdot n+(l-1)$ . Nachrechnen ergibt, dass dann $f(j)=(m,l)$ gilt. Dies zeigt Surjektivität.

Um Injektivität zu zeigen, haben wir jetzt die Möglichkeit $f^{-1}:\mathbb{N}\times \{1,\ldots,n\}\to\mathbb{N}$ durch $f^{-1}((m,l))=m\cdot n+ (l-1)$ zu definieren. Da $f^{-1}(f(n))=n$ für alle $n\in\mathbb{N}$ , d.h., $f\circ f^{-1}=\text{id}$ . Da die Identität insbesondere injektiv ist, muss also schon $f$ injektiv gewesen sein nach Lemma von Iris.

21 Hinterlasse einen Kommentar

21

Hinterlasse einen Kommentar