PlanetMath: operations on relations

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (232)
Orphanage
Unclass'd
Unproven (519)
Corrections (22)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

operations on relations

(Definition)

Recall that an -ary relation () is a subset of a product of some sets. In this definition, any -ary relation for which is automatically an -ary relation, and consequently a binary relation. On the other hand, a unary, or -ary relation, being the subset of some set , can be viewed as a binary relation (either realized as $B\times B$ or $\Delta_B:=\lbrace (b,b)\mid b\in B\rbrace$ ) on . Hence, we shall concentrate our discussion on the most important kind of relations, the binary relations, in this entry.

Compositions, Inverses, and Complements

Let $\rho \subseteq A\times B$ and $\sigma \subseteq B\times C$ be two binary relations. We define the composition of $\rho$ and $\sigma$ , the inverse (or converse) and the complement of $\rho$ by

$\rho\circ\sigma := \lbrace (a,c)\mid (a,b)\in \rho$ and $(b,c)\in \sigma$ for some $b\in B\rbrace$ ,
$\rho^{-1}:=\lbrace (b,a)\mid (a,b)\in \rho\rbrace$ , and
$\rho':=\lbrace (a,b)\mid (a,b)\notin \rho\rbrace$ .

$\rho\circ\sigma,\rho^{-1}$ and $\rho'$ are binary relations of $A\times C, B\times A$ and $A\times B$ respectively.

Remarks. Suppose $\rho,\sigma,\tau$ are binary relations of $A\times B,B\times C,C\times D$ respectively.

Associativity of relational compositions: $(\rho\circ\sigma)\circ \tau =\rho\circ (\sigma\circ\tau)$ .
$(\rho\circ\sigma)^{-1}=\sigma^{-1}\circ\rho^{-1}$ .
For the rest of the remarks, we assume . Define the power of $\rho$ recursively by $\rho^1=\rho$ , and $\rho^{n+1}=\rho\circ\rho^n$ . By 1 above, $\rho^{n+m}=\rho^n\circ\rho^m$ for $m,n\in \mathbb{N}$ .
$\rho^{-n}$ may be also be defined, in terms of $\rho^{-1}$ for .
However, $\rho^{n+m}\ne\rho^n\circ\rho^m$ for all integers, since $\rho^{-1}\circ\rho\neq \rho\circ\rho^{-1}$ in general.
Nevertheless, we may define $\Delta:=\lbrace (a,a)\mid a\in A\rbrace$ . This is called the identity or diagonal relation on . It has the property that $\Delta\circ \rho=\rho\circ\Delta=\rho$ . For this, we may define, for every relation $\rho$ on , $\rho^0:=\Delta$ .
Let $\mathcal{R}$ be the set of all binary relations on a set . Then $(\mathcal{R},\circ)$ is a monoid with $\Delta$ as the identity element.
(Special relations) Let $\rho$ be a binary relation on a set :
- $\rho$ is reflexive if $\Delta\subseteq\rho$ ;
- $\rho$ is symmetric if $\rho=\rho^{-1}$ ;
- $\rho$ is anti-symmetric if $\rho\cap\rho^{-1}\subseteq \Delta$ ;
- $\rho$ is transitive if $\rho\circ\rho \subseteq \rho$ ;
- $\rho$ is a pre-order if it is reflexive and transitive
- $\rho$ is a partial order if it is a pre-order and is anti-symmetric
- $\rho$ is an equivalence if it is a pre-order and is symmetric
Of these, only reflexivity is preserved by $\circ$ and both symmetry and anti-symmetry are preserved by the inverse operation.

Other Operations

Some operations on binary relations yield unary relations. The most common ones are the following:

Given a binary relation $\rho\in A\times B$ , and an elements $a\in A$ and $b\in B$ , define

$\displaystyle \rho(a,\cdot):=\lbrace y\mid (a,y)\in \rho\rbrace$ and $\displaystyle \quad \rho(\cdot,b):=\lbrace x\mid (x,b)\in \rho\rbrace.$

$\rho(a,\cdot)\subseteq B$ is called the section of $\rho$ in based at , and $\rho(\cdot,b)\subseteq A$ is the section of $\rho$ in (based) at . When the base points are not mentioned, we simply say a section of $\rho$ in or , or an -section or a -section of $\rho$ .

Finally, we define the domain and range of a binary relation $\rho\subseteq A\times B$ , to be

$\operatorname{dom}(\rho):=\lbrace a\mid (a,b)\in \rho$ for some $b\in B\rbrace$ , and
$\operatorname{ran}(\rho):=\lbrace b\mid (a,b)\in \rho$ for some $a\in A\rbrace.$

respectively. When $\rho$ is a function, the domain and range of $\rho$ coincide with the domain of range of $\rho$ as a function.

Remarks. Given a binary relation $\rho\subseteq A\times B$ .

$\rho(a,\cdot)$ , realized as a binary relation $\lbrace a\rbrace \times \rho(a,\cdot)$ can be viewed as the composition of $\Delta_a\circ \rho$ , where $\Delta_a=\lbrace (a,a)\rbrace$ . Similarly, $\rho\circ \Delta_b=\rho(\cdot,b) \times \lbrace b\rbrace$ .
$\operatorname{dom}(\rho)$ is the disjoint union of -sections of $\rho$ and $\operatorname{ran}(\rho)$ is the disjoint union of -sections of $\rho$ .
$\operatorname{dom}(\rho^{-1})=\operatorname{ran}(\rho)$ and $\operatorname{ran}(\rho^{-1})=\operatorname{dom}(\rho)$ .
$\rho\circ\rho^{-1}=\operatorname{dom}(\rho)\times \operatorname{dom}(\rho)$ and $\rho^{-1}\circ\rho=\operatorname{ran}(\rho)\times \operatorname{ran}(\rho)$ .
If , then $\operatorname{dom}(\rho)\times A=\rho\circ A^2$ and $\operatorname{ran}(\rho) = A^2\circ \rho$ .

"operations on relations" is owned by CWoo.

(view preamble | get metadata)

Other names:

inverse relation, relation composition, converse of a relation, diagonal relation

Also defines:

power of a relation, relational composition, inverse of a relation, section, domain, range, identity relation

This object's parent.

Log in to rate this entry.
(view current ratings)

Cross-references: disjoint union, function, base points, unary relations, operation, symmetry, reflexivity, equivalence, partial order, pre-order, transitive, anti-symmetric, symmetric, Reflexive, identity element, property, integers, terms, associativity, unary, binary relation, product, subset, relation
There are 96 references to this entry.

This is version 10 of operations on relations, born on 2006-12-04, modified 2008-02-15.
Object id is 8600, canonical name is OperationsOnRelations.
Accessed 7691 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.

Discussion

forum policy

No messages.

Interact