Existenz zweier bijektiver Abbildungen

10.05.2012, 14:08	Josef S	Auf diesen Beitrag antworten »
Existenz zweier bijektiver Abbildungen Derzeit beschäftige ich mich mit Abbildungen und kann schon einige Beweise bezüglich der Injektivität und Surjektivität tadellos ausführen. Nun plagen mich aber die zwei letzten Aufgaben eines Kapitels zu diesem Thema: Man beweise oder widerlege, ... Problem 1: ...dass es eine bijektive Abbildung $\begin{eqnarray} f: \mathbb{R}\leftrightarrow\mathbb{R}\setminus\{0\} \end{eqnarray}$ gibt. Problem 2 (angeblich besonders schwierig): ...dass es eine bijektive Abbildung $\begin{eqnarray} f:\mathbb{N}\leftrightarrow\mathbb{N}\times\mathbb{N} \end{eqnarray}$ gibt. Gedanken zu 1: Sicherlich gibt es eine solche Abbildung, da ich z.B. jeder reellen Zahl eine Zahl aus $\begin{eqnarray} \mathbb{R}\setminus{0} \end{eqnarray}$ zuordnen kann, der ich noch kein Urbild unter $\begin{eqnarray} f \end{eqnarray}$ zugewiesen habe. Da beide Mengen unendlich sind, finde ich stets eine solche Zahl. Schwierig wird es nur mit der Bijektivität: wie kann ich kurz und knapp zeigen, dass jedem Wert aus $\begin{eqnarray} \mathbb{R}\setminus{0} \end{eqnarray}$ genau ein Urbild aus $\begin{eqnarray} \mathbb{R} \end{eqnarray}$ zugeordnet ist? Vielleicht habe ich mich ja doch mit der Existenz geirrt... Gedanken zu 2: Die Elemente aus $\begin{eqnarray} \mathbb{N}\times\mathbb{N} \end{eqnarray}$ kann ich nach folgendem Muster abzählen: $\begin{eqnarray} (1,1); (1,2); (2,1); (2,2); (1,3); (3,1); (2,3); (3,2); (3,3); (1,4); \dots \end{eqnarray}$ Dadurch kann ich jedem Paar eine eindeutige natürliche Zahl zuordnen. Mein Problem liegt nun in der mathematischen Formulierung. Die Ansätze habe ich im Prinzip schon geliefert. Daher wäre ich über Lösungen oder alternative Ansätze sehr dankbar. Gruß Josef
10.05.2012, 18:39	Mystic	Auf diesen Beitrag antworten »
RE: Existenz zweier bijektiver Abbildungen Deine Gedanken zu 2 stimmen im Prinzip, nur ist diese Idee so elendiglich "abgedroschen" und man kann auch nicht leicht eine Formel dazu finden, sodass ich persönlich eine andere vorziehe: Sei $\begin{eqnarray} 2^s \end{eqnarray}$ die größte Potenz von 2, durch welche n teilbar ist und $\begin{eqnarray} t=n/2^s \end{eqnarray}$ der "ungerade Anteil" von n, so kann man auch die Abbildung $\begin{eqnarray} n \mapsto (s+1,(t+1)/2) \end{eqnarray}$ betrachten... Details überlass ich dir...
10.05.2012, 20:14	Louis1991	Auf diesen Beitrag antworten »
RE: Existenz zweier bijektiver Abbildungen Hey Josef, Ich möchte dir noch ein oder zwei kleinere Tipps geben (insbesondere, da Mystic nicht auf das Problem 1 eingegangen ist): Um die bloße Existenz einer bijektiven Abbildung zwischen zwei Mengen X und Y zu zeigen, reicht es schon, zu zeigen, dass es sowohl eine injektive als auch eine (unter Umständen ganz anders aussehende) surjektive Abbildung von X nach Y gibt. Ich denke, das wurde in deinem Buch auch erwähnt? Falls nicht, versuch es dir als Übungsaufgabe doch mal selbst zu überlegen (ich weiß gerade nicht, wie schwer der Beweis mit deinem Vorwissen ist - wenn man ein wenig darüber Bescheid weiß, wie die Mächtigkeit von Mengen mit der Existenz von injektiven/surjektiven/bijektiven Abb. zwischen diesen Mengen zusammenhängt, ist das aber eigentlich fast eine Trivialität) Bei Problem 1 bietet sich das meiner Meinung nach an: Eine injektive Abbildung von R\{0} nach R zu finden, sollte ziemlich einfach sein Bei der surjektiven Abbildung muss man vielleicht etwas länger überlegen, aber da gibt es tatsächlich auch eine elementare Abbildung, die man in der Schule kennenlernt, welche funktionieren sollte. Zu Problem 2: Da hat dir Mystic schon einen Tipp gegeben. Deine Idee mit der Abzählung ist natürlich richtig, und die kann man auch in eine Formelschreibweise packen, die in der Tat nicht einmal soooo kompliziert ist (wir hatten die gleiche Aufgabe als Übung im 1. Semester). Ich weiß nicht, ob du noch Schüler oder schon Student bist, aber du brauchst dafür jedenfalls (bzw. es ist sehr hilfreich) die Sigmasummenschreibweise - und wenn du die Formel dann erstmal hast, musst du immer noch formal Injektivität und Surjektivität nachweisen, was u.U. ziemlich länglich wird. Also: möglich ist deine Idee sicher, aber vielleicht fährst du mit der Methode von Mystic ja besser. Auf jeden Fall scheint mir die nicht so altbacken und ausgelutscht zu sein! lg kai
10.05.2012, 20:51	Josef S	Auf diesen Beitrag antworten »
RE: Existenz zweier bijektiver Abbildungen @Mystic: Ja, da hast du recht. Eine halbwegs handliche Vorschrift für meine Abzählungsweise gibt es wohl kaum. Hingegen hat deine wunderbare Idee mich sofort zum Beweis geführt. Ich weiß zwar nicht wie man auf eine solche Idee kommen kann, ohne Zahlentheorie näher behandelt zu haben, aber egal... wenigstens eine Lösung, mit der ich vielleicht später glänzen kann (wenn ich dann endlich diesen Winter anfange zu studieren). ----- Für Interessierte: Man zeige, dass eine bijektive Abbildung $\begin{eqnarray} f:\mathbb{N}\rightarrow\mathbb{N}^{2} \end{eqnarray}$ existiert. Beweis: Sei $\begin{eqnarray} \displaystyle v\rightarrow\mathbb{N}_{0}: n\mapsto\max_{s\in\mathbb{N}_{0}}\{2^{s}\mid n\} \end{eqnarray}$ die Exponentenbewertung über 2 von n, also die größte natürliche Zahl $\begin{eqnarray} s \end{eqnarray}$ (einschließlich Null), für die $\begin{eqnarray} n \end{eqnarray}$ durch $\begin{eqnarray} 2^{s} \end{eqnarray}$ teilbar ist, dann existiert eine solche Abbildung mit $\begin{eqnarray} \displaystyle f: n\mapsto (v(n)+1, (n/2^{v(n)} + 1) / 2) \end{eqnarray}$ , wobei $\begin{eqnarray} v(n)+1\in\mathbb{N} \end{eqnarray}$ gilt, weil $\begin{eqnarray} v(n)\in\mathbb{N}_{0} \end{eqnarray}$ , und ebenfalls $\begin{eqnarray} (n/2^{v(n)} + 1) / 2\in\mathbb{N} \end{eqnarray}$ , da $\begin{eqnarray} n/2^{v(n)} \end{eqnarray}$ das ungerade Produkt aller ungeraden Primfaktoren von $\begin{eqnarray} n \end{eqnarray}$ beschreibt, wodurch $\begin{eqnarray} n/2^{v(n)}+1 \end{eqnarray}$ gerade ist und damit auch durch zwei teilbar. Um die Bijektivität dieser Abbildung zu beweisen, zeige man, dass sie surjektiv und injektiv ist: Beweis der Surjektivität: Surjektiv bedeutet: $\begin{eqnarray} \forall (a,b)\in\mathbb{N}^{2}\exists n\in\mathbb{N}:\quad f(n)=(a,b) \end{eqnarray}$ $\begin{eqnarray} (a,b)=(v(n)+1,(n/2^{v(n)}+1)/2) \end{eqnarray}$ Daraus folgt: $\begin{eqnarray} a=v(n)+1 \end{eqnarray}$ $\begin{eqnarray} b=(n/2^{v(n)} + 1)/2 \end{eqnarray}$ Nach wenigen Umformungen erhält man als mögliches $\begin{eqnarray} n \end{eqnarray}$ : $\begin{eqnarray} n=(2b-1)\cdot 2^{a-1} \end{eqnarray}$ Also gilt: $\begin{eqnarray} \forall (a,b)\in\mathbb{N}^{2}:\quad f((2b-1)\cdot 2^{a-1})=(a,b) \end{eqnarray}$ , was die Surjektivität beweist. Beweis der Injektivität Injektiv bedeutet: $\begin{eqnarray} \forall x,y\in\mathbb{N}:\quad f(x)=f(y)\Rightarrow x=y \end{eqnarray}$ Aus $\begin{eqnarray} (v(x)+1,(x/2^{v(x)}+1)/2)=(v(y)+1,(y/2^{v(y)}+1)/2) \end{eqnarray}$ folgt: $\begin{eqnarray} v(x)+1=v(y)+1\Leftrightarrow v(x)=v(y) \end{eqnarray}$ Dann erhält man bei Gleichsetzung der zweiten Komponente des geordneten Paares: $\begin{eqnarray} (x/2^{v(x)}+1)/2=(y/2^{v(y)}+1)/2 \end{eqnarray}$ Nach Umformen ergibt sich: $\begin{eqnarray} x/2^{v(x)}=y/2^{v(y)} \end{eqnarray}$ , was äquivalent ist mit $\begin{eqnarray} x/2^{v(x)}=y/2^{v(x)} \end{eqnarray}$ , wodurch $\begin{eqnarray} x=y \end{eqnarray}$ gilt und die Injektivität bewiesen ist. Ergo: Die Funktion ist bijektiv. Nochmal Danke an dich, Mystic. ----- Und nun zu dir Louis1991: Zu Aufgabe 1: Danke für all die Tipps. Das mit der Existenz einer Injektiven und Surjektiven Abbildung stand leider nicht drin, lediglich, dass für eine bijektive Abbildung eine eindeutige Umkehrabbildung existiert. Ich werde mir das auf jeden Fall genauer durch den Kopf gehen lassen. Zu Aufgabe 2: Wie du siehst, hat sich das erledigt. Und ja, mit der Sigmasummenschreibweise habe ich mich schon mal vertraut gemacht. Zu meinem Vorwissen: Wie bereits oben beiläufig angegeben: Ich bin noch Schüler, ferner Abiturient, und eigne mir gerade das Vorwissen an. Bisher habe ich mich viel mit elementare Zahlentheorie und axiomatische Mengenlehre beschäftigt, wie ich mich jetzt auch mit Abbildungen und später mit Gruppentheorie befassen werde. Ich bin also einer von den Menschen, denen Mathematik Spaß macht. Nochmal danke an Euch beide. Werde mich jetzt an die 1 ran machen. Gruß Josef
10.05.2012, 21:06	Josef S	Auf diesen Beitrag antworten »
Hinzufügung: Umfasst $\begin{eqnarray} \mathbb{N} \end{eqnarray}$ nicht nur positive ganze Zahlen, sondern, wie manchmal üblich, auch nicht-negative ganze Zahlen (d.h. die Null ist dabei), dann würde auch $\begin{eqnarray} (v(n), (n/2^{v(n)}+1)/2) \end{eqnarray}$ funktionieren.
10.05.2012, 21:09	Louis1991	Auf diesen Beitrag antworten »
Da du die 2 ja jetzt hast (ich werde mir den Beweis nachher mal durchlesen, bin schon gespannt!) kann ich dir ja die Formel (jedenfalls die, die meine Abgabepartnerin und ich letztes Semester gefunden hatten) für die Abzählung sagen: $\begin{eqnarray} f: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}, f((n_1,n_2))= \sum\limits_{i=0}^{n_1+n_2}i +n_1 \end{eqnarray}$ Falls dich der Nachweis für die Bijektivität interessiert, kannst du mir gerne eine PN schicken. Ansonsten wie immer: erstmal selbst probieren.
Anzeige

