Zbadać, czy jest to relacja częściowego i liniowego porządku

[mariusz689]

Niech \(\displaystyle{ R \subset A \times A}\) będzie relacją określoną warunkiem:
\(\displaystyle{ xRy \Leftrightarrow (x ^{2} +1)|(y ^{2} +1)}\)
gdzie A={1,4,5,6,7,8}.
Zbadać, czy jest to relacja częściowego i liniowego porządku. Jeśli jest relacją częściowego porządku wyznacz jej elementy wyróżnione oraz dwa dowolne łańcuchy.

[Rafix_]

Mam do rozwiązania podobne zadanie... mógłby ktoś sprawdzić, czy dobrze robię:

1. zwrotność
\(\displaystyle{ \bigwedge\limits_{x \in A} xRx \Leftrightarrow (x ^{2} +1)|(x ^{2} +1) \\}\) co jest oczywiście prawdą

2. antysymetria
\(\displaystyle{ \bigwedge\limits_{x,y \in A} xRy \wedge yRx \Leftrightarrow (x ^{2} +1)|(y ^{2} +1) \wedge (y ^{2} +1)|(x ^{2} +1) \Leftrightarrow \\
(y^{2}+1)=k(x^{2}+1) \ \wedge \ (x^{2}+1)=l(y^{2}+1) \ \wedge \ k,l \in \mathbb{Z} \Leftrightarrow \\
(y^{2}+1)=kl(y^{2}+1) \ \wedge \ k,l \in \mathbb{Z} \Rightarrow \ x=y}\)
relacja jest antysymetryczna

3. przechodniość
\(\displaystyle{ \bigwedge\limits_{x,y,z \in A} xRy \wedge yRz \Leftrightarrow \
(x ^{2} +1)|(y ^{2} +1) \ \wedge \ (y ^{2} +1)|(z ^{2} +1) \Leftrightarrow \\
(y^{2}+1)=k(x^{2}+1) \ \wedge \ (z^{2}+1)=m(y^{2}+1) \ \wedge \ k,m \in \mathbb{Z} \Leftrightarrow \\
(z^2+1)=mk(x^2+1) \Rightarrow (x ^{2} +1)|(z ^{2} +1) \Leftrightarrow xRz}\)
relacja jest przechodnia

zatem relacja jest częściowo porządkująca

4. spójność
\(\displaystyle{ \bigwedge\limits_{x,y \in A} xRy \vee yRx \Leftrightarrow \\
(x ^{2} +1)|(y ^{2} +1) \vee (y ^{2} +1)|(x ^{2} +1) \\}\)
wykażemy, że relacja nie jest spójna przez podanie kontrprzykładu np.
\(\displaystyle{ x= 4, y=5}\) tj. \(\displaystyle{ x^2+1=17, y^2+1 = 26}\)
\(\displaystyle{ 26\nmid 17 \wedge 26 \nmid 17}\)
relacja nie jest zatem relacją liniowego porząku.

Jak wyznaczyć teraz łańcuchy i elementy wyróżnione??

[Jan Kraszewski]

W zasadzie dobrze.
Uwagi:

1. Formalnie zapis

\(\displaystyle{ \bigwedge\limits_{x \in A} xRx \Leftrightarrow (x ^{2} +1)|(x ^{2} +1)}\)

jest niepoprawny (z jednej strony masz kwantyfikator, a z drugiej nie). Lepiej byłoby napisać

"zwrotność
Dla dowolnego \(\displaystyle{ x\in A}\) mamy
\(\displaystyle{ xRx \Leftrightarrow (x ^{2} +1)|(x ^{2} +1)}\), co jest..."

2. Ostatnie wynikanie przy antysymetrii wymagałoby słowa komentarza.

3. By wyznaczyć łańcuchy i elementy wyróżnione narysuj diagram Hassego tego porządku.

JK

[Rafix_]

Dziękuje za uwagi dot. zapisu, niestety nie mogę już edytować.

Natomiast z diagramem Hassego trochę się pogubiłem. Mianowicie pewne twierdzenie mówi nam, że każda zbiór z relacją częściowo uporządkowaną ma diagram Hassego. wyżej wykazaliśmy, że nasza relacja jest relacją częściowego porządku.
Natomiast, gdy zabrałem się do rysowania to np {4} nie można połączyć z żadnym innym elementem, podobnie dla {6} i {8}. Czy wierzchołki te mogą zostać niepołączone ? Ale czy wtedy będzie to diagram?

pozdrawiam

[Jan Kraszewski]

Oczywiście, że mogą. Diagram Hassego może nawet nie mieć żadnych połączeń... (w skrajnym przypadku relacji równości, która też jest częściowym porządkiem).

JK

[Rafix_]

ok.

w takim razie przykładowymi łańcuchami są: {1,5} lub {1,7}, tak?
co będzie el. wyróżnionym?

[Jan Kraszewski]

w takim razie przykładowymi łańcuchami są: {1,5} lub {1,7}, tak?

Tak.

co będzie el. wyróżnionym?

Popatrz na diagram i zastanów się, które elementy są minimalne (nie mają nic pod sobą), a które maksymalne (nie mają nic nad sobą). Pamiętaj, że ten sam element może być równocześnie minimalny i maksymalny. Ponieważ i jednych i drugich będzie więcej niż jeden, więc nie będzie ani największych, ani najmniejszych.

JK