Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Beweis der Abzählbarkeit einer unendlichen Menge

Beweis der Abzählbarkeit einer unendlichen Menge

Universität / Fachhochschule

Sonstiges

Tags: Sonstiges

Komisch aktiv_icon

11:53 Uhr, 15.10.2014

Hi,

ich möchte zeigen, dass

ℕ

und

ℤ^{2}

gleichmächtig sind. Das die natürlichen Zahlen abzählbar unendlich sind ist denke ich klar. Das die Menge der Quadrate der ganzen Zahlen unendlich abzählbar sind müsste ich irgendwie zeigen.

Erste Gedanke von mir war ich muss zeigen, dass es zwischen den Mengen eine bijektive Abb. gibt. (f(x)=x^2)
Allerdings möchte ich von dem Fall ausgehen, dass ich keine solche Abb. finden kann. Wie würde ich in diesem Fall vorgehen um trotzdem die Bijektivität zu zeigen. Zwischen zwei abzählbar unendlichen Mengen existiert immer eine bijektive Abbildung

\Rightarrow

ich muss diese Eigenschaft für das Quadrat der ganzen Zahlen zeigen.

Wie ich so etwas zeige weiß ich leider nicht und wir haben in der Vorlesung auch die für keine Menge jemals bewiesen. Außerdem bin ich mir nicht sicher, dass ich die Eigenschaft, dass zw. 2 unendlichen abzählbaren Mengen immer eine bijektive Abb. existiert einfach voraussetzen kann oder ob dies auch erst von mir bewiesen werden muss.

(Oder gibt es vielleicht noch eine ganz andere Möglichkeit. (Das Cantor'sche Diagonalisierungsverfahren habe ich mir noch nicht angesehen)

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Bummerang

12:04 Uhr, 15.10.2014

Hallo,

ℤ^{2}

ist nicht die Menge aller Quadrate ganzer Zahlen sondern das Kreuzprodukt

ℤ \times ℤ

und damit die Menge aller Paare

(m, n)

mit

m, n \in ℤ!

Komisch aktiv_icon

12:19 Uhr, 15.10.2014

Gut, dann finde ich tatsächlich keine Funktion die mir eine Abbildung zwischen diesen Mengen ermöglicht. Damit müsste ich dann also einen anderen Weg gehen.

Wie genau gehe ich diesen "anderen" Weg? ...und welchen sollte ich wählen?

Respon

12:28 Uhr, 15.10.2014

Cantor'sches Diagonalverfahren

Bummerang

12:33 Uhr, 15.10.2014

Hallo,

es gibt nur den Weg über bijektive Abbildungen. Ich würde zunächst eine Bijektion

ℤ \to ℕ

suchen, mit deren Hilfe ich eine Bijektion von

ℤ^{2} \to ℕ^{2}

definiere. Als Bijektion von

ℕ^{2} \to ℕ

nehme ich die, die auch beim Beweis der Gleichmächtigkei von

ℚ

und

ℕ

benutzt wurde. Die Hinter- und Ineinanderausführung dieser Bijektionen ergibt eine gesuchte Bijektion.

Komisch aktiv_icon

17:09 Uhr, 19.10.2014

Ich habe es bis heute nicht gelöst. Eine bijektive Funktion für

ℤ \to ℕ

zu finden oder

ℤ^{2} \to ℕ^{2}

war kein Problem für

ℕ^{2} \to ℕ

oder

ℚ \to ℕ

finde ich keine bezeichne mich als dumm aber keine Ahnung es geht nicht.

Ich kann es mir grafisch aufmalen etc. aber selbst komm ich nicht drauf.
Ich kann aus Wiki (Cantor'sche Paarungsfunktion) mir eine Formel kopieren aber auch das bringt mich nicht ans Ziel.

π (x, y) = \frac{1}{2} (x + y) (x + y + 1) + y

Könnt ihr mir bitte eine klare Anleitung geben wie man so eine Funktion finden kann?

Bummerang

11:48 Uhr, 20.10.2014

Hallo,

bijektive Abbildung

φ : ℤ \to ℕ :

Alle nichtnegativen Zahlen

z_{g \in} ℤ

werden abgebildet auf

2 \cdot z_{g \in} ℕ_{0}

(bei mir ist

ℕ_{0}

die Menge der natürlichen Zahlen die Null!), alle negativen Zahlen

z_{u} \in ℤ

werden abgebildet auf

- 2 \cdot z_{u} - 1 \in ℕ

Gemäss dieser Bijektion wird jede nichtnegative ganze Zahl auf eine gerade natürliche Zahl abgebildet und jede negative ganze Zahl auf eine ungerade natürliche Zahl.

bijektive Abbildung

ψ : ℤ^{2} \to ℕ_{0}^{2}

Jedem Paar

(z_{1}, z_{2}) \in ℤ^{2}

wird das Paar

(φ (z_{1}), φ (z_{2})) \in ℕ^{2}

zugeordnet. Auch das ist eine Bijektion.

bijektive Abbildung

ρ : ℕ_{0}^{2} \to N

In einem (Cantor-) Tableau gibt es Zeilen und Spalten. Die Zeilen stehen für das erste Element im Paar

(n_{z}, n_{s}) \in ℕ^{2},

die Spalten für das zweite Element dieses Paares. die erste Zeile steht somit für die 0 als erstes Element im Paar, die zweite für die

1,

usw.. Die erste Spalte analog für die 0 als zweites Element im Paar, die zweite für die

1,

usw.. Jetzt beginn man in der ersten Spalte der ersten Zeile (steht für

(0,0))

diesem Element die 1 zuzuordnen. Jetzt geht man eine Spalte nach rechts (steht für

(0,1))

und ordnet diesem Feld die 2 zu. Jetzt geht man diagonal nach links unten und ordnet den Feldern, die man dabei streift, die nächsten Zahlen zu. Das ist hier am Anfang nur das Feld, das für

(1,0)

steht und die zugeordneten Zahlen beschränken sich auf die 3. Jetzt geht man ein Feld tiefer (steht für

(2,0))

und vergibt die 4. Dann diagonal nach rechts oben bis zum Feld

(0,2),

dabei werden die Zahlen 5 und 6 vergeben. Dann wieder nach rechts auf das Feld

(0,3)

und die 7 vergeben. Dann diagonal nach links unten bis zum Feld

(3,0)

und die Zahlen

8, 9

und

10

vergeben.

. .

.

Erkennst Du das Prinzip, das nennt sich Cantor-Diagonalisierung (genauer Cantors erstes Diagonalargument) und ist das klassische Prinzip zur Bestätigung der Abzählbarkeit bei unendlichen Mengen. Auch dieses Verfahren ist eine Bijektion, denn man kann einfach einer Zahl

n \in ℕ

durch abzählen der Felder ein bestimmtes Feld eindeutig zuordnen. Die Hinter- und Ineinanderausführung dieser drei Bijektionen ergibt wieder eine Bijektion:

ℤ^{2} \to ℕ : (z_{1}, z_{2}) \mapsto (ρ \circ ψ) (z_{1}, z_{2}) = ρ (φ (z_{1}), φ (z_{2}))

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

1191853

1190350

	Status: nicht eingeloggt	Noch nicht registriert?