Sets

Nearly all of modern mathematics is written in the language of sets. Numbers, functions, spaces and structures are described as sets, or as sets equipped with extra data. This topic covers the working vocabulary: how sets are described, compared and combined, and how they are used to build new objects.

The approach is naive: a set is taken to be an intuitively understood collection. That is enough for everyday mathematics, and a later section explains where care is needed.

Conventions

$\mathbb{N} = \{1, 2, 3, \dots\}$ is the set of positive integers, and $\mathbb{N}_0 = \{0, 1, 2, \dots\}$ also includes 0. Many authors instead include 0 in $\mathbb{N}$ .
$A \subseteq B$ means $A$ is a subset of $B$ , and $A \subsetneq B$ means a proper subset. The symbol $\subset$ is avoided because authors use it for either meaning.
Set-builder notation uses a colon, as in $\{x \in A : P(x)\}$ . The form $\{x \in A \mid P(x)\}$ is a common alternative.
A complement $A^c$ is always taken relative to a stated universe $U$ , a fixed set of which all the sets under discussion are subsets.
$\lvert A \rvert$ is the number of elements of a finite set $A$ , used informally here.
Intervals of real numbers use a square bracket for an included endpoint and a parenthesis for an excluded one: $[a, b] = \{x \in \mathbb{R} : a \le x \le b\}$ , $(a, b) = \{x \in \mathbb{R} : a < x < b\}$ , and $[a, \infty) = \{x \in \mathbb{R} : x \ge a\}$ ; $[a, b)$ and $(a, b]$ are mixed cases. Context distinguishes the interval $(a, b)$ from the ordered pair $(a, b)$ .
Other common notations are $2^A$ for $\mathcal{P}(A)$ , $\bar{A}$ or $A'$ for $A^c$ , $A - B$ for $A \setminus B$ , and $A \oplus B$ for $A \mathbin{\triangle} B$ .
Families are written $(A_i)_{i \in I}$ , and $\{A_i\}_{i \in I}$ is a common alternative.
” $A$ contains $x$ ” means $x \in A$ , though some authors also say that $A$ contains $B$ when $B \subseteq A$ .
A disjoint union here is the union of a pairwise disjoint family. The term also commonly names a construction that makes any family disjoint by tagging each element with its index, $\bigcup_{i \in I} (\{i\} \times A_i)$ .

Builds on

Informal familiarity with numbers, with proof by induction, and with reading mathematical statements, including “if and only if”, “for all” and “there exists”.

Sets and membership

Definition 1 (Set)

A set is a collection of objects, called its elements. We write $x \in A$ if $x$ is an element of $A$ , and $x \notin A$ otherwise.

A set is determined entirely by which elements it has.

Definition 2 (Equality of sets)

Sets $A$ and $B$ are equal, written $A = B$ , if they have exactly the same elements: for every $x$ , we have $x \in A$ if and only if $x \in B$ .

Small sets can be described by listing their elements between braces. Since only membership matters, order and repetition make no difference: $\{1, 2, 2\} = \{2, 1\}$ .

The standard number sets are the natural numbers $\mathbb{N}$ , the integers $\mathbb{Z}$ , the rational numbers $\mathbb{Q}$ and the real numbers $\mathbb{R}$ .

Larger sets are usually described by a property.

Definition 3 (Set-builder notation)

For a set $A$ and a property $P$ , the set $\{x \in A : P(x)\}$ consists of those elements $x$ of $A$ for which $P(x)$ holds.

A related form gives a pattern for the elements, with variables ranging over existing sets: $\{t(x) : x \in A\}$ consists of the values of the expression $t(x)$ as $x$ ranges over $A$ , and similarly with several variables.

Example 4

$\{n \in \mathbb{Z} : n = 2k \text{ for some } k \in \mathbb{Z}\}$ is the set of even integers, and $\{x \in \mathbb{R} : x^2 = -1\}$ has no elements. In the pattern form, the even integers are $\{2k : k \in \mathbb{Z}\}$ .

Definition 5 (Empty set)

The empty set $\emptyset$ is the set with no elements.

There is only one empty set, since any two sets without elements have the same elements. Sets can themselves be elements of sets, so $\emptyset$ and $\{\emptyset\}$ are different: the first has no elements, while the second has one.

Subsets

Definition 6 (Subset)

$A$ is a subset of $B$ , written $A \subseteq B$ , if every element of $A$ is an element of $B$ . It is a proper subset, written $A \subsetneq B$ , if also $A \ne B$ . The relation $\subseteq$ is called inclusion.

