# Binary relation

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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.