Transitive relation - Citizendia

In mathematics, a binary relation R over a set X is transitive if it holds for all a, b, and c in X, that if a is related to b and b is related to c, then a is related to c. Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and In Mathematics, a binary relation (or a dyadic or 2-place relation) is an arbitrary association of elements within a set or with elements of

To write this in predicate logic:

$\forall a, b, c \in X,\ a \,R\, b \and b \,R\, c \; \Rightarrow a \,R\, c.$

For instance, the "greater than" relation is transitive:

If A > B, and B > C, then A > C. In Mathematical logic, predicate logic is the generic term for symbolic Formal systems like First-order logic, Second-order logic, Many-sorted

1 Examples
2 Closure properties
3 Properties of transitivity
4 Other properties that require transitivity
5 Counting transitive relations
6 See also
7 External links
8 References

Examples

For example, "is greater than," "is at least as great as," and "is equal to" (equality) are transitive relations:

whenever A > B and B > C, then also A > C

whenever A ≥ B and B ≥ C, then also A ≥ C

whenever A = B and B = C, then also A = C

For some time, economists and philosophers believed that preference was a transitive relation however there are now mathematical theories which demonstrate that preferences and other significant economic results can be modelled without resorting to this assumption. Equality is the paradigmatic example of the more general concept of Equivalence relations on a set those binary relations which are reflexive, symmetric

On the other hand, "is the mother of" is not a transitive relation, because if Alice is the mother of Brenda, and Brenda is the mother of Claire, then Alice is not always the mother of Claire. What is more, it is antitransitive: Alice can never be the mother of Claire. In Mathematics, the term intransitivity is used for related but different properties of Binary relations The property of not being transitive

Then again, in biology we often need to consider motherhood over an arbitrary number of generations: the relation "is a matrilinear ancestor of". Matrilineality is a system in which lineage is traced through the mother and maternal ancestors This is a transitive relation. More precisely, it is the transitive closure of the relation "is the mother of". In Mathematics, the transitive closure of a Binary relation R on a set X is the smallest Transitive relation on X

More examples of transitive relations:

"is a subset of" (set inclusion)
"divides" (divisibility)
"implies" (implication)

Closure properties

The converse of a transitive relation is always transitive: e. In Mathematics, a divisor of an Integer n, also called a factor of n, is an integer which evenly divides n without g. knowing that "is a subset of" is transitive and "is a superset of" is its converse, we can conclude that the latter is transitive as well.

The intersection of two transitive relations is always transitive: knowing that "was born before" and "has the same first name as" are transitive, we can conclude that "was born before and also has the same first name as" is also transitive.

The union of two transitive relations is not always transitive. For instance "was born before or has the same first name as" is not generally a transitive relation.

The complement of a transitive relation is not always transitive. For instance, while "equal to" is transitive, "not equal to" is only transitive on sets with at most two elements.

Properties of transitivity

For a transitive relation the following are equivalent:

Other properties that require transitivity

preorder - a reflexive transitive relation
partial order - an antisymmetric preorder
total preorder - a total preorder
equivalence relation - a symmetric preorder
strict weak ordering - a strict partial order in which incomparability is an equivalence relation
total ordering - a total, antisymmetric transitive relation

Counting transitive relations

