Relations and Functions

Relation

A relation from a set A to a set B is a subset of the Cartesian product \(A \times B\).

\[ R \subseteq A \times B \]

If \((a, b) \in R\), then we say that a is related to b and we write \(a \, R \, b\).

Example:

Let \(A = \{1, 2\}\) and \(B = \{3, 4\}\).

\[ A \times B = \{(1,3), (1,4), (2,3), (2,4)\} \]

A relation R may be:

\[ R = \{(1,3), (2,4)\} \]

A relation in a set A is a subset of \(A \times A\).

Number of Relations from Set A to Set B

Let |A| = m and |B| = n.

The number of elements in the Cartesian product is:

\[ |A \times B| = m \times n \]

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

The number of subsets of a set having k elements is \(2^k\).

Therefore, the number of relations from A to B is:

\[ 2^{mn} \]

Special Case:

The number of relations in a set A is:

\[ 2^{m^2} \]

Example:

If |A| = 2 and |B| = 3, then the number of relations is:

\[ 2^{2 \times 3} = 2^6 = 64 \]

Domain of a Relation

Let R be a relation from a set A to a set B.

The domain of the relation R is the set of all first elements of the ordered pairs in R.

That is,

\[ \text{Domain of } R = \{ a \in A \mid (a, b) \in R \text{ for some } b \in B \} \]

Example:

If \(R = \{(1,2), (3,4), (5,6)\}\), then

Domain of R = \(\{1, 3, 5\}\)

Range of a Relation

The range of the relation R is the set of all second elements of the ordered pairs in R.

That is,

\[ \text{Range of } R = \{ b \in B \mid (a, b) \in R \text{ for some } a \in A \} \]

Example:

If \(R = \{(1,2), (3,4), (5,6)\}\), then

Range of R = \(\{2, 4, 6\}\)

Types of Relations

Let R be a relation defined on a set A.

1. Reflexive Relation

A relation R on a set A is said to be reflexive if every element of A is related to itself.

That is,

\[ (a, a) \in R \quad \text{for all } a \in A \]

Example:
If A = \({1, 2, 3}\), then \(\{(1,1), (2,2), (3,3)\}\) is a reflexive relation.

2. Symmetric Relation

A relation R on a set A is said to be symmetric if whenever a is related to b, then b is also related to a.

That is,

\[ (a, b) \in R \Rightarrow (b, a) \in R \]

Example:
If \((2,3) \in R\), then \((3,2) \in R\). Hence the relation is symmetric.

3. Transitive Relation

A relation R on a set A is said to be transitive if whenever a is related to b and b is related to c, then a is also related to c.

That is,

\[ (a, b) \in R \text{ and } (b, c) \in R \Rightarrow (a, c) \in R \]

Example:
If \((1,2) \in R\) and \((2,3) \in R\), then \((1,3) \in R\). Hence the relation is transitive.

Equivalence Relation

A relation R on a set A is called an equivalence relation if it satisfies all the following three properties:

1. Reflexive: \((a, a) \in R\) for all \(a \in A\)

2. Symmetric: If \((a, b) \in R\), then \((b, a) \in R\)

3. Transitive: If \((a, b) \in R\) and \((b, c) \in R\), then \((a, c) \in R\)

Example:
Let A = \{1, 2, 3\} and R = \{(1,1), (2,2), (3,3)\}. Then R is an equivalence relation.

Partial Order Relation

A relation R on a set A is called a partial order relation if it satisfies all the following three properties:

1. Reflexive: \((a, a) \in R\) for all \(a \in A\)

2. Antisymmetric: If \((a, b) \in R\) and \((b, a) \in R\), then \(a = b\)

3. Transitive: If \((a, b) \in R\) and \((b, c) \in R\), then \((a, c) \in R\)

Example:
The relation \(\le\) on the set of natural numbers is a partial order relation.

Relation and Function

A function is a special type of relation.

Every function is a relation, but every relation is not a function.

When is a Relation a Function?

A relation R from a set A to a set B is called a function if it satisfies the following condition:

Each element of set A is related to exactly one element of set B.

That is,

\[ \text{For every } a \in A, \text{ there exists a unique } b \in B \text{ such that } (a, b) \in R \]

Definition of a Function

A function from a set A to a set B is a relation f such that every element of A has one and only one image in B.

It is written as:

\[ f : A \rightarrow B \]

If \((a, b) \in f\), then we write \(f(a) = b\).

Examples of Relations which are Functions

Let $A = \{1, 2, 3\}$ and $B = \{4, 5, 6\}$.

\(f = \{(1,4), (2,5), (3,6)\}\)

This relation is a function because each element of A has exactly one image in B.

Relations which are NOT Functions

Case 1: One element has more than one image

\(R_1 = \{(1,2), (1,3), (2,4)\}\)

This is not a function because element 1 is related to two different elements (2 and 3).

Case 2: An element has no image

Let $A = \{1, 2, 3\}$ and $B = \{4, 5\}$.

\(R_2 = \{(1,4), (2,5)\}\)

This is not a function because element 3 has no image in B.

Function in Terms of Domain, Codomain and Range

Let A and B be two non-empty sets.

A function f from A to B is a relation which assigns to each element of A exactly one element of B.

It is written as:

\[ f : A \rightarrow B \]

Domain

The set A is called the domain of the function.

Every element of the domain must have an image in B.

Codomain

The set B is called the codomain of the function.

The image of elements of A must belong to the codomain.

Range

The range of the function is the set of all images of elements of A in B.

That is,

\[ \text{Range of } f = \{ f(a) \mid a \in A \} \]

Example:

