Abzählbarkeit + Gleichmächtigkeit + Primzahl
-
TI'er schrieb:
Hallo,
hab mal 3 kleinere Fragen:- Ich soll zeigen, dass N und das kartesische Produkt N x N gleich mächtig sind. Und dann noch, ob N und N* auch gleich mächtig sind.
zum beispiel NxN in ne tebelle eintragen und schräg abzählen
TI'er schrieb:
- Ich soll zeigen, dass die Menge R der reellen Zahlen nicht(!) abzählbar ist.
digonalbeweis
TI'er schrieb:
- Es ist ein Algorithmus gegeben, der eine beliebige natürliche Zahl n auf Primzahl prüft, wobei er aber nur durch 2 und 3 Teilbarkeit prüft. Wenn also die Zahl n durch 2 oder 3 teilbar ist, dann ist keine Primzahl, ansonsten ist es eine. Wie bekomme ich jetzt raus wie groß die Fehlerwahrscheinlichkeit des Algorithmus' ist?
http://de.wikipedia.org/wiki/Primzahlsatz
for große n sagt der algo, po(x)=2/6*x
richtige wären pi(x)
fehleranzahl: po(x)-pi(x)
kann man
lim fpr x->inf von (po(x)-pi(x))/x
errechnen?
-
-
TI'er schrieb:
Und dann noch, ob N und N* auch gleich mächtig sind.
nee, ist nicht, weil N* gleichmächtig mit der Menge der reellen Zahlen ist (Beweis: jede reelle Zahl läßt sich als endlicher oder unendlicher Dezimalbruch schreiben, weil die rationalen Zahlen dicht in den reellen Zahlen liegen)
-
u_ser-l schrieb:
TI'er schrieb:
Und dann noch, ob N und N* auch gleich mächtig sind.
nee, ist nicht, weil N* gleichmächtig mit der Menge der reellen Zahlen ist (Beweis: jede reelle Zahl läßt sich als endlicher oder unendlicher Dezimalbruch schreiben, weil die rationalen Zahlen dicht in den reellen Zahlen liegen)
dein N* isz nicht das von http://de.wikipedia.org/wiki/Natürliche_Zahl
welches hast du?
-
ich meine mit N* alle Folgen über N; mit N* = N-{0} wäre die Aufgabe ja nun arg schlicht. Aber vielleicht hast Du recht und er meint N-{0}.
-
u_ser-l schrieb:
ich meine mit N* alle Folgen über N
vielleicht hast du recht.
muss der threadersteller entscheiden, was der prof meinte.u_ser-l schrieb:
mit N* = N-{0} wäre die Aufgabe ja nun arg schlicht
jup. die einfachheit hat mich erschreckt. ich zittere noch am ganzen körper.
-
u_ser-l schrieb:
ich meine mit N* alle Folgen über N; mit N* = N-{0} wäre die Aufgabe ja nun arg schlicht. Aber vielleicht hast Du recht und er meint N-{0}.
Mit N* können auch alle endlichen Tupel mit natürlichen Zahlen gemeint sein. In dem Fall glaube ich stimmt die Behauptung.
N* als Menger aller Folgen kenne ich nicht. Das ist N^N.
-
in der Tat, am plausibelsten wirkt N* = Menge aller endlichen Folgen über N. Die ist als abzählbare Vereinigg abzählbarer Mengen selbst abzählbar.
-
u_ser-l schrieb:
Die ist als abzählbare Vereinigg abzählbarer Mengen selbst abzählbar.
Wie zeigt man sowas?
-
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).