Sets

A set is a collection of distinct objects, its elements. Order and repeats do not matter: {1, 2, 3} = {3, 1, 2} = {1, 1, 2, 3}.

• Roster form lists the elements: A = {2, 4, 6, 8}.
• Set-builder form gives a rule: A = {x | x is even and 0 < x < 10}, read "the set of x such that ...".
• x ∈ A means x is an element of A; x ∉ A means it is not.
• ∅ (or {}) is the empty set. |A| is the number of elements, the cardinality: |{2, 4, 6, 8}| = 4.

Python's set behaves exactly like a mathematical set.

Subsets

A ⊆ B ("A is a subset of B") when every element of A is also in B. A ⊂ B (a proper subset) when also A ≠ B. The empty set is a subset of every set, and every set is a subset of itself.

Operations

With a universal set U holding everything under discussion:

A Venn diagram draws each set as a circle inside a rectangle for U; overlaps show intersections. Two sets are disjoint if A ∩ B = ∅.

U = set(range(1, 11))
A = {2, 4, 6, 8, 10}          # even
B = {1, 2, 3, 5, 7}           # primes, and 1

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("A′ =", sorted(U - A))
print("{2, 4} ⊆ A:", {2, 4} <= A)
print("|A ∪ B| =", len(A | B), "=", len(A), "+", len(B), "-", len(A & B))

Power sets and products

• The power set P(A) is the set of all subsets of A. If |A| = n, then |P(A)| = 2ⁿ: each element is either in a subset or not.
• The Cartesian product A × B is the set of all ordered pairs (a, b) with a ∈ A and b ∈ B, and |A × B| = |A| × |B|. A database table is a subset of a Cartesian product, which is why relational databases have their name.

A = ["a", "b", "c"]
n = len(A)

subsets = []
for mask in range(2 ** n):              # 000, 001, ..., 111 in binary
    subset = [A[i] for i in range(n) if mask & (1 << i)]
    subsets.append(subset)

print(subsets)
print(len(subsets), "subsets = 2 **", n)

pairs = [(x, y) for x in [1, 2] for y in ["p", "q", "r"]]
print("{1, 2} × {p, q, r} has", len(pairs), "pairs:", pairs)

The program builds P(A) by treating the numbers 0 to 2ⁿ − 1 as bit patterns: bit i of the number says whether element i is in the subset.

Counting a union

|A ∪ B| = |A| + |B| − |A ∩ B|. Adding |A| and |B| counts the elements in both twice, so subtract them once. This is the inclusion-exclusion principle, and a later lesson extends it to three sets.

Mark lesson complete