PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (200)
Orphanage
Unclass'd
Unproven (490)
Corrections (6)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very high Entry average rating: Very high
relation (Definition)

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

$\displaystyle 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
$\displaystyle 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,

$\displaystyle \operatorname{dom}(R):=\lbrace x\in A\mid (x,y)\in R$    for some $\displaystyle y \in B \rbrace$
and the range $ \operatorname{ran}(R)$ of $ R$ is the set of parts of pairs of $ R$ coming from $ B$:
$\displaystyle \operatorname{ran}(R):=\lbrace y\in B\mid (x,y)\in R$    for some $\displaystyle x\in A \rbrace.$

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). Notice that, unlike the previous definition, sets $ A$ and $ B$ are not specified in advance. The domain and range of a binary relation are defined in the same way as before. It is also possible to recover the previous definition in this setting: a binary relation from $ A$ to $ B$ is a binary relation whose domain is a subset of $ A$ and whose range is a subset of $ B$.
  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. In term rewriting theory, a binary relation on a set is sometimes called a reduction, and is written $ \to$. This is to signify that $ a\to b$ means that the element $ a$ is being “reduced” to $ b$ via $ \to$.

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

$\displaystyle 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

$\displaystyle 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
$\displaystyle 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
    $\displaystyle \chi_R:A\to \lbrace 0,1\rbrace,$
    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 $ \lbrace 0,1\rbrace$ (or truth/falsity).



"relation" is owned by CWoo. [ full author list (3) | owner history (2) ]
(view preamble)

View style:

See Also: poset, partial order, total order, ordering relation, function, well-founded relation, property, grounded relation

Also defines:  unary relation, binary relation, ternary relation, $n$-ary relation, domain, range, nullary relation
Keywords:  cartesian ordered pair

Attachments:
operations on relations (Definition) by CWoo
Log in to rate this entry.
(view current ratings)

Cross-references: unary, equivalent, iff, characteristic function, function, arity, section, finite, cardinality, indexed by, reduction, theory, term, class, set theory, integers, ordered pair, subset, collections, objects
There are 202 references to this entry.

This is version 23 of relation, born on 2001-10-06, modified 2008-05-08.
Object id is 122, canonical name is Relation.
Accessed 30989 times total.

Classification:
AMS MSC: 03E20 (Mathematical logic and foundations :: Set theory :: Other classical set theory )
 08A02 (General algebraic systems :: Algebraic structures :: Relational systems, laws of composition)
Pending Errata and Addenda
None.
[ View all 12 ]
Discussion
Style: Expand: Order:
forum policy
my addendum, formatting by antizeus on 2001-10-19 03:16:30
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.
[ reply | up ]
Interact
post | correct | update request | add derivation | add example | add (any)