Kardinalität

01.11.2005, 18:41

ninaxyz

Kardinalität

Hi,
ich weiß nicht genau wie ich folgende Aufgabe beweisen soll.
Man zeige:

M°° ist abzählbar unendlich und cd M° = $\begin{eqnarray*} 2^{\mid x \mid} \end{eqnarray*}$ .

wobei M°°(X) die Menge aller Zählmaße auf X, also aller Abb. y: X--> $\begin{eqnarray*} \mathbb N_0 \end{eqnarray*}$ ist und M°(X) die Menge aller einfachen Zählmaße auf X, also aller Abb. y: X--> {0,1}ist.
Wie zeigt man, dass M°° abzählbar unendlich ist?
Und die Kardinalität ist zwar einleuchtend, aber wie zeigt man das.
Danke.

01.11.2005, 19:21

Auf diesen Beitrag antworten »

Zunächst mal hast du eine wichtige Information unterschlagen: Dass nämlich $\begin{eqnarray*} X \end{eqnarray*}$ endlich ist.

Sein $\begin{eqnarray*} n \end{eqnarray*}$ die Anzahl der Elemente von $\begin{eqnarray*} X \end{eqnarray*}$ . Die Menge aller Abb. $\begin{eqnarray*} y:\; X \to \mathbb{N}_0 \end{eqnarray*}$ entspricht dann der Menge aller $\begin{eqnarray*} n \end{eqnarray*}$ -Tupel von natürlichen Zahlen, d.h. $\begin{eqnarray*} \mathbb{N}_0^n \end{eqnarray*}$ . Und dass das abzählbar ist, hast du vielleicht schon mal gesehen (Diagonalverfahren).

02.11.2005, 13:41

ninaxyz

Auf diesen Beitrag antworten »

stimmt,das X endlich ist habe ich vergessen.
ich kenne nur dieses verfahren von cantor, bei dem man alle zahlenzweidimensional aufschreibt.etwa so
1/1 1/2 1/3......
2/1 2/2 2/3.....
3/1 3/2 3/3....
.
.
.
und dann alle kürzbaren brüche auslässt.
ich dachte, dass man damit die gleichmächtigkeit der rationale und der natürlichen zahlen zeigen kann. (habe ich aber nicht so ganz verstanden). Reicht es, weil ich sagen kann, das die rationalen zahlen unendlich sind Wenn nein, was bringt mir das für mei kleines problem? Falls doch, könnte mir dann jemand noch kurz das verfahren genauer erklären?
danke

02.11.2005, 14:30

Tobias

Auf diesen Beitrag antworten »

Also die Analogie zwischen den Zählmaßen und den n-Tupel hast du verstanden, oder?

Zuerst zeigen wir, dass $\begin{eqnarray*} \mathbb{N} \times \mathbb{N} \end{eqnarray*}$ abzählbar ist:

Wir schreiben die Elemente in ein Quadrat:

code:
1: 2: 3: 4: 5: 6: 7: 8: 9:	1 2 3 ... 1 (1,1) (1,2) (1,3) 2 (2,1) (2,2) (2,3) 3 (3,1) (3,2) (3,3) 4 (4,1) (4,2) (4,3) 5 (5,1) (5,2) (5,3) . .

Jetzt durchlaufen wir dieses Quadrat diagonal und bilden so eine Liste:

(1,1), (1,2), (2,1), (3,1), (2,2), (1,3), ....

In der Liste kommen alle Elemente aus $\begin{eqnarray*} \mathbb{N} \times \mathbb{N} \end{eqnarray*}$ vor. Jedes Element hat in dieser Liste auch eine Position. Wir bilden also bijektiv ein Tupel auf seine Position ab und haben so die Abzählbarkeit bewiesen.

Jetzt gehen wir über auf $\begin{eqnarray*} \mathbb{N} \times \mathbb{N} \times \mathbb{N} \end{eqnarray*}$ , indem wir wieder ein Quadrat bilden, diesmal bestehen die x-Elemente jedoch nichtmehr aus natürlichen Zahlen sondern Tupeln in der Reihenfolge der Auflistung von oben. Wir können wieder diagonal durchgehen und erhalten erneut eine aufzählbare Liste.

Das können wir induktiv fortsetzen und haben so gezeigt: $\begin{eqnarray*} \mathbb{N}^n \end{eqnarray*}$ ist abzählbar für alle n.

02.11.2005, 14:35

ninaxyz

Auf diesen Beitrag antworten »

ja, schönen dank. das habe ich wohl verstanden.
wie zeige ich denn die kardinalität? da fehlt mir jeder ansatz.
Das es so ist klingt zwar einleuchtend, aber ich weiß nicht wie ich es zeigen soll.
wäre nett, falls mir jemand dazu auch noch helfen könnte.
danke

02.11.2005, 22:03

ninaxyz

Auf diesen Beitrag antworten »

Ist das x denn die anzahl der zustande die man bei einem versuch erzielen kann, oder ist das die anzahl der Versuche die ich unternehme???
ich stehe echt auf dem schlauch.

03.11.2005, 19:05

Boing

Auf diesen Beitrag antworten »

Hi,
habe mir gerade diese aufgabe durchgelesen und verstehe etwas nicht.
Wenn doch X endlich ist (nach voraussetzung), wie kann dann eine Abbildung von X in die natürlichen Zahlen abzählbar unendlich sein????
Das ist mir irgendwie zu hoch.
Und dann noch etwas zum diagonalverfahren:
In zweiten schritt würde man dann die einträge aus der Liste unter dem Quadrat schreiben (in der Reihenfolge wie in der Liste) und die gleiche prozedur theoretisch immer wieder wiederholen???

03.11.2005, 19:37

Auf diesen Beitrag antworten »

Es geht nicht um eine solche Abbildung, sondern um die Anzahl aller solcher Abbildungen. Genauer lesen!

03.11.2005, 20:55

ninaxyz

Auf diesen Beitrag antworten »

hi nochmal
@ Arthur
hast du vielleicht ne idee, wie ich das kardinalitätsproblem löse?
sitze da schon den ganzen Tag drüber
habe ^den tipp bekommen:
Sei y element M°
M°(X) = {y : y: M°----> {0,1}}
das entspricht = {y~ : y~ kleiner oder gleich X}
dann folgt
cd M° =cd {y~: y~ kleiner gleich X} = 2^{cd x}
ich verstehe aber noch nicht so genau, warum und wie ich mir das y~wählen kann.
Schönen Dank, falls mir jemand hilft.

Neue Frage »

Antworten »

Kardinalität

Verwandte Themen