Discrete Mathematics Relations

Relations in Group Theory

Let A and B two non-empty sets. Then a relation R from A to B is a subset of A\times B containing the ordered pairs \left( a,b \right)\in A\times B such that some relation exists between a and b.
In other words, a relation R is merely a subset of A\times B.

If \left( a,b \right)\in R then we say that “a is R related to b” and is written as aRb.
If B = A then we say that R is a relation in A.

For example, let A = {2, 3, 5}, B = {4, 6, 9} then A\times B=\left\{ \left( 2,4 \right),\left( 2,6 \right),\left( 2,9 \right),\left( 3,4 \right),\left( 3,6 \right),\left( 3,9 \right),\left( 5,4 \right),\left( 5,6 \right),\left( 5,9 \right) \right\}. Let us define a relation R by R=\left\{ \left( a,b \right)\in A\times B:a\,\,divides\,\,b \right\}.
Then R=\left\{ \left( 2,4 \right),\left( 2,6 \right),\left( 3,6 \right),\left( 3,9 \right) \right\}

If another relation S is defined by S=\left\{ \left( a,b \right)\in A\times B:a\,\,and\,\,b\,\,are\,\,relatively\,\,prime \right\}. Then S=\left\{ \left( 2,9 \right),\left( 3,4 \right),\left( 5,4 \right),\left( 5,6 \right),\left( 5,9 \right) \right\}.

 

Domain and Range of a Relation

Let R be a relation from A to B. The domain of R is the set of all first coordinates of the ordered pairs of R and the range of R is the set of second coordinates of the pairs of R. That is

\[Domain\,\,of\,\,R=\left\{ a\in A:\left( a,b \right)\in R \right\}\]

\[Range\,\,of\,\,R=\left\{ b\in B:\left( a,b \right)\in R \right\}\]

Obviously, the domain of R is a subset of A and the range of R is a subset of B.
In the above example, Domain\,\,of\,\,R=\left\{ 2,3 \right\}and Range\,\,of\,\,R=\left\{ 4,6,9 \right\}.

 

Inverse of a Relation

Let R be a relation from a set A to a set B. The inverse relation of R denoted by R-1 is the relation from the set B to the set A defined by

\[{{R}^{-1}}=\left\{ \left( b,a \right):\left( a,b \right)\in R \right\}\]

In other words {{R}^{-1}} can be obtained by reversing the ordered pairs of R. Clearly {{R}^{-1}} is a subset of B\times A. For example, let A = {2, 3, 5}, B = {1, 4}. If R=\left\{ \left( a,b \right)\in A\times b:a>b \right\}=\left\{ \left( 2,1 \right),\left( 3,1 \right),\left( 5,1 \right),\left( 5,4 \right) \right\} then {{R}^{-1}}=\left\{ \left( 1,2 \right),\left( 1,3 \right),\left( 1,5 \right),\left( 4,5 \right) \right\}.

 

Reflexive Relation

A relation R in a set A is said to be reflexive if for every a\in A,\,\left( a,a \right)\in R. Thus R is reflexive if we have aRa for every a\in A.

Examples

1. Let L be the set of lines in the plane. Consider a relation R defined by

\[R=\left\{ \left( x,y \right):x\,\,is\,\,parallel\,\,to\,\,y \right\}\]

Since every line is parallel to itself, it follows that \left( x,x \right)\in R for every x\in L. Hence R is a reflexive relation.

2. Let N be the set of natural numbers. Relations xRy defined by

i) “x divides y” is reflexive since every natural number divides itself.

ii) “x = y” is reflexive since every number is equal to itself.

iii) “x – y is divisible by 5” is reflexive since x – x = 0 is divisible by 5 for every x\in N.

iv) “x < y” is not reflexive since for any a\in N,\,\,a<a is not true.

 

Symmetric Relation

A relation R in a set A is said to be symmetric if \left( a,b \right)\in R\Rightarrow \left( b,a \right)\in R. That is R is said to be symmetric if aRb\Rightarrow bRa.

Examples

1. Let A be the set of triangles in a plane. The relation in A defined by “α is similar to β” where \alpha ,\beta \in A is symmetric since if a triangle α is similar to β then β is similar to α.
Similarly, if L is a set of straight lines in a plane then a relation in L defined by “x is parallel to y” and “x is perpendicular to y” are symmetric.

2. Define relation R in N by

i) “x = y” is a symmetric relation since x = y implies y = x.

ii) “x – y is divisible by 5” is a symmetric relation since if x – y is divisible by 5 then y – x is also divisible by 5.

iii) “x < y” is not symmetric since x < y does not imply y < x.

 

Anti-symmetric Relation

A relation R in a set A is said to be anti-symmetric relation if \left( a,b \right)\in R,\left( b,a \right)\in R\Rightarrow a=b.
In other words if a ≠ b then either \left( a,b \right)\in R\,\,or\,\,\left( b,a \right)\in R and never both.

Examples

1. Let N be the set of natural numbers and let R be the relation in N defined by “x divides y”. Then R is anti-symmetric since a divides b and b divides a implies a = b.

