Sets, Relations and Functions
This domain tests set language and counting formulae, the classification of relations, and whether a mapping is a function and, if so, one-one or onto.
Set language and counting
- Roster form lists elements; set-builder states a property. ∅ is a subset of every set, and a set with n elements has 2ⁿ subsets (2ⁿ−1 proper subsets).
- n(A∪B) = n(A) + n(B) − n(A∩B); De Morgan: (A∪B)′ = A′∩B′ and (A∩B)′ = A′∪B′.
- n(A×B) = p·q; relations from A to B = 2^(pq); functions from A to B = q^p.
Relations and functions
R on A is reflexive if (a,a) ∈ R for every a, symmetric if (a,b) ∈ R ⇒ (b,a) ∈ R, transitive if (a,b),(b,c) ∈ R ⇒ (a,c) ∈ R. All three together give an equivalence relation. f: A→B is a function when every element of A has exactly one image; it is one-one if f(a)=f(b) ⇒ a=b, and onto if range = codomain.
Worked example
In a class of 60, 35 take Mathematics, 30 take Physics and 10 take both. Students taking at least one = 35 + 30 − 10 = 55, so neither = 60 − 55 = 5. For A = {1,2,3}, B = {p,q}: n(A×B) = 6, so there are 2⁶ = 64 relations and 2³ = 8 functions from A to B. No function can be one-one, since 3 elements cannot map injectively into 2.
Traps that cost marks
- ∅, {0} and {∅} are three different sets; {∅} has one element and ∅ has none.
- "Reflexive" needs all n pairs (a,a); listing (1,1) and (2,2) only is not enough for A = {1,2,3}.
- Onto is about covering the codomain, not merely having some image in it.
- A relation that sends one input to two outputs is not a function.