4.1: Sets

Informally, a set is a bunch of objects, which are called the elements of the set. The elements of a set can be just about anything: numbers, points in space, or even other sets. The conventional way to write down a set is to list the elements inside curly-braces. For example, here are some sets:

\[\begin{aligned}A &= \{\text{Alex, Tippy, Shells, Shadow}\} & \text{dead pets} \\ B &= \{\text{red, blue, yellow}\} & \text{primary colors} \\ C &= \{\{a, b\}, \{a, c\}, \{b, c\}\} & \text{a set of sets} \end{aligned}\]

This works fine for small finite sets. Other sets might be defined by indicating how to generate a list of them:

\[\begin{aligned}D &::= \{1, 2, 4, 8, 16, \ldots\} & \text{the powers of 2} \end{aligned}\]

The order of elements is not significant, so \(\{x, y\} \text{ and } \{y, x\}\) are the same set written two different ways. Also, any object is, or is not, an element of a given set— there is no notion of an element appearing more than once in a set.¹ So, writing \(\{x, x\}\) is just indicating the same thing twice: that \(x\) is in the set. In particular, \(\{x, x\} = \{x\}.\)

The expression \(e \in S\) asserts that \(e\) is an element of set \(S\). For example, \(32 \in D\) and blue \(\in B\), but Tailspin \(\notin A\)—yet.

Sets are simple, flexible, and everywhere. You’ll find some set mentioned in nearly every section of this text.

Some Popular Sets

Mathematicians have devised special symbols to represent some common sets.

\[\nonumber \begin{array}[lll] & \textbf{symbol} & \textbf{set} & \textbf{elements} \\ \emptyset & \text{the empty set} & \text{none} \\ \mathbb{N} & \text{nonnegative integers} & \{0, 1, 2, 3, \ldots\}\\ \mathbb{Z} & \text{integers} & \{\ldots, -3, -2, -1, 0, 1, 2, 3, \ldots\}\\ \mathbb{Q} & \text{rational numbers} & \{\frac{1}{2}, \frac{-5}{3}, 16, \text{etc}.\}\\ \mathbb{R} & \text{real numbers} & \{\pi, e, -9, \sqrt{2}, \text{etc}.\}\\ \mathbb{C} & \text{complex numbers} & \{i, \frac{19}{2}, \sqrt{2} - 2i, \text{etc}.\} \end{array}\]

A superscript "\(^+\)" restricts a set to its positive elements; for example, \(\mathbb{R}^+\) denotes the set of positive real numbers. Similarly, \(\mathbb{Z}^-\) denotes the set of negative integers.

Comparing and Combining Sets

The expression \(S \subseteq T\) indicates that set \(S\) is a subset of set \(T\), which means that every element of \(S\) is also an element of \(T\). For example, \(\mathbb{N} \subseteq \mathbb{Z}\) because every nonnegative integer is an integer; \(\mathbb{Q} \subseteq \mathbb{R}\) because every rational number is a real number, but \(\mathbb{C} \nsubseteq \mathbb{R}\) because not every complex number is a real number.

As a memory trick, think of the “\(\subseteq\)” symbol as like the “\(\leq\)” sign with the smaller set or number on the left hand side. Notice that just as \(n \leq n\) for any number \(n\), also \(S \subseteq S\) for any set \(S\).

There is also a relation, \(\subset\), on sets like the “less than” relation < on numbers. \(S \subset T\) means that \(S\) is a subset of \(T\), but the two are not equal. So just as \(n \nless n\) for every number \(n\), also \(A \not \subset A\), for every set \(A\). “\(S \subset T\) ” is read as “\(S\) is a strict subset of \(T\).”

There are several basic ways to combine sets. For example, suppose

\[\begin{aligned} X &::= \{1, 2, 3\},\\ Y &::= \{2, 3, 4\}.\end{aligned}\]

Definition \(\PageIndex{1}\)

• The union of sets \(A\) and \(B\), denoted \(A \cup B\), includes exactly the elements appearing in \(A\) or \(B\) or both. That is,

\[\nonumber x \in A \cup B \text{ IFF } x \in A \text{ OR } x \in B.\]

So \(X \cup Y = \{1, 2, 3, 4\}.\)

• The intersection of sets \(A\) and \(B\), denoted \(A \cap B\), consists of all elements that appear in both \(A\) and \(B\) or both. That is,

\[\nonumber x \in A \cap B \text{ IFF } x \in A \text{ AND } x \in B.\]

So \(X \cap Y = \{2, 3\}.\)

• The set difference of sets \(A\) and \(B\), denoted \(A - B\), consists of all elements that are in \(A\), but not in \(B\) or both. That is,

\[\nonumber x \in A - B \text{ IFF } x \in A \text{ AND } x \notin B.\]

So \(X - Y = \{1\} \text{ and } Y - X = \{4\}.\)

Often all the sets being considered are subsets of a known domain of discourse, \(D\). Then for any subset, \(A\), of \(D\), we define \(\overline{A}\) to be the set of all elements of \(D\) not in \(A\). That is,

\[\nonumber \overline{A} ::= D - A.\]

The set \(\overline{A}\) is called the complement of \(A\). So

\[\nonumber \overline{A} = \emptyset \text{ IFF } A = D.\]

For example, if the domain we’re working with is the integers, the complement of the nonnegative integers is the set of negative integers:

\[\nonumber \mathbb{\overline{N}} = \mathbb{Z}^-.\]

We can use complement to rephrase subset in terms of equality

\[ \nonumber A \subseteq B \text{ is equivalent to } A \cap \overline{B} = \emptyset .\]

Power Set

The set of all the subsets of a set, \(A\), is called the power set, pow(\(A\)), of \(A\). So

