Zbiory przeliczalne 4: suma zbiorów

Algebra zbiorów. Relacje, funkcje, iloczyny kartezjańskie... Nieskończoność, liczby kardynalne... Aksjomatyka.
nne

Zbiory przeliczalne 4: suma zbiorów

Post autor: nne » 25 cze 2013, o 13:25

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.

Jan Kraszewski
Administrator
Administrator
Posty: 30652
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz
Pomógł: 4889 razy

Zbiory przeliczalne 4: suma zbiorów

Post autor: Jan Kraszewski » 25 cze 2013, o 15:03

nne pisze:b) \(\displaystyle{ f: \bigcup_{n\in \NN} A_n \rightarrow \NN \times \NN, f(n,k) = (n,k)}\) jest iniekcją
Co to jest za dziwna definicja?

JK

nne

Zbiory przeliczalne 4: suma zbiorów

Post autor: nne » 25 cze 2013, o 17:07

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?

Jan Kraszewski
Administrator
Administrator
Posty: 30652
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz
Pomógł: 4889 razy

Zbiory przeliczalne 4: suma zbiorów

Post autor: Jan Kraszewski » 25 cze 2013, o 17:59

nne pisze:Więc mam jakąś funkcję na zbiorach \(\displaystyle{ f: \bigcup_{n\in \NN} A_n \rightarrow \NN \times \NN}\).
Jaką funkcję i skąd ja masz?

JK

nne

Zbiory przeliczalne 4: suma zbiorów

Post autor: nne » 25 cze 2013, o 18:02

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

Jan Kraszewski
Administrator
Administrator
Posty: 30652
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz
Pomógł: 4889 razy

Zbiory przeliczalne 4: suma zbiorów

Post autor: Jan Kraszewski » 25 cze 2013, o 21:46

Zupełnie mi się to nie podoba. Jak zamierzasz pokazać, że funkcja \(\displaystyle{ f}\) jest dobrze zdefiniowana?

JK

nne

Zbiory przeliczalne 4: suma zbiorów

Post autor: nne » 26 cze 2013, o 15:46

\(\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ć?

Jan Kraszewski
Administrator
Administrator
Posty: 30652
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz
Pomógł: 4889 razy

Zbiory przeliczalne 4: suma zbiorów

Post autor: Jan Kraszewski » 27 cze 2013, o 03:01

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

nne

Zbiory przeliczalne 4: suma zbiorów

Post autor: nne » 28 cze 2013, o 20:46

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?

Jan Kraszewski
Administrator
Administrator
Posty: 30652
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz
Pomógł: 4889 razy

Zbiory przeliczalne 4: suma zbiorów

Post autor: Jan Kraszewski » 28 cze 2013, o 23:12

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...
Dlaczego? Ta funkcja jest dobrze zdefiniowana.

JK

nne

Zbiory przeliczalne 4: suma zbiorów

Post autor: nne » 28 cze 2013, o 23:35

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

Jan Kraszewski
Administrator
Administrator
Posty: 30652
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz
Pomógł: 4889 razy

Zbiory przeliczalne 4: suma zbiorów

Post autor: Jan Kraszewski » 29 cze 2013, o 00:07

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

nne

Zbiory przeliczalne 4: suma zbiorów

Post autor: nne » 29 cze 2013, o 01:45

Teraz chyba już wszystko jasne. Jeszcze ponowie pytanie odnośnie 2 c).

Jan Kraszewski
Administrator
Administrator
Posty: 30652
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz
Pomógł: 4889 razy

Zbiory przeliczalne 4: suma zbiorów

Post autor: Jan Kraszewski » 29 cze 2013, o 02:22

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

nne

Zbiory przeliczalne 4: suma zbiorów

Post autor: nne » 29 cze 2013, o 03:03

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

ODPOWIEDZ