indukcyjny dowod przeliczalnosci zbioru A^+

[wapnoziom]

Probuje udowodnic indukcyjne ze
Zakladajac ze zbior A jest przeliczalny to zbior \(\displaystyle{ A ^{n}}\) , gdzie
n nalezy do liczb dodatnich calkowitych

krok pierwszy dla \(\displaystyle{ A^{1}}\) powstanie z tego po prostu A co jest przeliczalne z zalozenia

krok drugi niech \(\displaystyle{ A^{k}}\) bedzie przeliczalne o ile A jest przeliczalne i k nalezy do dodatnich calkowitych
i teraz musze udowodnic ze \(\displaystyle{ A ^{k+1}}\)

Logiczne dla mnie ze jesli zapisze dany zbior jako ciag to bedzie to jednoznaczne z przyporzadkowaniem go do zbioru liczb naturalnych (wykazanie bijekcji). Ale bede szczery ze mam duze problemy z zapisaniem tego, rowniez mam problem z zapisaniem tego ciagu dla \(\displaystyle{ A^{k+1}}\) , wydaje mi sie ze powinienem przejsc do zapisu \(\displaystyle{ A \cdot A^{k}}\) i wtedy zapisywac go jako ciag przeliczalny \(\displaystyle{ A ^{k}}\) pomnozony przezstala, tylko ze musze udowodnic przy okazji ze samo
\(\displaystyle{ A^{k}}\) jest przeliczalne i tu tez jest problem, AxA jest dosc proste gdyz zapisuje go jako (a1a1, a2a1, a1a2 a3a1 a2a2 a1a3....) co przyporzadkowuje do liczb naturalnych i jest to zbior przeliczalny, ale dla wiekszych poteg mam problem z zapisem tego, pomoze ktos?

[UNIX_admin]

chyba w dowodzie wystarczy wyjsc od tego, ze moc iloczynu zbiorow jest rowna iloczynowi mocy tych zbiorow (prawo mnozenia)

mozna to tez ladnie rozpisac, bo jeśli \(\displaystyle{ A=(a_1, a_2, a_3, \dots, a_r)}\)


to \(\displaystyle{ A^n=(a_1, a_2, a_3, \dots, a_r)^n = \sum_{k_1,k_2,k_3, \dots ,k_r \choose k_1+k_2+k_3+ \dots +k_r = n}^{} \frac{n!}{k_1! k_2! k_3! \dots k_r!} a_1^{k_1}a_2^{k_2}a_3^{k_3} \dots a_r^{k_r}}\)

[Jan Kraszewski]

chyba w dowodzie wystarczy wyjsc od tego, ze moc iloczynu zbiorow jest rowna iloczynowi mocy tych zbiorow (prawo mnozenia)

mozna to tez ladnie rozpisac, bo jeśli \(\displaystyle{ A=(a_1, a_2, a_3, \dots, a_r)}\)

to \(\displaystyle{ A^n=(a_1, a_2, a_3, \dots, a_r)^n = \sum_{k_1,k_2,k_3, \dots ,k_r \choose k_1+k_2+k_3+ \dots +k_r = n}^{} \frac{n!}{k_1! k_2! k_3! \dots k_r!} a_1^{k_1}a_2^{k_2}a_3^{k_3} \dots a_r^{k_r}}\)

Co to ma być? W szczególności dla nieskończonego zbioru \(\displaystyle{ A}\)?

wapnoziom, żeby pokazać to, co chcesz, musisz najpierw pokazać, że jeśli \(\displaystyle{ A}\) jest przeliczalny, to \(\displaystyle{ A^2}\) jest przeliczalny. By to pokazać, musisz skorzystać z faktu, że zbiory\(\displaystyle{ \mathbb{N}}\) i \(\displaystyle{ \mathbb{N}^2}\) są równoliczne.

JK

[UNIX_admin]

faktycznie, wzmianka o prawie mnozenia (bez dodatkowego komentarza) jest nie na miejscu, nie doczytalem ze zbior jest przeliczalny, a nie skonczony.

Jednak dalsza czesc jest jak najbardziej poprawna i pokazuje, jak uszeregowac taki iloczyn zbiorow.

P.S. troche niefortunnie dobralem oznaczenia, moje "k" to nie "k" z zadania

[Jan Kraszewski]

Jednak dalsza czesc jest jak najbardziej poprawna i pokazuje, jak uszeregowac taki iloczyn zbiorow.

