Prove that $cl_{f}(A)= \bigcap\{C:A\subseteq C \subseteq B \text{ and } C \text{ is closed under } f\}$

Question

Let $B$ be a set and $f:B^m \rightarrow B$. We say that a subset $C \subseteq B$ is closed under $f$ if for all $x_1,...,x_m \in C, f(x_1,...,x_m) \in C$. Note that $B$ itself is closed under $f$.

Prove that $cl_{f}(A)= \bigcap\{C:A\subseteq C \subseteq B \text{ and } C \text{ is closed under } f\}$. (Hint: you need to show that the right-hand side is closed under $f$)

My attempt:

We want to show that $cl_{f}(A) \subseteq \bigcap\{C:A\subseteq C \subseteq B \text{ and } C \text{ is closed under } f\}$ and vice-versa. Observe $cl_{f}(A).$ By definition, $cl_{f}(A)$ is the smallest subset of $B$ which contains $A$ and is closed under $f$. By definition, a subset $C\subseteq B$ is closed under $f$ if for all $x_1, ..., x_m \in C$, then $f(x_1,...,x_m)\in C$. We have that $cl_{f}(A) \subseteq B$. We also know that $cl_{f}(A)$ contains $A$, thus $A\subseteq B$. Hence, putting this together, we have that $A \subseteq cl_{f}(A) \subset B$. As $C$ is closed under $f$, then we have that $cl_{f}(A) \subseteq C$, $cl_{f}(A) \subseteq \bigcap\{C:A\subseteq C \subseteq B \text{ and } C \text{ is closed under } f\}$.

Does the first part of my proof make sense? What am I missing or doing wrong? It seems a bit too straightforward.

Answer 1

I am slightly annoyed with your question... Not your question, but the question you are citing. Here is why.

You say $\operatorname{cl}_f(A)$ is defined to be the smallest subset of $B$ containing $A$ and closed under $f$. The “smallest” (the “minimum”) means that, as you said, for every set $C$ with that same property, it is $\operatorname{cl}_f(A)\subseteq C$. The relation used to determine the notion of being “smallest” is the set inclusion, $\subseteq$, which is a partial ordering on the set $\mathcal{P}(B)$ of all subsets of $B$.

Now, how do we know that a minimum exists? You cannot define $\operatorname{cl}_f(A)$ the way you define it, unless you prove that this minimum exists, and is unique. Luckily, minima are always unique, and so the burden is on proving existence.

Now to what is annoying me. Your problem seems to assume that the minimum exists, because it refers to $\operatorname{cl}_f(A)$ as something well known and defined. Once you can assume that, it is indeed easy, and no wonder you feel it is a bit too straightforward. On the other hand, the hint given to you is essentially equivalent with proving that the minimum exists in the first place.

So it seems that the author of the problem wasn’t sure, to start with, whether we can assume that $\operatorname{cl}_f(A)$ is well defined, or not.

I believe the proper question would be to prove that $\operatorname{cl}_f(A)$ is well defined. The proof would make use of the right-hand side: you would take the set $\bigcap\{ C\mid A\subseteq C\subseteq B, C\text{ closed under }f\}$ and prove that that set satisfies the conditions for the definition of closure:

• It itself is closed under $f$ (your “hint”) and is “between” $A$ and $B$;
• It is contained in every other subset of $B$ with the same properties (obvious, as it is the intersection of those).