Beweis über abzählbare Menge < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:51 So 15.04.2012 | | Autor: | yangwar1 |
| Aufgabe | | Zeigen Sie, dass die Menge [mm] \IN [/mm] x [mm] \IN [/mm] = {(m, n):m,n [mm] \in \IN} [/mm] abzählbar ist. |
Hallo,
folgende Definition:
Sei A eine Menge.
A heißt abzählbar, wenn A endlich oder abzählbar unendlich ist.
A heißt abzählbar unendlich, wenn es eine bijektive Abbildung c: [mm] A->\IN [/mm] gibt.
Die Aufgabe ist auf einem Übungszettel in Informatik. Die Menge [mm] \IN [/mm] x [mm] \IN [/mm] ist nicht endlich. Zu zeigen ist also, dass die Menge [mm] \IN [/mm] x [mm] \IN [/mm] abzählbar unendlich ist. Dazu müsste man eine bijektive Abbildung [mm] \IN [/mm] x [mm] \IN [/mm] -> [mm] \IN [/mm] finden. Die Abbildung f: [mm] \IN [/mm] x [mm] \IN ->\IN, [/mm] f(m,n):=m ist injektiv und surjektiv. Damit ist eine Abbildung gefunden, somit ist die Menge [mm] \IN [/mm] x [mm] \IN [/mm] abzählbar unendlich und somit abzählbar.
Stimmt das? Würde mir nämlich ein bisschen leicht vorkommen, für eine Übungsaufgabe.
|
|
| |
|
Hallo,
> Zeigen Sie, dass die Menge [mm] \IN [/mm] x [mm] \IN [/mm] = {(m, [mm] n):m,n\in \IN}
[/mm]
> abzählbar ist.
> Hallo,
> folgende Definition:
> Sei A eine Menge.
> A heißt abzählbar, wenn A endlich oder abzählbar
> unendlich ist.
> A heißt abzählbar unendlich, wenn es eine bijektive
> Abbildung c: [mm] A->\IN [/mm] gibt.
> Die Aufgabe ist auf einem Übungszettel in Informatik. Die
> Menge [mm]\IN[/mm] x [mm]\IN[/mm] ist nicht endlich. Zu zeigen ist also,
> dass die Menge [mm]\IN[/mm] x [mm]\IN[/mm] abzählbar unendlich ist.
![[ok]](/images/smileys/ok.gif "[ok]")
> Dazu
> müsste man eine bijektive Abbildung [mm]\IN[/mm] x [mm]\IN[/mm] -> [mm]\IN[/mm]
> finden.
> Die Abbildung f: [mm]\IN[/mm] x [mm]\IN ->\IN,[/mm] f(m,n):=m ist
> injektiv und surjektiv.
Nein. Die Injektivität ist doch locker verletzt:
f(1,2) = f(1,3) = f(1,4) = 1.
Dass deine Argumentation nicht funktionieren kann, siehst du auch an der Tatsache, dass deine Funktion auch für eine Menge
[mm] $\IN \times \IR \to \IN$
[/mm]
Abzählbarkeit liefern würde, obwohl [mm] $\IN \times \IR$ [/mm] nicht abzählbar ist.
--------
Um eine geeignete Funktion zu finden, kannst du dich am Diagonalverfahren orientieren: Schreibe waagerecht und senkrecht die Zahlen 1,2,3,4,5,... der Menge [mm] \IN [/mm] auf, und zähle dann diagonal ab:
1 2 3 4 5 6
------------------
1 I 1 3 6 10 15 21
2 I 2 5 9 14 20
3 I 4 8 13 19
4 I 7 12 18
5 I 11 17
6 I 16
Finde also eine Funktion, die dem Paar (1,1) den Wert 1 zuordnet, (1,2) den Wert 3, usw.
Viele Grüße,
Stefan
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:23 So 15.04.2012 | | Autor: | tobit09 |
Hallo yangwar,
> Zeigen Sie, dass die Menge [mm]\IN[/mm] x [mm]\IN[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
= $\{$(m, n):m,n [mm]\in \IN$\}$[/mm]
> abzählbar ist.
Wisst ihr schon, dass abzählbare Vereinigungen abzählbarer Mengen wieder abzählbar sind?
In diesem Fall betrachte mal
[mm] $A_n:=\{(m,n)|m\in\IN\}$
[/mm]
für [mm] $n\in\IN$.
[/mm]
Viele Grüße
Tobias
|
|
|
|
