Zbiory nieskończone

[NumberTwo]

Zad.1 Pokazać, że jeśli zbiór \(\displaystyle{ X}\) jest nieskończony (tzn. nie jest równoliczny z żadnym zbiorem skończonym), to zawiera on podzbiór równoliczny ze zbiorem liczb naturalnych.
Zad.2 Pokazać, że jeśli zbiór \(\displaystyle{ X}\) jest nieskończony \(\displaystyle{ a ∈ X}\) to zbiory \(\displaystyle{ X}\) oraz \(\displaystyle{ X − \{a\}}\) są równoliczne. Uogólnić (i udowodnić), że fakt ten jest prawdziwy, gdy \(\displaystyle{ {a}}\) zastąpimy dowolnym skończonym podzbiorem zbioru \(\displaystyle{ X}\).

[Dasio11]

1. Wystarczy wykazać, że istnieje ciąg różnowartościowy \(\displaystyle{ (x_n)}\) o wartościach w \(\displaystyle{ X}\), bo taki ciąg jest bijekcją z liczb naturalnych na zbiór swoich wyrazów, który jest podzbiorem \(\displaystyle{ X}\). Konstrukcja jest rekurencyjna: dla ustalonego \(\displaystyle{ n \in \NN}\) zakładamy, że wyrazy \(\displaystyle{ x_1, \ldots, x_{n-1}}\) są już skonstruowane w taki sposób, że \(\displaystyle{ x_i \neq x_j}\) dla \(\displaystyle{ i \neq j}\). Wtedy musi istnieć element \(\displaystyle{ x \in X \setminus \{ x_1, x_2, \ldots, x_{n-1} \}}\), bo w przeciwnym razie zachodziłoby \(\displaystyle{ X = \{ x_1, x_2, \ldots, x_{n-1} \}}\), tj. \(\displaystyle{ X}\) byłby skończony. Wystarczy zdefiniować \(\displaystyle{ x_n := x}\).

Pozostaje zauważyć, że tak skonstruowany ciąg jest różnowartościowy, co kończy dowód.

[Jan Kraszewski]

2. Tu jest napisane, co trzeba zrobić: Wskaż bijekcję.

JK

[Jakub Gurak]

Zad.1 Pokazać, że jeśli zbiór \(\displaystyle{ X}\) jest nieskończony (tzn. nie jest równoliczny z żadnym zbiorem skończonym), to zawiera on podzbiór równoliczny ze zbiorem liczb naturalnych.

W tym celu wykażemy, że zbiór liczb naturalnych jest najmniejszym, względem mocy, zbiorem nieskończonym. Z tego faktu łatwo wynika nasze zadanie.

Dowód wymaga aksjomatu wyboru (dowodu, że wymaga nie znam).

DOWÓD:

Ustalmy dowolny zbiór nieskończony \(\displaystyle{ X}\). Pokażemy, że \(\displaystyle{ \left| \NN\right| \le \left| X\right| }\) .W tym celu określamy funkcję różnowartościową z \(\displaystyle{ \NN}\) do \(\displaystyle{ X}\). W tym celu użyjemy twierdzenia o funkcji wyboru, równoważnego aksjomatowi wyboru. Zastosujemy je do zbioru \(\displaystyle{ P\left( X\right) \setminus \left\{ \emptyset \right\} }\) dostając funkcję \(\displaystyle{ g:P\left( X\right) \setminus \left\{ \emptyset \right\} \rightarrow X}\), taką, że \(\displaystyle{ g\left( B\right) \in B}\), dla każdego zbioru \(\displaystyle{ B}\), jeśli tylko \(\displaystyle{ B}\) jest niepustym podzbiorem zbioru \(\displaystyle{ X}\).

Aby udowodnić istnienia żądanej funkcji zastosujemy twierdzenie o definiowaniu przez indukcję. Dzięki niemu dostaniemy funkcję \(\displaystyle{ h: \NN \rightarrow P\left( X\right)}\), taką, że:

\(\displaystyle{ h\left( 0\right)=\left\{ g\left( X\right) \right\};}\) oraz:

\(\displaystyle{ h(n')=h(n) \cup \left\{ g\left( X \setminus h(n) \ \right) \right\}, \hbox { dla każdego } n\in \NN. }\)

Jest to funkcja, która tak: na początek wybieramy z całego zbioru \(\displaystyle{ X}\) jeden element, i na początek, w kroku zerowym, tworzymy zbiór jednoelementowy złożony z tego elementu, a dalej, w dalszych krokach, funkcja wyrzuca z całego zbioru \(\displaystyle{ X}\) ostatnio rozpatrywany zbiór, i wybiera, z pozostałej części, jego jeden element, i go dodaje do tego ostatnio rozpatrywanego zbioru, czyli jest to funkcja, która każdej liczbie naturalnej przypisuje zbiór większy o jeden element niż przypisany poprzedniej liczbie naturalnej- przepiękna funkcja.

Aby otrzymać żądaną injekcję wystarczy zdefiniować funkcję

\(\displaystyle{ f:\NN \rightarrow X}\), w poniższy sposób:

\(\displaystyle{ f(n)=x \Longleftrightarrow h(n') \setminus h(n)=\left\{ x\right\}. }\)

Funkcją \(\displaystyle{ f}\) jest dobrze zdefiniowana, gdyż dla każdego \(\displaystyle{ n}\) naturalnego zbiór \(\displaystyle{ h(n') \setminus h(n)}\) jest jednoelementowy, i jest funkcją różnowartościową.\(\displaystyle{ \square}\)


Łatwo teraz będzie udowodnić nasze zadanie:

Ustalmy dowolny zbiór nieskończony \(\displaystyle{ X}\). Ponieważ, wiemy już, że zbiór liczb naturalnych jest najmniejszym zbiorem nieskończonym, a więc \(\displaystyle{ \left| \NN\right| \le \left| X\right|.}\) A zatem istnieje funkcja różnowartościowa \(\displaystyle{ f}\) z \(\displaystyle{ \NN}\) do \(\displaystyle{ X}\). Funkcja \(\displaystyle{ f}\) jest różnowartościową i 'na' zbiór wartości \(\displaystyle{ f_P}\), a zatem zbiór \(\displaystyle{ f_P}\) jest zbiorem równolicznym z \(\displaystyle{ \NN.}\) Ponieważ ten zbiór ze swej natury jest podzbiorem zbioru \(\displaystyle{ X}\), to jest jego przeliczalnym podzbiorem.\(\displaystyle{ \square}\)

[matmatmm]

Do zadania 1 zaproponuję dowód alternatywny oparty na następującym fakcie:

Fakt 1. Jeśli \(\displaystyle{ X}\) jest nieskończony oraz istnieje funkcja różnowartościowa \(\displaystyle{ f:X\rightarrow\NN}\), to \(\displaystyle{ X}\) jest równoliczny z \(\displaystyle{ \NN}\).

Dowód faktu 1 (bez pewnika wyboru):
Oznaczmy \(\displaystyle{ A=f[X]}\) i zauważmy, że zbiór \(\displaystyle{ A}\) jest nieograniczony z góry, bo w przeciwnym razie \(\displaystyle{ X}\) byłby skończony. Wobec tego możemy określić indukcyjnie ciąg \(\displaystyle{ (a_n)}\) o wartościach w \(\displaystyle{ A}\) przez zależności

\(\displaystyle{ a_0:=\min A}\)
\(\displaystyle{ a_{n+1}:=\min A\cap (a_n,\infty)}\)

Ciąg \(\displaystyle{ (a_n)}\) jest różnowartościowy, więc z twierdzenia Cantora-Bernsteina \(\displaystyle{ A}\) jest równoliczny z \(\displaystyle{ \NN}\).

Teraz zadanie 1 wynika w łatwy sposób ze "spójności":
Dla dowolnych zbiorów \(\displaystyle{ X,Y}\) zachodzi \(\displaystyle{ |X|\leq |Y|}\) lub \(\displaystyle{ |X|\geq |Y|}\).

[Jan Kraszewski]

Teraz zadanie 1 wynika w łatwy sposób ze "spójności":
Dla dowolnych zbiorów \(\displaystyle{ X,Y}\) zachodzi \(\displaystyle{ |X|\leq |Y|}\) lub \(\displaystyle{ |X|\geq |Y|}\).

Której dowód wymaga pewnika wyboru...

JK