Types of Relations

Introduction to Relations

A relation R from a non-empty set A to a non-empty set B is a subset of the Cartesian product $A \times B$. If a relation is from a set A to itself, we call it a relation on A. An element 'a' is related to an element 'b' under the relation R if $(a, b) \in R$, which is written as $aRb$.

• Example: If $A = \{1, 2, 3\}$, a relation R on A can be defined as $R = \{(a, b) : a - b = 1\}$. Here, $R = \{(2, 1), (3, 2)\}$.

-Domain: The set of all first elements of the ordered pairs in a relation R. Domain $\subseteq A$.

-Range: The set of all second elements of the ordered pairs in a relation R. Range $\subseteq B$.

Types of Relations

1. Empty Relation

A relation R on a set A is an empty relation if no element of A is related to any other element of A. It is the empty set, $\emptyset$, which is a subset of $A \times A$.

• Example: Let A be the set of all students in a boys' school. Let the relation R on A be defined as $R = \{(a, b) : a \text{ is the sister of } b\}$. Since no student can be a sister of another student in a boys' school, $R = \emptyset$.

2. Universal Relation

A relation R on a set A is a universal relation if each element of A is related to every element of A. It is the entire Cartesian product, $R = A \times A$.

• Example: Let $A = \{1, 2, 3\}$. Let R be defined as $R = \{(a, b) : |a - b| \ge 0\}$. Since the absolute difference between any two numbers in A is always greater than or equal to zero, R contains all possible ordered pairs. Thus, $R = A \times A$.

Core Types of Relations

For a relation R on a set A:

1. Reflexive Relation

A relation R is reflexive if every element of A is related to itself.

$$\text{For every } a \in A, (a, a) \in R.$$

• Example: The relation 'is less than or equal to' ($\le$) on the set of integers is reflexive since $a \le a$ is always true.
• Non-Example: The relation 'is the father of' on a set of people is not reflexive as no person is their own father.

2. Symmetric Relation

A relation R is symmetric if whenever 'a' is related to 'b', then 'b' is also related to 'a'.

$$\text{If } (a, b) \in R, \text{ then } (b, a) \in R.$$

• Example: The relation 'is a cousin of' is symmetric. If A is B's cousin, B is A's cousin.
• Non-Example: The relation 'is greater than' ($>$) is not symmetric. If $5 > 3$, it does not imply $3 > 5$.

3. Transitive Relation

A relation R is transitive if whenever 'a' is related to 'b' and 'b' is related to 'c', then 'a' is also related to 'c'.

$$\text{If } (a, b) \in R \text{ and } (b, c) \in R, \text{ then } (a, c) \in R.$$

• Example: The relation 'is an ancestor of' is transitive. If A is an ancestor of B, and B is an ancestor of C, then A is an ancestor of C.
• Non-Example: The relation 'is the mother of' is not transitive. If A is the mother of B, and B is the mother of C, then A is the grandmother of C, not the mother.

Equivalence Relation

A relation R on a set A is an equivalence relation if it is reflexive, symmetric, and transitive.

• Example: Let T be the set of all triangles. The relation R defined as 'is similar to' is an equivalence relation.

  • Reflexive: Every triangle is similar to itself.
  • Symmetric: If $\triangle_1$ is similar to $\triangle_2$, then $\triangle_2$ is similar to $\triangle_1$.
  • Transitive: If $\triangle_1$ is similar to $\triangle_2$ and $\triangle_2$ is similar to $\triangle_3$, then $\triangle_1$ is similar to $\triangle_3$.

• Example: The relation 'is congruent to' on the set of all triangles is also an equivalence relation.

• Example: Let the relation R on the set of integers $\mathbb{Z}$ be defined by $aRb$ if $a-b$ is divisible by 3.

  • Reflexive: $a-a=0$, which is divisible by 3. So $(a,a) \in R$.
  • Symmetric: If $a-b$ is divisible by 3, then $a-b=3k$. So $b-a=-3k$, which is also divisible by 3. So $(b,a) \in R$.
  • Transitive: If $a-b=3k_1$ and $b-c=3k_2$, then adding them gives $(a-b)+(b-c)=3(k_1+k_2) \implies a-c=3(k_1+k_2)$, which is divisible by 3. So $(a,c) \in R$.
  • Since R is reflexive, symmetric, and transitive, it is an equivalence relation.

Example 1: Checking Properties for a Finite Set

Question: Let R be the relation in the set $A = \{1, 2, 3, 4\}$ given by $R = \{(1, 2), (2, 2), (1, 1), (4, 4), (1, 3), (3, 3), (3, 2)\}$. Check if R is reflexive, symmetric, or transitive.

