Intransitivity

From Wikipedia, the free encyclopedia

In mathematics, intransitivity is the property of a binary relation's not being transitive.

Although the word transitivity is often used very generally when speaking of many sorts of binary relations other than preference orderings, the term intransitivity is seldom used except when speaking of scenarios in which weighing several options produces a "loop" of preference. For example:

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

A concrete example of intransitivity that does not involve preference loops arises in freemasonry: lodge A recognizes lodge B, and lodge B recognizes lodge C, but lodge A does not recognize lodge C. Thus the recognition relation among Masonic lodges is intransitive.

1 Formal definitions, with examples
2 Occurrences
3 Likelihood of intransitivity
4 References
5 External link

[edit] Formal definitions, with examples

There are several different notions of intransitivity.

In mathematics, a binary relation $R$ is transitive if $\forall a, b, c,\ \left(a R b\ \mathrm{and}\ b R c\right)\ \mathrm{implies}\ a R c.$

Examples of transitive relations include "more than", "lives in the same county as", and "is ancestor of".

The transitive closure of a relation is the smallest transitive relation that includes it. For example,

"is ancestor of" is the transitive closure of "is parent of"
"is connected by road with" is the transitive closure of "is on a road leading to"
(for atoms) "is in the same molecule as" is the transitive closure of "has a molecular bond with"

A relation is sometimes called intransitive to indicate that it is not transitive. That is to say, if not for all a, b, c, a R b and b R c implies a R c.

A more common mathematical definition, however, is this: a binary relation R is intransitive (or antitransitive) when $\forall \{ a, b, c \}$ , $a R b$ and $b R c$ implies not $a R c$ . ^[1] ^[2]

This notion is stricter: every nonempty relation that is antitransitive, is not transitive, but the reverse does not hold: many relations are neither transitive nor antitransitive.

Antitransitivity does not seem to be a very useful characterization of a relation. Note that it is still possible to have ${a, b, c, d}$ with $a R b$ , $b R c$ , $c R d$ , and $a R d$ .

Examples of antitransitive relations:

"is married to"
"is parent of", if we disregard incest

The notion mentioned in the first paragraph, however, is different, and can be defined as follows: an intransitivity (or conflict) in a binary relation R is a pair a, b such that a R+ b and b R a, where R+ is the transitive closure of R. A relation has intransitivity if such a pair exists, i.e., if its transitive closure is not antisymmetric. Most mathematicians will not use the term intransitive to describe such a relation, but instead say that it does not define a partial order.

[edit] Occurrences

Intransitivity can occur under majority rule, in probabalistic 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. A well-known example is the children's game rock, paper, scissors. Intransitive dice demonstrate that probabilities are not necessarily transitive.

[edit] Likelihood of intransitivity

It has been suggested that 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 conservatisim

While each voter may not assess the units of measure identically, the trend then becomes a single vector on which the consensus agrees is a preferred balance of candidate criteria.