Chapter 1: Relations and Functions
Definitions, Types & Counting Formulas
1. Types of Relations (on Set A)
| Empty Relation | $$R = \phi$$ (No element is related to any other) |
| Universal Relation | $$R = A \times A$$ (Every element related to every element) |
| Reflexive | $$(a, a) \in R$$for every$$a \in A$$ |
| Symmetric | If $$(a, b) \in R \Rightarrow (b, a) \in R$$ |
| Transitive | If $$(a, b) \in R$$and$$(b, c) \in R \Rightarrow (a, c) \in R$$ |
| Equivalence Relation | Relation is Reflexive, Symmetric AND Transitive |
2. Types of Functions ($$f: A \to B$$)
| One-One (Injective) | $$f(x_1) = f(x_2) \Rightarrow x_1 = x_2$$ (Distinct elements have distinct images) |
| Many-One | Two or more elements in $$A$$have the same image in$$B$$ |
| Onto (Surjective) | Range $$=$$ Codomain ($$B$$) (Every element in B has a pre-image in A) |
| Into | Range $$\subset$$ Codomain ($$B$$) (At least one element in B has no pre-image) |
| Bijective | Function is both One-One AND Onto |
3. Number of Relations
Let $$n(A) = p$$and$$n(B) = q$$.
| Total Number of Relations from A to B | $$2^{pq}$$ |
| Number of Relations on Set A ($$A \to A$$) | $$2^{p^2}$$ |
| Number of Reflexive Relations on A | $$2^{p^2 – p}$$ |
| Number of Symmetric Relations on A | $$2^{\frac{p(p+1)}{2}}$$ |
4. Number of Functions (Cases)
Let $$n(A) = p$$(domain) and$$n(B) = q$$ (codomain).
| Type | Case 1: $$p < q$$ | Case 2: $$p = q$$ | Case 3: $$p > q$$ |
|---|---|---|---|
| Total Functions | $$q^p$$ | $$q^p$$(or$$p^p$$) | $$q^p$$ |
| One-One (Injective) | $$^qP_p = \frac{q!}{(q-p)!}$$ | $$p!$$ | $$0$$ |
| Onto (Surjective) | $$0$$ | $$p!$$ | $$\sum_{r=1}^{q} (-1)^{q-r} {}^qC_r r^p$$ |
| Bijective | $$0$$ | $$p!$$ | $$0$$ |