Relations and Types of Relations

Introduction to Relations

In mathematics, a relation is a fundamental concept that describes a connection or association between elements of two sets, or between elements of the same set. Formally, a relation from a set A to a set B is a subset of the Cartesian product A × B. If A and B are the same set, then the relation is said to be a relation on A.

Let A and B be two non-empty sets. The Cartesian product A × B is the set of all ordered pairs (a, b) where a ∈ A and b ∈ B. A relation R from A to B is a subset of A × B. We write 'a R b' if the ordered pair (a, b) belongs to the relation R, and 'a ⧸ R b' if (a, b) does not belong to R.

If R is a relation from A to A, it is called a relation on A. In this case, R is a subset of A × A. The elements of the ordered pairs are from the same set A.

Example: Let A = {1, 2, 3} and B = {a, b}. The Cartesian product A × B = {(1, a), (1, b), (2, a), (2, b), (3, a), (3, b)}. A relation R from A to B could be R = {(1, a), (2, b)}. This means that element 1 from set A is related to element 'a' from set B, and element 2 from set A is related to element 'b' from set B.

Domain and Codomain of a Relation

For a relation R from a set A to a set B: The domain of R is the set of all first elements of the ordered pairs in R. It is a subset of A. Domain(R) = {a ∈ A | ∃b ∈ B such that (a, b) ∈ R}

The codomain of R is the set B itself.

The range of R is the set of all second elements of the ordered pairs in R. It is a subset of B. Range(R) = {b ∈ B | ∃a ∈ A such that (a, b) ∈ R}

It's important to note that Domain(R) ⊆ A, Codomain(R) = B, and Range(R) ⊆ B. Also, Range(R) ⊆ Codomain(R).

Example: Let A = {1, 2, 3, 4} and B = {a, b, c}. Let R be a relation from A to B defined as R = {(1, a), (2, b), (3, a), (4, c)}. Domain(R) = {1, 2, 3, 4} Codomain(R) = {a, b, c} Range(R) = {a, b, c}

Consider another relation S from A to B: S = {(1, a), (2, a)}. Domain(S) = {1, 2} Codomain(S) = {a, b, c} Range(S) = {a}

Types of Relations

When we consider relations on a set A (i.e., subsets of A × A), we can classify them into several important types based on their properties. These properties are reflexivity, symmetry, and transitivity. A relation can possess one, two, all three, or none of these properties.

1. Reflexive Relation

A relation R on a set A is called reflexive if every element of A is related to itself. In terms of ordered pairs, this means that for every element 'a' in A, the pair (a, a) must be in R.

Formally, a relation R on a set A is reflexive if (a, a) ∈ R for all a ∈ A.

Example 1: Let A = {1, 2, 3}. Consider the relation R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)}. Since (1, 1), (2, 2), and (3, 3) are all in R, the relation R is reflexive on A.

Example 2: Let A = {1, 2, 3}. Consider the relation S = {(1, 1), (2, 2), (1, 2)}. This relation is NOT reflexive on A because the element 3 ∈ A is not related to itself, i.e., (3, 3) ∉ S.

Example 3: Let A be the set of all people in a room. Let R be the relation "is a sibling of". This relation is not reflexive because a person is not a sibling of themselves.

Example 4: Let A be the set of all people in a room. Let R be the relation "is married to". This relation is not reflexive because a person cannot be married to themselves (in most contexts). However, if the set A was defined as "individuals" and the relation was "is the same person as", then it would be reflexive.

Example 5: Let A = {1, 2, 3}. Consider the relation R = {(a, b) | a, b ∈ A and a ≤ b}. R = {(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)}. This relation is reflexive because for every a ∈ A, a ≤ a is true.

2. Symmetric Relation

A relation R on a set A is called symmetric if whenever an element 'a' is related to an element 'b', then 'b' must also be related to 'a'.

Formally, a relation R on a set A is symmetric if for every a, b ∈ A, if (a, b) ∈ R, then (b, a) ∈ R.

Example 1: Let A = {1, 2, 3}. Consider the relation R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)}. We check the condition: (1, 1) ∈ R ⇒ (1, 1) ∈ R (True) (2, 2) ∈ R ⇒ (2, 2) ∈ R (True) (3, 3) ∈ R ⇒ (3, 3) ∈ R (True) (1, 2) ∈ R ⇒ (2, 1) ∈ R (True) (2, 1) ∈ R ⇒ (1, 2) ∈ R (True) All conditions hold, so R is symmetric.

