2
$\begingroup$

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

(a, b) ≺ (c, d) iff

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

Define (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.)

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

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$).
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.