Słowa należące do zbioru

[Lukassz]

Witajcie, mam problem ze wskazaniem przykładów do tego zadania.

Niech \(\displaystyle{ X = \left\{ a,b,c\right\}}\) i niech \(\displaystyle{ Y}\) oznacza zbiór wszystkich niepustych słów nad alfabetem \(\displaystyle{ X}\) niech \(\displaystyle{ \le Y \times Y}\) będzie relacją określoną tak:
dla dowolnych słów \(\displaystyle{ w,v \in Y}\)
\(\displaystyle{ w \preceq v}\) wtw. \(\displaystyle{ \left( w=v\right) \vee \exists z \in Y \left( v=zw\right)}\)
Wskaż cztery słowa \(\displaystyle{ w_1,w_2,w_3,w_4 \in Y}\) takie że \(\displaystyle{ w_1 \le w_2 \le w_3 \le w_4}\)

[Jan Kraszewski]

Zacznij od zrozumienia definicji.

JK

[Lukassz]

Przypomniałem sobie definicje zbioru częściowo uporządkowanego.
\(\displaystyle{ \le Y \times Y}\) mam rozumieć jako zbór elementów dwuelementowych (znak iloczynu kartezjańskiego?

[aidwhoe]

Przyjrzyj się tej relacji i spróbuj zrozumieć, co mówią jej poszczególne człony.

Zapis \(\displaystyle{ \le Y \times Y}\) mówi tyle, że relacja jest opisana na elementach \(\displaystyle{ Y}\), czyli wyrazach.

[Jan Kraszewski]

\(\displaystyle{ \le Y \times}\) mam rozumieć jako zbór elementów dwuelementowych (znak iloczynu kartezjańskiego?

Tego, co napisałeś, akurat nie da się zrozumieć, zarówno na poziomie symbolicznym, jak i opisowym.

To, co napisałeś w pierwszym poście, też było niepoprawne (chodzi o symbole). Powinno być:

"niech \(\displaystyle{ \le \red\subseteq\black Y \times Y}\) będzie relacją określoną tak"

i wtedy zapis \(\displaystyle{ \le \subseteq Y \times Y}\) oznacza dokładnie tyle, że \(\displaystyle{ \le}\) jest relacją na zbiorze \(\displaystyle{ Y}\).

JK

[Lukassz]

No tak, ale sam element \(\displaystyle{ a}\) nie jest wynikiem pochodzącym z \(\displaystyle{ \le \subseteq Y \times Y}\) tak?

[aidwhoe]

Nie, a nie jest wynikiem \(\displaystyle{ \le \subseteq Y \times Y}\). Ten zapis gwarantuje Ci podstawowe informacje o relacji, jako że relacja jest działaniem binarnym i potrzebuje 2 elementów, które możesz porównać. Tutaj dowiadujesz się, że porównujesz elementy z \(\displaystyle{ Y}\) z elementami z \(\displaystyle{ Y}\).

[Lukassz]

Czyli minimalne i maksymalne słowo będzie miało 2 elementy zawsze tak?

[aidwhoe]

Nie, Twoje słowa \(\displaystyle{ a \in P(X) \setminus \left\{ \emptyset\right\}}\) (zgodnie z tym, co napisałeś). Spostrzeżenie, które napisałem wcześniej mówi tylko tyle, że musisz wziąć 2 elementy, aby móc je porównać względem jakiejś relacji.

Zatem w tej konkretnej relacji jesteś proszony o porównanie 2 elementów \(\displaystyle{ Y}\). O elementach tej relacji masz powiedziane tylko tyle, że muszą być niepuste. Czy to oznacza, że dowolny wyraz \(\displaystyle{ a \in P(X) \setminus \left\{ \emptyset\right\}}\) jest dwuelementowy?

[Jan Kraszewski]

Twoje słowa \(\displaystyle{ \red a \in P(X) \setminus \left\{ \emptyset\right\}}\) (zgodnie z tym, co napisałeś).

Hmmm...?

Po pierwsze, \(\displaystyle{ a}\) jest po prostu elementem \(\displaystyle{ X}\), a nie niepustym podzbiorem tego zbioru. Po drugie, relacja jest na zbiorze niepustych słów \(\displaystyle{ Y=X^*\setminus\{\epsilon\}}\), który jest zdecydowanie różny od zbioru niepustych podzbiorów.

JK