Let A = $\{1, 2, 3\}$ and $B = \{4, 5, 6, 7\}$.

Define a function $f : A \rightarrow B$ by \(f(1) = 4,\; f(2) = 5,\; f(3) = 6\).

Here,

Domain = \(\{1, 2, 3\}\)
Codomain = \(\{4, 5, 6, 7\}\)
Range = \(\{4, 5, 6\}\)

Types of Functions

Functions are classified based on how the elements of the domain are mapped to the codomain.

1. One–One Function (Injective Function)

A function $f : A \rightarrow B$ is said to be one–one or injective if different elements of A have different images in B.

That is,

\[ f(a_1) = f(a_2) \Rightarrow a_1 = a_2 \]

Example:
If f(x) = 2x, then the function is one–one because different values of x give different values of f(x).

2. Many–One Function

A function $f : A \rightarrow B$ is said to be many–one if two or more different elements of A have the same image in B.

That is,

\[ f(a_1) = f(a_2) \text{ for } a_1 \neq a_2 \]

Example:
If f(x) = x^2, then f(2) = f(-2) = 4. Hence, the function is many–one.

3. Onto Function (Surjective Function)

A function $f : A \rightarrow B$ is said to be onto or surjective if every element of the codomain B has at least one pre-image in A.

That is,

\[ \text{Range of } f = \text{Codomain} \]

Example:
Let A = \{1,2,3\} and B = \{4,5,6\}. If f = \{(1,4),(2,5),(3,6)\}, then f is onto.

4. Into Function

A function $f : A \rightarrow B$ is said to be into if at least one element of the codomain B has no pre-image in A.

That is,

\[ \text{Range of } f \subset \text{Codomain} \]

Example:
Let A = \{1,2,3\} and B = \{4,5,6,7\}. If f = \{(1,4),(2,5),(3,6)\}, then 7 has no pre-image. Hence, f is an into function.

5. Bijective Function

A function f : $A \rightarrow B$ is said to be bijective if it is both one–one (injective) and onto (surjective).

That is,

Each element of A is related to a unique element of B and every element of B has exactly one pre-image in A.

Mathematically,

\[ f(a_1) = f(a_2) \Rightarrow a_1 = a_2 \quad \text{and} \quad \text{Range} = \text{Codomain} \]

Example:
Let A = \{1,2,3\} and B = \{4,5,6\}.

Define $f : A \rightarrow B$ by \(f(1)=4,\; f(2)=5,\; f(3)=6\).

Here, f is one–one and onto. Hence, f is a bijective function.

Important Result

A function has an inverse if and only if it is bijective.

Composition of Functions

Let $f : A \rightarrow B$ and $g : B \rightarrow C$ be two functions.

The composition of f and g, denoted by \(g \circ f\), is defined as:

\[ (g \circ f)(x) = g(f(x)), \quad \text{for all } x \in A \]

Thus, \(g \circ f : A \rightarrow C\).

Important Note:
The composition \(g \circ f\) is defined only if the codomain of f is the same as the domain of g.

Example of Composition

Let f(x) = 2x and g(x) = x + 1.

Then,

\[ (g \circ f)(x) = g(2x) = 2x + 1 \]

Similarly,

\[ (f \circ g)(x) = f(x + 1) = 2(x + 1) \]

Hence, in general, \(g \circ f \neq f \circ g\).

Inverse of a Function

Let $f : A \rightarrow B$ be a function.

If there exists a function g : B \rightarrow A such that

\[ g \circ f = I_A \quad \text{and} \quad f \circ g = I_B \]

then g is called the inverse function of f and is denoted by \(f^{-1}\).

Here, \(I_A\) and \(I_B\) denote identity functions on sets A and B respectively.

Condition for Existence of Inverse

A function $f : A \rightarrow B$ has an inverse if and only if it is bijective.

That is, f must be:

1. One–one (injective)  and  2. Onto (surjective)

Example of Inverse Function

Let $f(x) = 2x + 3$, where $f : \mathbb{R} \rightarrow \mathbb{R}$.

To find the inverse, let:

\[ y = 2x + 3 \]

Interchanging x and y,

\[ x = 2y + 3 \]

Solving for y,

\[ y = \frac{x - 3}{2} \]

Thus,

\[ f^{-1}(x) = \frac{x - 3}{2} \]

Important Formulas for Functions

Let A and B be two finite sets with |A| = m and |B| = n.

1. Number of One–One (Injective) Functions

A function f : A → B is one–one if no two elements of A map to the same element in B.

Formula:

\[ \text{Number of one-one functions} = \begin{cases} n \cdot (n-1) \cdot (n-2) \cdots (n-m+1) = \frac{n!}{(n-m)!}, & \text{if } m \le n \\ 0, & \text{if } m > n \end{cases} \]

2. Number of Onto (Surjective) Functions

A function f : A → B is onto if every element of B has at least one pre-image in A.

Formula:

\[ \text{Number of onto functions} = \sum _{k=0}^{n}(-1)^{k}{n \choose k}(n-k)^{m} \]

Full Expanded Series:\(n^{m}-{n \choose 1}(n-1)^{m}+{n \choose 2}(n-2)^{m}-{n \choose 3}(n-3)^{m}+\dots +(-1)^{n}{n \choose n}(0)^{m}\)

3. Number of Bijective Functions

A function f : A → B is bijective if it is both one–one and onto.

Formula:

\[ \text{Number of bijective functions} = \begin{cases} n!, & \text{if } m = n \\ 0, & \text{if } m \ne n \end{cases} \]

Note: These formulas are fundamental for combinatorics problems involving functions between finite sets.