Sets and set operations

A set is a collection of distinct objects, and it is the most basic structure in mathematics. Almost every other structure in this course is built from sets: functions and relations are sets of pairs, graphs are sets of vertices and edges, and a database table is a set of rows. Python's set type, which you used in CMPUT-174, implements the finite case directly, so you can experiment with every idea in this lesson.

Describing sets

A set is determined entirely by its elements. Order and repetition do not matter: \(\{1, 2, 3\}\), \(\{3, 1, 2\}\) and \(\{1, 1, 2, 3\}\) are the same set. We write \(x \in A\) for x is an element of A and \(x \notin A\) for x is not an element of A. Sets can be described in two main ways. Roster notation lists the elements: \(V = \{a, e, i, o, u\}\). Set-builder notation gives a property: \(E = \{n \in \mathbb{Z} \mid n \text{ is even}\}\), read as the set of integers n such that n is even.

Some sets have standard names. \(\mathbb{N}\) is the natural numbers; in computing, and in this course, \(\mathbb{N} = \{0, 1, 2, \ldots\}\), though some texts start at 1. \(\mathbb{Z}\) is the integers, \(\mathbb{Q}\) the rational numbers and \(\mathbb{R}\) the real numbers. The empty set, written \(\varnothing\) or \(\{\}\), has no elements at all. Note that \(\{\varnothing\}\) is not empty: it is a set with one element, which happens to be the empty set. A box containing an empty box is not an empty box.

A = {3, 1, 2, 2, 1}
print("A =", A, "  size:", len(A))
print("{1,2,3} == {3,2,1}:", {1, 2, 3} == {3, 2, 1})
evens = {n for n in range(-6, 7) if n % 2 == 0}      # set-builder notation as a comprehension
print("evens in -6..6:", sorted(evens))
empty = set()                                         # note: {} is an empty dict, not a set
print("len(set()) =", len(empty), "  len({frozenset()}) =", len({frozenset()}))

A = {1, 2, 3}   size: 3
{1,2,3} == {3,2,1}: True
evens in -6..6: [-6, -4, -2, 0, 2, 4, 6]
len(set()) = 0   len({frozenset()}) = 1

Subsets and equality

A set \(A\) is a subset of \(B\), written \(A \subseteq B\), if every element of \(A\) is also an element of \(B\): \(\forall x\, (x \in A \to x \in B)\). If in addition \(A \ne B\), then \(A\) is a proper subset, written \(A \subset B\). Two facts follow straight from the definition. Every set is a subset of itself. The empty set is a subset of every set, because the condition \(x \in \varnothing \to x \in B\) has a false hypothesis for every \(x\), so it is vacuously true.

Two sets are equal exactly when each is a subset of the other. This gives the standard method for proving set equality, called double inclusion: show \(A \subseteq B\) and \(B \subseteq A\). To prove \(A \subseteq B\), take an arbitrary element \(x \in A\) and show \(x \in B\).

Set operations

The basic operations correspond exactly to the logical connectives of lesson 2. Union collects elements in either set (or), intersection those in both (and), difference those in the first but not the second (and not), and the complement those not in the set, relative to a universal set \(U\) of everything under discussion.

U = set(range(1, 11))
A = {1, 2, 3, 4, 5}
B = {4, 5, 6, 7}
print("A | B  =", sorted(A | B))
print("A & B  =", sorted(A & B))
print("A - B  =", sorted(A - B))
print("A ^ B  =", sorted(A ^ B))
print("comp A =", sorted(U - A))
print("A & B <= A:", (A & B) <= A, "   A <= A | B:", A <= A | B)

A | B  = [1, 2, 3, 4, 5, 6, 7]
A & B  = [4, 5]
A - B  = [1, 2, 3]
A ^ B  = [1, 2, 3, 6, 7]
comp A = [6, 7, 8, 9, 10]
A & B <= A: True    A <= A | B: True

Sets \(A\) and \(B\) are disjoint if \(A \cap B = \varnothing\). A collection of non-empty, pairwise disjoint sets whose union is a set \(S\) is a partition of \(S\). Partitions are everywhere in computing: a hash table partitions its keys into buckets, and in lesson 9 you will see that equivalence relations correspond exactly to partitions.

Set identities

Because each set operation corresponds to a connective, every equivalence law of lesson 3 gives a set identity. De Morgan's laws become \(\overline{A \cup B} = \bar{A} \cap \bar{B}\) and \(\overline{A \cap B} = \bar{A} \cup \bar{B}\). Distributivity becomes \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\). Each can be proved by double inclusion, by a membership table (the set version of a truth table) or by reducing to the logical law.

from itertools import product
# Membership table: each row says whether an element is in A, B, C.
ok = True
for a, b, c in product([True, False], repeat=3):
    lhs = a and not (b or c)                 # x in A - (B | C)
    rhs = (a and not b) and (a and not c)    # x in (A - B) & (A - C)
    ok &= (lhs == rhs)
print("membership table proves A-(B|C) == (A-B)&(A-C):", ok)
import random
random.seed(7)
U = range(20)
for _ in range(3):
    A, B, C = ({x for x in U if random.random() < 0.5} for _ in range(3))
    print(A - (B | C) == (A - B) & (A - C), end=" ")
print()

membership table proves A-(B|C) == (A-B)&(A-C): True
True True True

Power sets

The power set of \(A\), written \(\mathcal{P}(A)\), is the set of all subsets of \(A\). For \(A = \{a, b, c\}\), the power set has 8 elements: \(\varnothing\), \(\{a\}\), \(\{b\}\), \(\{c\}\), \(\{a, b\}\), \(\{a, c\}\), \(\{b, c\}\) and \(\{a, b, c\}\). In general, if \(|A| = n\) then \(|\mathcal{P}(A)| = 2^n\), because building a subset means deciding, for each of the \(n\) elements independently, whether to include it.

That argument links power sets to binary numbers: a subset of an \(n\)-element set corresponds to an \(n\)-bit string, with bit \(i\) equal to 1 if element \(i\) is included. The integers 0 to \(2^n - 1\) therefore enumerate all subsets, which is a standard programming technique.

items = ["a", "b", "c"]
n = len(items)
for mask in range(2 ** n):
    subset = [items[i] for i in range(n) if mask >> i & 1]
    print(f"{mask:03b} -> {{{', '.join(subset)}}}")
print("number of subsets:", 2 ** n)

000 -> {}
001 -> {a}
010 -> {b}
011 -> {a, b}
100 -> {c}
101 -> {a, c}
110 -> {b, c}
111 -> {a, b, c}
number of subsets: 8

Exponential growth makes power sets enormous. A set of 30 elements has over a billion subsets, and 300 elements give more subsets than there are atoms in the observable universe. That is why algorithms that try every subset, like the brute-force SAT solver in lesson 3, quickly become impractical, and why algorithm design (CMPUT-204 and CMPUT-304) looks for cleverer approaches.

Cartesian products and tuples

An ordered pair \((a, b)\) differs from the set \(\{a, b\}\): order matters, so \((1, 2) \ne (2, 1)\), and repetition is allowed, as in \((3, 3)\). The Cartesian product \(A \times B\) is the set of all ordered pairs with first element from \(A\) and second from \(B\). If \(|A| = m\) and \(|B| = n\), then \(|A \times B| = mn\). More generally, \(A_1 \times \cdots \times A_k\) contains the \(k\)-tuples, and \(A^k\) means \(A \times \cdots \times A\) with \(k\) factors.

Cartesian products are the mathematics behind many data structures. A Python tuple is an element of a Cartesian product. A row in a database table with columns name, age and province is an element of \(\text{Names} \times \text{Ages} \times \text{Provinces}\). Every pixel position on a 1920 by 1080 screen is an element of \(\{0, \ldots, 1919\} \times \{0, \ldots, 1079\}\), a set with 2,073,600 elements.

from itertools import product
sizes = ["S", "M", "L"]
finishes = ["matte", "gloss"]
variants = list(product(sizes, finishes))
print(variants)
print("|sizes x finishes| =", len(variants), "= 3 * 2")
print("|{0,1}^8| =", len(list(product([0, 1], repeat=8))), "(the number of bytes)")

[('S', 'matte'), ('S', 'gloss'), ('M', 'matte'), ('M', 'gloss'), ('L', 'matte'), ('L', 'gloss')]
|sizes x finishes| = 6 = 3 * 2
|{0,1}^8| = 256 (the number of bytes)

Inclusion–exclusion

How many elements are in \(A \cup B\)? Adding \(|A| + |B|\) counts the elements of \(A \cap B\) twice, so we subtract them once. For three sets we add the three sizes, subtract the three pairwise intersections, and then add back the triple intersection, which was subtracted once too often.

N = 1000
direct = sum(1 for n in range(1, N + 1) if n % 3 == 0 or n % 5 == 0 or n % 7 == 0)
f = lambda d: N // d
formula = f(3) + f(5) + f(7) - f(15) - f(21) - f(35) + f(105)
print("direct count:", direct, "  inclusion-exclusion:", formula)

direct count: 543   inclusion-exclusion: 543

A caution: Russell's paradox

It seems natural to allow any property to define a set. In 1901 Bertrand Russell showed that this leads to contradiction. Consider \(R = \{x \mid x \notin x\}\), the set of all sets that are not members of themselves. Is \(R \in R\)? If it is, then by definition it is not; if it is not, then by definition it is. Modern set theory avoids the paradox by restricting how sets may be formed, for example by always selecting elements from an existing set: \(\{x \in A \mid P(x)\}\). In practice, if you always specify the domain, as this course recommends, you never meet the problem. The same self-reference trick reappears in CMPUT-474 as the heart of Turing's proof that some problems cannot be solved by any program.