10.05.2012, 21:20	Josef S	Auf diesen Beitrag antworten »
@Louis1991: Eine interessante Funktion. Werde mich mal darin versuchen, ihre Bijektivität zu zeigen. Ich melde mich, wenn ich Hilfe brauche
11.05.2012, 09:47	Mystic	Auf diesen Beitrag antworten »
@Josef S Ich hätte jetzt nicht gedacht, dass die Begründung zu meinem Lösungsvorschlag zu Punkt 2 noch so umfangreich ausfällt, aber es stimmt natürlich alles... Was Punkt 1 betrifft, könnte man auch eine Abbildung $\begin{eqnarray} f: \mathbb R \to \mathbb R \setminus \{0\} \end{eqnarray}$ betrachten, welche alle irrationalen Zahlen als Fixpunkte hat und deren Einschränkung $\begin{eqnarray} f:\mathbb Q \to \mathbb Q \setminus \{0\} \end{eqnarray}$ eine Bijektion ist... Da $\begin{eqnarray} \mathbb Q \end{eqnarray}$ abzählbar ist, sollte das wesentlich einfacher sein... Zu Punkt 2 hätte ich noch einen Vorschlag anzubieten, der - so hoffe ich wenigstens - ebenfalls jeden Kenner hörbar mit der Zunge schnalzen lässt wie bei der Verkostung eines besonders edlen Tropfen Weins... Man benützt dabei, dass sich jede positive ganze Zahl in eindeutiger Weise darstellen lässt als Produkt n=u²v, wobei u,v ebenfalls positive ganze Zahlen sind und v überdies quadratfrei ist...Die Abbildung $\begin{eqnarray} n \mapsto (u,v) \end{eqnarray}$ von $\begin{eqnarray} \mathbb N \to \mathbb N \times \mathbb N \end{eqnarray}$ (schweren Herzens und ganz ausnahmsweise mache ich hier das Zugeständnis, dass 0 nicht in $\begin{eqnarray} \mathbb N \end{eqnarray}$ liegt! ) ist dann schon injektiv, aber noch nicht surjektiv... Man braucht also noch eine Modifikation, um daraus eine Bijektion zu machen, die verrate ich aber noch nicht, vielleicht hast du ja dazu eine andere Idee als ich selbst...

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »