Starke Induktion

06.01.2011, 16:20	missy54	Auf diesen Beitrag antworten »
Starke Induktion Ich habe eine Frage zu einem Beweis mit starker Induktion: Jede nichtleere Teilmenge M echte Teilmenge von N (natürliche Zahlen) hat ein kleinstes Element. Beweis durch starke Induktion: Sei M aus N (natürl. Z.) beliebig. Angenommen M hat kein kleinstes Element. Zeige für alle n aus N: n nicht Element von M mit starker Induktion: sei n aus N beliebig. Angenommen für alle k kleiner n gilt: k nicht Element von M. Dann kann auch n nicht in M sein, denn sonst wäre für (n kleiner gleich m): aus (Für alle m aus M) folgt (n kleinstes Element). Das ist ein Widerspruch zur Annahme, dass M kein kleinstes Element hat. Ich verstehe die Struktur dieses Beweises leider gar nicht und hoffe (zuerst wir k verwendet und dann auf einmal m?!), dass mir jemand helfen kann.
06.01.2011, 16:52	Math1986	Auf diesen Beitrag antworten »
Bitte nutze den Formeleditor und schreib das nochmal sauber auf
06.01.2011, 18:00	missy54	Auf diesen Beitrag antworten »
Jede nichtleere Teilmenge M $\begin{eqnarray} \subseteq \end{eqnarray}$ N (natürliche Zahlen) hat ein kleinstes Element. Beweis durch starke Induktion: Sei M $\begin{eqnarray} \in \end{eqnarray}$ N (natürl. Z.) beliebig. Angenommen M hat kein kleinstes Element. Zeige für alle n $\begin{eqnarray} \in \end{eqnarray}$ N: n nicht $\begin{eqnarray} \in \end{eqnarray}$ M mit starker Induktion: sei n $\begin{eqnarray} \in \end{eqnarray}$ N beliebig. Angenommen $\begin{eqnarray} \forall \end{eqnarray}$ k $\begin{eqnarray} kleiner als \end{eqnarray}$ n gilt: k nicht $\begin{eqnarray} \in \end{eqnarray}$ M. Dann kann auch n nicht in M sein, denn sonst wäre für n $\begin{eqnarray} \leq \end{eqnarray}$ m: $\begin{eqnarray} \forall \end{eqnarray}$ m $\begin{eqnarray} \in \end{eqnarray}$ M $\begin{eqnarray} \Rightarrow \end{eqnarray}$ n kleinstes Element. Das ist ein Widerspruch zur Annahme, dass M kein kleinstes Element hat.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »