Udowodnij, że Zasada Indukcji Matematycznej wynika z faktu, iż każdy niepusty podzbiór liczb naturalnych zawiera liczbę
najmniejszą.
Zasada Indukcji Matematycznej
-
- Użytkownik
- Posty: 4
- Rejestracja: 16 lip 2023, o 21:10
- Płeć: Mężczyzna
- wiek: 18
- Podziękował: 1 raz
- Dasio11
- Moderator
- Posty: 10261
- Rejestracja: 21 kwie 2009, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 41 razy
- Pomógł: 2381 razy
Re: Zasada Indukcji Matematycznej
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.
(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.