Editing Intransitivity

{{About|intransitivity in mathematics||Intransitive (disambiguation)}}
{{Short description|Property of mathematical relations}}
In [[mathematics]], '''intransitivity''' (sometimes called '''nontransitivity''') is a property of [[binary relation]]s that are not [[transitive relation]]s.  That is, we can find three values <math>a</math>, <math>b</math>, and <math>c</math> where the transitive condition does not hold.  

'''Antitransitivity''' is a [[Mathematical jargon#stronger|stronger property]] which describes a relation where, for any three values, the transitivity condition never holds.

Some authors use the term {{em|intransitive}} to refer to  antitransitivity.<ref>{{Cite web |url=http://www.jgsee.kmutt.ac.th/exell/Logic/Logic42.htm#33 |title=Guide to Logic, Relations II<!-- Bot generated title --> |access-date=2006-07-13 |archive-url=https://web.archive.org/web/20080916115323/http://www.jgsee.kmutt.ac.th/exell/Logic/Logic42.htm#33 |archive-date=2008-09-16 |url-status=dead }}</ref><ref>{{Cite web |url=http://www.virtual.cvut.cz/kifb/en/concepts/_intransitive_relation.html |title=IntransitiveRelation<!-- Bot generated title --> |access-date=2006-07-13 |archive-url=https://web.archive.org/web/20160303172324/http://www.virtual.cvut.cz/kifb/en/concepts/_intransitive_relation.html |archive-date=2016-03-03 |url-status=dead }}</ref>

== Intransitivity ==

A relation is transitive if, whenever it relates some A to some B, and that B to some C, it also relates that A to that C.  A relation is {{em|intransitive}} if it is not transitive.  Assuming the relation is named <math>R</math>, it is intransitive if:

<math display=block>\lnot\left(\forall a, b, c: a R b \land b R c \implies a R c\right).</math>

This statement is equivalent to
<math display=block>\exists a,b,c : a R b \land b R c \land \lnot(a R c).</math>

For example, the inequality relation, <math>\neq</math>, is intransitive.  This can be demonstrated by replacing <math>R</math> with <math>\neq</math> and choosing <math>a=1</math>, <math>b=2</math>, and <math>c=1</math>.  We have <math>1\neq 2</math> and <math>2\neq 1</math> and it is not true that <math>1\neq 1</math>.

Notice that, for a relation to be intransitive, the transitivity condition just has to be not true at some <math>a</math>, <math>b</math>, and <math>c</math>.  It can still hold for others.  For example, it holds when <math>a=1</math>, <math>b=2</math>, and <math>c=3</math>, then <math>1\neq 2</math> and <math>2\neq 3</math> and it is true that <math>1\neq 3</math>.

For a more complicated example of intransitivity, consider the relation ''R'' on the integers such that ''a R b'' if and only if ''a'' is a multiple of ''b'' or a divisor of ''b''. This relation is intransitive since, for example, 2 ''R'' 6 (2 is a divisor of 6) and 6 ''R'' 3 (6 is a multiple of 3), but 2 is neither a multiple nor a divisor of 3. This does not imply that the relation is {{em|antitransitive}} (see below); for example, 2 ''R'' 6, 6 ''R'' 12, and 2 ''R'' 12 as well.

An example in biology comes from the [[food chain]].  Wolves feed on deer, and deer feed on grass, but wolves do not feed on grass.<ref>Wolves ''do'' in fact eat grass – see {{cite book|title=Wild Health: Lessons in Natural Wellness from the Animal Kingdom|first1=Cindy|last1=Engel|year=2003|edition=paperback|publisher=Houghton Mifflin|isbn=0-618-34068-8|page=141}}.</ref> Thus, the {{em|feed on}} relation among life forms is intransitive, in this sense.

== 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''.

== Cycles ==
[[File:Three-part cycle diagram.png|alt=Cycle diagram|thumb|Sometimes, when people are asked their preferences through a series of binary questions, they will give logically impossible responses:  1 is better than 2, and 2 is better than 3, but 3 is better than 1.]]
The term {{em|intransitivity}} is often used when speaking of scenarios in which a relation describes the relative preferences between pairs of options, and weighing several options produces a "loop" of preference:

* A is preferred to B
* B is preferred to C
* C is preferred to A

[[Rock, paper, scissors]]; [[intransitive dice]]; and [[Penney's game]] are examples. Real combative relations of competing species,<ref>{{Cite journal | doi=10.1038/nature00823| pmid=12110887| title=Local dispersal promotes biodiversity in a real-life game of rock–paper–scissors| journal=Nature| volume=418| issue=6894| pages=171–174| year=2002| last1=Kerr| first1=Benjamin| last2=Riley| first2=Margaret A.| last3=Feldman| first3=Marcus W.| last4=Bohannan| first4=Brendan J. M.| bibcode=2002Natur.418..171K| s2cid=4348391|authorlink4=Brendan Bohannan}}</ref> strategies of individual animals,<ref>[http://www.scientificamerican.com/article/mating-lizards-play-a-gam/ Leutwyler, K. (2000). Mating Lizards Play a Game of Rock-Paper-Scissors. Scientific American.]</ref> and fights of remote-controlled vehicles in BattleBots shows ("robot Darwinism")<ref>[http://www.popsci.com/technology/article/2013-06/elaborate-history-how-wedges-ruined-battlebots Atherton, K. D. (2013). A brief history of the demise of battle bots.]</ref> can  be cyclic as well.

Assuming no option is preferred to itself i.e. the relation is [[irreflexive]], a preference relation with a loop is not transitive. For if it is, each option in the loop is preferred to each option, including itself. This can be illustrated for this example of a loop among A, B, and C. Assume the relation is transitive. Then, since A is preferred to B and B is preferred to C, also A is preferred to C. But then, since C is preferred to A, also A is preferred to A.

Therefore such a preference loop (or {{em|[[Cycle (graph theory)|cycle]]}}) is known as an {{em|intransitivity}}.

Notice that a cycle is neither necessary nor sufficient for a binary relation to be not transitive.  For example, an [[equivalence relation]] possesses cycles but is transitive.  Now, consider the relation "is an enemy of" and suppose that the relation is symmetric and satisfies the condition that for any country, any enemy of an enemy of the country is not itself an enemy of the country.  This is an example of an antitransitive relation that does not have any cycles.  In particular, by virtue of being antitransitive the relation is not transitive.

The game of [[rock, paper, scissors]] is an example.  The relation over rock, paper, and scissors is "defeats", and the standard rules of the game are such that rock defeats scissors, scissors defeats paper, and paper defeats rock.  Furthermore, it is also true that scissors does not defeat rock, paper does not defeat scissors, and rock does not defeat paper.  Finally, it is also true that no option defeats itself. This information can be depicted in a table:
{| class="wikitable" style="text-align:center;
! !! rock !! scissors !! paper
|-
! rock
| 0 || 1 || 0
|-
! scissors
| 0 || 0 || 1
|-
! paper
| 1 || 0 || 0
|}

The first argument of the relation is a row and the second one is a column.  Ones indicate the relation holds, zero indicates that it does not hold.  Now, notice that the following statement is true for any pair of elements x and y drawn (with replacement) from the set {rock, scissors, paper}:  If x defeats y, and y defeats z, then x does not defeat z.  Hence the relation is antitransitive.

Thus, a cycle is neither necessary nor sufficient for a binary relation to be antitransitive.

== Occurrences in preferences<!--This section is linked from [[Preference (economics)]]--> ==

* Intransitivity can occur under [[majority rule]], in probabilistic outcomes of [[game theory]], and in the [[Condorcet voting]] method in which ranking several candidates can produce a loop of preference when the weights are compared (see [[voting paradox]]). 
* [[Intransitive dice]] demonstrate that the relation "{{sic|die|hide=y}} ''X'' rolls a higher number than die ''Y'' more than half the time" need not be transitive.
* In [[psychology]], intransitivity often occurs in a person's [[Value system|system of values]] (or [[preference]]s, or [[Taste (sociology)|tastes]]), potentially leading to unresolvable conflicts.
* Analogously, in [[economics]] intransitivity can occur in a consumer's [[Preference (economics)|preferences]]. This may lead to [[consumer behaviour]] that does not conform to perfect [[Rationality#Economics|economic rationality]].  Economists and philosophers have questioned whether violations of transitivity must necessarily lead to 'irrational behaviour' (see Anand (1993)).

== Likelihood ==

It has been suggested that [[Condorcet method|Condorcet voting]] tends to eliminate "intransitive loops" when large numbers of voters participate because the overall assessment criteria for voters balances out.  For instance, voters may prefer candidates on several different units of measure such as by order of social consciousness or by order of most fiscally conservative.

In such cases intransitivity reduces to a broader equation of numbers of people and the weights of their units of measure in assessing candidates.

Such as:

* 30% favor 60/40 weighting between social consciousness and fiscal conservatism
* 50% favor 50/50 weighting between social consciousness and fiscal conservatism
* 20% favor a 40/60 weighting between social consciousness and fiscal conservatism

While each voter may not assess the units of measure identically, the trend then becomes a single [[Probability vector|vector]] on which the [[Consensus decision-making|consensus]] agrees is a preferred balance of candidate criteria.

== References ==

{{reflist|group=note}}
{{reflist}}

== Further reading ==

* {{cite book|last1=Anand|first1=P|year=1993|title=Foundations of Rational Choice Under Risk|location=Oxford|publisher=Oxford University Press}}.
* [https://www.researchgate.net/publication/225909889_How_vicious_are_cycles_of_intransitive_choice Bar-Hillel, M., & Margalit, A. (1988). How vicious are cycles of intransitive choice? ''Theory and Decision, 24''(2), 119-145.]
* {{cite journal|doi = 10.1007/s11518-014-5245-x|title = Complexity and intransitivity in technological development|journal = Journal of Systems Science and Systems Engineering|volume = 23|issue = 2|pages = 128–152|year = 2014|last1 = Klimenko|first1 = Alexander Y.|s2cid = 59390606|url = http://staff.mechmining.uq.edu.au/klimenko/pub/pdf/JSSSE_2014_p.pdf}}
* {{cite journal|doi = 10.3390/e17064364|title = Intransitivity in Theory and in the Real World|journal = Entropy|volume = 17|issue = 12|pages = 4364–4412|year = 2015|last1 = Klimenko|first1 = Alexander|bibcode = 2015Entrp..17.4364K|arxiv = 1507.03169|doi-access = free}}

[[Category:Properties of binary relations]]