Closures

What is the smallest set containing $S$ that "respects" some operation? That is the question closure answers. Start with ${2}$ and ask: what is the smallest set containing $2$ that is closed under addition? Answer: ${2, 4, 6, 8, \ldots}$. Start with a relation $R$ and ask: what is the smallest transitive relation containing $R$? Answer: its transitive closure. This pattern recurs everywhere — subgroups generated by a set, topological closures, the linear span of vectors, the deductive closure of axioms, the reachability set of a graph. Each is the smallest extension that adds just enough to satisfy a desired property.

Closed under an operation

A set $C$ is closed under a binary operation $*$ if $a, b \in C$ implies $a * b \in C$. Examples:

• $\mathbb{Z}$ is closed under addition, subtraction, multiplication, but not division.
• $\mathbb{N}$ is closed under addition and multiplication, but not subtraction ($3 - 5 \notin \mathbb{N}$).
• ${0, 1}$ is closed under multiplication but not addition ($1 + 1 = 2 \notin {0, 1}$).

The closure of a set

The closure of $S$ under $\ast$∗ is the smallest set $\overline{S}$ such that $S \subseteq \overline{S}$ and $\overline{S}$ is closed under $\ast$. Formally,

The intersection of any family of closed sets is closed, so this intersection is itself closed; and it is contained in every closed superset of $S$, so it is the smallest. Operationally, you build $\overline{S}$ by iteratively adding any "missing" element forced by closure, until nothing new appears.

Closures of relations

For a relation $R$ on $A$:

• The reflexive closure $r(R) = R \cup {(a, a) \mid a \in A}$ adds exactly the diagonal pairs needed.
• The symmetric closure $s(R) = R \cup R^{-1}$ adds the reverse of every pair.
• The transitive closure $t(R) = R \cup R^2 \cup R^3 \cup \cdots = \bigcup_{n \geq 1} R^n$, where $R^n$ is the $n$-fold composition. A pair $(a, b)$ lies in $t(R)$ iff there is a chain $a = x_0, x_1, \ldots, x_n = b$ with each consecutive pair in $R$.

Pause and think: What is the closure of ${2, 3}$ under addition in $\mathbb{Z}^+$? (You can reach 4 = 2+2, 5 = 2+3, 6 = 3+3, then everything $\geq 4$.) Why doesn’t $1$ end up in the closure?

Try it

• Predict: is ${-1, 0, 1}$ closed under multiplication? Under addition? Verify by listing every product/sum.
• Compute the transitive closure of $R = {(1, 2), (2, 3), (3, 4)}$.
• Compute the reflexive closure of $R = {(1, 2), (2, 3)}$ on ${1, 2, 3}$.
• Compute the symmetric closure of $R = {(1, 2), (3, 4)}$.
• Find the closure of ${4}$ under the operation $x \mapsto x + 7$ (treat as a unary operation). What set do you get?

A trap to watch for

Closures depend on both the starting set and the operation. The same starting set yields different closures under different operations: the closure of ${1}$ is ${1}$ under multiplication, $\mathbb{Z}^+$ under addition, and the rationals under "addition, subtraction, multiplication, division by non-zero." Also note that taking closures one at a time does not commute in general — the symmetric closure of the transitive closure is not always the transitive closure of the symmetric closure.

What you now know

You can decide whether a set is closed under a given operation, define and compute the closure as the smallest closed superset, and compute the reflexive, symmetric, and transitive closures of any relation. Section 5.5 tackles the dual notions of image and preimage, which let you push functions through subsets of the domain and codomain.

References

• Velleman, D. J. (2019). How to Prove It (3rd ed.). Cambridge University Press, §5.4.
• Hammack, R. (2018). Book of Proof, ch. 11.
• Bloch, E. D. (2011). Proofs and Fundamentals (2nd ed.). Springer, ch. 5.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press, §22.5 (Tarjan’s SCC), §25.2 (Floyd-Warshall, transitive closure).
• Munkres, J. R. (2000). Topology (2nd ed.). Prentice Hall, §17 (topological closure).