1

So I've been redoing some relations problems and came across this one:

Prove that the relation defined over $\mathbb{R}^2$ is a total order relation $$ (x_1, y_1) \rho (x_2, y_2) \iff x_1 < x_2 \lor (x_1 = x_2 \land y_1 \le y_2) $$

Assuming the relation is indeed reflexive, antisymmetric and transitive ( these don't seem too difficult to prove, and the task focuses more on the type of relations ), it doesn't take too long to find an example that counters the totality i.e. $(2,0)$ and$(1,0)$.

Did I misunderstood the concept of a total order relation, i.e. having already proven the reflexivity, antisymmetry and transitivity, we are left to prove the totality i.e. $$ (\forall\ x,y\in \mathbb{R}^2)\ x\rho y\ \lor\ y\rho x $$

which of course is not true for the given sample values. In fact, it doesn't make sense for this relation to be total order since it never allows $x_2 > x_1$, or at least i think so.

Gerry Myerson
  • 179,216
Transcendental
  • 2,204
  • $(1,0)\rho(2,0)$ so that is not a totality counter example. – fleablood Oct 25 '16 at 08:01
  • 1
    Just flip the order. I.e, aRb is false as you pointed out, but is bRa false too? This is just lexicographical ordering or dictionary ordering. So, if you face bc and ac, do you say you can't arrange them in a dictionary? – IamThat Oct 25 '16 at 08:03

3 Answers3

2

I think you are misunderstanding totality.

For all $(a,b)$ and $(c,d)$ either $(a,b)\rho(c,d)$ or $(c,d)\rho(a,b)$ or $(a,b) = (c,d)$ all mutually exclusive.

So you if you can prove

1) $(a,b)\not \rho (a,b)$ for any $(a,b)$.

2) If $(a,b) \ne (c,d)$ either $(a,b) \rho (c,d)$ or $(c,d) \rho (a,b)$ but never both.

you will have proven it is a total order.

=====

Actually, I screwed up the definition of total order too. I was thinking of "<" vs "$\le$". I always get them confused.

we want

1)$(a,b) \rho (a,b)$

2)$(c,d) \rho (a,b)$ or $(a,b)\rho(c,d)$ for any two $(a,b), (c,d)$ but if $(a,b)\rho(c,d)$ AND $(c,d)\rho(a,b)$ then $(a,b) = (c,d)$.

fleablood
  • 124,253
  • Yeah, I can't believe i just did this. I explicitly wrote $x \rho y\ \lor \ y \rho x$ but treated it as conjunction. Thank you. I think i need some coffe. – Transcendental Oct 25 '16 at 08:06
1

$(1,0)\lt (2,0)$ since $1\lt 2.$

Mitchell Spector
  • 9,917
  • 3
  • 16
  • 34
1

Your totality requirement is that $(\forall x,y\in \mathbb{R}^2)(x\rho y\ \lor\ y\rho x)$ be true.

A counter example would be a witness that $(\exists x,y\in\Bbb R^2)(\neg x\rho y\ \wedge\ \neg y\rho x)$.

That is both would have to be false for at least one pair.

However, if not $((x_1\lt x_2)\vee(x_1= x_2~\wedge~ y_1\leq y_2))$, then $(x_1\geq x_2)\wedge(x_1\gtrless x_2~\vee~y_1\gt y_2)$ which means $((x_2<x_1)\vee(x_2=x_1\wedge y_1\leq y_2))$

(...Can you show how?)

Thus if ever $\neg x\rho y$ then $y\rho x$, so no counter example can exist.

Graham Kemp
  • 129,094