A
binary relation over a
set X and a set
Y is a
subset of
X ×
Y (where
X ×
Y is the
Cartesian product of
X and
Y). It may also be thought of as a
binary function that takes as arguments an element
x of
X and an element
y of
Y and evaluates to true or false (indicating whether the ordered pair (
x,
y) is an element of the set which is the relation). The notations
R(
x,
y) or
xRy are used to mean "The
ordered pair (
x,
y) is an element of the binary relation
R".
Some important properties that binary relation R over X and Y may or may not have are:
- total: for all x in X there exists a y in Y such that xRy
- functional: for all x in X, and y and z in Y it holds that if xRy and xRz then y = z
- surjective: for all y in Y there exists an x in X such that xRy
- injective: for all x and z in X and y in Y it holds that if xRy and zRy then x = z
If X = Y then we simply say that the binary relation is over X.
Some important properties that binary relations over a set X may or may not have are:
- reflexive: for all x in X it holds that xRx
- irreflexive: for all x in X it holds that not xRx
- symmetric: for all x and z in X it holds that if xRz then zRx
- antisymmetric: for all x and z in X it holds that if xRz and zRx then x = z
- transitive: for all x, y and z in X it holds that if xRy and yRz then xRz
- trichotomous: for all x and y in X exactly one of xRy, yRx and x = y holds
See Also:
--
Function --
Partial order --
Total order --
Well-order --
Equivalence relation --
/Talk