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

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

תגובה אחרונה: לפני 7 שניםתגובה אחתאדם אחד בשיחה

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

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

עלינו להוכיח כי $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}$ .