Sets, Relations and Functions

Chapter 3 · Algebra · 2 questions in the paper · 14 min read

Sets, Relations and Functions

What the syllabus asks for 3
  • Sets, subsets, operations and Venn-diagram word problems
  • Relations and their types
  • Functions, domain, range, composite and inverse functions

Sets and functions give about two questions in the paper, and they are among the most predictable: a Venn-diagram word problem, a count of subsets or relations, the domain of a function, and a composite or inverse.

The Dean's Office model asks "A − (B ∪ C)" and a 120-student maths/statistics problem. Learn the counting formulas and the vocabulary, and these are quick marks.

What the paper asks from this chapter
  • Venn counting: n(A\cup B)=n(A)+n(B)-n(A\cap B) and its three-set form.
  • Counting: subsets 2^n, proper subsets 2^n-1, n(A\times B)=mn, relations 2^{mn}.
  • Laws: De Morgan, A-B=A\cap B', distributive laws.
  • Relations: reflexive, symmetric, transitive, equivalence.
  • Functions: one-one, onto, domain of \sqrt{\ } and \frac{1}{x}, composite and inverse.

3.1 Sets, subsets, operations and Venn-diagram word problems

  • A set with n elements has 2^n subsets, 2^n-1 proper subsets, and \binom{n}{r} subsets of exactly r elements. The power set has 2^n elements.
  • A-B=A\cap B'. A\,\Delta\,B=(A-B)\cup(B-A) and n(A\Delta B)=n(A)+n(B)-2n(A\cap B).
  • De Morgan: (A\cup B)'=A'\cap B', (A\cap B)'=A'\cup B'.
  • Distributive: A-(B\cup C)=(A-B)\cap(A-C) and A-(B\cap C)=(A-B)\cup(A-C).
  • n(A\cup B\cup C)=n(A)+n(B)+n(C)-n(A\cap B)-n(B\cap C)-n(C\cap A)+n(A\cap B\cap C).
  • A\cup A'=U, A\cap A'=\varnothing, and A\subseteq B gives A\cup B=B and A\cap B=A.
Maths and statistics

Problem. Of 120 students, 90 take mathematics and 72 take statistics; 10 take neither. How many take both?

Solution. n(M\cup S)=120-10=110. Both =90+72-110=52.

photograph
(a) John Venn
photograph
(b) Venn diagram on Drypool Bridge, Hull
photograph
(c) Georg Cantor, founder of set theory
Plate 3.1. The people and places behind sets. (a) John Venn (1834-1923), the English logician who popularised the overlapping-circle diagram in 1880. (b) The Drypool Bridge in Hull, England, carries a giant Venn diagram as its decoration. (c) Georg Cantor (1845-1918), the founder of set theory, who proved that some infinite sets are strictly bigger than others.Photo credits: (a) Unknown, Public domain; (b) Ian S, CC BY-SA 2.0; (c) Unknown author Unknown author, Public domain.

diagram
Figure 3.1. A three-set Venn diagram with every region counted. The eight regions add to 50 students. From the regions: n(A) = 12 + 5 + 3 + 2 = 22, n(B) = 21, n(C) = 17, and n(A union B union C) = 44 both by adding the seven shaded regions and by the inclusion-exclusion formula 22 + 21 + 17 - 7 - 6 - 5 + 2. Six students belong to none of the sets.

3.2 Relations and their types

  • A relation from A to B is any subset of A\times B. If n(A)=m and n(B)=n there are 2^{mn} relations.
  • On a set A: reflexive if (a,a)\in R for all a; symmetric if (a,b)\in R\Rightarrow(b,a)\in R; transitive if (a,b),(b,c)\in R\Rightarrow(a,c)\in R; equivalence if all three.
  • "a divides b" on the positive integers is reflexive and transitive but not symmetric. "=" is an equivalence relation; "<" is only transitive.
  • Domain = set of first coordinates; range = set of second coordinates that actually occur.

