Binary relation

A binary relation is a relation which relates pairs of objects.

Thus, the relation $\sim$ of triangle similarity is a binary relation over the set of triangles but the relation $R(x, y, z) = \{(x, y, z) \mid x, y, z \in \mathbb{Z}_{>0}, x\cdot y = z\}$ which says $x\cdot y$ is a factorization of $z$ over the positive integers is not a binary relation because it takes 3 arguments.

Formal Definition and Notation

Formally, we say that a relation $\mathfrak{R}$ on sets $A$ and $B$ is a subset of $A \times B$ (the Cartesian product of $A$ and $B$ ). We often write $a \, \mathfrak{R} \, b$ instead of $(a,b) \in \mathfrak{R}$ . If $A=B$ (the case of most common interest), then we say that $\mathfrak{R}$ is a relation on $A$ .

Thus, in the example of $\sim$ above, we may let $\sim$ be the set of ordered pairs of triangles in the Euclidean plane which are similar to each other. We could also define a relation $\leq$ on the power set of a set $S$ , so that $(A,B) \in \leq$ , or $A\leq B$ , if and only if $A$ and $B$ are subsets of $S$ and $A$ is a subset of $B$ . This is a common example of an order relation.

More generally, we say that a relation $\mathfrak{R}(x,y)$ is a mathematical sentence in which two letters, $x$ and $y$ , are of particular interest. This more general definition is useful because it admits relations whose "domain" is a class of sets too large to constitute a set. For instance, the relation $\mathfrak{R}(x,y)$ defined as $(x=y)$ applies to all sets, not just sets contained in some larger set.

Domain and Range

The domain of a binary relation $\mathfrak{R}$ over $A$ and $B$ , written $\text{Dom}(\mathfrak{R})$ , is defined to be the set $\{x \in A | (\exists y \in B)(x,y) \in \mathfrak{R}\}$ . It is thus the set of the first components of the ordered pairs in $\mathfrak{R}$ .

The range of a binary relation $\mathfrak{R}$ over $A$ and $B$ , written $\text{Ran}(\mathfrak{R})$ , is defined to be the set $\{y \in B | (\exists x \in A)(x,y) \in \mathfrak{R}\}$ . It is thus the set of the second components of the ordered pairs in $\mathfrak{R}$ .

Reflexivity, Symmetry and Transitivity

A binary relation $\mathfrak{R}$ over $A$ is defined to be reflexive if $(\forall a \in A)(a \mathfrak{R} a)$ .

A binary relation $\mathfrak{R}$ over $A$ is defined to be symmetric if $(\forall (a,b) \in A^2)((a \mathfrak{R} b) \rightarrow (b \mathfrak{R} a))$ .

A binary relation $\mathfrak{R}$ over $A$ is defined to be anti-symmetric if $(\forall (a,b) \in A^2)(((a \mathfrak{R} b) \wedge (b \mathfrak{R} a)) \rightarrow (a = b))$ .

A binary relation $\mathfrak{R}$ over $A$ is defined to be transitive if $(\forall (a,b,c) \in A^3)(((a \mathfrak{R} b) \wedge (b \mathfrak{R} c)) \rightarrow (a \mathfrak{R} c))$ .

A reflexive, symmetric and transitive relation is called an equivalence relation. A reflexive, anti-symmetric and transitive relation is called an order relation.

Page

Toolbox

Search

Binary relation

Contents

Formal Definition and Notation

Domain and Range

Reflexivity, Symmetry and Transitivity

See also