Matematyka.pl

Udowodnić, że zbiór słów nad alfabetem skończonym jest zbiorem przeliczalnym.

Jak to zrobić? Może mi ktoś pomóc?

Policz ile jest słów `n`-literowych

Ok, no zakładając, że alfabet ma \(\displaystyle{ L}\) znaków, to będzie \(\displaystyle{ L^n}\). Czyli ten zbiór będzie zawierał \(\displaystyle{ L+L^2+L^3+L^4+L^5+...}\) elementów. Czyli tych elementów będzie \(\displaystyle{ L\cdot \frac{1-L^n}{1-L}}\) przy \(\displaystyle{ n \rightarrow \infty}\), no to z tej postaci już chyba widać, że moc tego zbioru jest taka sama jak moc zbioru liczb naturalnych. Chociaż nie wiem czy dobrze mówię?

max123321 pisze: ↑10 cze 2024, o 18:01Czyli ten zbiór będzie zawierał \(\displaystyle{ L+L^2+L^3+L^4+L^5+...}\) elementów. Czyli tych elementów będzie \(\displaystyle{ L\cdot \frac{1-L^n}{1-L}}\) przy \(\displaystyle{ n \rightarrow \infty}\), no to z tej postaci już chyba widać, że moc tego zbioru jest taka sama jak moc zbioru liczb naturalnych. Chociaż nie wiem czy dobrze mówię?

Nie bardzo. Ten zbiór to \(\displaystyle{ \bigcup_{n\in\NN}S^n }\), gdzie \(\displaystyle{ |S^n|=L^n}\), czyli przeliczalna suma zbiorów skończonych, czyli zbiór przeliczalny.

JK

Dodam jeszcze, że zbiór wszystkich takich słów nad alfabetem \(\displaystyle{ S=\left\{ w _{1}; w _{2}; \ldots; w _{n} \right\} }\) istotnie jest nieskończony, bo można rozważyć takie słowa:
\(\displaystyle{ \left( w _{1} \right); \left( w _{1},w _{1} \right) ; \left( w _{1}; w _{1}; w _{1} \right); \ldots }\)
których to słów jest oczywiście tyle, ile jest liczb naturalnych dodatnich, a więc nieskończenie wiele.

To jest zbędne. Suma rodziny mocy \(\displaystyle{ \aleph_0}\) zbiorów skończonych (a taka sytuacja tutaj występuje) jest na mocy twierdzenia mocy \(\displaystyle{ \aleph_0.}\)

Przeliczalna suma zbiorów skończonych nie musi być nieskończona

a4karo pisze: ↑10 cze 2024, o 21:57 Przeliczalna suma zbiorów skończonych nie musi być nieskończona

Przeczytaj uważnie:

Jan Kraszewski pisze: ↑10 cze 2024, o 19:58 Suma rodziny mocy \(\displaystyle{ \aleph_0}\) zbiorów skończonych

Gdyby suma takiej rodziny była skończona, to suma ta miałaby skończenie wiele podzbiorów. Z drugiej strony każdy element rodziny mocy \(\displaystyle{ \aleph_0}\) jest podzbiorem sumy tej rodziny i mamy sprzeczność, bo w tej rodzinie jest nieskończenie wiele elementów, a suma ma tylko skończenie wiele podzbiorów.

JK

Jest taki fakt, że dla dowolnego \(\displaystyle{ n}\) oraz dowolnych ciągów \(\displaystyle{ \epsilon ,\sigma \in \{0,1\}^{\NN}}\) zachodzi równoważność


Dowód \(\displaystyle{ (\Leftarrow)}\) jest oczywisty. W drugą stronę; przypuśćmy nie wprost, że \(\displaystyle{ \sum_{i=1}^{n} \frac{\epsilon_i}{2^i} = \sum_{i=1}^{n} \frac{\sigma_i}{2^i}}\) mimo, iż dla pewnych \(\displaystyle{ i\in\{1,\dots,n\}}\) mamy \(\displaystyle{ \epsilon_i \neq \sigma_i}\). Niech \(\displaystyle{ i^*}\) będzie najmniejszym z takich \(\displaystyle{ i}\). Można wtedy zapisać, że