Unlike other relation properties, no general formula that counts the number of transitive relations on a finite set (sequence A006905 in OEIS) is known. In Set theory, a Binary relation can have among other properties reflexivity or irreflexivity. Asymmetric often means simply not symmetric In this sense an asymmetric relation is a Binary relation which is not a Symmetric relation. In Mathematics, especially Order theory, a partially ordered set (or poset) formalizes the intuitive concept of an ordering sequencing or arrangement In Mathematics, especially in Order theory, preorders are Binary relations that satisfy certain conditions In Set theory, a Binary relation can have among other properties reflexivity or irreflexivity. In Mathematics, especially Order theory, a partially ordered set (or poset) formalizes the intuitive concept of an ordering sequencing or arrangement In Mathematics, a Binary relation R on a set X is antisymmetric if for all a and b in X, if In Mathematics, especially Order theory, a strict weak ordering is a Binary relation S that is a strict partial order In Mathematics, a Binary relation R over a set X is total if it holds for all a and b in X that In Mathematics, an equivalence relation is a Binary relation between two elements of a set which groups them together as being "equivalent" In Mathematics, a Binary relation R over a set X is symmetric if it holds for all a and b in X that In Mathematics, especially Order theory, a strict weak ordering is a Binary relation S that is a strict partial order In Mathematics and Set theory, a total order, linear order, simple order, or (non-strict ordering is a Binary relation In Mathematics, a Binary relation R over a set X is total if it holds for all a and b in X that In Mathematics, a Binary relation R on a set X is antisymmetric if for all a and b in X, if The On-Line Encyclopedia of Integer Sequences ( OEIS) also cited simply as Sloane's, is an extensive searchable Database of Integer sequences ^[1] However, there is a formula for finding the number of relations which are simultaneously reflexive, symmetric, and transitive – in other words, equivalence relations – (sequence A000110 in OEIS), those which are symmetric and transitive, those which are symmetric, transitive, and antisymmetric, and those which are total, transitive, and antisymmetric. In Mathematics, an equivalence relation is a Binary relation between two elements of a set which groups them together as being "equivalent" The On-Line Encyclopedia of Integer Sequences ( OEIS) also cited simply as Sloane's, is an extensive searchable Database of Integer sequences Pfeiffer^[2] has made some progress in this direction, expressing relations with combinations of these properties in terms of each other, but still calculating any one is difficult. See also^[3].

Number of n-element binary relations of different types
n	all	transitive	reflexive	preorder	partial order	total preorder	total order	equivalence relation
0	1	1	1	1	1	1	1	1
1	2	2	1	1	1	1	1	1
2	16	13	4	4	3	3	2	2
3	512	171	64	29	19	13	6	5
4	65536	3994	4096	355	219	75	24	15
OEIS	A002416	A006905	A053763	A000798	A001035	A000670	A000142	A000110

External links

Transitivity in Action at cut-the-knot

References

^ Steven R. In Mathematics, a binary relation (or a dyadic or 2-place relation) is an arbitrary association of elements within a set or with elements of In Set theory, a Binary relation can have among other properties reflexivity or irreflexivity. In Mathematics, especially in Order theory, preorders are Binary relations that satisfy certain conditions In Mathematics, especially Order theory, a partially ordered set (or poset) formalizes the intuitive concept of an ordering sequencing or arrangement In Mathematics, especially Order theory, a strict weak ordering is a Binary relation S that is a strict partial order In Mathematics and Set theory, a total order, linear order, simple order, or (non-strict ordering is a Binary relation In Mathematics, an equivalence relation is a Binary relation between two elements of a set which groups them together as being "equivalent" The On-Line Encyclopedia of Integer Sequences ( OEIS) also cited simply as Sloane's, is an extensive searchable Database of Integer sequences In Mathematics, the transitive closure of a Binary relation R on a set X is the smallest Transitive relation on X In Mathematics, the transitive reduction of a Binary relation R on a set X is a minimal Relation R' on In Mathematics, the term intransitivity is used for related but different properties of Binary relations The property of not being transitive In Set theory, a Binary relation can have among other properties reflexivity or irreflexivity. In Mathematics, a Binary relation R over a set X is symmetric if it holds for all a and b in X that Quasitransitivity is a weakened version of transitivity that is used in Social choice theory or Microeconomics. Cut-the-knot is an educational website maintained by Alexander Bogomolny and devoted to popular exposition of a great variety of topics in Mathematics. Finch, "Transitive relations, topologies and partial orders", 2003.
^ Götz Pfeiffer, "Counting Transitive Relations", Journal of Integer Sequences, Vol. 7 (2004), Article 04. 3. 2.
^ Gunnar Brinkmann and Brendan D. McKay,"Counting unlabelled topologies and transitive relations"

Discrete and Combinatorial Mathematics - Fifth Edition - by Ralph P. Grimaldi ISBN 0-201-19912-2

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
network: | |

Contents