Closure
Closure
Closure is a property of a set with respect to a specific operation. A set is said to be closed under an operation if performing the operation on one or more elements of the set always produces a result that is also an element of the set.
For example, take the set of natural numbers, \mathbb{N} = \{1, 2, 3, \ldots\}. This set is closed under the addition operation. Take any two elements of \mathbb{N}, say a and b, then a + b \in \mathbb{N}. Always. There are no a and b, both elements of \mathbb{N}, for which this isn鈥檛 true. So, the set \mathbb{N} is closed under addition.
A proof of this involves induction. Here鈥檚 the basic idea:
The natural numbers can be defined inductively. Let the successor function be S(n) = n + 1. The base case for generating the natural numbers is 1 \in \mathbb{N} (that is, 1 is an element of the natural numbers by definition). The inductive step states that for any n \in \mathbb{N}, the successor of n, S(n) = n + 1, is also in \mathbb{N}. Thus, \mathbb{N} is the set of all numbers generated repeatedly applying the successor function, starting from the base case of 1.
Now, let m be any fixed element of \mathbb{N}. Since S(m) \in \mathbb{N} for any m \in \mathbb{N}, we have m + 1 \in \mathbb{N}. Our inductive hypothesis is that we assume m + n \in \mathbb{N} for the same, fixed m, and some n \in \mathbb{N}. By the definition of addition, we have m + S(n) = S(m + n). By inductive hypothesis m + n \in \mathbb{N}. Since the successor of any natural number is also a natural number, we have S(m + n) \in \mathbb{N}. Thus, m + n \in \mathbb{N} for any fixed m \in \mathbb{N}, for all n \in \mathbb{N}.
Since the argument applies to any fixed m \in \mathbb{N}, it generalizes to all m, n \in \mathbb{N}. Thus, \mathbb{N} is closed under addition. Done.
For an example in which a set is not closed under some operation, consider subtraction. Unlike addition, the set \mathbb{N} is not closed under subtraction. To prove this, all we need is one counterexample. Let m = 1, and n = 2. Both m, n \in \mathbb{N}. However, m - n \not \in \mathbb{N}. 1 - 2 = -1, and -1 \not \in \mathbb{N}, and there鈥檚 a counterexample. Therefore, \mathbb{N} is not closed under subtraction.
Relevance for theory of computation
As one example, if you are studying theory of computation, you鈥檒l encounter closure properties of certain classes of languages. For example, regular languages are closed under union, intersection, complementation, concatenation, and Kleene star operations. This means, for example, if we have two regular languages, A and B, then their intersection A \cap B is also a regular language.
Copyright 漏 2024鈥�2025 Clayton Cafiero