Difference between revisions of "Binary relation"
Line 14: | Line 14: | ||
The range of a binary relation <math>\mathfrak{R}</math> over <math>A</math> and <math>B</math>, written <math>\text{Ran}(\mathfrak{R})</math>, is defined to be the set <math>\{y \in B | (\exists x \in A)(x,y) \in \mathfrak{R}\}</math>. It is thus the set of the second components of the ordered pairs in <math>\mathfrak{R}</math>. | The range of a binary relation <math>\mathfrak{R}</math> over <math>A</math> and <math>B</math>, written <math>\text{Ran}(\mathfrak{R})</math>, is defined to be the set <math>\{y \in B | (\exists x \in A)(x,y) \in \mathfrak{R}\}</math>. It is thus the set of the second components of the ordered pairs in <math>\mathfrak{R}</math>. | ||
+ | |||
+ | == Reflexivity, Symmetry and Transitivity == | ||
+ | |||
+ | A binary relation <math>\mathfrak{R}</math> over <math>A</math> is defined to be reflexive if <math>(\forall a \in A)(a \mathfrak{R} a)</math>. | ||
+ | |||
+ | A binary relation <math>\mathfrak{R}</math> over <math>A</math> is defined to be symmetric if <math>(\forall (a,b) \in A^2)((a \mathfrak{R} b) \rightarrow (b \mathfrak{R} a))</math>. | ||
+ | |||
+ | A binary relation <math>\mathfrak{R}</math> over <math>A</math> is defined to be anti-symmetric if <math>(\forall (a,b) \in A^2)(((a \mathfrak{R} b) \wedge (b \mathfrak{R} a)) \rightarrow (a = b))</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>. | ||
==See also== | ==See also== |
Revision as of 17:13, 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
.
See also
This article is a stub. Help us out by expanding it.