Bijektion Natürliche zahlen -> Primzahlen

[WebFritzi]

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?

[SG1]

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:
$n \notin PRIM$

[Jester]

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

[SG1]

Jester schrieb:

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.

Die Voraussetzung ist, dass es keinen solchen gibt.

[volkard]

lerne a: (fundamentalsatz der zahlentheorie) eine zahl ist entweder eine primzahl oder läßt sich als produkt von primzahlen darstellen.
lerne b: (aus a) eine zahl, die sich nicht als produkt von primzahlen darstellen läßt, ist eine primzahl.
lerne c: (annahme) alle primzahlen sind: 2,3,5,7,11,13. es gibt keine weitere.
lerne d: (rechnen) 2*3*5*7*1113+1 läßt sich nicht durch 2,3,5,7,11 oder 13 teilen.
lerne e: (c+d) 2*3*5*7*1113+1 läßt sich durch keine primzahl teilen.

und hier steht es. durch keine primzahl. eure anmerkungen, es gäbe weitere primzahlen sind hier nicht notwendig, da aussage c ist noch im speicher und die weiteren inexistent wären. es ist falsch, hier die anmerkung zu fordern, wennauch die anmerkung selbst unschädlich ist.

lerne f: (e) 2*3*5*7*1113+1 läßt sich nicht als produkt von primzahlen darstellen.
lerne g: (e+b) 2*3*5*7*1113+1 ist eine primzahl.
lerne h: (rechnen) 2*3*5*7*1113+1 ist nicht in der menge {2,3,5,7,11,13} enthalten.
lerne i: (h+c) 2*3*5*7*1113+1 ist keine primzahl.

jetzt liegt ein widerspruch offen zwischen i und g.

Jester schrieb:

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.

hier machste IMHO den fehler, plötzlich die theorie zu wechseln. wird die theorie in der mir angegebenen reihenfolge aufgebaut, stimmt die zwischenaussage "2*3*5*7*11*13+1 ist prim" erstmal (und führt bald zum widerspruch).

es steht dir natürlich frei, in einer anderen reihenfolge vorzugehen.

dir mag es eher liegen, die aussage c möglichst lange zurückzuhalten.

lerne a: (fundamentalsatz der zahlentheorie) eine zahl ist entweder eine primzahl oder läßt sich als produkt von primzahlen darstellen.
//evtl einige zwischenschritte
lerne b: (aus a) das um ein vermehrte produkt von primzahlen ist prim oder enthält eine nicht im produkt enthaltene primzahl.

jo, b ist wohl korrekt. es war ja auch nicht das um ein vermehrte produkt *aller* primzahlen.

lerne c: (annahme) alle primzahlen sind: 2,3,5,7,11,13. es gibt keine weitere.
lerne d: (b+c) 2*3*5*7*1113+1 ist prim oder enthält eine bisher unbekannte primzahl.
lerne e: (rechnen) 2*3*5*7*1113+1 ist nicht in der menge {2,3,5,7,11,13} enthalten.
lerne f: (h+c) 2*3*5*7*1113+1 ist keine primzahl.
lerne g: (f+d) 2*3*5*7*1113+1 enthält eine bisher unbekannte primzahl namens p.
lerne h: (g) p ist eine primzahl.
lerne i: (g) p ist nicht in {2,3,5,7,11,13}
lerne j: (i+c) p ist keine primzahl.

widerspruch uwischen j und h.

[WebFritzi]

OK, der Schluss ist schon richtig, aber ein wenig zu schnell vollzogen worden. Dabei muss man sich nochmal klar machen, was eine Primzahl ist. Eine Primzahl ist eine Zahl, die nur durch 1 und sich selbst teilbar ist. Dabei ist die 1 ausgenommen.

Annahme: Es gibt nur endlich viele Primzahlen p\_1,\dots,p\_n. So, und dann definiere q := p\_1\cdot\dots\cdot p\_n + 1. Diese Zahl ist durch keine andere Zahl teilbar als durch 1 und sich selbst, da sie durch keine der Primzahlen $p_i$ teilbar ist. Und es kann auch nicht die 1 sein, denn dann wäre $p_i = 0$ für ein i\in\{1,\dots,n\}. Also ist q eine Primzahl. q ist aber größer als alle $p_i$. So, und nun haben wir den Widerspruch.

[Jester]

@volkard: Hast Du für a) einen schönen Beweis, der nicht die Existenz unendlich vieler Primzahlen benötigt?

MfG Jester

[WebFritzi]

@Jester: Das lässt sich doch ganz einfach zeigen. Sogar mit vollständiger Induktion.

Behauptung: Jede natürliche Zahl n > 1 ist entweder eine Primzahl oder lässt sich als Produkt von Primzahlen darstellen.

Beweis: Fangen wir bei n=2 an. 2 ist ne Primzahl. Fertig! Nun sei die Behauptung für ein n-1 (und alle Zahlen kleiner als n-1) wahr. Wir betrachten n. Ist n eine Primzahl, so gibt es nichts mehr zu zeigen. Ist n keine Primzahl, dann gibt es Zahlen p und q, so dass n = p * q und p,q≠n. p und q sind kleiner als n, also ist die Induktionsvoraussetzung anwendbar, und wir erhalten die Behauptung für n.

[Bashar]

AFAIK ist der Fundamentalsatz der Zahlentheorie die Eindeutigkeit der Primfaktorzerlegung, nicht nur die bloße Möglichkeit. Ist hier aber auch egal, weil volkard die Eindeutigkeit nicht benutzt hat.

[volkard]

Bashar schrieb:

AFAIK ist der Fundamentalsatz der Zahlentheorie die Eindeutigkeit der Primfaktorzerlegung, nicht nur die bloße Möglichkeit. Ist hier aber auch egal, weil volkard die Eindeutigkeit nicht benutzt hat.

ups, stimmt.
hab auch keinen beweis dafür.