Abzählbarkeit + Gleichmächtigkeit + Primzahl
-
knivil schrieb:
wohl beste Abzählung ...
Ansichtsache, ich finde meine Abzaehlung viel besser
ganz ohne Rechnen.Meins hat auch kein Rechnen
Für diverse Dinge ist das aber vonnöten oder zumindest nützlich, eine Formel zu haben.
Und vor allem: deine Abzählung ist zu meiner identisch
-
ZetaX schrieb:
knivil schrieb:
wohl beste Abzählung ...
Ansichtsache, ich finde meine Abzaehlung viel besser
ganz ohne Rechnen.Meins hat auch kein Rechnen
Für diverse Dinge ist das aber vonnöten oder zumindest nützlich, eine Formel zu haben.
Und vor allem: deine Abzählung ist zu meiner identischBist du dir sicher?
knivils Ordnung führt IMHO zu keiner Durchnummerierung, solange er nicht erklärt, wie man Tupel unterschiedlicher Länge lexikografisch vergleichen soll.
Deine Abbildung bildet endliche Teilmengen von natürlichen Zahlen auf natürliche Zahlen ab. Die Menge IN* ist aber die Menge aller endlichen Folgen, nicht die Menge aller endlichen Teilmengen von IN.
-
TI'er schrieb:
Und dann noch, ob N und N* auch gleich mächtig sind.
mir wills nicht einsehen, daß sie gleichmächtig sind.
vielleicht sollten wir nach einem beweis suchen, daß N* in einer höheren mächtigkeitsklasse steckt.
aber nur aus sportlichem interesse, da TI'er nicht mehr mitmacht. sozusagen thisforum-interner wettbewerb.
-
Vielen lieben Dank, ich bin ja förmlich erschrocken, wieviel hier plötzlich stand, huiiijujujuju
Ich werde es mir aber morgen/heute erst durchlesen, da ich den ganzen Tag ne so viel Zeit hatte und jetzt zu müde bin.Danke nochmal allen!!!
-
volkard schrieb:
TI'er schrieb:
Und dann noch, ob N und N* auch gleich mächtig sind.
mir wills nicht einsehen, daß sie gleichmächtig sind.
Hmm... An welcher Stelle hapert's denn mit dem Verständnis?
1. N, NxN, NxNxN, ... sind alle gleich mächtig.
2. N* = N u NxN u NxNxN u ... (wobei 'u' "disjunkt vereinigt mit" heissen soll)
3. N* ~ N u NxN u NxNxN u ... ~ N u N u N u ... ~ NxN ~ N (wobei '~' "ist gleichmächtig wie" heissen soll)
-
SG1 schrieb:
Hmm... An welcher Stelle hapert's denn mit dem Verständnis?
mir haperts daran, daß
ähm, moment mal.SG1 schrieb:
1. N, NxN, NxNxN, ... sind alle gleich mächtig.
ok, das sehe ich ein.
solange es nicht N^inf wird. aber N^inf darf ja gar nicht mitspielen. also: ok.SG1 schrieb:
2. N* = N u NxN u NxNxN u ... (wobei 'u' "vereinigt mit" heissen soll)
das verstehe ich nicht.
3. N* ~ N u NxN u NxNxN u ... ~ N u N u N u ... ~ NxN ~ N (wobei '~' "ist gleichmächtig wie" heissen soll)
das wäre wieder klar.
-
gna
-
[quote="volkard"]
SG1 schrieb:
Hmm... An welcher Stelle hapert's denn mit dem Verständnis?
SG1 schrieb:
2. N* = N u NxN u NxNxN u ... (wobei 'u' "vereinigt mit" heissen soll)
das verstehe ich nicht.
sorry. *me haut sich die tastatur an den kopf*
ich verstehe es.
ich werde das jetzt noch ein paar mal lesen müssen, um es auch zu glauben, (das gesamtergebnis meine ich) bis morgen hab ichs begriffen.
lustig, ich weiß es, aber glaube es noch nicht. das muss ich mal in einen der unzählichen religionsthreads einbringen.
und danke für die übersichtliche zusammenfassung.
-
Ben04 schrieb:
Hier geht es jedoch um eine Vereinigung unendlich vieler Mengen.
so, hab' drüber nachgedacht. Wenn A_1, A_2, A_3, ... abzählbar viele abzählbare Mengen sind und a_nm das m-te Elemt. von A_n bezeichnet, dann betrachtet man folgende Anordnung:
a_11 a_12 a_13 ...
a_21 a_22 a_23 ...
a_31 a_32 a_33 ...
...
...
...und zählt diese Anordnung so ab wie N x N.
A_1 u A_2 u A_3 ... erhält man aus dieser Anordnung durch Weglassen von (mehrfachen) Elementen, was an der Tatsache der Abzählbarkeit nichts ändert.
-
Lexikographisch bedeutet: Erst nach Laenge sortieren und dann "alphabetisch". So kann man z.B. zeigen, dass A*, wobei A ein endliches Alphabet ist, abzaehlbar ist. Das Problem bei N* ist, dass zwischen den Elementen {123, 124} und {123, 125} unendlich viele Elemente liegen. Das ist bloed wenn man sie Durchnumerieren moechte. Deswegen das zusaetzlich vorangestellte Kriterium der Summe.
Wenn z.B. die Null erstmal aussen vorgelassen wird, reicht die Summe und lexikographische Ordnung als Kriterium (die alphabetische wuerde dann auch reichen). In diesem Fall wuerde die Ordnung so aussehen:
Summe: 0 ; 1 ; 3 ; 4 ; ....
Folge: () ; (1) ; (2), (1,1) ; (3), (1,2) (2,1), (1,1,1) ; (4) , (1,3) , (2,2), ...Wenn ich jetzt alle nacheinander aufzaehle, dann lasse ich kein Element aus und ich habe eine Durchnummerierung. Gewiss es ist nur eine Beweisidee, aber das korrekt aufzuschreiben, ist mit Boardmitteln zu umstaendlich. Nimmt man die 0 hinzu, muss man sich noch ein klein wenig mehr einfallen lassen, verkompliziert die Sache aber nur, veraendert die Maechtigkeit aber nicht (man koennte die 0 als 0.5 in der Summe werten).
@ZetaX: Langsam finde ich deine Abzaehlung auch besser, sie ist einfach weniger kompliziert und es gibt weniger Noergler.
3. N* ~ N u NxN u NxNxN u ... ~ N u N u N u ... ~ NxN ~ N
Das ist komisch, rein intuitiv wuerde ich die Argumentation ablehnen (oder zumindestens es anders machen), da es hier um unendliche Vereinigung geht. Auch ist N u N u N u ... = N.
-
-
knivil schrieb:
Auch ist N u N u N u ... = N.
*dumdidum* *editier*
-
knivil schrieb:
Das ist komisch, rein intuitiv wuerde ich die Argumentation ablehnen (oder zumindestens es anders machen), da es hier um unendliche Vereinigung geht.
die Argumentation ist schon Ok, Vereinigungen von abzählbar vielen abzählbaren Mengen sind abzählbar, das beweist sich genau so wie N ~ N x N.
-
Eigentlich sollte den theoretischen Informatikern auch noch eine andere Abzählung bekannt sein, genannt Gödelnummern
Der Folge a_1 , ... , a_n (positiver) natürlicher Zahlen ordne man {p_1}{a_1}·{p_2}{a_2}· ... ·{p_n}^{a_n} zu, wobei p_k die k-te Primzahl ist. Will man die 0 als natürliche Zahl unbedingt mit rein, muss man eben alle Exponenten um 1 erhöhen.Es gibt in der Praxis eh nur die endlichen, die abzählbare und die kontinuierliche Kardinalität, alles weitere läuft einem außerhalb der Logik nie als solche übern Weg
Klar gibt es viel mehr, aber man erreicht sie seltenst bewusst (und unbewusst auch nur wenig mehr als obige, z.B. als endliche Iteration von Potenzmengen obiger Mengen).
-
ZetaX schrieb:
Es gibt in der Praxis eh nur die endlichen, die abzählbare und die kontinuierliche Kardinalität, alles weitere läuft einem außerhalb der Logik nie als solche übern Weg
Aber selbstverständlich: Wie oft spricht man z.B. von der Menge der einmalig stetig differenzierbaren Funktionen (von IR nach IR)? Diese Menge hat eine größere Kardinalität als die reellen Zahlen.
-
Und wo bitte ist deren Kardinalität von belang¿
Ich habe nicht umsonst das Wort "bewusst" benutzt und trotzdem die (iterierten) Potenzmengen erwähnt...