Definition 1.2.1. Empty set.
The empty set (or null set or void set) is the set which contains no elements. It is denoted \(\es\text{.}\) For any object \(x\text{,}\) we always have \(x \notin \es\text{;}\) hence \(\es = \set{ }\text{.}\)
Section 1.2 Describing a set
We really need to be able to describe and define lots of different sets when we are doing mathematics. It must be completely clear from the definition how to answer the question “Is this object in the set or not?”
- “Let \(A\) be the set of even integers between 1 and 13.” — nice and clear.
- “Let \(B\) be the set of tall people in this class room.” — not clear.
More generally if there are only a small number of elements in the set we just list them all out
- “Let \(C = \set{1,2,3}\text{.}\)”
When we write out the list we put the elements inside braces \(\{ \cdot \}\text{.}\) Do not use round, square or angle brackets — those things have other mathematical meanings — we must use braces or “curly brackets” if you like. Not that the order we write things in doesn’t matter
\begin{align*}
C & = \set{1,2,3} = \set{2,1,3} = \set{3,2,1}
\end{align*}
because the only thing we can ask is “Is this object an element of \(C\text{?}\)” We cannot ask more complex questions like “what is the third element of \(C\)” — we require more sophisticated mathematical objects to ask such questions and we’ll might get around to looking at such things later in the course.
Similarly, it doesn’t matter how many times we write the same object in the list
\begin{align*}
C &= \set{1,1,1,2,3,3,3,3,1,2,1,2,1,3} = \set{1,2,3}
\end{align*}
because all we ask is “Is \(1 \in C\text{?}\)”. Not “how many times is 1 in \(C\text{?}\)” (you need a mathematical construction called a multiset to ask and answer this question).
Now — if the set is a bit bigger then we might write do something like this
- \(C = \set{1,2,3,\dots,40}\) the set of all integers between 1 and 40 (inclusive).
- \(A = \set{1,4,9,16,\dots}\) the set of all positive square integers
The “\(\dots\)” (ellipsis) is shorthand for the missing entries and tells us to follow the pattern as long as we can. You must be careful with this as you can easily confuse the reader if the pattern is not clear. That, in turn, that means that your set is not defined sufficiently precisely.
- \(B = \set{3,5,7,\dots }\) — is this all odd primes, or all odd numbers bigger than 1 or prime numbers that differ from a power of 2 by exactly 1?
Only use this where it is completely clear by context. A few extra words can save the reader (and yourself) a lot of confusion.
This is perhaps the most important set — many other important objects in mathematics can be built up from this.
Notice that the empty set is not nothing — you should think of it as an empty bag. Be careful not to confuse it with the empty in the empty bag 11 .
Example 1.2.2.
- \(A = \set{1,2,\es }\) — this set contains three elements; the numbers one and two and the empty set. A set can contain sets.
- \(B = \set{\es }\) — this set is not the empty set — it contains a single element, being the empty set. You can think of this set as being a bag that contains an empty bag.
- \(C = \set{\es, \set{\es } }\) — this set contains two elements; the empty set and the set that contains the empty set (our set \(B\) above).
Now — this is all fine when the set doesn’t contain too many elements. But for infinite sets or even just big sets we can’t do this and instead we have to give the defining rule. For example the set of all positive even numbers we write as
\begin{align*}
S &= \set{x \so x \text{ is even and positive} } = \set{2,4,6,8\dots}
\end{align*}
The second notation is also okay, but you have to be careful to make sure it is completely clear which set you are talking about. The first notation can be read as “\(S\) is the set of elements \(x\) such that \(x\) is even and positive”. This is the standard way of writing a set defined by a rule. This sort of notation is sometimes called set-builder notation.
\begin{align*}
S &= \set{\text{some expression } \so \text{ some rule} } &\text{or}\\
&= \set{\text{a function} \so \text{ a domain}}
\end{align*}
The set of all primes is
\begin{align*}
S &= \set{ p : p \mbox{ is prime} }
\end{align*}
the “:” is read as “such that” or “so that”, and you will also often see
\begin{align*}
S &= \set{ p \st p \mbox{ is prime} } = \set{ p \so p \mbox{ is prime} }
\end{align*}
This author prefers “\(\so\)” since it provides a clear (even physical) demarcation. You should recognise all three notations.
While set-builder notation avoids many problems of clarity, it does not avoid all problems. A very famous example is
\begin{align*}
S \amp = \set{A \so A \not\in A }
\end{align*}
ie. the set of all sets that do not contain themselves. This is a problem, because if \(S \in S\text{,}\) then according to the defining rule, it cannot be. On the other hand, if \(S \not\in S\) then it must be. Hence the rule is ambiguous. This is Russell’s paradox. It is closely related to the sentence
This sentence is false.
One way around these problems is to avoid talking about self-referential objects — but this is way too heavy for the moment, and we should just get back to easier sets 12 .
The empty set is one important set, here are a few more. What follows is not really a formal definition of these sets, rather it is here to remind the reader of some sets that they should already know and to highlight some standard notation that people use to refer to them.
Definition 1.2.3.
Some other important sets.
- Positive integers \(\mathbb{N} = \set{1,2,3,\dots }\) — these are usually called the natural numbers.
- All integers \(\mathbb{Z} = \set{\dots,-2,-1,0,1,2,\dots}\)
- All rational numbers (fractions) \(\mathbb{Q} = \set{ \frac{a}{b} \so a \in \mathbb{Z}, b \in \mathbb{N} }\)
- All real numbers \(\mathbb{R}\)
- Irrational numbers \(\mathbb{I}\) = real numbers that are not rational. Examples of this are \(\sqrt{2}, \sqrt{3}, \pi, e\text{.}\) Hence \(\sqrt{2} \in \mathbb{R}\) and \(\sqrt{2} \notin \mathbb{Q}\text{,}\) so \(\sqrt{2} \in \mathbb{I}\) (we’ll get around to proving this later in the text).
Here are some points to note about the above definition.
- Unfortunately there is often confusion as to whether or not zero should be included in the set of “natural numbers”. This text will not include zero as is, in the experience of the authors at least, the more common mathematical convention. If you work in formal logic, set theory or computer science, then often zero is included in the set. The number zero has an interesting history in mathematics and the reader should search-engine their way to articles on that history. Often its use in mathematics was complicated by the question “how can nothing be something?”
- We can also define the set of rational numbers as \(\mathbb{Q} = \set{ \frac{a}{b} \so a,b \in \mathbb{Z}, b \neq 0 }\text{.}\) The authors prefer the one given in the definition; it feels a little “cleaner” in that we represent a third as \(\frac{1}{3}\) rather than \(\frac{-1}{-3}\text{.}\) Of course, we can also represent \(\frac{1}{3} = \frac{2}{6}\text{.}\) We discuss this more in Example 9.2.7.
- We must use “blackboard bold” to denote these sets.\begin{align*} \mathbb{N} &\neq N, &\mathbb{R} &\neq R. \end{align*}Notice here, these are not written in a normal bold font, but rather they are written in “blackboard bold” so that certain lines, usually the vertical ones, are doubled. This style of writing came from the need to distinguish between regular and bold face letters when writing on blackboards (as mathematicians are want to do). It eventually became standard notation both on boards and in print. Since it is now quite standard notation, please learn it and use it. Do not confuse the reader.
- Also note that \(\mathbb{I}\) is not a very standard notation (though we might use it from time to time in this text) — the others are standard. This is in part because the set of irrational numbers has some pretty ugly properties — it is not closed under addition or multiplication; you can take two irrational numbers and add them to get a rational number; you can take two irrational numbers and multiply them to get a rational number. The other sets are closed under addition and multiplication.
So now using these as standard sets we can start to build more interesting things
- Even integers\begin{align*} E &= \set{ n \so n \text{ is an even integer} }\\ &= \set{n \so n =2k \text{ for some } k \in \mathbb{Z} }\\ &= \set{2n \so n \in \mathbb{Z} } \end{align*}
- Square integers \(S = \set{n^2 \so n \in \mathbb{Z} }\text{.}\)
One obvious question that one can ask about a set is “How many elements are there in it?” — there is quite a bit more to this question than you might think.
Definition 1.2.4.
For a set \(S\) we write \(|S|\) to denote the cardinality of \(S\) or its cardinal number. For finite sets, \(|S|\) is just the the number of elements in \(S\text{.}\) We extend this concept to infinite sets in Chapter 12.
Hence \(|\es| = 0\text{,}\) and \(| \set{ 1,2,\set{\es } }| = 3\text{.}\) For (small) finite sets we can just list things out, but for larger sets it gets very difficult very quickly, and for infinite sets things become very weird. One thing we will study in this course is the size of sets — in particular we show that
- \(\displaystyle |\mathbb{N}| = | \mathbb{Z}|\)
- \(\displaystyle |E| = |\mathbb{Z}|\)
- \(\displaystyle |\mathbb{Z}| = |\mathbb{Q}|\)
- \(\displaystyle |\mathbb{Z}| \lt | \mathbb{R}|\)
These statements are really very strange and we need to build up some mathematical infrastructure to make sense of them. Notice that the first and second statement tell us that there are two infinite sets (positive integers and all integers), where one is a strict subset of the other, but they are actually the same size! The last statement is even stranger — it tells us that there are two infinite sets (integers and reals) that are definitely not the same size. This implies that there is more than one sort of infinity. Before we are done we will actually prove that there are an infinite number of different infinities!
This potential confusion is akin to that caused by the number zero. How can something, that is “0”, denote nothing? We recommend taking a little digression into this topic (with digressions into Parmenides, Leucippus, Democritus, Zeno, horror vacui, and many other topics) with your favourite search engine.
The book “Gödel, Escher, Bach: An Eternal Golden Braid” by Douglas Hofstadter is a wonderful exploration of topics related to Russell’s paradox and much much more.
