IAS Buddha - UPSC Preparation

There is no permanent place in the world for ugly mathematics. — G. H. Hardy

1.1 Introduction

A relation $R$ from a set $A$ to a set $B$ is a subset of $A \times B$ .

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

Functions are special relations. This chapter covers types of relations, types of functions, composition, and invertible functions.

A relation $R$ in a set $A$ is a subset of $A \times A$ .

Empty relation: $R = \phi \subset A \times A$ (no element is related to any element)
Universal relation: $R = A \times A$ (every element is related to every element)

Empty and universal relations are called trivial relations.

A relation $R$ in $A$ is:

Reflexive if $(a, a) \in R$ for every $a \in A$
Symmetric if $(a_1, a_2) \in R$ implies $(a_2, a_1) \in R$
Transitive if $(a_1, a_2) \in R$ and $(a_2, a_3) \in R$ implies $(a_1, a_3) \in R$

$R$ is an equivalence relation if it is reflexive, symmetric and transitive.

An equivalence relation partitions $A$ into disjoint equivalence classes $[a]$ .

Example: Congruence of triangles is an equivalence relation. Perpendicularity of lines is symmetric but neither reflexive nor transitive.

Let $f : X \to Y$ .

One-one (injective): $f(x_1) = f(x_2)$ implies $x_1 = x_2$
Many-one: not one-one
Onto (surjective): for every $y \in Y$ there exists $x \in X$ with $f(x) = y$ (range of $f$ is $Y$ )
Bijective: both one-one and onto

For a finite set $X$ , $f : X \to X$ is one-one if and only if it is onto. This need not hold for infinite sets.

If $f : A \to B$ and $g : B \to C$ , the composition $gof : A \to C$ is

$(gof)(x) = g(f(x))$

In general $gof \mathrel{\htmlClass{course-neq}{\char"2260}} fog$ .

$f : X \to Y$ is invertible if there exists $g : Y \to X$ such that

$gof = I_X \quad\text{and}\quad fog = I_Y$

Then $g = f^{-1}$ .

$f$ is invertible if and only if $f$ is bijective.