Relations

A relation \( R \) from a non-empty set \( A \) to another non-empty set \( B \) is defined as a subset of the Cartesian product \( A \times B \). Formally,

\[ R \subseteq A \times B = \{(a,b) : a \in A, b \in B\} \]

Thus, any subset of \( A \times B \) is a relation from \( A \) to \( B \).

Note: If \( A \) and \( B \) are finite sets with \( p \) and \( q \) elements respectively, then \( n(A \times B) = pq \). The total number of relations from \( A \) to \( B \) is the number of subsets of \( A \times B \), which is \( 2^{pq} \).

Domain, Range and Co-domain of a Relation

Domain: The domain of a relation \( R \) from \( A \) to \( B \) is the set of all elements \( a \in A \) such that there exists \( b \in B \) with \( (a,b) \in R \). Formally,

\[ \text{Dom}(R) = \{ a \in A : \exists b \in B, (a,b) \in R \} \]

Range: The range of \( R \) is the set of all elements \( b \in B \) such that there exists \( a \in A \) with \( (a,b) \in R \). Formally,

\[ \text{Range}(R) = \{ b \in B : \exists a \in A, (a,b) \in R \} \]

Co-domain: The co-domain of \( R \) is the set \( B \) itself.

Types of Relations

• Empty Relation: \( R = \emptyset \).
• Universal Relation: \( R = A \times B \).
• Identity Relation: Defined on \( A \) as \( I_A = \{(a,a) : a \in A\} \).
• Reflexive Relation: \( R \) on \( A \) is reflexive if \( (a,a) \in R \) for all \( a \in A \).
• Symmetric Relation: \( R \) on \( A \) is symmetric if \( (a,b) \in R \Rightarrow (b,a) \in R \) for all \( a,b \in A \).
• Transitive Relation: \( R \) on \( A \) is transitive if \( (a,b) \in R \) and \( (b,c) \in R \) imply \( (a,c) \in R \) for all \( a,b,c \in A \).
• Equivalence Relation: A relation that is reflexive, symmetric, and transitive.

Worked Example 1

Let \( A = \{1,2,3,7\} \), \( B = \{3,6\} \), and define \( R = \{(a,b) : a < b\} \). Find domain, range, and co-domain.

Solution:

\( R = \{(1,3), (1,6), (2,3), (2,6), (3,6)\} \)

Domain: \( \{1,2,3\} \)

Range: \( \{3,6\} \)

Co-domain: \( B = \{3,6\} \)

Worked Example 2

Check if the relation \( R = \{(1,1),(2,2),(3,3),(1,2),(2,1),(1,3)\} \) on \( A = \{1,2,3\} \) is reflexive.

Solution:

Check if \( (a,a) \in R \) for all \( a \in A \):

\( (1,1), (2,2), (3,3) \in R \), so \( R \) is reflexive.

Practice Set

Level 1 – Easy

• Define the relation \( R \) on \( A = \{1,2\} \) and \( B = \{3,4\} \) as \( R = \{(1,3)\} \). Find domain, range, and co-domain.
• Is the empty relation on \( A = \{1,2,3\} \) reflexive?

Level 2 – Moderate

• Given \( A = \{1,2,3\} \), check if \( R = \{(1,2),(2,1),(2,3),(3,2)\} \) is symmetric.
• Show that the universal relation on \( A = \{1,2\} \) is reflexive.

Level 3 – Challenging

• Prove that the relation \( R = \{(a,b) : a-b \text{ is even}\} \) on integers is an equivalence relation.
• Given \( A = \{1,2,3\} \), \( R = \{(1,1),(2,2),(3,3),(1,2),(2,1),(1,3),(3,1),(2,3),(3,2)\} \), verify if \( R \) is transitive.

Answer Key

Level 1

• Domain: \( \{1\} \), Range: \( \{3\} \), Co-domain: \( \{3,4\} \)
• No, empty relation is not reflexive as \( (a,a) \notin R \) for all \( a \in A \).

Level 2

• Yes, \( R \) is symmetric because for every \( (a,b) \in R \), \( (b,a) \in R \).
• Universal relation contains all pairs including \( (a,a) \), so it is reflexive.

Level 3

• Reflexive: \( a-a=0 \) even, Symmetric: if \( a-b \) even, then \( b-a \) even, Transitive: sum of even numbers is even. Hence equivalence relation.
• Check transitivity: For all \( (a,b), (b,c) \in R \), \( (a,c) \in R \) holds. Hence \( R \) is transitive.

Quick Reference

Glossary