Example 2: Let A = {1, 2, 3}. Consider the relation S = {(1, 1), (2, 2), (1, 2)}. Check: (1, 1) ∈ S ⇒ (1, 1) ∈ S (True) (2, 2) ∈ S ⇒ (2, 2) ∈ S (True) (1, 2) ∈ S ⇒ (2, 1) ∈ S. But (2, 1) ∉ S. Since the condition fails for (1, 2), S is NOT symmetric.

Example 3: Let A be the set of all people. Let R be the relation "is a friend of". This relation is symmetric because if person X is a friend of person Y, then person Y is also a friend of person X.

Example 4: Let A be the set of all people. Let R be the relation "is married to". This is symmetric because if person X is married to person Y, then person Y is married to person X.

Example 5: Let A = {1, 2, 3}. Consider the relation R = {(a, b) | a, b ∈ A and a ≤ b}. R = {(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)}. Check: (1, 2) ∈ R, but (2, 1) ∉ R. (1, 3) ∈ R, but (3, 1) ∉ R. (2, 3) ∈ R, but (3, 2) ∉ R. This relation is NOT symmetric.

3. Transitive Relation

A relation R on a set A is called transitive if whenever an element 'a' is related to an element 'b', and 'b' is related to an element 'c', then 'a' must also be related to 'c'.

Formally, a relation R on a set A is transitive if for every a, b, c ∈ A, if (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R.

Example 1: Let A = {1, 2, 3}. Consider the relation R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1), (1, 3), (3, 1)}. We need to check all combinations: If (a, b) ∈ R and (b, c) ∈ R, does (a, c) ∈ R? - (1, 2) ∈ R and (2, 1) ∈ R ⇒ (1, 1) ∈ R (True) - (1, 2) ∈ R and (2, 2) ∈ R ⇒ (1, 2) ∈ R (True) - (2, 1) ∈ R and (1, 2) ∈ R ⇒ (2, 2) ∈ R (True) - (2, 1) ∈ R and (1, 1) ∈ R ⇒ (2, 1) ∈ R (True) - (1, 3) ∈ R and (3, 1) ∈ R ⇒ (1, 1) ∈ R (True) - (3, 1) ∈ R and (1, 3) ∈ R ⇒ (3, 3) ∈ R (True) - (1, 3) ∈ R and (3, 3) ∈ R ⇒ (1, 3) ∈ R (True) - (3, 1) ∈ R and (1, 1) ∈ R ⇒ (3, 1) ∈ R (True) - Pairs involving only reflexive elements like (1,1), (2,2), (3,3) will also hold trivially. For example, (1,1) ∈ R and (1,2) ∈ R ⇒ (1,2) ∈ R. This relation R is transitive.

Example 2: Let A = {1, 2, 3}. Consider the relation S = {(1, 1), (2, 2), (1, 2)}. Check: (1, 1) ∈ S and (1, 2) ∈ S ⇒ (1, 2) ∈ S (True) (1, 1) ∈ S and (1, 1) ∈ S ⇒ (1, 1) ∈ S (True) (2, 2) ∈ S and (2, 2) ∈ S ⇒ (2, 2) ∈ S (True) Are there any other combinations? No. S is transitive.

Example 3: Let A = {1, 2, 3}. Consider the relation T = {(1, 2), (2, 3)}. Check: (1, 2) ∈ T and (2, 3) ∈ T ⇒ (1, 3) ∈ T. But (1, 3) ∉ T. So, T is NOT transitive.

Example 4: Let A be the set of all people. Let R be the relation "is an ancestor of". This relation is transitive because if X is an ancestor of Y, and Y is an ancestor of Z, then X is an ancestor of Z.

Example 5: Let A = {1, 2, 3}. Consider the relation R = {(a, b) | a, b ∈ A and a ≤ b}. R = {(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)}. Check: If (a, b) ∈ R and (b, c) ∈ R, then a ≤ b and b ≤ c. By the property of inequality, a ≤ c. This means (a, c) ∈ R. Thus, the relation R is transitive.

4. Anti-symmetric Relation

A relation R on a set A is called anti-symmetric if whenever 'a' is related to 'b' and 'b' is related to 'a', it must be the case that 'a' and 'b' are the same element.

Formally, a relation R on a set A is anti-symmetric if for every a, b ∈ A, if (a, b) ∈ R and (b, a) ∈ R, then a = b.

Note: This is different from "not symmetric". A relation can be neither symmetric nor anti-symmetric, or it can be one but not the other. An element can be related to itself, i.e., (a, a) ∈ R is allowed and does not violate anti-symmetry because if a=b, then a=b is true.

