TOPICS

Miscellaneous

Relations and Functions

**Example-1 :-** If R₁ and R₂ are equivalence relations in a set A, show that R₁ ∩ R₂ is also an equivalence relation.

Since R₁ and R₂ are equivalence relations, (a, a) ∈ R₁, and (a, a) ∈ R₂ ∀a ∈ A. This implies that (a, a) ∈ R₁ ∩ R₂, ∀a, showing R₁ ∩ R₂ is reflexive. Further, (a, b) ∈ R₁ ∩ R₂ ⇒ (a, b) ∈ R₁ and (a, b) ∈ R₂ ⇒ (b, a) ∈ R₁ and (b, a) ∈ R₂ ⇒ (b, a) ∈ R₁ ∩ R₂, Hence, R₁ ∩ R₂ is symmetric. Similarly, (a, b) ∈ R₁ ∩ R₂ and (b, c) ∈ R₁ ∩ R₂ ⇒ (a, c) ∈ R₁ and (a, c) ∈ R₂ ⇒ (a, c) ∈ R₁ ∩ R₂. This shows that R₁ ∩ R₂ is transitive. Thus, R₁ ∩ R₂ is an equivalence relation.

**Example-2 :-** Let R be a relation on the set A of ordered pairs of positive integers defined by (x, y) R (u, v) if and only if xv = yu. Show that R is an equivalence relation.

Clearly, (x, y) R (x, y), ∀(x, y) ∈ A, since xy = yx. This shows that R is reflexive. Further, (x, y) R (u, v) ⇒ xv = yu ⇒ uy = vx and hence (u, v) R (x, y). This shows that R is symmetric. Similarly, (x, y) R (u, v) and (u, v) R (a, b) ⇒ xv = yu and ub = va ⇒ xv(a/u)= yu(a/u) = ⇒ xv(b/v)= yu(a/u) ⇒ xb = ya and Hence, (x, y) R (a, b). Thus, R is transitive. Thus, R is an equivalence relation.

**Example-3 :-** Let X = {1, 2, 3, 4, 5, 6, 7, 8, 9}. Let R₁ be a relation in X given by R₁ = {(x, y) : x – y is divisible by 3} and R₂ be another relation on X given by R₂ = {(x, y): {x, y} ⊂ {1, 4, 7}} or {x, y} ⊂ {2, 5, 8} or {x, y} ⊂ {3, 6, 9}}. Show that R₁ = R₂.

Sets {1, 4, 7}, {2, 5, 8} and {3, 6, 9} is that difference between any two elements of these sets is a multiple of 3. Therefore, (x, y) ∈ R₁ ⇒ x – y is a multiple of 3 ⇒ {x, y} ⊂ {1, 4, 7} or {x, y} ⊂ {2, 5, 8} or {x, y} ⊂ {3, 6, 9} ⇒ (x, y) ∈ R₂. Hence, R₁ ⊂ R₂. Similarly, {x, y} ∈ R₂ ⇒ {x, y} ⊂ {1, 4, 7} or {x, y} ⊂ {2, 5, 8} or {x, y} ⊂ {3, 6, 9} ⇒ x – y is divisible by 3 ⇒ {x, y} ∈ R₁. This shows that R₂ ⊂ R₁. Hence, R₁ = R₂.

**Example-4 :-** Let f : X → Y be a function. Define a relation R in X given by R = {(a, b): f(a) = f(b)}. Examine whether R is an equivalence relation or not.

For every a ∈ X, (a, a) ∈ R, since f(a) = f(a), showing that R is reflexive. Similarly, (a, b) ∈ R ⇒ f(a) = f(b) ⇒ f(b) = f(a) ⇒ (b, a) ∈ R. Therefore, R is symmetric. Further, (a, b) ∈ R and (b, c) ∈ R ⇒ f(a) = f(b) and f(b) = f(c) ⇒ f(a) = f(c) ⇒ (a, c) ∈ R, which implies that R is transitive. Hence, R is an equivalence relation.

**Example-5 :-** Determine which of the following binary operations on the set R are associative and which are commutative.

