Hinweis auf die DSGVO: Auf unserer Seite werden keine Dritt-Anbieter-Cookies verwendet und nur Daten erfasst, welche für das Minimum an Board-Funktionalität notwendig sind.
Bevor Sie sich registrieren oder das Board verwenden, lesen Sie bitte zusätzlich die DSGVO-Erklärung, welche in der Navigationsleiste verlinkt ist.

Kurzfassung der unserer Meinung nach wichtigsten DSGVO-Punkte:
Es kann vorkommen, dass Benutzer eigenverantwortlich Videos oder sonstige Medien in ihren Beiträgen verlinken, welche beim Aufruf der Forenseite als Teil der Seite samt zugehörigem Material mitgeladen werden. Sollten Sie dies nicht wünschen, verwenden Sie beim Benutzen des Forums einen Blocker wie z.B. uMatrix, welcher das Laden von Inhaltsblöcken von Fremd-URLs effektiv unterbinden kann.
Wir blenden keine Werbung ein und schränken die Inhalte in keinster Weise bei Benutzung von Addblockern ein. Dadurch ist die Grundfunktionalität des Forums auch bei vollständigem Blockieren von Drittanbieter-Inhalten stets gegeben.

Cookies werden unsererseits nur verwendet um das Einloggen des Benutzers für die Dauer der Forenbenutzung zu speichern. Es steht dem Benutzer frei die Option 'Angemeldet bleiben' zu verwenden, damit der Cookie dauerhaft gespeichert bleibt und beim nächsten Besuch kein erneutes Einloggen mehr notwendig ist.
EMail-Adressen werden für Kontakt bei wichtigen Mitteilungen und zur Widerherstellung des Passwortes verwendet. Die verwendeten IPs können von uns ohne externe Hilfsmittel mit keiner realen Person in Verbindung gebracht werden und werden nach spätestens 7 Tagen gelöscht. Diese IPs werden höchstens verwendet um Neuanmeldungen unerwünschter oder gesperrter Nutzer zu identfizieren und zu unterbinden. Wir behalten uns daher vor bei Verdacht, die Frist für die IP-Löschung auf maximal 14 Tage zu verlängern.
Unsere Webseite läuft auf einem virtuellen Linux-Server, welcher von einem externen Anbieter gehostet wird. Etwaige Verstöße der DSGVO-Auflagen seitens dieses deutschen Hosters können wir nicht feststellen und somit auch nicht verfolgen.
Wir halten Backups unserer Datenbanken, welche in regelmäßigen Abständen als Schutz vor Katastrophen, Hackerangriffen und sonstigen Ausfällen erstellt werden. Sollte ein Nutzer die Löschung seiner Daten wünschen, betrachten wir es als Unzumutbar die Backups auch von den Daten zu befreien, da es sich hierbei um eine mehrtägiges Unterfangen handelt - dies ist für eine Einzelperson beim Betrieb eines privaten Forums nicht zumutbar möglich ohne das Backup komplett zu löschen.
Sollten Sie etwas gegen die dauerhafte anonyme Speicherung ihrer EMail-Adresse, ihres Pseudonyms und ihrer Beiträge in einem Backup haben, sehen Sie von der Registrierung in diesem Forum ab. Für Mitglieder, welche vor dem 25.05.2018 registriert waren steht jedoch das Recht im Raum, eine Löschung der Datenbank-Backups zu beantragen.



Wenn dies Ihr erster Besuch hier ist, lesen Sie bitte zunächst die FAQs sowie die wesentlichen Regeln zur Benutzung des Forums.
Um an den Diskussionen teilnehmen zu können, müssen Sie sich zunächst registrieren.

Beweis für kleinstes Element in IN und allen nichtleeren Teilmengen

Mathematische Fragestellungen
Antworten
Pippen
Ehrenmitglied
Ehrenmitglied
Beiträge: 2071
Registriert: 9. Jul 2010, 04:02

Beweis für kleinstes Element in IN und allen nichtleeren Teilmengen

Beitrag von Pippen » 12. Sep 2017, 00:31

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?

Benutzeravatar
tomS
Ehrenmitglied
Ehrenmitglied
Beiträge: 10670
Registriert: 19. Nov 2007, 20:29

Re: Beweis für kleinstes Element in IN und allen nichtleeren Teilmengen

Beitrag von tomS » 12. Sep 2017, 06:22

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.
Gruß
Tom

Der Wert eines Dialogs hängt vor allem von der Vielfalt der konkurrierenden Meinungen ab.
Sir Karl R. Popper

ralfkannenberg
Ehrenmitglied
Ehrenmitglied
Beiträge: 3587
Registriert: 13. Jan 2017, 10:00

Re: Beweis für kleinstes Element in IN und allen nichtleeren Teilmengen

Beitrag von ralfkannenberg » 12. Sep 2017, 10:36

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

Pippen
Ehrenmitglied
Ehrenmitglied
Beiträge: 2071
Registriert: 9. Jul 2010, 04:02

Re: Beweis für kleinstes Element in IN und allen nichtleeren Teilmengen

Beitrag von Pippen » 12. Sep 2017, 19:36

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?

Benutzeravatar
tomS
Ehrenmitglied
Ehrenmitglied
Beiträge: 10670
Registriert: 19. Nov 2007, 20:29

Re: Beweis für kleinstes Element in IN und allen nichtleeren Teilmengen

Beitrag von tomS » 12. Sep 2017, 23:11

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.
Gruß
Tom

Der Wert eines Dialogs hängt vor allem von der Vielfalt der konkurrierenden Meinungen ab.
Sir Karl R. Popper

ralfkannenberg
Ehrenmitglied
Ehrenmitglied
Beiträge: 3587
Registriert: 13. Jan 2017, 10:00

Re: Beweis für kleinstes Element in IN und allen nichtleeren Teilmengen

Beitrag von ralfkannenberg » 12. Sep 2017, 23:12

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

Skeltek
Site Admin
Site Admin
Beiträge: 5081
Registriert: 25. Mär 2008, 23:51
Wohnort: Stuttgart, Germany
Kontaktdaten:

Re: Beweis für kleinstes Element in IN und allen nichtleeren Teilmengen

Beitrag von Skeltek » 13. Sep 2017, 01:12

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.
Gödel für Dummies:
  • Unentscheidbarkeit - Dieser Satz ist wahr.
  • Unvollständig - Aussage A: Es existiert nur ein Element A.
  • Widersprüchlich - Dieser Satz ist falsch.

Benutzeravatar
tomS
Ehrenmitglied
Ehrenmitglied
Beiträge: 10670
Registriert: 19. Nov 2007, 20:29

Re: Beweis für kleinstes Element in IN und allen nichtleeren Teilmengen

Beitrag von tomS » 13. Sep 2017, 09:52

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.
Gruß
Tom

Der Wert eines Dialogs hängt vor allem von der Vielfalt der konkurrierenden Meinungen ab.
Sir Karl R. Popper

Pippen
Ehrenmitglied
Ehrenmitglied
Beiträge: 2071
Registriert: 9. Jul 2010, 04:02

Re: Beweis für kleinstes Element in IN und allen nichtleeren Teilmengen

Beitrag von Pippen » 13. Sep 2017, 14:14

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?
Dateianhänge
Beweis.jpg
Beweis.jpg (101.82 KiB) 13570 mal betrachtet

Benutzeravatar
tomS
Ehrenmitglied
Ehrenmitglied
Beiträge: 10670
Registriert: 19. Nov 2007, 20:29

Re: Beweis für kleinstes Element in IN und allen nichtleeren Teilmengen

Beitrag von tomS » 13. Sep 2017, 15:33

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

Der Wert eines Dialogs hängt vor allem von der Vielfalt der konkurrierenden Meinungen ab.
Sir Karl R. Popper

ralfkannenberg
Ehrenmitglied
Ehrenmitglied
Beiträge: 3587
Registriert: 13. Jan 2017, 10:00

Re: Beweis für kleinstes Element in IN und allen nichtleeren Teilmengen

Beitrag von ralfkannenberg » 14. Sep 2017, 10:31

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

ralfkannenberg
Ehrenmitglied
Ehrenmitglied
Beiträge: 3587
Registriert: 13. Jan 2017, 10:00

Re: Beweis für kleinstes Element in IN und allen nichtleeren Teilmengen

Beitrag von ralfkannenberg » 14. Sep 2017, 10:33

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

Benutzeravatar
seeker
Ehrenadmin
Ehrenadmin
Beiträge: 8098
Registriert: 26. Dez 2009, 10:29

Re: Beweis für kleinstes Element in IN und allen nichtleeren Teilmengen

Beitrag von seeker » 14. Sep 2017, 10:48

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... :) :devil:
Grüße
seeker


Wissenschaft ... ist die Methode, kühne Hypothesen aufstellen und sie der schärfsten Kritik auszusetzen, um herauszufinden, wo wir uns geirrt haben.
Karl Popper

Skeltek
Site Admin
Site Admin
Beiträge: 5081
Registriert: 25. Mär 2008, 23:51
Wohnort: Stuttgart, Germany
Kontaktdaten:

Re: Beweis für kleinstes Element in IN und allen nichtleeren Teilmengen

Beitrag von Skeltek » 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.
Gödel für Dummies:
  • Unentscheidbarkeit - Dieser Satz ist wahr.
  • Unvollständig - Aussage A: Es existiert nur ein Element A.
  • Widersprüchlich - Dieser Satz ist falsch.

Benutzeravatar
tomS
Ehrenmitglied
Ehrenmitglied
Beiträge: 10670
Registriert: 19. Nov 2007, 20:29

Re: Beweis für kleinstes Element in IN und allen nichtleeren Teilmengen

Beitrag von tomS » 14. Sep 2017, 11:53

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.
Gruß
Tom

Der Wert eines Dialogs hängt vor allem von der Vielfalt der konkurrierenden Meinungen ab.
Sir Karl R. Popper

Antworten