Difference between revisions of "Binary relation"
(→Reflexivity, Symmetry and Transitivity) |
|||
Line 24: | Line 24: | ||
A binary relation <math>\mathfrak{R}</math> over <math>A</math> is defined to be transitive if <math>(\forall (a,b,c) \in A^3)(((a \mathfrak{R} b) \wedge (b \mathfrak{R} c)) \rightarrow (a \mathfrak{R} c))</math>. | A binary relation <math>\mathfrak{R}</math> over <math>A</math> is defined to be transitive if <math>(\forall (a,b,c) \in A^3)(((a \mathfrak{R} b) \wedge (b \mathfrak{R} c)) \rightarrow (a \mathfrak{R} c))</math>. | ||
+ | |||
+ | A reflexive, symmetric and transitive relation is called an [[equivalence relation]]. A reflexive, anti-symmetric and transitive relation is called an [[order relation]]. | ||
==See also== | ==See also== |
Revision as of 17:16, 30 November 2007
A binary relation is a relation which relates pairs of objects.
Thus, the relation of triangle similarity is a binary relation over the set of triangles but the relation which says is a factorization of over the positive integers is not a binary relation because it takes 3 arguments.
Contents
[hide]Formal Definition and Notation
Formally, we say that a relation on sets and is a subset of (the Cartesian product of and ). We often write instead of . If (the case of most common interest), then we say that is a relation on .
Thus, in the example of above, we may let be the set of ordered pairs of triangles in the Euclidean plane which are similar to each other. We could also define a relation on the power set of a set , so that , or , if and only if and are subsets of and is a subset of . This is a common example of an order relation.
Domain and Range
The domain of a binary relation over and , written , is defined to be the set . It is thus the set of the first components of the ordered pairs in .
The range of a binary relation over and , written , is defined to be the set . It is thus the set of the second components of the ordered pairs in .
Reflexivity, Symmetry and Transitivity
A binary relation over is defined to be reflexive if .
A binary relation over is defined to be symmetric if .
A binary relation over is defined to be anti-symmetric if .
A binary relation over is defined to be transitive if .
A reflexive, symmetric and transitive relation is called an equivalence relation. A reflexive, anti-symmetric and transitive relation is called an order relation.
See also
This article is a stub. Help us out by expanding it.