Abzählbarkeit + Gleichmächtigkeit + Primzahl
-
Ben04 schrieb:
u_ser-l schrieb:
Die ist als abzählbare Vereinigg abzählbarer Mengen selbst abzählbar.
Wie zeigt man sowas?
Du gibst ne surjektive Abbildung von NxN in Deine Menge an. Dabei benutzt Du den ersten Index um die Mengen abzuzählen und den zweiten für die Elemente.
Wenn Du das ganze noch mit einer surjektiven Funktion N-->NxN zusammensteckst hast Du Deine Abzählung.
-
Ben04 schrieb:
u_ser-l schrieb:
Die ist als abzählbare Vereinigg abzählbarer Mengen selbst abzählbar.
Wie zeigt man sowas?
Wenn N* einfach nur die Menge aller endlichen Folgen aus natuerlichen Zahlen ist, so kann man die Menge "lexikographisch" ordnen und von oben anfangen duchzunummerieren.
-
Jester schrieb:
Ben04 schrieb:
u_ser-l schrieb:
Die ist als abzählbare Vereinigg abzählbarer Mengen selbst abzählbar.
Wie zeigt man sowas?
Du gibst ne surjektive Abbildung von NxN in Deine Menge an. Dabei benutzt Du den ersten Index um die Mengen abzuzählen und den zweiten für die Elemente.
Wenn Du das ganze noch mit einer surjektiven Funktion N-->NxN zusammensteckst hast Du Deine Abzählung.
Danke, das klappt
knivil schrieb:
Ben04 schrieb:
u_ser-l schrieb:
Die ist als abzählbare Vereinigg abzählbarer Mengen selbst abzählbar.
Wie zeigt man sowas?
Wenn N* einfach nur die Menge aller endlichen Folgen aus natuerlichen Zahlen ist, so kann man die Menge "lexikographisch" ordnen und von oben anfangen duchzunummerieren.
Ist mit dieser Argumentation nicht auch R abzählbar? R ist auch total geordnet und dennoch kann ich die Elemente nicht durchnummerieren. Auch die Existenz eines "Startelements" also eines Minimums reicht nicht, siehe R+.
-
Ist mit dieser Argumentation nicht auch R abzählbar?
Nein. Ich beziehe mich nur auf endliche Zahlenreihen. R enthaelt viele unendliche nicht-periodische Zahlenreihen, N* hat keine einzige. In N* gibt es ... sagen wir mal ... Nachbarn, zwischen denen kein weiteres Element liegt. In R gibt es solche Nachbarn nicht. Die totale Ordnung ist nicht mein einziges Argument, sondern auch, dass ich N* lexikographisch ordnen kann (nicht mit der Ordnung im Lexikon verwechseln). R kann ich nicht so ordnen (da nicht jedes Element endlich ist). Ausserdem benoetigt man eine bijektive Abbildung zwischen den Mengen, um Gleichmaechtigkeit zu zeigen. Surjektivitaet allein reicht nicht. Die angegebene ist eine.
-
knivil schrieb:
Ist mit dieser Argumentation nicht auch R abzählbar?
Nein. Ich beziehe mich nur auf endliche Zahlenreihen. R enthaelt viele unendliche nicht-periodische Zahlenreihen, N* hat keine einzige.
Das ist mir klar, aber das hast du in deiner Argumentation nicht verwendet.
knivil schrieb:
In N* gibt es ... sagen wir mal ... Nachbarn, zwischen denen kein weiteres Element liegt.
Sei f eine Bijektion N -> N* dann sind f(n) und f(n+1) deine Nachbarn. Die Existenz von f nennt man Abzählbarkeit von N*. Um die Abzählbarkeit von N* zu zeigen verwendest du, dass es die Nachbarn gibt, also verwendest du die Abzählbarkeit um die Abzählbarkeit zu zeigen.
-
Ben04 schrieb:
knivil schrieb:
Ist mit dieser Argumentation nicht auch R abzählbar?
Nein. Ich beziehe mich nur auf endliche Zahlenreihen. R enthaelt viele unendliche nicht-periodische Zahlenreihen, N* hat keine einzige.
Das ist mir klar, aber das hast du in deiner Argumentation nicht verwendet.
knivil schrieb:
In N* gibt es ... sagen wir mal ... Nachbarn, zwischen denen kein weiteres Element liegt.
Sei f eine Bijektion N -> N* dann sind f(n) und f(n+1) deine Nachbarn. Die Existenz von f nennt man Abzählbarkeit von N*. Um die Abzählbarkeit von N* zu zeigen verwendest du, dass es die Nachbarn gibt, also verwendest du die Abzählbarkeit um die Abzählbarkeit zu zeigen.
Wer sagt dass f(n) der Nachbar von f(n+1) ist?
-
Die wohl beste Abzählung von IN* (als die endlichen Teilmengen von IN) ist wohl A -> sum_{a \in A} 2^a.
-
Ben04 schrieb:
Das ist mir klar, aber das hast du in deiner Argumentation nicht verwendet.
Doch!
knivil schrieb:
Menge aller endlichen Folgen aus natuerlichen Zahlen
Ben04 schrieb:
Um die Abzählbarkeit von N* zu zeigen verwendest du, dass es die Nachbarn gibt
Nein! Ich verwende die lexikographische Ordnung endlicher Zahlenfolgen. Das mit den Nachbarn war nur ein Beispiel, warum die gleiche Argumentation bei reellen Zahlen Probleme bereitet.
wohl beste Abzählung ...
Ansichtsache, ich finde meine Abzaehlung viel besser
ganz ohne Rechnen.
-
knivil schrieb:
Ist mit dieser Argumentation nicht auch R abzählbar?
Nein. Ich beziehe mich nur auf endliche Zahlenreihen. R enthaelt viele unendliche nicht-periodische Zahlenreihen, N* hat keine einzige. In N* gibt es ... sagen wir mal ... Nachbarn, zwischen denen kein weiteres Element liegt. In R gibt es solche Nachbarn nicht.
Zwischen zwei beliebigen unterschiedlichen rationalen Zahlen liegt auch immer eine weitere.
knivil schrieb:
Die totale Ordnung ist nicht mein einziges Argument, sondern auch, dass ich N* lexikographisch ordnen kann (nicht mit der Ordnung im Lexikon verwechseln). R kann ich nicht so ordnen (da nicht jedes Element endlich ist).
R ist lexikografisch geordnet, zumindest für die auf unendliche Folgen verallgemeinerte Definition von "lexikografisch".
Wenn du zwei reelle Zahlen (sagen wir, aus dem Intervall [0,1]) als unendlichen Dezimalbruch aufschreibst (*), kannst du anhand des lexikografischen Prinzips entscheiden, welche von beiden die größere ist: Nämlich genau die, die möglichst weit links eine größere Ziffer besitzt als die andere Zahl.
Dass die Ziffernfolgen unendlich lang sind, stört dabei nicht. Wenn sich zwei relle Zahlen unterscheiden, müssen sie sich schon an einer endlichen Nachkommastelle unterscheiden; damit kannst du die Zahlen dann ordnen.
(*) Mehrdeutigkeiten wie 0,999... = 1,000... ausgeschlossen.
-
knivil schrieb:
Ben04 schrieb:
u_ser-l schrieb:
Die ist als abzählbare Vereinigg abzählbarer Mengen selbst abzählbar.
Wie zeigt man sowas?
Wenn N* einfach nur die Menge aller endlichen Folgen aus natuerlichen Zahlen ist, so kann man die Menge "lexikographisch" ordnen und von oben anfangen duchzunummerieren.
Genau das muss man aber beweisen. Du postulierst einfach, dass so eine Durchnummerierung existiert.
-
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.
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
Ok, lexikographisch funktioniert nicht ganz, da das Alphabet unendlich ist. Als weiteres Sortierkriterium kann noch die Summe der Zahlen in der Folge herangezogen werden. Ich sortiere also erst nach der Summe der einzelnen Folgen und dann "alphabetisch". Hey, klar kann jemand sagen, was ist mit Folgen, die nur Nullen enthalten, aber die Laenge der Zahlenfolgen ist einfach nur ein weiteres Ordnungskriterium. Der Rest ist wie beim Beweis, dass Q abzaehlbar unendlich ist, einfach durch Hingucken ... Details kann sich jeder selber aufschreiben. Ausserdem brauch ich nicht zu Postulieren, dass diese Durchnumerierung existiert, sondern nur dass ich nach und nach mit dieser Ordnung alle Zahlenfolgen "einsammle". Das ist aber der Fall. (Fuer den Beweis - Widerspruchsbeweis bin ich jetzt aber zu faul. Wer ein Gegenbeispiel findet, sagt mal bescheid).
-
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.