Matematyka.pl

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

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

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

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

ad 1 mamy znaleźć funkcję \(\displaystyle{ f:N_+\times N_+\to Q_+}\) ?

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

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

JK

czy taka jest ok
\(\displaystyle{ f(n,m)= \frac{n}{m}}\)?

Tak.

JK

skąd otrzymujemy oszacowanie \(\displaystyle{ |\mathbb{Q}_+|\le|\mathbb{N}_+^2|}\)?

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

JK

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}|}\)

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

jak tę funkcję zmodyfikować \(\displaystyle{ f:N\times N\to N, f(n,k)=2^n(2k+1)-1}\)?

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

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