\[\nonumber B \in \text{pow}(A) \text{ IFF } B \subseteq A.\]

For example, the elements of pow\((\{1, 2\})\) are \(\emptyset, \{1\}, \{2\}, \text{ and } \{1, 2\}.\)

More generally, if \(A\) has \(n\) elements, then there are \(2^n\) sets in pow\((A)\)—see Theorem 4.5.5. For this reason, some authors use the notation \(2^A\) instead of pow\((A)\).

Set Builder Notation

An important use of predicates is in set builder notation. We’ll often want to talk about sets that cannot be described very well by listing the elements explicitly or by taking unions, intersections, etc., of easily described sets. Set builder notation often comes to the rescue. The idea is to define a set using a predicate; in particular, the set consists of all values that make the predicate true. Here are some examples of set builder notation:

\[\begin{aligned} A &::= \{n \in \mathbb{N} \mid n \text{ is a prime and } n = 4k + 1 \text{ for some integer } k\}\\ B &:= \{x \in \mathbb{R} \mid x^3 - 3x + 1 > 0\} \\ C &::= \{a + bi \in \mathbb{C} \mid a^2 + 2b^2 \leq 1\} \end{aligned}\]

The set \(A\) consists of all nonnegative integers \(n\) for which the predicate

\[\nonumber “n \text{ is a prime and } n = 4k + 1 \text{ for some integer } k”\]

is true. Thus, the smallest elements of \(A\) are:

\[\nonumber 5, 13, 17, 29, 37, 41, 53, 61, 73, \ldots\]

Trying to indicate the set \(A\) by listing these first few elements wouldn’t work very well; even after ten terms, the pattern is not obvious! Similarly, the set \(B\) consists of all real numbers \(x\) for which the predicate

\[\nonumber x^3 - 3x + 1 > 0\]

is true. In this case, an explicit description of the set \(B\) in terms of intervals would require solving a cubic equation. Finally, set \(C\) consists of all complex numbers a C bi such that:

\[\nonumber a^2 + 2b^2 \leq 1\]

This is an oval-shaped region around the origin in the complex plane.

Providing Set Equalities

Two sets are defined to be equal if they have exactly the same elements. That is, \(X = Y\) means that \(z \in X\) if and only if \(z \in Y\), for all elements, \(z\).² So, set equalities can be formulated and proved as “iff” theorems. For example:

Theorem \(\PageIndex{2}\)

[Distributive Law for Sets] Let \(A, B, \) and \(C\) be sets. Then:

\[\label{4.1.1} A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\]

Proof

The equality (\ref{4.1.1}) is equivalent to the assertion that

\[\label{4.1.2} z \in A \cap (B \cup C) \text{ iff } z \in (A \cap B) \cup (A \cap C)\]

for all \(z\). Now we’ll prove (\ref{4.1.2}) by a chain of iff’s.

Now we have

\[\begin{aligned} z &\in A \cap (B \cup C)  \\  &\text{iff } (z \in A) \text{ AND } (z \in B \cup C) & (\text{def of } \cap) \\ &\text{iff } (z \in A) \text{ AND } (z \in B \text{ OR } z \in C) & (\text{def of } \cup) \\ &\text{iff }  (z \in A \text{ AND } z \in B) \text{ OR } (z \in A \text{ AND } z \in C) & (\text{AND distributivity Thm 3.4.1}) \\ &\text{iff } (z \in A \cap B) \text{ OR } (z \in A \cap C) & (\text{def of } \cap)\\ &\text{iff } z \in (A \cap B) \cup (A \cap C) & (\text{def of } \cup) \\ & & \quad \blacksquare \end{aligned}\]

Although the basic set operations and propositional connectives are similar, it’s important not to confuse one with the other. For example, \(\cap\) resembles \(text{OR}\), and in fact was defined directly in terms of \(text{OR}\):

\[\nonumber x \in A \cup B \text{ is equivalent to } (x \in A \text{ OR } x \in B).\]

Similarly, \(\cap\) resembles \(\text{AND}\), and complement resembles \(\text{NOT}\).

But if \(A\) and \(B\) are sets, writing \(A \text{ AND } B\) is a type-error, since \(\text{AND}\) is an operation on truth-values, not sets. Similarly, if \(P\) and \(Q\) are propositional variables, writing \(P \cup Q\) is another type-error.

The proof of Theorem 4.1.2 illustrates a general method for proving a set equality involving the basic set operations by checking that a corresponding propositional formula is valid. As a further example, from De Morgan’s Law (3.4.8) for propositions

\[\nonumber \text{NOT}(P \text{ AND } Q) \text{ is equivalent to } \overline{P} \text{ OR } \overline{Q}\]

we can derive (Problem 4.5) a corresponding De Morgan’s Law for set equality:

\[\label{4.1.3} \overline{A \cap B} = \overline{A} \cup \overline{B}.\]

Despite this correspondence between two kinds of operations, it’s important not to confuse propositional operations with set operations. For example, if \(X\) and \(Y\) are sets, then it is wrong to write “\(X \text{ AND } Y\)” instead of “\(X \cap Y.\)” Applying \(\text{AND}\) to sets will cause your compiler—or your grader—to throw a type error, because an operation that is only supposed to be applied to truth values has been applied to sets. Likewise, if \(P\) and \(Q\) are propositions, then it is a type error to write “\(P \cup Q\)” instead of “\(P \text{ OR } Q\).”

 

¹It’s not hard to develop a notion of multisets in which elements can occur more than once, but multisets are not ordinary sets and are not covered in this text.

²This is actually the first of the ZFC axioms for set theory mentioned at the end of Section 1.3 and discussed further in Section 7.3.2.