Matematyka.pl

Jakiej mocy są zbiory wszystkich takich funkcji z \(\displaystyle{ \NN}\) w \(\displaystyle{ \NN}\), że:
(a) obraz każdego zbioru skończonego jest skończony,
(b) obraz każdego niepustego zbioru skończonego jest nieskończony,
(c) przeciwobraz każdego zbioru skończonego jest skończony,
(d) przeciwobraz każdego niepustego zbioru skończonego jest nieskończony?

Chyba nie do końca rozumiem treść zadania. Wiem, że moc zbioru wszystkich funkcji z \(\displaystyle{ \NN}\) w \(\displaystyle{ \NN}\) jest \(\displaystyle{ \mathfrak{C}}\). Ale nie rozumiem dlaczego tu są obrazy i przeciwobrazy (być może dlatego, że nie wiem dowodu \(\displaystyle{ \NN \rightarrow \NN = \mathfrak{C}}\)). Byłbym bardzo wdzięczny za jakąś wskazówkę.

W (a), warunek nic nie wnosi bo nierówność kardynałów \(\displaystyle{ \left| f(A)\right| \le \left| A\right| }\) zachodzi zawsze. Z tego samego względu w (b) nie ma takich funkcji. W (c) zauważ, że każda funkcja ze zbioru \(\displaystyle{ \text{id}+\left\{ 0,1\right\}^{\NN} }\) jest dobra oraz \(\displaystyle{ |\text{id}+\left\{ 0,1\right\}^{\NN}| = \mathfrak{c}}\). (d) Może da się to pociągnąć dalej ostatnim spostrzeżeniem wątku Funkcje. Bo po pierwsze nieskończoność przeciwobrazu skończonych zbiorów sprowadza się do warunku, iż dla każdego \(\displaystyle{ n\in\NN}\) mamy \(\displaystyle{ \left| f^{-1}[\left\{ n\right\} ]\right| =\aleph_0}\). A poza tym podejrzewam, że funkcje o tej własności są równoliczne za zbiorem bijekcji z \(\displaystyle{ (\NN \times \NN)^{\NN}}\).

Augustyn Kaczmarek pisze: ↑14 sty 2024, o 19:52 Wiem, że moc zbioru wszystkich funkcji z \(\displaystyle{ \NN}\) w \(\displaystyle{ \NN}\) jest \(\displaystyle{ \mathfrak{C}}\). Ale nie rozumiem dlaczego tu są obrazy i przeciwobrazy (być może dlatego, że nie wiem dowodu \(\displaystyle{ \NN \rightarrow \NN = \mathfrak{C}}\)).

Przykładowy dowód na to, że \(\displaystyle{ \left| \NN^{\NN}\right|= \mathfrak{c} }\) można oprzeć na tym, że \(\displaystyle{ \{0,1\}^{\NN}}\) jest mniejsze w sensie inkluzji od \(\displaystyle{ \NN^{\NN}}\) i w zasadzie jest to zbiór Cantora (który ma moc \(\displaystyle{ \mathfrak{c}}\)). Albo \(\displaystyle{ \{0,1\}^{\NN}}\) traktujemy standardowo jak ciągi nieskończone. Ponieważ każdą liczbę z \(\displaystyle{ \RR}\) można zapisać binarnie (niekoniecznie jednoznacznie ale to nie szkodzi) właśnie jako taki ciąg to \(\displaystyle{ \left| \RR\right| \le \left| \{0,1\}^{\NN}\right| }\).

Augustyn Kaczmarek pisze: ↑14 sty 2024, o 19:52Chyba nie do końca rozumiem treść zadania. Wiem, że moc zbioru wszystkich funkcji z \(\displaystyle{ \NN}\) w \(\displaystyle{ \NN}\) jest \(\displaystyle{ \mathfrak{C}}\). Ale nie rozumiem dlaczego tu są obrazy i przeciwobrazy

Porównanie: wszystkich liczb rzeczywistych jest kontinuum. Jeśli wybierzemy tylko nieujemne, to takich liczb nadal jest kontinuum. Ale jeśli wybierzemy takie, które są miejscami zerowymi funkcji sinus, to jest ich przeliczalnie wiele.

Podobnie jest u Ciebie: zamiast wszystkich możliwych funkcji \(\displaystyle{ \mathbb{N} \to \mathbb{N}}\), których jest kontinuum, rozważamy tylko takie, które mają określoną własność. Wtedy takich funkcji może zrobić się mniej, ale może być ich tyle samo. Zadanie polega na podaniu, ile ich dokładnie jest. Obraz jest tylko narzędziem, by sformułować odpowiednią własność funkcji.