Sets and their operations

A collection with a clear rule

Your class register is a list of names. The books in your bag are a collection of books. The vowels of the English alphabet are $a, e, i, o, u$. In each case, you can say for sure whether something belongs to the collection or not.

A set is a collection of objects in which it is clear what belongs to it and what does not. The objects are called the elements (or members) of the set. We write sets with capital letters, and elements with small letters.

• $x \in A$ means: $x$ is an element of $A$. We read it "$x$ belongs to $A$".
• $x \notin A$ means: $x$ is not an element of $A$.

"The tall students of the class" is not a set, because people may not agree who is tall. "The students of the class with a height above $170\ \text{cm}$" is a set.

Two ways to write a set

Roster form. List all the elements between braces: $A = \{1, 2, 3, 4\}$. The order does not matter, and a repeated element counts once.

Set-builder form. Give the rule: $A = \{x : x \text{ is a natural number less than } 5\}$. We read the colon as "such that".

Some sets have standard names:

The empty set $\varnothing$ has no element. For example, $\{x : x \in \mathbb{N}, 2 < x < 3\} = \varnothing$. A set with one element is a singleton. A set is finite if we can count its elements, and infinite if we cannot. The number of elements of a finite set $A$ is written $n(A)$.

Subsets

$A$ is a subset of $B$, written $A \subseteq B$, if every element of $A$ is also in $B$. For example, $\{1, 2\} \subseteq \{1, 2, 3\}$. Three facts are always true:

• every set is a subset of itself, $A \subseteq A$;
• the empty set is a subset of every set, $\varnothing \subseteq A$;
• if $A \subseteq B$ and $B \subseteq A$, then $A = B$.

How many subsets? To make a subset of a set with $n$ elements, we decide for each element: in or out. There are $2$ choices for each of the $n$ elements, so the number of subsets is

The set of all subsets of $A$ is called the power set $P(A)$. For $A = \{1, 2, 3\}$ there are $2^3 = 8$ subsets: $\varnothing$, $\{1\}$, $\{2\}$, $\{3\}$, $\{1,2\}$, $\{1,3\}$, $\{2,3\}$ and $\{1,2,3\}$. All except $A$ itself are proper subsets, so there are $2^n - 1$ of them.

Intervals

Sets of real numbers between two ends are written as intervals. A round bracket leaves the end out. A square bracket keeps it.

We use intervals all the time for the domain and the range of a function. The symbol $\infty$ is not a number. It only says that the interval has no end.

Operations on sets

Let $U$ be the universal set, the set of everything that we talk about.

If $A \cap B = \varnothing$, the sets are disjoint.

Example. Let $U = \{1, 2, \ldots, 10\}$, $A = \{1, 2, 3, 4, 5, 6\}$ and $B = \{4, 5, 6, 7, 8\}$. Then $A \cup B = \{1, 2, 3, 4, 5, 6, 7, 8\}$, $A \cap B = \{4, 5, 6\}$, $A - B = \{1, 2, 3\}$, $B - A = \{7, 8\}$ and $A' = \{7, 8, 9, 10\}$.

De Morgan's laws. The complement of a union is the intersection of the complements, and the complement of an intersection is the union of the complements:

Counting with two sets

If we add $n(A)$ and $n(B)$, the elements of $A \cap B$ are counted twice. So we take them away once:

Example. In a class of $40$ students, $25$ play cricket, $20$ play chess and $8$ play both. The number who play at least one game is $25 + 20 - 8 = 37$. So $40 - 37 = 3$ students play neither.

Push the overlap up to the size of the smaller set. Then the smaller circle sits inside the larger one, and n(A ∪ B) is just the larger size.

Practise with new numbers

Try it in Python

Python has sets, with the same operations. This program finds the union, the intersection, the differences and the complement of two sets.

Remember these

• A set has a clear rule for what belongs to it. We write it in roster form or in set-builder form.
• A set with $n$ elements has $2^n$ subsets.
• $n(A \cup B) = n(A) + n(B) - n(A \cap B)$.
• $(A \cup B)' = A' \cap B'$ and $(A \cap B)' = A' \cup B'$.
• $(a, b)$ leaves out the ends. $[a, b]$ keeps them.

Check yourself

Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.

1. Write $\{x : x \in \mathbb{Z}, -2 \le x < 3\}$ in roster form.

2. How many subsets does $\{a, b, c, d, e\}$ have?

3. If $n(A) = 12$, $n(B) = 9$ and $n(A \cap B) = 4$, find $n(A \cup B)$.

4. Write $2 \le x < 7$ as an interval.