Zbiory induktywne

[Jakub Gurak]

Aksjomat nieskończoności

Istnieje zbiór \(\displaystyle{ X}\) taki że:

(1) \(\displaystyle{ \varnothing\in X}\)

(2) \(\displaystyle{ Y\in X \rightarrow Y \cup \left\{ Y\right\} \in X}\)

Każdy taki zbiór, spełniający te dwa warunki nazwiemy zbiorem induktywnym. Aksjomat nieskończoności mówi więc że istnieje co najmniej jeden zbiór induktywny

Taki zbiór \(\displaystyle{ X}\) musi być nieskończony- mamy \(\displaystyle{ \varnothing\in X}\),

stosując (2) dla zbioru pustego, otrzymujemy że \(\displaystyle{ \left\{ \varnothing\right\}=\varnothing \cup \left\{ \varnothing\right\} \in X}\),

dalej stosując (2) dla \(\displaystyle{ \left\{ \varnothing\right\}}\) otrzymujemy że \(\displaystyle{ \left\{ \varnothing, \left\{ \varnothing\right\}\right\}=\left\{ \varnothing\right\}\cup \left\{ \left\{ \varnothing\right\}\right\} \in X}\)

I dalej ponieważ \(\displaystyle{ \left\{ \varnothing, \left\{ \varnothing\right\}\right\}\in X}\), więc stosując ponownie (2) dla tego zbioru otrzymujemy że \(\displaystyle{ \Bigl \{ \varnothing, \left\{ \varnothing\right\}, \ \left\{ \varnothing, \left\{ \varnothing\right\}\right\} \Bigr\}\in X}\)

Itd.- taki zbiór musi być nieskończony

Jednak aksjomat nie nakłada ograniczeń górnych na ten zbiór. Najmniejszy z takich zbiorów będzie służył nam jako \(\displaystyle{ \NN}\) Najpierw musimy udowodnić ze taki istnieje


Istnieje najmniejszy, względem inkluzji, zbiór induktywny

W dowodzie bardzo pomocny będzie poniższy lemat

Jeśli \(\displaystyle{ C}\) jest niepustym zbiorem zbiorów induktywnych, to \(\displaystyle{ \bigcap C}\) jest również zbiorem induktywnym

Dowód tego lematu jest raczej żmudny, i przedstawie go może później

Dowód twierdzenia :

Ustalmy zbiór induktywny \(\displaystyle{ X}\) I rozważmy zbiór

\(\displaystyle{ Y=\left\{ A\in P\left( X\right): \ A \hbox{ jest induktywny } \right\}}\)

Innymi słowy, rozważamy wszystkie podzbiory \(\displaystyle{ X}\) induktywne

Taki zbiór \(\displaystyle{ Y}\) jest niepusty, bo \(\displaystyle{ X \in Y}\), bo \(\displaystyle{ X}\) z założenia jest induktywny

\(\displaystyle{ Y}\) jest niepustym zbiorem zbiorów induktywnych, zatem na mocy lematu \(\displaystyle{ \bigcap Y}\) jest również zbiorem induktywnym

Ten iloczyn podzbiorów \(\displaystyle{ X}\) jest podzbiorem \(\displaystyle{ X}\) i jest induktywny, zatem \(\displaystyle{ \bigcap Y \in Y}\)

Ponieważ \(\displaystyle{ \bigcap Y}\) jest podzbiorem każdego elementu \(\displaystyle{ Y}\),

więc \(\displaystyle{ \bigcap Y}\) jest najmniejszym ( ze względu na inkluzję ) elementem \(\displaystyle{ Y}\), a więc \(\displaystyle{ \bigcap Y}\) jest najmniejszym zbiorem induktywnym będącym podzbiorem \(\displaystyle{ X}\)

Pokażemy, że w ogóle jest najmniejszy. W tym celu ustalmy dowolny zbiór induktywny \(\displaystyle{ Z}\)

\(\displaystyle{ Z}\) jest induktywny i \(\displaystyle{ X}\) jest induktywny, zatem znowu stosując lemat \(\displaystyle{ Z \cap X}\) jest induktywny

Niewątpliwie \(\displaystyle{ Z \cap X \subset Z}\)

Oczywiście również \(\displaystyle{ Z \cap X \subset X}\) i \(\displaystyle{ Z \cap X}\) jest induktywny, a skoro zaznaczyłem że \(\displaystyle{ \bigcap Y}\) jest najmniejszym zbiorem induktywnym będącym podzbiorem \(\displaystyle{ X}\) więc \(\displaystyle{ \bigcap Y \subset Z \cap X \subset Z}\) Pokazaliśmy że \(\displaystyle{ \bigcap Y \subset Z}\)

Z dowolności wyboru zbioru induktywnego \(\displaystyle{ Z}\), \(\displaystyle{ \bigcap Y}\) jest podzbiorem każdego zbioru induktywnego, a więc jest najmniejszym, w sensie inkluzji, zbiorem induktywnym \(\displaystyle{ \square}\)

Taki zbiór jest tylko jeden. Gdyby istniały dwa najmniejsze zbiory induktywne ( względem inkluzji), to by się wzajemnie zawierały, zatem muszą być równe

Łatwo sprawdzić, że taki zbiór spełnia aksjomaty Peano liczb naturalnych, a więc może służyć jako \(\displaystyle{ \NN}\)



PróbaCzas udowodnić lemat

Jeśli \(\displaystyle{ C}\) jest niepustym zbiorem zbiorów induktywnych, to \(\displaystyle{ \bigcap C}\) jest również zbiorem induktywnym

Dowód

Niech \(\displaystyle{ C}\) będzie niepustym zbiorem zbiorów induktywnych

Pokażemy że \(\displaystyle{ \bigcap C}\) jest również zbiorem induktywnym

Musimy pokazać dwa fakty

(1) \(\displaystyle{ \varnothing\in \bigcap C}\)

(2) \(\displaystyle{ Y\in \bigcap C \rightarrow Y \cup \left\{ Y\right\} \in \bigcap C}\)

Aby udowodnić punkt pierwszy, należy pokazać że zbiór pusty \(\displaystyle{ \varnothing}\) jest elementem każdego zbioru \(\displaystyle{ A\in C}\)

Niech \(\displaystyle{ A\in C}\) Ponieważ \(\displaystyle{ C}\) jest zbiorem zbiorów induktywnych, to \(\displaystyle{ A}\) jest zbiorem induktywnym, a skoro tak to \(\displaystyle{ \varnothing\in A}\) Pokazaliśmy że zbiór pusty jest elementem każdego zbioru \(\displaystyle{ A\in C}\), co należało pokazać


Aby udowodnić punkt drugi, niech \(\displaystyle{ Y\in \bigcap C}\)

Oznacza to dokładnie tyle że \(\displaystyle{ Y\in A}\) dla każdego zbioru \(\displaystyle{ A\in C}\)

Niech \(\displaystyle{ A\in C}\), wnioskujemy że \(\displaystyle{ Y\in A}\) Ponieważ jednak \(\displaystyle{ A\in C}\) jest zbiorem induktywnym, więc \(\displaystyle{ Y \cup \left\{ Y\right\} \in A}\)

Z dowolności wyboru zbioru \(\displaystyle{ A\in C}\) otrzymujemy że \(\displaystyle{ Y \cup \left\{ Y\right\}}\) jest elementem każdego zbioru \(\displaystyle{ A\in C}\), a to oznacza że \(\displaystyle{ Y \cup \left\{ Y\right\} \in \bigcap C}\) Dowód drugiego punktu został zakończony

Zatem \(\displaystyle{ \bigcap C}\) jest zbiorem induktywnym, co kończy dowód lematu