Zbiory przeliczalne 4: suma zbiorów
Zbiory przeliczalne 4: suma zbiorów
Udowodnić:
1) Suma przeliczalnie wielu zbiorów przeliczalnych jest przeliczalna.
2) Suma co najwyżej przeliczalnie wielu zbiorów co najwyżej przeliczalnych jest co najwyżej przeliczalna.
3) Suma przeliczalnie wielu zbiorów co najwyżej przeliczalnych jest przeliczalna.
Oprócz tego mam przedstawiony dowód twierdzenia "Suma co najwyżej przeliczalnie wielu zbiórów przeliczalnych jest przeliczalna" (nazwę to Twierdzeniem T).
1) Dowód zawiera się bezpośrednio w dowodzie Twierdzenia T.
2) Muszę udowodnić:
a) Suma przeliczalnie wielu zbiorów przeliczalnych jest co najwyżej przeliczalna.
b) Suma przeliczalnie wielu zbiorów skończonych jest co najwyżej przeliczalna.
c) Suma skończenie wielu zbiorów skończonych jest co najwyżej przeliczalna.
d) Suma skończenie wielu zbiorów przeliczalnych jest co najwyżej przeliczalna.
a) Dowód zawarty w dowodzie Twierdzenia T.
b) Dowód 3 b).
c) Muszę to jakoś udowadniać czy mogę to uznać za "oczywiste"?
d) Tutaj dowód za pomocą twierdzenia "Suma dwóch zbiorów przeliczalnych jest przeliczalna", które możemy rozszerzyć indukcją matematyczną na skończoną liczbę zbiorów przeliczalnych.
3) Muszę udowodnić:
a) Suma przeliczalnie wielu zbiorów przeliczalnych jest przeliczalna.
b) Suma przeliczalnie wielu zbiorów skończonych jest przeliczalna.
a) Twierdzenie T.
b) \(\displaystyle{ f: \bigcup_{n\in \NN} A_n \rightarrow \NN \times \NN, f(n,k) = (n,k)}\) jest iniekcją czyli mamy \(\displaystyle{ |A_n| \le |\bigcup_{n\in \NN} A_n| \le |\NN \times \NN| = |\NN|}\). Udowodniłem, że suma przeliczalnie wielu zbiorów skończonych jest co najwyżej przeliczalna czyli 2 b). Brakuje najważniejszego kroku. Może do udowodnienia 3 b) powinienem podejść tak jak do Twierdzenia T?. Tzn. pierw wybrać zbiór z rodziny zbiorów tyle, że w Twierdzeniu T wybrany zbiór był nieskończony, a teraz funkcja musiałaby przelecieć wszystkie elementy danego zbioru, później przeskoczyć do drugiego zbioru zrobić to samo, do następnego itd., a nie wiem czy to się da jakoś sensownie zapisać.
Wiem jeszcze, że jest iniekcja \(\displaystyle{ g: \NN \rightarrow \{A_n: n \in \NN\}}\). Teraz wystarczyłoby wyjaśnić, że \(\displaystyle{ \{A_n: n \in \NN\} \le \bigcup_{n \in \NN} A_n}\) i mamy zatem \(\displaystyle{ |\NN| =\{A_n: n \in \NN\} \le |\bigcup_{n\in \NN} A_n| \le |\NN \times \NN| = |\NN|}\). Teraz C-B i koniec dowodu.
1) Suma przeliczalnie wielu zbiorów przeliczalnych jest przeliczalna.
2) Suma co najwyżej przeliczalnie wielu zbiorów co najwyżej przeliczalnych jest co najwyżej przeliczalna.
3) Suma przeliczalnie wielu zbiorów co najwyżej przeliczalnych jest przeliczalna.
Oprócz tego mam przedstawiony dowód twierdzenia "Suma co najwyżej przeliczalnie wielu zbiórów przeliczalnych jest przeliczalna" (nazwę to Twierdzeniem T).
1) Dowód zawiera się bezpośrednio w dowodzie Twierdzenia T.
2) Muszę udowodnić:
a) Suma przeliczalnie wielu zbiorów przeliczalnych jest co najwyżej przeliczalna.
b) Suma przeliczalnie wielu zbiorów skończonych jest co najwyżej przeliczalna.
c) Suma skończenie wielu zbiorów skończonych jest co najwyżej przeliczalna.
d) Suma skończenie wielu zbiorów przeliczalnych jest co najwyżej przeliczalna.
a) Dowód zawarty w dowodzie Twierdzenia T.
b) Dowód 3 b).
c) Muszę to jakoś udowadniać czy mogę to uznać za "oczywiste"?
d) Tutaj dowód za pomocą twierdzenia "Suma dwóch zbiorów przeliczalnych jest przeliczalna", które możemy rozszerzyć indukcją matematyczną na skończoną liczbę zbiorów przeliczalnych.
3) Muszę udowodnić:
a) Suma przeliczalnie wielu zbiorów przeliczalnych jest przeliczalna.
b) Suma przeliczalnie wielu zbiorów skończonych jest przeliczalna.
a) Twierdzenie T.
b) \(\displaystyle{ f: \bigcup_{n\in \NN} A_n \rightarrow \NN \times \NN, f(n,k) = (n,k)}\) jest iniekcją czyli mamy \(\displaystyle{ |A_n| \le |\bigcup_{n\in \NN} A_n| \le |\NN \times \NN| = |\NN|}\). Udowodniłem, że suma przeliczalnie wielu zbiorów skończonych jest co najwyżej przeliczalna czyli 2 b). Brakuje najważniejszego kroku. Może do udowodnienia 3 b) powinienem podejść tak jak do Twierdzenia T?. Tzn. pierw wybrać zbiór z rodziny zbiorów tyle, że w Twierdzeniu T wybrany zbiór był nieskończony, a teraz funkcja musiałaby przelecieć wszystkie elementy danego zbioru, później przeskoczyć do drugiego zbioru zrobić to samo, do następnego itd., a nie wiem czy to się da jakoś sensownie zapisać.
Wiem jeszcze, że jest iniekcja \(\displaystyle{ g: \NN \rightarrow \{A_n: n \in \NN\}}\). Teraz wystarczyłoby wyjaśnić, że \(\displaystyle{ \{A_n: n \in \NN\} \le \bigcup_{n \in \NN} A_n}\) i mamy zatem \(\displaystyle{ |\NN| =\{A_n: n \in \NN\} \le |\bigcup_{n\in \NN} A_n| \le |\NN \times \NN| = |\NN|}\). Teraz C-B i koniec dowodu.
-
- Administrator
- Posty: 34128
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5192 razy
Zbiory przeliczalne 4: suma zbiorów
Co to jest za dziwna definicja?nne pisze:b) \(\displaystyle{ f: \bigcup_{n\in \NN} A_n \rightarrow \NN \times \NN, f(n,k) = (n,k)}\) jest iniekcją
JK
Zbiory przeliczalne 4: suma zbiorów
No jest bez sensu.
Więc mam jakąś funkcję na zbiorach \(\displaystyle{ f: \bigcup_{n\in \NN} A_n \rightarrow \NN \times \NN}\). Wiem poza tym, że istnieją bijekcje
\(\displaystyle{ g_0: \{1,2,3,...,n_1\} \rightarrow A_0}\)
\(\displaystyle{ g_1: \{n_1 + 1, n_1 + 2, ..., n_1 + n_2\} \rightarrow A_1}\)
\(\displaystyle{ g_k: \{...\}}\), gdzie \(\displaystyle{ k \in \NN}\)
i teraz zdefiniowałbym funkcję \(\displaystyle{ f}\) z pomocą tych funkcji \(\displaystyle{ g}\) czyli \(\displaystyle{ f(g_k(n)) = (k,n)}\). Mogę tak czy to też jest bez sensu?
Więc mam jakąś funkcję na zbiorach \(\displaystyle{ f: \bigcup_{n\in \NN} A_n \rightarrow \NN \times \NN}\). Wiem poza tym, że istnieją bijekcje
\(\displaystyle{ g_0: \{1,2,3,...,n_1\} \rightarrow A_0}\)
\(\displaystyle{ g_1: \{n_1 + 1, n_1 + 2, ..., n_1 + n_2\} \rightarrow A_1}\)
\(\displaystyle{ g_k: \{...\}}\), gdzie \(\displaystyle{ k \in \NN}\)
i teraz zdefiniowałbym funkcję \(\displaystyle{ f}\) z pomocą tych funkcji \(\displaystyle{ g}\) czyli \(\displaystyle{ f(g_k(n)) = (k,n)}\). Mogę tak czy to też jest bez sensu?
-
- Administrator
- Posty: 34128
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5192 razy
Zbiory przeliczalne 4: suma zbiorów
Jaką funkcję i skąd ja masz?nne pisze:Więc mam jakąś funkcję na zbiorach \(\displaystyle{ f: \bigcup_{n\in \NN} A_n \rightarrow \NN \times \NN}\).
JK
Zbiory przeliczalne 4: suma zbiorów
No zacząłem jakby od nowa 3 b) i w momencie zacytowanym jeszcze nie miałem zdefiniowanej funkcji. Może źle się wyraziłem. Najpierw ustaliłem dziedzinę i przeciwdziedzinę dla funkcji, a poniżej (pod funkcjami \(\displaystyle{ g_k}\)) dopiero zdefiniowałem funkcję \(\displaystyle{ f}\).
-
- Administrator
- Posty: 34128
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5192 razy
Zbiory przeliczalne 4: suma zbiorów
Zupełnie mi się to nie podoba. Jak zamierzasz pokazać, że funkcja \(\displaystyle{ f}\) jest dobrze zdefiniowana?
JK
JK
Zbiory przeliczalne 4: suma zbiorów
\(\displaystyle{ f: \NN \rightarrow \{A_n: n \in \NN\}}\)
\(\displaystyle{ g^{-1}_n: A_n \rightarrow \{n+1, n+2,...,m\}}\)
\(\displaystyle{ g_n: \{n+1,n+2,...,m\} \rightarrow A_n}\)
\(\displaystyle{ i: \NN \rightarrow \bigcup_{n\in \NN} A_n, i(n) = (g_n \circ g_n^{-1} \circ f)(n)}\).
Funkcja \(\displaystyle{ i(n)}\) jest bijekcją co kończy dowód.
Może być?
\(\displaystyle{ g^{-1}_n: A_n \rightarrow \{n+1, n+2,...,m\}}\)
\(\displaystyle{ g_n: \{n+1,n+2,...,m\} \rightarrow A_n}\)
\(\displaystyle{ i: \NN \rightarrow \bigcup_{n\in \NN} A_n, i(n) = (g_n \circ g_n^{-1} \circ f)(n)}\).
Funkcja \(\displaystyle{ i(n)}\) jest bijekcją co kończy dowód.
Może być?
-
- Administrator
- Posty: 34128
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5192 razy
Zbiory przeliczalne 4: suma zbiorów
Nie. Nawet byty się nie zgadzają, bo \(\displaystyle{ i=f}\).
Dużo prościej jest skorzystać z tw. C-B i w tym celu wystarczy pokazać, że suma przeliczalnie wielu zbiorów skończonych jest nieskończona (co daje oszacowanie z dołu, oszacowanie z góry już masz). W tym celu wystarczy założyć nie wprost, że jest skończona. Ale każdy z wyjściowych zbiorów jest podzbiorem tej sumy, jest ich przeliczalnie (czyli nieskończenie) wiele, a zbiór skończony ma tylko skończenie wiele podzbiorów - sprzeczność.
A tak ogólnie umiarkowanie podoba mi się całe to twoje rozpisanie - komplikujesz sobie życie. Po co rozbijać co najwyżej przeliczalność na dwa przypadki - nieskończony i skończony?
JK
Dużo prościej jest skorzystać z tw. C-B i w tym celu wystarczy pokazać, że suma przeliczalnie wielu zbiorów skończonych jest nieskończona (co daje oszacowanie z dołu, oszacowanie z góry już masz). W tym celu wystarczy założyć nie wprost, że jest skończona. Ale każdy z wyjściowych zbiorów jest podzbiorem tej sumy, jest ich przeliczalnie (czyli nieskończenie) wiele, a zbiór skończony ma tylko skończenie wiele podzbiorów - sprzeczność.
A tak ogólnie umiarkowanie podoba mi się całe to twoje rozpisanie - komplikujesz sobie życie. Po co rozbijać co najwyżej przeliczalność na dwa przypadki - nieskończony i skończony?
JK
Zbiory przeliczalne 4: suma zbiorów
Jeżeli mam nie rozbijać tego trzeciego zadania to wychodzi mi na to, że Pana dowód nie wprost jest poprawny dla całego zadania trzeciego. Pozostaje mi pokazać \(\displaystyle{ |A| \le \aleph_0}\) (\(\displaystyle{ A}\) to dla uproszczenia suma). Wystarczy pokazać suriekcję \(\displaystyle{ f: \NN \times \NN \rightarrow A, f(n,k) = f_n (k)}\), ale tutaj pojawia się problemy, gdy podzbiór \(\displaystyle{ A_n}\) sumy jest skończony. Wtedy nasza funkcja nie jest dobrze zdefiniowana...
W sumie jak zaznaczę, że
\(\displaystyle{ f_1: \{1,2,...,k\} \rightarrow^{1-1}_{na} A_1}\)
\(\displaystyle{ f_2: \{k+1, k+2,...,l\} \rightarrow^{1-1}_{na} A_2}\) itd.,
i zdefiniuję
\(\displaystyle{ f(n,k) = \begin{cases} f_n (k) &\text {jeśli} \ k \in D_{f_n} \\f_m (k) &\text {jeśli} \ k \in D_{f_m} \end {cases}}\)
to chyba już lepiej czy nadal do bani?
W sumie jak zaznaczę, że
\(\displaystyle{ f_1: \{1,2,...,k\} \rightarrow^{1-1}_{na} A_1}\)
\(\displaystyle{ f_2: \{k+1, k+2,...,l\} \rightarrow^{1-1}_{na} A_2}\) itd.,
i zdefiniuję
\(\displaystyle{ f(n,k) = \begin{cases} f_n (k) &\text {jeśli} \ k \in D_{f_n} \\f_m (k) &\text {jeśli} \ k \in D_{f_m} \end {cases}}\)
to chyba już lepiej czy nadal do bani?
-
- Administrator
- Posty: 34128
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5192 razy
Zbiory przeliczalne 4: suma zbiorów
Dlaczego? Ta funkcja jest dobrze zdefiniowana.nne pisze:Jeżeli mam nie rozbijać tego trzeciego zadania to wychodzi mi na to, że Pana dowód nie wprost jest poprawny dla całego zadania trzeciego. Pozostaje mi pokazać \(\displaystyle{ |A| \le \aleph_0}\) (\(\displaystyle{ A}\) to dla uproszczenia suma). Wystarczy pokazać suriekcję \(\displaystyle{ f: \NN \times \NN \rightarrow A, f(n,k) = f_n (k)}\), ale tutaj pojawia się problemy, gdy podzbiór \(\displaystyle{ A_n}\) sumy jest skończony. Wtedy nasza funkcja nie jest dobrze zdefiniowana...
JK
Zbiory przeliczalne 4: suma zbiorów
A czy funkcja nie musi przypisywać każdemu elementowi dziedziny jakiegoś elementu przeciwdziedziny? Weźmy sumę przeliczalnie wielu zbiorów skończonych. Niech \(\displaystyle{ A_1 = \{a\}}\). Wiemy, że istnieje bijekcja \(\displaystyle{ f_1: \{1\} \rightarrow \{a\}}\). Czyli \(\displaystyle{ f(1,1) = a}\). Co przypiszemy elementowi \(\displaystyle{ (1,2) \in \NN \times \NN}\)?
-
- Administrator
- Posty: 34128
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5192 razy
Zbiory przeliczalne 4: suma zbiorów
Ale mnie nie interesuje taka funkcja \(\displaystyle{ f_1}\). Ja dla każdego \(\displaystyle{ n}\) mam surjekcję \(\displaystyle{ f_n:\NN\to A_n}\).
JK
JK
Zbiory przeliczalne 4: suma zbiorów
Teraz chyba już wszystko jasne. Jeszcze ponowie pytanie odnośnie 2 c).
-
- Administrator
- Posty: 34128
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5192 razy
Zbiory przeliczalne 4: suma zbiorów
Suma skończenie wielu zbiorów skończonych jest skończona. To, czy uznasz to za oczywiste, zależy od poziomu formalizmu. W razie czego dowodzisz tego indukcyjnie.
Z drugiej strony, tak naprawdę punkt 2c) nie jest Ci do niczego potrzebny (tzn. nie ma potrzeby rozbijania punktu 2 na cztery podpunkty).
JK
Z drugiej strony, tak naprawdę punkt 2c) nie jest Ci do niczego potrzebny (tzn. nie ma potrzeby rozbijania punktu 2 na cztery podpunkty).
JK
Zbiory przeliczalne 4: suma zbiorów
Muszę pokazać \(\displaystyle{ |A| \le |\NN|}\). Więc znowu muszę szukać suriekcji \(\displaystyle{ \NN \rightarrow A}\) i czy to takie prostsze skoro wcześniej już miałem wszystkie dowody praktycznie na tacy? \(\displaystyle{ f: \NN \times \NN \rightarrow A, f(n,k) = f_n (k)}\) tym razem nic mi nie daje, bo mogę mieć skończenie wiele zbiorów, których elementy tworzą sumę czyli funkcja nie będzie dobrze zdefiniowana.
Mój błąd przecież mogę sobie "stworzyć" nieskończenie wiele takich samych zbiorów czyli wszystko gra. Podsumowując wystarczy tak jak już pisałem rozpatrzeć funkcję \(\displaystyle{ f: \NN \times \NN \rightarrow A, f(n,k) = f_n (k)}\) tzn. pokazać, że jest suriekcją.
Mój błąd przecież mogę sobie "stworzyć" nieskończenie wiele takich samych zbiorów czyli wszystko gra. Podsumowując wystarczy tak jak już pisałem rozpatrzeć funkcję \(\displaystyle{ f: \NN \times \NN \rightarrow A, f(n,k) = f_n (k)}\) tzn. pokazać, że jest suriekcją.