diagram
Figure 3.2. Subsets of {1, 2, 3}, counted by brute force in the cell. The 8 = 2^3 subsets sit in rows by size, 1 + 3 + 3 + 1 (Pascal's row). Proper subsets exclude the set itself, so 2^3 - 1 = 7; non-empty proper subsets are 2^3 - 2 = 6. The bars on the right show how fast 2^n grows: 10 elements already give 1,024 subsets.

diagram
Figure 3.3. Relations on {1, 2, 3}, by brute force. There are 2^9 = 512 relations (every subset of the 9 ordered pairs); 2^6 = 64 are reflexive, 2^6 = 64 are symmetric, and exactly 5 are equivalence relations (one for each way of splitting the set into groups: 1 + 3 + 1). The table tests four sample relations; only R2 is an equivalence relation.

3.3 Functions, domain, range, composite and inverse functions

  • A function from A to B gives every element of A exactly one image. With n(A)=m, n(B)=n there are n^m functions and \frac{n!}{(n-m)!} one-one functions (m\le n).
  • One-one: different inputs, different outputs. Onto: range = codomain. Bijective: both.
  • Domain rules: \frac{1}{g(x)} needs g(x)\ne0; \sqrt{g(x)} needs g(x)\ge0; \log g(x) needs g(x)>0.
  • Composite: (f\circ g)(x)=f(g(x)). In general f\circ g\ne g\circ f.
  • Inverse exists only for a bijection: swap x and y and solve. If f(x)=3x-6 then f^{-1}(x)=\frac{x+6}{3}, and f(f^{-1}(x))=x.
  • Even: f(-x)=f(x) (x^2, |x|). Odd: f(-x)=-f(x) (x^3, \sin x).
Common mistake

f(x)=x^2 on \mathrm{R} is neither one-one (f(2)=f(-2)) nor onto (no negative outputs). Check both before saying "bijective".

diagram
Figure 3.4. The four kinds of mapping, with the counts checked by brute force. From A = {1, 2, 3} to B = {a, b} there are 2^3 = 8 functions, none one-one (3 > 2) and 6 onto; from {1, 2} to {a, b, c} there are 3^2 = 9 functions, 3 x 2 = 6 one-one and none onto. A function must give every element of A exactly one arrow; the range is the set of elements of B that are actually hit.

diagram
Figure 3.5. Composite and inverse functions for f(x) = 2x + 3 and g(x) = x^2. At x = 2: (f o g)(2) = f(4) = 11 but (g o f)(2) = g(7) = 49, so composition is not commutative. The inverse f^-1(x) = (x - 3)/2 undoes f (f^-1(7) = 2) and its graph is the mirror image of f in the line y = x.

3.4 Eight traps in sets, relations and functions

Set questions are shorter than they look, and nearly every wrong option is a plausible slip. These eight traps come from the model questions on subsets, equivalence relations and composite functions.

  1. The empty set is a subset of every set, and \{\varnothing\} is not empty. A set with n elements has 2^n subsets, including \varnothing and the set itself (Fig 3.2). The proper subsets exclude the set itself, so there are 2^n-1, and the non-empty proper subsets number 2^n-2. The set \{\varnothing\} has one element, so n(\{\varnothing\})=1, not 0.
  2. "Neither" is the universal total minus the union. If 100 students are asked and 60 like tea, 50 like coffee and 20 like both, the union is 60+50-20=90 and 10 like neither. Always subtract the intersection once, or the overlap is counted twice. With three sets use the full formula with the triple intersection added back (Fig 3.1).
  3. "Only A" is not the same as "A". The region "only A" removes the parts shared with B and C, so in Fig 3.1 only A has 12 students while n(A) is 22. A question that says "exactly two of the sets" wants 5+4+3=12, and "at least two" adds the triple region to get 14. Read these words carefully and draw the diagram.
  4. A-B is not B-A, and De Morgan flips the sign. A-B=A\cap B' is what is in A but not in B. The laws (A\cup B)'=A'\cap B' and (A\cap B)'=A'\cup B' swap union and intersection when you take the complement. A symmetric difference takes both one-sided parts, so n(A\Delta B)=n(A)+n(B)-2n(A\cap B).
  5. A relation is a set of ordered pairs. (a,b) is not the same as (b,a), so n(A\times B)=mn and the number of relations from A to B is 2^{mn}, which is 512 for A=B=\{1,2,3\} (Fig 3.3). The number of reflexive relations is 2^{n^2-n}=64 because the diagonal pairs are forced. Do not confuse the count of relations with the count of functions.
  6. Equivalence needs all three properties. Reflexive, symmetric and transitive must all hold. The relation \{(1,1),(2,2)\} on \{1,2,3\} is not reflexive because (3,3) is missing, and \{(1,2),(2,1)\} is symmetric but not transitive. The empty relation is symmetric and transitive but not reflexive on a non-empty set.
  7. A function gives every input exactly one output. Domain is the set of inputs, codomain is the set where outputs may lie, and range is the set of outputs actually reached (Fig 3.4). Onto means range equals codomain, and one-one means different inputs give different outputs. For m inputs and n outputs there are n^m functions, and n(n-1)\cdots(n-m+1) of them are one-one.
  8. Composite order is right to left, and only a bijection has an inverse. (f\circ g)(x)=f(g(x)) means apply g first, and in general f\circ g\neq g\circ f (Fig 3.5). An inverse exists only when the function is both one-one and onto, and then (f\circ g)^{-1}=g^{-1}\circ f^{-1} with the order reversed. To find f^{-1}, write y=f(x), solve for x, then swap the letters.

3.4.1 Worked checks

Q. In a class of 80, 45 play football, 38 play volleyball and 12 play both. How many play neither and how many play exactly one game?

Answer. Union =45+38-12=71, so neither =80-71=9. Exactly one game =71-12=59, and the check 33+26=59 (football only 45-12=33, volleyball only 38-12=26) agrees. The 9 plus 59 plus 12 add to 80.

Q. How many relations, and how many reflexive relations, are there on a set with 3 elements?

Answer. There are 3\times3=9 ordered pairs and each is either in or out, so 2^9=512 relations. A reflexive relation must contain the 3 diagonal pairs, so only the other 6 pairs are free: 2^6=64. Fig 3.3 confirmed both numbers by listing every relation.

Q. If f(x)=2x+3 and g(x)=x^2, find (f\circ g)(2), (g\circ f)(2) and f^{-1}(7).

Answer. g(2)=4 so (f\circ g)(2)=f(4)=11. f(2)=7 so (g\circ f)(2)=g(7)=49. For the inverse, y=2x+3 gives x=\frac{y-3}{2}, so f^{-1}(7)=\frac{7-3}{2}=2, which agrees with f(2)=7.

Formula and fact sheet

Item Result
Subsets / proper subsets 2^n / 2^n-1
n(A\times B) mn
Relations from A to B 2^{mn}
Functions / one-one functions n^m / \frac{n!}{(n-m)!}
n(A\cup B) n(A)+n(B)-n(A\cap B)
De Morgan (A\cup B)'=A'\cap B'

Chapter summary

  • Count with n(A\cup B)=n(A)+n(B)-n(A\cap B); "neither" is the total minus the union.
  • A set of n elements has 2^n subsets, one of them the empty set.
  • A-B means A\cap B'.
  • Equivalence = reflexive + symmetric + transitive.
  • A function gives each input exactly one output; check one-one and onto separately.
  • Domain: no zero denominators, no negative square roots, positive log arguments.
  • To invert, swap x and y; to compose, work from the inside out.

Practice questions

Set A — Recall (20 questions)

  1. The number of subsets of a set with 3 elements isa6b8c9d3
  2. If n(A)=3 and n(B)=4, then n(A\times B) isa7b1c81d12
  3. A-B equalsaA\cap B'bA'\cap BcA\cup B'dA'\cup B
  4. By De Morgan's law, (A\cup B)' equalsaA'\cup B'bA\cap BcA'\cap B'dA\cup B'
  5. The number of proper subsets of \{a,b,c\} isa6b8c3d7
  6. A relation that is reflexive, symmetric and transitive is calledaa partial orderban equivalence relationca functiondan identity map
  7. If f(x)=2x+3, then f(4) isa11b9c14d8
  8. The domain of f(x)=\frac{1}{x-2} isaall real numbersbx>2c\mathrm{R}-\{2\}dx\ne-2
  9. If f(x)=x^2 and g(x)=x+1, then (f\circ g)(2) isa5b9c25d6
  10. The inverse of f(x)=3x-6 isa3x+6b\frac{x-6}{3}c\frac{x}{3}-6d\frac{x+6}{3}
  11. If n(A)=20, n(B)=15 and n(A\cap B)=5, then n(A\cup B) isa30b35c40d25
  12. Which of the following is the empty set?a\{0\}b\{\varnothing\}c\{x\in\mathrm{R}: x^2=-1\}d\{x: x=x\}
  13. A\cap A' equalsaAbUcA'd\varnothing
  14. The range of f(x)=x^2, x\in\mathrm{R}, isay\ge0ball real numberscy>0dy\le0
  15. A function that is both one-one and onto is calledainjective onlybbijectivecconstantdidentity only
  16. If A\subseteq B, then A\cup B equalsaAbA\cap BcBdU
  17. The number of relations from a 2-element set to a 3-element set isa64b36c8d9
  18. The function f(x)=x^3 isaevenbneither even nor oddcconstantdodd
  19. A\cup A equalsa\varnothingbAcUdA'
  20. The number of elements in the power set of a 4-element set isa8b4c16d32
Answers and explanations — Set A

1. (b) — 2³ = 8, including the empty set and the set itself.

2. (d) — n(A×B) = 3 × 4 = 12.

3. (a) — A − B keeps what is in A and not in B: A ∩ B′.

4. (c) — complement of a union is the intersection of complements.

5. (d) — 2³ − 1 = 7; only the set itself is excluded.

6. (b) — the three properties together define an equivalence relation.

7. (a) — 2(4) + 3 = 11.

8. (c) — the denominator vanishes only at x = 2.

9. (b) — g(2) = 3 and f(3) = 9. (f∘g) means g first.

10. (d) — y = 3x − 6 gives x = (y + 6)/3.

11. (a) — 20 + 15 − 5 = 30.

12. (c) — x² = −1 has no real solution. {0} and {∅} each have one element.

13. (d) — nothing is in both A and its complement.

14. (a) — squares are never negative, and 0 is attained.

15. (b) — one-one and onto together is bijective.

16. (c) — if A is inside B, joining adds nothing new.

17. (a) — subsets of a 6-element product: 2⁶ = 64.

18. (d) — (−x)³ = −x³.

19. (b) — idempotent law.

20. (c) — 2⁴ = 16.

Set B — Understanding (12 questions)

  1. Of 120 students, 90 take mathematics, 72 take statistics and 10 take neither. The number taking both isa42b48c52d62
  2. In a class of 40, 25 play football, 20 play cricket and 5 play neither. The number playing both isa10b15c5d20
  3. The domain of f(x)=\sqrt{x-3} isax>3bx\le3call real numbersdx\ge3
  4. If f(x)=2x+1 and g(x)=x^2, then (f\circ g)(3) isa7b19c49d13
  5. The number of functions from a 3-element set to a 2-element set isa8b9c6d5
  6. R=\{(1,1),(2,2),(3,3),(1,2)\} on \{1,2,3\} isasymmetric onlyban equivalence relationcreflexive and transitive but not symmetricdnot reflexive
  7. If f(x)=3x+2, then f^{-1}(11) isa1b2c5d3
  8. If A=\{1,2,3\} and B=\{2,3,4\}, then (A-B)\cup(B-A) isa\{2,3\}b\{1,4\}c\{1,2,3,4\}d\{1\}
  9. If f(x)=|x|, then f(-3)+f(3) isa0b3c6d-6
  10. The function f(x)=x^2+1 on \mathrm{R} isaone-one and ontobone-one intocmany-one ontodmany-one into
  11. If n(A)=4, n(B)=3 and n(A\cap B)=2, then n(A\,\Delta\,B) isa3b5c1d7
  12. The number of one-one functions from \{1,2\} to \{a,b,c\} isa9b6c8d5
Answers and explanations — Set B

1. (c) — union = 110; both = 90 + 72 − 110 = 52.

2. (a) — union = 35; both = 25 + 20 − 35 = 10.

3. (d) — need x − 3 ≥ 0; at x = 3 the root is 0, which is defined.

4. (b) — g(3) = 9, f(9) = 19. Computing g(f(3)) = 49 reverses the order.

5.(a) — each of 3 inputs has 2 choices: 2³ = 8;(b) is 3².

6. (c) — reflexive, transitive, but (1,2) has no (2,1).

7. (d) — 3x + 2 = 11 gives x = 3.

8. (b) — A − B = {1}, B − A = {4}.

9. (c) — 3 + 3 = 6.

10. (d) — f(1) = f(−1), and the range is y ≥ 1, not all of ℝ.

11. (a) — 4 + 3 − 2·2 = 3.

12. (b) — 3 × 2 = 6 ordered choices without repetition.

Set C — Application (8 questions)

  1. In a group of 100 people, 60 like tea, 50 like coffee and 20 like both. The number liking neither isa0b5c20d10
  2. If f(x)=2x-1 and g(x)=\frac{x+1}{2}, then f(g(x)) equalsa0bxc2xdx+1
  3. The number of subsets of a 5-element set having exactly 2 elements isa10b20c5d25
  4. On the positive integers, "a divides b" isaan equivalence relationbsymmetriccreflexive and transitive but not symmetricdsymmetric and transitive only
  5. If f(x)=ax+b, f(1)=5 and f(2)=8, then f(5) isa15b17c20d14
  6. In a universal set of 50 elements, n(A)=30, n(B)=25 and n(A\cup B)=45. Then n(A\cap B) isa5b15c20d10
  7. The range of f(x)=3x-2 defined on \{1,2,3\} isa\{1,4,7\}b\{3,6,9\}c\{2,4,6\}d\{1,2,3\}
  8. The number of functions from \{1,2\} to \{a,b,c\} isa8b6c9d64
Answers and explanations — Set C

1. (d) — union = 60 + 50 − 20 = 90, so neither = 10.

2. (b) — 2·(x+1)/2 − 1 = x; f and g are inverses.

3. (a) — C(5,2) = 10.

4. (c) — a | a and transitive, but 2 | 4 does not give 4 | 2.

5. (b) — a = 3, b = 2, so f(5) = 17.

6. (d) — 30 + 25 − 45 = 10.

7. (a) — f(1), f(2), f(3) = 1, 4, 7.

8. (c) — 3² = 9; (b) 6 counts only the one-one ones.