dla pewnego ciągu \(\displaystyle{ \xi}\) powstałego z różnic pomiędzy \(\displaystyle{ \epsilon ,\sigma}\) lub odwrotnie, zatem przyjmującego możliwe wartości \(\displaystyle{ -1,0,1}\). To jednak nie możliwe ponieważ nawet, gdyby \(\displaystyle{ \xi = 1 }\) zawsze, to prawa strona była by zbyt mała. To znaczy


Ten fakt ma swój odpowiednik dla \(\displaystyle{ n=\infty}\) ale to nie jest w tym momencie istotne. Można pokazać nawet więcej. Mianowicie nie jest ważne, że \(\displaystyle{ n}\) jest ustalone. Dla dowolnych \(\displaystyle{ m,n}\) oraz dowolnego ciągu \(\displaystyle{ \xi \in \{-1,0,1\}^{\NN}}\) zachodzi

Znów kierunek \(\displaystyle{ (\Leftarrow)}\) jest oczywisty. A w drugą stronę założenie nie wprost daje możliwość zapisania


gdzie \(\displaystyle{ i^*}\) jest pierwszym indeksem dla którego \(\displaystyle{ \xi \neq 0}\). To jednak sprzeczność z tego samego powodu co wcześniej. Zatem funkcja przypisująca skończonym ciągom \(\displaystyle{ \{0,1\}^{<\omega}}\) (naturalnie zanurzonych w \(\displaystyle{ \{0,1\}^{\omega}}\) poprzez konkatencje z zerem) wymierną sumę \(\displaystyle{ \sum_{}^{} \epsilon_i/2^i}\) jest różnowartościowym włożeniem \(\displaystyle{ \{0,1\}^{<\omega}}\) w \(\displaystyle{ \QQ}\). Zatem \(\displaystyle{ \left| \{0,1\}^{<\omega}\right| =\aleph_0 }\). To, że tu alfabet ma dwa elementy nie ma większego znaczenia. Do póki elementów jest skończenie wiele to podobny argument powinien działać. Może trzeba jedynie zmienić system z \(\displaystyle{ 2}\)-kowego na \(\displaystyle{ \left| L\right| }\)-arny lub zauważyć, że dla pewnego \(\displaystyle{ p}\) nieformalnie mówiąc, mamy \(\displaystyle{ \left| L^{<\omega}\right| \le \left| (\{0,1\}^p)^{<\omega}\right| = \left| \{0,1\}^{<p\omega} \right| =\aleph_0 }\).

Jan Kraszewski pisze: ↑10 cze 2024, o 18:19

max123321 pisze: ↑10 cze 2024, o 18:01Czyli ten zbiór będzie zawierał \(\displaystyle{ L+L^2+L^3+L^4+L^5+...}\) elementów. Czyli tych elementów będzie \(\displaystyle{ L\cdot \frac{1-L^n}{1-L}}\) przy \(\displaystyle{ n \rightarrow \infty}\), no to z tej postaci już chyba widać, że moc tego zbioru jest taka sama jak moc zbioru liczb naturalnych. Chociaż nie wiem czy dobrze mówię?

Nie bardzo. Ten zbiór to \(\displaystyle{ \bigcup_{n\in\NN}S^n }\), gdzie \(\displaystyle{ |S^n|=L^n}\), czyli przeliczalna suma zbiorów skończonych, czyli zbiór przeliczalny.

JK

Czy jeżeli `A_i={π}`, to suma tej rodziny jest przeliczalna

Dodano po 7 minutach 14 sekundach:

Janusz Tracz pisze: ↑10 cze 2024, o 22:45 jest różnowartościowym włożeniem \(\displaystyle{ \{0,1\}^{<\omega}}\) w \(\displaystyle{ \QQ}\). Zatem \(\displaystyle{ \left| \{0,1\}^{<\omega}\right| =\aleph_0 }\).

A jak stąd wynika, że zbiór po lewej stronie jest nieskończony?
`f(X)=x` jest różnowartosciowym włożeniem `{0,1}` w `\QQ`...

a4karo pisze: ↑11 cze 2024, o 08:20 A jak stąd wynika, że zbiór po lewej stronie jest nieskończony?
`f(X)=x` jest różnowartosciowym włożeniem `{0,1}` w `\QQ`...

