Sets, Relations & Functions

A set is an unordered collection of distinct objects called elements or members. We write $a \in S$ to mean "a is an element of S" and $a \notin S$ to mean the opposite. Two sets are equal if and only if they have exactly the same elements — order and repetition do not matter, so ${1, 2, 3} = {3, 1, 2} = {1, 1, 2, 3}$.

Sets can be described by roster notation (list the elements: ${2, 4, 6}$) or set-builder notation (describe a property: ${x \in \mathbb{Z} \mid x > 0 \text{ and } x \text{ is even}}$). The vertical bar reads "such that."

The empty set $\emptyset$ (also written ${}$) contains no elements. It is unique. Note: $\emptyset \neq {\emptyset}$ — the latter is a set containing one element (the empty set itself).

Fundamental number sets: $\mathbb{N}$ (natural numbers, sometimes including 0), $\mathbb{Z}$ (integers), $\mathbb{Q}$ (rationals), $\mathbb{R}$ (reals), $\mathbb{C}$ (complex numbers).

In code, Python's set type models mathematical sets almost exactly. The distinction that matters: mathematical sets can contain any object (including other sets), but Python sets can only contain hashable objects.

# Set-builder notation: {x in Z | 0 <= x < 10 and x % 2 == 0}
evens = {x for x in range(10) if x % 2 == 0}
print(evens)  # {0, 2, 4, 6, 8}

# Membership
print(4 in evens)   # True
print(5 in evens)   # False
print(len(evens))   # 5

# Order and repetition don't matter
print({1, 2, 3} == {3, 1, 2})   # True
print({1, 1, 2, 3} == {1, 2, 3}) # True

Given sets $A$ and $B$ (drawn from a common universe $U$), the core operations are:

• Union: $A \cup B = {x \mid x \in A \text{ or } x \in B}$ — everything in either.
• Intersection: $A \cap B = {x \mid x \in A \text{ and } x \in B}$ — only what they share.
• Difference: $A \setminus B = {x \mid x \in A \text{ and } x \notin B}$ — A without B's elements.
• Complement: $\bar{A} = U \setminus A$ — everything in the universe not in A.
• Symmetric difference: $A \triangle B = (A \setminus B) \cup (B \setminus A)$ — elements in exactly one.

Subset and superset: $A \subseteq B$ means every element of A is in B. $A \subset B$ (strict subset) means $A \subseteq B$ and $A \neq B$. Note: $\emptyset \subseteq A$ for every set A (vacuously true — there is no element of $\emptyset$ that fails to be in A).

Key algebraic laws (analogous to Boolean algebra — this is not a coincidence):

• De Morgan: $\overline{A \cup B} = \bar{A} \cap \bar{B}$ and $\overline{A \cap B} = \bar{A} \cup \bar{B}$
• Distributivity: $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$

In databases, SQL's UNION, INTERSECT, and EXCEPT (or MINUS) are literally these operations on relations (sets of tuples).

A = {1, 2, 3, 4}
B = {3, 4, 5, 6}

print(A | B)   # union:     {1,2,3,4,5,6}
print(A & B)   # intersect: {3,4}
print(A - B)   # diff:      {1,2}
print(A ^ B)   # sym diff:  {1,2,5,6}
print(A <= B)  # subset?    False
print({3,4} <= A)  # True

The power set $\mathcal{P}(A)$ (also written $2^A$) is the set of ALL subsets of $A$, including $\emptyset$ and $A$ itself. If $|A| = n$, then $|\mathcal{P}(A)| = 2^n$. The notation $2^A$ is not accidental — it is a genuine exponentiation in the algebra of sets, and it connects directly to counting: each element is independently "in" or "out," giving $2 \times 2 \times \ldots \times 2 = 2^n$ choices.

Example: $A = {a, b, c}$, so $\mathcal{P}(A) = {\emptyset, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}}$, which has $2^3 = 8$ elements.

The Cartesian product $A \times B = {(a, b) \mid a \in A, b \in B}$ is the set of all ordered pairs. If $|A| = m$ and $|B| = n$, then $|A \times B| = mn$. Higher-dimensional products: $A^n = A \times A \times \ldots \times A$ ($n$ times) gives $n$-tuples.