Explanation:

Reflexivity: A relation is reflexive if $(a, a) \in R$ for every element $a \in A$.

• We must check for the pairs (1,1), (2,2), (3,3), and (4,4).
• Looking at the set R, we find that (1,1), (2,2), (3,3), and (4,4) are all present.
• Therefore, R is reflexive.

Symmetry: A relation is symmetric if for every $(a, b) \in R$, the pair $(b, a)$ must also be in R.

• Let's check the pair (1,2). We see that $(1,2) \in R$.
• For R to be symmetric, the pair (2,1) must also be in R.
• We check the set R and find that (2,1) is not in R.
• Therefore, R is not symmetric.

Transitivity: A relation is transitive if for every $(a, b) \in R$ and $(b, c) \in R$, the pair $(a, c)$ must also be in R.

• We need to look for 'chains' of elements. Let's check the pair $(1,3) \in R$ and $(3,2) \in R$.
• For transitivity, this requires the pair $(1,2)$ to be in R.
• We check the set R and find that (1,2) is in R.
• After checking all such possible chains (e.g., (1,1) and (1,2) implies (1,2) must be in R, which it is), we find no violations.
• Therefore, R is transitive.

Conclusion: R is reflexive and transitive, but not symmetric.

Example 2: Relation of Parallel Lines

Question: Show that the relation 'is parallel to' on the set L of all lines in a plane is an equivalence relation.

Explanation: An equivalence relation must be reflexive, symmetric, and transitive. Let R be the relation 'is parallel to' ($||$) on the set L of all lines.

Reflexivity:

• Condition: For any line $l \in L$, is $l R l$? (Is a line parallel to itself?)
• Check: Yes, by convention, every line is considered parallel to itself ($l || l$).
• Result: The relation is reflexive.

Symmetry:

• Condition: If $l_1 R l_2$, does that imply $l_2 R l_1$? (If $l_1 || l_2$, is $l_2 || l_1$?)
• Check: Yes, this is a fundamental property of parallel lines.
• Result: The relation is symmetric.

Transitivity:

• Condition: If $l_1 R l_2$ and $l_2 R l_3$, does that imply $l_1 R l_3$? (If $l_1 || l_2$ and $l_2 || l_3$, is $l_1 || l_3$?)
• Check: Yes, this is another fundamental property of parallel lines in Euclidean geometry.
• Result: The relation is transitive.

Conclusion: Since the relation is reflexive, symmetric, and transitive, it is an equivalence relation.

Example 3: Relation of Perpendicular Lines

Question: Show that the relation 'is perpendicular to' on the set L of all lines in a plane is symmetric but neither reflexive nor transitive.

Explanation: Let R be the relation 'is perpendicular to' ($\perp$) on the set L of all lines.

Reflexivity:

• Condition: For any line $l \in L$, is $l \perp l$? (Is a line perpendicular to itself?)
• Check: No. A line cannot be perpendicular to itself, as the angle between a line and itself is 0°, not 90°.
• Result: The relation is not reflexive.

Symmetry:

• Condition: If $l_1 \perp l_2$, is $l_2 \perp l_1$?
• Check: Yes. If the angle between line $l_1$ and $l_2$ is 90°, then the angle between $l_2$ and $l_1$ is also 90°.
• Result: The relation is symmetric.

Transitivity:

• Condition: If $l_1 \perp l_2$ and $l_2 \perp l_3$, is $l_1 \perp l_3$?
• Check: No. If line $l_1$ is perpendicular to $l_2$, and $l_2$ is perpendicular to $l_3$, then $l_1$ and $l_3$ must be parallel to each other (or be the same line). They are not perpendicular.
• Result: The relation is not transitive.

Conclusion: The relation is symmetric, but not reflexive or transitive.

Example 4: Relation on Integers (Divisibility)

Question: Let R be a relation on the set of integers $\mathbb{Z}$ defined by $aRb$ if $a-b$ is divisible by 5. Show that R is an equivalence relation.

Explanation: To be an equivalence relation, R must be reflexive, symmetric, and transitive.

Reflexivity:

• Condition: For any integer $a$, is $aRa$? (Is $a-a$ divisible by 5?)
• Check: $a-a = 0$. Since $0 = 5 \times 0$, 0 is divisible by 5.
• Result: The relation is reflexive.

Symmetry:

• Condition: If $aRb$, does that imply $bRa$?
• Check: Assume $aRb$ is true. This means $a-b$ is divisible by 5. So, we can write $a-b = 5k$ for some integer $k$. Multiplying by -1 gives $b-a = -5k = 5(-k)$. Since $-k$ is also an integer, $b-a$ is divisible by 5. This means $bRa$ is true.
• Result: The relation is symmetric.

