Fragen zu einer Musterlösung Beweis

Question

In Blau sind meine(vlt. unnötigen) Kommentare, damit die Frage spezifischer beantwortet werden kann

Die rot markierten Stellen verstehe ich nicht :(

Beh.: Sei M⊂ℕ mit M≠∅. Dann existiert ein n∈M, sodass n≤m für alle m∈M gilt.

Für jede nicht leere Teilmenge M der natürlichen Zahlen, gibt es eine kleinste Zahl n∈M, die kleiner-gleich als alle anderen Zahlen m∈M ist.

Widerspruchsannahme: Für alle n∈M existiert ein m∈M, sodass m<n.Wir beweisen, dass M=∅, also für alle n∈ℕ, n∉M gilt.

Es wird angenommen das es eine noch kleinere Zahl als n gibt, die ebenfalls zu der Teilmenge M gehört, also insbesondere eine natürliche Zahl ist. 

[IA] Sei 1∈M. Dann existiert m⊂ℕ⊂ℤ, sodass m<1, also m≤0. Dies ist ein Widerspruch zu m∈ℕ , also 1∉M.

[IS] Sei n+1 ∈ M. Dann existiert m ∈ M, sodass m< n+1. Das bedeutet, dass m ∈ {q ∈ ℕ:q<n+1}={1,...,n}. Dies ist ein Widerspruch, da {1,...,n}∩M=∅ (Induktionsannahme) *

 M=∅ wäre zwar ein Widerspruch zur ursprünglichen Behauptung, aber ich verstehe nicht ganz wie es mit dem Rest der Widerspruchsannahme zusammenhängt?

"Dies ist ein Widerspruch, da {1,...,n}∩M=∅". Natürlich ist die Schnittmenge mit der leeren Menge gleich die leere Menge, wo ist der Widerspruch und der Beweis das M die leere Menge ist?

*Ist hiermit die ursprüngliche Behauptung oder die Widerspuchsannahme gemeint?

An die Beantworter, helfen die farblichen Markierungen in der Frage oder irritieren sie eher?

Comments

Die Farben sind schon hilfreich, nur weiß man halt oft trotzdem nicht genau, was man erklären soll und was nicht, fast wie ein Doktor, der nur ein Symptom sieht, aber etwas tiefer Zugrundeliegendes behandeln muss.

Answer 1

Ein Widerspruchsbeweis funktioniert so, dass du das Gegenteil der zu beweisenden Aussage als Voraussetzung annimmst, und dann durch logische Folgerungen zu einem Widerspruch zwischen zwei deiner Voraussetzungen kommst. Damit kann unter diesen Voraussetzungen die Aussage niemals wahr sein, was bedeutet, dass die gegenteilige Aussage (die zu beweisende Aussage) immer wahr ist (natürlich nur, wenn nicht die anderen Voraussetzungen sich widersprechen, dann hast du aber ein größeres Problem mit deinem Satz...).

In diesem Fall haben wir als Annahmen die Annahmen des Satzes und außerdem nehmen wir an, dass die Folgerung des Satzes falsch ist. Von dieser Startposition aus müssen wir beweisen, dass wir einen logischen Widerspruch in unseren Annahmen haben. Das können wir machen, indem wir zeigen, dass M die leere Menge sein muss, weil sie gleichzeitig nach Voraussetzung NICHT leer sein muss.

Zu diesem Zweck machen wir innerhalb dieses Widerspruchbeweises jetzt noch einen Induktionsbeweis.

Induktionsvoraussetzung: "Keine Zahl kleiner oder gleich n ist in M."

Induktionsanfang: "1 ist nicht in M": Da Eins die kleinste natürliche Zahl ist, kann es keine kleinere natürliche Zahl in M geben, damit ist auch 1 nicht in M. n=1 ist also der Induktionsanfang.

Induktionsschritt: "Wenn keine Zahl kleiner oder gleich n in M ist, ist auch keine Zahl kleiner oder gleich n+1 in M.": Für alle Zahlen außer n+1 ist die Aussage klar. Für n+1 gibt es genau n natürliche Zahlen, die kleiner n+1 sind, die sind aber wegen der Induktionsvoraussetzung nicht in M, daher ist auch n+1 nicht in M.

Damit ist der Induktionsbeweis abgeschlossen und es gilt für alle natürlichen n, dass n nicht in M ist. Da aber M nur natürliche Zahlen zulässt, bedeutet das, dass M leer ist. Dies ist ein Widerspruch zu unserer Annahme, dass M nichtleer sei.