Sets and set operations

Almost every object in modern mathematics is defined as a set or built from sets: the solution set of an equation, the domain of a function, a vector space, a group, the open intervals of the real line. Set theory supplies the vocabulary in which definitions are written and the rules by which they are manipulated. This lesson covers the basic notation, the ways of combining sets, and the main technique for proving facts about sets, which is to show that two sets have the same elements. It is also a good place to practise the logic of the first half of the course, because every set identity is a logical equivalence in disguise.

Sets and elements

A set is a collection of objects, called its elements or members. We write \(x \in A\) when \(x\) is an element of \(A\) and \(x \notin A\) when it is not. A set is determined entirely by its elements: order does not matter and repetition is ignored, so \(\{1, 2, 3\}\), \(\{3, 1, 2\}\) and \(\{1, 1, 2, 3\}\) are the same set. The empty set \(\emptyset\) has no elements at all. A set may contain other sets as elements: \(\{1, \{1\}\}\) has two elements, the number 1 and the set \(\{1\}\), and these are different objects.

Small sets can be listed: \(\{2, 3, 5, 7\}\). Larger sets are described by set-builder notation, \(\{x \in U : P(x)\}\), read 'the set of \(x\) in \(U\) such that \(P(x)\)'. For example \(\{n \in \mathbb{Z} : n^2 < 10\} = \{-3, -2, -1, 0, 1, 2, 3\}\) and \(\{x \in \mathbb{R} : x^2 = -1\} = \emptyset\). Intervals are common sets of real numbers: \([a, b] = \{x \in \mathbb{R} : a \le x \le b\}\) and \((a, b) = \{x \in \mathbb{R} : a < x < b\}\).

Specifying the universe \(U\) in set-builder notation is not fussiness. Around 1901 Bertrand Russell showed that allowing 'the set of all \(x\) such that \(P(x)\)' with no restriction leads to a contradiction. Consider \(R = \{x : x \notin x\}\), the set of all sets that are not elements of themselves. If \(R \in R\) then by definition \(R \notin R\); if \(R \notin R\) then by definition \(R \in R\). Either way we have a contradiction. Russell's paradox led to the axiomatic set theories used today, such as Zermelo–Fraenkel set theory, which allow you to form \(\{x \in A : P(x)\}\) only inside a set \(A\) that already exists. In everyday mathematics this restriction is invisible: we always work inside some known set such as \(\mathbb{Z}\) or \(\mathbb{R}\).

Subsets and equality

A set \(A\) is a subset of \(B\), written \(A \subseteq B\), if every element of \(A\) is an element of \(B\): \(\forall x,\ x \in A \implies x \in B\). For example \(\mathbb{N} \subseteq \mathbb{Z} \subseteq \mathbb{Q} \subseteq \mathbb{R}\). If \(A \subseteq B\) and \(A \ne B\) we say \(A\) is a proper subset and write \(A \subsetneq B\). Two facts follow straight from the definition: every set is a subset of itself, and the empty set is a subset of every set. The second is vacuously true: the statement '\(x \in \emptyset \implies x \in B\)' has a false hypothesis for every \(x\).

Two sets are equal when they have exactly the same elements, which is the same as saying each is a subset of the other: \(A = B\) if and only if \(A \subseteq B\) and \(B \subseteq A\). This gives the standard method for proving that two sets are equal, called double inclusion: let \(x\) be an arbitrary element of \(A\) and show \(x \in B\); then let \(x\) be an arbitrary element of \(B\) and show \(x \in A\).

Operations on sets

Let \(A\) and \(B\) be subsets of a universal set \(U\). The basic operations are defined by logical connectives.

Sets with no common elements, \(A \cap B = \emptyset\), are called disjoint. The complement depends on the universe: the complement of the even integers in \(\mathbb{Z}\) is the odd integers, but in \(\mathbb{R}\) it also contains every non-integer. When there is any doubt, write \(U \setminus A\) instead of \(A^c\).

Venn diagrams, introduced by John Venn in 1880, are excellent for discovering and remembering set identities. They are not proofs, because a diagram shows one arrangement of the sets and might mislead when there are many sets or special relationships. A proof works with elements.

Set identities

Because each operation corresponds to a connective, every logical equivalence from lesson 2 gives a set identity. For subsets \(A, B, C\) of \(U\):

• Commutative: \(A \cup B = B \cup A\) and \(A \cap B = B \cap A\).

• Associative: \((A \cup B) \cup C = A \cup (B \cup C)\) and \((A \cap B) \cap C = A \cap (B \cap C)\).

• Distributive: \(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)\).

• De Morgan: \((A \cup B)^c = A^c \cap B^c\) and \((A \cap B)^c = A^c \cup B^c\).

• Difference: \(A \setminus B = A \cap B^c\).

• Double complement: \((A^c)^c = A\).

Theorem (De Morgan's law for sets). \((A \cup B)^c = A^c \cap B^c\).

Proof. We show that an element belongs to one side exactly when it belongs to the other. For \(x \in U\): \(x \in (A \cup B)^c\) iff \(x \notin A \cup B\) iff \(\neg(x \in A \vee x \in B)\) iff \(x \notin A \wedge x \notin B\) (by De Morgan's law of logic) iff \(x \in A^c \wedge x \in B^c\) iff \(x \in A^c \cap B^c\). \(\blacksquare\)

A chain of 'iff' steps proves both inclusions at once. Use it only when every step genuinely reverses; otherwise write the two inclusions separately, as in the double inclusion example.

Disproving set statements

To show that two sets are not always equal, give a specific example. Is \(A \setminus (B \setminus C) = (A \setminus B) \setminus C\)? Try \(A = B = C = \{1\}\). The left side is \(\{1\} \setminus \emptyset = \{1\}\) and the right side is \(\emptyset \setminus \{1\} = \emptyset\). So set difference is not associative. Small examples with one or two elements, or with some sets equal or empty, are usually enough.

Power sets and Cartesian products

The power set of \(A\), written \(\mathcal{P}(A)\), is the set of all subsets of \(A\). For \(A = \{1, 2, 3\}\), \(\mathcal{P}(A) = \{\emptyset, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\}\}\), which has 8 elements. In general a set with \(n\) elements has \(2^n\) subsets, because each element is independently in or out. You can prove this by induction: adding a new element doubles the number of subsets, since each old subset appears once without it and once with it. Lesson 12 compares the size of \(A\) and \(\mathcal{P}(A)\) for infinite sets, with a startling result.

The Cartesian product \(A \times B\) is the set of ordered pairs \((a, b)\) with \(a \in A\) and \(b \in B\). Unlike sets, ordered pairs care about order: \((1, 2) \ne (2, 1)\). For example \(\{1, 2\} \times \{x, y\} = \{(1, x), (1, y), (2, x), (2, y)\}\). If \(A\) has \(m\) elements and \(B\) has \(n\), then \(A \times B\) has \(mn\). The plane \(\mathbb{R}^2 = \mathbb{R} \times \mathbb{R}\) is the most familiar Cartesian product, named after René Descartes. Lessons 10 and 11 define functions and relations as subsets of Cartesian products.

Indexed families

Sometimes we combine many sets at once. If \(A_1, A_2, A_3, \dots\) are sets, then \(\bigcup_{n=1}^{\infty} A_n\) is the set of elements belonging to at least one \(A_n\), and \(\bigcap_{n=1}^{\infty} A_n\) is the set of elements belonging to every \(A_n\). In logical terms, these are the existential and universal quantifiers. For example, with \(A_n = [1/n, 2]\), the union is \((0, 2]\) and the intersection is \([1, 2]\). With \(B_n = (0, 1/n)\), the intersection is empty: every positive number \(x\) misses \(B_n\) once \(1/n \le x\). Facts like this become important in analysis and topology (MATH-447).

Sets in Python

Python's set type supports all of these operations directly, which makes it easy to test identities on small examples and to search for counterexamples. The code below checks De Morgan's law and the distributive law on random subsets, confirms that difference is not associative, and counts power sets.

import random
from itertools import combinations
random.seed(228)
U = set(range(10))

def rand_subset():
    return {x for x in U if random.random() < 0.5}

def comp(A):
    return U - A

ok_dm = ok_dist = True
for _ in range(2000):
    A, B, C = rand_subset(), rand_subset(), rand_subset()
    ok_dm &= comp(A | B) == comp(A) & comp(B)
    ok_dist &= A & (B | C) == (A & B) | (A & C)
print("De Morgan holds in all trials:", ok_dm)
print("distributive law holds in all trials:", ok_dist)

A = B = C = {1}
print("A-(B-C) =", A - (B - C), "  (A-B)-C =", (A - B) - C)

def power_set(S):
    S = list(S)
    return [set(c) for r in range(len(S) + 1) for c in combinations(S, r)]
for n in range(6):
    print(f"|P(S)| for |S| = {n}: {len(power_set(range(n)))}")

De Morgan holds in all trials: True
distributive law holds in all trials: True
A-(B-C) = {1}   (A-B)-C = set()
|P(S)| for |S| = 0: 1
|P(S)| for |S| = 1: 2
|P(S)| for |S| = 2: 4
|P(S)| for |S| = 3: 8
|P(S)| for |S| = 4: 16
|P(S)| for |S| = 5: 32