Gibt es ein n, für dass es eine Bijektion von N^n -> R gibt?

12.03.2014, 10:36

MartinL

Gibt es ein n, für dass es eine Bijektion von N^n -> R gibt?

Moin,

ich soll folgende Aussage Beweisen oder Widerlegen: "Für (mindestens) ein $\begin{eqnarray*} n \in \mathbb{N} \end{eqnarray*}$ existiert eine bijektive Funktion $\begin{eqnarray*} g_n:\mathbb{N}^n \rightarrow \mathbb{R} \end{eqnarray*}$

Ich vermute, dass diese Aussage falsch ist. Ich weiß, dass $\begin{eqnarray*} \mathbb{N} \end{eqnarray*}$ abzählbar viele Elemente und $\begin{eqnarray*} \mathbb{R} \end{eqnarray*}$ überabzählbar viele Elemente enthält. Ich habe folgenden Ansatz ausprobiert aber komme nicht zu einem Ergebnis.
Ich habe mir gedacht, dass $\begin{eqnarray*} \mathbb{N}^n \end{eqnarray*}$ entweder überabzählbar viele Elemente oder abzählbar viele Elemente enthält. Da ich davon ausgehe, dass die Menge abzählbar viele Elemente enthält, habe ich versucht eine bijektive Abbildung von $\begin{eqnarray*} \mathbb{N}^n \rightarrow \mathbb{N} \end{eqnarray*}$ zu finden. Wenn ich diese bijektive Abbildung finde, weiß ich, dass die Aussage widerlegt ist. Ich finde allerdings keine Bijektion.

Ich könnte es natürlich auch mittels der guten alten vollständigen Induktion versuchen. Ich weiß ja, dass die Aussage für n=1 falsch ist. Es wäre cool, wenn jemand mich auf den rechten Weg führen könnte smile

.

Gruß
Martin

12.03.2014, 11:49

bijektion

Auf diesen Beitrag antworten »

Hi!

Fällt dir denn eine Bijektion $\begin{eqnarray*} \mathbb{N}^2 \to \mathbb{N} \end{eqnarray*}$ ein? Damit kannst du alles weitere Konstruieren Augenzwinkern

12.03.2014, 17:44

MartinL

Auf diesen Beitrag antworten »

Mhh ja ich habe da so eine Idee. Die leitet sich ab von der Aufzählung der rationalen Zahlen. Ich schreibe die Elemente aus $\begin{eqnarray*} \mathbb{N} \times \mathbb{N} \end{eqnarray*}$ in eine Matrix mit n Zeilen und n Spalten (wobei n natürlich dann schlussendlich unendlich groß ist) in der Form:

$\begin{eqnarray*} \begin{pmatrix} (1,1) & (1,2) & (1,3) & ... & (1,n) \\ (2,1) & (2,2) & (2,3) & ... & (2,n) \\ (3,1) & (3,2) & (3,3) & ... & (3,n) \\ ... & ... & ... & ... & ... \\ (n,1) & (n,2) & (n,3) & ... & (n,n) \end{pmatrix} \end{eqnarray*}$

Die kann ich dann der Reihe nach aufschreiben, indem ich von (1,1) startend erst eins nach unten gehe zu (2,1), dann diagonal hoch zu (1,2), dann eins nach rechts, dann diagonal runter von (1,3) über (2,2) nach (3,1), dann wieder eins runter bis (4,1) und wieder diagonal hoch und so weiter und so fort. Dann habe ich schon mal gezeigt, dass $\begin{eqnarray*} |\mathbb{N}| = |\mathbb{N}^2| \end{eqnarray*}$ ist.

Wenn ich jetzt die eben gezählten Elemente aus $\begin{eqnarray*} \mathbb{N}^2 \end{eqnarray*}$ beim durchgehen direkt umbenenne in (1,1) = x1, (2,1) = x2, (1,2) = x3 .... dann kann ich ja wieder kombinieren wie oben und erhalte:

$\begin{eqnarray*} \begin{pmatrix} (x1,1) & (x1,2) & (x1,3) & ... & (x1,n) \\ (x2,1) & (x2,2) & (x2,3) & ... & (x2,n) \\ (x3,1) & (x3,2) & (x3,3) & ... & (x3,n) \\ ... & ... & ... & ... & ... \\ (xn,1) & (xn,2) & (xn,3) & ... & (xn,n) \end{pmatrix} \end{eqnarray*}$

Diese Elemente repräsentieren die Menge $\begin{eqnarray*} \mathbb{N}^3 \end{eqnarray*}$ und können wieder durchgezählt werden. Dabei kann ich ja direkt die Elemente umbenennen in b1, b2, b3, ...., bn und wieder neu kombinieren. So komm ich immer weiter bis $\begin{eqnarray*} \mathbb{N}^n \end{eqnarray*}$

Reicht das so? Oder hab ich irgendwelche komischen Fälle übersehen?

Gruß
Martin

12.03.2014, 22:47

bijektion

Auf diesen Beitrag antworten »

Gib es doch einfach explizit an: die Abbildung $\begin{eqnarray*} \phi_2: \mathbb{N}_0 \times \mathbb{N}_0 \to \mathbb{N}_0 \end{eqnarray*}$ mit $\begin{eqnarray*} \phi_2(n,m)=n+\frac{(n+m)\cdot (n+m+1)}{2} \end{eqnarray*}$ sollte darstellen, was du beschrieben hast.

Dann findest du aber auch eine Abbildung $\begin{eqnarray*} \phi_3:\mathbb{N}_0^3 \to \mathbb{N}_0 \end{eqnarray*}$ , und zwar $\begin{eqnarray*} \phi_3(n,m,l)=\phi_2(n,\phi_2(m,l)) \end{eqnarray*}$ . Somit folgt die Behauptung Induktiv.

