Simple but nontrivial trichotomous relation that isn’t a strict total order?

Question

A binary relation $R$ over a set $A$ is a strict order if it’s irreflexive, asymmetric, and transitive. It’s trichotomous if for every $a, b \in A$ exactly one of $xRy$, $yRx$, and $x = y$ is true. It’s a strict total order if it’s both trichotomous and a strict order.

I’ve been teaching a discrete math class for years and have been looking without success for a simple example of a binary relation that is trichotomous but not a strict total order. None of the “nice” trichotomous binary relations I’ve tried fit the bill, and the best I’m able to do is draw a picture of an example of such a relation and say “this works, but there isn’t a simple explanation for the rule defining $R$ other than this picture.”

Is there a simple way to define a trichotomous relation $R$ over a set $A$ such that

1. the definition of $R$ is “simple” (e.g. accessible to a first-quarter college freshman with no prior experience with proof-based mathematics),
2. the definition is given symbolically (e.g. not a picture),
3. the relation $R$ isn’t a strict total order, and
4. (ideally) $A$ is a large set, or there’s a family or such relations over arbitrarily large sets?

Thanks!

Answer 1

The direct successor relation on residue of classes integers modulo $3$: $[m] \prec [n]$ iff $$n \equiv m + 1 \pmod{3}\text{.}$$ The three elements of this relation are $[0]\prec [1]$, $[1]\prec [2]$, $[2]\prec[0]$.

Conversely, a nontransitive, irreflexive, asymmetric relation $<$ has $a_0<a_1$, $a_1<a_2$, and $\neg(a_0<a_2)$ for some distinct $a_0,a_1,a_2$. Trichotomy implies $a_2<a_0$, so the restriction of $<$ to these elements is an isomorphic copy of $\prec$.

---

There exist explicit modular-arithmetic constructions due to Bose (1939) and Skolem (1958) of Steiner triple systems of order $6k+3$ and $6k+1$, respectively. Let $<$ be the lexicographic ordering on the elements of one of these constructions. Define $\prec$ such that $$a\prec b\prec c \prec a$$ if and only if $\{a,b,c\}$ is a triple in the system such that with $a<b<c$. Then $\prec$, which is trichotomous by construction, is "maximally intransitive" in the sense that $$a \prec b \Rightarrow \exists!_c(b\prec c \land c \prec a)\text{,}$$ i.e., every pair completes to a unique cycle. It may be helpful to illustrate the construction for systems of order 7 and 9 (data taken from related paper by Fort and Hedlund (1958)):

---

More generally, one may consider a set $S$ of cardinality $2k+1$ together with a trichotomous relation $\prec$ such that $$\#\{y|y\prec x \} = k = \#\{x|x\prec y\}\text{.}$$

In graph language, $(S,\prec)$ is a complete digraph (a tournament) that is regular—this condition is an opposite extreme to being a strict total order. Akin (2020) calls such graphs games; they show that

• There are a small number of games of small orders:
  • 1 game of order $3$ ("rock, paper, scissors"),
  • 1 game of order $5$ (the memetic "rock, paper, scissors, Spock, lizard"), and
  • 3 games of order $7$.