Transitivity:

• Condition: If $aRb$ and $bRc$, does that imply $aRc$?
• Check: Assume $aRb$ and $bRc$ are true. This means $a-b = 5k_1$ and $b-c = 5k_2$ for some integers $k_1, k_2$. To check for $aRc$, we need to look at $a-c$. We can find this by adding the two equations: $(a-b) + (b-c) = 5k_1 + 5k_2$ $a-c = 5(k_1+k_2)$. Since $k_1+k_2$ is an integer, $a-c$ is divisible by 5. This means $aRc$ is true.
• Result: The relation is transitive.

Conclusion: Since R is reflexive, symmetric, and transitive, it is an equivalence relation.

Example 5: Inequality Relation

Question: Check the properties of the relation R defined by $aRb$ if $a \le b$ on the set of real numbers.

Explanation:

Reflexivity:

• Condition: For any real number $a$, is $a \le a$?
• Check: Yes, any number is equal to itself, which satisfies the 'less than or equal to' condition.
• Result: The relation is reflexive.

Symmetry:

• Condition: If $a \le b$, does that imply $b \le a$?
• Check: No. We can use a counterexample. Let $a=3$ and $b=5$. $3 \le 5$ is true, but $5 \le 3$ is false.
• Result: The relation is not symmetric.

Transitivity:

• Condition: If $a \le b$ and $b \le c$, does that imply $a \le c$?
• Check: Yes, this is a fundamental property of inequalities.
• Result: The relation is transitive.

Conclusion: The relation is reflexive and transitive, but not symmetric.

Example 6: Relation on a Power Set

Question: Let A be a set. Let R be the relation 'is a subset of' ($\subseteq$) on the power set P(A). Is R an equivalence relation?

Explanation: The power set P(A) is the set of all subsets of A. The relation R is $\subseteq$.

Reflexivity:

• Condition: For any set $X \in P(A)$, is $X \subseteq X$?
• Check: Yes, by definition, any set is a subset of itself.
• Result: The relation is reflexive.

Symmetry:

• Condition: If $X \subseteq Y$, does that imply $Y \subseteq X$?
• Check: No. This is only true if $X=Y$. For a counterexample, let $A = \{1, 2\}$. Let $X = \{1\}$ and $Y = \{1, 2\}$. Then $X \subseteq Y$ is true, but $Y \subseteq X$ is false.
• Result: The relation is not symmetric.

Transitivity:

• Condition: If $X \subseteq Y$ and $Y \subseteq Z$, does that imply $X \subseteq Z$?
• Check: Yes. If every element of X is in Y, and every element of Y is in Z, then it follows that every element of X must also be in Z.
• Result: The relation is transitive.

Conclusion: Since the relation is not symmetric, it is not an equivalence relation. It is, however, a partial ordering.

Example 7: Relation on Ordered Pairs

Question: Let R be a relation on $\mathbb{N} \times \mathbb{N}$ defined by $(a,b)R(c,d)$ if $a+d=b+c$. Prove R is an equivalence relation.

Explanation: The condition $a+d=b+c$ can be helpfully rearranged as $a-b = c-d$. This means two pairs are related if the difference between their components is the same.

Reflexivity:

• Condition: Is $(a,b)R(a,b)$?
• Check: This requires checking if $a+b = b+a$. This is true by the commutative property of addition.
• Result: R is reflexive.

Symmetry:

• Condition: If $(a,b)R(c,d)$, does that imply $(c,d)R(a,b)$?
• Check: Assume $(a,b)R(c,d)$. This means $a+d=b+c$. We want to check if $(c,d)R(a,b)$, which requires $c+b=d+a$. Since $a+d=b+c$ is the same equation as $c+b=d+a$, the implication is true.
• Result: R is symmetric.

Transitivity:

• Condition: If $(a,b)R(c,d)$ and $(c,d)R(e,f)$, does that imply $(a,b)R(e,f)$?
• Check: Assume the first two relations are true: 1) $a+d=b+c$ 2) $c+f=d+e$ We want to show that $a+f=b+e$. We can add the two assumed equations: $(a+d) + (c+f) = (b+c) + (d+e)$ $a+d+c+f = b+c+d+e$ Cancelling $d$ and $c$ from both sides gives $a+f=b+e$. This is the condition for $(a,b)R(e,f)$.
• Result: R is transitive.

Conclusion: Since R is reflexive, symmetric, and transitive, it is an equivalence relation.

Example 8: Counting Relations

Question: Let $A=\{1,2\}$. How many symmetric relations can be defined on A?

Explanation: 1. Understand the Building Blocks: A relation on A is any subset of the Cartesian product $A \times A$. Here, $A \times A = \{(1,1), (1,2), (2,1), (2,2)\}$.

2. Analyze the Condition of Symmetry: For a relation R to be symmetric, for any pair $(a,b)$, if $(a,b) \in R$, then $(b,a)$ must also be in R.

• Diagonal Elements: Pairs like (1,1) and (2,2) are their own reverse. Their presence or absence does not affect the symmetry property. We can choose to include (1,1) or not (2 options). We can choose to include (2,2) or not (2 options).
• Off-Diagonal Elements: Pairs like (1,2) and (2,1) are reverses of each other. For symmetry, we cannot choose one without the other. They must be treated as a single unit. We can either include the pair {(1,2), (2,1)} in our relation, or we can exclude it (2 options).

3. Count the Choices: We have three independent choices to make to build a symmetric relation:

1. To include the element (1,1) or not? (2 choices)
2. To include the element (2,2) or not? (2 choices)
3. To include the set of elements {(1,2), (2,1)} or not? (2 choices)

4. Calculate the Total: By the multiplication principle, the total number of possible symmetric relations is: Total = $2 \times 2 \times 2 = 2^3 = 8$.

Answer: There are 8 possible symmetric relations.

Example 9: A Non-Transitive Relation

Question: Let R be a relation on $\mathbb{R}$ defined by $xRy$ if $|x-y| \le 1$. Show that R is reflexive and symmetric but not transitive.

Explanation:

Reflexivity:

• Check: For any real number $x$, is $|x-x| \le 1$? Yes, $|0| \le 1$ is true.
• Result: R is reflexive.

Symmetry:

• Check: If $|x-y| \le 1$, is $|y-x| \le 1$? Yes, because $|y-x| = |-(x-y)| = |x-y|$. If one is less than or equal to 1, so is the other.
• Result: R is symmetric.

Transitivity:

• Condition: If $xRy$ and $yRz$, does it always imply $xRz$?
• Check with a Counterexample: We need to find three numbers $x, y, z$ such that the distance from $x$ to $y$ is small, and the distance from $y$ to $z$ is small, but the distance from $x$ to $z$ is large. Let's choose: $x=1$, $y=1.8$, and $z=2.6$.
  • Check $xRy$: $|x-y| = |1 - 1.8| = |-0.8| = 0.8$. Since $0.8 \le 1$, $(x,y) \in R$.
  • Check $yRz$: $|y-z| = |1.8 - 2.6| = |-0.8| = 0.8$. Since $0.8 \le 1$, $(y,z) \in R$.
  • Check $xRz$: $|x-z| = |1 - 2.6| = |-1.6| = 1.6$. Since $1.6$ is not $\le 1$, $(x,z) \notin R$.
• Result: We found a case where $xRy$ and $yRz$ are true, but $xRz$ is false. Therefore, R is not transitive.

Conclusion: The relation is reflexive and symmetric, but not transitive.

Example 10: Finding Smallest Equivalence Relation

Question: Let $A=\{1,2,3\}$. Find the smallest equivalence relation on A containing the element (1,2).

Explanation: An equivalence relation must be reflexive, symmetric, and transitive. We start with the given element and add the minimum number of other elements needed to satisfy these three properties.

1. Start: We are given that the relation R must contain (1,2).

2. Satisfy Reflexivity: For R to be reflexive on A={1,2,3}, it must contain all pairs of the form (a,a). We must add: (1,1), (2,2), (3,3). Our relation so far: $R = \{(1,1), (2,2), (3,3), (1,2)\}$.

3. Satisfy Symmetry: For every (a,b) in R, we must have (b,a). We currently have (1,2), so we must add its reverse: (2,1). Our relation so far: $R = \{(1,1), (2,2), (3,3), (1,2), (2,1)\}$.

4. Satisfy Transitivity: We must check if any chains $(a,b)$ and $(b,c)$ require a new element $(a,c)$.

   • We have (1,2) and (2,1). This implies we need (1,1). It's already in our set. ✅
   • We have (2,1) and (1,2). This implies we need (2,2). It's also already in our set. ✅ All other chains, like (1,1) and (1,2), also lead to elements that are already present. No new elements are needed to satisfy transitivity.

5. Final Smallest Relation: The smallest set that contains (1,2) and satisfies all three properties is the combination of all the elements we've gathered.

Answer: The smallest equivalence relation is $R = \{(1,1), (2,2), (3,3), (1,2), (2,1)\}$.