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.

  • $\begingroup$ WHat is B here for you $\endgroup$
    – Guy Fsone
    Jan 30, 2018 at 22:35
  • $\begingroup$ What is $B $, what is $f $, what do they have to do with each other, and why is this not trivial? $\endgroup$ Jan 30, 2018 at 22:48
  • $\begingroup$ Edited......... $\endgroup$ Jan 30, 2018 at 22:59
  • $\begingroup$ @AndrésE.Caicedo I find this a bit trivial too... but is my explanation alright for one side? $\endgroup$ Jan 30, 2018 at 23:03

1 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).
  • $\begingroup$ I see where you are coming from and I agree. $\endgroup$ Jan 30, 2018 at 23:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .