Abzählbarkeit + Gleichmächtigkeit + Primzahl
-
knivil schrieb:
kannst du anhand des lexikografischen Prinzips entscheiden, welche von beiden die größere ist
Nein, dieses Problem ist nicht entscheidbar, hoechstens berechenbar. Angenommen du hast 2 irrationale Zahlen in Dezimalschreibweise. Nenne einen Algorithmus, der mit "Ja" auf die Frage "Sind diese beiden Zahlen gleich?" antwortet.
Berechenbarkeit ist bei reellen Zahlen so gut wie nie gegeben, das ist klar. Aber die meisten Mathematiker werden trotzdem behaupten, dass es nicht-berechenbare reelle Zahlen gibt, dass diese sehr sinvoll sind, und dass man die vergleichen kann.
Glücklicherweise ist die Mathematik durch den All-Quantor flexibel genug. All-quantifizierte Aussagen sind sehr selten algorithmisch entscheidbar, wenn die Trägermenge unendlich groß ist. Trotzdem kann man Aussagen treffen, in denen der All-Quantor über die natürlichen Zahlen oder mehr geht.
In diesem Fall läuft der All-Quantor über die natürlichen Zahlen: Eine reelle Zahl x ist gleich einer reellen Zahl y (aus dem Intervall [0,1] und in eindeutiger Dezimalbruchdarstellung), wenn für alle i gilt: Die i-te Nachkommastelle von x und y sind gleich.
Die Ordnung kann man ähnlich definieren. Das ist also überhaupt kein Problem.
Was dahinter steckt, ist diese sehr wichtige Eigenschaft der reellen Zahlen:
Für alle x, y gilt genau eines von
1. x < y
2. x > y
3. x = y
aber nicht mehreres gleichzeitig.Diese Eigenschaft garantiert, dass man zwei reelle Zahlen immer vergleichen kann. Ob ein Computer das Ergebnis letztendlich ausrechnen kann, ist eine völlig andere Frage.
Falls du in diese Richtung weitergehst und mit Algorithmen argumentieren möchtest: Die berechenbaren Zahlen bilden eine Teilmenge der reellen Zahlen, die zwar dicht, aber nur *abzählbar* groß ist. Um die Überabzählbarkeit von R zu zeigen, sind diese Betrachtungen also IMHO nicht sehr zielführend.
edit: Schon die berechenbaren Zahlen sind so "kompliziert", dass man nicht entscheiden kann, ob zwei berechenbare Zahlen identisch sind; das ist äquivalent zum Halteproblem. Und das, obwohl es nur abzählbar unendlich viele berechenbare Zahlen gibt.
Dass ein Computer die Gleichheit von zwei Zahlen nicht entscheiden kann, ist also nicht hinreichend dafür, dass die betrachtete Zahlenmenge überabzählbar ist.
knivil schrieb:
Ausserdem, was hast du gegen meine Bijektive Abbildung? Ist sie nicht korrekt um die Abzaehlbarkeit von N* zu zeigen? Ich sage ja nicht sie sei auf R uebertragbar.
Genau das muss man aber beweisen. Du postulierst einfach, dass so eine Durchnummerierung existiert
Beweis durch hinschauen ... Ist genauso wie der Beiweis, das Q abzaehlbar unendlich ist. Details wie genaues aufschreiben etc. habe ich weggelassen.
Ganz so einfach ist das nicht. Wir reden über die Menge der endlichen Folgen von natürlichen Zahlen, oder? Wie definierst du darauf "lexikografische Ordnung"? Ich frage, weil ich lexikografische Ordnung nur für gleich große Tupel bzw. Folgen kenne.
-
Einwender, Der schrieb:
Wer sagt dass f(n) der Nachbar von f(n+1) ist?
Weil das, die einzig sinnvolle Formalisierung davon ist die mir einfällt.
knivil schrieb:
Nein, dieses Problem ist nicht entscheidbar, hoechstens berechenbar. Angenommen du hast 2 irrationale Zahlen in Dezimalschreibweise. Nenne einen Algorithmus, der mit "Ja" auf die Frage "Sind diese beiden Zahlen gleich?" antwortet.
Die Antwort auf die Frage ist wurscht, da es hier um Abzählbarkeit und nicht um effektive Abzählbarkeit geht.
knivil schrieb:
Ok, lexikographisch funktioniert nicht ganz, da das Alphabet unendlich ist.
Na und? R^2 lässt sich wunderbar so total ordnen obwohl R sogar überabzählbar unendlich ist.
Ganz egal wie du jetzt "lexikographisch Ordnung" definierst, am Ende steht eine totale Ordnung da. Diese alleine reicht aber nicht um die Abzählbarkeit zu folgern.
-
Ben04 schrieb:
u_ser-l schrieb:
Die ist als abzählbare Vereinigg abzählbarer Mengen selbst abzählbar.
Wie zeigt man sowas?
ich würde sagen, so:
(1) Die Vereinigung zweier abzählbarer Mengen A={a_1, a_2, ... } und B={b_1, b_2, ...} ist abzählbar:
A u B = {a_1, b_1, a_2, b_2, ..., ... }Für n Mengen klappt es mit Induktion:
- ist die Sache für n-1 abzählbare Mengen bewiesen, dann ist A := A_1 u A_2 u ... u A_n-1 also bereits abzählbar und A u A_n ist abzählbar nach (1) oben.
-
Das war auch mein erster Gedanke, aber das klappt glaube ich nicht so ohne weiteres. Du hast gezeigt, dass die Vereinigung endlich vieler abzählbarer Mengen abzählbar ist. Hier geht es jedoch um eine Vereinigung unendlich vieler Mengen.
-
Dass die abzählbare Vereinigung abzählbarer Mengen wieder abzählbar ist, kann man so zeigen wie die Abzählbarkeit der rationalen Zahlen. Seien also A_n = { a_n1, a_n2, ... } für n=1,2,... jeweils abzählbare Mengen, dann ist die Vereinigung { a_11, a_12, a_21, a_31, a_22, a_13, ... }.
-
Ben04 schrieb:
u_ser-l schrieb:
Die ist als abzählbare Vereinigg abzählbarer Mengen selbst abzählbar.
Wie zeigt man sowas?
Sei a_i_j das j-te Element der i-ten Folge. Dann ist
A_k = { a_i_j | i,j <= k }
eine Folge von endlichen Mengen, in denen jedes Element enthalten ist. Wie man daraus eine Folge der Elemente bastelt, sei dem Leser als Übung überlassen.
-
Ben04 schrieb:
Hier geht es jedoch um eine Vereinigung unendlich vieler Mengen.
hast Recht! ich werde drüber nachdenken
aber nicht mehr heute ...
-
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.