Bijektion Natürliche zahlen -> Primzahlen
-
Hallo
Kann mir jemand aufzeigen wie man eine Funktion, die jeder natürlichen Zahl eine Primzahl zuordnet, konstruieren kann? Wie stellt man diese funktion in der Mengenlehre dar? Das Prinzip n -> n. Primzahl ist mir schon klar.
Gruss Tobias
-
denke nicht, daß man die funktion konstruieren kann.
aber man kann bestimmt zeigen, daß es sie gibt. ob es reicht, zu wissen, daß es keine größte primzahl gibt?
-
volkard schrieb:
ob es reicht, zu wissen, daß es keine größte primzahl gibt?
Ja, reicht. Daraus folgt naemlich, dass es unendlich viele Primzahlen gibt. Da die Primzahlen eine Teilmenge der natuerlichen Zahlen bilden, gibt es also abzaehlbar unendlich viele Primzahlen. Somit existiert (nach Definition von abzaehlbar unendlich) eine Bijektion zwischen den natuerlichen Zahlen und den Primzahlen.
-
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.
-
SG1 schrieb:
Ja, reicht. Daraus folgt naemlich, dass es unendlich viele Primzahlen gibt. Da die Primzahlen eine Teilmenge der natuerlichen Zahlen bilden, gibt es also abzaehlbar unendlich viele Primzahlen. Somit existiert (nach Definition von abzaehlbar unendlich) eine Bijektion zwischen den natuerlichen Zahlen und den Primzahlen.
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.
-
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.