Logika, zadanie nr 1365

Autor	Zadanie / 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