Closures Again

In §5.4 a closure was defined "from outside" — the smallest set with a property, computed as an intersection of all closed sets containing the seed. That definition is correct but it tells you nothing about how to actually build the closure. Induction unlocks a constructive definition "from inside": start with the seed $A$, apply the operation once to get a new layer, apply it to the new layer to get another, and so on. The union of all layers is the closure. Once you have the construction, induction on the layer index becomes the proof tool for everything: every element of the closure has a finite construction history, and you can reason about it the way you reason about natural numbers.

The inductive construction

Let $A \subseteq S$ and let $\star : S \times S \to S$ be a binary operation. Define a sequence of sets stage by stage:

The closure of $A$ under $\star$ is

Each $A_n$ is a finite (or at least bounded) approximation; the union gathers them all. An element $x$ belongs to $\overline{A}$ exactly when there is some finite stage $n$ where $x \in A_n$.

Transitive closure of a relation

Let $R \subseteq S \times S$. Define $R^1 = R$ and $R^{n+1} = R^n \circ R$ where $\circ$ is relational composition: $(a, b) \in R^n \circ R$ iff there exists $c$ with $(a, c) \in R^n$ and $(c, b) \in R$. The transitive closure of $R$ is

The pair $(a, b) \in R^n$ means there is a path of length $n$ from $a$ to $b$ stepping along arrows of $R$. Thus $R^+$ is the relation "$b$ is reachable from $a$ by following $R$ for one or more steps." The reflexive-transitive closure $R^*$ adds the identity pairs $(a, a)$ to allow zero-step paths.

Why it really is the smallest closed set

Two facts together pin down $\overline{A}$ as the smallest set containing $A$ and closed under $\star$:

(i) $\overline{A}$ is closed. If $a, b \in \overline{A}$, then $a \in A_m$ and $b \in A_n$ for some $m, n$. Let $N = \max(m, n)$. Both belong to $A_N$ (since the $A_i$ are nested), so $a \star b \in A_{N+1} \subseteq \overline{A}$.

(ii) Any closed $C$ containing $A$ also contains $\overline{A}$. Prove by induction on $n$ that $A_n \subseteq C$. Base $n = 0$: $A_0 = A \subseteq C$. Step: if $A_n \subseteq C$, then for any $a, b \in A_n$ we have $a, b \in C$, so $a \star b \in C$ (since $C$ is closed). Thus $A_{n+1} \subseteq C$. Taking the union, $\overline{A} \subseteq C$. $\blacksquare$

Pause and think: consider $A = {2} \subseteq \mathbb{Z}^+$ under addition. What is $A_0, A_1, A_2$? Find a stage $n$ at which $10 \in A_n$ but $10 \notin A_{n-1}$.

Try it

• Predict: closure of ${3}$ under addition in $\mathbb{Z}^+$. Compute $A_0, A_1, A_2$ and conjecture the full closure.
• Predict the transitive closure of $R = {(1, 2), (2, 3), (3, 4)}$ on ${1, 2, 3, 4}$. Compute $R^1, R^2, R^3$ explicitly.
• Is $\mathbb{Z}$ closed under subtraction? Under division? For each, decide and give a concrete witness.
• On paper, draw a small relation on ${1, 2, 3, 4}$ as an arrow diagram (the widget above can hold the base relation $R$). Compute $R^1, R^2, R^3$ stage by stage by listing the pairs that appear at each step, then union them for $R^+$. Predict which new pairs each stage adds before checking.

A trap to watch for

It is tempting to assume that some single stage $A_N$ already equals the entire closure. That is generally false when $A$ is infinite or the operation produces infinitely many new elements. For example, with $A = {1}$ under addition, $A_1 = {1, 2}$, $A_2 = {1, 2, 3, 4}$, $A_3 = {1, 2, \ldots, 8}$. No single $A_n$ equals $\mathbb{Z}^+$; the closure is the union of all stages. Conversely, if the operation produces no genuinely new elements at some stage (i.e., $A_{n+1} = A_n$), then the sequence has stabilised and $A_n$ is the closure. Always check whether the construction stabilises before claiming a finite description.

What you now know

You can describe a closure constructively as a union of stages, prove it equals the smallest closed set containing the seed, and use induction on the stage index to verify properties of every element of the closure. You can compute small transitive and reflexive closures by hand. This is also the structural template behind "generated by" in algebra, recursive CTE in databases, and Warshall's algorithm in graph theory — all variations on the same idea: iterate the operation until nothing new appears, then bundle the work into a single proof by induction on stage.

References

• Velleman, D. J. (2019). How to Prove It: A Structured Approach (3rd ed.). Cambridge University Press, §6.5.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press, ch. 25 (all-pairs shortest paths / Warshall).
• Hammack, R. H. (2018). Book of Proof (3rd ed.). Virginia Commonwealth University, ch. 11.
• Graham, R. L., Knuth, D. E., Patashnik, O. (1994). Concrete Mathematics (2nd ed.). Addison-Wesley, ch. 1.
• Pierce, B. C., et al. (2018). Software Foundations, Vol. 1: Logical Foundations. Online, ch. "Relations."