Wykazać zbiory przeliczalne
-
- Użytkownik
- Posty: 53
- Rejestracja: 21 sty 2006, o 14:51
- Płeć: Mężczyzna
- Lokalizacja: stąd
- Podziękował: 1 raz
Wykazać zbiory przeliczalne
Witam
1. Używając metody przekątniowej, wykazać że iloczyn kartezjański dwóch zbiorów przeliczalnych jest zbiorem przeliczalnym.
2. Wykazać, że zbiór liczb wymiernych jest zbiorem przeliczalnym
Pozdrawiam
1. Używając metody przekątniowej, wykazać że iloczyn kartezjański dwóch zbiorów przeliczalnych jest zbiorem przeliczalnym.
2. Wykazać, że zbiór liczb wymiernych jest zbiorem przeliczalnym
Pozdrawiam
-
- 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
Wykazać zbiory przeliczalne
Ad 1. Dowód sprowadza się do pokazania, że par liczb naturalnych jest tyle samo, co liczb naturalnych, to zaś robi się wypisując funkcję jawnym wzorem i dowodząc, że jest bijekcją, np. \(\displaystyle{ f:\NN\times \NN\to \NN, f(n,k)=2^n(2k+1)-1}\). Metoda przekątniowa nie ma tu nic do rzeczy.gg1985 pisze:1. Używając metody przekątniowej, wykazać że iloczyn kartezjański dwóch zbiorów przeliczalnych jest zbiorem przeliczalnym.
2. Wykazać, że zbiór liczb wymiernych jest zbiorem przeliczalnym
Ad 2. Najprościej wykorzystać punkt 1 i tw. Cantora Bernsteina.
JK
Ostatnio zmieniony 24 sty 2020, o 13:11 przez Jan Kraszewski, łącznie zmieniany 2 razy.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
- Użytkownik
- Posty: 1676
- Rejestracja: 2 kwie 2007, o 14:43
- Płeć: Mężczyzna
- Lokalizacja: warszawa
- Podziękował: 178 razy
- Pomógł: 17 razy
Wykazać zbiory przeliczalne
Mam pytanie odnośnie 2, co trzeba zrobić konkretniej, mógłbym prosic o wskazówki?
chodzi o to tw?
Twierdzenie Cantora-Bernsteina to twierdzenie teorii mnogości, głoszące, że jeśli zbiór A jest równoliczny z pewnym podzbiorem zbioru B oraz zbiór B jest równoliczny z pewnym podzbiorem zbioru A, to zbiory A i B są równoliczne.
ale jak go zastosować w tym zadaniu
chodzi o to tw?
Twierdzenie Cantora-Bernsteina to twierdzenie teorii mnogości, głoszące, że jeśli zbiór A jest równoliczny z pewnym podzbiorem zbioru B oraz zbiór B jest równoliczny z pewnym podzbiorem zbioru A, to zbiory A i B są równoliczne.
ale jak go zastosować w tym zadaniu
-
- 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
Wykazać zbiory przeliczalne
1. Konstruujemy surjekcję z \(\displaystyle{ \mathbb{N}_+^2}\) w \(\displaystyle{ \mathbb{Q}_+}\) - stąd otrzymamy oszacowanie \(\displaystyle{ |\mathbb{Q}_+|\le|\mathbb{N}_+^2|}\).
2. Pokazujemy, że \(\displaystyle{ |\mathbb{N}_+^2|=|\mathbb{N}|}\).
3. Ponieważ \(\displaystyle{ \mathbb{N}_+ \subseteq \mathbb{Q}_+}\), więc już dość prosto, korzystając z tw. Cantora-Bernsteina, pokazać, że \(\displaystyle{ |\mathbb{Q}_+|=|\mathbb{N}|}\).
4. Teraz trzeba trochę pomyśleć i pokazać, że \(\displaystyle{ |\mathbb{Q}_+|=|\mathbb{Q}|}\) i już.
JK
2. Pokazujemy, że \(\displaystyle{ |\mathbb{N}_+^2|=|\mathbb{N}|}\).
3. Ponieważ \(\displaystyle{ \mathbb{N}_+ \subseteq \mathbb{Q}_+}\), więc już dość prosto, korzystając z tw. Cantora-Bernsteina, pokazać, że \(\displaystyle{ |\mathbb{Q}_+|=|\mathbb{N}|}\).
4. Teraz trzeba trochę pomyśleć i pokazać, że \(\displaystyle{ |\mathbb{Q}_+|=|\mathbb{Q}|}\) i już.
JK
Ostatnio zmieniony 6 cze 2010, o 18:23 przez Jan Kraszewski, łącznie zmieniany 1 raz.
-
- Użytkownik
- Posty: 1676
- Rejestracja: 2 kwie 2007, o 14:43
- Płeć: Mężczyzna
- Lokalizacja: warszawa
- Podziękował: 178 razy
- Pomógł: 17 razy
-
- 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
Wykazać zbiory przeliczalne
Tak, ale surjekcję, czyli funkcję "na".
Przepraszam za niezbyt czytelny zapis, już poprawiłem.
JK
Przepraszam za niezbyt czytelny zapis, już poprawiłem.
JK
-
- Użytkownik
- Posty: 1676
- Rejestracja: 2 kwie 2007, o 14:43
- Płeć: Mężczyzna
- Lokalizacja: warszawa
- Podziękował: 178 razy
- Pomógł: 17 razy
-
- 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
-
- Użytkownik
- Posty: 1676
- Rejestracja: 2 kwie 2007, o 14:43
- Płeć: Mężczyzna
- Lokalizacja: warszawa
- Podziękował: 178 razy
- Pomógł: 17 razy
Wykazać zbiory przeliczalne
skąd otrzymujemy oszacowanie \(\displaystyle{ |\mathbb{Q}_+|\le|\mathbb{N}_+^2|}\)?
-
- 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
Wykazać zbiory przeliczalne
Z twierdzenia, że jeśli istnieje surjekcja \(\displaystyle{ f:A \rightarrow B}\), to \(\displaystyle{ |B|\le|A|}\).
JK
JK
-
- Użytkownik
- Posty: 1676
- Rejestracja: 2 kwie 2007, o 14:43
- Płeć: Mężczyzna
- Lokalizacja: warszawa
- Podziękował: 178 razy
- Pomógł: 17 razy
Wykazać zbiory przeliczalne
dzieki
biore sie za 2 i koleny problem jak to pokazac
\(\displaystyle{ |\mathbb{N}_+^2|=|\mathbb{N}|}\)?
czy wystarczy korzystać z tego powyzszego postu?
i pozostało jak dla mnie najtrudniejsze to \(\displaystyle{ |\mathbb{Q}_+|=|\mathbb{Q}|}\)
biore sie za 2 i koleny problem jak to pokazac
\(\displaystyle{ |\mathbb{N}_+^2|=|\mathbb{N}|}\)?
czy wystarczy korzystać z tego powyzszego postu?
Jan Kraszewski pisze:gg1985 pisze: Dowód sprowadza się do pokazania, że par liczb naturalnych jest tyle samo, co liczb naturalnych, to zaś robi się wypisując funkcję jawnym wzorem i dowodząc, że jest bijekcją, np. \(\displaystyle{ f:N\times N\to N, f(n,k)=2^n(2k+1)-1}\). Metoda przekątniowa nie ma tu nic do rzeczy.
JK
i pozostało jak dla mnie najtrudniejsze to \(\displaystyle{ |\mathbb{Q}_+|=|\mathbb{Q}|}\)
Ostatnio zmieniony 6 cze 2010, o 18:46 przez robin5hood, łącznie zmieniany 1 raz.
-
- 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
Wykazać zbiory przeliczalne
Np. z powyższego postu (czyli tego z 2006 r.), oraz z tego, że \(\displaystyle{ |\mathbb{N}|=|\mathbb{N}_+|}\) i faktu, że \(\displaystyle{ |A|=|B| \Rightarrow |A^2|=|B^2|}\).
Można też zmodyfikować funkcję z "powyższego postu", by dostać od razu bijekcję \(\displaystyle{ f:\mathbb{N}_+^2 \rightarrow \mathbb{N}}\).
JK
Można też zmodyfikować funkcję z "powyższego postu", by dostać od razu bijekcję \(\displaystyle{ f:\mathbb{N}_+^2 \rightarrow \mathbb{N}}\).
JK
-
- Użytkownik
- Posty: 1676
- Rejestracja: 2 kwie 2007, o 14:43
- Płeć: Mężczyzna
- Lokalizacja: warszawa
- Podziękował: 178 razy
- Pomógł: 17 razy
Wykazać zbiory przeliczalne
jak tę funkcję zmodyfikować \(\displaystyle{ f:N\times N\to N, f(n,k)=2^n(2k+1)-1}\)?
Ostatnio zmieniony 6 cze 2010, o 18:54 przez robin5hood, łącznie zmieniany 2 razy.
-
- 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
Wykazać zbiory przeliczalne
Pomyśl: w argumentach \(\displaystyle{ n}\) i \(\displaystyle{ k}\) zaczynasz od 1 zamiast od 0. Jak zmienić wzór funkcji, by dostać ten sam wynik?
JK
JK
-
- Użytkownik
- Posty: 1676
- Rejestracja: 2 kwie 2007, o 14:43
- Płeć: Mężczyzna
- Lokalizacja: warszawa
- Podziękował: 178 razy
- Pomógł: 17 razy