Intransitivity
Encyclopedia
In mathematics
, the term intransitivity is used for related, but different, properties of binary relation
s:
if, whenever it relates some A to some B, and that B to some C, it also relates that A to that C. Some authors call a relation intransitive if it is not transitive, i.e.
Where
indicates some relationship.
For instance, in the food chain
, wolves feed on deer, and deer feed on grass, but wolves do not feed on grass. Thus, the feed on relation among life forms is intransitive, in this sense.
Another example that does not involve preference loops arises in freemasonry
: it may be the case that 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.
We just saw that the 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 antitransitive if this never occurs at all, i.e.,
Many authors use the term intransitivity to mean antitransitivity.
An example of an antitransitive relation: the defeated relation in knockout tournaments. 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.
Rock, paper, scissors
is an example.
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 "cycle
") is known as an 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.
Finally, let us work with the example of rock, paper, scissors
, calling the three options A, B, and C.
Now, the relation over A, B, and C is "defeats" and the standard rules of the game are such that A defeats B, B defeats C, and C defeats A. Furthermore, it is also true that B does not defeat A, C does not defeat B, and A does not defeat C. Finally, it is also true that no option defeats itself. This information can be depicted in a table:majority rule
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, the term intransitivity is used for related, but different, properties of binary relation
Binary relation
In mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...
s:
Intransitivity
A relation is transitiveTransitive relation
In mathematics, a binary relation R over a set X is transitive if whenever an element a is related to an element b, and b is in turn related to an element c, then a is also related to c....
if, whenever it relates some A to some B, and that B to some C, it also relates that A to that C. Some authors call a relation intransitive if it is not transitive, i.e.
Where
indicates some relationship.For instance, in the food chain
Food chain
A food web depicts feeding connections in an ecological community. Ecologists can broadly lump all life forms into one of two categories called trophic levels: 1) the autotrophs, and 2) the heterotrophs...
, wolves feed on deer, and deer feed on grass, but wolves do not feed on grass. Thus, the feed on relation among life forms is intransitive, in this sense.
Another example that does not involve preference loops arises in freemasonry
Freemasonry
Freemasonry is a fraternal organisation that arose from obscure origins in the late 16th to early 17th century. Freemasonry now exists in various forms all over the world, with a membership estimated at around six million, including approximately 150,000 under the jurisdictions of the Grand Lodge...
: it may be the case that 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.
Antitransitivity
Often the term intransitive is used to refer to the stronger property of antitransitivity.We just saw that the 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 antitransitive if this never occurs at all, i.e.,
Many authors use the term intransitivity to mean antitransitivity.
An example of an antitransitive relation: the defeated relation in knockout tournaments. 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.
Cycles
The term 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
Rock, Paper, Scissors
Rock-paper-scissors is a hand game played by two people. The game is also known as roshambo, or another ordering of the three items ....
is an example.
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 "cycle
Cycle (graph theory)
In graph theory, the term cycle may refer to a closed path. If repeated vertices are allowed, it is more often called a closed walk. If the path is a simple path, with no repeated vertices or edges other than the starting and ending vertices, it may also be called a simple cycle, circuit, circle,...
") is known as an intransitivity.
Notice that a cycle is neither necessary nor sufficient for a binary relation to be not transitive. For example, an equivalence relation
Equivalence relation
In mathematics, an equivalence relation is a relation that, loosely speaking, partitions a set so that every element of the set is a member of one and only one cell of the partition. Two elements of the set are considered equivalent if and only if they are elements of the same cell...
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.
Finally, let us work with the example of rock, paper, scissors
Rock, Paper, Scissors
Rock-paper-scissors is a hand game played by two people. The game is also known as roshambo, or another ordering of the three items ....
, calling the three options A, B, and C.
Now, the relation over A, B, and C is "defeats" and the standard rules of the game are such that A defeats B, B defeats C, and C defeats A. Furthermore, it is also true that B does not defeat A, C does not defeat B, and A does not defeat C. Finally, it is also true that no option defeats itself. This information can be depicted in a table: