N x N x N Tripe Aufzählbarkeitsprinzip Cantor

Aufrufe: 130     Aktiv: 22.10.2023 um 00:19

0
Konkrete Aufgabe:
Auch die Menge N^3 der Zahlentripel über den natürlichen Zahlen ist gleich groß, d.h.: sie ist abzählbar
unendlich. Um diese Behauptung zu beweisen, sollen Sie eine Aufzählung der Elemente von N^3 skizzieren.
Zwecks Nachvollziehbarkeit der Aufzählung, sollten Sie bei dieser Aufzählung die Zahlentripel in Gruppen
gliedern. Geben Sie für jede Gruppe auch die Anzahl der Elemente in dieser Gruppe sowie die Positionen,
die die Elemente der Gruppe in der Aufz ̈ahlung einnehmen, an.

Ich hab probiert die Gruppe soll einfach die Summe aller Werte im Tripel und deshalb eindeutig dann sein.
Nur habe ich Probleme die Anzahl einer beliebigen Summe zu definiere bzw. die Position.

Als Bsp in den Unterlagen ist
"Idee: für M = N × N:
Aufzählung (Cantor’sches Abzählprinzip):
(0,0),
(1,0), (1,1), (0,1),
(2,0), (2,1), (2,2), (1,2), (0,2)
(3,0), (3,1), (3,2), (3,3), (2,3), (1,3), (0,3),
etc."
Gebe es eine andere Möglichkeit außer der Summe des Tripels. Eine einfachere wie o.a für die Tupel N^2

Danke und LG
gefragt

Punkte: 16

 
Kommentar schreiben
1 Antwort
1
Man kann z.B. die Tripel nach ihrem Maximum gruppieren:
\( G_m =  \{(a,b,c)\in\mathbb{N}_0^3;\; \max(a,b,c)=m\} \) für \(m\in\mathbb{N}_0\).

Die Elemente von \(G_m\) kann man wie folgt aufzählen:
  1. Zuerst kommen die Tripel aus \(A_m \;=\; \{(m,b,c); \; b\le m,\, c \le m\}\).
    Von diesen Tripeln gibt es \((m+1)^2\) Stück.
  2. Dann kommen die Tripel aus \(B_m \;=\; \{(a,m,c); \; a<m,\,c \le m\}\).
    Von diesen Tripeln gibt es \(m(m+1)\) Stück.
  3. Dann kommen die Tripel aus \(C_m \;=\; \{(a,b,m); \; a<m,\,b<m\}\).
    Von diesen Tripeln gibt es \(m^2\) Stück.
Die Tripel von \(A_m\) können lexikographisch durchgezählt werden:
\((m,0,0),\,(m,0,1),\ldots,(m,0,m)\)
\((m,1,0),\,(m,1,1),\ldots,(m,1,m)\)
\(\ldots\)
\((m,m,0),\,(m,m,1),\ldots,(m,m,m)\)

Die Position eines Tripels \((m,b,c)\) innerhalb von \(A_m\) ist dann \(1+(m+1)b + c\).
\(B_m\) und \(C_m\) können ebenfall lexikographisch durchgezählt und so durchnumeriert werden.

Die Position p eines Tripels T innerhalb \(G_m\) kann wie folgt bestimmt werden:
  • Falls \(T\in A_m\), dann ist p = Position von T innerhalb von \(A_m\)
  • Falls \(T\in B_m\), dann ist p = \((m+1)^2\) + (Position von T innerhalb von \(B_m\))
  • Falls \(T \in C_m\), dann ist p = \((m+1)^2 + m(m+1)\) + (Position von T innerhalb von \(C_m\))

\(G_m\) hat dann soviele Elemente \(A_m\), \(B_m\) und \(C_m\) zusammen, also \((m+1)^2 + m(m+1) + m^2 = (m+1)^3 - m^3\) Elemente.

Die Position eines Tripels \(T\in G_m\) innerhalb von \(\mathbb{N}_0^3\) ist dann:
Position von T innerhalb von \(G_m\) + (Anzahl der Tripel mit Maximum < m)
= Position von T innerhalb von \(G_m\) + \(m^3\).
Diese Antwort melden
geantwortet

Punkte: 1.05K

 

Kommentar schreiben