Relation composition

In set theory, composition is an operation on relations.

Let R be a relation between X and Y and S a relation S between Y and Z. The composite relation R.S between X and Z is defined by

$x~{R\circ S}~z\Leftrightarrow \exists y\in Y,xRy{\mbox{ and }}ySz.\,$

If we equate a relation with its graph, then we may write

$R\circ S=\{(x,z)\in X\times Z:\exists y\in Y,~(x,y)\in R{\hbox{ and }}(y,z)\in S\}.\,$

Function composition may be regarded as relation composition on functional relations.