Relations and Functions
What is tested
Relations and Functions in this paper asks you to classify a relation as reflexive, symmetric or transitive, to count relations and functions on finite sets, and to test whether a function is one-one, onto or invertible. Composition and inverse functions carry the heaviest marks.
Core rules
- A relation on A is reflexive when (a,a) ∈ R for every a; symmetric when (a,b) ∈ R implies (b,a) ∈ R; transitive when (a,b) and (b,c) in R force (a,c) ∈ R. All three together give an equivalence relation.
- On a set of n elements: total relations 2^(n²), reflexive 2^(n²−n), symmetric 2^(n(n+1)/2).
- Functions from A (m elements) to B (n elements): n^m in total; one-one functions number nPm, which is 0 when n < m.
- f is invertible exactly when it is one-one and onto; then f⁻¹∘f = I_A.
- (f∘g)(x) = f(g(x)), and f∘g is defined only when range(g) ⊆ domain(f).
Worked example
A = {1,2,3}, B = {a,b,c,d}. Building a one-one function: the image of 1 has 4 choices, of 2 has 3, of 3 has 2, so 4×3×2 = 24. Since |B| > |A|, no function from B to A can be one-one.
Equivalence check: R = {(a,b) : 5 divides (a−b)} on Z. 5|0 gives reflexivity; 5|(a−b) implies 5|(b−a), giving symmetry; 5|(a−b) with 5|(b−c) gives 5|(a−c), so transitive. The classes are [0],[1],[2],[3],[4].
Marks-losing traps
Confusing range with codomain when claiming onto; reversing the order in fog; using f⁻¹ before proving f is bijective; proving only two of three properties for an equivalence relation; assuming every relation is a function.