Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Gleichmächtigkeit begründen

Gleichmächtigkeit begründen

Universität / Fachhochschule

Sonstiges

Tags: Menge

snowman81145 aktiv_icon

16:12 Uhr, 23.06.2009

Hallo,

ich habe folgende zwei Menge

A = ℕ \times ℕ

und

B = ℕ \times ℕ \times ℕ

und soll:

1. festellen, ob die beiden Mengen gleichmächtig sind und
2. dies Begründen.

Was ich weiß ist, dass

A \times B = {(x; y) | x

A ⋀ y

B}

und das

ℕ

abzählbar unendlich ist - was auch immer das heißen mag.

Meine erste Frage ist nun: Wenn ich die Produktmenge der einzelnen Mengen bilde, verändert sich dann deren Mächtigkeit?

Spontan würde ich sagen nein. Auch wenn ich das nicht begründen kann. Daraus würde ich dann schlussfolgern, dass die Mengen gleichmächtig sind.

Da kommt auch gleich die zweite Frage: Wie kann ich das nun beweisen?

Und für den Fall, dass die beiden Mengen doch nicht gleichmächtig sind die dritte Frage: Woher weiß ich, wann eine Menge ihre Mächtigkeit ändert? Besonders, wenn es so wie hier, immer der gleiche Zahlenbereich ist.

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich bräuchte bitte einen kompletten Lösungsweg." (setzt voraus, dass der Fragesteller alle seine Lösungsversuche zur Frage hinzufügt und sich aktiv an der Problemlösung beteiligt.)

Astor aktiv_icon

16:37 Uhr, 23.06.2009

Hallo,
wenn zwei Mengen gleichmächtig sind, so gibt es eine bijektive Abbildung von einer Menge zur anderen.
So würde ich sagen, dass die Mengen

N x N

und

N x N x 1

gleichmächtig sind.
Aber nicht mehr:

N x N

und

N x N x 1; 2

Gruß Astor

snowman81145 aktiv_icon

17:32 Uhr, 23.06.2009

Ok, erst mal Danke für die Antwort, aber so richtig klar ist mir das noch nicht.

Ich habe jetzt in meinem schlauen Hefter nachgeschlagen und ein paar sehr interessante Sachen gefunden. Zunächst einmal das mit der äquivalenten Menge

A ~ B

was Astor schon einmal erwähnt hat. Hinzu kommt das eine Bijektion folgende Bedingungen erfüllt:

A ~ B

(reflexiv)

A ~ B ⋀ B ~ C \Rightarrow A ~ C

(transitiv)

A ~ B \Rightarrow B ~ A

(symmetrisch)

Dann habe ich noch zwei schöne Sätze gefunden:

Eine Menge A heißt unendlich, wenn es eine Bijektion von A auf eine echte Teilmenge von A gibt, andernfalls heißt sie endlich.

Eine Menge A heißt abzählbarunendlich, wenn

A ~ ℕ

. Eine unendliche Menge, die nicht abzählbar unendlich ist, heißt überabzählbar unendlich.

Mit diesen ganzen Ingredienzien muss ich mir doch jetzt eine Lösung zusammenstellen können oder?

Ich denke ja, das ich das mit den Bedingungen machen kann. Allerdings habe ich jetzt das Problem, dass ich nicht so richtig weiß wie die Menge A und

B

aufschreiben soll.

Ich habe jetzt das hier versucht:

A = {{0,0}; {0,1}; {0,2}; ...; {1,0}; {1,1}; {1,2}; ...; {2,0}; {2,1}; {2,2}; ...}

und

B = {{0,0,0}; {0,0,1}; {0,0,2}; ...; {0,1,0}; {0,1,1}; {0,1,2}; . .

{0,2,0}; {0,2,1}; {0,2,2}; ...; {1,0,0}; {1,0,1}; {1,0,2}; ...; {1,1,0}; {1,1,1}; {1,1,2}; . .

{1,2,0}; {1,2,1}; {1,2,2}; ...; {2,0,0}; {2,0,1}; {2,0,2}; ...; {2,1,0}; {2,1,1}; {2,1,2}; . .

{2,2,0}; {2,2,1}; {2,2,2}; ...;}

Jetzt stehe ich allerdings wieder vor dem Problem, obwohl ich die ganzen Informationen oberhalb der zwei Mengen stehen habe, nicht weiß, ob die Mengen nun unendlich, abzählbar unendlich oder überabzählbar unendlich sind. Vielleicht kann mir das ja mal einer an einem Beispiel erklären und keine Hotelgeschichten bitte.

Mfg snowman81145

