Relation

On September 18, 2010, in Analysis, by ufukkaya

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=\emptyset$ ,

$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}=\emptyset$ ,

$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.

Academic Maths

Relation

Related Posts:

Leave a Reply Cancel reply

Recent Posts

Categories

Blogroll

Academic Maths

Pages

Stay In Touch

More