Binary Relation

Let P and Q be two non- empty sets. A binary relation R is defined to be a subset of P x Q from a set P to Q. If (a, b) ∈ R and R ⊆ P x Q then a is related to b by R i.e., aRb. If sets P and Q are equal, then we say R ⊆ P x P is a relation on P e.g.

1. (i) Let A = {a, b, c}  
2.       B = {r, s, t}  
3. Then R = {(a, r), (b, r), (b, t), (c, s)}  
4. is a relation from A to B.  
5.   
6. (ii) Let A = {1, 2, 3} and B = A  
7.          R = {(1, 1), (2, 2), (3, 3)}  
8. is a relation (equal) on A.  

Example1: If a set has n elements, how many relations are there from A to A.

Solution: If a set A has n elements, A x A has n² elements. So, there are 2ⁿ² relations from A to A.

Example2: If A has m elements and B has n elements. How many relations are there from A to B and vice versa?

Solution: There are m x n elements; hence there are 2^{m x n} relations from A to A.

Example3: If a set A = {1, 2}. Determine all relations from A to A.

Solution: There are 2²= 4 elements i.e., {(1, 2), (2, 1), (1, 1), (2, 2)} in A x A. So, there are 2⁴= 16 relations from A to A. i.e.

1.      {(1, 2), (2, 1), (1, 1), (2, 2)}, {(1, 2), (2, 1)}, {(1, 2), (1, 1)}, {(1, 2), (2, 2)},  
2. {(2, 1), (1, 1)},{(2,1), (2, 2)}, {(1, 1),(2, 2)},{(1, 2), (2, 1), (1, 1)}, {(1, 2), (1, 1),  
3. (2, 2)}, {(2,1), (1, 1), (2, 2)}, {(1, 2), (2, 1), (2, 2)}, {(1, 2), (2, 1), (1, 1), (2, 2)} and ∅.  

Domain and Range of Relation

Domain of Relation: The Domain of relation R is the set of elements in P which are related to some elements in Q, or it is the set of all first entries of the ordered pairs in R. It is denoted by DOM (R).

Range of Relation: The range of relation R is the set of elements in Q which are related to some element in P, or it is the set of all second entries of the ordered pairs in R. It is denoted by RAN (R).

Example:

1. Let A = {1, 2, 3, 4}  
2.     B = {a, b, c, d}  
3.     R = {(1, a), (1, b), (1, c), (2, b), (2, c), (2, d)}.  

Solution:

DOM (R) = {1, 2}
RAN (R) = {a, b, c, d}

Complement of a Relation

Consider a relation R from a set A to set B. The complement of relation R denoted by R is a relation from A to B such that

  R = {(a, b): {a, b) ∉ R}.

Example:

1. Consider the relation R from X to Y  
2.         X = {1, 2, 3}  
3.         Y = {8, 9}  
4.         R = {(1, 8) (2, 8) (1, 9) (3, 9)}  
5. Find the complement relation of R.  

Solution:

X x Y = {(1, 8), (2, 8), (3, 8), (1, 9), (2, 9), (3, 9)}
 Now we find the complement relation  R from X x Y
   R = {(3, 8), (2, 9)}