# If I make the non-strict part of a semiorder Euclidean, do I then get a preorder?

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$.

Questions:

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.

• What is $d$ in the semitransitive definition (1)? Or should the first part (after the "if") have a $d$ in it somewhere? Sep 30 '16 at 12:04
• @coffeemath: $(1)$ should have $a,b,c$, and $d$ all universally quantified. Sep 30 '16 at 12:07
• 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. Sep 30 '16 at 13:27
• 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. Sep 30 '16 at 14:02
• @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. 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.