Matematyka.pl

Udowodnij, że Zasada Indukcji Matematycznej wynika z faktu, iż każdy niepusty podzbiór liczb naturalnych zawiera liczbę
najmniejszą.

Należy wykazać, że jeśli \(\displaystyle{ A \subseteq \mathbb{N}}\) jest dowolnym podzbiorem spełniającym

(i) \(\displaystyle{ 0 \in A}\)
(ii) \(\displaystyle{ (\forall n \in \mathbb{N}) \big( n \in A \implies n+1 \in A \big)}\),

to \(\displaystyle{ A = \mathbb{N}}\). Weźmy zatem dowolny taki zbiór \(\displaystyle{ A \subseteq \mathbb{N}}\) i załóżmy nie wprost, że \(\displaystyle{ A \neq \mathbb{N}}\). Wtedy zbiór \(\displaystyle{ \mathbb{N} \setminus A}\) jest niepustym podzbiorem \(\displaystyle{ \mathbb{N}}\), zatem ma element najmniejszy \(\displaystyle{ b_0}\). Rozważmy dwa przypadki:

1. \(\displaystyle{ b_0 = 0}\) - w szczególności \(\displaystyle{ 0 \in \mathbb{N} \setminus A}\), co jest sprzeczne z warunkiem (i).
2. \(\displaystyle{ b_0 > 0}\) - wtedy \(\displaystyle{ b_0 = n+1}\) dla pewnego \(\displaystyle{ n \in \mathbb{N}}\). Skoro \(\displaystyle{ b_0 = \min( \mathbb{N} \setminus A )}\), to \(\displaystyle{ n}\) nie może należeć do \(\displaystyle{ \mathbb{N} \setminus A}\) (bo jest mniejszy od \(\displaystyle{ b_0}\)), zatem \(\displaystyle{ n \in A}\). Z warunku (ii) mamy, że \(\displaystyle{ n+1 \in A}\), czyli \(\displaystyle{ b_0 \notin \mathbb{N} \setminus A}\) - sprzeczność.

Oba przypadki prowadzą do sprzeczności, co kończy dowód nie wprost.