Induktionsbeweis (gleiche Größe) falsch?

Question

Hallo allerseits!

Mir wurde die folgende Aufgabe gestellt: Finde den Fehler im folgenden Beweis:

 Satz: Alle Personen in einer Menge X von n Personen haben die gleiche Größe.

Beweis: Die Induktionsvoraussetzung für n = 1 ist offensichtlich erfüllt. Für den Induktionschritt nehmen wir an, dass die Aussage für alle Mengen mit bis zu n Personen gilt, und betrachten eine Menge X mit n + 1 Personen. Wir zerlegen X in Teilmengen A und B:  |A| ≤ n, |B| ≤ n, A∩B =/= ∅ und A∪ B= X. Dann folgt nach Induktionsannahme, dass alle Personen in A und B gleich gross sind. Da der Schnitt von A und B nicht leer ist,sind also alle Personen in A∪B= X gleich gross.

Ich glaube so eine ähnliche Aufgabe schon mal mit gleichfärbigen Ponies oder Frauen mit gleicher Haarfarbe gesehen zu haben, der 'Trick' war, dass der Schritt von n=1 auf n=2 nicht funktioniert hat, aber dabei wurden einzelne Ponies/Frauen aus der Menge entfernt und hinzugefügt und hier ist die Sachlage ja doch ein bisschen anders. Ich wäre für jegliche Hilfe sehr dankbar!

Answer 1

> Wir zerlegen X in Teilmengen A und B:  |A| ≤ n, |B| ≤ n, A∩B ≠ ∅ und A∪ B= X.

> Da der Schnitt von A und B nicht leer ist,sind also alle Personen in A∪B= X gleich gross.

Für  n+1 = 2  sei X = { u,v }   →  A = {u} , B = {v}   →  A∩B = { }   (Widerspruch!)

Der Induktionsschluss "n → n+1"  geht also  bei 1 → 2 schief.

[ Lustigerweise funktioniert er bei 2→3 , 3→ 4 .... , aber was nützt das? :-) ]

---------------

> ... aber dabei wurden einzelne Ponies/Frauen aus der Menge entfernt und hinzugefügt und hier ist die Sachlage ja doch ein bisschen anders.

Aber wirklich nur ein "bisschen": Mit der Voraussetzung  A∩B ≠ ∅  versucht man auch, mindestens ein "Pony" aus der Menge A∪B in die Menge A∩B zu schieben.

Gruß Wolfgang  

Comments

wenn "zerlegen" im wörtlichen Sinn einer Partition interpretiert wird, so ist bereits die Forderung ein Widerspruch in sich, da \(A \cap B \neq \emptyset\) überhaupt nicht erlaubt ist. Damit hast Du erst einmal gar nichts bewiesen, als nur dass die Forderung nicht erfüllbar ist. Das hat mit vollst. Induktion überhaupt nichts zu tun.

Fall "zerlegen" nicht so eng gemeint ist, kannst Du \( A = \{u,v \} \) und \( B = \{ u \} \) setzen, und hast bisher noch nichts bewiesen. oder widerlegt.

Grüße,

M.B.

---

@MatheMB Es war $$|A|,|B| \le n$$ vorausgesetzt, wobei hier n=1 ist. Insofern hat er Recht, dass keine Zerlegung in Mengen A,B möglich ist, welche die Bedingungen erfüllt.

---

Hallo Raskolnikow,,

Deine Argumentation ist ebenfalls falsch.

Hier wird eine Zerlegung (im Sinne von Partitionierung) verlangt, mit \(A \cap B \neq \emptyset\). Das ist aber ein Widerspruch zu Definition einer Partitionierung die eben gerade \(A \cap B = \emptyset\) verlangt. Damit ist aber die Aufgabenstellung vom Prinzip her falsch und die Folgerung daraus ist, dass überhaupt nicht gerechnet oder bewiesen werden darf.

(Und das Ganze hat mit vollständiger Induktion überhaupt nichts zu tun.)

Grüße,

M.B.

---

Du irrst. Es wird verlangt, zwei Mengen A,B zu finden, die nicht disjunkt sind und $$ X = A\cup B$$ erfüllen.

Für n+1 = 2 heißt das:

$$ X = \{a,b\},$$

was sich zwar in der Form

$$ X = \{a,b\} \cup \{a\} = A \cup B$$

zerlegen lässt (das ist in der Aufgabe mit Zerlegung gemeint), aber nicht die Bedingung |A|=1 erfüllt. Wie Wolfgang korrekt bemerkt hat, scheitert es an dieser Stelle, denn die einzige Zerlegung mit $$|A|\le 1 ~\text{und} ~|B| \le 1~\text{und}~ A\cup B = X$$ wäre

$$ \{a\} \cup \{b\} ,$$

was aber offensichtlich disjkunkte Mengen sind.

---

Noch ein Hinweis: Die Annahme, die ganze Aufgabenstellung sei falsch, ist oft ein Hinweis, dass man die Aufgabe nicht so ganz verstanden hat ;)