A set is a collection with no argument about membership
A set is a well-defined collection of distinct objects. "Well-defined" is doing real work in that sentence: given any object, there must be no dispute about whether it belongs. "The set of prime numbers below 20" is a set. "The set of interesting numbers" is not, because nobody can settle the boundary.
Sets are written in three ways, and the paper expects you to move between them: descriptive ("the set of even numbers less than 10"), tabular or roster form ({2, 4, 6, 8}), and set-builder notation ({x | x is even, x < 10, x ∈ ℕ}).
Two conventions catch people out. Order does not matter, so {1, 2, 3} and {3, 1, 2} are the same set. And repetition does not count, so {1, 2, 2, 3} is just {1, 2, 3}.
| Term | Meaning | Example |
|---|---|---|
| Subset A ⊆ B | every element of A is in B | {1,2} ⊆ {1,2,3} |
| Proper subset A ⊂ B | A ⊆ B but A ≠ B | {1,2} ⊂ {1,2,3} |
| Empty set { } or ∅ | a set with no elements | the set of even primes above 2 |
| Singleton | a set with exactly one element | {0} |
| Equal sets | exactly the same elements | {a,b} = {b,a} |
| Equivalent sets | the same number of elements | {1,2} and {p,q} |
| Power set P(A) | the set of all subsets of A | P({1,2}) has 2² = 4 members |
∅ and {∅} are not the same thing
The empty set has no elements. The set {∅} has one element, and that element happens to be the empty set. Likewise {0} is not empty — it contains the number zero. The number of elements in P(A) is 2ⁿ where n is the number of elements of A, and the empty set is always one of them.
The four operations
Everything the chapter asks you to shade or calculate is built from four operations, and a Venn diagram settles every one of them faster than the algebra does.
- Union A ∪ B — everything in A, or in B, or in both.
- Intersection A ∩ B — only what is in both. If A ∩ B = ∅ the sets are disjoint.
- Difference A − B — in A but not in B. Note that A − B and B − A are usually different sets.
- Complement A′ — everything in the universal set U that is not in A. Always relative to some stated U.
Compare (A∪B)′ with what you get by shading A′ and B′ and taking the overlap. They are the same region — that is De Morgan's law, and shading it is a perfectly valid way to answer a "verify" question.
De Morgan's laws and the laws you can quote
These are worth memorising because "verify the following" is a standing exam question and quoting the law tells you what you are trying to reach.
How to verify a set law for full marks
Take the sets you are given. Work out the left-hand side completely, listing its elements. Work out the right-hand side completely, listing its elements. Then write the sentence "the two sets have the same elements, so the law is verified". Marks are given for the two lists and for the concluding statement — skipping the conclusion is the commonest way to lose one.
From ordered pairs to relations
Once you can build sets you can build sets of pairs. The Cartesian product A × B is the set of all ordered pairs (a, b) with a ∈ A and b ∈ B. If A has m elements and B has n, then A × B has mn of them.
Order matters in an ordered pair: (2, 5) and (5, 2) are different, and in general A × B ≠ B × A.
A relation from A to B is any subset of A × B — any rule picking out some of the pairs. The set of first components is the domain; the set of second components is the range.
A = {1, 2} and B = {p, q, r}. Write A × B and state how many relations from A to B exist.
- Pair every element of A with every element of B:
A × B = {(1,p), (1,q), (1,r), (2,p), (2,q), (2,r)}.Work systematically — all pairs starting with 1, then all starting with 2 — so none is missed. - Count: 2 × 3 = 6 ordered pairs.n(A × B) = n(A) × n(B), which is a useful check on your list.
- A relation is any subset of A × B, so the number of relations is the size of the power set:
2⁶ = 64.Each of the six pairs is either in the relation or not, independently — two choices, six times.
A × B has 6 elements; there are 64 possible relations.
A function is a relation that never hesitates
A function from A to B is a relation in which every element of A is paired with exactly one element of B. Two conditions, and both matter: nothing in the domain may be left out, and nothing in the domain may have two outputs.
That is the whole test. If any first component appears twice with different second components, it is a relation but not a function. Graphically this is the vertical line test: a vertical line drawn anywhere must cut the graph at most once.
| Type | Condition | Plain English |
|---|---|---|
| Into | range ⊆ B, some of B unused | not every output gets used |
| Onto (surjective) | range = B | every element of B is hit |
| One-one (injective) | different inputs → different outputs | no output is reused |
| Bijective | one-one and onto together | a perfect pairing, so an inverse exists |
The mistake that costs a mark every year
A function may send two different inputs to the same output — that is allowed, and it simply means the function is not one-one. What it may never do is send one input to two different outputs. Students reverse this constantly. f(x) = x² is a function even though f(2) and f(−2) are both 4.
Before you leave this chapter
- A set must be well defined; order and repetition are ignored.
- n(P(A)) = 2ⁿ, and ∅ is a subset of every set.
- De Morgan: complement of a union is the intersection of the complements, and vice versa.
- n(A × B) = n(A) × n(B), and (a, b) ≠ (b, a).
- Function = every input used, each input giving exactly one output. Two outputs for one input is fatal; two inputs sharing an output is fine.