Matematyka.pl

Czy istnieje funkcja \(\displaystyle{ \NN \rightarrow \NN}\), która przyjmuje każdą wartość ze zbioru \(\displaystyle{ \NN}\) nieskończenie wiele razy?

Tak. Niech \(\displaystyle{ f}\) będzie taka, że \(\displaystyle{ f(p_i^{ \alpha })=i}\), gdzie \(\displaystyle{ p_i}\) to \(\displaystyle{ i}\)-ta liczba pierwsza oraz \(\displaystyle{ \alpha \in\NN}\) dowolna. Dla pozostałych \(\displaystyle{ n\in \NN}\) które nie są postaci -czystej- potęgi liczby pierwszej kładziemy \(\displaystyle{ 0}\) (bo powiedzmy, że \(\displaystyle{ 0\in\NN}\) i brakowało).

Można też w inny sposób zbiór liczb naturalnych rozłożyć na nieskończoną (przeliczalną) ilość zbiorów przeliczalnych (tzn. równolicznych ze zbiorem \(\displaystyle{ \NN}\)):
Rozważmy zbiór wszystkich liczb naturalnych nieparzystych, oznaczmy go jako \(\displaystyle{ A_0}\). Pozostają zatem do pokrycia wszystkie liczby parzyste. Rozważmy zbiór wszystkich dwukrotności liczb nieparzystych, czyli: \(\displaystyle{ A_1:=\left\{ 2n\Bigl| n \in A_0\right\}}\). Pozostaje zatem do pokrycia dwukrotności liczb parzystych, czyli elementy zbioru \(\displaystyle{ \left\{ 4n\Bigl| n \in \NN\right\}}\). Rozważmy zbiór wszystkich czterokrotności liczb nieparzystych, nazwijmy go jako \(\displaystyle{ A_2}\); pozostają zatem do pokrycia czterokrotności liczb parzystych, czyli elementy zbioru \(\displaystyle{ \left\{ 8n\Bigl| \ n \in \NN\right\}}\) . Dalej rozważamy ośmiokrotności liczb nieparzystych,... itd. W ten sposób otrzymujemy rozkład \(\displaystyle{ \mathbb{B}}\) zbioru liczb naturalnych na przeliczalną rodzinę zbiorów przeliczalnych.
I aby otrzymać żądaną funkcję liczbie naturalnej \(\displaystyle{ n}\) przypisujemy najpierw zbiór \(\displaystyle{ A_m}\) tego rozkładu \(\displaystyle{ \mathbb{B}}\), do którego ta liczba należy (ponieważ jest to rozkład, to taki zbiór jest dokładnie jeden), i następnie przypisujemy temu zbiorowi \(\displaystyle{ A_m \rightarrow m}\) jego numer, i w końcu przypisujemy \(\displaystyle{ n \stackrel{f}{\rightarrow} m}\). Ponieważ każdy zbiór \(\displaystyle{ A_n}\) jest nieskończony, to każda liczba naturalna \(\displaystyle{ n}\) jest przyjmowana
przez funkcję \(\displaystyle{ f}\) nieskończenie wiele razy.

To jakby to samo co wyzej: jesli \(\displaystyle{ n = 2^k m}\) (\(\displaystyle{ m}\) nieparzyste) to \(\displaystyle{ f(n)= k }\)...

Przykładów jest dużo. Niech \(\displaystyle{ \phi:\NN\to\NN \times \NN}\) to dowolna bijekcja. Wtedy zbiory \(\displaystyle{ \phi^{-1}[\left\{ n\right\} \times \NN ]}\) dla \(\displaystyle{ n=0,1,2,\dots}\) zadają podział \(\displaystyle{ \NN}\) na nieskończenie wiele nieskończonych rozłącznych podzbiorów. Jeśli na każdym z nich określimy pewną wartość (powiedzmy \(\displaystyle{ n}\)) to dostaniemy funkcję spełniającą wymagania.

PS być może ten problem jest kompletnie równoważy znajdywaniu bijekcji \(\displaystyle{ \phi:\NN\to\NN \times \NN}\). Odwrotnie gdyby mieć funkcję \(\displaystyle{ f}\) taką jak w zadaniu to pewnie łatwo bijekcję znaleźć.