Editing Intransitivity (section)

== Antitransitivity ==

Antitransitivity for a relation says that the transitive condition does not hold for any three values.  

In the example above, the {{em|feed on}} relation is not transitive, but it still contains some transitivity: for instance, humans feed on rabbits, rabbits feed on carrots, and humans also feed on carrots.

A relation is {{em|antitransitive}} if this never occurs at all.  The formal definition is:
<math display=block>\forall a, b, c: a R b \land b R c \implies \lnot (a R c).</math>

For example, the relation ''R'' on the integers, such that ''a R b'' if and only if ''a + b'' is odd, is intransitive. If ''a R b'' and ''b R c'', then either ''a'' and ''c'' are both odd and ''b'' is even, or vice-versa. In either case, ''a + c'' is even.

A second example of an antitransitive relation: the ''defeated'' relation in [[knockout tournament]]s.  If player A defeated player B and player B defeated player C, A can have never played C, and therefore, A has not defeated C.

By [[Transposition (logic)|transposition]], each of the following formulas is equivalent to antitransitivity of ''R'':
<math display=block>\begin{align}
  &\forall a, b, c: a R b \land a R c \implies \lnot (b R c) \\[3pt]
  &\forall a, b, c: a R c \land b R c \implies \lnot (a R b)
\end{align}</math>

===Properties===

* An antitransitive relation is always [[Irreflexive relation|irreflexive]].
* An antitransitive relation on a set of ≥4 elements is never [[Connex relation|connex]]. On a 3-element set, the depicted cycle has both properties.
* An irreflexive and [[Left-unique relation|left-]] (or [[Right-unique relation|right-]]) unique relation is always anti-transitive.<ref>If ''aRb'', ''bRc'', and ''aRc'' would hold for some ''a'', ''b'', ''c'', then {{math|1=''a'' = ''b''}} by left uniqueness, contradicting ''aRb'' by irreflexivity.</ref> An example of the former is the ''mother'' relation. If ''A'' is the mother of ''B'', and ''B'' the mother of ''C'', then ''A'' cannot be the mother of ''C''.
* If a relation ''R'' is antitransitive, so is each subset of ''R''.