Przypominam najpierw parę rzeczy:
Zbiór nazywamy skończonym, gdy jest równoliczny z pewną liczbą naturalną von Neumanna \(\displaystyle{ n}\).
Zbiór nazywamy nieskończonym, gdy nie jest skończony.
Fakt: Każdy podzbiór zbioru skończonego jest skończony.
Fakt: Suma zbioru skończonego i jednoelementowego jest zbiorem skończonym. Ogólniej: Suma dwóch zbiorów skończonych jest zbiorem skończonym(prosty dowód indukcyjny ze względu na ilość elementów drugiego zbioru).
Jeśli \(\displaystyle{ X}\) jest zbiorem skończonym, to jego zbiór potęgowy \(\displaystyle{ P(X)}\) jest zbiorem skończonym:
DOWÓD: Wykażemy indukcyjnie, że dla każdej liczby naturalnej von Neumanna \(\displaystyle{ n}\), jeśli zbiór \(\displaystyle{ X\sim n}\), to zbiór \(\displaystyle{ P(X)}\) jest skończony. Jeśli \(\displaystyle{ X\sim 0=\emptyset}\), to \(\displaystyle{ X=\emptyset}\), (gdyż bijekcja na zbiorze niepustym nie może prowadzić w zbiór pusty). Wtedy \(\displaystyle{ P(X)=P(\emptyset)=\left\{ \emptyset\right\}=1\sim 1\in\NN}\), a więc zbiór \(\displaystyle{ P(X)}\) jest skończony.
Krok indukcyjny: Ustalmy dowolne \(\displaystyle{ n}\) naturalne, i przypuśćmy, że zbiór potęgowy dowolnego zbioru równolicznego ze zbiorem \(\displaystyle{ n}\) jest skończony. Wykażemy, że również zbiór potęgowy dowolnego zbioru równolicznego z \(\displaystyle{ n' }\) jest skończony. Ustalmy dowolny zbiór \(\displaystyle{ X\sim n'}\). Wtedy \(\displaystyle{ X \neq \emptyset}\)( inaczej by było \(\displaystyle{ n'=0}\), co nie może mieć miejsca), a więc istnieje \(\displaystyle{ x\in X}\). Ustalmy taki element. Wtedy mamy również bijekcję \(\displaystyle{ f: X \rightarrow n'.}\) Dość łatwo można pokazać, że jeśli z różnej od zera liczby naturalnej von Neumanna \(\displaystyle{ n}\) usuniemy jeden dowolny element, to powstały zbiór będzie równoliczny z (\(\displaystyle{ n-1}\)). W związku z czym \(\displaystyle{ n' \setminus \left\{ f(x)\right\}\sim n}\). Ponieważ mamy bijekcję między \(\displaystyle{ X}\) a \(\displaystyle{ n' }\), więc również \(\displaystyle{ X \setminus \left\{ x\right\}\sim n' \setminus \left\{ f(x)\right\}\sim n.}\) Ponieważ \(\displaystyle{ X \setminus \left\{ x\right\}\sim n}\), więc na mocy założenia indukcyjnego jego zbiór potęgowy jest skończony, tzn. \(\displaystyle{ P\left( X \setminus \left\{ x\right\}\right) \sim m}\), dla pewnego \(\displaystyle{ m}\) naturalnego. Niech \(\displaystyle{ P'}\) oznacza dopełnienie \(\displaystyle{ P\left( X \setminus \left\{ x\right\}\right)}\) do zbioru \(\displaystyle{ P(X)}\). Łatwo zauważyć, że funkcja \(\displaystyle{ g:P\left( X \setminus \left\{ x\right\}\right) \rightarrow P' }\) określona jako:
\(\displaystyle{ g(A)=A \cup\left\{ x\right\}}\)
jest bijekcją. A zatem zbiory \(\displaystyle{ P\left( X \setminus \left\{ x\right\}\right), P'}\) są równoliczne,i skończone. W efekcie \(\displaystyle{ P(X) }\) jako suma dwóch zbiorów skończonych jest zbiorem skończonym. Dowolność zbioru \(\displaystyle{ X}\) kończy dowód kroku indukcyjnego. Zasada indukcji matematycznej daje przytoczoną własność, a zatem jeśli \(\displaystyle{ X}\) jest zbiorem skończonym, czyli równolicznym z pewną liczbą naturalną \(\displaystyle{ n}\), to ta udowodniona własność daje nam, że zbiór \(\displaystyle{ P(X)}\) jest skończony.
Och te bijekcję...Fakt: Jeśli \(\displaystyle{ X}\) jest zbiorem, to każda rodzina podzbiorów \(\displaystyle{ X}\) jest uporządkowana przez inkluzję.
Niech \(\displaystyle{ \left( X, \le \right) }\) będzie zbiorem uporządkowanym. Element \(\displaystyle{ a\in X}\) nazywamy maksymalnym, gdy nie ma w \(\displaystyle{ X }\) elementów silnie większych od \(\displaystyle{ a}\), tzn. takich elementów \(\displaystyle{ b\in X}\), aby \(\displaystyle{ a<b}\). (Gdy nie ma od niego elementów silnie większych).
Fakt: W skończonym niepustym zbiorze uporządkowanym \(\displaystyle{ \left( X, \le \right) }\) jest zawsze element maksymalny.(Nieformalnie, wyciągamy na początek jeden element, jeśli jest to element maksymalny to koniec, a jeśli nie to można do niego dobrać większy, i jeśli jest to element maksymalny to koniec, itd., więc gdyby nie było elementu maksymalnego to można by było utworzyć łańcuch nieskończony na skończonym zbiorze \(\displaystyle{ X}\)).
Możemy zatem w końcu sformułować definicję:
Zbór \(\displaystyle{ X}\) nazywamy skończonym w sensie Tarskiego, gdy w każdej niepustej rodzinie podzbiorów \(\displaystyle{ X}\) istnieje zbiór maksymalny( pod względem inkluzji).
Zbiór nazywamy nieskończonym w sensie Tarskiego, gdy nie jest skończony w sensie Tarskiego.
I nareszcie, wykażemy, że zbiór jest skończony, wtedy i tylko wtedy, gdy jest skończony w sensie Tarskiego.
Dowód: \(\displaystyle{ \Longrightarrow}\) Niech zbiór \(\displaystyle{ X}\) będzie skończony. Niech \(\displaystyle{ \mathbb{B}}\) będzie niepustą rodziną podzbiorów \(\displaystyle{ X}\). Wiemy, że jest ona uporządkowana przez inkluzję. Ponadto ponieważ, \(\displaystyle{ X}\) jest skończony, to rodzina jego wszystkich podzbiorów jest skończona, a więc również \(\displaystyle{ \mathbb{B}}\) jest skończona. Zatem \(\displaystyle{ \left( \mathbb{B},\subset\right)}\) jest niepustym skończonym zbiorem(rodziną) uporządkowaną. Zatem ma zbiór maksymalny. A więc \(\displaystyle{ X}\) jest skończony w sensie Tarskiego.
\(\displaystyle{ \Leftarrow}\) (ciekawszy) Niech zbiór \(\displaystyle{ X}\) będzie skończony w sensie Tarskiego. Wykażemy, że jest również skończony. Rozważmy rodzinę \(\displaystyle{ \mathbb{B}}\) wszystkich skończonych podzbiorów \(\displaystyle{ X}\):
\(\displaystyle{ \mathbb{B}=\left\{ A\subset X\Bigl| \ \ A\hbox{ jest skończony }\right\}.}\)
Rodzina \(\displaystyle{ \mathbb{B}}\) jest niepusta, gdyż \(\displaystyle{ \emptyset\in \mathbb{B}, }\) gdyż \(\displaystyle{ \emptyset}\) jest skończony( nie lubię tak pisać, ale ściśle rzecz biorąc zbiór pusty jest skończony, gdyż \(\displaystyle{ \emptyset\sim\emptyset=0\in\NN }\)). A zatem \(\displaystyle{ \emptyset\in \mathbb{B}, }\) a więc \(\displaystyle{ \mathbb{B} \neq\emptyset }\)
( dla niedowiarków: przecież \(\displaystyle{ \emptyset\not\in\emptyset}\), bo zbiór pusty nie ma żadnych elementów). Ponieważ zbiór \(\displaystyle{ X}\) jest skończony w sensie Tarskiego, więc w rodzinie \(\displaystyle{ \mathbb{B}}\) jest zbiór maksymalny \(\displaystyle{ A\in\mathbb{B}}\). Ponieważ \(\displaystyle{ A\in\mathbb{B}}\), więc \(\displaystyle{ A}\) jest skończonym podzbiorem \(\displaystyle{ X}\). Jeśli zatem \(\displaystyle{ A=X}\), to \(\displaystyle{ X}\) jest skończony, i dowód jest zakończony. Pozostaje przyjąć, że tak nie jest, czyli że \(\displaystyle{ A\subsetneq X}\). Wtedy istnieje element \(\displaystyle{ x\in X}\), taki, że \(\displaystyle{ x\not\in A }\)(spoza zbioru \(\displaystyle{ A}\)). Wtedy \(\displaystyle{ B=A \cup \left\{ x\right\} \subset X }\), i ponieważ \(\displaystyle{ A}\) jest skończony, to \(\displaystyle{ B}\) również. Zatem \(\displaystyle{ B\in\mathbb{B}}\). Niewątpliwie \(\displaystyle{ B=A \cup \left\{ x\right\} \supsetneq A }\), a ponieważ \(\displaystyle{ A}\) był elementem maksymalnym, to nie ma w \(\displaystyle{ \mathbb{B}}\) elementów od niego silnie większych. Otrzymaliśmy sprzeczność, która kończy dowód.\(\displaystyle{ \square}\)