• Games constructed from Steiner triple systems as before are called Steiner games.
• Given a group $G$ and a subset $A\subset G$ such that $A\cap A^{-1} = \emptyset$, $A\cup A^{-1}=G\setminus\{e\}$, the relation $(g \prec h)\equiv (g^{-1}h\in A)$ is the group game associated with $(G,A)$; and the special case of $\mathbb{Z}/(2k+1)$ in I. K.'s answer is called a rotational tournament.
• Given two tournaments $S$ and $T$, their lexicographic product $S\ltimes T$ is also a tournament (as in MJD's answer). If $S$ and $T$ are games, then so is $S\ltimes T$.

Akin goes on to provide a large number of constructions, including "doubled" games, "coset space" games, infinite games, and game invariants—when it comes seems finding examples, it seems we have an embarrassment of riches to choose from.

---

Akin, Ethan. 2020. “Rock, Paper, Scissors, Etc – Topics in the Theory of Regular Tournaments.” arXiv.

Bose, R. C. 1939. “On the Construction of Balanced Incomplete Block Designs.” Annals of Eugenics 9 (4): 353–99.

Fort, M. K., and G. A. Hedlund. 1958. “Minimal Coverings of Pairs by Triples.” Pacific Journal of Mathematics 8 (4): 709–19.

Skolem, Th. 1958. “Some Remarks on the Triple Systems of Steiner.” Mathematica Scandinavica 6 (December): 273–80.

Answer 2

Inspired by the examples of K B Dave and MJD, here's another simple example over a finite (but arbitrarily large) set:

Let $A = \{1, 2, \dots, 2n+1\}$ and let $x \prec y \iff y - x \equiv k \pmod{2n + 1}$ for some $k \in \{1, 2, \dots, n\}$.

Intuitively, $\prec$ can be visualized by arranging the numbers from $1$ to $2n+1$ clockwise in a circle and letting $x \prec y$ denote "$y$ is closer to $x$ clockwise than counterclockwise."

• $\prec$ is clearly trichotomous: if the shortest way from $x$ to $y$ is clockwise, then the shortest way from $y$ to $x$ must be counterclockwise, and vice versa. The fact that $2n+1$ is odd ensures that the clockwise and counterclockwise distance between $x$ and $y$ cannot be the same unless $x = y$.

• $\prec$ cannot be a strict order, since transitivity fails: $x \prec x+1$ for all $x \in \{1, 2, \dots, 2n\}$, but $2n+1 \prec 1$. In fact, we can always find three elements $x$, $y$ and $z$, spaced approximately evenly around the circle, such that $x \prec y$, $y \prec z$ and $z \prec x$.*

I'd say this relation $\prec$ meets all your criteria pretty well:

1. the definition of $R$ is “simple” (e.g. accessible to a first-quarter college freshman with no prior experience with proof-based mathematics),

The symbolic definition of $\prec$ requires some basic modular arithmetic, but little enough that it's easy to introduce "on the fly" even if youre students aren't familiar with the concept already.

2. the definition is given symbolically (e.g. not a picture),

Yes, but you can (and probably should) also draw a picture of the "number circle".

3. the relation $R$ isn’t a strict total order, and

Check, $\prec$ is not transitive.

4. (ideally) $A$ is a large set, or there’s a family or such relations over arbitrarily large sets?

Check, $A$ can have any odd number of elements.

(The same trick almost works for any even number of elements, but the problem is that trichotomy fails because there will be pairs of elements that are on opposite sides of the circle from each other. Alas, the same thing also happens if you try to naively extend this example to an infinite number of elements with e.g. $A = [0,1)$ and $x \prec y \iff 0 < y - x - \lfloor y -x \rfloor < \frac12$.)

---

*) In fact any non-transitive trichotomous relation must have three elements that form such a "rock, paper, scissors" triplet.

The proof is straightforward: non-transitivity implies the existence of some $x$, $y$ and $z$ such that $x \prec y$, $y \prec z$ and $x \not\prec z$. Trichotomy then implies that either $z \prec x$ (in which case we have our triplet) or $x = z$; but the latter isn't possible either, since it would imply that $x \prec y$ and $y \prec x$, which also violates trichotomy.

---

Ps. This is pretty much the same as one of the examples I used in this old answer from 2015.

Answer 3

Let's expand K B Dave's suggestion above.

Suppose, following Dave's suggestion, that we have three “colors” called “rock”, “paper”, “scissors” ($R, P, S$), which are ordered nontransitively $R< P< S< R$.

For each “color” we have numbers $1\ldots n$ of that “color”.

All the rock numbers precede the paper numbers, which precede the scissors numbers, which precede the rock numbers. But if two numbers are the same color we compare them normally.

Formally, consider the set $ \{R, P, S\}\times \{1\ldots n\} $

and take the order relation where $$\langle c, n\rangle \prec \langle c', n'\rangle$$

if and only if either

1. $c<c'$, or
2. $c=c'$ and $n<n'$

It's trichotomous. For example rock 5 is preceded by all scissors numbers and by rock $0\ldots 4$; it is followed by rock numbers $6\ldots n$ and by all paper numbers.

I think this should still work even if you replace $\{1\ldots n\}$ with $\Bbb N$ or $\Bbb R$ or whatever.

Answer 4

You could use non-transitive dice to generate a simple example, with the ordering $A\prec B$ if the die $A$ beats the die $B$ more than half the time. To generate a large set of this type, it's necessary to eliminate cases where $A$ beats $B$ exactly half the time. So, for example, suppose we took a set of 3-sided dice, where no number appears on two different dice. Then, ties are impossible, and the probability of one die beating another is always a whole number of ninths.

To state this formally: Let $S$ be a partition of $\mathbb{Z}$ into subsets of size 3. For $A,B\in S$ we say $A\prec B$ if $\#\{(a,b)\in A\times B \hspace{4pt}\vert\hspace{4pt}a<b\} \le 4$.

Of course, for some partitions, this will be strict order, but it is not in general.