Gleichmächigkeit von Mengen zeigen

27.10.2007, 12:22

FabiB

Auf diesen Beitrag antworten »

Gleichmächigkeit von Mengen zeigen

Ich möchte die Gleichmächtigkeit der Menge
$\begin{eqnarray*} R=\{ \sum_{i=0}^\infty~a_ix^i|a_i\in\{0,1\} \forall i \in \mathbb N_o \} \end{eqnarray*}$

und der Potenzmenge $\begin{eqnarray*} P(\mathbb N_o) \end{eqnarray*}$ zeigen.

Dazu möchte ich zeigen, dass es eine Bijektion $\begin{eqnarray*} R \to P(\mathbb N_o) \end{eqnarray*}$ gibt.

Also, als erstes möchte ich zeigen, dass eine injektive Abbildung existiert und danach, dass eine surjektive Abbildung existiert.

Ich habe zwar eine Idee, weiss aber nicht wie ich sie richtig aufschreiben kann oder ob sie richtig ist.

Injektion:

$\begin{eqnarray*} R \to P(\mathbb N_o) \end{eqnarray*}$
$\begin{eqnarray*} \{x_o,x_1,...x_n\} \to \sum_{i=0}^n~a_ix^i ,a_i =1 \end{eqnarray*}$
ich glaube, dass ist nicht richtig aufgeschrieben.
ich meine jedenfalls, daß jedem Element der Potenzmenge ein Element in R zugeordnet wird, so dass alle x_i die in dem Element der Potenzmenge auftreten, den Koeffizienten 1 bekommen und alle anderen 0.

Dann müsste ich noch eine Surjektion aufzeigen.

Außerdem müsste ich wohl beweisen, dass diese Abbildungen injektiv bzw. surjektiv sind (falls sie es sind).

27.10.2007, 12:38

therisen

Auf diesen Beitrag antworten »

Hallo,

deine Abbildung ist leider nicht injektiv. Zum Beispiel werden die Mengen $\begin{eqnarray*} \{1\} \end{eqnarray*}$ und $\begin{eqnarray*} \{2\} \end{eqnarray*}$ beide auf den Wert 1 abgebildet.
Aber dein Ansatz sollte ausbaubar sein ( $\begin{eqnarray*} \mathbb N \end{eqnarray*}$ ist abzählbar).

Gruß, therisen

27.10.2007, 12:43

FabiB

Auf diesen Beitrag antworten »

Ja, also das Ziel soll auch sein zu zeigen, dass R überabzählbar ist.

Habe ich denn wenigstens die Abbildung richtig aufgeschrieben? auch wenn sie nicht injektiv ist.

darf ich dem x in R eigentlich einen festen Wert zuweisen zur Bildung einer Injektion?

Ich hätte auch noch die Idee, das der Koeffizient, dann 1 ist wenn die Potenz von x einem Element der Potenzmenge entspricht.

Also z.B.

$\begin{eqnarray*} \{1\} \to 1*x^1 + 0*x^2 + 0*x^3...=x^1 \end{eqnarray*}$
$\begin{eqnarray*} \{2\} \to 1*x^1 + 0*x^2 + 0*x^3..=x^2 \end{eqnarray*}$
$\begin{eqnarray*} \{1,3,4\} \to 1*x^1 + 0*x^2 + 1 * x^3 + 1*x^4+ 0*x^5...=x^1+x^3+x^4 \end{eqnarray*}$

ich würde das etwa so aufschreiben,

$\begin{eqnarray*} \{a_1,a_2,...,a_n\} \to \sum_{i=0}^\infty~ a*x^i , a =1\ falls\ i \in \{a_1,a_2,...,a_n\}, sonst\ a=0 \end{eqnarray*}$

27.10.2007, 13:49

therisen

Auf diesen Beitrag antworten »

Um ehrlich zu sein würde ich $\begin{eqnarray*} R \end{eqnarray*}$ mit $\begin{eqnarray*} \{0,1\}^{\mathbb N_0} \end{eqnarray*}$ identifizieren (das sind Folgen mit Wertebereich $\begin{eqnarray*} \{0,1\} \end{eqnarray*}$ ). Dann ist es eigentlich klar, wie man eine Bijektion herstellen kann. Die konstante Folge $\begin{eqnarray*} x_n=1 \end{eqnarray*}$ würde dann gerade $\begin{eqnarray*} \mathbb N_0 \end{eqnarray*}$ repräsentieren.

27.10.2007, 14:35

FabiB

Auf diesen Beitrag antworten »

wäre meine idee denn falsch?

27.10.2007, 14:51

therisen

Auf diesen Beitrag antworten »

Zitat:

Original von FabiB
Habe ich denn wenigstens die Abbildung richtig aufgeschrieben? auch wenn sie nicht injektiv ist.

Nein, deine Abbildungsvorschrift gilt nur für endliche Teilmengen. Außerdem hast du Definitions- und Wertebereich vertauscht.

Zitat:

Original von FabiB
darf ich dem x in R eigentlich einen festen Wert zuweisen zur Bildung einer Injektion?

