0
$\begingroup$

Let $(X, \preceq)$ be a total ordered set, show that

$$ x \prec y \leftrightarrow x \preceq y \land x \neq y$$ is a transitive relation, such that for each $x$, $y$ $\in X$ exactly one case holds: 1) $x \prec y$ 2) $x=y$ 3) $y \prec x$

I am really unsure here, doesn't the transitivity and trichotomy follow from X being total ordered? Is this https://proofwiki.org/wiki/Trichotomy_Law_(Ordering) the proof needed here?

$\endgroup$

2 Answers 2

3
$\begingroup$

They do follow from the fact that $\preceq$ is a total ordering, but there’s a bit of work to be done in order to show that they do.

You’re being asked to show two things. The first is that $\prec$ is transitive, i.e., that if $x,y,z\in X$ and $x\prec y\prec z$, then $x\prec z$. That $x\preceq z$ is immediate from the transitivity of $\preceq$, but you still have to show that $x\ne z$, which isn’t quite trivial.

The second is that for each $x,y\in X$, exactly one of $x\prec y$, $x=y$, and $y\prec x$ holds. You know that either $x\preceq y$ or $y\preceq x$. If $x\preceq y$, then either $x\ne y$, in which case $x\prec y$ by definition, and it’s easy to verify that $y\not\prec x$, or $x=y$, in which case by definition $x\not\prec y$ and $y\not\prec x$. Finishing it off is just more of the same sort of reasoning.

$\endgroup$
6
  • $\begingroup$ Hello Brian, thank you so much for your great helping comments each and everytime, the second part is clear but could you tell me for the first part, how I can exactly show $ x \neq y$? $\endgroup$
    – Parinn
    May 26, 2020 at 8:59
  • 1
    $\begingroup$ @Parinn: You mean that $x\ne z$? Suppose that $x=z$. Then $z\prec y$ and $y\prec z$; is that possible? $\endgroup$ May 26, 2020 at 16:06
  • $\begingroup$ Thank you, so by taking the assumption that $x = y$, and then showing that a contradiction occurs, I would be finished? Or is there something additional to do for proving the first part? $\endgroup$
    – Parinn
    May 28, 2020 at 4:15
  • 1
    $\begingroup$ @Parinn: If you assume that $x=z$ and arrive at a contradiction, then you know that $x\ne z$. Since at that point you already know that $x\preceq z$, that immediately tells you that $x\prec z$, which is what you had to prove in order to show that $\prec$ is transitive. $\endgroup$ May 28, 2020 at 4:18
  • $\begingroup$ Thank you for your help $\endgroup$
    – Parinn
    May 28, 2020 at 9:33
2
$\begingroup$

Show $\forall x,y$($x\preceq y\lor y\prec x)$ : Suppose not, i.e. $\exists x,y(x\npreceq y\land y\nprec x)$. From $y\nprec x$, $y\npreceq x\lor y=x$ (definition). If $y=x$ holds, then $x\preceq y$, which contradicts the assumption $x\npreceq y$. Therefore $y\npreceq x$ holds, however, again this contradicts that $(X,\preceq)$ is total ordered set. Therefore $\forall x,y$($x\preceq y\lor y\prec x)$ holds, which states at least one of 1),2) and 3) holds.

Now show only one of 1),2) and 3) holds for given $x,y\in X$ : Suppose not. If 1) and 2) holds in same time, then $x\preceq y\land x\neq y\land x=y$, which clearly a contradiction. The case for 2) and 3) can be seen similarly. If 1) and 3) holds in same time, then $x\preceq y\land y\preceq x\land x\neq y\Rightarrow x=y\land x\neq y$, a contradiction. Therefore for given $x,y\in X$, only one of 1),2), and 3) holds.

$\endgroup$
1
  • $\begingroup$ Thank you so much for your answer, the second paragraph is perfectly clear. In the first one I have struggles to understand your argumentation, you first negate the sentence $\neg ( x \preceq y \land x \neq y) $ in the definition ? But then I could not understand your argument chain, if possible could you please further explain? $\endgroup$
    – Parinn
    May 26, 2020 at 9:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .