zbiór przeliczalny..

Algebra zbiorów. Relacje, funkcje, iloczyny kartezjańskie... Nieskończoność, liczby kardynalne... Aksjomatyka.
raphel
Użytkownik
Użytkownik
Posty: 657
Rejestracja: 9 gru 2007, o 12:27
Płeć: Mężczyzna
Lokalizacja: Czewa/Wrocław
Podziękował: 84 razy
Pomógł: 138 razy

zbiór przeliczalny..

Post autor: raphel »

Wykaż że zbiór słabo malejących funkcji \(\displaystyle{ f: \mathbb{N} \rightarrow \mathbb{N}}\) jest przeliczalny.
(funkcja \(\displaystyle{ f: \mathbb{N} \rightarrow \mathbb{N}}\) jest słabo malejąca, jeśli \(\displaystyle{ x>y f(x) qslant f(y)}\) dla wszelkich \(\displaystyle{ x,y \mathbb{N}}\)).
Awatar użytkownika
max
Użytkownik
Użytkownik
Posty: 3306
Rejestracja: 10 gru 2005, o 17:48
Płeć: Mężczyzna
Lokalizacja: Lebendigentanz
Podziękował: 37 razy
Pomógł: 778 razy

zbiór przeliczalny..

Post autor: max »

Oznaczmy zbiór wszystkich takich funkcji przez \(\displaystyle{ S}\), a zbiór skończonych podzbiorów \(\displaystyle{ \mathbb{N}\times (\mathbb{N}\cup\{\aleph_{0}\})}\) przez \(\displaystyle{ \mathcal{P}_{0}}\).
Zauważmy, że dowolne \(\displaystyle{ f\in S}\) przyjmuje skończenie wiele wartości (wynika to np z dobrego uporządkowania \(\displaystyle{ \mathbb{N}}\)) a ponadto jednoznacznie wyznacza zbiór \(\displaystyle{ A_{f}:= \{(n, m) \mathbb{N}\times(\mathbb{N}\cup\{\aleph_{0}\}) \ : \ n f(\mathbb{N}), \ m = \#f^{-1}(\{n\})\}}\)
Ponieważ funkcja:
\(\displaystyle{ S \ni f \mapsto A_{f}\in \mathcal{P}_{0}}\) jest injekcją, to \(\displaystyle{ \#S qslant \#\mathcal{P}_{0} = \aleph_{0}}\) (zbiór skończonych podzbiorów zbioru przeliczalnego jest przeliczalny), a z drugiej strony \(\displaystyle{ S}\) jest nieskończony (bo należy do niego każda funkcja stała, a takich jest nieskończenie wiele), czyli \(\displaystyle{ \#S = \aleph_{0}}\).
raphel
Użytkownik
Użytkownik
Posty: 657
Rejestracja: 9 gru 2007, o 12:27
Płeć: Mężczyzna
Lokalizacja: Czewa/Wrocław
Podziękował: 84 razy
Pomógł: 138 razy

zbiór przeliczalny..

Post autor: raphel »

ok, dzięki za rozwiązanie. Mam jeszcze pytanie co oznacza # i czy to zadanie musi być rozwiązywane z \(\displaystyle{ \aleph_{0}}\) czy można to jakoś w innej postaci przedstawić(troche prostszej do zrozumienia??)
Awatar użytkownika
max
Użytkownik
Użytkownik
Posty: 3306
Rejestracja: 10 gru 2005, o 17:48
Płeć: Mężczyzna
Lokalizacja: Lebendigentanz
Podziękował: 37 razy
Pomógł: 778 razy

zbiór przeliczalny..

Post autor: max »

\(\displaystyle{ \#A}\) oznacza moc zbioru \(\displaystyle{ A}\).
Zapis \(\displaystyle{ \#A = \aleph_{0}}\) można zastąpić sformułowaniem, że \(\displaystyle{ A}\) jest przeliczalny (taki jest dokładnie sens tego oznaczenia).
raphel
Użytkownik
Użytkownik
Posty: 657
Rejestracja: 9 gru 2007, o 12:27
Płeć: Mężczyzna
Lokalizacja: Czewa/Wrocław
Podziękował: 84 razy
Pomógł: 138 razy

zbiór przeliczalny..

Post autor: raphel »

aha, ok, myślę że jakoś to rozgryzę:)

i mam jeszcze podobne(tak sie przynajmniej wydaje) zadanie:

Wykaż że zbiór słabo rosnących funkcji \(\displaystyle{ f: \mathbb{N} \rightarrow \mathbb{N}}\) jest nieprzeliczalny.
(funkcja \(\displaystyle{ f: \mathbb{N} \rightarrow \mathbb{N}}\) jest słabo rosnąca, jeśli \(\displaystyle{ x>y f(x) qslant f(y)}\) dla wszelkich \(\displaystyle{ x,y \mathbb{N}}\)).
Awatar użytkownika
max
Użytkownik
Użytkownik
Posty: 3306
Rejestracja: 10 gru 2005, o 17:48
Płeć: Mężczyzna
Lokalizacja: Lebendigentanz
Podziękował: 37 razy
Pomógł: 778 razy

zbiór przeliczalny..

Post autor: max »

Oznaczmy zbiór tych funkcji przez \(\displaystyle{ T}\). Wystarczy pokazać surjekcję z \(\displaystyle{ T}\) na nieprzeliczalny zbiór \(\displaystyle{ \mathcal{P}(\mathbb{N})\setminus\{\emptyset\}}\), gdzie \(\displaystyle{ \mathcal{P}(\mathbb{N})}\) to zbiór potęgowy zbioru liczb naturalnych.
Odwzorowanie \(\displaystyle{ T\ni f \mapsto f(\mathbb{N})\in \mathcal{P}(\mathbb{N})\setminus\{\emptyset\}}\) jest taką funkcją:
Dla dowolnego podzbioru \(\displaystyle{ \emptyset A\subset \mathbb{N}}\), funkcję \(\displaystyle{ f\in T}\), taką, że \(\displaystyle{ f(\mathbb{N}) = A}\) określamy indukcyjnie:
jeśli \(\displaystyle{ A}\) jest nieskończony, to definiujemy:
\(\displaystyle{ \begin{cases} f(0) = \min A,\\ f(n + 1) = \min (A\setminus \{f(0),\ldots, f(n)\})\end{cases}}\)
jeśli natomiast \(\displaystyle{ A}\) jest skończony i ma, powiedzmy \(\displaystyle{ n_{0}}\) elementów, to kładziemy:
\(\displaystyle{ \begin{cases}f(0) = \min A, \\ f(n + 1) = \min (A\setminus \{f(0),\ldots, f(n)\}), \ n < n_{0}, \\ f(n+1) = f(n), \ n qslant n_{0}\end{cases}}\)
ODPOWIEDZ