Przeliczalność zbioru liczb całkowitych i wymiernych

Algebra zbiorów. Relacje, funkcje, iloczyny kartezjańskie... Nieskończoność, liczby kardynalne... Aksjomatyka.
emong00
Użytkownik
Użytkownik
Posty: 29
Rejestracja: 21 paź 2022, o 20:42
Płeć: Mężczyzna
wiek: 19
Podziękował: 21 razy

Przeliczalność zbioru liczb całkowitych i wymiernych

Post autor: emong00 »

Mam ćwiczenie, żeby udowodnić przeliczalność zbioru liczb całkowitych i zbioru liczb wymiernych. Na wykładach nam podano dowody, zastanawiałem się za to w tym ćwiczeniu czy nie można tego w prostszy sposób zapisać i prosiłym o sprawdzenie i poprawienie.
1)Zbiór liczb całkowitych
Biore ciągi \(\displaystyle{ \left\{ a_n\right\}}\) i \(\displaystyle{ \left\{ b_n\right\}}\), takie, że \(\displaystyle{ a(i)=i, i\in\mathbb{N}}\) i \(\displaystyle{ b(i)=-i, i\in\mathbb{N}}\). Teraz wziąłbym zbiory \(\displaystyle{ A=\left\{a(i)|i\in \mathbb{N} \right\}}\) i \(\displaystyle{ B=\left\{b(i)|i\in \mathbb{N} \right\}}\). Oba te zbiory są przeliczalne, bo skoro każdemu elementowi można przypisać jakąś liczbę naturalną, to na pewno istnieje jakaś liczba naturalna równa mocy tych zbiorów, czyli \(\displaystyle{ |\mathbb{Z}|=|A \cup B \cup \left\{ 0\right\}| \le |\omega| }\), czyli zbiór liczb całkowitych jest przeliczalny
2)Zbiór liczb wymiernych
Analogicznie do liczb całkowitych, po prostu tworzę ciąg \(\displaystyle{ a_n=\frac{1}{n}}\), potem \(\displaystyle{ b_n=\frac{2}{n}}\), ... i tak dalej. Analogicznie dla ujemnych. Jest ich przeliczalna ilość, bo w liczebniku wpisuję kolejne liczby naturalne, których jest przeliczalna ilość. Potem tworzę zbiory, one są przeliczalne, więc ich suma też jest, a że ich suma razem z \(\displaystyle{ 0}\) tworzy zbiór liczb wymiernych to on też jest przeliczalny.
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Re: Przeliczalność zbioru liczb całkowitych i wymiernych

Post autor: a4karo »

emong00 pisze: 4 gru 2022, o 16:56 Mam ćwiczenie, żeby udowodnić przeliczalność zbioru liczb całkowitych i zbioru liczb wymiernych. Na wykładach nam podano dowody, zastanawiałem się za to w tym ćwiczeniu czy nie można tego w prostszy sposób zapisać i prosiłym o sprawdzenie i poprawienie.
1)Zbiór liczb całkowitych
Biore ciągi \(\displaystyle{ \left\{ a_n\right\}}\) i \(\displaystyle{ \left\{ b_n\right\}}\), takie, że \(\displaystyle{ a(i)=i, i\in\mathbb{N}}\) i \(\displaystyle{ b(i)=-i, i\in\mathbb{N}}\). Teraz wziąłbym zbiory \(\displaystyle{ A=\left\{a(i)|i\in \mathbb{N} \right\}}\) i \(\displaystyle{ B=\left\{b(i)|i\in \mathbb{N} \right\}}\). Oba te zbiory są przeliczalne, bo skoro każdemu elementowi można przypisać jakąś liczbę naturalną, to na pewno istnieje jakaś liczba naturalna równa mocy tych zbiorów,
E tam...
Jan Kraszewski
Administrator
Administrator
Posty: 34123
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Przeliczalność zbioru liczb całkowitych i wymiernych

Post autor: Jan Kraszewski »

