szukanie zaawansowane
 [ Posty: 40 ]  Przejdź na stronę 1, 2, 3  Następna strona
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 23 kwi 2018, o 07:42 
Użytkownik

Posty: 19
Lokalizacja: Lato
Mam takie pytanie, mam alfabet M = \{ a,b,c,d,e,f,g \} i zbiór wszystkich słów nad tym alfabetem to M^*. Jak pokazać że zbiór M^* jest równoliczny ze swoim podzbiorem (językiem L)? Proszę o szybką odpowiedź.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 23 kwi 2018, o 09:06 
Gość Specjalny

Posty: 5788
Lokalizacja: Toruń
Jest to zbiór przeliczalny, więc jest równoliczny z każdym innym przeliczalnym. W szczególności jest równoliczny z każdym swoim nieskończonym podzbiorem.
Góra
Mężczyzna Offline
PostNapisane: 23 kwi 2018, o 09:11 
Użytkownik

Posty: 19
Lokalizacja: Lato
A tę równoliczność dałoby radę zapisać za pomocą bijekcji pomiędzy tym zbiorem a podzbiorem?
Góra
Mężczyzna Offline
PostNapisane: 23 kwi 2018, o 09:39 
Administrator

Posty: 22651
Lokalizacja: Wrocław
Ja bym się nie podjął napisania bijekcji...

Najprościej skorzystać z twierdzenia (które trzeba znać bądź udowodnić), że suma przeliczalnie wielu zbiorów skończonych jest zbiorem przeliczalnym, apotem skorzystać z twierdzenia (które trzeba znać bądź udowodnić), o którym napisał bartek118.

JK
Góra
Mężczyzna Offline
PostNapisane: 23 kwi 2018, o 09:45 
Użytkownik

Posty: 19
Lokalizacja: Lato
A jak jest najprościej udowodnić że zbiór L jest zbiorem nieskończonym?
Góra
Mężczyzna Offline
PostNapisane: 23 kwi 2018, o 09:47 
Gość Specjalny

Posty: 5788
Lokalizacja: Toruń
Jan Kraszewski napisał(a):
Ja bym się nie podjął napisania bijekcji...


Myślę, że da się to zrobić. Potraktujmy każde słowo nad M jako liczbę zapisaną w systemie 8-kowym (każda litera to jedna cyfra, bez zera - aby nie było problemów z niejednoznacznością). Zamieniamy tę liczbę na system dziesiętny, a następnie takiej liczbie przyporządkujemy słowo składające się tylko z liter a, o tej właśnie długości.
Góra
Mężczyzna Offline
PostNapisane: 23 kwi 2018, o 10:36 
Administrator

Posty: 22651
Lokalizacja: Wrocław
lukas616 napisał(a):
A jak jest najprościej udowodnić że zbiór L jest zbiorem nieskończonym?

Ale co to jest L ?

bartek118 napisał(a):
Potraktujmy każde słowo nad M jako liczbę zapisaną w systemie 8-kowym (każda litera to jedna cyfra, bez zera - aby nie było problemów z niejednoznacznością). Zamieniamy tę liczbę na system dziesiętny, a następnie takiej liczbie przyporządkujemy słowo składające się tylko z liter a, o tej właśnie długości.

Ale między jakimi zbiorami ma to być bijekcja?

JK
Góra
Mężczyzna Offline
PostNapisane: 23 kwi 2018, o 10:52 
Użytkownik

Posty: 19
Lokalizacja: Lato
Zbiór L to jest podzbiór zbioru M^* czyli zbioru wszystkich możliwych słów nad alfabetem.
Góra
Mężczyzna Offline
PostNapisane: 23 kwi 2018, o 11:00 
Gość Specjalny

Posty: 5788
Lokalizacja: Toruń
lukas616 napisał(a):
Zbiór L to jest podzbiór zbioru M* czyli zbioru wszystkich możliwych słów nad alfabetem.


Na pewno nie może być dowolny. Musi być nieskończony.

Jan Kraszewski napisał(a):
lukas616 napisał(a):

Ale między jakimi zbiorami ma to być bijekcja?

JK


Z tego co zrozumiałem, to między M^* a jakimś podzbiorem M^*.
Informacyjnie - w informatyce, jeśli M to alfabet, a M^* to zbiór wszystkich słów nad tym alfabetem, to dowolny podzbiór L \subset M^* nazywa się językiem.
Góra
Mężczyzna Offline
PostNapisane: 23 kwi 2018, o 11:10 
Użytkownik

