## You are here

Homerelation

## Primary tabs

# relation

# Binary Relations

Before describing what a *relation* is generally, let us define a more specific kind of a relation: a *binary relation*. Basically, a binary relation $R$ involves objects coming from two collections $A,B$, where the objects are paired up so that each pair consists of an object from $A$, and an object from $B$.

More formally, a *binary relation* is a subset $R$ of the Cartesian product of two sets $A$ and $B$. One may write

$a\>R\>b$ |

to indicate that the ordered pair $(a,b)$ is an element of $R$. A subset of $A\times A$ is simply called a binary relation on $A$. If $R$ is a binary relation on $A$, then we write

$a_{1}\>R\>a_{2}\>R\>a_{3}\>\cdots\>a_{{n-1}}\>R\>a_{n}$ |

to mean $a_{1}\>R\>a_{2},a_{2}\>R\>a_{3},\ldots,$ and $a_{{n-1}}\>R\>a_{n}$.

Given a binary relation $R\subseteq A\times B$, the *domain* $\operatorname{dom}(R)$ of $R$ is the set of elements in $A$ forming parts of the pairs in $R$. In other words,

$\operatorname{dom}(R):=\{x\in A\mid(x,y)\in R\mbox{ for some }y\in B\}$ |

and the *range* $\operatorname{ran}(R)$ of $R$ is the set of parts of pairs of $R$ coming from $B$:

$\operatorname{ran}(R):=\{y\in B\mid(x,y)\in R\mbox{ for some }x\in A\}.$ |

An example of a binary relation is the less-than relation on the integers, i.e., $<$ $\subseteq\mathbb{Z}\times\mathbb{Z}$. $(1,2)\in$ $<$, but $(2,1)\notin$ $<$.

Remarks.

1. In set theory, a binary relation is simply a set of ordered pairs (of sets or classes, depending on the axiom system used). Notice that, unlike the previous definition, sets (or classes) $A$ and $B$ are not specified in advance. Given a (binary) relation $R$, the domain of $R$ is the set (or class) of elements $a$ such that $aRb$ for some $b$, and the range of $R$ is the set (or class) or elements $b$ such that $aRb$ for some $a$. The union and the domain and the range of $R$ is called the

*field*of $R$.2. It may be possible to define a relation over a class. For example, if $\mathcal{C}$ is the class of all sets, then $\in$ can be thought of as a binary relation on $\mathcal{C}$.

3.

# Arbitrary Relations

From the definition of a binary relation, we can easily generalize it to that of an arbitrary relation. Since a binary relation involves two sets, an arbitrary relation involves an arbitrary collection of sets. More specifically, a *relation* $R$ is a subset of some Cartesian product of a collection of sets. In symbol, this is

$R\subseteq\prod_{{i\in I}}A_{i}$ |

where each $A_{i}$ is a set, indexed by some set $I$.

From this more general definition, we see that a binary relation is just a relation where $I$ has two elements. In addition, an *$n$-ary relation* is a relation where the cardinality of $I$ is $n$ ($n$ finite). In symbol, we have

$R\subseteq\prod_{{i=1}}^{n}A_{i}.$ |

It is not hard to see that any $n$-ary relation where $n>1$ can be viewed as a binary relation in $n-1$ different ways, for

$R\subseteq A_{1}\times A_{2}\times\cdots\times A_{n}=\prod_{{i=1}}^{j}A_{i}% \times\prod_{{i=j+1}}^{n}A_{i},$ |

where $j$ ranges from $1$ through $n-1$.

A common name for a $3$-ary relation is a *ternary relation*. It is also possible to have a *$1$-ary relation*, or commonly known as a *unary relation*, which is nothing but a subset of some set.

Remarks.

1. Following from the first remark from the previous section, relations of higher arity can be inductively defined: for $n>1$, an $(n+1)$-ary relation is a binary relation whose domain is an $n$-ary relation. In this setting, a “unary relation” and relations whose arity is of “arbitrary” cardinality are not defined.

2. A relation can also be viewed as a function (which itself is a relation). Let $R\subseteq A:=\prod_{{i\in I}}A_{i}$. As a subset of $A$, $R$ can be identified with the characteristic function

$\chi_{R}:A\to\{0,1\},$ where $\chi_{R}(x)=1$ iff $x\in R$ and $\chi_{R}(x)=0$ otherwise. Therefore, an $n$-ary relation is equivalent to an $(n+1)$-ary characteristic function. From this, one may say that a $0$-ary, or a

*nullary relation*is a unary characteristic function. In other words, a nullary relation is just a an element in $\{0,1\}$ (or truth/falsity).

## Mathematics Subject Classification

08A02*no label found*03E20

*no label found*82C35

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Comments

## my addendum, formatting

I meant to have my addendum in five paragraphs, but now it's all in one paragraph and looks like the frantic ravings of a madman.

## Re: my addendum, formatting

That is fixed, btw.

-apk

## Doubt

A binary relation could be seen as a binary characteristic function. I don't get why a binary relation could be represented as a ternary characteristic function.