Mächtigkeit von P(N) und N^N

05.04.2011, 21:23	magixD	Auf diesen Beitrag antworten »
Mächtigkeit von P(N) und N^N Hallo, Hab habe hier in Linearer Algebra ein Übungsbeispiel, bei dem ich Hilfe benötige. Das Beispiel lautet: " $\begin{eqnarray} \text{Ist }\mathcal{P}(\mathbb{N}) \sim \mathbb{N}^\mathbb{N} \text{?} \end{eqnarray}$ " Für eine endliche Menge A, wäre ja $\begin{eqnarray} \|\mathcal{P}(A)\| = 2^{\|A\|} \end{eqnarray}$ und $\begin{eqnarray} \|A^A\| = \|A\|^{\|A\|} \end{eqnarray}$ und somit für \|A\|>2 $\begin{eqnarray} \mathcal{P}(A) \prec A^A \end{eqnarray}$ . Intuitiv würde ich sagen, dass auch $\begin{eqnarray} \mathcal{P}(\mathbb{N}) \prec \mathbb{N}^\mathbb{N} \end{eqnarray}$ gilt, aber das muss ich natürlich auch zeigen . Ich weiß, das zwei Mengen A und B gleichmächtig sind, wenn es eine Bijektion zwischen A und B gibt, oder wenn es eine Injektion zwischen A und B und eine Injektion zwischen B und A gibt (Satz von Schröder-Bernstein). Des weiteren weiß ich, das für jede Menge A P(A) mächtiger als A ist. Diesen Satz haben wir gezeigt, in dem wir bewiesen haben, das es keine surjektive Funktion von P(A) auf A geben kann. Ich denke, dass ich im Prinzip hier auch so vorgehen muss, jedoch habe ich keine Idee wie ich das konkret zeigen kann. Wahrscheinlich liegt das auch daran, das ich mir die Menge $\begin{eqnarray} \mathbb{N}^\mathbb{N} \end{eqnarray}$ nicht gut vorstellen kann (Ich weiß natürlich, dass $\begin{eqnarray} \mathbb{N}^\mathbb{N} \end{eqnarray}$ die Menge aller Funktionen von $\begin{eqnarray} \mathbb{N} \end{eqnarray}$ nach $\begin{eqnarray} \mathbb{N} \end{eqnarray}$ ist). Vielleicht ist es auch möglich, dass man $\begin{eqnarray} \mathbb{R} \sim \mathbb{N}^\mathbb{N} \end{eqnarray}$ (oder so ähnlich) zeigt. Für Anregungen wäre ich dankbar! magixD
06.04.2011, 01:42	Merlinius	Auf diesen Beitrag antworten »
Hallo, also wenn Du weißt, dass $\begin{eqnarray} \mathbb N^{\mathbb N} \end{eqnarray}$ die Menge aller Funktionen von $\begin{eqnarray} \mathbb N \end{eqnarray}$ nach $\begin{eqnarray} \mathbb N \end{eqnarray}$ ist, dann ist das doch schonmal eine gute Vorstellung. Denn schließlich ist dies gleich der Menge der Folgen in $\begin{eqnarray} \mathbb N \end{eqnarray}$ . Man kann eigentlich recht gut eine Injektion von beiden Mengen ineinander definieren. Mit dem Verständnis, dass $\begin{eqnarray} \mathbb N^{\mathbb N} \end{eqnarray}$ die Menge aller natürlichen Folgen ist, lässt sich eine Injektion von $\begin{eqnarray} P(\mathbb N) \text{ nach } \mathbb N^{\mathbb N} \end{eqnarray}$ eigentlich sehr leicht definieren. Wie kann man ein Element aus der Potenzmenge als Folge identifizieren? Umgekehrt würde ich folgenden Ansatz vorschlagen: Mach Dir klar, wie man eine streng monotone Folge natürlicher Zahlen mit einem Element aus der Potenzmenge identifizieren kann (injektiv). Wenn Dir dann noch einfällt, wie man jede beliebige Folge aus natürlichen Zahlen bijektiv mit einer streng monotonen Folge identifizieren kann - d.h. wie man eine Folge eindeutig in eine streng monotone Folge überführen kann und auch eindeutig wieder zurück -, wäre auch die Rückrichtung gezeigt.
06.04.2011, 12:12	magixD	Auf diesen Beitrag antworten »
Hallo, Ah, der Gedanke mit den Folgen ist gut, so hab ich das noch garnicht betrachtet! Ich kann jetzt eine injektive Funktion finden, die ein Element von $\begin{eqnarray} \mathcal{P}(\mathbb{N}) \end{eqnarray}$ (z.B.: $\begin{eqnarray} {1,2,3,4,\ldots} \end{eqnarray}$ ) auf ein entsprechendes Element in $\begin{eqnarray} \mathbb{N}^\mathbb{N} \end{eqnarray}$ abbildet. Wie schreibe ich das formal korrekt auf? Die Elemente von $\begin{eqnarray} \mathbb{N}^\mathbb{N} \end{eqnarray}$ sind ja irgendwelche Funktionen. Kann man das so irgendwie schreiben: $\begin{eqnarray} f: \mathcal{P}(\mathbb{N}) \to \mathbb{N}^\mathbb{N}, {a_1, a_2, \ldots} \mapsto (a_1, a_2, \ldots) \end{eqnarray}$ Bei der Rückrichtung tu ich mir schwerer. In $\begin{eqnarray} \mathbb{N}^\mathbb{N} \end{eqnarray}$ müsste es ja auch Folgen wie (2, 1, 3, 4, 7, 5, 6, ...) geben, und für solche Elemente kann ich ja dann keine injektive Funktion in den P(N) finden. Oder stelle ich mir die Elemente im N^N noch nicht richtig vor? magixD
06.04.2011, 13:34	Merlinius	Auf diesen Beitrag antworten »
Genau. Für die eine Richtung kannst Du ein Element der Potenzmenge einfach der Größe nach sortieren und dies dann als Folge betrachten. Also für $\begin{eqnarray} X \in P(\mathbb N) \end{eqnarray}$ $\begin{eqnarray} a_0 = \text{ min } X, a_1 = \text{ min } X\setminus \{a_0\}, ..., a_{n+1} = \text{ min } X\setminus\{a_0, ..., a_n\} \end{eqnarray}$ Hier benutzt Du, dass jede Menge aus natürlichen Zahlen ein kleinstes Element enthält. Rückrichtung: Doch, auch für solche Folgen kannst Du eine Injektion finden. Also das mit der streng monotonen Folge ist aber klar, oder? Wenn $\begin{eqnarray} a_0 < a_1 < a_2 < ... \end{eqnarray}$ , dann kann ich der Folge eindeutig ein Element $\begin{eqnarray} \{a_0, a_1, ...\} \in P(\mathbb N) \end{eqnarray}$ zuordnen. Jetzt müssen wir nur noch einer beliebigen (nicht notwendig streng monotonen) Folge eindeutig eine streng monotone Folge zuordnen. Dies geht bei natürlichen Zahlen aber ganz gut: Der Einfachheit halber sei meine Folge nun positiv, d.h. alle Elemente ungleich 0. Dann kann ich doch einfach: $\begin{eqnarray} (a_0, a_1, a_2, ...) \mapsto (a_0, a_0+a_1, a_0+a_1+a_2, ...) \end{eqnarray}$ machen und habe eine streng monotone Folge. Warum ist diese Abbildung für positive Folgen injektiv? Selbst wenn ich nun eine Folge habe, die auch Nullen enthält, kann ich die Idee benutzen, denn eine solche Folge kann ich ja ganz einfach (injektiv, oder auch bijektiv) in eine positive Folge umwandeln. Wie?

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »