A binary relation $R$ over $D$ is semitransitive if the following condition holds for all $a, b, c, d\in D$:

(1) If $aRb$ and $bRc$, then $aRd$ or $dRc$.

A binary relation $R$ over $D$ is Ferrers if the following condition holds for all $a, b, c, d\in D$:

(2) If $aRb$, $cRd$, and not $cRb$, then $aRd$.

A semiorder $R$ is reflexive, semitransitive, and Ferrers. As usual, the strict part $P$ of $R$ is defined as $aPb$ iff. $aRb$ and not $bRa$, and the nonstrict part $I$ is defined as $aIb$ iff. $aRb$ and $bRa$. An interesting property of a semiorder is that while $P$ is transitive, $I$ is not transitive. Another definition for completenes: A binary relation $R$ is Euclidean iff. $aRb$ and $aRc$ implies $bRc$.


1. Is it true that $I$ is not Euclidean when it is derived from a total semiorder?

2. If I impose an additional constraint that $I$ must be Euclidean, does $R$ then become a preorder?

I'm asking because in preference theory and mathematical psychology, nice examples have been given for the non-transitivity of preferences (Luce's sugar in coffee example), and these lead to semiorder representations. But the case $aIb$, $aIc$ and $bPc$ is apparently never discussed in this literature and seems quite odd if $P$ is supposed to express preferences and $I$ is (non-transitive) indistinguishability.

  • $\begingroup$ What is $d$ in the semitransitive definition (1)? Or should the first part (after the "if") have a $d$ in it somewhere? $\endgroup$
    – coffeemath
    Sep 30 '16 at 12:04
  • 1
    $\begingroup$ @coffeemath: $(1)$ should have $a,b,c$, and $d$ all universally quantified. $\endgroup$ Sep 30 '16 at 12:07
  • $\begingroup$ You're right I was sloppy about it. The existence of $d$ must be guaranteed, and the other values are (implicitly) universally quantified. I've made the definition clearer. $\endgroup$ Sep 30 '16 at 13:27
  • $\begingroup$ Eric: If as now $d$ is only qualified by "there is a $d$ etc," then it seems one could just let $d=b$ so that any relation at all becomes semitransitive. $\endgroup$
    – coffeemath
    Sep 30 '16 at 14:02
  • $\begingroup$ @coffemath I'm so stupid, you're right, it must be universally quantified, of course. I'm fixing this again. On the bright side, I've got the proof that it becomes a preorder if I is also Euclidean, it's fairly trivial because every symmetric and Euclidean relation is also transitive. So perhaps I should answer my own question..? (Regarding #1 I'm still not sure.) I'm not a mathematician, as you might have guessed. $\endgroup$ Sep 30 '16 at 14:29

Okay, this seems to be fairly easy and I believe I can answer it myself. Short answer: Yes to both questions. Intentionally verbose answers:

Theorem 1: Suppose $R$ is a semiorder, which implies that $I$ derived from $R$ is symmetric but not transitive. Then $I$ is also not Euclidean.

Proof: That $I$ is not transitive implies that there is at least one triple $a, b, c$ in the domain of $R$ such that $aIb$, $bIc$, but $\lnot (a I c)$. Since $I$ is symmetric, we also get $bIa$, $bIc$ and $\lnot (aIc)$, which directly violates Euclideanness.

Theorem 2: Suppose $S$ is a semiorder and we add a constraint that $I$ derived from $S$ in the usual way must additionally be Euclidean. Then $S$ is a preorder (as a special case of a semiorder).

Proof: A preorder $R$ is a reflexive and transitive relation. From the definition of the strict part $P$ as $aPb$ iff. $aRb$ and $\lnot(bRa)$ and the symmetric part $I$ as $aIb$ iff. $aRb$ and $bRa$, it follows that both $P$ and $I$ must be transitive. In fact, given distinct relations $P$ and $I$, a preorder can be defined as $aRb$ iff $aPb$ or $aIb$, where $P$ is asymmetric and transitive, and $I$ is symmetric and transitive. Since $P$ derived from a semiorder is also asymmetric and transitive, we only have to show that $I$ derived from a semiorder $S$ plus Euclideanness is also symmetric and transitive.

(a) $I$ is defined as $aIb$ iff. $aSb$ and $bSa$ from semiorder $S$, hence it is symmetric.

(b) By assumption, $I$ is Euclidean, and from (a) we know that it is symmetric. From Lemma 1 we know that it is also transitive. So any relation $R$ defined from $P$ and $I$ is a preorder, hence $S$ must be a preorder, too.

Lemma 1: Every symmetric and Euclidean relation is transitive.

Proof: Euclideanness of a binary relation $R$ states that (1) for all a, b, c: $aRb$ and $aRc$ implies $bRc$. Symmetry states that (2) for all a,b: $aRb$ implies $bRa$. By symmetry of $R$ from (1) we get from (1'): $bRa$ and $aRc$ implies $bRc$. This is just the definition of transitivity.


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.