Chapter 1 at a Glance

Relations

A relation in AA is a subset of A×AA \times A. The extremes: empty relation R=ϕR = \phi and universal relation R=A×AR = A \times A (the trivial relations). The three structural properties:

reflexive: (a,a)∈R ∀asymmetric: (a,b)∈R⇒(b,a)∈Rtransitive: (a,b),(b,c)∈R⇒(a,c)∈R\textbf{reflexive:}\ (a, a) \in R\ \forall a \qquad \textbf{symmetric:}\ (a, b) \in R \Rightarrow (b, a) \in R \qquad \textbf{transitive:}\ (a,b), (b,c) \in R \Rightarrow (a, c) \in R

Cards illustrating reflexive, symmetric, transitive; partition of integers into three classes

All three together make an equivalence relation, which partitions its set into disjoint equivalence classes [a][a] covering everything — and conversely every partition defines an equivalence relation. Standard equivalences: congruence and similarity of triangles, "same remainder mod nn", "same value of ff". Standard non-examples: ≤\leq and divisibility (no symmetry), perpendicularity (symmetric only), a≤b2a \leq b^2 (nothing at all).

Functions

one-one: f(x1)=f(x2)⇒x1=x2onto: range=co-domainbijective: both\textbf{one-one:}\ f(x_1) = f(x_2) \Rightarrow x_1 = x_2 \qquad \textbf{onto:}\ \text{range} = \text{co-domain} \qquad \textbf{bijective: both}

Four mapping diagrams: one-one not onto, many-one, onto not one-one, bijective

Proof templates: for one-one, run the algebra from f(x1)=f(x2)f(x_1) = f(x_2); for onto, solve f(x)=yf(x) = y and check the solution lies in the domain; to disprove either, one counterexample. The domain and co-domain are part of the function — 2x2x is bijective on R\mathbb{R} but not onto N\mathbb{N}. On a finite set mapping to itself, one-one   ⟺  \iff onto.

Composition and inverses

(g∘f)(x)=g(f(x)) (right to left);associative, not commutative(g \circ f)(x) = g(f(x)) \ (\text{right to left}); \quad \text{associative, not commutative} f invertible  ⟺  f bijective;(f−1)−1=f;(g∘f)−1=f−1∘g−1f \text{ invertible} \iff f \text{ bijective}; \qquad \big(f^{-1}\big)^{-1} = f; \qquad (g \circ f)^{-1} = f^{-1} \circ g^{-1}

To compute f−1f^{-1}: solve y=f(x)y = f(x) for xx, then verify both compositions equal the identity.

The JEE counting card

What Count
relations on nn-set 2n22^{n^2}
reflexive 2n2−n2^{n^2 - n}
symmetric 2n(n+1)/22^{n(n+1)/2}
equivalence relations Bell numbers 1,2,5,151, 2, 5, 15
functions m→nm \to n nmn^m
one-one m→nm \to n nPm^n P_m (00 if m>nm > n)
onto m→nm \to n ∑(−1)k(nk)(n−k)m\sum (-1)^k \binom{n}{k}(n-k)^m;  2m−2\ 2^m - 2 onto a 2-set; 00 if m<nm < n
bijections of nn-set n!n!

The mistake checklist (read before every exam)

Reflexivity needs every element — one failing aa (like a=12a = \frac{1}{2} for a≤b2a \leq b^2) kills it; and symmetric + transitive does not imply reflexive.

Vacuous transitivity — a relation with no linking chains is transitive by default.

Proving vs disproving — properties are proved with arbitrary elements, disproved with one concrete counterexample; never "prove" by example.

Range vs co-domain — onto compares the range with the stated co-domain, and preimages must lie in the stated domain.

f−1≠1ff^{-1} \neq \frac{1}{f} — the inverse function is not the reciprocal.

Composition order — g∘fg \circ f applies ff first; and (g∘f)−1=f−1∘g−1(g \circ f)^{-1} = f^{-1} \circ g^{-1}, undone in reverse.

Counting exponents — functions m→nm \to n number nmn^m (domain in the exponent); one-one is 00 when m>nm > n, onto is 00 when m<nm < n.