Problem z zadaniem - wykaż że relacja porządkuje zbiór

[piotrekvs]

Dane są dwa uporządkowane zbiory \(\displaystyle{ (X,\rho_1)}\) i \(\displaystyle{ (Y,\rho_2)}\). Wykazać że relacja \(\displaystyle{ \rho}\) określona na zbiorze \(\displaystyle{ X \times Y}\) następująco \(\displaystyle{ (x_1, y_1) \mathrel{\rho} (x_2, y_2) \Leftrightarrow x_1 \mathrel{\rho_1} x_2 \vee (x_1=x_2 \wedge y_1 \mathrel{\rho_2} y_2)}\) porządkuje ten zbiór.

Jak dowieść, że relacja jest antysymetryczna?

[Dasio11]

Tak jak zwykle: załóż, że \(\displaystyle{ (x_1, y_1) \mathrel{\rho} (x_2, y_2)}\) oraz \(\displaystyle{ (x_2, y_2) \mathrel{\rho} (x_1, y_1)}\), i dojdź do sprzeczności.

[piotrekvs]

Tak jak zwykle: załóż, że \(\displaystyle{ (x_1, y_1) \mathrel{\rho} (x_2, y_2)}\) oraz \(\displaystyle{ (x_2, y_2) \mathrel{\rho} (x_1, y_1)}\), i dojdź do sprzeczności.

dla \(\displaystyle{ x_{1} \neq x_{2}}\) dochodzę do sprzeczności, ale gdy \(\displaystyle{ x_{1} = x_{2}}\) i różnią się tylko \(\displaystyle{ y_{1} \neq y_{2}}\) to wychodzi mi prawda. Więc dalej nie rozumiem

[Jakub Gurak]

Akurat nad tym się jeszcze nie zastanawiałem, bo jeśli dobrze rozumiem jest to relacja porządku leksykograficznego zbiorów uporządkowanych \(\displaystyle{ X}\) i \(\displaystyle{ Y}\), ale może Ci pomoże słowny opis: z dwóch par o różnych pierwszych współrzędnych jest ta wcześniejsza (mniejsza) których pierwszą współrzedna jest wcześniejsza, a z dwóch par o takiej samej pierwszej współrzędnej jest ta wcześniejsza, której drugą współrzędna jest wcześniejsza. Jest to definicja silnego porządku leksykograficznego (bardziej dla dwóch zbiorów liniowo uporządkowanych).

Należy wykorzystać oczywiście, że relacja porządku na \(\displaystyle{ X}\) jest antysymetryczna, i relacja porządku na \(\displaystyle{ Y}\) jest antysymetryczna.

Może Ci napiszę dowód antysymetrii, bo rzeczywiście możesz z nim mieć problem, a przechodniość już spróbujesz sam.

Niech \(\displaystyle{ \left( x _{1},y _{1} \right) p \left(x _{2},y _{2} \right) }\) oraz \(\displaystyle{ \left( x _{2},y _{2} \right) p \left( x _{1},y _{1} \right). }\) Pokażemy, że \(\displaystyle{ \left( x _{1},y _{1} \right)=\left( x _{2},y _{2} \right). }\)

Przypuśćmy, że \(\displaystyle{ x _{1} \neq x _{2}. }\) W takim wypadku z definicji porządku leksykograficznego \(\displaystyle{ x _{1} \le _{X} x _{2} }\) i \(\displaystyle{ x_{2} \le _{X} x _{1} }\), ponieważ relacja porządku na X- \(\displaystyle{ \le _{X} }\) jest antysymetryczna, więc \(\displaystyle{ x _{1}= x _{2}}\)- sprzeczność z założeniem.

Wobec czego \(\displaystyle{ x _{1}=x _{2}, }\) wtedy z definicji porządku leksykograficznego dostajemy \(\displaystyle{ y _{1} \le _{Y} y _{2} }\) i \(\displaystyle{ y _{2} \le _{Y} y _{1} }\), ponieważ relacja \(\displaystyle{ \le _{Y}}\) porządku na \(\displaystyle{ Y}\) jest antysymetryczna, więc \(\displaystyle{ y _{1}= y _{2} . }\) Wobec czego \(\displaystyle{ \left( x _{1},y _{1} \right)= \left( x _{2},y _{2} \right). \square }\)