2. Let A = {1, 2, 3, 4} and let R be a relation in A defined by R=\left\{ \left( 1,2 \right),\left( 2,1 \right),\left( 3,1 \right),\left( 4,2 \right),\left( 4,4 \right) \right\}. Then R is not an anti-symmetric relation in A since \left( 1,2 \right)\in R\,\,and\,\,\left( 2,1 \right)\in R\,\,but\,\,1\ne 2.

 

Transitive Relation

A relation R in a set A is said to be transitive if \left( a,b \right)\in R,\left( b,c \right)\in R\Rightarrow \left( a,c \right)\in R. That is R is said to be transitive if aRb\,\,and\,\,bRc\Rightarrow aRc.

Examples

1. If L is the set of all straight lines in a plane then a relation in L defined by “a is parallel to b” is transitive since if a, b, c are three straight lines in L then a is parallel to b and b is parallel to c implies a is parallel to c.

However a relation defined by “ a is perpendicular to b” is not transitive since a is perpendicular to b and b is perpendicular to c does not imply a is perpendicular to c, in fact a is parallel to c.

2. The relations in N defined by

i) “x = y” is transitive since x = y and y = z implies x = z.

ii) “x – y is divisible by 5” is transitive since if x – y divisible 5 and y – z is divisible by 5 implies (x – y) + (y – z) = x – z is divisible by 5.

iii) “x < y” is transitive since x < y and y < z implies x < z.

 

Equivalence Relation

A relation R in a set A is said to be an equivalence relation if
i) R is reflexive, that is, for every a\in A,\,\left( a,a \right)\in R,
ii) R is symmetric, that is,\left( a,b \right)\in R\Rightarrow \left( b,a \right)\in R,
iii) R is transitive, that is,\left( a,b \right)\in R,\left( b,c \right)\in R\Rightarrow \left( a,c \right)\in R.
In other words, a relation R in a set A is said to be an equivalence relation if it is reflexive, symmetric, and transitive.

Examples

1. If A is the set of triangles in a plane then the relation R defined by “a is similar to b” is an equivalence relation.
For, if a, b, c are any three triangles, then
(i) a is similar to itself
(ii) if a is similar to b then b is similar to a
(iii) if a is similar to b and b is similar to c then a is similar to c.

2. In the set L of all straight lines in a plane the relation defined by “a is parallel to b” is an equivalence relation. For, if a, b, c are any three straight lines then
(i) a is parallel to itself
(ii) if a is parallel to b then b is parallel to a
(iii) if a is parallel to b and b is parallel to c then a is parallel to c.
However the relation “a is perpendicular to b” is not an equivalence relation, since it is symmetric but not reflexive and transitive.

3. Let N be the set of natural numbers. The relations defined by

i) “x = y” is an equivalence relation.

ii) “x – y is divisible by 5” is an equivalence relation.

iii) “x < y” is not an equivalence relation since it is not reflexive and symmetric but is only transitive.

 

Partial Order Relation

A relation which is reflexive, anti-symmetric and transitive is called a partial order relation.

Partitions

Let S=A\cup B\cup C... where A, B, C are the non-empty subsets of the non-empty set S. A set P = {A, B, C, …} is said to be the partition of S if
(i) each x\in S\Rightarrow x belongs to an element of P and
(ii) any A and B \in S then A = B or A\cap B=\phi .

Example

The partition of S = {1, 2, 0, 5, 4} are {{1}, {2, 4}, {5, 0}, {1, 2}, {5}, {0, 4}} etc.

 Example 01

Give an example of relation which is reflexive but neither symmetric nor transitive.

Solution:

Let S be the set where S = {5, 6, 7} and R be a relation where R ={(5, 5), (5, 6), (6, 6), (6, 7), (7, 7)}.
Here the reflexive property holds since aRa holds for all a\in S as for example \left( 5,5 \right)\in R,\,where\,\,5\in R,\,\left( 6,6 \right)\in R,\,where\,\,6\in R,\,\left( 7,7 \right)\in R,\,where\,\,7\in R
Again, here \left( 5,6 \right)\in R\,\,but\,\left( 6,5 \right)\notin R, so the relation R is not symmetric.
Again here \left( 5,6 \right)\in R\,\,and\,\left( 6,7 \right)\in R\,\,but\,\,\left( 5,7 \right)\notin R. Therefore R is not transitive.
Hence R is not an equivalence relation.

 Example 02

Show that the relation ''\subseteq ''defined on P(S), the power set of S is partial order relation.

Solution:

Here R=\left\{ \left( A,B \right):A,B\in P,A\subseteq B \right\}
a) Since every set is a subset of itself, R is reflexive.
b) Since A\subseteq B\,\,and\,\,B\subseteq A\Rightarrow A=B, R is anti-symmetric.
c) Since A\subseteq B\,\,and\,\,B\subseteq C\Rightarrow A\subseteq C,R is transitive.
Therefore is a partial order relation.

<< Previous Topic
Set Theory
Next Topic >>
Functions

Leave a Comment

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

0

Scroll to Top