Abenteuer-Universum

Ich versuche mir gerade o.G. zu beweisen und habe meine Schwierigkeiten, auch weil ich die Lehrbuchbeweise irgendwie nicht verstehe. Ein mir verständlicher Beweis sähe zZ so aus:

1. Sei M eine nichtleere Teilmenge von IN. Wenn M n-viele Elemente aus IN enthält, dann gibt es in M auch ein kleinstes Element m (m <= andere Elemente (Zahlen) von M) = Induktionsvoraussetzung.
2. Induktionsannahme: Ist in M ein Element enthalten (n=1), dann ist dieses Element per se das kleinste.
3. Induktionsschritt: Wenn M n-viele Elemente enthält, dann gilbt es in M auch ein kleinstes Element m, dann wiederum gilt auch, dass wenn M n+1-viele Elemente enthält, es in M ein kleinstes Element m' gibt.
4. Wenn (unterstrichene) IV wahr, dann kann mit dem neuen Element n+1 nur gelten: n+1 = m, dann n+1 = m' oder n+1 >= m, dann m = m' oder n+1 <=m, dann n+1 = m'.
5. Da also 3. durch 4. bewiesen, ist die IV für alle natürlichen Zahlen bewiesen.

Wäre so ein Beweis möglich, was würdet ihr davon halten? Wenn da ein Fehler drinsteckt, wie würdet ihr den Beweis erbringen?

Klingt irgendwie kompliziert und ist für mich nicht ganz nachvollziehbar.

Ich würde versuchen, die Wohlordnung der natürlichen Zahlen sowie beliebiger Teilmengen durch einen Widerspruchsbeweis mittels des unendlichen Abstiegs zu zeigen.

Hallo Pippen,

per Konstruktionem über die Peano-Axiome hast Du eine Menge, die bereits ihrem Absolutbetrag nach angeordnet ist. Wenn Du hier eine Teilmengen-Bildung vornimmst, so ist stets das erste Element der Teilmenge deren absolut kleinstes Element.

Was genau ist nun Deine Frage: möchtest Du beweisen, dass das erste Elkement auch das absolut-kleinste Element ist ?

Oder willst Du die natürlichen Zahlen in ihrer Reihenfolge ändern, dann von der in ihrer Reihenfolge geänderten Menge eine Teilmenge bilden und dann das kleinste Element finden ?

Bemerkung: wenn Du zweiteres vorhast, so kannst Du die Änderung der Reihenfolge über eine Bijektion definieren.


Freundliche Grüsse, Ralf

Ich will beweisen, dass jede nichtleere Teilmenge von IN ein kleinstes Element hat. So steht's immer in den LB's. Nur bin ich leider kein Mathematiker und deshalb hänge ich immer mal dort mal da beim Verständnis und gerade bei diesem ja eigentlich leichten Beweis verstehe ich die klass. LB-Beweise via Induktion nicht so richtig und habe mir daher "meinen "Beweis gebastelt. Wie würdet ihr das beweisen? Oder alternativ: was ist in meinem obigen Beweis nicht nachvollziehbar?

Ich denke, ein Widerspruchsbeweis ist weniger überzeugend als ein konstruktiver.

Sei M = {x: A(x)} eine nicht-leere Untermenge der natürlichen Zahlen N und z ein beliebiges Element aus M.
Sei N(z) die endliche Menge {x: x = k, k-1, ..., 0} sowie M(z) die Untermenge {x: x = k, k-1, ..., 0 UND A(x)}.
Da z endlich viele Vorgänger hat ist N(z) in endlich vielen Schritten konstruierbar. Damit ist auch M(z) in endlich vielen Schritten konstruierbar.
Das erste Element von M(z) ist gerade das minimale Element von M.

Es gibt m.E. ein Schlupfloch in diesen Beweis, nämlich wenn A(x) für kein x in endlich vielen Schritten berechenbar ist. Damit fehlt ggf. die Möglichkeit, überhaupt mit irgendeinem z aus M zu starten, und es fehlt die Möglichkeit, M(z) absteigend von z aus zu konstruieren.

Dafür würde evtl. doch ein nicht-konstruktiver Widerspruchsbeweis benötigt.

Pippen hat geschrieben: ↑

12. Sep 2017, 19:36

Wie würdet ihr das beweisen? Oder alternativ: was ist in meinem obigen Beweis nicht nachvollziehbar?

Hallo Pippen,

solange ich Deine Frage nicht verstanden habe beweise ich gar nichts.

Noch einmal: die natürlichen Zahlen sind nach ihrer Konstruktion per definitinen der Grösse nach angeordnet. Dafür benötigen wir keine vollständige Induktion, das folgt direkt aus der Konstruktion.

Ist das für Deine nicht-leere Teilmenge auch der Fall, d.h. ist diese ebenfalls der Grösse nach angeordnet, oder schüttelst Du die natürlichen Zahlen vor der Teilmengen-Bildung noch gründlich durch, so dass die Teilmenge nicht mehr der Grösse nach angeordnet ist ?


Oder anders formuliert: willst Du beweisen, dass bei einer der Grösse nach angeordneten Menge, bei der somit das erste Element das kleinste ist, auch nach der Teilmengen-Bildung das erste Element das kleinste Element ist ?

Oder willst Du darauf hinaus, dass ich die Umkehrabbildung einer Bijektion betrachte, welche die durcheinander-geschüttelte Menge wieder in ihre ursprüngliche, d.h. der Grösse nach angeordnete, Menge überführt ?

Oder meinst Du noch etwas anderes ?


Freundliche Grüsse, Ralf

Es gibt einen ganz einfachen Beweis, der jedoch als voraussetzung hat, dass alle oder mindestens eines der in der Teilmenge enthaltenen Elemente endlich sind.
Man wählt ein beliebiges Element x0 aus M, x0 sei endlich.
Abstand zum ersten Element aus N ist d = x0 - 1.
Man kann in endliche vielen Schritten prüfen, ob x0 kleinstes Element der Teilmenge ist.
Entweder es ist kleinstes Element, oder ein anderes Element ist kleinstes Element.

Voraussetzung ist, dass die Menge einen endlichen Abstand zur '1' hat, was man aber voraussetzen kann, da bei der Konstruktion der ganzen Zahlen, nur Elemente erfasst werden, welche auch durch eine endliche Aneinanderreihung an Additionen von '1' konstruier- als auch erreichbar sind.
Wenn man jetzt die Leute dazu nimmt, die 'aktual unendliches' als existent behaupten, sieht das ganze schonmal anders aus.

Zum Widerspruchsbeweis mittels unendlichem Abstieg.

Sei M eine nicht-leere Untermenge der natürlichen Zahlen N.
Annahme ist, das M kein kleinstes Element hat.
Sei z ein beliebiges Element aus M. Gemäß Annahme existiert dann mindestens ein kleineres zᵃ = z-a mit a>0, das wiederum Element aus M sein muss, andernfalls wäre z das kleinste Element, entgegen der Annahme. Für dieses zᵃ gilt dasselbe, d.h. es existiert mindestens ein kleineres zᵇ= zᵃ-b = z-(a+b) mit b>0, das wiederum Element aus M sein muss.
Diese Argumentation kann beliebig fortgesetzt werden.
Damit führt die Annahme, dass kein kleinsten Element existiert, zu einem Widerspruch mittels unendlichem Abstieg:
Einerseits wächst (a+b+c+…) über alle Grenzen, d.h. es folgt insbs. (a+b+c+…) > z.
Andererseits ist z⁰ = z-z = 0 die kleinste Zahl, die man ausgehend von z innerhalb der natürlichen Zahlen erreichen kann, d.h. die Bildung (a+b+c+…) muss spätestens bei diesem endlichem z terminieren.

Hier übrigens ein Link zum "Standardbeweis", den ich nach einiger Mühe auch verstehe: https://www3.mathematik.tu-darmstadt.de ... sung02.pdf

Warum aber nicht so wie unten, das wäre doch viel kürzer und besser, oder?

Ich halte den Beweisansatz mit vollständiger Induktion für zu kompliziert. Ich überlege mir aber gerne mal, wie man das verkürzen kann.

Pippen hat geschrieben: ↑

13. Sep 2017, 14:14

Warum aber nicht so wie unten, das wäre doch viel kürzer und besser, oder?

Hallo Pippen,

da steht ganz zu Beginn ein Hinweis, auf dem ich auch schon die ganze Zeit herumreite: Formulieren Sie vorher exakt, welche Aussage Sie beweisen wollen.

Das hast Du bislang immer noch nicht geschrieben. Zwar habe ich zwei Rateversuche unternommen, bin aber nicht sicher, ob das wirklich das ist, was Du beweisen willst.


Freundliche Grüsse, Ralf

tomS hat geschrieben: ↑

13. Sep 2017, 15:33

Ich halte den Beweisansatz mit vollständiger Induktion für zu kompliziert.

Hallo Tom,

vielleicht. Er ist aber sehr hübsch


Freundliche Grüsse, Ralf

Kurzer Ausflug:

Behauptung: Alle natürlichen Zahlen sind interessant!
Definition: Eine Zahl ohne jegliche besondere Eigenschaft ist eine uninteressante Zahl, alle anderen Zahlen sind interessante Zahlen.

Beweis:

Der kurze und klassisch anmutende Widerspruchsbeweis nutzt die Wohlordnung der natürlichen Zahlen, die besagt, dass jede nichtleere Teilmenge der natürlichen Zahlen eine kleinste Zahl enthält.

Angenommen, es gibt eine nichtleere Menge von uninteressanten natürlichen Zahlen. Dann gibt es wegen der Wohlordnung der natürlichen Zahlen auch eine kleinste uninteressante natürliche Zahl. Diese kleinste uninteressante natürliche Zahl ist aber gerade durch ihre Minimalitätseigenschaft gegenüber allen anderen uninteressanten Zahlen besonders ausgezeichnet und ist daher gerade keine uninteressante natürliche Zahl. Dies steht aber im Widerspruch zu unserer Annahme, dass es sich um eine uninteressante natürliche Zahl handelt. Somit ist unsere Annahme der Existenz uninteressanter natürlicher Zahlen falsch, es gibt ausschließlich interessante natürliche Zahlen.

https://de.wikipedia.org/wiki/Interessa ... -Paradoxon

Sorry, das konnte ich mir nicht verkneifen...

Der Beweis ist natürlich unabhängig davon, ob das kleinste Element der Teilmenge in der Praxis determiniert werden kann oder nicht.

Skeltek hat geschrieben: ↑

14. Sep 2017, 11:17

Der Beweis ist natürlich unabhängig davon, ob das kleinste Element der Teilmenge in der Praxis determiniert werden kann oder nicht.

Das kommt auf den konkreten Beweis an.

Ich habe oben einen konstruktiven Beweis angegeben, für den das nicht gilt.