Przechodniość spróbuj sam.

[Dasio11]

Niech \(\displaystyle{ \left( x _{1},y _{1} \right) p \left(x _{2},y _{2} \right) }\) oraz \(\displaystyle{ \left( x _{2},y _{2} \right) p \left( x _{1},y _{1} \right). }\) Pokażemy, że \(\displaystyle{ \left( x _{1},y _{1} \right)=\left( x _{2},y _{2} \right). }\)

Przy takiej definicji antysymetryczności - a jak wiadomo, funkcjonują dwie - definicja z zadania jest mało sensowna a teza jest nieprawdziwa (w szczególności: Twój dowód jest niepoprawny). Obstawiam więc, że w zadaniu chodzi o ostre porządki i o drugą definicję relacji antysymetrycznej: \(\displaystyle{ (\forall x, y) \, \neg \big( x \mathrel{R} y \wedge y \mathrel{R} x \big)}\).

Przy powyższym założeniu dowód idzie tak: przypuśćmy nie wprost, że dla pewnych par jest \(\displaystyle{ (x_1, y_1) \mathrel{\rho} (x_2, y_2)}\) i \(\displaystyle{ (x_2, y_2) \mathrel{\rho} (x_1, y_1)}\). Dla obu tych par zachodzi więc któryś człon alternatywy z definicji relacji \(\displaystyle{ \rho}\), co łącznie daje cztery przypadki. W jednym z nich otrzymujemy, że \(\displaystyle{ x_1 \mathrel{\rho_1} x_2}\) i \(\displaystyle{ x_2 \mathrel{\rho_1} x_1}\), co daje sprzeczność z antysymetrycznością \(\displaystyle{ \rho_1}\). W drugim przypadku mamy w szczególności \(\displaystyle{ x_1 \mathrel{\rho_1} x_2}\) oraz \(\displaystyle{ x_1 = x_2}\), co jest niemożliwe z uwagi na przeciwzwrotność \(\displaystyle{ \rho_1}\). Trzeci przypadek jest analogiczny do drugiego, a w czwartym mamy \(\displaystyle{ y_1 \mathrel{\rho_2} y_2}\) i \(\displaystyle{ y_2 \mathrel{\rho_2} y_1}\) co znów jest sprzeczne, tym razem z antysymetrycznością \(\displaystyle{ \rho_2}\). W każdym przypadku otrzymaliśmy sprzeczność, co kończy dowód nie wprost.

[Jakub Gurak]

Przy takiej definicji antysymetryczności - a jak wiadomo, funkcjonują dwie - definicja z zadania jest mało sensowna a teza jest nieprawdziwa (w szczególności: Twój dowód jest niepoprawny ).

W którym miejscu

Z tego co kojarzę, to relacja porządku leksykograficznego dwóch zbiorów uporządkowanych jest relacją porządku, a zatem jest antysymetryczna, czy jestem w błędzie

[Dasio11]

W którym miejscu

W tym:

Wobec czego \(\displaystyle{ x _{1}=x _{2}, }\) wtedy z definicji porządku leksykograficznego dostajemy \(\displaystyle{ y _{1} \le _{Y} y _{2} }\) i \(\displaystyle{ y _{2} \le _{Y} y _{1} }\)

Jeśli uznać, że \(\displaystyle{ \rho_1}\) i \(\displaystyle{ \rho_2}\) są słabymi porządkami, to takie wynikanie nie zachodzi.

[Jakub Gurak]

Nie rozumiem. Skoro \(\displaystyle{ \left( x _{1}, y _{1} \right) p \left( x_2,y_2\right) }\) oraz \(\displaystyle{ x_{1}=x_2 }\), to z definicji porządku leksykograficznego druga współrzędna pierwszej pary musi być mniejsza od drugiej współrzędnej drugiej pary.

Hm ..., to dla porządku silnego, może w tym rzecz

I jeszcze pytanie: czy relacja porządku leksykograficznego (słabego jak zwykle) dwóch zbiorów uporządkowanych jest relacją porządku na iloczynie kartezjańskim

I czy, w tym zadaniu, chodzi o dokładnie ten porządek leksykograficzny czy może jest jakaś różnica??