Example 1: Let A = {1, 2, 3}. Consider the relation R = {(1, 1), (2, 2), (3, 3), (1, 2)}. Check: - (1, 1) ∈ R and (1, 1) ∈ R ⇒ 1 = 1 (True) - (2, 2) ∈ R and (2, 2) ∈ R ⇒ 2 = 2 (True) - (3, 3) ∈ R and (3, 3) ∈ R ⇒ 3 = 3 (True) - (1, 2) ∈ R. Is (2, 1) ∈ R? No. So this condition doesn't apply. The relation R is anti-symmetric.

Example 2: Let A = {1, 2, 3}. Consider the relation S = {(1, 1), (2, 2), (1, 2), (2, 1)}. Check: - (1, 1) ∈ S and (1, 1) ∈ S ⇒ 1 = 1 (True) - (2, 2) ∈ S and (2, 2) ∈ S ⇒ 2 = 2 (True) - (1, 2) ∈ S and (2, 1) ∈ S. Here, a=1, b=2. We have (a, b) ∈ S and (b, a) ∈ S. For S to be anti-symmetric, we must have a = b, i.e., 1 = 2. This is false. So, S is NOT anti-symmetric. (Note: S is symmetric).

Example 3: Let A = {1, 2, 3}. Consider the relation R = {(a, b) | a, b ∈ A and a ≤ b}. R = {(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)}. Check: If (a, b) ∈ R and (b, a) ∈ R, then a ≤ b and b ≤ a. The only way for both inequalities to be true is if a = b. Thus, R is anti-symmetric.

Example 4: Let A = {1, 2, 3}. Consider the relation T = {(1, 2)}. Check: Is there any pair (a, b) ∈ T and (b, a) ∈ T where a ≠ b? No. So, T is anti-symmetric.

5. Universal Relation

A relation R on a set A is called the universal relation if R = A × A. This means every element of A is related to every element of A.

Example: Let A = {1, 2}. The universal relation on A is R = A × A = {(1, 1), (1, 2), (2, 1), (2, 2)}.

Properties of Universal Relation: - It is always reflexive: (a, a) ∈ A × A for all a ∈ A. - It is always symmetric: If (a, b) ∈ A × A, then (b, a) ∈ A × A. - It is always transitive: If (a, b) ∈ A × A and (b, c) ∈ A × A, then (a, c) ∈ A × A. - It is NOT anti-symmetric (unless A has 0 or 1 element): If A has more than one element, say a ≠ b, then (a, b) ∈ A × A and (b, a) ∈ A × A, but a ≠ b.

6. Empty Relation (or Void Relation)

A relation R on a set A is called the empty relation if R = ∅ (the empty set). This means no element of A is related to any element of A.

Example: Let A = {1, 2}. The empty relation on A is R = ∅.

Properties of Empty Relation: - It is always reflexive IF AND ONLY IF the set A is empty. If A is non-empty, then R cannot contain (a, a) for any a ∈ A, so it's not reflexive. - It is always symmetric: The condition "if (a, b) ∈ ∅, then (b, a) ∈ ∅" is vacuously true because the premise (a, b) ∈ ∅ is always false. - It is always transitive: The condition "if (a, b) ∈ ∅ and (b, c) ∈ ∅, then (a, c) ∈ ∅" is vacuously true. - It is always anti-symmetric: The condition "if (a, b) ∈ ∅ and (b, a) ∈ ∅, then a = b" is vacuously true.

Equivalence Relations

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

Equivalence relations are very important because they partition the set A into disjoint subsets called equivalence classes. All elements within an equivalence class are related to each other.

Example 1: Let A = {1, 2, 3}. Relation R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)}. - Reflexive: Yes, (1, 1), (2, 2), (3, 3) are in R. - Symmetric: Yes, (1, 2) is in R and (2, 1) is in R. - Transitive: - (1, 2) ∈ R and (2, 1) ∈ R ⇒ (1, 1) ∈ R (True) - (1, 2) ∈ R and (2, 2) ∈ R ⇒ (1, 2) ∈ R (True) - (2, 1) ∈ R and (1, 1) ∈ R ⇒ (2, 1) ∈ R (True) - (2, 1) ∈ R and (1, 2) ∈ R ⇒ (2, 2) ∈ R (True) All checks pass. R is transitive. Since R is reflexive, symmetric, and transitive, it is an equivalence relation.

