Skip to main content

Foundations of Advanced Mathematics

Sam Macdonald

Section 3.1 Set Basics

Subsection Sets and Notation

In the present chapter we will discuss the common basis for all systems of axioms used in contemporary mathematics, which is set theory. Though of surprisingly recent vintage, having been developed by Georg Cantor in the late nineteenth century, set theory has become widely accepted among mathematicians as the starting place for rigorous mathematics. We will take an intuitive approach to set theory (often referred to as “naive set theory”), but then build on it rigorously.

Convention 3.1.

A set is a well-defined collection of objects that can be thought of as a single entity itself.
The most basic way of specifying the elements of a set is to list the elements of that set. This works well when the set contains only a small number of objects. The usual practice is to list these elements between braces.

Example 3.2.

  • Natural Numbers.
    the set of natural numbers
    \begin{equation*} \{1, 2, 3, \dots\}\text{,} \end{equation*}
    denoted \(\N\text{;}\)
  • Integers.
    the set of integers
    \begin{equation*} \{\dots, -2, -1, 0, 1, 2, \dots\}\text{,} \end{equation*}
    denoted \(\Z\text{;}\)
  • Rational Numbers.
    the set of rational numbers, denoted \(\Q\text{,}\) which is the set of fractions;
  • Real Numbers.
    the set of real numbers, denoted \(\R\text{,}\) which is the set of all the numbers that are informally thought of as forming the number line.

Example 3.3. Empty Set.

An extremely valuable set we will regularly encounter is the empty set (also called the null set) which is the set that does not have any elements in it. That is, the empty set is the set \(\{ \}\text{.}\) This set is denoted \(\emptyset\text{.}\)
It may seem strange to consider a set that doesn't have anything in it, but the role of the empty set in set theory is somewhat analogous to the role of zero in arithmetic.

Convention 3.4. Set Builder Notation.

Sometimes it is not possible to list all the elements of a set. In this case, it is sometimes convenient to use the so-called set builder notation in which the set is defined by stating a rule that all elements of the set must satisfy. If P .x/ is a predicate in the variable x, then the notation stands for the set of all elements x in the universal set U for which P .x/ is true. If it is clear what set is being used for the universal set, this notation is sometimes shortened to fx j P .x/g. This is usually read as “the set of all x such that P .x/.” The vertical bar stands for the phrase “such that.” Some writers will use a colon (:) instead of the vertical bar.

Subsection Subsets and Set Equality

Definition 3.5.

Let \(A\) and \(B\) be sets. The set \(A\) is a subset of the set \(B\text{,}\) denoted \(A \subseteq B\text{,}\) if \(x\in A\) implies \(x\in B\text{.}\) If \(A\) is not a subset of \(B\text{,}\) we write \(A not\subseteq B\text{.}\)

Structure 3.6. Subset Proof.

There is a standard strategy for proving a statement of the form “\(A \subseteq B\text{,}\)” which is to take an arbitrary element \(a\in A\text{,}\) and then to use the definitions of \(A\) and \(B\) to deduce that \(a\in B\text{.}\) Such a proof typically has the following form.
Proof. Let \(a\in A\text{.}\) ... (argumentation) ... Then \(a\in B\text{.}\) Hence \(A \subseteq B\text{.}\)

Remark 3.7.