Why this matters: a relation from $A$ to $B$ is just a subset of $A \times B$. A relational database table with schema $(\text{Name}, \text{Age}, \text{Score})$ is literally a subset of $\text{String} \times \mathbb{N} \times \mathbb{R}$. The word "relational" in "relational database" is a direct reference to this mathematical concept.

from itertools import chain, combinations, product

def power_set(s):
    """Returns all subsets of s as a list of frozensets."""
    lst = list(s)
    return [frozenset(c)
            for r in range(len(lst) + 1)
            for c in combinations(lst, r)]

A = {1, 2, 3}
print(len(power_set(A)))  # 8

# Cartesian product
B = {'x', 'y'}
pairs = list(product(A, B))
print(len(pairs))  # 6  (3 * 2)
print(pairs[:3])   # e.g. [(1,'x'),(1,'y'),(2,'x')]

A binary relation $R$ from set $A$ to set $B$ is any subset $R \subseteq A \times B$. We write $a, R, b$ (or $(a, b) \in R$) to mean the pair $(a,b)$ is in the relation. When $A = B$ we say $R$ is a relation on $A$.

Common examples:

• "is less than" on $\mathbb{Z}$: $R = {(a,b) \in \mathbb{Z}^2 \mid a < b}$
• "divides" on $\mathbb{N}$: $R = {(a,b) \mid a \mid b}$, so $(2,6) \in R$ but $(3,5) \notin R$
• "is a sibling of" on a set of people

Key properties a relation on $A$ may have:

• Reflexive: $\forall a \in A,; a, R, a$ (every element relates to itself). Example: $\leq$.
• Irreflexive: $\forall a,; (a, a) \notin R$. Example: $<$.
• Symmetric: $a, R, b \Rightarrow b, R, a$. Example: "is a sibling of."
• Antisymmetric: $a, R, b$ and $b, R, a$ implies $a = b$. Example: $\leq$ on $\mathbb{Z}$.
• Transitive: $a, R, b$ and $b, R, c$ implies $a, R, c$. Example: $<$.

These five properties are the atoms from which all the important relation types are built.

# Represent a relation as a set of pairs
divides = {(a, b) for a in range(1, 7) for b in range(1, 7) if b % a == 0}
print((2, 6) in divides)  # True
print((3, 5) in divides)  # False

def is_transitive(R, domain):
    return all(
        (a, c) in R
        for a in domain for b in domain for c in domain
        if (a, b) in R and (b, c) in R
    )

print(is_transitive(divides, range(1, 7)))  # True

A relation $R$ on $A$ is an equivalence relation if it is reflexive, symmetric, and transitive. Equivalence relations formalize the idea that two things are "the same for our purposes."

Examples:

• Congruence modulo $n$: $a \equiv b \pmod{n}$ iff $n \mid (a - b)$. This is the foundation of modular arithmetic and cryptography.
• "Same type" in a programming language.
• "Same connected component" in a graph.

The key theorem: an equivalence relation on $A$ is equivalent to a partition of $A$.

The equivalence class of $a$ under $R$ is $[a]_R = {b \in A \mid a, R, b}$. Equivalence classes are:

1. Non-empty (since $a \in [a]$ by reflexivity).
2. Either identical or completely disjoint (if $[a] \cap [b] \neq \emptyset$ then $[a] = [b]$).
3. Their union is all of $A$.

Thus the classes form a partition — a collection of disjoint, non-empty sets whose union is $A$. Conversely, every partition induces an equivalence relation ("is in the same piece as").

The set of all equivalence classes is called the quotient set $A/R$. This construction is everywhere: $\mathbb{Z}/n\mathbb{Z}$ (integers mod n), the rational numbers $\mathbb{Q}$ (pairs $(p,q)$ where $(p,q) \sim (p',q')$ iff $pq' = p'q$), and type equivalence in programming language semantics.

Union-Find (Disjoint Set Union) in algorithms is precisely the efficient computation of partitions maintained under union and membership queries.

# Congruence mod 3 on {0,...,8}: three equivalence classes
A = range(9)
mod3 = {(a, b) for a in A for b in A if (a - b) % 3 == 0}

# Compute equivalence class of 1
classes = {a: frozenset(b for b in A if (a, b) in mod3) for a in A}
print(classes[1])  # frozenset({1, 4, 7})
print(classes[0])  # frozenset({0, 3, 6})
# Partition: classes[0], classes[1], classes[2] are disjoint and cover {0..8}