Example 2: Let A be the set of all integers (ℤ). Define a relation R on A such that a R b if and only if a - b is an even number. - Reflexive: For any integer a, a - a = 0, which is even. So, (a, a) ∈ R for all a ∈ ℤ. R is reflexive. - Symmetric: If a R b, then a - b is even. This means a - b = 2k for some integer k. Then b - a = -(a - b) = -2k = 2(-k), which is also even. So, b R a. R is symmetric. - Transitive: If a R b and b R c, then a - b is even and b - c is even. So, a - b = 2k₁ and b - c = 2k₂ for integers k₁ and k₂. Then, a - c = (a - b) + (b - c) = 2k₁ + 2k₂ = 2(k₁ + k₂). Since k₁ + k₂ is an integer, a - c is even. So, a R c. R is transitive. Since R is reflexive, symmetric, and transitive, it is an equivalence relation. The equivalence classes are the set of even numbers and the set of odd numbers.

Partial Order Relations

A relation R on a set A is called a partial order relation (or simply a partial order) if it is reflexive, anti-symmetric, and transitive.

Sets with a partial order relation are called partially ordered sets, often denoted as (A, R).

Example 1: Let A = {1, 2, 3}. Consider the relation R = {(a, b) | a, b ∈ A and a ≤ b}. We already verified that R is reflexive, anti-symmetric, and transitive. Therefore, R is a partial order relation on A.

Example 2: Let A = {1, 2, 3}. Consider the relation S = {(1, 1), (2, 2), (3, 3), (1, 2)}. - Reflexive: Yes. - Anti-symmetric: Yes, as (2, 1) is not in S. - Transitive: Yes, as checked before. So, S is a partial order relation.

Example 3: Let A be the set of all subsets of a set X. Let R be the relation "⊆" (subset of). - Reflexive: Every set is a subset of itself (A ⊆ A). True. - Anti-symmetric: If A ⊆ B and B ⊆ A, then A = B. True. - Transitive: If A ⊆ B and B ⊆ C, then A ⊆ C. True. Thus, the subset relation is a partial order relation.

Example 4: Let A be the set of positive integers. Let R be the relation "divides" (denoted by |). So, a R b if a divides b. - Reflexive: For any positive integer a, a divides a. True. - Symmetric: If a divides b, does b divide a? Only if a = b. So, it's not generally symmetric. - Anti-symmetric: If a divides b and b divides a, then a = b. True for positive integers. - Transitive: If a divides b and b divides c, then a divides c. True. So, the divisibility relation is a partial order relation on the set of positive integers.

Summary Table of Relation Types

Let R be a relation on a set A.

Property	Condition	Example Relation	On Set
Reflexive	∀a ∈ A, (a,a) ∈ R	{(1,1), (2,2), (3,3)}	{1,2,3}
Symmetric	∀a,b ∈ A, if (a,b) ∈ R then (b,a) ∈ R	{(1,2), (2,1)}	{1,2}
Transitive	∀a,b,c ∈ A, if (a,b) ∈ R and (b,c) ∈ R then (a,c) ∈ R	{(1,2), (2,3), (1,3)}	{1,2,3}
Anti-symmetric	∀a,b ∈ A, if (a,b) ∈ R and (b,a) ∈ R then a = b	{(1,1), (1,2)}	{1,2}
Equivalence Relation	Reflexive, Symmetric, Transitive	{(1,1), (2,2), (1,2), (2,1)}	{1,2}
Partial Order Relation	Reflexive, Anti-symmetric, Transitive	{(1,1), (1,2), (2,2)}	{1,2}
Universal Relation	R = A × A	{(1,1), (1,2), (2,1), (2,2)}	{1,2}
Empty Relation	R = ∅	{}	{1,2}

Common Pitfalls and Tricks

When dealing with relations, especially for exams, pay close attention to the set on which the relation is defined. A relation might be reflexive on one set but not on another.

Trick for Transitivity: To prove a relation is NOT transitive, you only need to find ONE instance where (a, b) ∈ R and (b, c) ∈ R, but (a, c) ∉ R. To prove it IS transitive, you must check ALL possible combinations or use a general argument based on the definition of the relation.

Trick for Symmetry vs. Anti-symmetry: A relation can be symmetric and anti-symmetric simultaneously only if it consists solely of pairs (a, a) or is the empty relation on a set with at most one element. If a relation has (a, b) with a ≠ b and also (b, a), it cannot be anti-symmetric. If it has (a, b) with a ≠ b but NOT (b, a), it cannot be symmetric.

Trick for Equivalence Relations: Remember the three key properties: Reflexive, Symmetric, Transitive. Many problems involve proving a given relation is an equivalence relation or finding parameters that make it so.

Trick for Partial Orders: Remember the three key properties: Reflexive, Anti-symmetric, Transitive. These are crucial for understanding orderings in mathematics, like numerical order, subset inclusion, or divisibility.

Universal and Empty Relations: These are often used as edge cases or base cases in proofs. Always remember their properties, especially regarding reflexivity for the empty relation.