Sets, relations & functions: practice problems with step-by-step solutions

1Sets and set operations

A set is a collection of distinct elements: A = {1, 2, 3}. Order and repetition do not matter. |A| is the number of elements, and U is the universal set that contains everything under discussion.

• A ∪ B (union): the elements in A or B or both.
• A ∩ B (intersection): the elements in both.
• A − B (difference): the elements of A that are not in B.
• A′ (complement): the elements of U that are not in A.

In a Venn diagram two circles split U into four regions: only A, both, only B, and neither. Every set expression is a union of some of these regions, so you can always count it region by region.

Here |A| = 12 + 5 = 17, |A ∩ B| = 5, |A ∪ B| = 12 + 5 + 8 = 25 and |(A ∪ B)′| = 15.

2Counting with inclusion–exclusion

Adding |A| and |B| counts the overlap twice, so subtract it once:

For three sets the pairwise overlaps are subtracted, but then the centre has been removed three times, so it is added back:

In word problems it is usually safer to fill in a Venn diagram from the centre outwards: first the elements in all three sets, then each pair minus the centre, then each single set minus what is already placed.

Two other counts come up often: a set with n elements has 2ⁿ subsets (its power set 𝒫(A)), and |A × B| = |A|·|B| ordered pairs.

3A worked example

Follow every step. Try to predict the next one before you open it.

4Relations

A relation R on a set X is a set of ordered pairs (x, y) with x and y in X. Drawn as a directed graph, each pair is an arrow and (x, x) is a loop.

• Reflexive: (x, x) ∈ R for every x: a loop at every vertex.
• Symmetric: (x, y) ∈ R always comes with (y, x) ∈ R.
• Antisymmetric: (x, y) and (y, x) are both in R only when x = y.
• Transitive: (x, y) and (y, z) in R force (x, z) ∈ R.

A relation that is reflexive, symmetric and transitive is an equivalence relation. It splits X into disjoint classes, such as the remainders 0, 1 and 2 for “x ≡ y (mod 3)”. A class with s elements contributes s² ordered pairs.

To disprove a property, one counterexample is enough; to prove it, check every pair.

5Functions

A function f: A → B gives every element of A exactly one image in B.

• Injective (one-to-one): different elements have different images; no element of B receives two arrows.
• Surjective (onto): every element of B receives at least one arrow.
• Bijective: both. Only then does f have an inverse f⁻¹.

The function in the figure is injective but not surjective: d receives no arrow. An injection needs |A| ≤ |B| and a surjection |A| ≥ |B|.

With |A| = m and |B| = n there are nᵐ functions and n!/(n − m)! injective ones. The composition (g ∘ f)(x) = g(f(x)) applies f first.

6Common mistakes

• Adding |A| + |B| without subtracting the overlap.
• Forgetting to add back the centre in three-set inclusion–exclusion.
• Writing mⁿ instead of nᵐ for the number of functions from m elements to n elements.
• Thinking a relation cannot be both symmetric and antisymmetric: the relation {(1, 1)} is both.
• Applying g ∘ f in the wrong order: f acts first.

7How exam questions look

• Easy: Venn diagrams and subsets. You count a set expression from a Venn diagram, click the region of an expression, or find the size of a power set, a Cartesian product or a family of subsets.
• Medium: inclusion–exclusion and relations. You solve two- and three-set counting problems, count expressions from region totals, decide which property a relation has, or count the pairs needed for a closure.
• Hard: functions and counting. You classify a function as injective, surjective or bijective, count functions, injections and surjections, evaluate compositions and inverses, and count pairs in equivalence relations.