Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Abzählbarkeit von Q und NxN

Abzählbarkeit von Q und NxN

Universität / Fachhochschule

Tags: Abzählbarkeit

Mathemaus90 aktiv_icon

16:48 Uhr, 18.11.2010

Hey! Ich komm leider mit der Aufgabe gar nicht klar und würde mich sehr über eure Hilfe freuen!

a)

Finden Sie eine Abzählung

ℕ \to ℕ \times ℕ

. (Hinweis: Definieren Sie die Abbildung rekursiv.)

b)

Zeigen Sie, dass

ℚ

abzählbar ist.

a)

Also, in der Vorlesung haben wir dazu ein Abzählschema notiert...

(0,0) (1,0) (2,0)

(0,1) (1,1) (2,1)

(0,2) (1,2) (2,2)

usw.

Die rekursive Funktion haben wir

z . T

. im Tutorat gegeben.

f : ℕ \to ℕ \times ℕ

n \mapsto (f_{1} (n), f_{2} (n))

n + 1 \mapsto {(f_{1} (n) + 1, f_{2} (n) - 1)

falls

f_{2} (n) = 0

(0, f_{1} (n) + f_{2} (n) + 1)

falls

f_{2} (n) = 0}

Aber ich vermute, ich hab' da einen Schreibfehler?
Kann mir vielleicht jemand erklären, wie man auf diese Abbildung kommt? Und was ich jetzt damit machen soll?
Muss ich einfach zeigen, dass diese Abbildung bijektiv ist? Aber die Umkehrabbildung muss doch auch noch irgendwo eine Rolle spielen, oder?

b)

Wir wissen ja, dass

ℕ ⋆

und

ℤ

abzählbar sind. Nur wie kann man daraus schließen, dass

ℚ

auch abzählbar ist?
Die Definitiovn von

Q

ist ja so.

q = \frac{m}{n}

mit

m \in ℤ

und

n \in ℕ ⋆

.
Kann man

Q

also irgendwie aus

ℕ ⋆ \times ℤ

darstellen?

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

Pocahontas007 aktiv_icon

22:45 Uhr, 18.11.2010

2)

Stell jede rationale Zahl als Bruch

\frac{m}{n}

mit teilerfremden

m \in ℤ

und

n \in ℕ

dar. Alle diese Brüche kannst du in Gitterform aufschreiben

. .

- \frac{2}{1} - \frac{1}{1} \frac{0}{1} \frac{1}{1} \frac{2}{1} \frac{3}{1} . .

. .

- \frac{2}{2} - \frac{1}{2} \frac{0}{2} \frac{1}{2} \frac{2}{2} \frac{3}{2} . .

. .

- \frac{2}{3} - \frac{1}{3} \frac{0}{3} \frac{1}{3} \frac{2}{3} \frac{3}{3} . .

.
.
.
.

Wenn du dieses Gitter im Ansatz aufgeschrieben hast, kannst du mit abzählen beginnen: Start bei

\frac{0}{1}

weiter zu

\frac{1}{1}, \frac{1}{2}, \frac{0}{2}, - \frac{1}{2}, - \frac{1}{1}, - \frac{2}{1}, - \frac{2}{2}, - \frac{2}{3}, - \frac{1}{3}, . .

.
Erkennst du das Muster?
Dabei musst du beachten, dass Brüche deren

m, n

nicht teilerfremd sind bei der Abzählung übersprungen werden.

Du erzeugst also eine bijektive Abbildung

ℕ

nach

ℚ

Mathemaus90 aktiv_icon

18:07 Uhr, 20.11.2010

Dankeschön :-) Und das reicht dann als Beweis aus, oder?

Pocahontas007 aktiv_icon

14:36 Uhr, 21.11.2010

Gern geschehn

(=

Also bei uns hat das so gereicht!

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

822510

821335

	Status: nicht eingeloggt	Noch nicht registriert?