(a) a ∗ b = 1 ∀ a, b ∈ R, (b) a ∗ b = (a+b)/2 ∀ a, b ∈ R

(a) Clearly, by definition a ∗ b = b ∗ a = 1, ∀a, b ∈ R. Also (a ∗ b) ∗ c = (1 ∗ c) =1 and a ∗ (b ∗ c) = a ∗ (1) = 1, ∀ a, b, c ∈ R. Hence R is both associative and commutative. (b) a ∗ b = (a+b)/2 ∀ a, b ∈ R (a+b)/2 = (b+a)/2 = b ∗ a, shows that ∗ is commutative. Further, Hence, ∗ is not associative

**Example-6 :-** Find the number of all one-one functions from set A = {1, 2, 3} to itself.

One-one function from {1, 2, 3} to itself is simply a permutation on three symbols 1, 2, 3. Therefore, total number of one-one maps from {1, 2, 3} to itself is same as total number of permutations on three symbols 1, 2, 3 which is 3! = 6.

**Example-7 :-** Let A = {1, 2, 3}. Then show that the number of relations containing (1, 2) and (2, 3) which are reflexive and transitive but not symmetric is three.

The smallest relation R1 containing (1, 2) and (2, 3) which is reflexive and transitive but not symmetric is {(1, 1), (2, 2), (3, 3), (1, 2), (2, 3), (1, 3)}. Now, if we add the pair (2, 1) to R1 to get R2, then the relation R2 will be reflexive, transitive but not symmetric. Similarly, we can obtain R3 by adding (3, 2) to R1 to get the desired relation. However, we can not add two pairs (2, 1), (3, 2) or single pair (3, 1) to R1 at a time, as by doing so, we will be forced to add the remaining pair in order to maintain transitivity and in the process, the relation will become symmetric also which is not required. Thus, the total number of desired relations is three.

**Example-8 :-** Show that the number of equivalence relation in the set {1, 2, 3} containing (1, 2) and (2, 1) is two.

The smallest equivalence relation R1 containing (1, 2) and (2, 1) is {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)}. Now we are left with only 4 pairs namely (2, 3), (3, 2), (1, 3) and (3, 1). If we add any one, say (2, 3) to R1, then for symmetry we must add (3, 2) also and now for transitivity we are forced to add (1, 3) and (3, 1). Thus, the only equivalence relation bigger than R1 is the universal relation. This shows that the total number of equivalence relations containing (1, 2) and (2, 1) is two.

**Example-9 :-** Show that the number of binary operations on {1, 2} having 1 as identity and having 2 as the inverse of 2 is exactly one.

A binary operation ∗ on {1, 2} is a function from {1, 2} × {1, 2} to {1, 2}, i.e., a function from {(1, 1), (1, 2), (2, 1), (2, 2)} → {1, 2}. Since 1 is the identity for the desired binary operation ∗, ∗ (1, 1) = 1, ∗ (1, 2) = 2, ∗ (2, 1) = 2 and the only choice left is for the pair (2, 2). Since 2 is the inverse of 2, i.e., ∗ (2, 2) must be equal to 1. Thus, the number of desired binary operation is only one.

**Example-10 :-** Consider the identity function IN : N → N defined as IN (x) = x ∀x ∈ N. Show that although IN is onto but IN + IN : N → N defined as (IN + IN) (x) = IN (x) + IN (x) = x + x = 2x is not onto.

Clearly IN is onto. But IN + IN is not onto, as we can find an element 3 in the co-domain N such that there does not exist any x in the domain N with (IN + IN) (x) = 2x = 3.

**Example-11 :-** Consider a function f : [0, π/2] → R given by f(x) = sin x and g : [0, π/2] → R given by g(x) = cos x. Show that f and g are one-one, but f + g is not one-one.

Since for any two distinct elements x₁ and x₂ in [0, π/2], sin x₁ ≠ sin x₂ and cos x₁ ≠ cos x₂, both f and g must be one-one. But (f + g) (0) = sin 0 + cos 0 = 1 and (f + g)(π/2) = sin(π/2) + cos(π/2) = 1. Therefore, f + g is not one-one.

CLASSES