Sets

A set is an unordered collection of distinct objects called elements. Order and repetition do not matter: {1, 2, 3} = {3, 1, 2} = {1, 1, 2, 3}.

#Notation

#Subsets and the power set

• A ⊆ B (subset): every element of A is in B. Every set is a subset of itself, and ∅ ⊆ A for every A.
• A ⊂ B (proper subset): A ⊆ B and A ≠ B.
• A = B exactly when A ⊆ B and B ⊆ A — the standard way to prove two sets are equal.

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).

from itertools import combinations

A = {"a", "b", "c"}
power_set = [set(c) for r in range(len(A) + 1) for c in combinations(sorted(A), r)]
print(len(power_set), "subsets:")
print([sorted(s) for s in power_set])

8 subsets:
[[], ['a'], ['b'], ['c'], ['a', 'b'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']]

#Set operations

Try your own sets:

#Set identities

They mirror the laws of logic — ∪ is like ∨, ∩ like ∧, complement like ¬:

U = set(range(1, 11))
A, B = {1, 2, 3, 4, 5}, {4, 5, 6, 7}
comp = lambda X: U - X
print("(A ∪ B)′ =", sorted(comp(A | B)))
print("A′ ∩ B′  =", sorted(comp(A) & comp(B)))
print("De Morgan holds:", comp(A | B) == comp(A) & comp(B), comp(A & B) == comp(A) | comp(B))
print("|A ∪ B| = |A| + |B| - |A ∩ B|:", len(A | B), "=", len(A), "+", len(B), "-", len(A & B))

(A ∪ B)′ = [8, 9, 10]
A′ ∩ B′  = [8, 9, 10]
De Morgan holds: True True
|A ∪ B| = |A| + |B| - |A ∩ B|: 7 = 5 + 4 - 2

#Cartesian product

The Cartesian product A × B is the set of all ordered pairs (a, b) with a ∈ A and b ∈ B. |A × B| = |A| · |B|.

from itertools import product
sizes = ["S", "M", "L"]
colours = ["red", "blue"]
pairs = list(product(sizes, colours))
print(len(pairs), pairs)

6 [('S', 'red'), ('S', 'blue'), ('M', 'red'), ('M', 'blue'), ('L', 'red'), ('L', 'blue')]

Order matters in pairs: (1, 2) ≠ (2, 1), so A × B ≠ B × A in general.

#Cardinality of unions

For two sets: |A ∪ B| = |A| + |B| − |A ∩ B| — the intersection was counted twice. This is the inclusion–exclusion principle, extended in Counting.

#Countable and uncountable

A set is countable if its elements can be listed as a sequence (a one-to-one match with ℕ). ℤ and ℚ are countable; Cantor's diagonal argument shows ℝ is uncountable — there are "more" real numbers than integers.