Example 7

Membership and inclusion are different relations. For $B = \{1, \{2\}\}$ , we have $\{2\} \in B$ but $\{2\} \not\subseteq B$ , since $2 \notin B$ . We also have $\{1\} \subseteq B$ but $\{1\} \notin B$ .

Proposition 8 (Basic properties of subsets)

For all sets $A$ , $B$ and $C$ :

$\emptyset \subseteq A$ ;
$A \subseteq A$ ;
if $A \subseteq B$ and $B \subseteq C$ , then $A \subseteq C$ .

Proof

A counterexample to (1) would be an element of $\emptyset$ that is not in $A$ . Since $\emptyset$ has no elements, there is none, so the statement holds vacuously. For (2), every element of $A$ is an element of $A$ . For (3), if $x \in A$ , then $x \in B$ because $A \subseteq B$ , and so $x \in C$ because $B \subseteq C$ .

Proposition 9 (Double inclusion)

$A = B$ if and only if $A \subseteq B$ and $B \subseteq A$ .

Proof

Each side says that $x \in A$ and $x \in B$ imply one another for every $x$ .

Remark 10

This is the standard way to prove that two sets are equal. Take an arbitrary $x \in A$ and show $x \in B$ , then take an arbitrary $x \in B$ and show $x \in A$ .

Operations on sets

Definition 11 (Union and intersection)

The union $A \cup B$ is the set of $x$ with $x \in A$ or $x \in B$ , where “or” includes the case of both. The intersection $A \cap B$ is the set of $x$ with $x \in A$ and $x \in B$ . Sets $A$ and $B$ are disjoint if $A \cap B = \emptyset$ .

Definition 12 (Difference and symmetric difference)

The difference is $A \setminus B = \{x \in A : x \notin B\}$ . The symmetric difference is $A \mathbin{\triangle} B = (A \setminus B) \cup (B \setminus A)$ , the set of elements belonging to exactly one of $A$ and $B$ .

Definition 13 (Complement)

If $A \subseteq U$ , the complement of $A$ in the universe $U$ is $A^c = U \setminus A$ .

Four Venn diagrams of two overlapping circles A and B, shading the union, the intersection, the difference A minus B, and the symmetric difference

Example 14

For $A = \{1, 2, 3\}$ and $B = \{3, 4\}$ , we get $A \cup B = \{1, 2, 3, 4\}$ , $A \cap B = \{3\}$ , $A \setminus B = \{1, 2\}$ , $B \setminus A = \{4\}$ and $A \mathbin{\triangle} B = \{1, 2, 4\}$ .

Claims about sets often reduce to logic, because $\cup$ and $\cap$ correspond to “or” and “and”, and, within a universe, complement corresponds to “not”.

Theorem 15 (Algebraic laws)

For all sets $A$ , $B$ and $C$ :

$A \cup B = B \cup A$ and $A \cap B = B \cap A$ ;
$(A \cup B) \cup C = A \cup (B \cup C)$ and $(A \cap B) \cap C = A \cap (B \cap C)$ ;
$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ and $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$ ;
$A \cup \emptyset = A$ and $A \cap \emptyset = \emptyset$ .

Proof

We prove the first law in (3); the others follow the same pattern. An element $x$ lies in $A \cap (B \cup C)$ if and only if $x \in A$ and either $x \in B$ or $x \in C$ . By the distributive law of logic, this holds if and only if either $x$ is in both $A$ and $B$ , or $x$ is in both $A$ and $C$ . That says exactly that $x \in (A \cap B) \cup (A \cap C)$ .

Proposition 16 (Inclusion and the operations)

For all sets $A$ and $B$ :

$A \cap B \subseteq A \subseteq A \cup B$ ;
the statements $A \subseteq B$ , $A \cup B = B$ and $A \cap B = A$ are equivalent;
if $A$ and $B$ are subsets of a universe $U$ , then $A \setminus B = A \cap B^c$ .

Proof

Statement (1) is immediate from the definitions.

For (2), suppose $A \subseteq B$ . Every element of $A \cup B$ then lies in $B$ , and $B \subseteq A \cup B$ by (1) with $A$ and $B$ interchanged and commutativity, so $A \cup B = B$ . Every element of $A$ also lies in $A \cap B$ , and $A \cap B \subseteq A$ by (1), so $A \cap B = A$ . Conversely, if $A \cup B = B$ , then $A \subseteq A \cup B = B$ . If $A \cap B = A$ , then $A = A \cap B \subseteq B$ , again by (1) with $A$ and $B$ interchanged and commutativity.