A partial order is a relation that is reflexive, antisymmetric, and transitive. We typically denote it $\leq$ and call $(A, \leq)$ a partially ordered set (poset).

The word "partial" is key: not every pair of elements need be comparable. In a total order (also called a linear order), every pair is comparable: $\forall a, b,; a \leq b$ or $b \leq a$.

Examples:

• Total order: $\leq$ on $\mathbb{Z}$; lexicographic order on strings.
• Partial order, not total: set inclusion $\subseteq$ on $\mathcal{P}({1,2,3})$ — neither ${1,2} \subseteq {1,3}$ nor ${1,3} \subseteq {1,2}$.
• Partial order, not total: divisibility on $\mathbb{N}$ — 4 and 6 are incomparable under divisibility.

A Hasse diagram draws a poset by placing larger elements higher and drawing an edge for each "cover" (direct step up), suppressing transitively implied edges.

Key vocabulary for posets:

• Minimal element: $a$ such that no $b \neq a$ satisfies $b \leq a$.
• Maximum element (the greatest): $a$ such that $b \leq a$ for all $b$.
• Least upper bound (lub/join) of $a, b$: the smallest element $\geq$ both.
• Greatest lower bound (glb/meet) of $a, b$: the largest element $\leq$ both.

A poset where every pair has both a join and a meet is called a lattice — the structure underlying type hierarchies, logic, and abstract interpretation in compilers.

# Poset: divisibility on {1,2,3,4,6,12}
D = {1, 2, 3, 4, 6, 12}
divides = {(a, b) for a in D for b in D if b % a == 0}

def comparable(a, b, rel):
    return (a, b) in rel or (b, a) in rel

# Is it a total order?
pairs = [(a, b) for a in D for b in D if a != b]
is_total = all(comparable(a, b, divides) for a, b in pairs)
print(is_total)  # False — e.g. 4 and 6 are incomparable

# Minimal elements (nothing divides them except themselves in D)
minimal = {a for a in D if not any((b, a) in divides and b != a for b in D)}
print(minimal)  # {1}

A function $f: A \to B$ is a relation from $A$ to $B$ such that every element of $A$ is paired with exactly one element of $B$. $A$ is the domain, $B$ is the codomain, and $f(A) = {f(a) \mid a \in A}$ is the image (or range).

Formal definition as a relation: $f \subseteq A \times B$ such that for every $a \in A$, there exists a unique $b$ with $(a, b) \in f$.

This formalization clarifies a subtle point: the codomain is part of the type of the function, not just determined by the values taken. The function $f: \mathbb{Z} \to \mathbb{Z}$ defined by $f(x) = x^2$ and $g: \mathbb{Z} \to \mathbb{N}$ defined by $g(x) = x^2$ have different types even though they compute the same values. This matters enormously in type theory and in asking "is this function surjective?"

Composition: $(g \circ f)(x) = g(f(x))$, defined when the codomain of $f$ equals the domain of $g$.

Identity function: $\text{id}_A: A \to A$ defined by $\text{id}_A(x) = x$.

Restriction: $f|_S$ for $S \subseteq A$ is the function from $S$ to $B$ with the same rule.

In Haskell, every value has a type, and types are sets. A function f :: Int -> Bool is literally a function from the set of 64-bit integers to the set ${\text{True}, \text{False}}$.

-- Haskell: functions are first-class, types are sets
-- f : Z -> Bool
f :: Integer -> Bool
f x = x `mod` 2 == 0

-- Composition: (g . f)(x) = g(f(x))
g :: Bool -> String
g True  = "even"
g False = "odd"

label :: Integer -> String
label = g . f   -- composition

-- label 4 = "even", label 7 = "odd"
main :: IO ()
main = do
  print (label 4)  -- "even"
  print (label 7)  -- "odd"

These three properties classify every function — they are among the most important definitions in all of mathematics.

A function $f: A \to B$ is:

• Injective (one-to-one): $f(a_1) = f(a_2) \Rightarrow a_1 = a_2$. No two inputs share the same output. Mnemonic: injective = into (different elements map to different places).
• Surjective (onto): $\forall b \in B,; \exists a \in A$ such that $f(a) = b$. Every element of the codomain is hit. The image equals the codomain.
• Bijective (one-to-one correspondence): both injective and surjective.

