Induktionsbeweis

[Mario Sandler]

Hallo,
ich soll folgenden Beweis durchführen:

Gegeben ist eine Menge M und eine Abbildung f: M->M
Eine Folge von Mengen wird definiert durch:

$M_0 = M$

$\forall n \in N : M_{n+1} = \{ f(x) | x \in M_n \}$

Beweisen sie:

$\forall n \in N : M_{n+1} \subseteq M_n$

Den Induktionsanfang krieg ich noch hin, M1 muss ja eine Teilmenge von M0
sein da M0 = M und f M auf M abbildet. Aber der Rest ist mir nicht klar.

Kann mir jemand helfen?

[SG1]

Versuchs doch mal mit einfach hinschreiben. Was weisst Du über M_{n+1}? Und was über M_n?

[Mario Sandler]

Ich hab mir folgendes überlegt.
Wenn f eine Abbildung ist von M auf M. Dann muss diese bijektiv sein,
da beide Mengen logischerweise gleich viel Elemente besitzen. Somit wäre
M_n+1 nur eine Permutation von M_n und damit alle Mengen M_n = M.

Ich versteh aber nicht wie ich das aufschreiben muss, damit es über
Induktion bewiesen ist.

[SG1]

Storm.Xapek.de schrieb:

Ich hab mir folgendes überlegt.
Wenn f eine Abbildung ist von M auf M. Dann muss diese bijektiv sein,
da beide Mengen logischerweise gleich viel Elemente besitzen.

Ah, ja. f(n) = n+1 ist also bijektiv auf den natürlichen Zahlen.

[Mario Sandler]

Hm stimmt. Aber wie argumentiert man dann?
Ich steh grad total auf dem Schlauch...

[BAM-O-MATIC]

Storm.Xapek.de schrieb:

Hm stimmt. Aber wie argumentiert man dann?
Ich steh grad total auf dem Schlauch...

Nehmen wir doch mal ein Beispiel.
f(1,2,3,4) = (3,3,1,2)
M = {1,2,3,4}
M_1 = {1,2,3}
M_2 = {1,3}
M_3 = {1,3}
...

meinst du, das supseteq sollte ein subseteq sein?

ansonsten, überleg dir mal, wie die 1 in M_3 reingekommen ist. Warum muss die 1 auch in M_2 drinnen sein?

[Bashar]

Storm.Xapek.de schrieb:

Hallo,
ich soll folgenden Beweis durchführen:

Gegeben ist eine Menge M und eine Abbildung f: M->M
Eine Folge von Mengen wird definiert durch:

$M_0 = M$

$\forall n \in \mathbb{N} : M_{n+1} = \{ f(x) | x \in M_n \}$

Beweisen sie:

$\forall n \in \mathbb{N} : M_{n+1} \supseteq M_n$

Den Induktionsanfang krieg ich noch hin, M1 muss ja eine Teilmenge von M0
sein da M0 = M und f M auf M abbildet. Aber der Rest ist mir nicht klar.

Kann mir jemand helfen?

//EDIT:
Der Latex-Code will irgendwie nicht

FTFY

[TIPP-0-MATIC]

Noch ein Tipp:
M_n = Bildⁿ(M) = Bild^n-1( Bild(M) ) ≤ Bild^n-1( M ) trivial.