For (3), an element $x \in A$ lies in $U$ , so $x \notin B$ if and only if $x \in B^c$ .

Proposition 17 (Complement laws)

For a subset $A$ of a universe $U$ :

$(A^c)^c = A$ ;
$A \cup A^c = U$ ;
$A \cap A^c = \emptyset$ .

Proof

Each $x \in U$ lies in exactly one of $A$ and $A^c$ . All three laws follow, since $A$ , $A^c$ and $(A^c)^c$ are subsets of $U$ .

Theorem 18 (De Morgan's laws)

For subsets $A$ and $B$ of a universe $U$ :

\begin{aligned} (A \cup B)^c &= A^c \cap B^c, \\ (A \cap B)^c &= A^c \cup B^c. \end{aligned}

Proof

For the first law, let $x \in U$ . Then $x \in (A \cup B)^c$ if and only if $x \notin A \cup B$ , which holds if and only if $x \notin A$ and $x \notin B$ . That says exactly that $x \in A^c \cap B^c$ . Both sides are subsets of $U$ , so they are equal.

For the second law, apply the first to $A^c$ and $B^c$ . By the complement laws, this gives $(A^c \cup B^c)^c = (A^c)^c \cap (B^c)^c = A \cap B$ . Taking complements of both sides and using the same laws gives $A^c \cup B^c = (A \cap B)^c$ .

Remark 19

An element-wise argument gives, for any sets $A$ , $B$ and $C$ , the identities $C \setminus (A \cup B) = (C \setminus A) \cap (C \setminus B)$ and $C \setminus (A \cap B) = (C \setminus A) \cup (C \setminus B)$ , with no universe needed.

Adding the sizes of two finite sets counts the elements they share twice, which gives a simple formula for the size of a union.

Proposition 20 (Inclusion-exclusion for two sets)

If $A$ and $B$ are finite, then $\lvert A \cup B \rvert = \lvert A \rvert + \lvert B \rvert - \lvert A \cap B \rvert$ .

Proof

The sum $\lvert A \rvert + \lvert B \rvert$ counts each element of $A \cap B$ twice and every other element of $A \cup B$ once. Subtracting $\lvert A \cap B \rvert$ leaves each element of $A \cup B$ counted once.

Power sets

Definition 21 (Power set)

The power set $\mathcal{P}(A)$ of a set $A$ is the set of all subsets of $A$ .

Example 22

$\mathcal{P}(\{1, 2\}) = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\}$ . Also $\mathcal{P}(\emptyset) = \{\emptyset\}$ , which has one element.

Proposition 23

A finite set with $n$ elements has exactly $2^n$ subsets.

Proof

We use induction on $n$ . The empty set has exactly one subset, and $2^0 = 1$ .

Now suppose every set with $n$ elements has $2^n$ subsets, let $\lvert A \rvert = n + 1$ , choose $a \in A$ and let $A_0 = A \setminus \{a\}$ , which has $n$ elements. The subsets of $A$ not containing $a$ are exactly the subsets of $A_0$ . The subsets containing $a$ are exactly the sets $S \cup \{a\}$ with $S \subseteq A_0$ . Different $S$ give different sets, because $a \notin S$ means that $S = (S \cup \{a\}) \setminus \{a\}$ . By the induction hypothesis, there are $2^n$ of each kind, for a total of $2^{n+1}$ .

Indexed families

We often need to combine many sets at once, such as one set for each natural number.

Definition 24 (Indexed family)

Let $I$ be a set, called the index set. A family of sets $(A_i)_{i \in I}$ assigns a set $A_i$ to each $i \in I$ . Different indices may be assigned the same set, so a family carries more information than the set $\{A_i : i \in I\}$ .

Definition 25 (Union and intersection of a family)

For a family $(A_i)_{i \in I}$ , the union $\bigcup_{i \in I} A_i$ is the set of $x$ with $x \in A_i$ for at least one $i \in I$ . If $I \ne \emptyset$ , the intersection $\bigcap_{i \in I} A_i$ is the set of $x$ with $x \in A_i$ for every $i \in I$ .

Example 26

