Discrete Mathematics – Nontrivial Trichotomous Relation That Isn’t a Strict Total Order

discrete mathematicsorder-theory

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!

Best Answer

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)):

order 7 complete intransitive digraph order 9 complete intransitive digraph

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.

Related Question