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

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

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

נגדיר קבוצה $ 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)