Posty: 19
Lokalizacja: Lato
DO zbioru M^* należą takie słowa jak \{ab, abcd, aaaaab, abcdeeee,....\} a do zbioru L należą słowa z języka polskiego np \{ada, baca, gafa, baba, ...\}.
Góra
Mężczyzna Offline
PostNapisane: 23 kwi 2018, o 11:18 
Administrator

Posty: 22651
Lokalizacja: Wrocław
bartek118 napisał(a):
Informacyjnie - w informatyce, jeśli M to alfabet, a M^* to zbiór wszystkich słów nad tym alfabetem, to dowolny podzbiór L \subset M^* nazywa się językiem.

To wiem, ale lukas616 jakoś nie potrafi poprawnie sformułować zadania, o które mu chodzi. Nagle w swoim piątym poście informuje nas, że

lukas616 napisał(a):
do zbioru L należą słowa z języka polskiego np \{ada, baca, gafa, baba, ...\}.

co jest dość istotną informacją... (choć dalej nie doprecyzował, czy do L należą wszystkie słowa języka polskiego nad tym alfabetem).

Tak czy inaczej dla mnie w tej wersji zadanie wydaje się nieprawdziwe - mam przekonanie, że słów języka polskiego jest skończenie wiele...

JK
Góra
Mężczyzna Offline
PostNapisane: 23 kwi 2018, o 11:24 
Użytkownik

Posty: 19
Lokalizacja: Lato
Skonkretyzuję moje zadanie: Niech zbiór L będzie zbiorem wszystkich napisów, które można utworzyć z liter ze zbioru M (dopuszczalne napisy mogą mieć dowolną długość, litery mogą występować wielokrotnie w napisie, nie muszą występować wszystkie litery). Udowodnij, że zbiór L jest nieskończony.
Góra
Mężczyzna Offline
PostNapisane: 23 kwi 2018, o 13:08 
Administrator

Posty: 22651
Lokalizacja: Wrocław
No wreszcie... Czyli zadanie dotyczy trochę czegoś innego, niż pisałeś - masz po prostu uzasadnić nieskończoność M^*.

Teraz kwestia kluczowa - jakiej definicji skończoności/nieskończoności zbioru używasz?

JK

PS
Niezależnie od tego, której definicji używasz, dowód nie jest trudny.
Góra
Mężczyzna Offline
PostNapisane: 23 kwi 2018, o 13:16 
Użytkownik

Posty: 19
Lokalizacja: Lato
Ja używam tej definicji: Zbiór A jest nieskończony jeżeli istnieje podzbiór B tego zbioru (B \subseteq A) taki że B nie jest równy A oraz B jest równoliczny z A. Znam jeszcze takie: Jeżeli A jest zbiorem nieskończonym i A  \subseteq  B to zbiór B także jest nieskończony oraz Jeżeli zbiór A jest nieskończony i zbiór B jest równoliczny z A to także B jest zbiorem nieskończonym. Jak te definicje przełożyć na moje zadanie?
Góra
Mężczyzna Offline
PostNapisane: 23 kwi 2018, o 15:06 
Administrator

Posty: 22651
Lokalizacja: Wrocław
Następny post bez \LaTeXa wyląduje w Koszu.

lukas616 napisał(a):
Ja używam tej definicji: Zbiór A jest nieskończony jeżeli istnieje podzbiór B tego zbioru (B \subseteq A) taki że B nie jest równy A oraz B jest równoliczny z A.

OK.

lukas616 napisał(a):
Znam jeszcze takie: Jeżeli A jest zbiorem nieskończonym i A  \subseteq  B to zbiór B także jest nieskończony oraz Jeżeli zbiór A jest nieskończony i zbiór B jest równoliczny z A to także B jest zbiorem nieskończonym. Jak te definicje przełożyć na moje zadanie?

To nie są definicje, tylko twierdzenia.

Rozważ właściwy podzbiór B zbioru M^*, np. B=M^*\setminus \{a\} i zdefiniuj bijekcję f:M^*\to B warunkiem

f(x)= \begin{cases} a^{n+1} &\mbox{gdy }x=a^n\mbox{ dla pewnego }n\in\NN^+ \\ x &\mbox{w pozostałych przypadkach} \end{cases}

gdzie a^n oznacza słowo składające się z n liter a. Oczywiście wypadałoby uzasadnić, że to istotnie bijekcja.

JK
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 40 ]  Przejdź na stronę 1, 2, 3  Następna strona


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Podaj ilustrację graficzną zbioru A razy B jeżeli  Monis  0
 Nieprzeliczalność zbioru - zadanie 2  Corinek  13
 moc zbioru R  carbon1  3
 Obraz i przeciwobraz zbioru - zadanie 8  kingofleon  30
 Znajdź supremum i infimum zbioru  izak110  7
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl