Before you start
- You know what a number system is — numbers.
What you will be able to do after this lesson:
- Use set notation for membership, subset, union, intersection and complement.
- Draw and read a Venn diagram for up to three sets.
- Apply the inclusion-exclusion principle to a counting problem.
- Explain why sets underpin databases, type systems and search.
Study route: read the lesson, then attempt every problem before opening the answers.
Now let’s introduce another fundamental mathematical idea.
A set is simply a collection of distinct objects.
For example:
We say:
3 belongs to set (A).
Written:
But:
A set can contain numbers:
letters:
or even objects:
Why are sets important to computing?
Because computers constantly deal with collections of things.
For example:
Set of valid states
Set of memory addresses
Set of instructions
Set of possible inputs
Set of characters
Set of numbersLater, when we talk about Boolean logic, we’ll essentially be working with systems containing a very small set of possible states:
That’s where our earlier transistor discussion starts connecting back to mathematics.
Practice — problems
Attempt all of these before opening the answers.
- Given , , , find , , , , and .
- Inclusion–exclusion. In a class of 40, 25 study Physics, 20 study Chemistry and 8 study both. How many study neither? Draw the Venn diagram first.
- Three sets. Of 100 people, 60 like tea, 50 like coffee, 40 like juice; 30 like tea and coffee, 20 tea and juice, 15 coffee and juice, and 10 like all three. How many like none?
- Why is rather than ? Answer in one sentence about double counting.
- Where do you already use this? Name the set operation each of these performs: SQL
UNION, SQLINNER JOIN, Python’s&on sets, a search querycats -dogs.
Answers — open only after an attempt
- ; ; ; ; .
- , so study neither.
- , so like none. Note the pattern: add singles, subtract pairs, add back the triple — each region must be counted exactly once.
- Because elements in both sets are counted once in and again in , so the overlap must be subtracted once to leave every element counted exactly once.
UNIONis ;INNER JOINis on the join key; Python’s&is ;cats -dogsis set difference .
Before moving on
You are done with this lesson when you can, closed-book:
- Use union, intersection, difference and complement correctly.
- Draw a three-set Venn diagram and label every region.
- Apply inclusion–exclusion and explain why the alternating signs appear.
- Name a computing operation that is each set operation.
Recap: A set is an unordered collection with no duplicates, and set notation is the language for saying precisely which things belong. Union, intersection, difference and complement combine sets; Venn diagrams show the regions. Inclusion–exclusion corrects for double counting by adding singles, subtracting pairs and adding back triples, so every element is counted exactly once. Databases, type systems and search queries are all set operations wearing different syntax.
Next: Variables — what happens when you stop naming specific numbers and start naming unknown ones.
Software engineering
Infrastructure & security
Computer science
Hardware & engineering