Set-builder notation
- sets (basic notation)
Motivation
Defining a set by listing all its elements is only feasible for small sets. But many sets are very large, for example the set of atoms in the universe (1082), or the set of bad horror movies produced after Scream (not quite as big, but too big to write down). Some sets can even be infinite, like the set of natural numbers or just the even natural numbers. If one cannot write down a list of all the elements, just how does on specify such a list?
One could approximate these sets, e.g. by writing \(\left \{ 2, 4, \ldots \right \}\) for the set of natural numbers that are even and greater than \(0\). But this is imprecise because there are many other sets that contain these numbers, for example the set of powers of 2: \(\left \{ 1, 2, 4, 8, 16, \ldots \right \}\). You might object that \(1\) is implicitly excluded because we the set started with \(2\), but that’s just your intuition, not a firm rule. Remember, sets have no order, so a set does not start with anything. And even if we take such human intuitions into account, it’s still too imprecise for more complex cases. Rather than rely on human intuition about what would be a natural interpretation of the ellipsis dots, we can use set-builder notation to succinctly describe large/infinite sets.
Format
Set-builder notation uses the general template
\[ \left \{ \text{expression using variable} \mid \text{definition of variable} \right \} \]
Instead of \(\left \{ 2, 4, 6, \ldots \right \}\) for the set of natural numbers that are both positive and even, one can write the following: \[ \left \{ 2n \mid \text{$n$ a natural number and $n \geq 1$} \right \} \] This means that for every \(n\) that is a natural number and is at least \(1\), the set contains \(2n\).
The table below illustrates this for a few values.
| Value of n | Satisfies definition? | Value of 2n |
|---|---|---|
| 0 | No | - |
| 0.3 | No | - |
| 1 | Yes | 2 |
| 1.7 | No | - |
| 2 | Yes | 4 |
| 3 | Yes | 6 |
For each one of the following finite sets, list all its elements.
There is no limit on the complexity of set-builder notation. For example, one could nest multiple set definitions, as in \(\left \{ \left \{ i \mid 0 \leq i \leq n \right \} \mid n \text{ a natural number} \right \}\). This is a set that contains all initial intervals of the natural numbers: \(\left \{ \left \{ 0 \right \}, \left \{ 0,1 \right \}, \left \{ 0,1,2 \right \}, \left \{ 0,1,2,3 \right \}, \ldots \right \}\) (yes, sets can contain other sets, more on that in a later unit). However, such nested definitions are often cumbersome to read, so try to avoid this. Quite generally, definitions should not intimidate or dazzle the reader.
A good definition is as complex as necessary and as simple as possible.
The following definition is more complex because it uses multiple variables and uses the expression to define two values at the same time. But it is still fairly simple and could be used in a definition: \[ \left \{ x^y, y^{10} | 1 \leq x \leq 3, y \in \left \{ 2,7 \right \}, \text{ and } x + y \geq 5 \right \} \]
The table below shows all the values for the variables and the resulting elements of the set.
| \(x\) | \(y\) | \(x + y \geq 5\)? | added \(x^y\) | added \(y^{10}\) |
|---|---|---|---|---|
| 1 | 2 | no | - | - |
| 1 | 7 | yes | 1 | 282,475,249 |
| 2 | 2 | no | - | - |
| 2 | 7 | yes | 128 | 282,475,249 |
| 3 | 2 | yes | 9 | 1024 |
| 3 | 7 | yes | 2187 | 282,475,249 |
For each one of the following, put \(=\) or \(\neq\) in the gap as appropriate:
- \(\left \{ 0,1,2,3,4,5 \right \} \_ \left \{ 10 - x \mid x \in \left \{ 5,6,7,8,9,10 \right \} \right \}\)
- \(\emptyset \_ \left \{ x \mid x \text{ is both a square and circle} \right \}\)
- \(\left \{ 2,3,5,7 \right \} \_ \left \{ n + 1 \mid n \text{ is a prime number between 0 and 10} \right \}\)
Express the following in terms of set-builder notation:
- \(\left \{ \text{George Washington}, \text{John Adams}, \text{Thomas Jefferson} \right \}\)
- \(\left \{ \text{a}, \text{e}, \text{i}, \text{o}, \text{u} \right \}\)
Recap
- The empty set, denoted \(\emptyset\), contains no elements at all.
- Set-builder notation uses the format \(\left \{ \text{expression using variable(s)} \mid \text{definition of variable(s)} \right \}\).
Let \(A\) and \(B\) be arbitrary sets.
- The union of \(A\) and \(B\) is \(A \cup B \mathrel{\mathop:}=\left \{ x \mid x \in A \text{ or } x \in B \right \}\).
- The intersection of \(A\) and \(B\) is \(A \cap B \mathrel{\mathop:}=\left \{ x \mid x \in A \text{ and } x \in B \right \}\).
- The relative complement of \(A\) and \(B\) is \(A - B \mathrel{\mathop:}=\left \{ x \mid x \in A \text{ and } x \notin B \right \}\).
- If \(A\) is clear from context, we just write \(\overline{B}\) for \(A - B\) and call it the complement of \(B\).