Binary relation

From AoPSWiki

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.

Personal tools

Navigation

Search

Toolbox

Binary relation

From AoPSWiki

Contents

Formal Definition and Notation

Domain and Range

Reflexivity, Symmetry and Transitivity

See also