# Relation

DEFINITION1: Let $X$ and $Y$ be two sets. Any subset of the cartesian product $X\times{Y}$ is called a relation with domain $X$ and codomain $Y$. While some sources are giving the definition of relation, they assume $X,Y\ne{\varnothing}$ and it’s said the emptyset being a subset of $X\times{Y}$ isn’t a relation. However, the assumption “the emptyset is a relation” is not a problem for any branch of the mathematics. On the contrary, the assumption “the emptyset is a relation” plays an important role in some branch of the mathematics.

If $X$ and $Y$ are two sets with $n$ and $m$ elements respectively, then the cartesian product $X\times{Y}$ has $n.m$ elements. Since a relation with domain $X$ and codomain $Y$ is an element of the power set $\mathbf{P}(X\times Y)$ and the number of the elements of the power set of a set with $k$ elements is $2^{k}$, then the number of all the relations with domain $X$ and codomain $Y$ is $2^{n.m}$. If $X,Y\ne{\varnothing}$ and at least one of $X$ and $Y$ is infinite set, then the number of all the relations with domain $X$ and codomain $Y$ is also infinity.

Let $R\subset{X\times{Y}}$ be a relation not being the emptyset. The statement $(x,y)\in{R}$ is read “x is R-related to y” and is denoted by $xRy$ or $R(x)=y$.

EXAMPLE1: Let $X=\{a,b,c\}$ and $Y=\{1,2\}$. Since $X$ has 3 elements and $Y$ has 2 elements, the number of all the relations with domain $X$ and codomain $Y$ is $2^{2.3}=2^{6}=64$. We can give some of these $64$ relations:

$R_1=\varnothing$,

$R_2=\{(a,1)\}$,

$R_3=\{(b,1),(b,2),(c,2)\}$,

$R_4=X\times{Y}$.

EXAMPLE2: Let $X=Y=\mathbb{R}$ and $R=\{(x,y)\in{\mathbb{R}\times\mathbb{R}}\:|\:x^2=y^2\}$. Since $(-1)^2=1^2$, then $(-1,1)\in{R}$. Let’s show all the elements of this relation on the cartesian coordinate plane:

DEFINITION2: Let $X$, $Y$ be two sets and $R\subset{X\times{Y}}$. The relation defined as

$R^{-1}=\{(y,x)\:|\:(x,y)\in{R}\}\subset{Y\times X}$

is called the inverse or converse relation of $R$. If $R=\varnothing$, then the inverse of $R$ is defined by $R^{-1}=\varnothing$.

EXAMPLE3: Find the inverses of the relations in Example1:

$R_1^{-1}=\varnothing$,

$R_2^{-1}=\{(1,a)\}$,

$R_3^{-1}=\{(1,b),(2,b),(2,c)\}$,

$R_4^{-1}=Y\times{X}$.

DEFINITION3: Let $X,Y,Z$ be three sets and $R\subset{X\times{Y}}$, $S\subset{Y\times{Z}}$ be two relations. The relation defined as

$S\circ R=\{(x,z)\:|\:\exists y\in{Y}: (x,y)\in{R}\land (y,z)\in{S}\}\subset{X\times{Z}}$

is called the composition of the relations $R$ and $S$.

EXAMPLE4: $X=\{a,b,c\}$, $Y=\{1,2,3\}$, $Z=\{x,y,z\}$, $R_1=\{(a,1),(a,2),(b,3)\}$, $R_2=\{(b,2),(b,3)\}$, $S_1=\{(1,x),(1,z)\}$ and $S_2=\{(2,z),(3,x)\}$. Hence:

$S_1\circ{R_1}=\{(a,x),(a,z)\}$,

$S_2\circ{R_1}=\{(a,z),(b,x)\}$,

$S_1\circ{R_2}=\varnothing$,

$S_2\circ{R_2}=\{(b,z),(b,x)\}$.

DEFINITION4: Let $X$ be a set and $R\subset{X\times{X}}$. (Note that the domain and the codomain of the relation $R$ are equal. The following definitions can be given for the relations over a set $X$. It can’t be given for the relations between two difference sets)

a) If $xRx$ for all $x\in{X}$, then the relation $R$ is called “reflexive”.

b) If it holds “$xRy\Rightarrow{yRx}$” for $x,y\in{X}$, then the relation $R$ is called “symmetric”.

c) If it holds “$xRy\land{yRx}\Rightarrow{x=y}$” for $x,y\in{X}$, then the relation $R$ is called “antisymmetric”.

d) If it holds “$xRy\land{yRz}\Rightarrow{xRz}$” for $x,y,z\in{X}$, then the relation $R$ is called “transitive”.

DEFINITION5: Let $X$ be a set and $R\subset{X\times{X}}$. If the relation $R$ is reflexive, antisymmetric and transitive, then the relation $R$ is called a "partial order relation" and denoted by $R=\le$ in general. If "$\le$" is a partial order relation over a set $X$, then $(X,\le)$ is called "partially ordered set" or shortly "poset".

DEFINITION6: Let $X$ be a set and $R\subset{X\times{X}}$. If the relation $R$ is reflexive, symmetric and transitive, then the relation $R$ is called an "equivalence relation" and denoted by $R=\sim$ in general.