Skip to main content
\( \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section4Set Theory

The theory of sets is a language that is well-suited to describing and explaining all types of mathematical structures. Instead of starting with axioms of set theory and deducing from them all of the useful properties of sets, we will provide some set-theoretic concepts used throughout the notes and advanced mathematics. Most mathematicians can do their work without going all the way back to the underlying axioms of set theory and that is what we will do here.

Subsection4.1Basic terminology

Definition4.1

A set is a collection of objects called elements.

We use capital letters, \(A, B, C, \dots\) to denote sets and lower-case letters \(a,b,c, \dots\) to denote elements of the sets. If \(a\) is an element of the set \(A\), we denote it by \(a \in A\). If \(b\) is not an element of the set \(A\), we denote it by \(b \notin A\). In this notes, we are mainly concerned with sets whose elements are mathematical objects such as numbers, functions, etc. Here are some sets that you are familiar with:

  • \(\mathbb{Z}\): the set of all integers.
  • \(\mathbb{Q}\): the set of all rational numbers.
  • \(\mathbb{R}\): the set of all real numbers.

There are two standard ways to describe a set:

  • The extensional method simply lists out all the elements of the set. For example \(S = \{0, 2, 4, 6, 8, 10\}\).
  • The intensional method describes a set by listing the common properties of the elements of the set. For example, \begin{equation*}S = \{n \in \mathbb{Z} \; | \; n \; \textrm{is even }, 0 \leq n \leq 10\}.\end{equation*} By putting "\(\in \mathbb{Z}\)" before the vertical bar, we know that we only concern with integers in this set (and not chairs, cars, etc.) This is called the universe. We read the first brace as "the set of all" and the vertical bar as "such that". So the expression \begin{equation*}S = \{n \in \mathbb{Z} \; | \; n \; \textrm{is even}, 0 \leq n \leq 10\}\end{equation*} is read as the set of all integer \(n\) such that \(n\) is even which is greater than or equal to \(0\) and less than or equal to \(10\). Note that this is the same set as \(S\) in the example in the extensional method. They are both the set of all even integers between \(0\) and \(10\). The general syntax of the intensional method is \begin{equation*}\{\textrm{expression} \in \textrm{universe} \; | \; \textrm{rule}\}.\end{equation*}
Definition4.2

Two sets are equal if they contain exactly the same elements.

For example, the set \(\{0,2\}\) is equal to the set \(\{2,0\}\). Note that the order we describe the elements in each case are different but that does not prevent these two sets from having exactly the same elements. Order is irrelevant when we determine if two sets are equal. Also the set \(\{0,2,2\}\) is equal to the set \(\{0,2\}\). Even though the element \(2\) has been repeated twice in the first set, it is still the case that the two sets have the same elements.

Definition4.7

The set that contains no elements is called the empty set, denoted by \(\emptyset\).

If we think of a set as a box containing some stuff, then the empty set is a box with nothing in it.

Subsection4.2Subsets

Let \(A\) and \(B\) be two sets. We say that \(A\) is a subset of \(B\) provided that every element of \(A\) is an element of \(B\). We denote it by \(A \subset B\).

Definition4.10

Let \(A\) and \(B\) be two sets. If \(A\) is a subset of \(B\) and \(A\) and \(B\) are not equal, we say that \(A\) is a proper subset of \(B\). We denote it by \(A \subsetneq B\).

Proof

Let \(A\) and \(B\) be two sets. Recall that \(A\) and \(B\) are equal provided that they have exactly the same elements. As a result, we may say that \(A = B\) if and only if \(A \subset B\) and \(B \subset A\). Here is what the general structure for proof of \(A = B\) looks like.

Proof

Subsection4.3Set Operations

We can use set operations to build new sets from old sets.

Definition4.16

Let \(A\) and \(B\) be two sets of some universal set \(U\). The union of \(A\) and \(B\), denoted by \(A \cup B\), is the set that contains all elements in \(A\) and all elements in \(B\). \begin{equation*} A \cup B = \{ x \in U\; | \; x \in A \; \; \textrm{or} \; \; x \in B\}.\end{equation*}

The intersection of \(A\) and \(B\), denoted by \(A \cap B\), is the set that contains elements that are both in \(A\) and in \(B\).\begin{equation*}A \cap B = \{x \in U \; | \; x \in A \; \; \textrm{and} \; \; x \in B\}.\end{equation*} If \(A \cap B = \emptyset\), then we say that \(A\) and \(B\) are disjoint.

The complement of \(A\) in \(U\), denoted by \(A^C\), is the set that contains all elements in \(U\) but not in \(A\).\begin{equation*}A^C = \{x \in U \; | \; x \notin A\}.\end{equation*}

Can you see how \(\cup\) is related to \(\lor\), how \(\cap\) is related to \(\land\), and how \({\cdot}^C\) is related to \(\sim\)?

We can use the so-called Venn diagrams to visually describe the constructions. The shaded region of each diagram shows the visual description of the set described below the diagram.

<<SVG image is unavailable, or your browser cannot render it>>

Figure4.18\(A \cup B\)

<<SVG image is unavailable, or your browser cannot render it>>

Figure4.19\(A \cap B\)

<<SVG image is unavailable, or your browser cannot render it>>

Figure4.20\(A^C\)

Venn diagram can be very useful when you try to understand a set-theoretical statement or even get the essence of why the statement might be true. But a Venn diagram is not a substitute for a rigorous proof. You can use Venn diagrams to guide your thinking but simply drawing a Venn diagram does not constitute a proof.

(Can you give a similar version in logic and convince yourself that it is true as well?)

(Can you see the resemblance of the DeMorgan's Law of sets and the DeMorgan's Law of logic in Task 2.36?)

Subsection4.4Power Sets and Product Sets

Definition4.27

Let \(S\) be a set. The power set of \(S\), denoted by \(P(S)\), is the set of all subsets of \(S\).

\(\in S\) \(\subset S\) \(\in P(S)\) \(\subset P(S)\)
\(1\)
\(\{1\}\)
\(\mathbb{Z}\)
\(-1,\{1\}\)
\(\{-1,1\}\)
\(\{-1,\{1\}\}\)
Table4.29Fill in the table with T or F
Definition4.33

Let \(A\) and \(B\) be two sets. the product of \(A\) and \(B\) is \begin{equation*}A \times B = \{(a,b) \; | \; a \in A, b\in B\}.\end{equation*} We read \(A \times B\) as "\(A\) cross \(B\)".

Subsection4.5Russell's Paradox

The definition of a set has a flaw. The fact that we can describe a collection of things does not guarantee that the object we have described is a set! For instance, we may be able to think about the collection of all possible sets, but this collection cannot itself be considered a set without leading to paradox. First let us consider a riddle.

The riddle has good answer. It is simply a colloquial rendition of a set-theoretic paradox universally called Russell's paradox after the British mathematician Bertrand Russell, who formulated it. Before we present Russell's paradox, we need a definition.

Definition4.38

A set \(S\) is said to be ordinary if \(S \notin S\).

For example, if \(S\) is the set of all chairs, then \(S \notin S\) because \(S\) itself is not a chair. So the set of all chairs is ordinary. Here is an example of a non-ordinary set. If \(T\) is the collection of all abstract ideas, then \(T\) itself is an abstract idea. Thus \(T \in T\).

Eventually, two German mathematicians Ernst Zermelo and Abraham Fraenkel got this settled. Basically, they came up with a list of axioms for set theory that rules out the possibility of Russell's paradox or any paradoxes of the same nature. This is called the Zermelo-Fraenkel set theory and it is the most common foundation of mathematics.