emong00 pisze: 4 gru 2022, o 16:561)Zbiór liczb całkowitych
Biore ciągi \(\displaystyle{ \left\{ a_n\right\}}\) i \(\displaystyle{ \left\{ b_n\right\}}\), takie, że \(\displaystyle{ a(i)=i, i\in\mathbb{N}}\) i \(\displaystyle{ b(i)=-i, i\in\mathbb{N}}\). Teraz wziąłbym zbiory \(\displaystyle{ A=\left\{a(i)|i\in \mathbb{N} \right\}}\) i \(\displaystyle{ B=\left\{b(i)|i\in \mathbb{N} \right\}}\). Oba te zbiory są przeliczalne, bo skoro każdemu elementowi można przypisać jakąś liczbę naturalną, to na pewno istnieje jakaś liczba naturalna równa mocy tych zbiorów, czyli \(\displaystyle{ |\mathbb{Z}|=|A \cup B \cup \left\{ 0\right\}| \le |\omega| }\), czyli zbiór liczb całkowitych jest przeliczalny
Rozumiem, że u Ciebie "przeliczalność" oznacza równoliczność z podzbiorem \(\displaystyle{ \NN}\), a zero nie jest naturalne.

Pomijając już Twoją skłonność do komplikowania prostych rzeczy (ja bym zapisał \(\displaystyle{ A=\NN, B=\{-n:n\in\NN\}}\)), to nie bardzo wiem, od czego ten dowód ma być prostszy. Tym bardziej, że nie bardzo jest to dowód.

No i oczywiście stwierdzenie "skoro każdemu elementowi można przypisać jakąś liczbę naturalną, to na pewno istnieje jakaś liczba naturalna równa mocy tych zbiorów" jest bardzo nieprawdziwe.
emong00 pisze: 4 gru 2022, o 16:562)Zbiór liczb wymiernych
Analogicznie do liczb całkowitych, po prostu tworzę ciąg \(\displaystyle{ a_n=\frac{1}{n}}\), potem \(\displaystyle{ b_n=\frac{2}{n}}\), ... i tak dalej. Analogicznie dla ujemnych. Jest ich przeliczalna ilość, bo w liczebniku wpisuję kolejne liczby naturalne, których jest przeliczalna ilość. Potem tworzę zbiory, one są przeliczalne, więc ich suma też jest, a że ich suma razem z \(\displaystyle{ 0}\) tworzy zbiór liczb wymiernych to on też jest przeliczalny.
To nie jest dowód, tylko machanie rękami.

JK
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: Przeliczalność zbioru liczb całkowitych i wymiernych

Post autor: Jakub Gurak »

W konstrukcji liczb całkowitych z par liczb naturalnych, mamy, że zbiór liczb całkowitych jest zbiorem wszystkich klas równoważności na zbiorze \(\displaystyle{ \NN \times \NN}\), względem relacji na parach liczb naturalnych, których różnica współrzędnych daje daną liczbę całkowitą. Ponieważ zbiór wszystkich klas równoważności względem relacji równoważności na danym zbiorze jest rozkładem tego zbioru, więc zbiór \(\displaystyle{ \ZZ}\) jest rozkładem zbioru \(\displaystyle{ \NN \times \NN}\)- zbioru przeliczalnego- jest więc zbiorem co najwyżej przeliczalnym. Jest też zbiorem nieskończonym, bo zawiera on zbiór (przez \(\displaystyle{ \approx}\) oznaczam odpowiednią relację równoważności ), jest on nadzbiorem zbioru :

\(\displaystyle{ \left\{ \left[ \left( n,0\right) \right] _{/ \approx }\Bigl| \ \ n \in \NN\right\}. }\)

Ktòry to zbiór jest oczywiście równoliczny ze zbiorem \(\displaystyle{ \NN.}\)
A zatem zbiór liczb całkowitych jest również nieskończony, i jest zbiorem przeliczalnym.

I dalej, skoro zbiór liczb całkowitych \(\displaystyle{ \ZZ}\) jest przeliczalny, a zbiór liczb wymiernych jest formalnie zbiorem wszystkich klas równoważności na zbiorze \(\displaystyle{ \ZZ \times \ZZ ^{\star}}\), gdzie \(\displaystyle{ \ZZ ^{\star}=\ZZ \setminus \left\{ 0\right\} }\), względem relacji na parach liczb całkowitych, których iloraz współrzędnych daje daną liczbę wymierną, więc zbiór liczb wymiernych jako rozkład zbioru \(\displaystyle{ \ZZ \times \ZZ ^{\star} }\)- zbioru przeliczalnego- jest więc zbiorem co najwyżej przeliczalnym. Jest też zbiorem nieskończonym, gdyż jest nadzbiorem zbioru (przez \(\displaystyle{ \sim}\) oznaczam odpowiednią relację równoważności ):

\(\displaystyle{ \left\{ \left[ \left( x,1\right)\right] _{/\sim} \Bigl| \ \ x \in \ZZ\right\},}\)

Który to zbiór jest oczywiście równoliczny ze zbiorem \(\displaystyle{ \ZZ}\)- zbiorem przeliczalnym; więc zbiór liczb wymiernych jest nieskończony i jest przeliczalny. 8-)
(Musiałem podnieść poziom rozważań).
Jan Kraszewski
Administrator
Administrator
Posty: 34123
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Przeliczalność zbioru liczb całkowitych i wymiernych

Post autor: Jan Kraszewski »

Naprawdę uważasz, że standardowy dowód przeliczalności zbiorów liczb całkowitych i wymiernych odwołuje się do ich konstrukcji?!

JK
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Re: Przeliczalność zbioru liczb całkowitych i wymiernych

Post autor: a4karo »

Lubię się bawić dziwnymi funkcjami. No to do roboty.
Załóżmy, że mówimy o liczbach naturalnych wraz z zerem. Pomysł jest taki:
Jeżeli liczba `n` jest parzysta, czyli gdy `n=2k`, to przypiszemy jej liczbę całkowitą `k`. Jeżeli zaś `n=2k+1`, to przypiszemy jej `-k`.
W porządku? Prawie... . Liczbom `0` i `1` odpowiada to samo `k=0`.
Możemy to naprawić na dwa sposoby: pierwszy jest taki, żeby liczbie nieparzystej `n=2k+1` przypisać `-k-1`.
Spróbujmy to zrealizować przy pomocy funkcji opisanej wzorem.
Będziemy to tego potrzebowali funkcji `g`, która przyjmie wartość `1`, gdy `n` jest nieparzyste i `0`. Taką funkcję łatwo znaleźć. Taką funckję można stworzyć na mnóstwo sposobów: na przykład tak

\(\displaystyle{ g(n)=\sin^2\frac{\pi n}{2}.}\)
albo tak
\(\displaystyle{ g(n)=\left[\frac{n+1}{2}\right]-\left[\frac{n}{2}\right]}\).

Żeby z `n` dostać `2k` trzeba obliczyć
\(\displaystyle{ n-g(n)}\),
wartośc `k` dostaniemy dzieląc to wyrażenie przez `2`
\(\displaystyle{ \frac{n-g(n)}{2}}\).
Teraz trzeba zmienić znak, ale tylko wtedy, gdy `n` jest nieparzyste. Osiągniemy to mnożąc wyrażenie przez `1-2g(n)` (sprawdź!)
\(\displaystyle{ (1-2g(n))\frac{n-g(n)}{2}}\).
Na koniec musimy odjąć jedynkę wtedy gdy `n` jest nieparzyste, czyli de facto musimy odjąć `g(n)`. I tak dostajemy gotowy wzór na bijekcję `f:\NN\to\ZZ`:
\(\displaystyle{ f(n)=(1-2g(n))\frac{n-g(n)}{2}-g(n)}\).

Uprośćmy go trochę:
\(\displaystyle{ \red{f(n)=}\frac{n-g(n)-2ng(n)+2g^2(n)-2g(n)}{2}=\red{\frac{n-(2n+1)g(n)}{2}}}\)


Drugi sposób jest taki, żeby liczbę nieparzystą zapisać nie w postaci `n=2k+1`, lecz w postaci `n=2k-1`. To już załatwia sprawę, bo przy takim przedstawieniu liczba naturalna `k=0` wykorzystywana jest tyko raz, a każda inna dwa razy.
Wystarczy zatem liczbie parzystej przypisać `k`, a nieparzystej `-k`. Cały wzór wygląda tak:
\(\displaystyle{ \red{f(n)}=(1-2g(n))\frac{n+g(n)}{2}=\frac{n+g(n)-2ng(n)-2g^2(n)}{2}=\red{\frac{n-(2n+1)g(n)}{2}}}\)

Jak widać oba sposoby prowadzą do tej samej funkcji.
ODPOWIEDZ