Das ist vermutlich das von dir ausformulierte smile

13.03.2014, 08:26

MartinL

Auf diesen Beitrag antworten »

Ja der zweite Teil ist der von mir ausformulierte. Auf den ersten Teil wäre ich so nicht gekommen. Ich weiß auch noch nicht genau, wie ich die Injektivität zeigen soll. Bisher habe ich das nur für Funktionen mit einer Variablen gemacht. Irgendwie stecke ich da fest. Ich glaube zwar, dass man sich das logisch überlegen kann aber rein anhand der Definition

$\begin{eqnarray*} f(n,m) = f(a,b) \Rightarrow (n,m)=(a,b) \end{eqnarray*}$

komme ich nicht klar.

Ich würde auf die Injektivität aktuell folgendermaßen schließen:

1. $\begin{eqnarray*} (n+m) >( a+b) \Rightarrow f(n,m) > f(a,b) \end{eqnarray*}$
$\begin{eqnarray*} \Rightarrow \ \ \ f(n,m) = f(a,b) \Rightarrow (n+m)=(a+b) \end{eqnarray*}$

2. Wenn die jeweiligen Summen der Variablen in zwei Tupeln identisch sind, ist der rechte Summand der Funktion (der Bruch) auf jeden Fall für die zwei Tupel identisch.
Wenn in diesem Fall f(n,m) = f(a,b) gilt, müssen auf jeden Fall die ersten beiden Variablen identisch sein, da sich ansonsten der ausschlaggebende linke Summand unterscheiden würde.
Wenn aber n = a gilt und (n+m) = (a+b) gilt, dann muss auch m=b gelten und somit die Injektivität.

Du siehst, mir fällt es leichter, Dinge einfach auszuformulieren. Vielleicht muss ich daran noch arbeiten Augenzwinkern

Gruß
Martin

13.03.2014, 08:39

bijektion

Auf diesen Beitrag antworten »

Die Injektivität ist leicht zu zeigen, wenn du dir die Tupel in ein Koordinatensystem aufzeichnest, und sie jeweils mit dem zugehörigen Wert bezeichnest, ähnlich wie in deiner Matrix geschehen.
Dann kannst du in jeder Spalte ein System erkennen; daraus ist auch die Surjektivität ersichtlich.

13.03.2014, 09:48

MartinL

Auf diesen Beitrag antworten »

Gut, die Surjektivität ist ein nettes Bonbon, was ich für meine Aufgabe aber nicht brauche. Hauptsache die Mengen bleiben immer maximal abzählbar unendlich.

Dann bedanke ich mich und betrachte diese Aufgabe hiermit als gelöst smile

13.03.2014, 10:08

bijektion

Auf diesen Beitrag antworten »

Eigentlich brauchst du die schon, du musst ja zeigen, dass die Abbildung bijektiv ist.

Ok, kein Problem Freude

13.03.2014, 10:16

MartinL

Auf diesen Beitrag antworten »

Ne Bijektivität brauche ich nicht oder?

Wenn ich die jeweilige Menge durchnummerieren kann, ist die Mächtigkeit ohne Surjektivität ja kleiner oder gleich der Mächtigkeit der natürlichen Zahlen. Insgesamt habe ich damit ja gezeigt, dass die Menge NxNxNxNx....xN sich auf jeden Fall injektiv abbilden lässt in die natürlichen Zahlen. Damit ist die Mächtigkeit kleiner oder gleich der der natürlichen Zahlen und somit auf jeden Fall kleiner als die der reellen Zahlen. Die Gleichmächtigkeit von N und N^n brauche ich ja in diesem Fall nicht unbedingt. Ich wollte ja nur zeigen, dass es keine Bijektion von N^n nach R gibt. Ich habe jetzt gezeigt, dass es keine surjektive Abbildung von N^n nach R geben kann. Damit gibt es sicher auch keine bijektive.

Gruß
Martin

13.03.2014, 10:28

bijektion

Auf diesen Beitrag antworten »

Ohne Surjektivität dürfte nur

Zitat:

Dann findest du aber auch eine Abbildung $\begin{eqnarray*} \phi_3:\mathbb{N}_0^3 \to \mathbb{N}_0 \end{eqnarray*}$ , und zwar $\begin{eqnarray*} \phi_3(n,m,l)=\phi_2(n,\phi_2(m,l)) \end{eqnarray*}$ . Somit folgt die Behauptung Induktiv.

nicht funktionieren.

EDIT: Es geht natürlich, weil die Abb. Surjektiv ist. Aber ich würde es der Vollständigkeithalber zeigen, das kommt ja schon fast mit der Injektivität.

13.03.2014, 10:37

MartinL

Auf diesen Beitrag antworten »

Stimmt, da müsste man sich über eventuelle Lücken in der Definition Gedanken machen. Das habe ich in meinem konstruierenden Ansatz dadurch umgangen, dass ich die entstehenden Elemente einfach durchnummeriert habe. Das wäre also immer surjektiv, da per Definition keine Lücke entstehen kann. Es wird ja beim Nummerieren bzw. Umbenennen der Ergebnisse immer die nächste freie natürliche Zahl verwendet.

Du hast aber recht, die Surjektivität sieht man in der Tabelle relativ schnell.

13.03.2014, 10:48

bijektion

Auf diesen Beitrag antworten »

Dann sollte das so reichen smile

Neue Frage »

Antworten »

Gibt es ein n, für dass es eine Bijektion von N^n -> R gibt?

Verwandte Themen