Bijektion Natürliche zahlen -> Primzahlen
-
xroads42 schrieb:
Ich verstehe nicht ganz wie du von der abzählbarkeit und der unendlichkeit der natürlichen zahlen, für die teilmenge der Primzahlen das auch sagen kannst?
unendlich ist klar.
Aber abzählbar?? Da will ich einen beweiß für.
Jede Teilmenge einer abzaehlbaren Menge ist wieder abzaehlbar. Reicht das?
-
Tobias Neukom GAST schrieb:
Kann mir jemand aufzeigen wie man eine Funktion, die jeder natürlichen Zahl eine Primzahl zuordnet, konstruieren kann?
Ordne einfach alle Primzahlen der Größe nach. Dann hast du 2 = p(1) < p(2) < p(3) < ... . Und genau das ist eine der gesuchten Bijektionen.
-
SG1 schrieb:
xroads42 schrieb:
Ich verstehe nicht ganz wie du von der abzählbarkeit und der unendlichkeit der natürlichen zahlen, für die teilmenge der Primzahlen das auch sagen kannst?
unendlich ist klar.
Aber abzählbar?? Da will ich einen beweiß für.
Jede Teilmenge einer abzaehlbaren Menge ist wieder abzaehlbar. Reicht das?
Jo, das du dich auf diese aussage stüzt ist mir schon klar. Aber hat du einen beweiß dafür? (link reicht)
-
Das habe ich doch gerade oben aufgezeigt: Sei . Dann kannst du wieder die Elemente von M der Größe nach ordnen, so dass jede Zahl einen Nachfolger und jede Zahl (bis auf genau eine) einen Vorgänger hat. Das folgt aus den Peano-Axiomen. Wir können die Elemente von M also numerieren: m\_1, m\_2, m_3, \dots. Fertig!
-
volkard schrieb:
SG1 schrieb:
volkard schrieb:
ob es reicht, zu wissen, daß es keine größte primzahl gibt?
Ja, reicht.
supi. dann nehmen wir mal an, es gäbe nur endlich viele primzahlen, plutimizieren die und zählen zum produkt eins dazu. es kommt ne zahl raus, die, egal durch welche primzahl man sie teilt, als divisionsrest ne eins hat. also ist sie ne primzahl, was der annahme widerspricht.
Nicht ganz, es muss keine Primzahl sein.
Sie kann auch nicht-Prim sein, dafür aber Primfaktoren haben die dann alle größer sind als die endlich vielen Primzahlen aus der Annahme.
Muss im Beweis auf jeden Fall erwähnt werden
Zum Thema:
Ein Monster, 1964 von C.P Williams veröffentlich (soweit ich weiss):p\_n=1+\sum\_{m=1}^{2^n}\lfloor \sqrt[n]n \cdot ( \sum_{x=1}^m \lfloor \cos^2( \pi \cdot \frac{ (x-1)!+1}{x})\rfloor )^{-\frac{1}{n}} \rfloor
Alternativ kann man eine Primzahl-Funktion mit Primitiver Rekursion darstellen. Ist aber eher für Informatiker interessant.
Gruß, space
-
space schrieb:
volkard schrieb:
supi. dann nehmen wir mal an, es gäbe nur endlich viele primzahlen, plutimizieren die und zählen zum produkt eins dazu. es kommt ne zahl raus, die, egal durch welche primzahl man sie teilt, als divisionsrest ne eins hat. also ist sie ne primzahl, was der annahme widerspricht.
Nicht ganz, es muss keine Primzahl sein.
Doch, die Zahl laesst (nach Konstruktion!) beim Teilen durch jede Primzahl einen Rest von 1, ist also selber eine Primzahl.
-
hi
@ volkard
war da sowas gemeint? 2*3*5*7*11*13 + 1 = 30031?
30031 = 59 * 509
somit ist die aussage eindeutig wiederlegt.
durch die producktbildung der ersten n primzahlen und der adition einer 1 erhälst du eine zahl die durch die division der ersten n primzahlen einen rest von 1 ergibt. über die restlichen primzahlen die zwischen sqr() und der grössten verwendeten primzahl liegen machst du keine aussage.und
2*3*5*7*11*13*17 + 1 = 510511 = 97 * 5263
gruss Termite
-
termite_ schrieb:
2*3*5*7*11*13 + 1 = 30031?
30031 = 59 * 509
somit ist die aussage eindeutig wiederlegt.es war gar nicht die aussage, daß man aus aus den ersten n primzahlen so eine n+1-te primzahl bauen kann.
es war die aussage, daß man aus den einzigen n primzahlen eine n+1-te bauen kann. sie ist nur innerhalb des absurd-beweises lebendig. nur, wenn es n primzahlen gibt und keine einzige mehr, dann kann ich zeigen, daß es doch eine mehr gibt.
-
SG1 schrieb:
space schrieb:
volkard schrieb:
supi. dann nehmen wir mal an, es gäbe nur endlich viele primzahlen, plutimizieren die und zählen zum produkt eins dazu. es kommt ne zahl raus, die, egal durch welche primzahl man sie teilt, als divisionsrest ne eins hat. also ist sie ne primzahl, was der annahme widerspricht.
Nicht ganz, es muss keine Primzahl sein.
Doch, die Zahl laesst (nach Konstruktion!) beim Teilen durch jede Primzahl einen Rest von 1, ist also selber eine Primzahl.
NEIN !
Sie lässt beim Teilen durch jede der endlich vielen Primzahlen aus der Annahme den Rest 1. Aber sie selbst muss deshalb noch lange keine Primzahl sein.
Man kann aber argumentieren, dass ihre Primfaktoren alle größer als die endlich vielen aus der Annahme sind.Alles schonmal oben geschrieben.
-
Und wers immer noch nicht glaubt:
2*3*5*7*11*13 + 1 = 30031 = 59*509 ist keine Primzahl !
-
space_ schrieb:
Und wers immer noch nicht glaubt:
2*3*5*7*11*13 + 1 = 30031 = 59*509 ist keine Primzahl !
Das hat auch keine bezweifelt.
-
space_ schrieb:
SG1 schrieb:
space schrieb:
volkard schrieb:
supi. dann nehmen wir mal an, es gäbe nur endlich viele primzahlen, plutimizieren die und zählen zum produkt eins dazu. es kommt ne zahl raus, die, egal durch welche primzahl man sie teilt, als divisionsrest ne eins hat. also ist sie ne primzahl, was der annahme widerspricht.
Nicht ganz, es muss keine Primzahl sein.
Doch, die Zahl laesst (nach Konstruktion!) beim Teilen durch jede Primzahl einen Rest von 1, ist also selber eine Primzahl.
NEIN !
Sie lässt beim Teilen durch jede der endlich vielen Primzahlen aus der Annahme den Rest 1.Die Annahme ist, dass es keine weiteren Primzahlen gibt, also ist der Schluss richtig.
-
Langsam wirds blöd.
Lies richtig oder lass es.
-
space_ schrieb:
Langsam wirds blöd.
Lies richtig oder lass es.
Langsam wirds blöd.
Lies richtig oder lass es.
-
SG1 schrieb:
Die Annahme ist, dass es keine weiteren Primzahlen gibt, also ist der Schluss richtig.
Welcher Schluss? Dass die neue Zahl ne Primzahl ist? Nein, der ist falsch! Denn wie du ja auch sagst: Es gibt nur n Primzahlen. Also kann p1 * ... * pn + 1 keine Primzahl sein. Allerdings haben wir im Beweis zugrunde gelegt, dass jede natürliche Zahl in Primfaktoren zerlegbar ist. Und das ist unsere neue Zahl eben nicht. Also haben wir die Annahme ad absurdum geführt.
-
space schrieb:
Zum Thema:
Ein Monster, 1964 von C.P Williams veröffentlich (soweit ich weiss):p\_n=1+\sum\_{m=1}^{2^n}\lfloor \sqrt[n]n \cdot ( \sum_{x=1}^m \lfloor \cos^2( \pi \cdot \frac{ (x-1)!+1}{x})\rfloor )^{-\frac{1}{n}} \rfloor
Quellen?
-
WebFritzi schrieb:
SG1 schrieb:
Die Annahme ist, dass es keine weiteren Primzahlen gibt, also ist der Schluss richtig.
Welcher Schluss? Dass die neue Zahl ne Primzahl ist? Nein, der ist falsch!
Ich haette vielleicht gueltig schreiben sollen. Dass das ein Widerspruch ist, ist ja der ganze Witz des Beweis.
-
SG1 schrieb:
WebFritzi schrieb:
SG1 schrieb:
Die Annahme ist, dass es keine weiteren Primzahlen gibt, also ist der Schluss richtig.
Welcher Schluss? Dass die neue Zahl ne Primzahl ist? Nein, der ist falsch!
Ich haette vielleicht gueltig schreiben sollen. Dass das ein Widerspruch ist, ist ja der ganze Witz des Beweis.
gueltig? Was ist gültig? Und wo ist der Widerspruch?
-
WebFritzi schrieb:
gueltig? Was ist gültig?
Argh. Kommando zurueck. Ich meinte doch korrekt. Und zwar nicht im Sinne "korrekte Aussage", sondern im Sinne "korrekter Schluss".
Es geht um den Schluss:
\Forall{p \in PRIM} p | (n - 1) \Longrightarrow n \in PRIM
Und der fuer sich allein ist korrekt.Und wo ist der Widerspruch?
Dass eben auch gilt:
-
Nein, dieser Schluß ist nicht korrekt. Die Zahl, die als das Produkt der Primzahlen p1,...,pn sowie 1 aufaddiert muß nicht zwangsläufig prim sein, aber sie ist entweder prim oder hat einen bis dato unbekannten Primteiler.
Zur Demonstration bediene ich mich jetzt einfach mal bei space_:
Diese hypotetische endliche Liste an Primzahlen wähle ich mal ganz konkret:
2,3,5,7,11,13 Der Beweis geht ja für eine beliebige endliche Liste, also muß er insbesondere auch für diese funktionieren.
Deine Aussage ist sodann: 2*3*5*7*11*13+1 ist prim.
Und genau das stimmt nicht, wie space_ oben gezeigt hat. Also ist der Beweis so falsch. Korrekt ist aber, daß bis dato unbekannte Primzahlen drinstecken, sodaß der Widerspruch erfolgreich hergeleitet ist.MfG Jester