Obraz zbioru skończonego jest skończony.

[matmatmm]

A ja zastanawiam się jeszcze, jak tutaj

(...) to łatwo można zauważyć więcej: dla dowolnej funkcji \(\displaystyle{ f:X \rightarrow Y}\) jej zbiór wartości \(\displaystyle{ f_P}\) jest mocy nie większej niż dziedzina \(\displaystyle{ X}\).

Zaobserwować jest to bardzo łatwo( choć takie twierdzenie chyba jest = w książce Kuratowski,Mostowski. Teoria Mnogości), gdyż każda funkcja przypisuję każdemu elementowi zbioru \(\displaystyle{ X}\) co najwyżej jedną wartość (nie więcej). Wobec czego zamieniamy jeden element na jeden, albo wiele elementów na jeden, więc dziedzina \(\displaystyle{ X}\) musi być liczniejsza niż zbiór wartości.

Formalnie- trzeba to pokazać, definiując funkcję różnowartościową ze zbioru \(\displaystyle{ f_{P}}\) w zbiór \(\displaystyle{ X}\). Wystarczy elementowi \(\displaystyle{ y\in f_P}\) przypisać element jego przeciwobrazu \(\displaystyle{ \stackrel{ \rightarrow }{f ^{-1} } \left\{ y\right\} .}\) Potrzeba tu aksjomatu wyboru na podobnej zasadzie jak tu, co wyjaśniłem. Taka funkcja będzie różnowartościowa, gdyż przeciwobrazy zbiorów jednoelementowych są rozłączne. A więc \(\displaystyle{ \left| f_P\right| \le \left| f_L=X\right|.}\)

ominąć pewnik wyboru, gdy \(\displaystyle{ X}\) jest skończony. Wszak krl napisał, że obraz zbioru skończonego jest skończony już w ZF. Mniemam, że prawdziwe jest twierdzenie (w ZF), że obraz zbioru dobrze uporządkowanego można dobrze uporządkować (bez założenia różnowartościowości).

[Dasio11]

Niech \(\displaystyle{ X}\) będzie dobrze uporządkowany i załóżmy, że \(\displaystyle{ f : X \to Y}\) jest surjekcją. Na \(\displaystyle{ X}\) istnieje funkcja wyboru (niewymagająca aksjomatu wyboru), a za jej pomocą łatwo skonstruować funkcję \(\displaystyle{ g : Y \to X}\), taką że \(\displaystyle{ f \circ g = \mathrm{id}_Y}\). W szczególności \(\displaystyle{ g}\) jest różnowartościowa, no a dalej wiadomo.

A dla zbiorów skończonych rzeczony fakt był udowodniony w pierwszym poście w tym wątku, tylko trzeba się przypatrzeć.

[Jakub Gurak]

A ja zastanawiam się jeszcze, jak tutaj

dla dowolnej funkcji \(\displaystyle{ f:X \rightarrow Y}\) jej zbiór wartości \(\displaystyle{ f_P}\) jest mocy nie większej niż dziedzina \(\displaystyle{ X}\).

ominąć pewnik wyboru, gdy \(\displaystyle{ X}\) jest skończony.

Nie jestem specjalistą, ale myślę tak: Rozważmy rodzinę \(\displaystyle{ \mathbb {B}:}\)

\(\displaystyle{ \mathbb{B}=\left\{ \stackrel{ \rightarrow } {f ^{-1} }\left\{ y\right\}\Bigl| \ \ y \in f _{ P} \right\}.}\)

rodzinę wszystkich przeciwobrazów zbiorów jednoelementowych o elemencie że zbioru wartości \(\displaystyle{ f _{P}.}\)

Takie przeciwobrazy są oczywiście rozłączne, łatwo sprawdzić, że ich suma to zbiór \(\displaystyle{ X}\). Zatem rodzina \(\displaystyle{ B}\) tworzy rozkład zbioru \(\displaystyle{ X}\). Wiemy, że rodzina \(\displaystyle{ B}\) jest mocy nie wiekszej niż zbiór \(\displaystyle{ X}\), a bez aksjomatu wyboru (tak mi się wydaje ) zachodzi to dla rozkładów zbiorów przeliczalnych. Zaryzykuję więc stwierdzenie, że bez aksjomatu wyboru, w naszym przypadku, rodzina \(\displaystyle{ B}\) jest mocy nie większej niż zbiór \(\displaystyle{ X}\) (to na pewno prawda, tylko nie jestem pewny czy bez aksjomatu wyboru też tak jest ). Ponieważ \(\displaystyle{ X}\) jest skończony, więc również zbiór \(\displaystyle{ B}\) jest skończony( mogę to łatwo udowodnić ). Skoro rodzina \(\displaystyle{ B}\) jest skończona, i jest rozkładem zbioru \(\displaystyle{ X}\), to można do niej zastosować aksjomat wyboru, ale bez aksjomatu wyboru możemy utworzyć zbiór wybierający po jednym elemencie- ponieważ rodzina \(\displaystyle{ B}\) jest skończona , więc wystarczy z dowolnego niepustego zbioru \(\displaystyle{ A \in B}\) wyciągnąć pewien element \(\displaystyle{ x _{A},}\) otrzymując skończenie wiele elementów \(\displaystyle{ x _{1},x _{2},\ldots ,x _{n}}\), a ze skończonej ilości elementów możemy utworzyć zbiór \(\displaystyle{ \left\{ x _{1},x _{2},\ldots, x _{n} \right\}.}\) Ponieważ wybraliśmy po jednym elemencie z przeciwobrazów zbiorów jednoelementowych, które są rozłączne, to funkcja \(\displaystyle{ g:y \in f _{P} \rightarrow x _{i} \in \stackrel{ \rightarrow } {f ^{} {-1} }\left\{ y\right\} =:X _{i}}\) jest różnowartościowa. A więc \(\displaystyle{ \left| f _{P} \right| \le \left| X \right|.\square}\)

[matmatmm]

Takie przeciwobrazy są oczywiście rozłączne, łatwo sprawdzić, że ich suma to zbiór \(\displaystyle{ X}\). Zatem rodzina \(\displaystyle{ B}\) tworzy rozkład zbioru \(\displaystyle{ X}\). Wiemy, że rodzina \(\displaystyle{ B}\) jest mocy nie wiekszej niż zbiór \(\displaystyle{ X}\), a bez aksjomatu wyboru (tak mi się wydaje ) zachodzi to dla rozkładów zbiorów przeliczalnych. Zaryzykuję więc stwierdzenie, że bez aksjomatu wyboru, w naszym przypadku, rodzina \(\displaystyle{ B}\) jest mocy nie większej niż zbiór \(\displaystyle{ X}\) (to na pewno prawda, tylko nie jestem pewny czy bez aksjomatu wyboru też tak jest ). Ponieważ \(\displaystyle{ X}\) jest skończony, więc również zbiór \(\displaystyle{ B}\) jest skończony( mogę to łatwo udowodnić ). Skoro rodzina \(\displaystyle{ B}\) jest skończona, i jest rozkładem zbioru \(\displaystyle{ X}\), to można do niej zastosować aksjomat wyboru, ale bez aksjomatu wyboru możemy utworzyć zbiór wybierający po jednym elemencie- ponieważ rodzina \(\displaystyle{ B}\) jest skończona , więc wystarczy z dowolnego niepustego zbioru \(\displaystyle{ A \in B}\) wyciągnąć pewien element \(\displaystyle{ x _{A},}\) otrzymując skończenie wiele elementów \(\displaystyle{ x _{1},x _{2},\ldots ,x _{n}}\), a ze skończonej ilości elementów możemy utworzyć zbiór \(\displaystyle{ \left\{ x _{1},x _{2},\ldots, x _{n} \right\}.}\) Ponieważ wybraliśmy po jednym elemencie z przeciwobrazów zbiorów jednoelementowych, które są rozłączne, to funkcja \(\displaystyle{ g:y \in f _{P} \rightarrow x _{i} \in \stackrel{ \rightarrow } {f ^{} {-1} }\left\{ y\right\} =:X _{i}}\) jest różnowartościowa. A więc \(\displaystyle{ \left| f _{P} \right| \le \left| X \right|.\square}\)

Ja bym ten fragment zastąpił takim rozumowaniem: Elementy rodziny \(\displaystyle{ \mathbb{B}}\) są podzbiorami \(\displaystyle{ X}\), a \(\displaystyle{ X}\) jako zbiór skończony jest dobrze uporządkowany (bez aksjomatu wyboru). Wobec tego możemy utworzyć funkcję \(\displaystyle{ h:\mathbb{B}\rightarrow X}\) o wzorze \(\displaystyle{ h(B):=\min B}\). Funkcja ta jest w oczywisty sposób różnowartościowa (gdyż elementy \(\displaystyle{ \mathbb{B}}\) są rozłączne), co dowodzi \(\displaystyle{ |\mathbb{B}|\leq |X|}\). Z drugiej strony rodzina \(\displaystyle{ \mathbb{B}}\) jest równoliczna z \(\displaystyle{ f[X]}\).

Przy okazji jest w tym dowodzie metoda dowodu wspomnianego przez ciebie faktu, że rozkład zbioru przeliczalnego ma moc nie większą niż ten zbiór (bez pewnika wyboru).

[Jakub Gurak]

Zrozumiałem ostatnio dowód z ważniaka mówiący, że obraz zbioru skończonego przez funkcję jest zbiorem skończonym. Przedstawię teraz dowód tego faktu.

Podajmy najpierw pewien Lemat.

Lemat 1. Jeśli \(\displaystyle{ \left\{ \right\} \neq x \subset \NN}\) jest niepustym zbiorem liczb naturalnych von Neumanna, to \(\displaystyle{ \bigcap x \in x,}\) i zbiór \(\displaystyle{ \bigcap x}\) jest najmniejszą liczbą naturalną w zbiorze \(\displaystyle{ x.}\)

Podajmy najpierw jeszcze jeden Lemat.

Lemat 2.Dla dowolnego \(\displaystyle{ n \in \NN}\), i dla dowolnego zbioru \(\displaystyle{ x \subset \NN}\), jeśli \(\displaystyle{ x \cap n \neq \left\{ \right\}}\), to \(\displaystyle{ \bigcap x \in x.}\)

Czyli dla dowolnej liczby naturalnej \(\displaystyle{ n}\) i dla dowolnego zbioru \(\displaystyle{ x}\) złożonego z liczb naturalnych, jeśli \(\displaystyle{ x \cap n \neq \left\{ \right\}}\), czyli jeśli zbiór \(\displaystyle{ x}\) zawiera, jako element, liczbę naturalną silnie mniejszą od \(\displaystyle{ n}\), to ten zbiór \(\displaystyle{ x}\) ma element najmniejszy ( którym jest \(\displaystyle{ \bigcap x}\) ).

Przypomnijmy, dowodzi się, że dla dowolnych liczb naturalnych \(\displaystyle{ n,m}\), mamy:

\(\displaystyle{ n \in m \hbox{ albo } m \in n \hbox{ albo } n =m ,}\)

gdzie dokładnie jeden z tych trzech warunków jest spełniony.

Przedstawiam teraz indukcyjny dowód tego (poprzedniego ) faktu:

DOWÓD TEGO FAKTU::    

Niech:

\(\displaystyle{ P= \left\{ n \in \NN: \ \ \bigwedge\limits_{x \subset \NN} x \cap n \neq \emptyset \Longrightarrow \bigcap x \in x \right\}.}\)

Czyli jest to zbiór liczb naturalnych dla których twierdzenie zachodzi.

Wykazujemy indukcyjnie, że \(\displaystyle{ P=\NN.}\)

Niewątpliwie \(\displaystyle{ 0=\emptyset \in P,}\) bo dla dowolnego zbioru \(\displaystyle{ x \subset \NN}\) fałszem jest \(\displaystyle{ x \cap \emptyset =\emptyset \neq \emptyset}\), a zatem założenia implikacji nie są spełnione, a więc cała implikacja jest prawdziwa; i to dla dowolnego zbioru \(\displaystyle{ x}\), a zatem \(\displaystyle{ 0 \in P.}\)

Krok indukcyjny: Załóżmy, że \(\displaystyle{ n \in P}\) i dowiedźmy, że \(\displaystyle{ n' \in P.}\)

W tym celu ustalmy dowolny zbiór \(\displaystyle{ x \subset \NN}\), taki, że \(\displaystyle{ x \cap n' \neq \left\{ \right\}}\). Ponieważ \(\displaystyle{ n'= n \cup \left\{ n\right\}}\) , to rozważmy dwa przypadki:

Jeśli \(\displaystyle{ x \cap n \neq \left\{ \right\}}\) , to do liczby naturalnej \(\displaystyle{ n}\) i do zbioru \(\displaystyle{ x}\) możemy zastosować założenie indukcyjne i otrzymać, że \(\displaystyle{ \bigcap x \in x}\), co należało pokazać.

Jeśli \(\displaystyle{ x \cap n=\emptyset}\), to ponieważ \(\displaystyle{ x \cap n' \neq \left\{ \right\} }\), a \(\displaystyle{ n'=n \cup \left\{ n\right\}}\), więc \(\displaystyle{ x \cap n'=\left\{ n\right\}.}\)
Wtedy \(\displaystyle{ n \in x.}\) Na mocy przytoczonego faktu, dla każdego \(\displaystyle{ z \in x}\), mamy: \(\displaystyle{ z \in n}\) lub \(\displaystyle{ n=z}\) lub \(\displaystyle{ n \in z}\), ale nie może być \(\displaystyle{ z \in n}\), bo wtedy \(\displaystyle{ z \in n \cap x=x \cap n=\emptyset}\)- sprzeczność.

Wobec czego \(\displaystyle{ n=z}\) lub \(\displaystyle{ n \in z}\), co daje (\(\displaystyle{ z \in \NN}\)), że \(\displaystyle{ n \subset z}\). Otrzymujemy zatem, że dla każdego \(\displaystyle{ z \in x}\): \(\displaystyle{ n \subset z}\), więc również (z własności przecięcia) \(\displaystyle{ n \subset \bigcap x}\), a ponieważ \(\displaystyle{ n \in x}\), więc \(\displaystyle{ \bigcap x \subset n}\), co daje \(\displaystyle{ \bigcap x= n \in x}\), czyli \(\displaystyle{ \bigcap x \in x}\), co należało wykazać.

Na mocy zasady indukcji \(\displaystyle{ P=\NN}\), czyli dla dowolnej liczby naturalnej \(\displaystyle{ n}\), i dla dowolnego zbioru \(\displaystyle{ x \subset \NN}\), jeśli \(\displaystyle{ x\cap n \neq \emptyset}\), to \(\displaystyle{ \bigcap x \in x.\square}\)

Przejdźmy do dowodu pierwszego Lematu:

DOWÓD TEGO FAKTU:

Niech \(\displaystyle{ \left\{ \right\} \neq x \subset \NN}\) będzie niepustym podzbiorem zbioru liczb naturalnych. A zatem istnieje liczba naturalna \(\displaystyle{ n}\), taka, że \(\displaystyle{ n \in x}\).
Rozważmy jej następnik \(\displaystyle{ n'}\). Na mocy dowodu powyżej \(\displaystyle{ n' \in P}\). Stosując zatem powyższą własność do liczby naturalnej \(\displaystyle{ n' }\) i do zbioru \(\displaystyle{ x}\) (mamy \(\displaystyle{ n' \cap x \neq \emptyset}\), gdyż \(\displaystyle{ n \in n' \cap x}\)) otrzymujemy \(\displaystyle{ \bigcap x \in x \subset \NN}\). A zatem zbiór \(\displaystyle{ \bigcap x}\) jest liczbą naturalną i elementem zbioru \(\displaystyle{ x}\).
Ponieważ zbiór \(\displaystyle{ \bigcap x}\) jest podzbiorem każdego zbioru \(\displaystyle{ a \in x}\), które to zbiory są liczbami naturalnymi i zbiór \(\displaystyle{ \bigcap x}\) jest liczbą naturalną, więc jest od nich mniejszy lub równy, i ten zbiór jest elementem zbioru \(\displaystyle{ x}\), zatem ten zbiór \(\displaystyle{ \bigcap x}\) jest najmniejszą liczbą naturalną w zbiorze \(\displaystyle{ x.\square}\)


Wykażemy teraz, że obraz zbioru skończonego poprzez funkcję jest zbiorem skończonym, tzn.:

Niech \(\displaystyle{ A}\) będzie zbiorem skończonym, i niech \(\displaystyle{ B}\) będzie zbiorem, a \(\displaystyle{ f:A \rightarrow B}\) dowolną funkcją. Wykażemy, że \(\displaystyle{ \stackrel{ \rightarrow }{f} \left( A\right) = f_P}\) jest zbiorem skończonym.

DOWÓD TEGO FAKTU:

Ponieważ zbiór \(\displaystyle{ A}\) jest zbiorem skończonym, więc \(\displaystyle{ A\sim n}\) dla pewnej liczby naturalnej \(\displaystyle{ n}\). A zatem istnieje bijekcja \(\displaystyle{ g: n \rightarrow A}\).

Definiujemy funkcję \(\displaystyle{ h: f_P \rightarrow n}\) poniższym wzorem:

\(\displaystyle{ h\left( b\right)= \bigcap \stackrel{ \rightarrow }{\left( f\circ g\right) ^{-1} } \left( \left\{ b\right\} \right),}\)

funkcję, która dla dowolnego elementu \(\displaystyle{ b \in f_P}\) zwraca przekrój przeciwobrazów zbioru jednopunktowego \(\displaystyle{ \left\{ b\right\}}\) przez złożenie funkcji \(\displaystyle{ g}\) i funkcji \(\displaystyle{ f}\) , czyli, na mocy Lematów powyżej, gdyż takie przeciwobrazy są podzbiorami zbioru \(\displaystyle{ n}\), więc jest to najmniejsza taka liczba naturalna, czyli jest to najmniejsza liczba naturalna, która jest przekształcana przez funkcję \(\displaystyle{ g}\) w zbiór \(\displaystyle{ \stackrel { \rightarrow }{f ^{-1} } \left( \left\{ b\right\} \right)}\). Oto ilustracja tego faktu: \(\displaystyle{ \\}\)

\(\displaystyle{ \\}\) Ponieważ przeciwobrazy zbiorów jednoelementowych są rozłączne, a element najmniejszy danego zbioru jest jego elementem, a zatem funkcja \(\displaystyle{ h}\) nie może dwóm różnym elementom przypisywać tego samego elementu, a zatem jest to funkcja różnowartościowa.
I jest to funkcja 'na' zbiór wartości \(\displaystyle{ h_P \subset n.}\) A zatem \(\displaystyle{ f_P\sim h_P,}\) gdzie zbiór \(\displaystyle{ h_P,}\) jako podzbiór liczby naturalnej, zbioru skończonego, jest zbiorem skończonym, czyli jest to zbiór równoliczny z pewną liczbą naturalną \(\displaystyle{ m}\); z przechodniości równoliczności zbiór \(\displaystyle{ f_P= \stackrel{ \rightarrow }{f} \left( A\right)}\) jest zbiorem równolicznym z liczbą naturalną \(\displaystyle{ m}\), a więc jest zbiorem skończonym.\(\displaystyle{ \square}\)