Jaki iloczyn chcesz szeregować? Zbiorów nieskończonych?

JK

[wapnoziom]

hmmm
czyli to bedzie tak
A jest przeliczalny, i \(\displaystyle{ A=\left\{ a1,a2,a3...\right\}}\)
wtedy
\(\displaystyle{ A \cdot A=\left\{ a1a1, a2a1, a1a2 a3a1 a2a2 a1a3....\right\}}\)

tworze pary teraz \(\displaystyle{ \left\{(1,a1a1), (2,a2a1), (3,a1a2) ...\right\}}\)

czyli przyporzadkowalem kazdemu elementowi z \(\displaystyle{ A \cdot A}\) liczbe naturalna(czy moze odwrotnie?), wiec stworzylem bijekcje, ale cos mi sie wydaje ze to malo formalny zapis tego jest

[UNIX_admin]

Jaki iloczyn chcesz szeregować? Zbiorów nieskończonych?

JK

przeliczalnych

[Jan Kraszewski]

czyli to bedzie tak
A jest przeliczalny, i \(\displaystyle{ A=\left\{ a1,a2,a3...\right\}}\)
wtedy
\(\displaystyle{ A \cdot A=\left\{ a1a1, a2a1, a1a2 a3a1 a2a2 a1a3....\right\}}\)

tworze pary teraz \(\displaystyle{ \left\{(1,a1a1), (2,a2a1), (3,a1a2) ...\right\}}\)

czyli przyporzadkowalem kazdemu elementowi z \(\displaystyle{ A \cdot A}\) liczbe naturalna(czy moze odwrotnie?), wiec stworzylem bijekcje, ale cos mi sie wydaje ze to malo formalny zapis tego jest

Po pierwsze, masz iloczyn kartezjański \(\displaystyle{ A\times A}\), symbol " imes". To nie jest kompleksowy iloczyn algebraiczny. Zatem elementami \(\displaystyle{ A\times A}\) są pary uporządkowane.
Po drugie, używaj dolnych indeksów (i przecinków).
Po trzecie, myśl masz dobrą, ale mało formalną i nie całkiem poprawną.

przeliczalnych

Jakoś tego nie widzę.

JK

[wapnoziom]

hmmm
czyli to bedzie tak
A jest przeliczalny, i \(\displaystyle{ A=\left\{ a _{1} ,a _{2},a _{3}...\right\}}\)
wtedy
\(\displaystyle{ AxA=\left\{ a _{1}a _{1}, a _{2}a _{1}, a _{1}a _{2}, a _{3}a _{1}, a _{2}a _{2}, a _{1}a _{3},....\right\}}\)

tworze pary teraz \(\displaystyle{ \left\{(1,a _{1}a _{1}), (2,a _{2}a _{1}), (3,a _{1}a _{2}), ...\right\}}\)

czyli przyporzadkowalem kazdemu elementowi z AxA liczbe naturalna(czy moze odwrotnie?), wiec stworzylem bijekcje, ale cos mi sie wydaje ze to malo formalny zapis tego jest

1 ok
2 ok
3 czyli co jest niepoprawne:)? i jak to sformalizowac

[Jan Kraszewski]

No zapis dalej marnie:

\(\displaystyle{ A\times A=\{(a_1,a_1), (a_2,a_1), (a_1,a_2),...\}}\)

Dobra, poprawności już się nie czepiam, istotnie podałeś pewien pomysł, jak skonstruować bijekcję z liczb naturalnych w \(\displaystyle{ A\times A}\). Natomiast formalizm na niskim poziomie.

Po pierwsze, musisz doprecyzować, co to znaczy, że \(\displaystyle{ A=\left\{ a _{1} ,a _{2},a _{3}...\right\}}\).
Po drugie, musisz sformalizować, co to znaczy, że \(\displaystyle{ A\times A=\{(a_1,a_1), (a_2,a_1), (a_1,a_2),...\}}\).
W obu przypadkach oznacza to odwołanie się do definicji oraz skorzystanie z pojęcia funkcji. Głównym problemem będzie zapisanie wzorem funkcji ustawiającej pary w ciąg. Jak już to zrobisz, to możesz zabrać się za pokazywanie, że zdefiniowana przez Ciebie funkcja jest bijekcją.

JK

PS. Ja tam wolę pokazać najpierw, że \(\displaystyle{ \mathbb{N}}\) i \(\displaystyle{ \mathbb{N}^2}\) są równoliczne, a potem tylko z tego skorzystać, ale de gustibus...