For $n \in \mathbb{N}$ , let $A_n = [0, 1/n]$ . Then $\bigcup_{n} A_n = [0, 1]$ and $\bigcap_{n} A_n = \{0\}$ . If instead $B_n = (0, 1/n)$ , then $\bigcap_{n} B_n = \emptyset$ . Both intersections rest on the Archimedean property of $\mathbb{R}$ : for every $x > 0$ there is an $n$ with $1/n < x$ .

Remark 27

For an empty index set, the union is $\emptyset$ . The intersection is a problem: every $x$ vacuously belongs to all $A_i$ , and there is no set of everything. So the intersection requires $I \ne \emptyset$ , unless a universe $U$ is fixed, in which case the empty intersection is taken to be $U$ .

Theorem 28 (De Morgan's laws for families)

For a family $(A_i)_{i \in I}$ of subsets of a universe $U$ , with $I \ne \emptyset$ :

\begin{aligned} \Bigl(\bigcup_{i \in I} A_i\Bigr)^c &= \bigcap_{i \in I} A_i^c, \\ \Bigl(\bigcap_{i \in I} A_i\Bigr)^c &= \bigcup_{i \in I} A_i^c. \end{aligned}

Proof

For $x \in U$ , we have $x \notin \bigcup_i A_i$ if and only if there is no $i$ with $x \in A_i$ , which holds if and only if $x \in A_i^c$ for every $i$ . Likewise, $x \notin \bigcap_i A_i$ if and only if $x \notin A_i$ for some $i$ , which holds if and only if $x \in \bigcup_i A_i^c$ . In each law both sides are subsets of $U$ , so they are equal.

Proposition 29 (Inclusion and distributivity for families)

For a family $(A_i)_{i \in I}$ with $I \ne \emptyset$ , a set $B$ and any $j \in I$ :

$\bigcap_{i \in I} A_i \subseteq A_j \subseteq \bigcup_{i \in I} A_i$ ;
$B \cap \bigcup_{i \in I} A_i = \bigcup_{i \in I} (B \cap A_i)$ ;
$B \cup \bigcap_{i \in I} A_i = \bigcap_{i \in I} (B \cup A_i)$ .

Proof

Statement (1) is immediate from the definitions. For (2), $x$ lies in the left side if and only if $x \in B$ and $x \in A_i$ for some $i$ , which says exactly that $x \in B \cap A_i$ for some $i$ . For (3), every $x \in B$ lies in both sides. If $x \notin B$ , then $x$ lies in the left side if and only if $x \in A_i$ for every $i$ , and that holds if and only if $x \in B \cup A_i$ for every $i$ .

Sets that pairwise do not overlap are especially useful, since each element of their union then lies in exactly one of them.

Definition 30 (Pairwise disjoint families and partitions)

A family $(A_i)_{i \in I}$ is pairwise disjoint if $A_i \cap A_j = \emptyset$ whenever $i \ne j$ . A set that is the union of a pairwise disjoint family is called the disjoint union of that family.

A partition of a set $A$ is a set of nonempty subsets of $A$ such that every element of $A$ lies in exactly one of them.

Example 31

The even integers and the odd integers form a partition of $\mathbb{Z}$ , and the intervals $[n, n + 1)$ for $n \in \mathbb{Z}$ form a partition of $\mathbb{R}$ . The sets $\{1, 2\}$ , $\{2, 3\}$ and $\{1, 3\}$ have empty intersection taken all together, but they are not pairwise disjoint.

Ordered pairs and Cartesian products

Sets ignore order, but coordinates and many other constructions depend on it.

Definition 32 (Ordered pair)

An ordered pair $(a, b)$ is an object determined by its first and second entries, in the sense that $(a, b) = (c, d)$ if and only if $a = c$ and $b = d$ .

So $\{1, 2\} = \{2, 1\}$ , but $(1, 2) \ne (2, 1)$ .

Remark 33

Ordered pairs can be built from sets alone. Kuratowski’s definition $(a, b) = \{\{a\}, \{a, b\}\}$ has the required property. Only the property matters in practice, not the particular construction.

Definition 34 (Cartesian product)

The Cartesian product of $A$ and $B$ is $A \times B = \{(a, b) : a \in A \text{ and } b \in B\}$ . More generally, for $n \ge 1$ , an $n$ -tuple $(a_1, \dots, a_n)$ is an object determined by its entries in order, in the sense that $(a_1, \dots, a_n) = (b_1, \dots, b_n)$ if and only if $a_i = b_i$ for every $i$ . The product $A_1 \times \dots \times A_n$ is the set of $n$ -tuples with each $a_i \in A_i$ , and $A^n$ is the product of $n$ copies of $A$ . A 2-tuple is an ordered pair, and $A^1$ is identified with $A$ .

Remark 35

Depending on how tuples are constructed, $((a, b), c)$ and $(a, b, c)$ may or may not be the same object. It is standard to identify them, and so to treat $(A \times B) \times C$ and $A \times B \times C$ as the same set.

Example 36

$\{1, 2\} \times \{x, y\} = \{(1, x), (1, y), (2, x), (2, y)\}$ , and $\mathbb{R}^2$ is the coordinate plane. In general $A \times B \ne B \times A$ , and $A \times \emptyset = \emptyset$ .

Proposition 37

For all sets $A$ , $B$ and $C$ :

$A \times (B \cup C) = (A \times B) \cup (A \times C)$ ;
$A \times (B \cap C) = (A \times B) \cap (A \times C)$ .

The corresponding laws hold with the union or intersection in the first factor.

Proof

Since a pair determines its entries, a pair $(a, b)$ lies in $A \times (B \cup C)$ if and only if $a \in A$ and either $b \in B$ or $b \in C$ . That says exactly that $(a, b)$ lies in $A \times B$ or in $A \times C$ . The other laws are proved the same way.

Proposition 38

If $A$ and $B$ are finite, then $\lvert A \times B \rvert = \lvert A \rvert \, \lvert B \rvert$ .

Proof

For each $a \in A$ , the pairs in $A \times B$ with first entry $a$ are the pairs $(a, b)$ with $b \in B$ . By the defining property of pairs, different $b$ give different pairs, so there are $\lvert B \rvert$ of them, and pairs with different first entries are different. Summing over the $\lvert A \rvert$ elements of $A$ gives the result.

Why naive set theory needs care

It is tempting to assume that every property defines a set. That assumption is inconsistent.

Theorem 39 (Russell's paradox)

There is no set $R$ whose elements are exactly the sets that are not elements of themselves.

Proof

Suppose such an $R$ exists. By its defining property, $R \in R$ if and only if $R \notin R$ , which is a contradiction.

Corollary 40 (No set of all sets)

There is no set that contains every set. In particular, there is no set of everything.

Proof

If $V$ were such a set, then $\{x \in V : x \text{ is a set and } x \notin x\}$ would be the impossible set $R$ .

This is why set-builder notation draws on existing sets, why a complement needs a universe, and why an intersection over an empty index set causes trouble. For the complement, if $\{x : x \notin A\}$ were a set, then its union with $A$ would be a set of everything. Axiomatic systems such as Zermelo-Fraenkel set theory with the axiom of choice (ZFC) state precisely which constructions are allowed. The constructions used in everyday mathematics, including those in this topic, are among them.

Summary

Sets are determined by their elements, so equality ignores order and repetition.
The empty set has no elements, and set-builder notation describes a set by a property of its elements or by a pattern for them.
Membership and inclusion differ: $x \in A$ says $x$ is an element of $A$ , while $A \subseteq B$ says every element of $A$ is an element of $B$ .
Double inclusion is the standard way to prove sets equal.
Union and intersection satisfy the algebraic laws. Complements satisfy the complement laws and De Morgan’s laws, and differences satisfy analogous identities.
The symmetric difference $A \mathbin{\triangle} B$ is the set of elements belonging to exactly one of $A$ and $B$ .
$A \subseteq B$ is equivalent to $A \cup B = B$ and to $A \cap B = A$ .
For finite sets, $\lvert A \cup B \rvert = \lvert A \rvert + \lvert B \rvert - \lvert A \cap B \rvert$ .
The power set of a set is the set of its subsets, and a finite set with $n$ elements has $2^n$ subsets.
An indexed family has a union and, for a nonempty index set, an intersection, and De Morgan’s laws extend to these, as does distributivity.
A family is pairwise disjoint if different indices give disjoint sets, and a partition of a set divides it into nonempty subsets so that each element lies in exactly one.
Ordered pairs remember order, and Cartesian products collect them. Products distribute over union and intersection, and for finite sets $\lvert A \times B \rvert = \lvert A \rvert \, \lvert B \rvert$ .
Russell’s paradox shows that not every property defines a set.

Conventions

Builds on

Sets and membership

Subsets

Operations on sets

Power sets

Indexed families

Ordered pairs and Cartesian products

Why naive set theory needs care

Summary

Referenced by