Sets — Read

Reading preferences

Optional display controls need JavaScript. All reading content and navigation work without it.

How to use Read

Read follows the source chapter in ordinary reading order. Mathematics remains native MathML so a compatible screen reader or braille system can navigate its internal structure. Use the small source links for exact provenance.

Extensionality

A set is a collection of objects, considered as a single object. The objects making up the set are called elements or members of the set. If $x$ source 14 is an element of a set $A$ source 14, we write $x \in A$ source 15; if not, we write $x \notin A$ source 15. The set which has no elements is called the empty set and denoted “ $\emptyset$ source 17”.

Definition: Extensionality

If $A$ source 27 and $B$ source 27 are sets, then $A = B$ source 27 iff every element of $A$ source 28 is also an element of $B$ source 28, and vice versa.

source 26

Extensionality licenses some notation. In general, when we have some objects $a_{1}$ source 33, …, $a_{n}$ source 33, then ${a_{1}, \dots, a_{n}}$ source 33 is the set whose elements are $a_{1}, \dots, a_{n}$ source 34. We emphasise the word “the”, since extensionality tells us that there can be only one such set. Indeed, extensionality also licenses the following: ${a, a, b} = {a, b} = {b, a} .$ source 38 This delivers on the point that, when we consider sets, we don't care about the order of their elements, or how many times they are specified.

Example 1

Whenever you have a bunch of objects, you can collect them together in a set. The set of Richard's siblings, for instance, is a set that contains one person, and we could write it as $S = {Ruth}$ source 49. The set of positive integers less than $4$ source 50 is ${1, 2, 3}$ source 50, but it can also be written as ${3, 2, 1}$ source 51 or even as ${1, 2, 1, 2, 3}$ source 51. These are all the same set, by extensionality. For every element of ${1, 2, 3}$ source 53 is also an element of ${3, 2, 1}$ source 53 (and of ${1, 2, 1, 2, 3}$ source 53), and vice versa.

source 46

Frequently we'll specify a set by some property that its elements share. We'll use the following shorthand notation for that: ${x : φ (x)}$ source 60, where the $φ (x)$ source 60 stands for the property that $x$ source 61 has to have in order to be counted among the elements of the set.

Example 2

In our example, we could have specified $S$ source 66 also as $S = {x : x is a sibling of Richard} .$ source 67

source 65

Example 3

A number is called perfect iff it is equal to the sum of its proper divisors (i.e., numbers that evenly divide it but aren't identical to the number). For instance, $6$ source 77 is perfect because its proper divisors are $1$ source 78, $2$ source 78, and $3$ source 78, and $6 = 1 + 2 + 3$ source 78. In fact, $6$ source 79 is the only positive integer less than $10$ source 79 that is perfect. So, using extensionality, we can say: ${6} = {x : x is perfect and 0 \leq x \leq 10}$ source 81 We read the notation on the right as “the set of $x$ source 84's such that $x$ source 84 is perfect and $0 \leq x \leq 10$ source 85”. The identity here confirms that, when we consider sets, we don't care about how they are specified. And, more generally, extensionality guarantees that there is at most one set of $x$ source 88's such that $φ (x)$ source 88. So, once the existence of such a set has been established, extensionality justifies calling ${x : φ (x)}$ source 90 the set of $x$ source 90's such that $φ (x)$ source 90.

source 74

Extensionality gives us a way for showing that sets are identical: to show that $A = B$ source 95, show that whenever $x \in A$ source 95 then also $x \in B$ source 95, and whenever $y \in B$ source 96 then also $y \in A$ source 96.

Exercise 1

Prove that there is at most one empty set, i.e., show that if $A$ source 99 and $B$ source 99 are sets without elements, then $A = B$ source 100.

source 98

Subsets and Power Sets

Definition: Subset

If every element of a set $A$ source 20 is also an element of $B$ source 20, then we say that $A$ source 21 is a subset of $B$ source 21, and write $A \subseteq B$ source 21. If $A$ source 22 is not a subset of $B$ source 22 we write $A ⊈ B$ source 22. If $A \subseteq B$ source 23 but $A \neq B$ source 23, we write $A ⊊ B$ source 23 and say that $A$ source 24 is a proper subset of $B$ source 24.

source 19

Example 4

Every set is a subset of itself, and $\emptyset$ source 28 is a subset of every set. The set of natural even numbers is a subset of the set of natural numbers. Also, ${a, b} \subseteq {a, b, c}$ source 30. But ${a, b, e}$ source 30 is not a subset of ${a, b, c}$ source 31.

source 27

Example 5

The number $2$ source 35 is an element of the set of integers, whereas the set of even numbers is a subset of the set of integers. However, a set may happen to both be an element and a subset of some other set, e.g., ${0} \in {0, {0}}$ source 38 and also ${0} \subseteq {0, {0}}$ source 38.

source 34

Extensionality gives a criterion of identity for sets: $A = B$ source 42 iff every element of $A$ source 43 is also an element of $B$ source 43 and vice versa. The definition of “subset” defines $A \subseteq B$ source 44 precisely as the first half of this criterion: every element of $A$ source 45 is also an element of $B$ source 46. Of course the definition also applies if we switch $A$ source 47 and $B$ source 47: that is, $B \subseteq A$ source 47 iff every element of $B$ source 48 is also an element of $A$ source 48. And that, in turn, is exactly the “vice versa” part of extensionality. In other words, extensionality entails that sets are equal iff they are subsets of one another.

Proposition

$A = B$ source 53 iff both $A \subseteq B$ source 53 and $B \subseteq A$ source 53.

source 52

Now is also a good opportunity to introduce some further bits of helpful notation. In defining when $A$ source 57 is a subset of $B$ source 57 we said that “every element of $A$ source 58 is …,” and filled the “ $\dots$ source 58” with “an element of $B$ source 59”. But this is such a common shape of expression that it will be helpful to introduce some formal notation for it.

Definition

$(\forall x \in A) φ$ source 64 abbreviates $\forall x (x \in A \to φ)$ source 64. Similarly, $(\exists x \in A) φ$ source 65 abbreviates $\exists x (x \in A \land φ)$ source 65.

source 63

Using this notation, we can say that $A \subseteq B$ source 69 iff $(\forall x \in A) x \in B$ source 69.

Now we move on to considering a certain kind of set: the set of all subsets of a given set.

Definition: Power Set

The set consisting of all subsets of a set $A$ source 76 is called the power set of $A$ source 77, written $℘ (A)$ source 77. $℘ (A) = {B : B \subseteq A}$ source 78

source 75

Example 6

What are all the possible subsets of ${a, b, c}$ source 84? They are: $\emptyset$ source 85, ${a}$ source 85, ${b}$ source 85, ${c}$ source 85, ${a, b}$ source 85, ${a, c}$ source 85, ${b, c}$ source 85, ${a, b, c}$ source 86. The set of all these subsets is $℘ ({a, b, c})$ source 87: $℘ ({a, b, c}) = {\emptyset, {a}, {b}, {c}, {a, b}, {b, c}, {a, c}, {a, b, c}}$ source 88

source 83

Exercise 2

List all subsets of ${a, b, c, d}$ source 95.

source 94

Exercise 3

Show that if $A$ source 99 has $n$ source 99 elements, then $℘ (A)$ source 99 has $2^{n}$ source 99 elements.

source 98

Some Important Sets

Example 7

We will mostly be dealing with sets whose elements are mathematical objects. Four such sets are important enough to have specific names: $\begin{matrix} N = {0, 1, 2, 3, \dots} \\ the set of natural numbers \\ Z = {\dots, - 2, - 1, 0, 1, 2, \dots} \\ the set of integers \\ Q = {\frac{m}{n} : m, n \in Z and n \neq 0} \\ the set of rationals \\ R = (- \infty, \infty) \\ the set of real numbers (the continuum) \end{matrix}$ source 16 These are all infinite sets, that is, they each have infinitely many elements.

As we move through these sets, we are adding more numbers to our stock. Indeed, it should be clear that $N \subseteq Z \subseteq Q \subseteq R$ source 30: after all, every natural number is an integer; every integer is a rational; and every rational is a real. Equally, it should be clear that $N ⊊ Z ⊊ Q$ source 33, since $- 1$ source 34 is an integer but not a natural number, and $\frac{1}{2}$ source 35 is rational but not integer. It is less obvious that $Q ⊊ R$ source 36, i.e., that there are some real numbers which are not rational.

We'll sometimes also use the set of positive integers $Z^{+} = {1, 2, 3, \dots}$ source 40 and the set containing just the first two natural numbers $B = {0, 1}$ source 42.

source 12

Example 8: Strings

Another interesting example is the set $A^{*}$ source 47 of finite strings over an alphabet $A$ source 48: any finite sequence of elements of $A$ source 48 is a string over $A$ source 49. We include the empty string $Λ$ source 49 among the strings over $A$ source 50, for every alphabet $A$ source 50. For instance, $\begin{matrix} B^{*} = {Λ, 0, 1, 00, 01, 10, 11, \\ 000, 001, 010, 011, 100, 101, 110, 111, 0000, \dots} . \end{matrix}$ source 51 If $x = x_{1} \dots x_{n} \in A^{*}$ source 56 is a stringReader correction: the source has no space between the displayed formula and ‘is’. This reader restores the space; the source file is unchanged. consisting of $n$ source 56 “letters” from $A$ source 57, then we say the length of the string isReader correction: the source omits ‘the’ before ‘length’. This reader supplies it; the source file is unchanged. $n$ source 57 and write $len (x) = n$ source 58.

source 46

Example 9: Infinite sequences

For any set $A$ source 63 we may also consider the set $A^{ω}$ source 63 of infinite sequences of elements of $A$ source 64. An infinite sequence $a_{1} a_{2} a_{3} a_{4} \dots$ source 65 consists of a one-way infinite list of objects, each one of which is an element of $A$ source 66.

source 62

Unions and Intersections

Explanation

In the Extensionality section, we introduced definitions of sets by abstraction, i.e., definitions of the form ${x : φ (x)}$ source 14. Here, we invoke some property $φ$ source 15, and this property can mention sets we've already defined. So for instance, if $A$ source 16 and $B$ source 16 are sets, the set ${x : x \in A \lor x \in B}$ source 17 consists of all those objects which are elements of either $A$ source 18 or $B$ source 18, i.e., it's the set that combines the elements of $A$ source 19 and $B$ source 19. We can visualize this as in the union diagram, where the highlighted area indicates the elements of the two sets $A$ source 21 and $B$ source 21 together.

The union

A \cup B

source 25 of two sets is the set of elementsReader correction: the source omits ‘the’ before ‘set’ in this caption. This reader supplies it; the source file is unchanged. of

A

source 26 together with those of

B

source 26.

Union of A and B: elements in A or B. The highlighted region contains every element in A or B, including elements in both sets.

Set A: The left boundary.
Set B: The right boundary.
Highlighted region: The highlighted region contains every element in A or B, including elements in both sets.

source 23

This operation on sets—combining them—is very useful and common, and so we give it a formal name and a symbol.

Definition: Union

The union of two sets $A$ source 35 and $B$ source 35, written $A \cup B$ source 35, is the set of all things which are elements of $A$ source 36, $B$ source 36, or both. $A \cup B = {x : x \in A \lor x \in B}$ source 37

source 34

Example 10

Since the multiplicity of elements doesn't matter, the union of two sets which have an element in common contains that element only once, e.g., ${a, b, c} \cup {a, 0, 1} = {a, b, c, 0, 1}$ source 45.

The union of a set and one of its subsets is just the bigger set: ${a, b, c} \cup {a} = {a, b, c}$ source 47.

The union of a set with the empty set is identical to the set: ${a, b, c} \cup \emptyset = {a, b, c}$ source 50.

source 42

Exercise 4

Prove that if $A \subseteq B$ source 55, then $A \cup B = B$ source 55.

source 54

Definition: Intersection

The intersection of two sets $A$ source 72 and $B$ source 72, written $A \cap B$ source 72, is the set of all things which are elements of both $A$ source 73 and $B$ source 73. $A \cap B = {x : x \in A \land x \in B}$ source 74 Two sets are called disjoint if their intersection is empty. This means they have no elements in common.

source 71

Example 11

If two sets have no elements in common, their intersection is empty: ${a, b, c} \cap {0, 1} = \emptyset$ source 83.

If two sets do have elements in common, their intersection is the set of all those: ${a, b, c} \cap {a, b, d} = {a, b}$ source 86.

The intersection of a set with one of its subsets is just the smaller set: ${a, b, c} \cap {a, b} = {a, b}$ source 89.

The intersection of any set with the empty set is empty: ${a, b, c} \cap \emptyset = \emptyset$ source 91.

source 81

Exercise 5

Prove rigorously that if $A \subseteq B$ source 96, then $A \cap B = A$ source 96.

source 95

Definition

If $A$ source 110 is a set of sets, then $⋃ A$ source 110 is the set of elements of elements of $A$ source 111: $\begin{matrix} ⋃ A & = {x : x belongs to an element of A}, i.e., \\ = {x : there is a B \in A so that x \in B} \end{matrix}$ source 112

source 109

Definition

If $A$ source 121 is a set of sets, then $⋂ A$ source 121 is the set of objects which all elements of $A$ source 122 have in common: $\begin{matrix} ⋂ A & = {x : x belongs to every element of A}, i.e., \\ = {x : for all B \in A, x \in B} \end{matrix}$ source 123

source 120

Example 12

Suppose $A = {{a, b}, {a, d, e}, {a, d}}$ source 131. Then $⋃ A = {a, b, d, e}$ source 132 and $⋂ A = {a}$ source 132.

source 130

Exercise 6

Show that if $A$ source 135 is a set and $A \in B$ source 135, then $A \subseteq ⋃ B$ source 135.

source 134

We could also do the same for a sequence of sets $A_{1}$ source 138, $A_{2}$ source 138, … $\begin{matrix} ⋃_{i} A_{i} & = {x : x belongs to one of the A_{i}} \\ ⋂_{i} A_{i} & = {x : x belongs to every A_{i}} . \end{matrix}$ source 139

When we have an index of sets, i.e., some set $I$ source 144 such that we are considering $A_{i}$ source 145 for each $i \in I$ source 145, we may also use these abbreviations: $\begin{matrix} ⋃_{i \in I} A_{i} & = ⋃ {A_{i} : i \in I} \\ ⋂_{i \in I} A_{i} & = ⋂ {A_{i} : i \in I} \end{matrix}$ source 147

Finally, we may want to think about the set of all elements in $A$ source 152 which are not in $B$ source 153. We can depict this as in the difference diagram.

The difference

A ∖ B

source 157 of two sets is the set of those elements of

A

source 158 which are not also elements of

B

source 158.

Difference A minus B: elements in A but not B. The highlighted region is the part of A outside B, containing elements in A that are not in B.

Set A: The left boundary.
Set B: The right boundary.
Highlighted region: The highlighted region is the part of A outside B, containing elements in A that are not in B.

source 155

Definition: Difference

The set difference $A ∖ B$ source 163 is the set of all elements of $A$ source 164 which are not also elements of $B$ source 164, i.e., $A ∖ B = {x : x \in A and x \notin B} .$ source 165

source 162

Exercise 7

Prove that if $A ⊊ B$ source 171, then $B ∖ A \neq \emptyset$ source 171.

source 170

Pairs, Tuples, Cartesian Products

Definition: Ordered pair

$⟨ a, b ⟩ = {{a}, {a, b}}$ source 30.

source 29

Exercise 8

Using the ordered-pair definition, prove that $⟨ a, b ⟩ = ⟨ c, d ⟩$ source 34 iff both $a = c$ source 35 and $b = d$ source 35.

source 33

Definition: Cartesian product

Given sets $A$ source 53 and $B$ source 53, their Cartesian product $A \times B$ source 53 is defined by $A \times B = {⟨ x, y ⟩ : x \in A and y \in B} .$ source 55

source 52

Example 13

If $A = {0, 1}$ source 61, and $B = {1, a, b}$ source 61, then their product is $A \times B = {⟨ 0, 1 ⟩, ⟨ 0, a ⟩, ⟨ 0, b ⟩, ⟨ 1, 1 ⟩, ⟨ 1, a ⟩, ⟨ 1, b ⟩} .$ source 62

source 60

Example 14

If $A$ source 69 is a set, the product of $A$ source 69 with itself, $A \times A$ source 69, is also written $A^{2}$ source 70. It is the set of all pairs $⟨ x, y ⟩$ source 70 with $x, y \in A$ source 71. The set of all triples $⟨ x, y, z ⟩$ source 71 is $A^{3}$ source 71, and so on. We can give a recursive definition: $\begin{matrix} A^{1} & = A \\ A^{k + 1} & = A^{k} \times A \end{matrix}$ source 73

source 68

Exercise 9

List all elements of ${1, 2, 3}^{3}$ source 80.

source 79

Proposition

If $A$ source 84 has $n$ source 84 elements and $B$ source 84 has $m$ source 84 elements, then $A \times B$ source 84 has $n \cdot m$ source 85 elements.

source 83

Proof

For every element $x$ source 89 in $A$ source 89, there are $m$ source 89 elements of the form $⟨ x, y ⟩ \in A \times B$ source 90. Let $B_{x} = {⟨ x, y ⟩ : y \in B}$ source 90. Since whenever $x_{1} \neq x_{2}$ source 91, $⟨ x_{1}, y ⟩ \neq ⟨ x_{2}, y ⟩$ source 91, $B_{x_{1}} \cap B_{x_{2}} = \emptyset$ source 92. But if $A = {x_{1}, \dots, x_{n}}$ source 92, then $A \times B = B_{x_{1}} \cup \dots \cup B_{x_{n}}$ source 93, and so has $n \cdot m$ source 94 elements.

To visualize this, arrange the elements of $A \times B$ source 96 in a grid: $\begin{array}{rcccc} B_{x_{1}} = & {⟨ x_{1}, y_{1} ⟩ & ⟨ x_{1}, y_{2} ⟩ & \dots & ⟨ x_{1}, y_{m} ⟩} \\ B_{x_{2}} = & {⟨ x_{2}, y_{1} ⟩ & ⟨ x_{2}, y_{2} ⟩ & \dots & ⟨ x_{2}, y_{m} ⟩} \\ ⋮ & ⋮ \\ B_{x_{n}} = & {⟨ x_{n}, y_{1} ⟩ & ⟨ x_{n}, y_{2} ⟩ & \dots & ⟨ x_{n}, y_{m} ⟩} \end{array}$ source 97 Since the $x_{i}$ source 105 are all different, and the $y_{j}$ source 105 are all different, no two of the pairs in this grid are the same, and there are $n \cdot m$ source 106 of them.

End of proof.

Exercise 10

Show, by induction on $k$ source 111, that for all $k \geq 1$ source 111, if $A$ source 111 has $n$ source 111 elements, then $A^{k}$ source 112 has $n^{k}$ source 112 elements.

source 110

Example 15

If $A$ source 116 is a set, a word over $A$ source 116 is any sequence of elements of $A$ source 117. A sequence can be thought of as an $n$ source 117-tuple of elements of $A$ source 118. For instance, if $A = {a, b, c}$ source 118, then the sequence “ $bac$ source 119” can be thought of as the triple $⟨ b, a, c ⟩$ source 119. Words, i.e., sequences of symbols, are of crucial importance in computer science. By convention, we count elements of $A$ source 121 as sequences of length $1$ source 122, and $\emptyset$ source 122 as the sequence of length $0$ source 122. The set of all words over $A$ source 123 then is $A^{*} = {\emptyset} \cup A \cup A^{2} \cup A^{3} \cup \dots$ source 124

source 115

Russell's Paradox

Extensionality licenses the notation ${x : φ (x)}$ source 13, for the set of $x$ source 14's such that $φ (x)$ source 14. However, all that extensionality really licenses is the following thought. If there is a set whose members are all and only the $φ$ source 16's, then there is only one such set. Otherwise put: having fixed some $φ$ source 18, the set ${x : φ (x)}$ source 18 is unique, if it exists.

But this conditional is important Crucially, not every property lends itself to comprehension. That is, some properties do not define sets. If they all did, then we would run into outright contradictions. The most famous example of this is Russell's Paradox.

Sets may be elements of other sets—for instance, the power set of a set $A$ source 28 is made up of sets. And so it makes sense to ask or investigate whether a set is an element of another set. Can a set be a member of itself? Nothing about the idea of a set seems to rule this out. For instance, if all sets form a collection of objects, one might think that they can be collected into a single set—the set of all sets. And it, being a set, would be an element of the set of all sets.

Russell's Paradox arises when we consider the property of not having itself as an element, of being non-self-membered. What if we suppose that there is a set of all sets that do not have themselves as an element? Does $R = {x : x \notin x}$ source 40 exist? It turns out that we can prove that it does not.

Theorem: Russell's Paradox

There is no set $R = {x : x \notin x}$ source 46.

source 45

Proof

If $R = {x : x \notin x}$ source 50 exists, then $R \in R$ source 51 iff $R \notin R$ source 51, which is a contradiction.

End of proof.

Explanation

Let's run through this proof more slowly. If $R$ source 56 exists, it makes sense to ask whether $R \in R$ source 56 or not. Suppose that indeed $R \in R$ source 57. Now, $R$ source 57 was defined as the set of all sets that are not elements of themselves. So, if $R \in R$ source 58, then $R$ source 59 does not itself have $R$ source 59's defining property. But only sets that have this property are in $R$ source 60, hence, $R$ source 60 cannot be an element of $R$ source 61, i.e., $R \notin R$ source 61. But $R$ source 61 can't both be and not be an element of $R$ source 62, so we have a contradiction.

Since the assumption that $R \in R$ source 64 leads to a contradiction, we have $R \notin R$ source 65. But this also leads to a contradiction For if $R \notin R$ source 65, then $R$ source 66 itself does have $R$ source 66's defining property, and so $R$ source 66 would be an element of $R$ source 67 just like all the other non-self-membered sets. And again, it can't both not be and be an element of $R$ source 68.