3
$\begingroup$

A partial order is a preorder with the following property:

$a\leq b \wedge b\leq a \implies a = b\quad(1)$

In my opinion, the following property it’s more intuitive:

$a\leq b \wedge b\leq c \implies a \neq c\quad(2)$

How do I prove they are equivalent?

First I start by saying $(1) \implies (2)$

$\lnot \big( (1) \land \lnot (2) \big)=\lnot(1)\lor(2) =$

$\lnot(a\leq b \land b\leq a\implies a=b)\lor(2)=$

$\lnot\Big(\lnot\big((a\leq b\land b\leq a)\land\lnot(a=b)\big)\Big)\lor(2)=$

$\big((a\le b\land b\le a)\land\lnot(a=b)\big)\lor(2)=$

$(a\le b\land b\le a \land a\ne b)\lor(2)=$

$(a\le b\land b\le a \land a\ne b)\lor\lnot\big((a\le b \land b \le c)\land\lnot(a\ne c)\big) = $

$(a\le b\land b\le a \land a\ne b)\lor\big(\lnot(a\le b \land b \le c)\lor(a\ne c)\big) = \quad ...$

I’m kind of stuck there. Is there a way to continue showing that this is a tautology?

$\endgroup$
  • 4
    $\begingroup$ They aren't equivalent. They actually negate each other. $\endgroup$ – user223391 Apr 16 '18 at 20:48
  • $\begingroup$ Well no, otherwise you would be able to evaluate it to false $\endgroup$ – gurghet Apr 16 '18 at 20:51
  • $\begingroup$ Why downvoter? why? $\endgroup$ – gurghet Apr 16 '18 at 20:55
  • $\begingroup$ @gurghet It wasn't me ... in fact I appreciate your attempt to prove equivalence! Unfortunately, it doesn't work, since your proposal leads to a problem .. see my Answer $\endgroup$ – Bram28 Apr 16 '18 at 20:58
5
$\begingroup$

Your alternative doesn't work, since a partial order is reflexive, and so if you pick $a=b=c$, then with your suggestion you get $a \not = a$, which is a contradiction.

$\endgroup$
  • $\begingroup$ Oh, that was actually faster. Thanks, but the = is not part of the partial order definition, so why did you bring reflexivity in this? I mean reflexivity states that a ≤ a, right? $\endgroup$ – gurghet Apr 16 '18 at 20:58
  • $\begingroup$ PS: I’m approaching this from a cat theory point of view so ≤ is just a symbol for a relation, it doesn't know what an = is, I suppose = is just our way to say that we are talking about the same object $\endgroup$ – gurghet Apr 16 '18 at 21:04
  • $\begingroup$ @gurghet Yes, reflexivity is $a \le a$, so if you pick the same $a$ for $a$, $b$, and $c$ you get $(a \le a \land a \le a) \rightarrow a \not = a$, and since a partial order is reflexive, we have $a \le a$ for any $a$, and thus $a \le a \land a \le a$ is true, and hence we obtain $a \not = a$ $\endgroup$ – Bram28 Apr 16 '18 at 21:07
  • $\begingroup$ Ok now I get it $\endgroup$ – gurghet Apr 16 '18 at 21:15
  • $\begingroup$ In categorical jargon, I think a partial order can be defined as a preorder (i.e., a category such that each hom-set has at most one element) that is skeletal (i.e., such that no two distinct objects are isomorphic). IMHO this jargon adds nothing to the underlying intuitive ideas behind preorders and partial orders. $\ddot{\smile}$. $\endgroup$ – Rob Arthan Apr 16 '18 at 21:22
2
$\begingroup$

Order relations come into two brands: strict and loose. Actually, they’re equivalent formulations, when the identity relation is available.

Let’s talk about relations on the set $A$. A relation $R$ on $A$ is areflexive if $(a,a)\notin R$, for all $a\in A$.

A strict preorder is just a transitive relation. A strict order is an areflexive and transitive relation.

A loose preorder is a reflexive and transitive relation. A loose order is a reflexive, antisymmetric (the property you seem not to like) and transitive relation.

Note that the identity relation is needed for stating the antisymmetric property.

How can one pass from strict to loose (pre)orders? Of course we need to have the identity relation available.

Suppose $S$ is a strict (pre)order on $A$ and define $$ S^+=S\cup\{(a,a):a\in A\} $$ It’s easy to show that $S^+$ is transitive as well. It is also reflexive by construction. Hence $S^+$ is a loose preorder when $S$ is a strict preorder. Suppose $S$ is a strict order and also that $(a,b)\in S^+$ and $(b,a)\in S^+$. We cannot have $a\ne b$, because otherwise $(a,b)\in S$ and $(b,a)\in S$ and, by transitivity, $(a,a)\in S$: a contradiction to $S$ being areflexive. Therefore $a=b$ and so $S^+$ is antisymmetric.

Thus, from any strict order $S$ we obtain a loose one. Conversely, if $L$ is a loose order on $A$, it can be easily proved that $$ L^-=L\setminus\{(a,a):a\in A\} $$ is a strict order on $A$. Moreover, it is obvious that

  • if $S$ is a strict order, then $S=(S^+)^-$;
  • if $L$ is a loose order, then $L=(L^-)^+$.

Hence there’s no real difference between strict and loose orders on $A$: they correspond bijectively.

In order that a strict preorder $S$ is a strict order, it is necessary and sufficient that

for all $a,b,c\in A$, if $(a,b)\in S$ and $(b,c)\in S$, then $a\ne c$.

Indeed, suppose $S$ is a strict order. Then $(a,b)\in S$ and $(b,a)\in S$ implies $(a,a)\in S$, by transitivity: a contradiction to $S$ being areflexive.

Conversely, suppose $S$ is a strict preorder that satisfies the above property and $(a,a)\in S$ (that is, $S$ is not areflexive). Then, with $b=c=a$, we have $(a,b)\in S$, $(b,c)\in S$ and $a=c$: a contradiction.

So your “more intuitive” property indeed characterizes strict preorders that are strict orders. But is it really more intuitive? This is a matter of preference. Strict (pre)orders can be defined with no appeal to the identity relation, but your property makes use of it (of its negation, but it’s the same).

For a loose preorder the property you like is definitely not equivalent to it being a loose order. Indeed, no loose order satisfies it for the simple reason it is reflexive.

$\endgroup$
  • $\begingroup$ That's a very good point. Thanks. Didn't know areflexivity was a thing. Do you know any application of such an order by the way? $\endgroup$ – gurghet Apr 16 '18 at 23:14
  • 1
    $\begingroup$ @gurghet Since strict and loose orders are essentially the same thing, there's no application of the former type that cannot be formulated with the latter. $\endgroup$ – egreg Apr 16 '18 at 23:37
  • $\begingroup$ @egreg "Irreflexive" is a more common word than "areflexive" $\endgroup$ – Derek Elkins Apr 17 '18 at 1:42

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.