Binary Relations and Total Orders

268 Views Asked by At

This question has two parts: 1) i) Given a relation $<$, define a relation $\leq$ by setting x $\leq$y if and only if x$<$y or x = y. Prove that if < satisfies transitivity and 'trichotomy' then $\leq$ is a total ordering.

ii) Given a relation $\leq$, define a relation < by setting x$<$y if and only if x$\leq$y and x$\neq$y. Prove that if $\leq$ is a total ordering then < satisfies transitivity and 'trichotomy'.

What I've gathered: So I know from class that the trichotomy is that either x$<$y, y$<$x or x$=$y For a relation to be total ordered, it must be antisymmetric, transitive and total (a$\leq$b or b$\leq$a)

My thoughts on the question: i) So we are given the relation <, now this is the part where I get stuck, do I proceed with the question assuming that < is defined for transitivity and the trichotomy? So then since < is defined, then say for a, b and c, then since < satisfies trichotomy and transitivity, then that implies that if $a<b$ and $b<c$, then $a<c$ (transitive) and $a<b$ or $a>b$ or $a=b$ (trichotomy), but I don't know how to apply that knowledge to show that '$\leq$' is a total order.

1

There are 1 best solutions below

0
On

Firstly, yes you assume that $<$ is transitive and satisifies the "trichotemy" property.

Then you have to show that $\leq$ satisfies three properties (completely nicked from Wikipedia):

  1. Antisymmetry - $a\leq b$ and $b \leq a$ implies $a=b$,
  2. Transitivity, and
  3. Totality - for every $a$ and $b$ either $a \leq b$ or $b \leq a$.

It shouldn't be too hard to show that these are true in all cases (they're almost trivial, but not quite).

As this looks like a homework question, I won't go further short of more inquiries.