It is important to distinguish between the notion of an object being an element of a set, and the notion of a set being a subset of another set. For example, let \(A =\{a, b, c\}\text{.}\) Then \(a\in A\) and \(\{a\} \subseteq A\) are true, whereas the statements “\(a \subseteq A\)” and “\(\{a\}\in A\)” are false. Also, observe that a set can be an element of another set. Let \(B = \{\{a\}, b, c\}\text{.}\) Observe that \(B\) is not the same as the set \(A\text{.}\) Then \(\{a\}\in B\) and \(\{\{a\}\} \subseteq B\) are true, but “\(a\in B\)” and “\(\{a\} \subseteq B\)” are false.
  1. To show that \(A \subseteq A\text{,}\) we start by choosing an arbitrary element \(a\in A\text{,}\) where we think of this “\(A\)” as the one on the left-hand side of the expression “\(A \subseteq A\text{.}\)” It then follows that \(a\in A\text{,}\) where we now think of this “\(A\)” as the one on the right-hand side of the expression “\(A \subseteq A\text{.}\)” Hence \(A \subseteq A\text{,}\) using the definition of subsets.
  2. We give two proofs, because both are instructive. First, we have a direct proof. To show that \(\emptyset \subseteq A\text{,}\) we need to show that if \(a\in\emptyset\text{,}\) then \(a\in A\text{.}\) Because \(a\in\emptyset\) is always false, then the logical implication “if \(a\in\emptyset\text{,}\) then \(a\in A\)” is always true, using the precise definition of the conditional given in Section 1.2.
    Next, we have a proof by contradiction. Suppose that \(\emptyset not\subseteq A\text{.}\) Then there exists some \(x\in\emptyset\) such that \(x /\in A\text{.}\) This statement cannot be true, however, because there is no \(x\) such that \(x\in\emptyset\text{.}\) We have therefore reached a contradiction, and hence the desired result is true.
    This proof by contradiction might not appear to fit the standard outline for such proofs as described in Section 2.3, because it does not appear as if we are viewing the statement being proved as having the form \(P \to Q\text{.}\) In fact, there are two ways of viewing the statement being proved as having this form. For the direct proof given above, we viewed the statement being proved as \((\forall A)([a\in\emptyset] \to [a\in A])\text{.}\) We then chose an arbitrary set \(A\text{,}\) and proved the statement \([a\in\emptyset] \to [a\in A]\text{.}\) For the proof by contradiction, we viewed the statement being proved as “if \(A\) is a set, then \(\emptyset \subseteq A\text{,}\)” and then indeed used our standard method of doing proof by contradiction.
  3. This proof, having no logical tricks, is extremely typical. Let \(a\in A\text{.}\) Because \(A \subseteq B\text{,}\) it follows that \(a\in B\text{.}\) Because \(B \subseteq C\text{,}\) it follows that \(a\in C\text{.}\) Therefore we see that \(a\in A\) implies \(a\in C\text{,}\) and hence \(A \subseteq C\text{.}\)

Definition 3.9. Set Equality.

Let \(A\) and \(B\) be sets. The set \(A\) equals the set \(B\text{,}\) denoted \(A = B\text{,}\) if \(A \subseteq B\) and \(B \subseteq A\text{.}\) The set \(A\) is a proper subset of the set \(B\text{,}\) denoted \(A \subset B\text{,}\) if \(A \subseteq B\) and \(A \neq B\text{.}\)

Convention 3.10.

There is a bit of variation in the mathematical literature for the notation used for proper subsets. Some texts use \(A \subset B\) to mean \(A\) is a proper subset of \(B\text{,}\) whereas others use the notation \(A \subset B\) to mean what we write as \(A \subseteq B\text{.}\)

Structure 3.11. Set Equality Proof.

Proof. Let \(a\in A\text{.}\) ... (argumentation) ... Then \(a\in B\text{.}\) Therefore \(A \subseteq B\text{.}\) Next, Let \(b\in B\text{.}\) ... (argumentation) ... Then \(b\in A\text{.}\) Hence \(B \subseteq A\text{.}\) We conclude that \(A = B\text{.}\)
All three parts of this lemma follow straightforwardly from the definition of equality of sets together with Lemma 3.2.4. Details are left to the reader.
In some situations we will find it useful to look at not just one subset of a given set, but at all subsets of the set. In particular, we can form a new set, the elements of which are the subsets of the given set.

Definition 3.13. Power Set.

Let \(A\) be a set. The power set of \(A\text{,}\) denoted \(\cP(A)\text{,}\) is the set defined by
\begin{equation*} \cP(A) = \{X | X \subseteq A\}\text{.} \end{equation*}

Example 3.14. Power Sets.

  • Because \(\emptyset \subseteq\emptyset\text{,}\) then \(P ( \emptyset) = \{ \emptyset\}\text{.}\) In particular, we see that \(P ( \emptyset) \neq\emptyset\text{.}\)
  • Let \(A = \{a, b, c\}\text{.}\) Then the subsets of \(A\) are \(\emptyset, \{a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\}, \{b, c\} \text{ and }\{a, b, c\}\text{.}\) The last of these subsets is not proper, but we need all subsets, not only the proper ones. Therefore
    \begin{equation*} \cP(A) = \{ \emptyset, \{a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\}, \{b, c\}, \{a, b, c\}\}. \end{equation*}
    It can be seen intuitively that if \(A\) is a finite set with n elements, then \(\cP(A)\) is a finite set with \(2^n\) elements; by Part (1) of this exercise we see that this formula holds even when \(n = 0\text{.}\) This formula is proved in Theorem 7.7.10 (1).
Let \(A\) and \(B\) be sets. Prove that it is not possible that \(A \subset B\) and \(B \subseteq A\) are both true.
<Prev^TopNext>