Intransitivity

Encyclopedia : I : IN : INT : Intransitivity

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

For details, see, e.g., http://library.thinkquest.org/26408/math/utility.shtml

Formal definitions, with examples

There are several different notions of intransitivity.

In mathematics, a binary relation R is transitive if for all a, b, c, a R b and b R c implies a R c.

Examples of transitive relations:

"more than"
"lives in the same county as"
"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 for all a, b, c, a R b and b R c implies not a R c. (see e.g. http://www.jgsee.kmutt.ac.th/exell/Logic/Logic42.htm#33 or http://www.virtual.cvut.cz/kifb/en/concepts/_intransitive_relation.html).

This notion is stricter: every 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.

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.

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.

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.