Bijections are the isomorphisms of set theory: they say two sets are "the same size." If a bijection exists between $A$ and $B$, we write $|A| = |B|$.

Key facts:

• $f$ is injective $\Leftrightarrow$ $f$ has a left inverse ($g \circ f = \text{id}_A$ for some $g$).
• $f$ is surjective $\Leftrightarrow$ $f$ has a right inverse ($f \circ h = \text{id}_B$ for some $h$).
• $f$ is bijective $\Leftrightarrow$ $f$ has a two-sided inverse $f^{-1}$.

Computational manifestation: a hash function is (ideally) injective (no collisions) from keys to buckets — that is why collisions are a problem. An encryption function must be a bijection (otherwise decryption is impossible). A compression algorithm cannot be an injection from all $n$-bit strings to shorter strings (pigeonhole principle).

def is_injective(f, domain):
    """Check if f is injective on the given domain."""
    seen = {}
    for x in domain:
        y = f(x)
        if y in seen:
            return False, f"f({x}) = f({seen[y]}) = {y}"  # collision
        seen[y] = x
    return True, None

def is_surjective(f, domain, codomain):
    """Check if f hits every element of codomain."""
    image = {f(x) for x in domain}
    missed = set(codomain) - image
    return len(missed) == 0, missed

f = lambda x: x * 2           # f: {1,2,3} -> Z, injective, not surjective onto {1..6}
g = lambda x: x % 3           # g: {0..5} -> {0,1,2}, surjective
h = lambda x: (x + 1) % 6     # h: {0..5} -> {0..5}, bijective

print(is_injective(f, [1,2,3]))          # (True, None)
print(is_surjective(g, range(6), range(3))) # (True, set())
print(is_injective(h, range(6)))         # (True, None)
print(is_surjective(h, range(6), range(6))) # (True, set())

The cardinality of a set $A$, written $|A|$, measures its size. For finite sets this is just the number of elements. For infinite sets the definition requires care.

The crucial move: we define $|A| = |B|$ to mean there exists a bijection between $A$ and $B$. This is the only rigorous way to compare sizes — it works for infinite sets too.

A set is countably infinite (or simply countable) if there is a bijection between it and $\mathbb{N}$. Such a set can be "listed" in a sequence $a_0, a_1, a_2, \ldots$.

Surprising examples:

• $\mathbb{Z}$ is countable: list as $0, 1, -1, 2, -2, 3, -3, \ldots$
• $\mathbb{N} \times \mathbb{N}$ (all pairs of natural numbers) is countable: use Cantor's diagonal enumeration, listing pairs along diagonals ${(0,0), (1,0), (0,1), (2,0), (1,1), (0,2), \ldots}$.
• $\mathbb{Q}$ is countable (every rational is a pair of integers, use the above).

A set is uncountable if it is infinite but NOT countable. The archetypal uncountable set is $\mathbb{R}$.

def cantor_pair_enum():
    """Generate all (i,j) in N x N via Cantor diagonals."""
    d = 0
    while True:
        for i in range(d + 1):
            yield (i, d - i)
        d += 1

# First 10 pairs in the enumeration
gen = cantor_pair_enum()
for _ in range(10):
    print(next(gen))
# (0,0) (0,1) (1,0) (0,2) (1,1) (2,0) (0,3) ...

# Show Z is countable: bijection N -> Z
def int_from_nat(n):
    return n // 2 if n % 2 == 0 else -(n // 2 + 1)

print([int_from_nat(n) for n in range(10)])
# [0, -1, 1, -2, 2, -3, 3, -4, 4, -5]

The most profound result in this module: Cantor's theorem states that for any set $A$, the cardinality of its power set is strictly larger: $|A| < |\mathcal{P}(A)|$. For infinite sets, this means there is an infinite hierarchy of infinities.

The key proof: suppose $f: A \to \mathcal{P}(A)$ is any function. Define the diagonal set $D = {a \in A \mid a \notin f(a)}$. Then $D \in \mathcal{P}(A)$. But $D$ cannot be in the image of $f$: if $D = f(a_0)$ for some $a_0$, then $a_0 \in D \Leftrightarrow a_0 \notin f(a_0) = D$, a contradiction. So no function from $A$ to $\mathcal{P}(A)$ is surjective, hence $|A| < |\mathcal{P}(A)|$.

