Part I — Relations. Cartesian product, binary and $n$-ary relations, representations (set, matrix, digraph), operations, composition.
Properties of binary relations on a set: reflexive, irreflexive, symmetric, antisymmetric, asymmetric, transitive — with formal definitions, counter-examples, and proofs.
Special relations: equivalence relations and the partition theorem (proved); partial / total / strict / well orders.
Closures of a relation: reflexive, symmetric, transitive (constructive proofs).
Part II — Functions. Function as a special relation; equality, restriction, image, preimage.
Injection, surjection, bijection — definitions and characterisations.
Composition of functions — associativity (proved), behaviour of injection / surjection / bijection under composition (proved).
Inverse function — existence theorem ($f$ invertible iff $f$ bijective), uniqueness, properties (proved).
Image and preimage of sets — distribution over $\cup$, $\cap$, $\setminus$ (proved, with the failure cases).
Cardinality via bijections — finite, countable, uncountable; Cantor's theorem (proved).
References: Rosen 8e §§9.1–9.6, §2.3; Velleman 3e ch. 4–5; Halmos, Naive Set Theory; Cori & Lascar vol. 1.
2 / 32
1.1 Cartesian product — recap
Given two sets $A$ and $B$, their Cartesian product is
$$A \times B \;:=\; \{\,(a, b) \;:\; a \in A,\; b \in B\,\}.$$
The elements $(a, b)$ are ordered pairs: $(a,b) = (a',b')$ iff $a = a'$ and $b = b'$.
If $|A| = m$ and $|B| = n$ are finite, then $|A \times B| = m \cdot n$.
Enumerate $A = \{a_1, \dots, a_m\}$. For each $a_i$ there are exactly $|B| = n$ pairs $(a_i, b)$ with $b \in B$. These $m$ collections are pairwise disjoint (different first components). By the sum / product rule for finite sets, $|A \times B| = \sum_{i=1}^{m} n = m \cdot n$. $\square$
For $n$ sets the construction iterates: $A_1 \times A_2 \times \cdots \times A_n$ is the set of $n$-tuples $(a_1, \dots, a_n)$ with $a_i \in A_i$.
$\{1,2\} \times \{a,b,c\} = \{(1,a),(1,b),(1,c),(2,a),(2,b),(2,c)\}$ — six elements.
Rosen 8e §2.1, p. 130.
3 / 32
1.2 Binary and $n$-ary relations
A binary relation from $A$ to $B$ is any subset $R \subseteq A \times B$. We write $a\,R\,b$ (or $(a,b) \in R$) to mean "$a$ is related to $b$". When $A = B$ we speak of a binary relation on $A$.
Generally, an $n$-ary relation on $A_1, \dots, A_n$ is a subset $R \subseteq A_1 \times \cdots \times A_n$.
Two extreme cases on $A \times B$ deserve names:
$\varnothing \subseteq A \times B$ — the empty relation: nothing is related to anything.
$A \times B$ itself — the universal (full) relation: everything is related to everything.
There are exactly $2^{mn}$ binary relations from $A$ to $B$ when $|A|=m$, $|B|=n$.
A binary relation is a subset of $A \times B$, which has $mn$ elements. The number of subsets of a set of size $k$ is $2^k$, so the count is $2^{mn}$. $\square$
Rosen 8e §9.1, p. 597.
4 / 32
1.3 Representations of a relation
Take $A = \{1, 2, 3\}$, $B = \{a, b\}$, and $R = \{(1,a), (1,b), (3,a)\}$.
As a set of ordered pairs
$R = \{(1,a), (1,b), (3,a)\}$.
As a Boolean matrix $M_R$
Rows indexed by $A$, columns by $B$; entry $1$ iff $(a_i, b_j) \in R$.
$a$
$b$
$1$
$1$
$1$
$2$
$0$
$0$
$3$
$1$
$0$
As a directed graph (digraph), when $A = B$
Vertices = elements of $A$; draw an arrow $u \to v$ iff $(u, v) \in R$. Loops $u \to u$ are allowed when $(u,u) \in R$.
Python — represent a relation# As a set of tuples
R = {(1,'a'), (1,'b'), (3,'a')}
# As a Boolean matrix (rows=A, cols=B)
import numpy as np
A, B = [1,2,3], ['a','b']
M = np.array([[(a,b) in R for b in B] for a in A], dtype=int)
print(M)
Rosen 8e §9.3.
5 / 32
1.4 Operations on relations
Let $R, S \subseteq A \times B$ and $T \subseteq B \times C$.
Union: $R \cup S = \{(a,b) : (a,b) \in R \;\text{or}\; (a,b) \in S\}$.
Intersection: $R \cap S = \{(a,b) : (a,b) \in R \;\text{and}\; (a,b) \in S\}$.
Composition: $T \circ R = \{(a,c) : \exists b \in B,\; (a,b) \in R \wedge (b,c) \in T\} \subseteq A \times C$.
Composition of binary relations is associative: $(U \circ T) \circ R \;=\; U \circ (T \circ R)$.
Take $(a,d) \in (U \circ T) \circ R$ iff $\exists b\, ((a,b) \in R \wedge (b,d) \in U \circ T)$ iff $\exists b\,\exists c\,((a,b) \in R \wedge (b,c) \in T \wedge (c,d) \in U)$. This last formula is symmetric in the two parenthesisations, so it also equals $\exists c\,((a,c) \in T \circ R \wedge (c,d) \in U)$, i.e. $(a,d) \in U \circ (T \circ R)$. $\square$
$\;(R^{-1})^{-1} = R\;$ and $\;(T \circ R)^{-1} = R^{-1} \circ T^{-1}\;$ (note the order reversal).
"Irreflexive" $\neq$ "not reflexive". A relation can fail reflexivity without being irreflexive — e.g. on $A = \{1,2\}$ the relation $\{(1,1)\}$ has $(1,1) \in R$ (so not irreflexive) but $(2,2) \notin R$ (so not reflexive either). The two properties are stronger than the negations of each other.
Rosen 8e §9.1, pp. 599–602.
7 / 32
2.2 Symmetric vs antisymmetric vs asymmetric
$R$ is asymmetric iff $R$ is both irreflexive and antisymmetric.
(⇒) Assume $R$ asymmetric. If $(a,a) \in R$, asymmetry gives $(a,a) \notin R$, contradiction; hence $R$ irreflexive. If $(a,b),(b,a) \in R$ then asymmetry on $(a,b)$ gives $(b,a) \notin R$, contradiction unless $a = b$; but then $(a,a) \in R$, again contradicted by irreflexivity. So $a$ and $b$ cannot both be related — antisymmetry is satisfied vacuously when both directions never hold. (⇐) Assume $R$ irreflexive and antisymmetric. If $(a,b) \in R$ and $(b,a) \in R$, antisymmetry gives $a = b$, but then $(a,a) \in R$ contradicts irreflexivity. So $(b,a) \notin R$ — $R$ is asymmetric. $\square$
"$=$" on any set: reflexive, symmetric, antisymmetric, transitive.
"$\leq$" on $\mathbb{R}$: reflexive, antisymmetric, transitive (a partial order).
"$<$" on $\mathbb{R}$: irreflexive, asymmetric, transitive (a strict order).
"$\perp$" (perpendicularity) on lines in the plane: irreflexive, symmetric, not transitive.
"$|$" (divides) on $\mathbb{N}^*$: reflexive, antisymmetric, transitive (partial order).
Rosen 8e §9.1, p. 601; Velleman 3e §4.5.
8 / 32
3.1 Equivalence relations
A binary relation $R$ on $A$ is an equivalence relation iff it is reflexive, symmetric, and transitive. We then write $a \sim b$ for $(a,b) \in R$.
For each $a \in A$, the equivalence class of $a$ modulo $\sim$ is
$$[a] \;:=\; \{\,x \in A \;:\; x \sim a\,\}.$$
The set of all equivalence classes is the quotient set $A / \sim$.
Congruence mod $n$ on $\mathbb{Z}$: $a \sim_n b \;\Leftrightarrow\; n \mid (a-b)$. Classes are $[0], [1], \dots, [n-1]$ — the $n$ residue classes. $\mathbb{Z}/\sim_n = \mathbb{Z}/n\mathbb{Z}$.
"$\leq$" on $\mathbb{R}$ is reflexive and transitive but not symmetric, so it is not an equivalence relation.
Rosen 8e §9.5; Velleman 3e §4.6.
9 / 32
3.2 The fundamental partition theorem
A partition of $A$ is a collection $\{A_i\}_{i \in I}$ of non-empty subsets of $A$ such that $A = \bigcup_{i \in I} A_i$ and $A_i \cap A_j = \varnothing$ whenever $i \neq j$.
Let $A$ be a non-empty set. The equivalence relations on $A$ are in bijection with the partitions of $A$:
Given $\sim$, the equivalence classes $\{[a] : a \in A\}$ form a partition.
Given a partition $\{A_i\}$, the relation "$a \sim b$ iff $a$ and $b$ lie in the same block" is an equivalence.
(Equivalence ⇒ Partition.) Reflexivity gives $a \in [a]$, so every class is non-empty and $A = \bigcup_a [a]$.
Suppose $[a] \cap [b] \neq \varnothing$; pick $c \in [a] \cap [b]$. Then $c \sim a$ and $c \sim b$. By symmetry $a \sim c$, then by transitivity with $c \sim b$ we get $a \sim b$. Hence for any $x \in [a]$, $x \sim a \sim b$ gives $x \in [b]$. By symmetry $[b] \subseteq [a]$. So $[a] = [b]$. Therefore distinct classes are disjoint. (Partition ⇒ Equivalence.) Reflexivity: $a$ is in its own block. Symmetry: if $a, b$ in the same block then $b, a$ in the same block. Transitivity: blocks are sets, so "same block" is transitive. $\square$
Rosen 8e §9.5 Theorem 1, p. 661; Halmos, §11.
10 / 32
3.3 Partial, total and strict orders
$R$ on $A$ is a partial order (poset relation) iff it is reflexive, antisymmetric, and transitive. We write $\leq$ and call $(A, \leq)$ a partially ordered set.
A total (linear) order additionally satisfies the trichotomy: $\forall a, b \in A,\; a \leq b \vee b \leq a$.
A strict order $<$ is irreflexive and transitive (hence asymmetric, by the theorem of slide 8).
A well-order is a total order in which every non-empty subset has a least element.
Example
Type
$(\mathbb{N}, \leq)$
well-order (and total order).
$(\mathbb{Z}, \leq)$
total order, not well-order ($\mathbb{Z}$ itself has no least element).
$(\mathbb{N}^*, \mid)$ — divisibility
partial order, not total ($2 \nmid 3$ and $3 \nmid 2$).
$(\mathcal{P}(X), \subseteq)$
partial order; total only if $|X| \leq 1$.
A poset can be visualised by a Hasse diagram: vertices are elements; an edge $a \to b$ is drawn (upward) iff $a < b$ and there is no $c$ with $a < c < b$. Reflexive loops and transitive edges are omitted.
Rosen 8e §9.6; Velleman 3e §4.6.
11 / 32
4. Reflexive, symmetric, transitive closures
Let $R \subseteq A \times A$ and let $\mathcal{P}$ be a property of relations. The $\mathcal{P}$-closure of $R$, denoted $R^{\mathcal{P}}$, is the smallest relation containing $R$ that satisfies $\mathcal{P}$. (It is the intersection of all $\mathcal{P}$-relations containing $R$.)
Let $\Delta_A = \{(a,a) : a \in A\}$ be the diagonal of $A$. Then:
Reflexive closure: $r(R) = R \cup \Delta_A$.
Symmetric closure: $s(R) = R \cup R^{-1}$.
Transitive closure: $t(R) = \bigcup_{n \geq 1} R^n$, where $R^1 = R$ and $R^{n+1} = R \circ R^n$.
Reflexive. $R \cup \Delta_A$ is reflexive (contains $\Delta_A$) and contains $R$. Any reflexive relation $S \supseteq R$ must contain $\Delta_A$ and $R$, hence $S \supseteq R \cup \Delta_A$. So $r(R) = R \cup \Delta_A$. Symmetric. $R \cup R^{-1}$ is symmetric: $(a,b) \in R \cup R^{-1}$ iff $(a,b) \in R$ or $(b,a) \in R$, iff $(b,a) \in R^{-1}$ or $(b,a) \in R$. Any symmetric $S \supseteq R$ contains both $R$ and $R^{-1}$. So $s(R) = R \cup R^{-1}$. Transitive. Let $T := \bigcup_{n \geq 1} R^n$. $T \supseteq R$. If $(a,b) \in R^m$ and $(b,c) \in R^n$, then $(a,c) \in R^{n+m} \subseteq T$, so $T$ is transitive. Conversely any transitive $S \supseteq R$ satisfies $S \supseteq R^n$ for all $n$ (by induction on $n$), hence $S \supseteq T$. $\square$
For finite $|A| = n$, $\;t(R) = \bigcup_{k=1}^{n} R^k$. (No path of length $> n-1$ can connect two vertices without revisiting one — Warshall's algorithm.)
Rosen 8e §9.4; Halmos, §8.
12 / 32
5.1 Function — formal definition
A function $f$ from $A$ to $B$, written $f: A \to B$, is a binary relation $f \subseteq A \times B$ satisfying two conditions:
Totality: for every $a \in A$, there exists $b \in B$ with $(a, b) \in f$.
Single-valuedness: if $(a, b) \in f$ and $(a, b') \in f$, then $b = b'$.
The set $A$ is the domain, $B$ is the codomain. The unique $b$ with $(a,b) \in f$ is denoted $f(a)$, the image (or value) of $a$ under $f$.
The image (range) of $f$ is $\mathrm{Im}(f) := \{\,f(a) : a \in A\,\} \subseteq B$. Two functions $f, g : A \to B$ are equal iff $f(a) = g(a)$ for every $a \in A$ — equivalently, iff $f = g$ as sets of ordered pairs.
The relation $R = \{(1, a), (1, b)\}$ on $\{1,2\} \to \{a, b\}$ is not a function: it fails single-valuedness ($1$ has two images) and fails totality ($2$ has no image).
Let $f: A \to B$ and $A' \subseteq A$. The restriction of $f$ to $A'$ is $f\!\restriction_{A'} : A' \to B$ defined by $(f\!\restriction_{A'})(a) := f(a)$ for $a \in A'$. Conversely, $f$ is an extension of $g$ if $g = f\!\restriction_{\mathrm{dom}(g)}$.
Identity function on $A$: $\mathrm{id}_A : A \to A$, $\mathrm{id}_A(a) = a$. Constant function: $c_b : A \to B$, $c_b(a) = b$ for all $a$, where $b \in B$ is a fixed value.
For any $f: A \to B$, $\;f \circ \mathrm{id}_A = f$ and $\mathrm{id}_B \circ f = f$.
For every $a \in A$: $(f \circ \mathrm{id}_A)(a) = f(\mathrm{id}_A(a)) = f(a)$; $(\mathrm{id}_B \circ f)(a) = \mathrm{id}_B(f(a)) = f(a)$. Equal as functions. $\square$
Rosen 8e §2.3.
14 / 32
6.1 Injection (one-to-one)
$f: A \to B$ is injective (one-to-one) iff
$$\forall a, a' \in A,\;\; f(a) = f(a') \;\Rightarrow\; a = a'.$$
Equivalently (contrapositive): $a \neq a' \Rightarrow f(a) \neq f(a')$.
$f : \mathbb{R} \to \mathbb{R}$, $f(x) = x^2$ is not injective: $f(-3) = f(3) = 9$ but $-3 \neq 3$.
If $f : A \to B$ is injective and $A$ is finite, then $|A| \leq |B|$.
The image $\mathrm{Im}(f) = \{f(a) : a \in A\}$ has size exactly $|A|$ (since distinct inputs give distinct outputs); but $\mathrm{Im}(f) \subseteq B$, so $|A| = |\mathrm{Im}(f)| \leq |B|$. $\square$
Rosen 8e §2.3, p. 146.
15 / 32
6.2 Surjection (onto)
$f: A \to B$ is surjective (onto) iff
$$\forall b \in B,\;\; \exists a \in A,\;\; f(a) = b.$$
Equivalently: $\mathrm{Im}(f) = B$.
$f : \mathbb{Z} \to \mathbb{Z}$, $f(n) = n - 5$ is surjective. Proof. For any $b \in \mathbb{Z}$, pick $a := b + 5 \in \mathbb{Z}$. Then $f(a) = (b + 5) - 5 = b$. $\square$
$f : \mathbb{Z} \to \mathbb{Z}$, $f(n) = 2n$ is not surjective: no integer $n$ satisfies $2n = 1$.
If $f : A \to B$ is surjective and $B$ is finite, then $|A| \geq |B|$.
Surjectivity means $B = \mathrm{Im}(f)$. The map $a \mapsto f(a)$ sends $A$ onto $B$, so by a counting argument (or by partitioning $A$ into the preimages $f^{-1}(\{b\})$ for $b \in B$), $|A| = \sum_{b \in B} |f^{-1}(\{b\})| \geq \sum_{b \in B} 1 = |B|$. $\square$
Rosen 8e §2.3, p. 147.
16 / 32
6.3 Bijection — and a finite-case shortcut
$f: A \to B$ is a bijection (one-to-one correspondence) iff $f$ is both injective and surjective.
Pigeonhole-type theorem. If $A$ and $B$ are finite with $|A| = |B|$, then for $f : A \to B$:
$$f \text{ injective} \;\Longleftrightarrow\; f \text{ surjective} \;\Longleftrightarrow\; f \text{ bijective}.$$
Set $n := |A| = |B|$. Injective ⇒ surjective. If $f$ is injective, $|\mathrm{Im}(f)| = n = |B|$. Since $\mathrm{Im}(f) \subseteq B$ and both have size $n$, $\mathrm{Im}(f) = B$. Surjective ⇒ injective. If $f$ is surjective, partition $A$ as $A = \bigsqcup_{b \in B} f^{-1}(\{b\})$; surjectivity makes each block non-empty. We have $n$ blocks summing to $n$, so each block has exactly one element — $f$ is injective.
The equivalence with bijection is immediate from the definitions. $\square$
Both implications fail when the sets are infinite. Take $f : \mathbb{N} \to \mathbb{N}$, $f(n) = n+1$: injective but not surjective (no $n$ maps to $0$). And $g: \mathbb{N} \to \mathbb{N}$, $g(0) = 0$, $g(n) = n - 1$ for $n \geq 1$: surjective but not injective ($g(0) = g(1) = 0$).
Rosen 8e §2.3, p. 148; Halmos, §5.
17 / 32
7.1 Composition of functions
Given $f : A \to B$ and $g : B \to C$, the composition $g \circ f : A \to C$ is defined by $(g \circ f)(a) := g(f(a))$.
This is the special case of relation composition (slide 6) applied to functions; the totality and single-valuedness of $f$ and $g$ together imply the same for $g \circ f$.
Associativity. If $f : A \to B$, $g : B \to C$, $h : C \to D$, then $h \circ (g \circ f) = (h \circ g) \circ f$.
For every $a \in A$:
$$\bigl(h \circ (g \circ f)\bigr)(a) = h\bigl((g \circ f)(a)\bigr) = h\bigl(g(f(a))\bigr) = (h \circ g)(f(a)) = \bigl((h \circ g) \circ f\bigr)(a).$$
Equal at every point, hence equal as functions. $\square$
Composition is not commutative in general: even when both $f \circ g$ and $g \circ f$ are defined (e.g. $A = B = C$), they need not be equal. Take $f(x) = x + 1$ and $g(x) = 2x$ on $\mathbb{R}$: $(f \circ g)(x) = 2x + 1$ vs $(g \circ f)(x) = 2x + 2$.
If $f$ and $g$ are both injective, then $g \circ f$ is injective.
If $f$ and $g$ are both surjective, then $g \circ f$ is surjective.
If $f$ and $g$ are both bijective, then $g \circ f$ is bijective.
(1) Suppose $(g \circ f)(a) = (g \circ f)(a')$, i.e. $g(f(a)) = g(f(a'))$. Injectivity of $g$ gives $f(a) = f(a')$; injectivity of $f$ then gives $a = a'$. (2) Let $c \in C$. Surjectivity of $g$: there is $b \in B$ with $g(b) = c$. Surjectivity of $f$: there is $a \in A$ with $f(a) = b$. Then $(g \circ f)(a) = g(f(a)) = g(b) = c$. (3) Combine (1) and (2). $\square$
Partial converses. If $g \circ f$ is injective, then $f$ is injective. If $g \circ f$ is surjective, then $g$ is surjective.
If $f(a) = f(a')$, then $(g \circ f)(a) = g(f(a)) = g(f(a')) = (g \circ f)(a')$, so by injectivity of $g \circ f$, $a = a'$.
If $c \in C$, by surjectivity of $g \circ f$ there is $a$ with $(g \circ f)(a) = c$; then $g(f(a)) = c$, so $f(a) \in B$ is a preimage of $c$ under $g$. $\square$
Rosen 8e §2.3 Ex. 32; Velleman 3e §5.2.
19 / 32
8.1 Inverse function — existence theorem
$f : A \to B$ is invertible iff there exists $g : B \to A$ such that $g \circ f = \mathrm{id}_A$ and $f \circ g = \mathrm{id}_B$. Such $g$ is called the inverse of $f$, denoted $f^{-1}$.
$f : A \to B$ is invertible iff $f$ is bijective.
(⇐) Assume $f$ bijective. For each $b \in B$, surjectivity gives some $a \in A$ with $f(a) = b$; injectivity makes this $a$ unique. Define $g(b) := a$. Then $g : B \to A$ is well-defined. For all $a \in A$, $g(f(a)) = a$ by definition of $g$ at $b = f(a)$; for all $b \in B$, $f(g(b)) = f(a) = b$. So $g$ is an inverse. (⇒) Assume $g$ is an inverse. Injectivity. If $f(a) = f(a')$, apply $g$: $g(f(a)) = g(f(a'))$, i.e. $a = a'$. Surjectivity. For $b \in B$, set $a := g(b)$; then $f(a) = f(g(b)) = b$. $\square$
The inverse, when it exists, is unique. If $g_1$ and $g_2$ are both inverses, then $g_1 = g_1 \circ \mathrm{id}_B = g_1 \circ (f \circ g_2) = (g_1 \circ f) \circ g_2 = \mathrm{id}_A \circ g_2 = g_2$.
Rosen 8e §2.3, p. 149; Velleman 3e §5.3.
20 / 32
8.2 Properties of $f^{-1}$
Let $f: A \to B$ and $g: B \to C$ be bijections. Then:
$f^{-1}$ is a bijection, and $(f^{-1})^{-1} = f$.
$g \circ f$ is a bijection, and $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$ (the order reverses).
(1) $f^{-1}$ has inverse $f$ (because $f \circ f^{-1} = \mathrm{id}_B$ and $f^{-1} \circ f = \mathrm{id}_A$ — same equations, $f$ playing the role of $g$). By the existence theorem (slide 20), $f^{-1}$ is bijective and $(f^{-1})^{-1} = f$. (2) By slide 19, $g \circ f$ is a bijection. To see the order reversal, compute
$$(g \circ f) \circ (f^{-1} \circ g^{-1}) = g \circ (f \circ f^{-1}) \circ g^{-1} = g \circ \mathrm{id}_B \circ g^{-1} = g \circ g^{-1} = \mathrm{id}_C,$$
and symmetrically $(f^{-1} \circ g^{-1}) \circ (g \circ f) = \mathrm{id}_A$. By uniqueness of the inverse, $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$. $\square$
(1) $b \in f(S \cup T)$ iff $\exists a \in S \cup T,\; f(a) = b$ iff $\exists a \in S,\;f(a) = b$ or $\exists a \in T,\;f(a) = b$ iff $b \in f(S) \cup f(T)$. (2) If $b \in f(S \cap T)$, pick $a \in S \cap T$ with $f(a) = b$; this $a$ witnesses $b \in f(S)$ and $b \in f(T)$. Strict-inclusion counter-example without injectivity: $A = \{1,2\}$, $B = \{0\}$, $f(1) = f(2) = 0$, $S = \{1\}$, $T = \{2\}$. Then $f(S) \cap f(T) = \{0\}$ but $f(S \cap T) = f(\varnothing) = \varnothing$. Equality under injectivity: take $b \in f(S) \cap f(T)$, pick $a_1 \in S, a_2 \in T$ with $f(a_1) = f(a_2) = b$; by injectivity $a_1 = a_2 \in S \cap T$, so $b \in f(S \cap T)$. $\square$
Rosen 8e §2.3 Ex. 40; Halmos, §10.
22 / 32
9.2 Preimage of a set $f^{-1}(T)$
For $f: A \to B$ and $T \subseteq B$, the preimage (or inverse image) of $T$ is
$$f^{-1}(T) \;:=\; \{\,a \in A \;:\; f(a) \in T\,\} \;\subseteq\; A.$$
Note: $f^{-1}(T)$ is well-defined for any $f$, not just bijections — it is just a notation.
Preimage commutes with all Boolean operations: for $T_1, T_2 \subseteq B$,
$$f^{-1}(T_1 \cup T_2) = f^{-1}(T_1) \cup f^{-1}(T_2),$$
$$f^{-1}(T_1 \cap T_2) = f^{-1}(T_1) \cap f^{-1}(T_2),$$
$$f^{-1}(B \setminus T_1) = A \setminus f^{-1}(T_1).$$
The contrast with images is striking: preimages are well-behaved (commute with $\cap$, complement, union), images only commute with $\cup$ in general. This is one reason topology, measure theory and analysis are formulated in terms of preimages: continuity is defined as "preimage of open is open", not "image of open is open".
Rosen 8e §2.3 Ex. 41; Halmos, §10.
23 / 32
10.1 Cardinality via bijections
Two sets $A$ and $B$ are equinumerous, written $|A| = |B|$, iff there exists a bijection $f : A \to B$. A set $A$ is finite with $n$ elements iff $|A| = |\{1, 2, \dots, n\}|$; otherwise infinite. $A$ is countably infinite (or denumerable) iff $|A| = |\mathbb{N}|$; countable iff finite or countably infinite; uncountable otherwise.
"Equinumerous" is an equivalence relation on sets: it is reflexive ($\mathrm{id}_A$), symmetric ($f^{-1}$), and transitive ($g \circ f$).
Reflexivity: $\mathrm{id}_A : A \to A$ is a bijection. Symmetry: $f$ bijective $\Rightarrow f^{-1}$ bijective (slide 21). Transitivity: $f, g$ bijective $\Rightarrow g \circ f$ bijective (slide 19). $\square$
$f : \mathbb{N} \to \mathbb{Z}$, $f(0) = 0$, $f(2k-1) = k$, $f(2k) = -k$ for $k \geq 1$, is a bijection. Hence $|\mathbb{N}| = |\mathbb{Z}|$ — there are "as many" integers as natural numbers, although $\mathbb{N} \subsetneq \mathbb{Z}$.
Rosen 8e §2.5; Halmos, §13.
24 / 32
10.2 Cantor's theorem
Cantor (1891). For every set $A$, there is no surjection $f : A \to \mathcal{P}(A)$. In particular $|A| \neq |\mathcal{P}(A)|$ — the power set is strictly larger.
Suppose, for contradiction, that $f : A \to \mathcal{P}(A)$ is a surjection. Define the diagonal set
$$D \;:=\; \{\,a \in A \;:\; a \notin f(a)\,\} \;\in\; \mathcal{P}(A).$$
By surjectivity, $D = f(d)$ for some $d \in A$. Now ask whether $d \in D$:
$$d \in D \;\Longleftrightarrow\; d \notin f(d) \;\Longleftrightarrow\; d \notin D.$$
This is a contradiction. Hence no surjection exists. $\square$
$\mathcal{P}(\mathbb{N})$ is uncountable. Consequently $\mathbb{R}$ is uncountable (since $|\mathbb{R}| = |\mathcal{P}(\mathbb{N})| = 2^{\aleph_0}$ — a result we will revisit when studying sequences). Cantor's theorem is the springboard for the entire theory of cardinal numbers.
Halmos, §25; Rosen 8e §2.5.
25 / 32
11.1 Worked example — congruence mod $3$
On $\mathbb{Z}$ define $a \sim b \;\Leftrightarrow\; 3 \mid (a - b)$.
Verify the three axioms
Reflexivity. $a - a = 0$ and $3 \mid 0$. ✓ Symmetry. If $3 \mid (a - b)$, write $a - b = 3k$. Then $b - a = -3k = 3(-k)$, so $3 \mid (b - a)$. ✓ Transitivity. If $a - b = 3k$ and $b - c = 3\ell$, then $a - c = (a - b) + (b - c) = 3(k + \ell)$, so $3 \mid (a - c)$. ✓ $\square$
Python — explore congruence mod $3$def classes_mod(n, sample):
cls = {}
for x in sample:
cls.setdefault(x % n, []).append(x)
return cls
print(classes_mod(3, range(-6, 10)))
# {0: [-6,-3,0,3,6,9], 1: [-5,-2,1,4,7], 2: [-4,-1,2,5,8]}
Velleman 3e §4.6; Rosen 8e §9.5.
26 / 32
11.2 Worked example — bijection $(0,1) \to \mathbb{R}$
Show that the open interval $(0, 1) \subseteq \mathbb{R}$ has the same cardinality as $\mathbb{R}$.
The function $f : (0, 1) \to \mathbb{R}$ defined by $f(x) := \tan\!\bigl(\pi(x - \tfrac{1}{2})\bigr)$ is a bijection.
Injectivity. Suppose $f(x_1) = f(x_2)$, i.e. $\tan(\pi(x_1 - \tfrac12)) = \tan(\pi(x_2 - \tfrac12))$. On the open interval $(-\tfrac{\pi}{2}, \tfrac{\pi}{2})$ the tangent function is strictly increasing, hence injective. Since $x_i \in (0,1)$ we have $\pi(x_i - \tfrac12) \in (-\tfrac{\pi}{2}, \tfrac{\pi}{2})$, so $\pi(x_1 - \tfrac12) = \pi(x_2 - \tfrac12)$, hence $x_1 = x_2$. ✓ Surjectivity. Let $y \in \mathbb{R}$. The tangent function $\tan : (-\tfrac{\pi}{2}, \tfrac{\pi}{2}) \to \mathbb{R}$ is surjective (its range is all of $\mathbb{R}$). Pick $\theta \in (-\tfrac{\pi}{2}, \tfrac{\pi}{2})$ with $\tan \theta = y$, and set $x := \tfrac{\theta}{\pi} + \tfrac{1}{2} \in (0, 1)$. Then $f(x) = \tan(\pi(x - \tfrac12)) = \tan \theta = y$. ✓
Hence $f$ is a bijection, and $|(0,1)| = |\mathbb{R}|$. $\square$
A finite-looking interval has the same cardinality as the whole real line — an infinite set can be equinumerous with a proper subset of itself. This is a signature property of infinite sets (Dedekind's definition: a set is infinite iff it is equinumerous with a proper subset).
Python — check properties of a relationdef is_reflexive(R, A): return all((a, a) in R for a in A)
def is_symmetric(R, A): return all((b, a) in R for (a, b) in R)
def is_antisymmetric(R, A): return all(a == b for (a, b) in R if (b, a) in R)
def is_transitive(R, A):
return all((a, c) in R for (a, b) in R for (b2, c) in R if b == b2)
A = {1, 2, 3, 4}
divides = {(a, b) for a, b in product(A, A) if b % a == 0}
print(is_reflexive(divides, A), # True — every a divides itself
is_antisymmetric(divides, A), # True
is_transitive(divides, A)) # True → partial order
Python — composition and inverse of a function as a dictdef compose(g, f): return {a: g[f[a]] for a in f}
def is_bijection(f, codomain):
return set(f.values()) == set(codomain) and len(set(f.values())) == len(f)
def invert(f): return {b: a for a, b in f.items()}
f = {1: 'a', 2: 'b', 3: 'c'}
g = {'a': 10, 'b': 20, 'c': 30}
print(compose(g, f)) # {1: 10, 2: 20, 3: 30}
print(is_bijection(f, ['a','b','c'])) # True
print(invert(f)) # {'a': 1, 'b': 2, 'c': 3}
28 / 32
13. SymPy support for relations & functions
SymPy — FiniteSet, ProductSet, Lambdafrom sympy import FiniteSet, ProductSet, Lambda, symbols, S, Eq, solve
# Cartesian product
A = FiniteSet(1, 2, 3); B = FiniteSet('a', 'b')
print(ProductSet(A, B)) # {1, 2, 3} x {a, b}
# Function defined symbolically
x = symbols('x')
f = Lambda(x, 2*x + 1)
print(f(3)) # 7
print(f(x).subs(x, 5)) # 11
# Solve the surjectivity equation 2x + 1 = y for y in Z
y = symbols('y')
print(solve(Eq(f(x), y), x)) # [(y - 1)/2] → not always integer ⇒ not surjective on Z
SymPy — partition from an equivalence relationfrom sympy.combinatorics.partitions import Partition
# Partition of {1,2,3,4,5,6} into residue classes mod 3
p = Partition([1, 4], [2, 5], [3, 6])
print(p) # {{1, 4}, {2, 5}, {3, 6}}
print(p.partition) # list of blocks
29 / 32
14. Summary — what we proved
Relations
$|A \times B| = |A| \cdot |B|$, and $2^{mn}$ relations between $A$ and $B$.
Composition of relations is associative; $(R^{-1})^{-1} = R$; $(T \circ R)^{-1} = R^{-1} \circ T^{-1}$.