A first look at the theory of sets

Section 1.1 A first look at the theory of sets

In this course we will be obsessed with different kinds of number. The simplest kinds of numbers are the natural numbers

\begin{equation*} 0, 1, 2, 3, 4, 5, 6, 7, 8, \dots\text{.} \end{equation*}

These are the counting numbers that we know and love. But what exactly are these objects? Can these be defined in more basic terms? There is a lot of philosophical literature about this, but here we're going to stay pretty pragmatic and adopt the most common mathematical attitude toward these objects.

With that attitude, these numbers, whatever they are, are used for counting. We want to be open-minded about what sorts of things we want to count. A notion of number that is only good for counting pebbles wouldn't help us count sheep or trees or meters. We need to be able to count (or try to count, at any rate) any collection of any sort of objects.

A set \(S\) is a collection of objects, which we call the elements of \(S\text{.}\) Those elements can be anything: pebbles, sheep, trees, meters, numbers, letters, animals, other sets \ldots

A note about set theory.

Properly speaking, the term “set” is a primitive notion. Both it and the symbol “\(\in\)” are left undefined, and mathematicians rely on a collection of axioms to reflect their intuitions on how these objects ought to work.

Interestingly, there are lots of different systems of axioms for sets out there, which correspond to different intuitions about how these notions ought to behave. The study of these different axiom systems and their interrelations is part of set theory. Set theory is closely tied to logic.

For now, we are mostly going to stick to a relatively informal discussion of the most widely agreed-upon axioms. These are the Zermelo–Fraenkel axioms of set theory. Most, mathematicians also include one further axiom: the Axiom of Choice.

What we will do here is what is often called naive set theory. We won't worry excessively about formalizing our sets; instead, we'll focus on how to be responsible end-users of sets.

One way of writing down a set is to list them between curly brackets. So the set \(S\) whose only elements are \(1,2,3\) is written as

\begin{equation*} S=\{1,2,3\}\text{.} \end{equation*}

The set whose only elements are Clark and Maggie is written as

\begin{equation*} T=\{\text{ Clark }, \text{ Maggie }\}\text{.} \end{equation*}

As a matter of notation, if \(a\) is an element of the set \(S\text{,}\) we write \(a\in S\text{.}\) We write \(a\not\in S\) if \(a\) is not an element of the set \(S\text{.}\) For example, \(1\in \{1,2,3\}\) but \(4\not\in \{1,2,3\}\text{.}\) Similarly, \(\text{ Clark } \notin \{1,2,3\}\text{,}\) but \(\text{ Clark } \in \{\text{ Clark }, \text{ Maggie }\}\text{.}\)

Sets can contain anything, even other sets. For example, \(S=\{1,\{2\}\}\) is the set consisting of the number \(1\) and also the set \(\{2\}\text{.}\) Thus \(1\in S\text{,}\) and \(\{2\}\in S\text{,}\) but \(2\notin S\text{.}\)

Definition 1.1.1. Subsets.

Let \(A\) and \(B\) be two sets. We say that \(A\) is a subset of \(B\text{,}\) or that \(A\) is contained in \(B\) if and only if every element \(x\in A\) is also an element of \(B\text{.}\) We write \(A \subseteq B\) to say that “\(A\) is a subset of \(B\text{.}\)” If there is an element of \(A\) not in \(B\text{,}\) we write \(A\not\subseteq B\text{.}\)

We say that \(A\) and \(B\) are equal if and only if both \(A \subseteq B\) and \(B \subseteq A\text{.}\)

So two sets are equal if and only if they have the same elements. That means, for instance, that \(\{1,2,3\}\) is the same set as \(\{3,1,2\}\text{.}\) When you're writing down a set, the order in which you list the elements is unimportant.

Question 1.1.2. Listing the subsets of \(\{1,2,3\}\).

How many subsets are there of the set \(\{1,2,3\}\text{?}\) List them.

Answer.

In all there are \(8\) subsets. There's \(\{1,2,3\}\) itself. Then there are the subsets with \(2\) elements: these are \(\{1,2\}\text{,}\) \(\{1,3\}\text{,}\) and \(\{2,3\}\text{.}\) (Note that \(\{2,1\}\) is a set that is already on our list!) Then there are the subsets with \(1\) element (sometimes called singletons): these are \(\{1\}\text{,}\) \(\{2\}\text{,}\) and \(\{3\}\text{.}\)

There is one more subset of \(\{1,2,3\}\text{.}\) This is the set with \(0\) elements. This is called the empty set.

Definition 1.1.3. Empty set.

The empty set, written \(\varnothing\text{,}\) is the set that has no elements.

The empty set \(\varnothing\) has the special property that it is a subset of any other set. That is, if \(A\) is a set, then \(\varnothing \subseteq A\text{.}\)

The empty set is unique: that is, there is only one set with the property that it has no elements. To prove this, let us suppose that \(A\) and \(B\) are each sets with no elements. Then \(A \subseteq B\) and \(B \subseteq A\text{;}\) so we conclude that \(A=B\text{.}\)

Example 1.1.4. Singletons.

If \(p\) is some object we're interested in, then we are always permitted to form the singleton set \(\{p\}\text{.}\) This is the set whose only element is \(p\text{.}\) In other words, \(a \in \{p\}\) if and only if \(a=p\text{.}\)

Definition 1.1.5. Proper subset.

If \(A \subseteq B\) and \(B \not\subseteq A\text{,}\) then we say that \(A\) is properly contained in \(B\text{,}\) and that \(A\) is a proper subset of \(B\text{.}\) Some people write \(A \subset B\) or even \(A \subsetneqq B\) to emphasize this.

Note 1.1.6.

In the next few sections, we will discuss some aspects of logic and set theory. In it, we'll want to give some examples. So, even though we haven't defined them yet, we will regularly appeal to the set of natural numbers

\begin{equation*} \NN_0 = \{0, 1, 2, 3, 4, 5, \dots \} \end{equation*}

as well as the set of positive natural numbers

\begin{equation*} \NN = \{1, 2, 3, 4, 5, \dots \}\text{.} \end{equation*}

We will also refer to the set of integers

\begin{equation*} \ZZ = \{ \dots, -2, -1, 0, 1, 2, \dots \}\text{,} \end{equation*}

the set of rational numbers \(\QQ\text{,}\) and the set of real numbers \(\RR\text{,}\) before we have defined them. Of course, we aren't meant to do this; we want to refer to things only once we've defined them carefully. Please think of examples that make reference to these sets only as intuition-building for now. In a later section, we will define these sets properly, and once we have, you can revisit these examples and see that we have used these objects in entirely respectable ways.