Wykazać zbiory przeliczalne

Algebra zbiorów. Relacje, funkcje, iloczyny kartezjańskie... Nieskończoność, liczby kardynalne... Aksjomatyka.
gg1985
Użytkownik
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

Post autor: gg1985 »

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
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

Wykazać zbiory przeliczalne

Post autor: Jan Kraszewski »

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 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.

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.
robin5hood
Użytkownik
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

Post autor: robin5hood »

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
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

Wykazać zbiory przeliczalne

Post autor: Jan Kraszewski »

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
Ostatnio zmieniony 6 cze 2010, o 18:23 przez Jan Kraszewski, łącznie zmieniany 1 raz.
robin5hood
Użytkownik
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

Post autor: robin5hood »

ad 1 mamy znaleźć funkcję \(\displaystyle{ f:N_+\times N_+\to Q_+}\) ?
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

Wykazać zbiory przeliczalne

Post autor: Jan Kraszewski »

Tak, ale surjekcję, czyli funkcję "na".

Przepraszam za niezbyt czytelny zapis, już poprawiłem.

JK
robin5hood
Użytkownik
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

Post autor: robin5hood »

czy taka jest ok
\(\displaystyle{ f(n,m)= \frac{n}{m}}\)?
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

Wykazać zbiory przeliczalne

Post autor: Jan Kraszewski »

Tak.

JK
robin5hood
Użytkownik
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

Post autor: robin5hood »

skąd otrzymujemy oszacowanie \(\displaystyle{ |\mathbb{Q}_+|\le|\mathbb{N}_+^2|}\)?
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

Wykazać zbiory przeliczalne

Post autor: Jan Kraszewski »

Z twierdzenia, że jeśli istnieje surjekcja \(\displaystyle{ f:A \rightarrow B}\), to \(\displaystyle{ |B|\le|A|}\).

JK
robin5hood
Użytkownik
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

Post autor: robin5hood »

dzieki
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.
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

Wykazać zbiory przeliczalne

Post autor: Jan Kraszewski »

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
robin5hood
Użytkownik
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

Post autor: robin5hood »

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.
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

Wykazać zbiory przeliczalne

Post autor: Jan Kraszewski »

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
robin5hood
Użytkownik
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

Post autor: robin5hood »

\(\displaystyle{ f:N\times N\to N, f(n,k)=2^{n-1}(2(k-1)+1)-1}\)?
ODPOWIEDZ