Przekrój

[kt26420]

Zbiór słów \(\displaystyle{ A \subseteq \left \{a, b \right\}^* }\) nazwiemy przekrojem, gdy:
(*) dla dowolnych różnych słów \(\displaystyle{ u, v \in A }\), słowo \(\displaystyle{ u}\) nie jest prefiksem \(\displaystyle{ v}\) ani \(\displaystyle{ v}\) nie jest prefiksem \(\displaystyle{ u}\);
(**) dla dowolnego słowa \(\displaystyle{ w \in \left\{ a,b\right\} ^*}\) istnieje takie słowo \(\displaystyle{ u \in A}\), że \(\displaystyle{ u}\) jest prefiksem \(\displaystyle{ w}\) lub \(\displaystyle{ w}\) jest prefiksem \(\displaystyle{ u}\).

Nie mogę zrozumieć, czy w takim przypadku przekrojem będzie tylko takie \(\displaystyle{ A = \{a,b\}}\)? bo jak weźmiemy jakieś większe słowo np. \(\displaystyle{ ab}\) to \(\displaystyle{ a}\) jest prefiksem \(\displaystyle{ ab}\)...
Więc \(\displaystyle{ A = \{a,b,ab\}}\) nie jest przekrojem, czy źle rozumiem?

[Jan Kraszewski]

czy w takim przypadku przekrojem będzie tylko takie \(\displaystyle{ A = \{a,b\}}\)

Nie tylko. Np. zbiór \(\displaystyle{ \{a, ba, bb\}}\) też jest przekrojem.

Więc \(\displaystyle{ A = \{a,b,ab\}}\) nie jest przekrojem,

Zgadza się, nie jest.

JK

[kt26420]

Dodano po 29 sekundach:

czy w takim przypadku przekrojem będzie tylko takie \(\displaystyle{ A = \{a,b\}}\)

Nie tylko. Np. zbiór \(\displaystyle{ \{a, ba, bb\}}\) też jest przekrojem.

Więc \(\displaystyle{ A = \{a,b,ab\}}\) nie jest przekrojem,

Zgadza się, nie jest.

JK

Bo mam takie zadanie:
Czy jeśli \(\displaystyle{ A}\) jest przekrojem, to każdy maksymalny łańcuch w \(\displaystyle{ \left\{ a,b \right\}^
* }\) z porządkiem prefiksowym ma niepuste przecięcie z \(\displaystyle{ A}\)?

Czy mogłabym poprosić Pana o jakieś wskazówce jak za to zabrać się?

[Jan Kraszewski]

Czy jeśli \(\displaystyle{ A}\) jest przekrojem, to każdy maksymalny łańcuch w \(\displaystyle{ \left\{ a,b \right\}^* }\) z porządkiem prefiksowym ma niepuste przecięcie z \(\displaystyle{ A}\)?

Czy mogłabym poprosić Pana o jakieś wskazówce jak za to zabrać się?

O \(\displaystyle{ \left\{ a,b \right\}^* }\) z porządkiem prefiksowym możesz myśleć jak o drzewie binarnym. Wtedy maksymalny łańcuch odpowiada (nieskończonej) gałęzi w tym drzewie, natomiast przekroje to w pewnym sensie poziomy w tym drzewie (dokładniej, każdy poziom jest przekrojem, ale nie każdy przekrój jest poziomem). Ściśle - przekroje to maksymalne antyłańcuchy w tym porządku. Zatem przekroje rozciągają się od lewego do prawego końca drzewa, a maksymalne łańcuchy ciągną się od samego dołu do samej góry tego drzewa. Wobec tego muszą się przeciąć.

Dowód jest natychmiastowy. Ustal przekrój \(\displaystyle{ A}\) i maksymalny łańcuch \(\displaystyle{ L}\). Ustal dowolny element \(\displaystyle{ l\in L}\). Ponieważ \(\displaystyle{ A}\) jest przekrojem, więc z (**) istnieje \(\displaystyle{ v\in A}\), które jest porównywalne z \(\displaystyle{ l}\). Ale skoro \(\displaystyle{ v}\) i \(\displaystyle{ l}\) są porównywalne, to z maksymalności łańcucha \(\displaystyle{ L}\) wynika (dlaczego? - musisz uzasadnić, że \(\displaystyle{ v}\) jest porównywalne ze wszystkimi elementami \(\displaystyle{ L}\)), że \(\displaystyle{ v\in L}\), czyli \(\displaystyle{ v\in A\cap L}\), co kończy dowód.

JK

[kt26420]

Czy jeśli \(\displaystyle{ A}\) jest przekrojem, to każdy maksymalny łańcuch w \(\displaystyle{ \left\{ a,b \right\}^* }\) z porządkiem prefiksowym ma niepuste przecięcie z \(\displaystyle{ A}\)?

Czy mogłabym poprosić Pana o jakieś wskazówce jak za to zabrać się?

O \(\displaystyle{ \left\{ a,b \right\}^* }\) z porządkiem prefiksowym możesz myśleć jak o drzewie binarnym. Wtedy maksymalny łańcuch odpowiada (nieskończonej) gałęzi w tym drzewie, natomiast przekroje to w pewnym sensie poziomy w tym drzewie (dokładniej, każdy poziom jest przekrojem, ale nie każdy przekrój jest poziomem). Ściśle - przekroje to maksymalne antyłańcuchy w tym porządku. Zatem przekroje rozciągają się od lewego do prawego końca drzewa, a maksymalne łańcuchy ciągną się od samego dołu do samej góry tego drzewa. Wobec tego muszą się przeciąć.

Dowód jest natychmiastowy. Ustal przekrój \(\displaystyle{ A}\) i maksymalny łańcuch \(\displaystyle{ L}\). Ustal dowolny element \(\displaystyle{ l\in L}\). Ponieważ \(\displaystyle{ A}\) jest przekrojem, więc z (**) istnieje \(\displaystyle{ v\in A}\), które jest porównywalne z \(\displaystyle{ l}\). Ale skoro \(\displaystyle{ v}\) i \(\displaystyle{ l}\) są porównywalne, to z maksymalności łańcucha \(\displaystyle{ L}\) wynika (dlaczego? - musisz uzasadnić, że \(\displaystyle{ v}\) jest porównywalne ze wszystkimi elementami \(\displaystyle{ L}\)), że \(\displaystyle{ v\in L}\), czyli \(\displaystyle{ v\in A\cap L}\), co kończy dowód.

JK

Dziękuję bardzo za pomoc!

[Dasio11]

Czy jeśli \(\displaystyle{ A}\) jest przekrojem, to każdy maksymalny łańcuch w \(\displaystyle{ \left\{ a,b \right\}^* }\) z porządkiem prefiksowym ma niepuste przecięcie z \(\displaystyle{ A}\)?

Otóż nie musi mieć! - mam świadka:

\(\displaystyle{ A = \{ a^nb : n \in \NN \}, L = \{ a^n : n \in \NN \}}\)

[Jan Kraszewski]

Masz rację, zbyt optymistycznie byłem nastawiony do tego fragmentu dowodu:

musisz uzasadnić, że \(\displaystyle{ v}\) jest porównywalne ze wszystkimi elementami \(\displaystyle{ L}\)

Swoją drogą to podstępny przykład - przekrój z jednej strony wygina się do góry, a łańcuch wciska się w powstałą szczelinę...

JK