שיחה:אינדוקציה מתמטית

אינדוקציה גוררת אינדוקציה שלמה

נשתמש באקסיומת האינדוקציה הרגילה.

נגדיר קבוצה $S\subseteq \mathbb {N}$ המקיימת

1. $1\in S$
2. $\{1,\ldots ,n\}\subseteq S\implies n+1\in S$

עלינו להוכיח כי $S=\mathbb {N}$ , כלומר להוכיח את עקרון האינדוקציה השלמה.

נגדיר טענה $P(n)$ כלשהיא המקיימת

$P(n)\iff \{1,\ldots ,n\}\subseteq S$

נגדיר קבוצה המקיימת

$S'=\{n\in \mathbb {N} :P(n){\text{ true}}\}$

$P(1)$ נכונה מהגדרה (1), לכן $1\in S'$ .

נניח $P(k)$ נכונה עבור $k\geq 1$ . לכן $k\in S'$ ומהגדרה (2)

$\{1,\ldots ,k\}\subseteq S\implies k+1\in S\implies \{1,\ldots ,k+1\}\subseteq S$

לכן $P(k+1)$ נכונה ומכאן $k+1\in S'$ .

$S'$ מקיימת את התנאים של $S$ , לכן $S'=\mathbb {N}$ והטענה $P(n)$ נכונה לכל $n$ .

באופן דומה גם $S=\mathbb {N}$ .

יהודה שמחה ולדמן (שיחה) 11:58, 1 באוקטובר 2017 (IDT)