Matematyka.pl

Ile jest funkcji z \(\displaystyle{ \NN}\) do \(\displaystyle{ \NN}\): (a) nierosnących? (b) niemalejących?

Hint \(\displaystyle{ (a)}\). Taki ciąg od pewnego miejsca będzie stały. Więc jest ich tyle co ciągów skończonych. Mnogość dowolność wyboru pierwszego wyrazu nie zmieni wiele.

Hint \(\displaystyle{ (b)}\). Takie funkcje można kodować ciągami \(\displaystyle{ \NN^{\NN}}\). Gdzie kodujemy różnice kolejnych skoków.

Panie Januszu, a czy mógłby Pan wytłumaczyć to jak dla debila?

A czego nie rozumiesz?

W (a) masz w zasadzie całe rozwiązanie.
W (b) można stosować szacowania i tw. Cantora-Bernsteina.

Można też skorzystać z wyszukiwarki na forum, bo ten temat pojawiał się w przeszłości przynajmniej kilkukrotnie.

JK

W \(\displaystyle{ (a)}\) sprawa wygląda tak, że masz ciągi, które zaczynają się jakąś liczbą naturalną, a potem nie rosną. To znaczy, że są stałe lub maleją lub kombinacja trochę tego trochę tego (cokolwiek to znaczy...). Tak czy inaczej to są ciągi o wartościach w \(\displaystyle{ \NN}\), a w tym zbiorze nie da się maleć w nieskończoność bo się w końcu wbijemy w zero. To tak naturalne, że ktoś to w końcu uznał za aksjomat. Dlatego od pewnego momentu to jest po prostu stałe. No i trzeba zliczyć ciągi od pewnego miejsca stałe, a to się robi zliczając ciągi skończone, bo jak jest skończony to ostatni wyraz można traktować jak to co się potem już powtarza. Zanurzając różnowartościowo ciągi skończone wzorem

w \(\displaystyle{ \NN}\) dostajesz oszacowanie górne \(\displaystyle{ \aleph_0}\). I koniec bo dolne to też oczywiście \(\displaystyle{ \aleph_0}\) (bo tyle jest choćby ciągów stałych).

Natomiast wszystkich funkcji słabo rosnących (czyli, jak rozumiem, chodzi o podpunkt b)) z \(\displaystyle{ \NN}\) do \(\displaystyle{ \NN}\) jest continuum.
Możemy nawet więcej pokazać: wszystkich funkcji silnie rosnących z \(\displaystyle{ \NN}\) do \(\displaystyle{ \NN}\) jest continuum.
Aby to pokazać, to niech \(\displaystyle{ \mathbb {B}}\) będzie rodziną wszystkich takich funkcji silnie rosnących. Aby wykazać, że takich funkcji jest co najmniej continuum definiujemy funkcję różnowartościową \(\displaystyle{ \alpha:\left\{ 0,1\right\} ^{\NN} \rightarrow \mathbb{B}}\), w następujący sposób:

