Prinzip der vollständigen Induktion beweisen

10.08.2023, 20:22	KonverDiv	Auf diesen Beitrag antworten »
Prinzip der vollständigen Induktion beweisen Hallo, Ich möchte gerne folgenden Satz beweisen: Angenommen $\begin{eqnarray} P(n) \end{eqnarray}$ ist eine Aussage über eine positive ganze Zahl und $\begin{eqnarray} c \end{eqnarray}$ ist eine feste positive ganze Zahl. Angenommen (1) $\begin{eqnarray} P(c) \end{eqnarray}$ is wahr und (2) für jedes $\begin{eqnarray} m \geq c \end{eqnarray}$ , falls $\begin{eqnarray} P(m) \end{eqnarray}$ wahr ist, ist auch $\begin{eqnarray} P(m+1) \end{eqnarray}$ wahr, dann ist $\begin{eqnarray} P(n) \end{eqnarray}$ wahr für alle $\begin{eqnarray} n \geq c \end{eqnarray}$ . Mein Beweis des Satzes sehe nun so aus: Angenommen $\begin{eqnarray} P(n) \end{eqnarray}$ ist falsch, dann definieren wir $\begin{eqnarray} S = \left\{ n \, \| \, n \in \mathbb{Z}^+ \text{ und } P(n) \text{ falsch } \right\} \end{eqnarray}$ , diese Menge ist nicht leer. Nach dem Wohlordnungssatz beinhaltet $\begin{eqnarray} S \end{eqnarray}$ ein kleineres Element mit $\begin{eqnarray} n < c \end{eqnarray}$ und dieses ist gleichzeitig $\begin{eqnarray} n \neq c \end{eqnarray}$ , weil $\begin{eqnarray} P(c) \end{eqnarray}$ nach (1) wahr ist. Dann ist $\begin{eqnarray} n - 1 \end{eqnarray}$ eine positive ganze Zahl und $\begin{eqnarray} P(n-1) \end{eqnarray}$ ist wahr, weil $\begin{eqnarray} n-1 \end{eqnarray}$ kleiner ist als $\begin{eqnarray} n \end{eqnarray}$ und nach (2) ist $\begin{eqnarray} P(n - 1 + 1) \end{eqnarray}$ ebenfalls wahr, das heißt aber auch, dass $\begin{eqnarray} P(n) \end{eqnarray}$ wahr ist. Das ist ein Widerspruch, dazu dass $\begin{eqnarray} P(n) \end{eqnarray}$ falsch ist. Daraus folgern wir, dass $\begin{eqnarray} P(n) \end{eqnarray}$ für alle $\begin{eqnarray} n \geq c \end{eqnarray}$ gilt. Ich bin mir nicht sicher, ob das so ok ist?
10.08.2023, 22:17	Finn_	Auf diesen Beitrag antworten »
Darin scheint mir $\begin{eqnarray} n\in\mathbb Z^+ \end{eqnarray}$ ein Flüchtigkeitsfehler zu sein. Berichtigt und zum Vergleich in alternativer Wortwahl: Angenommen, es ist ein $\begin{eqnarray} n\ge c \end{eqnarray}$ zu finden, bei dem $\begin{eqnarray} P(n) \end{eqnarray}$ nicht gilt. Man setze $\begin{eqnarray} S := \{n\in\mathbb Z\mid n\ge c\land\lnot P(n)\}. \end{eqnarray}$ Das Minimum $\begin{eqnarray} n_0=\min(S) \end{eqnarray}$ existiert, weil $\begin{eqnarray} S \end{eqnarray}$ total geordnet, fundiert und laut Annahme nichtleer ist. Wegen (1) ist $\begin{eqnarray} n_0>c, \end{eqnarray}$ und somit $\begin{eqnarray} n_0-1\ge c. \end{eqnarray}$ Es muss $\begin{eqnarray} P(n_0-1) \end{eqnarray}$ gelten, weil $\begin{eqnarray} n_0 \end{eqnarray}$ sonst nicht das Minimum wäre. Mit (2) folgt nun $\begin{eqnarray} P(n_0), \end{eqnarray}$ womit wir den Widerspruch $\begin{eqnarray} n_0\notin S \end{eqnarray}$ erhalten.
11.08.2023, 10:07	KonverDiv	Auf diesen Beitrag antworten »
Hallo @Finn_, vielen Dank für deine Korrektur! Warum ist es bei dir $\begin{eqnarray} n\in\mathbb Z \end{eqnarray}$ , wenn wir doch im Satz positive ganze Zahlen betrachten?
11.08.2023, 13:02	Finn_	Auf diesen Beitrag antworten »
Bezüglich $\begin{eqnarray} c\in\mathbb Z^+ \end{eqnarray}$ besteht für $\begin{eqnarray} S_1 := \{n\in\mathbb Z\mid n\ge c\land\lnot P(n)\}, \end{eqnarray}$ $\begin{eqnarray} S_2 := \{n\in\mathbb Z^+\mid n\ge c\land\lnot P(n)\}, \end{eqnarray}$ $\begin{eqnarray} S_3 := \{n\in\mathbb Z_{\ge c}\mid \lnot P(n)\}, \end{eqnarray}$ $\begin{eqnarray} S_4 := \{n\mid n\in\mathbb Z^+\land n\ge c\land\lnot P(n)\} \end{eqnarray}$ üblicherweise die Gleichheit $\begin{eqnarray} S_1=S_2=S_3=S_4. \end{eqnarray}$ Welche Schreibweise du wählst, muss dir überlassen sein. Insofern $\begin{eqnarray} P \end{eqnarray}$ lediglich auf $\begin{eqnarray} \mathbb Z^+ \end{eqnarray}$ definiert ist, mögen $\begin{eqnarray} S_1,S_4 \end{eqnarray}$ im Zweifel seltsam wirken. Sofern $\begin{eqnarray} \mathbb Z^+ \end{eqnarray}$ das Diskursuniversum ist, ginge auch $\begin{eqnarray} S := \{n\mid n\ge c\land\lnot P(n)\}. \end{eqnarray}$

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »