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.
Przeliczalność zbioru liczb całkowitych i wymiernych
-
- 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
E tam...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,
-
- 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
Rozumiem, że u Ciebie "przeliczalność" oznacza równoliczność z podzbiorem \(\displaystyle{ \NN}\), a zero nie jest naturalne.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
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.
To nie jest dowód, tylko machanie rękami.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.
JK
-
- 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
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.
(Musiałem podnieść poziom rozważań).
\(\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.
(Musiałem podnieść poziom rozważań).
-
- 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
Naprawdę uważasz, że standardowy dowód przeliczalności zbiorów liczb całkowitych i wymiernych odwołuje się do ich konstrukcji?!
JK
JK
-
- 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
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.
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.