Corollary: $\mathbb{R}$ is uncountable. One proof (Cantor's diagonal argument): suppose we could list all reals in $[0,1]$ as $r_1, r_2, r_3, \ldots$. Construct $d$ whose $n$-th decimal digit differs from the $n$-th decimal digit of $r_n$. Then $d$ is not on the list — contradiction.

Why this shakes computer science to its core: the set of all programs is countable (programs are finite strings over a finite alphabet). The set of all functions $\mathbb{N} \to \mathbb{N}$ is uncountable (it bijects with $\mathcal{P}(\mathbb{N})$). Therefore most functions cannot be computed by any program. The halting problem is a specific, concrete witness to this impossibility — it is the diagonal set of the enumeration of all programs.

# Cantor's diagonal argument, illustrated for binary strings
# Suppose we claim to list ALL infinite binary sequences:
rows = [
    [0, 1, 0, 1, 0, 1, 0, 1],  # row 0
    [1, 1, 0, 0, 1, 1, 0, 0],  # row 1
    [0, 0, 1, 1, 0, 0, 1, 1],  # row 2
    [1, 0, 1, 0, 1, 0, 1, 0],  # row 3
    # ... (pretend this continues for all N)
]

# Diagonal: take row[i][i] and FLIP it
diagonal = [rows[i][i] for i in range(len(rows))]
diff = [1 - bit for bit in diagonal]  # flip each bit
print("diagonal:", diagonal)   # [0, 1, 1, 0, ...]
print("anti-diag:", diff)      # [1, 0, 0, 1, ...]
# diff differs from row 0 in position 0,
#                    row 1 in position 1, etc.
# So diff is NOT any row in our list — the list is incomplete.

We write $|A| \leq |B|$ if there exists an injection from $A$ to $B$. We write $|A| = |B|$ if there exists a bijection. The Cantor-Bernstein-Schroeder theorem states: if $|A| \leq |B|$ and $|B| \leq |A|$, then $|A| = |B|$. This lets us prove equality of cardinalities by finding injections in both directions, without explicitly constructing a bijection.

The cardinality of $\mathbb{N}$ is denoted $\aleph_0$ (aleph-naught). The cardinality of $\mathbb{R}$ is $2^{\aleph_0}$ (also called $\mathfrak{c}$, the cardinality of the continuum). By Cantor's theorem, $\aleph_0 < 2^{\aleph_0}$.

All of the following turn out to have cardinality $\aleph_0$: $\mathbb{Z}$, $\mathbb{Q}$, the set of all finite strings over any finite alphabet (including all programs!), the set of algebraic numbers.

All of the following have cardinality $2^{\aleph_0} = \mathfrak{c}$: $\mathbb{R}$, $(0,1) \subset \mathbb{R}$, $\mathbb{R}^n$ for any finite $n$, the set of all functions $\mathbb{N} \to {0,1}$, the power set $\mathcal{P}(\mathbb{N})$.

The Continuum Hypothesis (CH) asks: is there a cardinality strictly between $\aleph_0$ and $2^{\aleph_0}$? Godel (1940) showed CH cannot be disproved from standard axioms (ZFC); Cohen (1963) showed it cannot be proved either. It is genuinely independent of the axioms — a profound epistemic limit of formal mathematics.

# Cantor-Bernstein intuition: if we can inject A into B AND B into A,
# then they have the same cardinality.
# Example: show |(0,1)| = |R| without explicit bijection.

import math

# Injection (0,1) -> R: just inclusion (identity)
f = lambda x: x  # x in (0,1) maps to x in R

# Injection R -> (0,1): tan^{-1} normalized
g = lambda x: math.atan(x) / math.pi + 0.5
# g: R -> (0,1) is injective (arctan is strictly monotone)

test_vals = [-1000, -1, 0, 1, 1000]
print([round(g(x), 4) for x in test_vals])
# [~0.0003, 0.25, 0.5, 0.75, ~0.9997] — all in (0,1)
# By CBS theorem: |(0,1)| = |R|