Po pierwsze to czy muszę pokazywać nieskończoność \(\displaystyle{ \left\{ 0,1\right\}^{<\omega} }\) zależy od przyjętej definicji zbioru przeliczalnego. Jeśli zbiór jest \(\displaystyle{ \le \aleph_0}\), co pokazuje różnowartościowe włożenie, to niektórzy już powiedzą, że jest przeliczalny (a to było celem). Osobiście takiej definicji nie lubię i wolę przeliczalność definiować przez \(\displaystyle{ = \aleph_0}\). Jednak rozumowanie, że \(\displaystyle{ \aleph_0 \le \left| \left\{ 0,1\right\}^{<\omega} \right| }\) jest niewspółmiernie prostsze do nierówności przeciwnej. Potem korzysta się z twierdzenia Cantora–Bernsteina oczywiście. Jednak pisanie takich oczywistości pewnie by się skończyło uznaniem ich za kolejną lekcję formalizmu.

a4karo pisze: ↑11 cze 2024, o 08:20 Czy jeżeli `A_i={π}`, to suma tej rodziny jest przeliczalna

To wtedy jest to rodzina jednoelementowa, a nie rodzina mocy \(\displaystyle{ \aleph_0}\).

JK

I zbiór wszystkich ciągów skończonych o elementach zbioru \(\displaystyle{ A _{i}= \left\{ \pi \right\} }\) musi być nieskończony; -gdyż można rozważyć takie ciągi skończone:
\(\displaystyle{ \left( \pi \right); \left( \pi , \pi \right); \left( \pi , \pi , \pi \right); \ldots }\)
których to ciągów jest oczywiście tyle, ile jest liczb naturalnych dodatnich, a więc nieskończenie wiele.\(\displaystyle{ \square}\)
(Chyba się dubluje, ale pomagam a4karo-wi, który nie ogarnia).

Dodano po 11 minutach 25 sekundach:
Przykład dla sumy:
Dla \(\displaystyle{ n=1,2,3,\ldots}\) weź:
\(\displaystyle{ A _{n} =\left\{ 1,2,\ldots,n \right\}. }\) I wtedy:
\(\displaystyle{ \bigcup_{n \in \NN _{+} } A _{n}=\NN _{+}\sim \NN.}\)

Jakub Gurak pisze: ↑11 cze 2024, o 13:44 I zbiór wszystkich ciągów skończonych o elementach zbioru \(\displaystyle{ A _{i}= \left\{ \pi \right\} }\) musi być nieskończony; -gdyż można rozważyć takie ciągi skończone:
\(\displaystyle{ \left( \pi \right); \left( \pi , \pi \right); \left( \pi , \pi , \pi \right); \ldots }\)
których to ciągów jest oczywiście tyle, ile jest liczb naturalnych dodatnich, a więc nieskończenie wiele.\(\displaystyle{ \square}\)
(Chyba się dubluje, ale pomagam a4karo-wi, który nie ogarnia).

Jakubie, jak nie rozumiesz, o czym dyskutujemy, to lepiej się nie wtrącaj, bo efekt jest żałosny - zapewniam Cię, że a4karo ogarnia dużo lepiej od Ciebie. A powyższy przykład nie ma z tą dyskusją nic wspólnego, więc to raczej Ty nie ogarniasz.

Jakub Gurak pisze: ↑11 cze 2024, o 13:44 Przykład dla sumy:
Dla \(\displaystyle{ n=1,2,3,\ldots}\) weź:
\(\displaystyle{ A _{n} =\left\{ 1,2,\ldots,n \right\}. }\) I wtedy:
\(\displaystyle{ \bigcup_{n \in \NN _{+} } A _{n}=\NN _{+}\sim \NN.}\)

No i co z tego?

JK

Życie nie jest aż tak proste. Jeżeli `P_n` oznacza zbiór liczb pierwszych bliźniaczych mniejszych od `n` to każdy z tych zbiorów niewątpliwie jest skończony, się obawiałbym się stwierdzenia, że jego suma jest nieskończona.

Dodano po 2 minutach 25 sekundach:
Może się okazać, że o każdym że zbiorów wiemy że jest skończony, ale nie jesteśmy w stanie stwierdzić, czy ich uniwersum jest nieskończona. Wtedy Twoje stwierdzenie staje się wątpliwe