Sprawdzić własności relacji porządek leksykograficzny

[max123321]

Sprawdzić własności relacji porządek leksykograficzny kartezjański w \(\displaystyle{ (\NN,\NN) \times
(\NN,\NN):: {(x_1; y_1)r(x_2; y_2)}}\) wtedy i tylko wtedy, gdy \(\displaystyle{ (x_1 < x_2) ∨ [(x_1 = x_2) ∧ (y_1 \le y_2)]}\).

Proszę o sprawdzenie:
Relacja jest zwrotna bo \(\displaystyle{ x<x \vee x=x \wedge y \le y}\).
Relacja jest antysymetryczna bo jeśli \(\displaystyle{ (x_1,y_1)r(x_2,y_2)}\) to \(\displaystyle{ x_1<x_2 \vee x_1=x_2 \wedge y_1 \le y_2}\). Jeśli \(\displaystyle{ x_1<x_2}\) to nie może być ani \(\displaystyle{ x_2<x_1}\) ani \(\displaystyle{ x_2=x_1}\). Jeśli natomiast \(\displaystyle{ x_1=x_2 \wedge y_1 \le y_2 \wedge x_2=x_1 \wedge y_2 \le y_1}\) to \(\displaystyle{ x_1=x_2 \wedge y_1=y_2}\), a zatem jeśli \(\displaystyle{ (a,b)r(c,d)}\) i \(\displaystyle{ (c,d)r(a,b)}\) to \(\displaystyle{ a=b=c=d}\).
Relacja jest przechodnia bo jeśli \(\displaystyle{ x_1<x_2 \vee x_1=x_2 \wedge y_1 \le y_2}\) i \(\displaystyle{ x_2<x_3 \vee x_2=x_3 \wedge y_2 \le y_3}\) to \(\displaystyle{ x_1<x_3}\) lub \(\displaystyle{ x_1=x_3}\), ale to wtedy \(\displaystyle{ y_1 \le y_3}\).

Zatem jest to relacja częściowego porządku,

[Jan Kraszewski]

Sprawdzić własności relacji porządek leksykograficzny kartezjański w \(\displaystyle{ \red{(\NN,\NN) \times
(\NN,\NN)}}\).

A cóż to takiego?! Pierwsze widzę...

Relacja jest zwrotna bo \(\displaystyle{ x<x \vee x=x \wedge y \le y}\).

Jak poprawisz niepoprawny zapis, to będzie dobrze.

Relacja jest antysymetryczna bo jeśli \(\displaystyle{ (x_1,y_1)r(x_2,y_2)}\) to \(\displaystyle{ x_1<x_2 \vee x_1=x_2 \wedge y_1 \le y_2}\). Jeśli \(\displaystyle{ x_1<x_2}\) to nie może być ani \(\displaystyle{ x_2<x_1}\) ani \(\displaystyle{ x_2=x_1}\). Jeśli natomiast \(\displaystyle{ x_1=x_2 \wedge y_1 \le y_2 \wedge x_2=x_1 \wedge y_2 \le y_1}\) to \(\displaystyle{ x_1=x_2 \wedge y_1=y_2}\), a zatem jeśli \(\displaystyle{ (a,b)r(c,d)}\) i \(\displaystyle{ (c,d)r(a,b)}\) to \(\displaystyle{ a=b=c=d}\).

I znów niepoprawnie oszczędzasz na nawiasach.

Relacja jest przechodnia bo jeśli \(\displaystyle{ x_1<x_2 \vee x_1=x_2 \wedge y_1 \le y_2}\) i \(\displaystyle{ x_2<x_3 \vee x_2=x_3 \wedge y_2 \le y_3}\) to \(\displaystyle{ x_1<x_3}\) lub \(\displaystyle{ x_1=x_3}\), ale to wtedy \(\displaystyle{ y_1 \le y_3}\).

I znów to samo. Poza tym pytanie brzmi, jak formalny ma być to dowód.

JK

[max123321]

A jak to zapisać poprawnie, w sensie to \(\displaystyle{ \red{(\NN,\NN) \times (\NN,\NN)}}\). Bo intuicyjnie to jest jasne, elementami są pary liczb naturalnych i dwie pary są ze sobą w relacji jeśli spełniony jest ten warunek. Choć faktycznie wygląda to trochę dziwnie. Może jakoś tak, mamy iloczyn kartezjański \(\displaystyle{ K=\NN^2 \times \NN^2}\) i ta relacja jest podzbiorem tego zbioru spełniającym ten warunek. Może tak być?

[max123321]

Ok poprawka:

Relacja jest zwrotna bo \(\displaystyle{ (x<x) \vee ((x=x) \wedge (y \le y))}\).
Relacja jest antysymetryczna bo jeśli \(\displaystyle{ (x_1,y_1)r(x_2,y_2)}\) to \(\displaystyle{ (x_1<x_2) \vee ((x_1=x_2) \wedge (y_1 \le y_2))}\). Jeśli \(\displaystyle{ x_1<x_2}\) to nie może być ani \(\displaystyle{ x_2<x_1}\) ani \(\displaystyle{ x_2=x_1}\). Jeśli natomiast \(\displaystyle{ (x_1=x_2) \wedge (y_1 \le y_2) \wedge (x_2=x_1) \wedge (y_2 \le y_1)}\) to \(\displaystyle{ (x_1=x_2) \wedge (y_1=y_2)}\), a zatem jeśli \(\displaystyle{ (a,b)r(c,d)}\) i \(\displaystyle{ (c,d)r(a,b)}\) to \(\displaystyle{ a=b=c=d}\).
Relacja jest przechodnia bo jeśli \(\displaystyle{ (x_1<x_2) \vee ((x_1=x_2) \wedge (y_1 \le y_2))}\) i \(\displaystyle{ (x_2<x_3) \vee ((x_2=x_3) \wedge (y_2 \le y_3))}\) to \(\displaystyle{ x_1<x_3}\) lub \(\displaystyle{ x_1=x_3}\), ale to wtedy \(\displaystyle{ y_1 \le y_3}\).

Dobrze?