Vollständige Induktion, Beweise: "Für alle Menge von Größe n ≥ 1, gibt es ein kleinstes Element."

Question

Aufgabe:

In dieser Übungen nehmen wir an, dass es eine partielle Ordnung ≼ gibt. Das bedeutet, dass es
nicht immer gilt, dass ≼ oder ≼ , sondern nur wenn und vergleichbar sind.
Beweisen Sie die folgende Eigenschaft durch vollständige Induktion für alle ∈ N:

"Für alle Menge von Größe ≥ 1, gibt es ein kleinstes Element."

Problem/Ansatz:

\(\textbf{Behauptung}:\)
\(\text{Für alle Mengen von Größe} n \geq 1, \text{ gibt es ein kleinstes Element.}\)

\(\textbf{Induktionsanfang}:\)
\(\text{Beweis der Behauptung für } n = 2 \text{. Unter Annahme einer partiellen Ordnung und der Vergleichbarkeit der Mengenelemente gilt für } n = 2:\)

\(M = \{a_{1}, a_{2}\}\)

Nun weiß ich nicht mehr weiter. Meiner Meinung nach kann ich ja nicht sagen, dass M eine Teilmenge der natürlichen Zahlen ist oder?

Habe dann Folgendes probiert:

Folglich entweder: \(a_{1} < a_{2}\)

oder: \(a_{1} > a_{2}\)

Würde mich freuen, wenn mir jemand helfen könnte diese vollständige Induktion zu lösen!

Freundliche Grüße

Jsmileman

Comments

Sicher, dass du die Angabe richtig abgeschrieben hast?

So macht die Angabe für mich nämlich wenig Sinn. Betrachten wir z.B die Potenzmenge einer beliebigen (nichtleeren) Menge M. Mit Relation der Teilmenge bildet diese eine partielle Ordnung. Nun betrachten wir eine Teilmenge von P_M, nämlich all jene Mengen, die einelementig sind. In dieser Menge gibt es aber kein kleinstes Element.

Mehr Sinn würde die Aufgabe machen (und ist auch eine sehr typische Aufgabe), wenn gefragt wäre: "Für alle Menge vergleichbarer Elemente von Größe ≥ 1, gibt es ein kleinstes Element."

Bzw. "Zeige, dass eine partiell geordnete Menge in total geordnete Ketten zerfällt und jede dieser Ketten ein kleinstes Element hat."

---

Hallo desRes,

ja die Aufgabenstellung ist falsch. Die Behauptung wurde erst im Nachhinein vom Dozenten korrigiert:

”Für alle Mengen von Größe n ≥ 1, gibt es ein minimales Element.”

Fand am Anfang schwierig den Unterscheid zwischen kleinsten und minimalem Element nachzuvollziehen. Ein minimales Element wird (nach der Ordnung) von keinem anderen Element der Menge untertroffen. Ein kleinstes Element untertrifft alle anderen Elemente der Menge. In Deinem Beispiel zur Potenzmenge kann man sehen, dass es nicht immer ein kleinstes aber (mindestens) ein minimales Element gibt.

Die Aufgabe konnte ich so lösen. Dennoch fand ich es schwer weil ich teilweise noch nicht die ganzen Ordnungsrelationen (Totalordnung, Halbordnung/partielle Ordnung etc.) genau verstehe.

Für die Aufgabe bzw. für den Induktionsschritt (n+1) kann man eine Fallunterscheidung machen: Und abhängig davon ob zwei Elemente vergleichbar sind ergibt sich dann das minimale Element. Die Vergleichbarkeit von zwei Mengenelementen hängt eben von der Ordnungsrelation ab, oder?

Danke Dir dennoch für die Hilfe @desRes.

Grüße jsmileman

P.S. kann den ursprünglichen Post nicht mehr ändern, um die Behauptung anzupassen.