Sets, relations and functions

Sets

A set is a collection of distinct objects, its elements. Order and repetition don’t matter: $\{1, 2, 3\}$, $\{3, 1, 2\}$ and $\{1, 1, 2, 3\}$ are the same set. We write $x \in A$ when $x$ is an element of $A$, and describe sets either by listing elements or by a property, as in $\{n \in \mathbb{N} : n \text{ is even}\}$.

$A \subseteq B$ (A is a subset of B) means every element of $A$ is also in $B$. Two sets are equal exactly when each is a subset of the other, and proving $A \subseteq B$ and $B \subseteq A$ separately is the standard way to show $A = B$. The empty set $\varnothing$ has no elements and is a subset of every set.

Operations

Each set operation is a logical connective in disguise: $x \in A \cup B$ means $x \in A \lor x \in B$, intersection is “and”, complement is “not”. So the laws of Boolean algebra carry over directly, including De Morgan’s laws:

The diagram below shades any expression you type. Check De Morgan by comparing (A ∪ B)ᶜ with Aᶜ ∩ Bᶜ, or the distributive law by comparing A ∩ (B ∪ C) with (A ∩ B) ∪ (A ∩ C).

Power sets and products

The power set $\mathcal{P}(A)$ is the set of all subsets of $A$. Each element is either in a subset or not, two choices per element, so a set with $n$ elements has $2^n$ subsets. For $A = \{a, b\}$, $\mathcal{P}(A) = \{\varnothing, \{a\}, \{b\}, \{a, b\}\}$.

The Cartesian product $A \times B$ is the set of ordered pairs $(a, b)$ with $a \in A$ and $b \in B$. It has $|A| \cdot |B|$ elements. Unlike sets, pairs are ordered: $(1, 2) \ne (2, 1)$.

Relations

A relation from $A$ to $B$ is any subset $R \subseteq A \times B$. We write $a \mathrel{R} b$ for $(a, b) \in R$. “Is less than”, “divides”, “is a prerequisite of” and “has the same birthday as” are all relations. A relation on a single set $A$ (a subset of $A \times A$) can be drawn as a directed graph or written as a 0/1 matrix with a 1 in row $a$, column $b$ when $a \mathrel{R} b$.

The five properties

Antisymmetric is not the opposite of symmetric. Equality is both; the relation $\{(1, 2), (2, 1), (1, 3)\}$ on $\{1, 2, 3\}$ is neither.

Equivalence relations and partitions

A relation that is reflexive, symmetric and transitive is an equivalence relation. It says when two things are “the same for our purposes”: same remainder mod 5, same parity, same connected component of a graph. Every equivalence relation splits its set into disjoint equivalence classes, and every way of splitting a set into disjoint non-empty pieces comes from exactly one equivalence relation. Choose “same parity” in the checker: the classes are the odd and the even numbers.

Partial orders

A relation that is reflexive, antisymmetric and transitive is a partial order. “Partial” because two elements need not be comparable: under “divides”, neither 4 nor 6 divides the other. Partial orders are drawn as Hasse diagrams, which show only the covering steps and leave the reflexive loops and transitive shortcuts implied. They are everywhere in computer science: dependency graphs, version histories, type hierarchies, and the information orderings of domain theory.

Closures

The transitive closure of $R$ is the smallest transitive relation containing it: add $(a, c)$ whenever there is a chain of $R$-steps from $a$ to $c$. For the relation “has a direct flight to”, the transitive closure is “can be reached by flying”. Warshall’s algorithm computes it in $O(n^3)$ time; the checker’s button uses it. Reflexive and symmetric closures are simpler: add the diagonal, or add every mirrored pair.

Functions

A function $f : A \to B$ is a relation in which every $a \in A$ is related to exactly one $b \in B$, written $f(a)$. $A$ is the domain and $B$ the codomain. The relation-checker preset $x \mapsto x + 1 \bmod 4$ passes the function test; “≤” fails it, since 1 is related to four elements.

Bijections are how mathematics compares sizes. Two finite sets have the same number of elements exactly when there is a bijection between them, and the same definition extends to infinite sets. The even numbers and the natural numbers have the same size, because $n \mapsto 2n$ pairs them up; Cantor’s diagonal argument shows there is no bijection between $\mathbb{N}$ and $\mathcal{P}(\mathbb{N})$, so some infinities are bigger than others.

References

1. K. H. Rosen, Discrete Mathematics and Its Applications, 8th ed., McGraw-Hill, 2019. Chapters 2 and 9.
2. P. R. Halmos, Naive Set Theory, Van Nostrand, 1960.
3. S. Warshall, “A theorem on Boolean matrices”, Journal of the ACM 9(1), 1962. doi:10.1145/321105.321107
4. “Binary relation”, Wikipedia.