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

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

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

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

1. $1\in S$
2. $\{1,\dots ,n\}\subseteq S⟹n+1\in S$

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

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

$P(n)⟺\{1,\dots ,n\}\subseteq S$

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

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

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

נניח $P(k)$ נכונה עבור $k\ge 1$ . לכן $k\in S^{\prime }$ ומהגדרה (2)

$\{1,\dots ,k\}\subseteq S⟹k+1\in S⟹\{1,\dots ,k+1\}\subseteq S$

לכן $P(k+1)$ נכונה ומכאן $k+1\in S^{\prime }$ .

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

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

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