FACTOID # 22: South Dakota has the highest employment ratio in America, but the lowest median earnings of full-time male employees.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Transitive relation

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. Euclid, a famous Greek mathematician known as the father of geometry, is shown here in detail from The School of Athens by Raphael. ... In mathematics, the concept of binary relation, sometimes called dyadic relation, is exemplified by such ideas as is greater than and is equal to in arithmetic, or is congruent to in geometry, or is an element of or is a subset of in set theory. ... In mathematics, a set can be thought of as any collection of distinct things considered as a whole. ...


In mathematical notation, this is: Mathematical notation is used in mathematics, and throughout the physical sciences, engineering, and economics. ...

forall a, b, c in X, a ,R, b and b ,R, c ; Rightarrow a ,R, c

Contents


Counting transitive relations

Unlike other relation properties, it is not possible to find a general formula that counts the number of transitive relations on a finite set. However, there is a formula for finding the number of relations which are simultaneously reflexive, symmetric, and transitive


Examples

For example, "is greater than" and "is equal to" are transitive relations: if a = b and b = c, then a = c.


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 the mother of Claire.


Examples of transitive relations include:

In mathematics, two mathematical objects are considered equal if they are precisely the same in every way. ... A is a subset of B, and B is a superset of A. In mathematics, especially in set theory, a set A is a subset of a set B, if A is contained inside B. The relationship of one set being a subset of another is called inclusion. ... A is a subset of B, and B is a superset of A. In mathematics, especially in set theory, a set A is a subset of a set B, if A is contained inside B. The relationship of one set being a subset of another is called inclusion. ... The feasible regions of linear programming are defined by a set of inequalities. ... In mathematics, a divisor of an integer n, also called a factor of n, is an integer which evenly divides n without leaving a remainder. ... In logic, material implication is a binary operator. ...

Other properties that require transitivity

This article is about the mathematics concept. ... 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 for short) is a set equipped with a partial order relation. ... This article is about the mathematics concept. ... In mathematics, a binary relation R on a set X is antisymmetric if, for all a and b in X, if a is related to b and b is related to a, then a = b. ... In mathematics, an equivalence relation on a set X is a binary relation on X that is reflexive, symmetric and transitive, i. ... This article is about the mathematics concept. ... In mathematics, a binary relation R over a set X is symmetric if it holds for all a and b in X that if a is related to b then b is related to a. ... In mathematics, a total order or linear order on a set X is any binary relation on X that is antisymmetric, transitive, and total. ... In mathematics, a binary relation R on a set X is antisymmetric if, for all a and b in X, if a is related to b and b is related to a, then a = b. ... In mathematics, a binary relation R over a set X is total if it holds for all a and b in X that a is related to b or b is related to a (or both). ...

See also

In mathematics, the transitive closure of a binary relation R on a set X is the smallest transitive relation on X that contains R. For any relation R the transitive closure of R always exists. ... In mathematics, the transitive reduction of a binary relation R on a set X is the smallest relation on X such that that the transitive closure of is the same as the transitive closure of R. If the transitive closure of R is antisymmetric and finite, then is unique. ... Intransitivity is a scenario in which weighing several options produces a loop of preference. ... 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 if a is related to b then b is related to a. ...

External links

  • Transitivity in Action at cut-the-knot
  • Number of transitive relations on n labeled nodes, sequence A006905 from the On-Line Encyclopedia of Integer Sequences

This article is being considered for deletion in accordance with Wikipedias deletion policy. ... The On-Line Encyclopedia of Integer Sequences (OEIS) is an extensive searchable database of integer sequences, freely available on the Web. ...

Sources

  • Discrete and Combinatorial Mathematics - Fifth Edition - by Ralph P. Grimaldi

  Results from FactBites:
 
Transitive Closure on the Instruction Systolic Array (3699 words)
Furthermore, a generalization of the transitive closure algorithm is implemented to solve other path problems, such as the shortest path problem.
The transitive closure problem may be generalized to the algebraic path problem.
The problem of computing the transitive closure of a graph may be viewed as a special case of the algebraic path problem.
Transitive relation - Wikipedia, the free encyclopedia (254 words)
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.
Unlike other relation properties, it is not possible to find a general formula that counts the number of transitive relations on a finite set.
equivalence relation - a relation that is a preorder and symmetric.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m