\(\displaystyle{ \alpha \left( f\right) = f';}\)

gdzie funkcja:

\(\displaystyle{ f':\NN \rightarrow \NN,}\)

jest dana jako:

\(\displaystyle{ f'\left( n\right) = 2n+f\left( n\right). }\)

(Wtedy zawsze \(\displaystyle{ f\left( n\right)}\) oznacza \(\displaystyle{ 0}\) lub \(\displaystyle{ 1}\), w zależności od tego jaką wartość na tym numerze naturalnym \(\displaystyle{ n}\) przyjmie ten ciąg zero-jedynkowy).
Łatwo jest pokazać, że jest to funkcja silnie rosnąca, a zatem \(\displaystyle{ f' \in \mathbb {B},}\) I funkcja \(\displaystyle{ \alpha }\) jest dobrze określona.

Wykażemy, że funkcja \(\displaystyle{ \alpha }\) jest różnowartościowa.
Jeśli \(\displaystyle{ f,g:\NN \rightarrow \left\{ 0,1\right\}}\), i \(\displaystyle{ f \neq g}\), to dla pewnego \(\displaystyle{ n}\) naturalnego: \(\displaystyle{ f\left( n\right) \neq g\left( n\right)}\) (wtedy jedna z tych wartości jest równa \(\displaystyle{ 0}\), a druga jest ròwna \(\displaystyle{ 1}\)), a wtedy:

\(\displaystyle{ f'\left( n\right) =2n+f\left( n\right) \neq 2n+g\left( n\right) =g'\left( n\right) ,}\)

skąd \(\displaystyle{ f' \neq g'}\), i funkcja \(\displaystyle{ \alpha }\) jest różnowartościowa.

A zatem rodzina \(\displaystyle{ \mathbb {B}}\) ma moc co najmniej continuum; a ponieważ wszystkich funkcji z \(\displaystyle{ \NN}\) do \(\displaystyle{ \NN}\) jest continuum, więc rodzina \(\displaystyle{ \mathbb{B} }\) ma moc co najwyżej continuum; i, na mocy twierdzenia Cantora-Bernsteina, ta rodzina \(\displaystyle{ \mathbb {B}}\) ma moc continuum, i wszystkich funkcji silnie rosnących z \(\displaystyle{ \NN}\) do \(\displaystyle{ \NN}\) jest continuum.\(\displaystyle{ \square}\)
(Zagadka: Ile jest funkcji silnie malejących z \(\displaystyle{ \NN}\) do \(\displaystyle{ \NN}\)?? Czy również continuum?? A czy w ogóle da się utworzyć taką funkcję silnie malejącą ).
Ponieważ każda funkcja silnie rosnąca z \(\displaystyle{ \NN}\) do \(\displaystyle{ \NN}\) jest słabo rosnąca (i wszystkich funkcji z \(\displaystyle{ \NN}\) do \(\displaystyle{ \NN}\) jest continuum), więc również wszystkich funkcji słabo rosnących jest continuum.\(\displaystyle{ \square}\)

Janusz Tracz pisze: 23 lis 2023, o 23:38

\(\displaystyle{ a\mapsto \prod_{i}^{} p_i^{a_i}}\)

Nie bardzo rozumiem ten wzór i dlaczego prowadzi do \(\displaystyle{ \aleph_0}\). Czy mógłby Pan wyjaśnić Panie Januszu?

Awdsfsaf6 pisze: 26 lis 2023, o 18:04Nie bardzo rozumiem ten wzór i dlaczego prowadzi do \(\displaystyle{ \aleph_0}\).

To jest wzór na funkcję, która skończonemu ciągowi liczb naturalnych \(\displaystyle{ a=\left\langle a_1,...,a_n\right\rangle }\) przypisuje pewną liczbę naturalną, będącą iloczynem odpowiednich potęg kolejnych liczb pierwszych. Należy zauważyć, że funkcja ta jest różnowartościowa, co pozwala stwierdzić, że skończonych ciągów liczb naturalnych jest co najwyżej tyle, ile liczb naturalnych, czyli \(\displaystyle{ \aleph_0.}\) Natomiast wcześniej wytłumaczono Ci, w jaki sposób skonstruować bijekcję pomiędzy nierosnącymi ciągami liczb naturalnych a skończonymi ciągami liczb naturalnych.

JK

Awdsfsaf6 pisze: 26 lis 2023, o 18:04 Czy mógłby Pan wyjaśnić Panie Januszu?

JK wszystko (zapewne zdecydowanie lepiej niż ja bym to zrobił) wytłumaczył pod moją nieobecność. Więc dodam tylko, że tak o to mi chodziło. A funkcja jest różnowartościowa bo liczbę naturalną można zapisać wyłącznie na jeden jedyny sposób jako iloczyn liczb pierwszych.