Kommt drauf an, was du darunter verstehst, aber x ist einfach nur die Unbestimmte.

Zitat:

Original von FabiB
$\begin{eqnarray*} \{1\} \to 1*x^1 + 0*x^2 + 0*x^3...=x^1 \end{eqnarray*}$
$\begin{eqnarray*} \{2\} \to 1*x^1 + 0*x^2 + 0*x^3..=x^2 \end{eqnarray*}$
$\begin{eqnarray*} \{1,3,4\} \to 1*x^1 + 0*x^2 + 1 * x^3 + 1*x^4+ 0*x^5...=x^1+x^3+x^4 \end{eqnarray*}$

Die zweite Zeile stimmt nicht.

Zitat:

Original von FabiB
$\begin{eqnarray*} \{a_1,a_2,...,a_n\} \to \sum_{i=0}^\infty~ a*x^i , a =1\ falls\ i \in \{a_1,a_2,...,a_n\}, sonst\ a=0 \end{eqnarray*}$

Das gilt nur für endliche Mengen.

Zitat:

Original von FabiB
wäre meine idee denn falsch?

Im Prinzip ist das die gleiche Idee wie ich hatte. Mir gefällt nur die Beschreibung von R nicht (->Konvergenz?). Man arbeitet also mit formalen Potenzreihen.

Anzeige

27.10.2007, 15:49

FabiB

Auf diesen Beitrag antworten »

$\begin{eqnarray*} \{1\} \to 1*x^1 + 0*x^2 + 0*x^3...=x^1 \end{eqnarray*}$
$\begin{eqnarray*} \{2\} \to 0*x^1 + 1*x^2 + 0*x^3..=x^2 \end{eqnarray*}$
$\begin{eqnarray*} \{1,3,4\} \to 1*x^1 + 0*x^2 + 1 * x^3 + 1*x^4+ 0*x^5...=x^1+x^3+x^4 \end{eqnarray*}$

$\begin{eqnarray*} \{a_1,a_2,...\} \to \sum_{i=0}^\infty~ a*x^i , a =1\ falls\ i \in \{a_1,a_2,...\}, sonst\ a=0 \end{eqnarray*}$

so besser?

27.10.2007, 15:54

therisen

Auf diesen Beitrag antworten »

Ja, so kann man es im Prinzip lassen.

27.10.2007, 15:57

FabiB

Auf diesen Beitrag antworten »

vielen dank. also die injektion habe ich damit gezeigt, ja? kann ich das im prinzip so umstellen das es eine surjektion ergibt? oder geht das ganz anders?

27.10.2007, 16:00

therisen

Auf diesen Beitrag antworten »

Die Abbildung ist sogar eine Bijektion.

27.10.2007, 16:15

FabiB

Auf diesen Beitrag antworten »

ja stimmt das dachte ich mir ja schon, ich glaube ich weiss blos nicht wie ich jetzt stichhaltig "beweise" das es sich um eine bijektion handelt.

27.10.2007, 16:16

therisen

Auf diesen Beitrag antworten »

Du weist einfach Injektivität und Surjektivität nach. Das ist beides schnell erledigt.

27.10.2007, 16:24

FabiB

Auf diesen Beitrag antworten »

kann ich die Abbildung auch so schreiben oder ist das nicht eindeutig?

$\begin{eqnarray*} f: P(\mathbb N_0) \to R \end{eqnarray*}$

$\begin{eqnarray*} f(\{a_0,a_1,...\}) =\sum_{i=0}^\infty~x^{a_i} = x^{a_0}+x^{a_1}+... \end{eqnarray*}$

27.10.2007, 18:27

FabiB

Auf diesen Beitrag antworten »

Injektivität:

zu zeigen: $\begin{eqnarray*} f(\{a_1,a_2,...\})=f(\{a'_1,a'_2,...\}) \Rightarrow\{a_1,a_2,...\}=\{a'_1,a'_2,...\} \end{eqnarray*}$

Also:

$\begin{eqnarray*} f(\{a_1,a_2,...\})=f(\{a'_1,a'_2,...\}) \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow x^{a_1}+x^{a_2}+...=x^{a'_1}+x^{a'_2}+... \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow \{a_1,a_2,...\}=\{a'_1,a'_2,...\} \end{eqnarray*}$

