Introduction to Relation
Domain and Range
Null Relation and Universal Relation
A relation in two sets may be defined as the collection (set) of ordered pairs. A relation R (denoted by R) from a non-empty set \(A\) to another non-empty set \(B\) is nothing but the subset of the cartesian product \(A×B\). A relation \( R: A\rightarrow B \) is mathematically defined as \( R\)={\((a,b): aRb, a\in A, b\in B\)}, i.e., the set of first components of the ordered pairs belong to first set and they are called the domain of the relation. The set of second components of the ordered pairs belong to second set and they are called the range of the relation.
A relation basically tells us how two sets are related to each other. \(( aRb)\) here stands for 'a is related to b'
Let us now get it with an example, suppose we have two sets as,
\(A\) = {Virat Kohli, Christiano Ronaldo, Sania Mirza}
and \(B\)= {cricket, football, wimbledon}.
Now, if we find the cartesian product of the two sets, then
\(A×B\) = {(Virat Kohli, cricket), (Virat Kohli, football), (Virat Kohli, wimbledon), (Ronaldo, cricket), (Christiano Ronaldo, football), (Christiano Ronaldo, wimbledon), (Sania Mirza, cricket), (Sania Mirza, football), (Sania Mirza, wimbledon)}
Now, if we define a relation \(R: A\rightarrow B\) between the two sets where \(aRb\) if \('a ~plays~ b' \) then
\(R\) = {(Virat Kohli, cricket),(Christiano Ronaldo, football), (Sania Mirza, wimbledon)}; which is undoubtedly a subset of \(A×B\), that's why we say \(R\subset A\times B \). But for usual case, we should better use \(\ R\subseteq A\times B \) because sometimes a relation becomes exactly equal to the cartesian products of its sets. Let us move ahead with another example, for two sets A = {Sourav Ganguly, MS Dhoni, Virat Kohli} and B = {India}, we get
\(P×Q\) = {(Sourav Ganguly, India), (MS Dhoni, India), (Virat Kohli, India)}
and now if we define a relation \(\ pRq = p \) was a cricket team captain of \(\ q \), then
R = {(Sourav Ganguly, India), (MS Dhoni, India), (Virat Kohli, India)} ; which is exactly equal to the cartesian product of the two sets P and Q, i.e., \(\ R=P×Q \), such a relation is called Universal Relation. It is the largest relation of all.
Now do you remember null set [Click here], a set containing no element was termed as a null set. So don't you think that there may be a relation too which does not contain any ordered pair? If you do, you're right. There is a type of relation which is empty, i.e., \(\ R = \phi \) and is therefore termed as Null Relation or Empty Relation.
Null relation is the smallest relation of all the relations. If \(\ R=\phi \) is a null relation then either of the domain or the range of the relation is a null set.
Example: if A = {1, 2, 3, 4} and
R = {\(\ (a, b): |a-b|≥ 100, a, b \in A\)}
i.e., no such two elements exist in the set A of which difference is 100 or more than 100.
Representation of Relation
Let us consider two sets A= {2, 3, 4, 5} and B = {3, 6, 7, 10}, and a relation \(R:aRb\) can be represented in various ways as follows-1. Set builder method or Rule method
R = {\(\ (x, y): x \) completely divides \(\ y \) where \(\ x \in A \) and \(\ y \in B\)}
2. Tabuler method or Roster method
R = {(2, 6), (2, 10), (3, 3), (3, 6), (5, 10)}
3. Graphical method
In this method, we plot all the ordered pairs in cartesian co-ordinate plane and each ordered pair gives us a point.
In this method, we connect all the elements of the domain to their corresponding ranges according to the relation with the help of arrows.
In this method, element from domain is connected to an element which is belonging to the range.
In this method, for all the ordered pairs existing in the relation we assign 1 and otherwise 0. so, the set of ordered pairs for which we get 1, constitutes the relation. Note that number of 1 in the table must be equal to the number of elements in the relation \(R\).
| \( \ \downarrow{x}|{y}\rightarrow \) | 3 | 6 | 7 | 10 |
|---|---|---|---|---|
| 2 | 0 | 1 | 0 | 1 |
| 3 | 1 | 1 | 0 | 0 |
| 4 | 0 | 0 | 0 | 0 |
| 5 | 0 | 0 | 0 | 1 |
Types of Relation
Inverse relation: If \(aRb\) is a relation then another relation \(bSa\) is called the inverse of the relation \(R\) if \(S\) = {\((b, a): (a, b) \in R\)}. In this case, \(S\) is denoted by \(R^{-1}\).
Here, \(\ d(R)= r(R^{-1}) \) and \(\ r(R)= d(R^{-1}) \)
Example: if \(R\) = {(1, 2), (3, 4), (5, 6), (7, 8)}, then
\(R^{-1}\)= {(2, 1), (4, 3), (6, 5), (8, 7)}
Identity relation: If \(A\) is a set, then a relation on \(A\) is called the identity relation if every element of \(A\) is related to itself, i.e., \(aRa\) = {\((a, a): ~for ~all~ a\in A\)}. Identity relation is usually denoted by \(I_A\) or simply by \(I\). In identity relation, \(d(R) = r(R)\).
Example: if \(A\) = {a, b, c, d} then
\(I\) = {(a, a), (b, b), (c, c), (d, d)}
Constant relation: A relation \(R:A\rightarrow B\) is said to be constant relation if all the elements of the domain are related to only one element of B. Here, range of the relation is a singleton set.
Example: Let, \(A\) = {\(x: x \in N, x< 11\)}
= {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
And a relation \(xRy\) is defined as follows,
\(R\) = {\((x, y): x = 2n + 1 \in A, y =1\)}
= {(1, 1), (3, 1), (5, 1), (7, 1), (9, 1)}
Here, \(d(R)\) = {1, 3, 5, 7, 9} and \(r(R)\) = {1},
We can see that the range of the relation is a singleton set and all the elements of the domain are related to the element of the range set.
Equality of relations: Two relations \(R\) and \(S\) are said to be equal if \(d(R) = d(S)\) and \(R(x)=S(x)\) for all \(x\in d\) (domain).
Binary Relations and their types
For a non-empty set A = {1,2,3}, any subset of A×A is called Binary relation on the set A itself. It is because, all the elements of A in such case is related to the some elements which are again belonging to the set A.
Reflexive relation
Let A be a set and \(aRa\) is a relation, then R is called a reflexive relation if \((a, a) \in R\) for all \(a \in A\). In other words, R is reflexive if we have \(aRa\) for all \(a \in A\). Here, R is not reflexive if there is at least one element \(a \in A\), such that \((a, a)\notin R\).
Example:
Let \(A\) ={1,2,3}, and a relation \(R\) defined on \(A\) is such that
\(R\) = {(1,1), (2,2), (3,3), (3,2), (2,1)}
Now the relation \(R\) is said to be reflexive, because
\(\ (1,1)\in R, (2,2)\in R, (3,3)\in R \)
Every identity relation on a non-empty set is a reflexive relation but the converse is not true.
Explanation:
Let us consider an identity relation on the set \(A\) = {1,2,3} is such that
\(I\) = {(1,1), (2,2), (3,3)}
Here, \(\ (1,1)\in I, (2,2)\in I, (3,3)\in I \)
⸫ \(I\) is reflexive.
Now, let us take a reflexive relation \(R\) defined on the set \(A\) is such that
\(R\) = {(1,1), (2,2), (3,3), (3,2), (2,1)}
Here, \(\ (3,2), (2,1)\in R \)
This is why the relation \(R\) is not an identity relation.
In an identity relation all the elements of the set are supposed to be related to themselves only and nothing other than that should be existed. In the other hand, in a reflexive relation all the elements of the set are supposed to be related to themselves and existance of anything else doesn't restrict the relation to be a reflexive relation.
Symmetric relation
Let \(R\) be a relation on set \(A\), then \(R\) is said to be a symmetric relation if \((a, b) \in R ⇒ (b, a) \in R\). In a symmetric relation \(bRa\) whenever we have \(aRb\) for \(a, b \in A\).
Example:
Let \(A\) ={1,2,3}, and a relation \(R\) defined on \(A\) is such that
\(R\) = {(1,2), (2,2), (2,3), (3,2), (2,1)}
Now the relation \(R\) is said to be symmetric, because
for \(\ (1,2)\in R \exists (2,1)\in R \)
for \(\ (2,2)\in R \exists (2,2)\in R \)
for \(\ (2,3)\in R \exists (3,2)\in R \)
Transitive relation
Let \(R\) be a relation on a set \(A\), then \(R\) is said to be a transitive relation on \(A\), if \(\ (a, b) \in R\) and \(\ (b, c) \in R ⇒ (a, c) \in R\) for \(\ (a, b, c) \in A\). Thus, in a transitive relation \(R\) on \(A\), if \(aRb\) and \(bRc\) then \(aRc\) for \(a, b, c \in A\).
Example:
Let \(A\) ={1,2}, and a relation \(R\) defined on \(A\) is such that
\(R\) = {(1, 1), (1, 2), (2, 1), (2, 2)}
Now the relation \(R\) is said to be transitive, because
for \(\ (1,1)\in R \) and \(\ (1,2)\in R \exists (1,2)\in R \)
for \(\ (1,2)\in R \) and \(\ (2,1)\in R \exists (1,1)\in R \)
for \(\ (2,1)\in R \) and \(\ (2,2)\in R \exists (2,2)\in R \)
Let us take another example
Let A = {1, 2, 3}, then identity relation R on A is such that
R = {(1, 1),(2, 2), (3,3)} is also transitive, because
for \(\ (1,1)\in R \nexists (1,a)\in R \forall a\in A\)
for \(\ (2,2)\in R \nexists (2,a)\in R \forall a\in A\)
for \(\ (3,3)\in R \nexists (3,a)\in R \forall a\in A\)
Anti-symmetric relation
Let \(R\) be a relation on a set \(A\), then \(R\) is said to be an anti-symmetric relation if \(\ (a, b) \in R\) and \(\ (b, a) \in R ⇒ a = b\). In other words, if \(a ≠ b\) then possibly \(a\) is related to \(b\) or possibly \(b\) is related to a\(\), but never both.
Example:
Let \(A\) ={1,2}, and a relation \(R\) defined on \(A\) is such that
\(R\) = {(1, 2)}
Now the relation \(R\) is said to be anti-symmetric, because
for \(\ (1,2)\in R \) and \(\ (2,1)\in R ⇒ 1\neq 2 \)
Equivalence relation
A relation \(R\) on a set \(A\) is said to be an equivalence relation on \(A\), iff \(R\) is simultaneously
- reflexive, i.e., \(\ (a, a) \in R\) for all \(a \in A\)
- symmetric, i.e., \(\ (a, b) \in R ⇒ (b, a) \in R\) for all \(a, b \in A\)
- transitive, i.e., \(\ (a, b) \in R\) and \(\ (b, c) \in R ⇒ (a, c) \in R\) for all \(a, b, c \in A\)
Let \(A\) = {a, b, c}, and a relation \(R\) defined on \(A\) is such that
\(R\) = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)}
Now the relation \(R\) is said to be an equivalence relation, because
since \(\ (a,a), (b,b), (c,c)\in R \)
⸫ \(R\) is reflexive.
Now, for \(\ (a, b)\in R \exists (b,a)\in R \)
for \(\ (b,c)\in R \exists (c,b)\in R \)
for \(\ (a, c)\in R \exists (c,a)\in R \)
⸫ \(R\) is symmetric.
Again, for \(\ (a,b)\in R \) and \(\ (b,a)\in R \exists (a,a)\in R \)
for \(\ (b,c)\in R \) and \(\ (c,a)\in R \exists (b,a)\in R \)
for \(\ (a,c)\in R \) and \(\ (c,a)\in R \exists (a,a)\in R \)
⸫ \(R \) is transitive.
Symbols used:
\( \exists \) → there exists
\( \nexists \) → there does not exist
\( \forall \) → for all
N.B.:
We've taken same examples repeatedly for simplicity which gives us the ability to focus more on core concepts.
Post a Comment