# Prove the relation to be a Linear Order.

Let (a, b),(x, y) ∈ R × R and deﬁne ≺ as follows:

(a, b) ≺ (c, d) iﬀ

a < c or a = c and b < d:

Deﬁne (a, b) ≼ (c, d) if and only if (a, b) = (c, d) or (a, b) ≺ (c, d).

Show that ≼ is a linear order on R × R.

I know that I must prove the relation is reflexive, transitive, and anti-symmetric, and a linear order.

1.) Let m=(a,b)

mRm

(a,b)=(a,b)

Therefore (a,b)=(c,d) is reflexive.

We do not have to show for (a,b) ≼ (c,d) because the definition includes equality.

2.) I know there are 4 cases to show for transitivity, but I am struggling with how to prove them.

I need to show A=B, B=C

A≺B, B=C

A≺B, B≺C

A=B, B≺C

a) if (a,b)=(c,d) and (c,d)=(e,f), then (a,b)=(e,f).

b) if (a,b)≺(c,d) and (c,d)=(e,f), then ?

c) if (a,b)≺(c,d) and (c,d)≺(e,f), then ?

d) if (a,b)=(c,d) and (c,d)≺(e,f), then ?

3.) If (a,b)≼ (c,d) and (c,d)≼(a,b), then (a,b)=(c,d).

They must be equal because the relation ≺ will be false.

4.)I know that I must show (x,y)≼(a,b) or (a,b)≼(x,y)

For every pair of elements, must show they are comparable.

(Somewhat unsure how to begin--guidance would be great.)

• TL:DR. Google for lexicographic order. – Git Gud Oct 23 '13 at 21:28
• For transitivity show that $<$ is transitive. Then $\le$ is automatically transitive. – Hagen von Eitzen Oct 23 '13 at 21:42

General hint: you don't need to separate it into these parts: we have $(a,b)\le (c,d)$ iff $a<c$ or ($a=c$ and $b\le d$).
1. If $m=(a,b)$ then $m\le m$ by definition, as you say.
2. b) If $(a,b)<(c,d)$ and $(c,d)=(e,f)$ then obviously $(a,b)<(e,f)$.
c) If $(a,b)<(c,d)$ and $(c,d)<(e,f)$ then either $a<c$ or ($a=c$ and $b<d$). In the first case we have $a<c\le e$, so that $(a,b)<(e,f)$ because of $a<e$. In the second case...
d) If $(a,b)=(c,d)$ and $(c,d)<(e,f)$ then obviously $(a,b)<(e,f)$.
3. Suppose $(a,b)\le (c,d)$ and $(c,d)\le (a,b)$. Then $a<c$ cannot hold, so $a=c$. Conclude similarly that $b=d$.
4. Given arbitrary pairs $(a,b)$ and $(x,y)$. Either $a<x$, $a>x$ or $a=x$ holds. In the first two cases, we are done, and if $a=x$, we have ($b\le y$ or $y\le b$).