Zbiór słów

Algebra zbiorów. Relacje, funkcje, iloczyny kartezjańskie... Nieskończoność, liczby kardynalne... Aksjomatyka.
max123321
Użytkownik
Użytkownik
Posty: 3446
Rejestracja: 26 maja 2016, o 01:25
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 1004 razy
Pomógł: 3 razy

Zbiór słów

Post autor: max123321 »

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

Jak to zrobić? Może mi ktoś pomóc?
a4karo
Użytkownik
Użytkownik
Posty: 22288
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3768 razy

Re: Zbiór słów

Post autor: a4karo »

Policz ile jest słów `n`-literowych
max123321
Użytkownik
Użytkownik
Posty: 3446
Rejestracja: 26 maja 2016, o 01:25
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 1004 razy
Pomógł: 3 razy

Re: Zbiór słów

Post autor: max123321 »

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ę?
Jan Kraszewski
Administrator
Administrator
Posty: 34530
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 4 razy
Pomógł: 5226 razy

Re: Zbiór słów

Post autor: Jan Kraszewski »

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
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1427
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 69 razy
Pomógł: 84 razy

Re: Zbiór słów

Post autor: Jakub Gurak »

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. :lol:
Jan Kraszewski
Administrator
Administrator
Posty: 34530
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 4 razy
Pomógł: 5226 razy

Re: Zbiór słów

Post autor: Jan Kraszewski »

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.}\)
a4karo
Użytkownik
Użytkownik
Posty: 22288
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3768 razy

Re: Zbiór słów

Post autor: a4karo »

Przeliczalna suma zbiorów skończonych nie musi być nieskończona
Ostatnio zmieniony 10 cze 2024, o 22:08 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Jan Kraszewski
Administrator
Administrator
Posty: 34530
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 4 razy
Pomógł: 5226 razy

Re: Zbiór słów

Post autor: Jan Kraszewski »

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
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4119
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 82 razy
Pomógł: 1411 razy

Re: Zbiór słów

Post autor: Janusz Tracz »

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

\(\displaystyle{ \sum_{i=1}^{n} \frac{\epsilon_i}{2^i} = \sum_{i=1}^{n} \frac{\sigma_i}{2^i} \quad \Longleftrightarrow \quad \bigwedge_{i=1}^n \epsilon_i = \sigma_i.}\)

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
\(\displaystyle{ \frac{1}{2^{i*}} = \sum_{i=i^*+1}^{n} \frac{\xi_i}{2^i} }\)

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

\(\displaystyle{ \sum_{i=i^*+1}^{n} \frac{\xi_i}{2^i} \le \sum_{i=i^*+1}^{n} \frac{1}{2^i} = \frac{1}{2^{i^*}} - \frac{1}{2^n} < \frac{1}{2^{i^*}}.}\)

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

\(\displaystyle{ \sum_{i=m}^{n} \frac{\xi_i}{2^i} =0 \quad \Longleftrightarrow \quad \bigwedge_{i=m}^n \xi_i = 0.}\)
Znów kierunek \(\displaystyle{ (\Leftarrow)}\) jest oczywisty. A w drugą stronę założenie nie wprost daje możliwość zapisania

\(\displaystyle{ \frac{1}{2^{i^*}} = \sum_{i=i^*+1}^{n} \frac{\xi_i}{2^i}, }\)

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 }\).
a4karo
Użytkownik
Użytkownik
Posty: 22288
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3768 razy

Re: Zbiór słów

Post autor: a4karo »

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`...
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4119
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 82 razy
Pomógł: 1411 razy

Re: Zbiór słów

Post autor: Janusz Tracz »

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.
Jan Kraszewski
Administrator
Administrator
Posty: 34530
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 4 razy
Pomógł: 5226 razy

Re: Zbiór słów

Post autor: Jan Kraszewski »

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
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1427
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 69 razy
Pomógł: 84 razy

Re: Zbiór słów

Post autor: Jakub Gurak »

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}\) :lol: 8-)
(Chyba się dubluje, ale pomagam a4karo-wi, który nie ogarnia). :P

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.}\) 8-)
Jan Kraszewski
Administrator
Administrator
Posty: 34530
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 4 razy
Pomógł: 5226 razy

Re: Zbiór słów

Post autor: Jan Kraszewski »

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}\) :lol: 8-)
(Chyba się dubluje, ale pomagam a4karo-wi, który nie ogarnia). :P
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.}\) 8-)
No i co z tego?

JK
a4karo
Użytkownik
Użytkownik
Posty: 22288
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3768 razy

Re: Zbiór słów

Post autor: a4karo »

Ż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
ODPOWIEDZ