Ist diese letzte Implikation so richtig? Ich sehe die Begründung da drin, dass die Gleichung nur dann wahr sein kann, wenn auf jeder Seite x gleich oft vorkommt, d.h. dass die Menge der Potenzen von x auf beiden Seiten gleich ist. (Die Reihenfolge in der sie vorkommen spielt ja dabei keine Rolle aber das macht ja nichts da die Elemente einer Potenzmenge Mengen sind, oder?

Surjektivität:
also entweder ist es so einfach oder ich habe es nicht verstanden.

Also ich zeige, daß es zu jedem Element von R ein Urbild gibt.
d.h.

d.h. ich nehme y aus R:

$\begin{eqnarray*} y=x^{a_1}+x^{a_2}+... \end{eqnarray*}$

Es gibt für so ein y ein Urbild:

$\begin{eqnarray*} f(\{a_1,a_2,...\})=y \end{eqnarray*}$

gibt es da jetzt noch was zu zeigen?

27.10.2007, 19:49

therisen

Auf diesen Beitrag antworten »

Zitat:

Original von FabiB
kann ich die Abbildung auch so schreiben oder ist das nicht eindeutig?

$\begin{eqnarray*} f: P(\mathbb N_0) \to R \end{eqnarray*}$

$\begin{eqnarray*} f(\{a_0,a_1,...\}) =\sum_{i=0}^\infty~x^{a_i} = x^{a_0}+x^{a_1}+... \end{eqnarray*}$

Für endliche Teilmengen hast du ein Problem. Das kannst du aber beheben, indem du die restlichen $\begin{eqnarray*} a_i = 0 \end{eqnarray*}$ setzt.

Die Surjektivität ist tatsächlich so einfach. Die Injektivität würde ich etwas ausführlicher zeigen (beidseitige Inklusion). Klarer wird das ganze meiner Meinung nach, wenn man mit Folgen arbeitet, aber das hatte ich ja schon bemerkt.

27.10.2007, 19:58

FabiB

Auf diesen Beitrag antworten »

Zitat:

Original von therisen

Für endliche Teilmengen hast du ein Problem. Das kannst du aber beheben, indem du die restlichen $\begin{eqnarray*} a_i = 0 \end{eqnarray*}$ setzt.

wie kann ich das denn aufschreiben?

27.10.2007, 20:03

therisen

Auf diesen Beitrag antworten »

Am besten gar nicht, denn ich sehe gerade, dass das Ergebnis dadurch verfälscht wird. Denn $\begin{eqnarray*} x^0=1 \end{eqnarray*}$ .

27.10.2007, 20:08

FabiB

Auf diesen Beitrag antworten »

also sollte ich lieber die vorherige Version nehmen mit der Fallunterscheidung? oder einfach so lassen?

27.10.2007, 20:12

therisen

Auf diesen Beitrag antworten »

Ja, nimm die vorherige Version.

27.10.2007, 21:11

FabiB

Auf diesen Beitrag antworten »

hmm. irgendwie kann ich das problem doch nicht mehr ganz einsehen...

wo sollen denn irgendwelche endlichen teilmengen herkommen die ich berücksichtigen muss?

27.10.2007, 21:21

therisen

Auf diesen Beitrag antworten »

Du hast doch selbst schon welche genannt, z.B. $\begin{eqnarray*} \{1,3,4\}\in\mathcal{P}(\mathbb N_0) \end{eqnarray*}$ .

27.10.2007, 21:27

FabiB

Auf diesen Beitrag antworten »

hmm {1,2,4} usw. sind ja Elemente der menge P(N) und keine Teilmengen.
und alle Elemente von P(N) sind teilmengen von N.

. hast du eigentlich mal meine ausführung zur Injektivität und Surjektivität durchgesehen?

ist das im prinzip richtig so? ich bin mir nämlich noch nicht sicher wie ich zeige, dass eine Abbildung surjektiv ist, selbst wenn es offensichtlich ist.

27.10.2007, 22:10

fabelwesen

Auf diesen Beitrag antworten »

Hallo.

Ich les die Beiträge gerade ganz interessiert mit. Aber kann man um die Bijektivität zu zeigen, nicht die Umkehrabbildung konstruieren?

Das geht vielleicht schneller?

Grüße!

27.10.2007, 22:18

FabiB

Auf diesen Beitrag antworten »

also wenn es eine umkehrabbildung gibt müsste die abbildung bijektiv sein, das stimmt.
aber dann stellen sich mir zwei fragen.
1. wie lautet die umkehrabbildung?
2. wie beweise ich das es die umkehrabbildung ist?

27.10.2007, 22:19

therisen

Auf diesen Beitrag antworten »

Zitat:

Original von FabiB
hmm {1,2,4} usw. sind ja Elemente der menge P(N) und keine Teilmengen.
und alle Elemente von P(N) sind teilmengen von N.

Ja, ich war mit meinen Gedanken woanders, habe es mal editiert.

Zitat:

Original von FabiB
. hast du eigentlich mal meine ausführung zur Injektivität und Surjektivität durchgesehen?

ist das im prinzip richtig so? ich bin mir nämlich noch nicht sicher wie ich zeige, dass eine Abbildung surjektiv ist, selbst wenn es offensichtlich ist.

Ja, siehe Gleichmächigkeit von Mengen zeigen

@Fabelwesen) Ja, das wäre auch möglich. Aber ob es wirklich schneller ist (man muss ja zeigen, dass es die Umkehrabbildung ist) wage ich zu bezweifeln. Es ist ja beides schnell erledigt Augenzwinkern

Augenzwinkern

28.10.2007, 10:18

fabelwesen

Auf diesen Beitrag antworten »

Hallöchen.

Wäre da die Umkehrfunktion nicht sowas:

$\begin{eqnarray*} f: R \to P(\mathbb{N}_0) , f(r) = \bigcup_{i=0}^{\infty}{\{i: a_i = 1 \}} \end{eqnarray*}$
Gruß

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »