Zbiory induktywne
: 31 maja 2016, o 03:50
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
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