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.

Leave a Reply

Your email address will not be published. Required fields are marked *