Rentnerin

07:46 Uhr, 24.06.2009

Hallo,

wenn es bijektive Abbildungen

f : N \to A

und

g : N \to B

gibt, dann gibt es auch bijektive Abbildungen von

A \times B

nach

N

. Mit

f (k) = a_{k}

und

g (l) = b_{l}

kannst Du z.B.

Λ : A \times B \to N

Λ (a_{k}, b_{l}) = 2^{k - 1} \cdot (2 l - 1)

als Bijektion wählen.

Gruß Rentnerin

snowman81145 aktiv_icon

11:37 Uhr, 26.06.2009

Danke für die Antwort.

Den ersten Teil kann ich, denke ich, auch grad noch so verstehen. Aber beim zweiten Teil

\land : A x B \to N, \land (a_{k}, b_{l}) = 2^{k - 1} \cdot (2 l - 1)

weiß ich absolut nicht wie man darauf kommt. Kannst du mir das erklären?

MfG Snowman81145

Rentnerin

20:08 Uhr, 26.06.2009

Die

a_{k}

werden auf die 2-er Potenzen und die

b_{l}

auf die ungeraden Zahlen abgebildet. Wenn nun das Paar

(a_{k}, b_{l})

auf das Produkt der 2-er Potenzen mit den ungeraden Zahlen abgebildet wird, dann liegt eine Bijektion vor.

Surjektivität:
Jedes

n \in N

läßt sich wegen der Eindeutigkeit der Primzahlzerlegung darstellen als

2^{x} \cdot m

, wobei

m

in Primzahlen ungleich 2 zerlegt werden kann;

m

ist also ungerade.

Injektivität:
Wenn die Elemente

(a_{k_{1}}, b_{l_{1}})

und

(a_{k_{2}}, b_{l_{2}})

auf dieselbe natürliche Zahl abgebildet werden, also

2^{k_{1} - 1} \cdot (2 l_{1} - 1) = 2^{k_{2} - 1} \cdot (2 l_{2} - 1)

,
dann folgt wieder wegen der Eindeutigkeit der Primfaktorzerlegung, dass jeweils in den rechten Faktoren die 2 nicht enthalten sein kann und damit

k_{1} = k_{2}

sein muss, woraus auch

l_{1} = l_{2}

folgt.

snowman81145 aktiv_icon

16:59 Uhr, 30.06.2009

Erst mal nochmals Danke für die Antwort und Entschuldigung für die späte Antwort.
Jetzt muss ich allerding zugeben das ich das ganze doch nicht so richtig verstanden habe. Ich verstehe nicht warum

k_{1} = k_{2}

ist nur weil die zwei nicht in den rechten Faktoren enthalten ist. Setzt man nicht für

k_{1}

und

k_{2}

zwei natürliche Zahlen ein

z . B

. 1 und 2 oder mach ich mir da nur was vor?

MfG snowman81145

Rentnerin

17:09 Uhr, 30.06.2009

Wenn die Bilder der beiden Elemente

(a_{k_{1}}, b_{l_{1}})

und

(a_{k_{2}}, b_{l_{2}})

gleich sind, d.h.

2^{k_{1} - 1} \cdot (2 l_{1} - 1) = n = 2^{k_{2} - 1} \cdot (2 l_{2} - 2)

,

dann sind die linken Faktoren Zweierpotenzen und die rechten Faktoren ungerade Zahlen. Wegen der Eindeutigkeit der Primfaktorzerlegung von n müssen die Exponenten der Zweierpotenzen gleich sein. Beachte: In den rechten Faktoren sind

\underline{k e i n e}

Zweierpotenzen enthalten!

snowman81145 aktiv_icon

18:42 Uhr, 30.06.2009

Ist das so kompliziert oder stelle ich mich nur so blöd an? Je nachdem wie groß mein

l

ist könnte ich doch diese Zahl also

2 l

wieder in Zweierpotenzen schreiben und mein

k

würde bei der Multiplikation größer werden. Könntest du mir vielleicht beispielhaft sagen was ich für

k_{1}, k_{2}, l_{1}

und

l_{2}

einsetzen muss/kann. Nur zum Verständnis. Hab hier echt Probleme das nachzuvollziehen. Sorry!

Rentnerin

23:48 Uhr, 30.06.2009

Hallo,

l_{1}

und

l_{2}

sind beliebige natürliche Zahlen und damit sind

2 l_{1} - 1

und

2 l_{2} - 1

ungerade. Wieso sollen hierin Zweierpotenzen enthalten sein?

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

626645

624729

	Status: nicht eingeloggt	Noch nicht registriert?