Relation

Definition

$\mathcal{R}=(X,Y,P(x,y))$ where $P$ is a Propositional Function

A relation over sets $X,Y$ is a new set of ordered pairs $(x,y)$ consisting of $x\in X$ and $y\in Y$.

Solution Set of Relation

$\{(x,y)|x\in X,y\in Y,P(x,y)=\text{true}\}$

A set of ordered pairs for which the result of a Propositional Function is true.

Let $\mathcal{R}:X\to Y$ Domain of $\mathcal{R}$: $\mathrm{Dom}(\mathcal{R})=X$ Codomain of $\mathcal{R}$: $\mathrm{Cod}(\mathcal{R})=Y$ Image of $\mathcal{R}$: $\mathrm{Im}(\mathcal{R})=\{y\in Y|\exists x\in X,x\mathcal{R}y\}$

Operations

Converse

${\mathcal{R}}^{-1}=\{(y,x)|(x,y)\in \mathcal{R}\}$

Composition

Let $\mathcal{R}$ be a relation over sets $X,Y$ and $\mathcal{S}$ be a relation over sets $Y,Z$ $\mathcal{S}\circ \mathcal{R}=\{(x,z)|\exists y\in Y,(x,y)\in \mathcal{R}\wedge (y,z)\in \mathcal{S}\}$

Properties

• Reflectivity
• Symmetricity
• Antisymmetricity
• Transitivity

Classes

• Equivalence Relation
• Partial Order Relation

Facts

$\mathcal{R}\subset A\times B$ A relation is a subset of Cartesian Product

$(F^{-1}{)}^{-1}=F$

$(H\circ G)\circ F=H\circ (G\circ F)$

$(G\circ F{)}^{-1}=F^{-1}\circ G^{-1}$