• Relation: A subset of \( A \times B \).
• Domain: Set of first elements in relation pairs.
• Range: Set of second elements in relation pairs.
• Co-domain: The set \( B \) in relation \( R \subseteq A \times B \).
• Reflexive: Every element relates to itself.
• Symmetric: Relation is bidirectional.
• Transitive: Relation passes through intermediate elements.
• Equivalence Relation: Relation that is reflexive, symmetric, and transitive.

Functions

A function \( f \) from a set \( A \) to a set \( B \) is a special type of relation where each element of \( A \) is related to exactly one element of \( B \). Formally, \( f \subseteq A \times B \) such that for every \( x \in A \), there exists a unique \( y \in B \) with \( (x,y) \in f \). The element \( y \) is called the image of \( x \) under \( f \), denoted \( f(x) \).

Difference Between Relation and Function

Real Valued Function of a Real Variable

If the domain and range of \( f \) are subsets of real numbers \( \mathbb{R} \), then \( f \) is called a real valued function of a real variable.

Common Real Functions

Types of Functions

• One-one (Injective) Function: \( f: A \to B \) is injective if \( f(a) = f(b) \Rightarrow a = b \) for all \( a,b \in A \).
• Onto (Surjective) Function: \( f: A \to B \) is surjective if for every \( b \in B \), there exists \( a \in A \) such that \( f(a) = b \).
• Bijective Function: A function that is both injective and surjective.
• Identity Function: \( I_A: A \to A \) defined by \( I_A(x) = x \) for all \( x \in A \).
• Equal Functions: Two functions \( f \) and \( g \) are equal if \( f(x) = g(x) \) for all \( x \) in their domain.

Algorithms to Check Injectivity and Surjectivity

Injectivity

1. Take arbitrary \( a,b \in A \).
2. Assume \( f(a) = f(b) \).
3. Solve for \( a = b \). If true for all \( a,b \), \( f \) is injective.

Surjectivity

1. Take arbitrary \( b \in B \).
2. Solve \( f(x) = b \) for \( x \).
3. If solution \( x \in A \) exists for all \( b \), \( f \) is surjective.

Worked Example 1

Show that \( f: A \to B \) defined by \( f(x) = 4x + 7 \) is one-one.

Solution:

Assume \( f(x_1) = f(x_2) \), then

\[ 4x_1 + 7 = 4x_2 + 7 \]

\[ 4x_1 = 4x_2 \]

\[ x_1 = x_2 \]

Hence, \( f \) is injective.

Worked Example 2

Show that \( f: \mathbb{N} \to \mathbb{N} \) defined by \( f(1) = f(2) = 1 \) and \( f(x) = x - 1 \) for \( x > 2 \) is onto but not one-one.

Solution:

Since \( f(1) = f(2) = 1 \), \( f \) is not injective.

For any \( y \in \mathbb{N} \), \( y \neq 1 \), choose \( x = y + 1 \), then \( f(x) = y \). Also \( f(1) = 1 \). Hence, \( f \) is onto.

Practice Set

Level 1 – Easy

• Define a function \( f: \{1,2,3\} \to \{4,5\} \) and find its domain, co-domain, and range.
• Is the function \( f(x) = 2x + 3 \) injective?

Level 2 – Moderate

• Check if \( f(x) = x^2 \) from \( \mathbb{R} \to \mathbb{R} \) is onto.
• Show that the function \( f(x) = \sin x \) is not one-one.

Level 3 – Challenging

• Prove that the function \( f: \mathbb{R} \to \mathbb{R} \) defined by \( f(x) = 3x + 2 \) is bijective.
• Find the inverse of the function \( f(x) = \frac{2x - 1}{3} \) and verify it is bijective.

Answer Key

Level 1

• Domain: \( \{1,2,3\} \), Co-domain: \( \{4,5\} \), Range depends on function definition.
• Yes, \( f(x) = 2x + 3 \) is injective.

Level 2

• \( f(x) = x^2 \) is not onto \( \mathbb{R} \) because negative numbers are not in range.
• \( f(x) = \sin x \) is not one-one as \( \sin x = \sin (\pi - x) \).

Level 3

• \( f(x) = 3x + 2 \) is bijective because it is both injective and surjective.
• Inverse: \( f^{-1}(y) = \frac{3y + 1}{2} \). Verified by composition.

Quick Reference

Glossary

• Function: Relation with unique image for each element in domain.
• Domain: Set of inputs.
• Co-domain: Set of possible outputs.
• Range: Actual set of outputs.
• Injective: One-to-one mapping.
• Surjective: Onto mapping.
• Bijective: Both injective and surjective.
• Inverse Function: Function reversing \( f \).