logowanie

matematyka » forum » forum zadaniowe - uczelnie wyższe » zadanie

Logika, zadanie nr 1365

ostatnie wiadomości  |  regulamin  |  latex

AutorZadanie / Rozwiązanie

jehns
postów: 10
2013-05-31 17:13:18

Zbadać, które z następujacych zbiorów są ze sobą równoliczne:
(a) Q×Z,
(b) R×Q,
(c) R\Q,
(d) $2^{N}$
(e) $2^{R}$
(f) P(R×Z),


tumor
postów: 8070
2013-05-31 19:34:39

$(a)$ jest przeliczalny, innego przeliczalnego nie ma

$(b) \sim (c) \sim (d)$

$(e) \sim (f)$

Rozwiązanie wymaga podania jakichś funkcji i skorzystania z twierdzeń (najłatwiej: Cantora-Bernsteina). Ale tu nie trzeba wiele myśleć.




jehns
postów: 10
2013-06-02 10:55:36

Mógłbym prosić o dokładniejsze rozwiązanie, ponieważ nie za bardzo wiem jak napisać odpowiedź.


tumor
postów: 8070
2013-06-02 11:31:46

A może spróbuj coś zrobić? :)

Nie wiem, co na wykładach było.

$N\sim N^2 \sim N\times \{0,1\} \sim Q \sim Z$ (prawdopodobnie w jakiejś formie wszystko to było robione)

zatem od razu $N\sim Q\times Z$

---

Potem dowód (śliczny, Cantora), że R nie jest równoliczny z N, oraz oczywistość, że pewien podzbiór R jest równoliczny z N.

Gdyby $R\backslash Q \sim N$, to $R\sim N$, co by przeczyło tw. wyżej.
Chcemy pokazać, że $R\backslash Q \sim R$.
Gdybyśmy mieli ogólne twierdzenie, że dla zbiorów nieskończonych
$P(A) \backslash A \sim A$, to byłoby z głowy. A dziubdzianie może wyglądać tak:
Mamy $R\sim [0,1] \sim R^2 \sim F$ (gdzie $F$ to ciągi zero-jedynkowe).
Stąd i tw. Cantora-Bernsteina dostajemy
$Q\sim Q \cap [0,1]$
$R \sim [0,1]\cup [2,3]$
$R\backslash Q \sim [2,3]\sim R$

(Włóż w to trochę wysiłku i pokaż krok po kroku, bo ja robię takie kroki jak gdy idę szybko, ludzie rzadko są w stanie nadążyć za moim marszem.)

Z tw. C-B (i wcześniejszych zadań) od razu dostajemy
$R\sim R\times Q \sim R\times R$

$2^N$ to właśnie ciągi zero-jedynkowe (ja pisałem F), dowód równoliczności z R gdzie indziej był.

Z Tw. Cantora niemożliwe, żeby $2^R$ było równoliczne z $N$ lub z $R$, czyli na pewno z żadnym wcześniej równoliczny nie jest.
Łatwo pokazać, że jeśli $A\sim B$, to $P(A)\sim P(B)$,
a skoro $R\times Q \sim R\times Z \sim R$, to
$P(R\times Z) \sim P(R) \sim 2^R$
(tożsamość $2^A$ i $P(A)$ też jest prosta)


jehns
postów: 10
2013-06-06 17:03:17

Dziękuję bardzo za wszystkie odpowiedzi!! ;)

strony: 1

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj





© 2019 Mariusz Śliwiński      o serwisie | kontakt   drukuj