My question is about closing sets under operations. First, I need a definition:

Definition: Let $A$ be a set and take a function $f : A^n \rightarrow A$ for $n \in \mathbb{N}_{\geq 0}$. For a set $S$, we define the closure of $S$ under $f$, $c_f (S)$, inductively as follows: define $S_0 = S$. For $i \in \mathbb{N}_{\geq 0}$, with $S_i$ defined, set $$S_{i+1} = S_i \cup \{ f ( a_1, ..., a_n ) : a_1, ..., a_n \in S_i \}$$ Define $c_f (S) = \bigcup_{i = 0}^{\infty} S_i$.

My question is this: let $A$ be a set. Take $n_1, ..., n_k \in \mathbb{N}_{\geq 0}$ and $f_i : A^{n_i} \rightarrow A$ for $1 \leq i \leq k$. Consider the set $S$. When is $c_{f_k} \circ c_{f_{k-1}} \circ \cdots \circ c_{f_1} (S)$ closed under $f_i$ for each $1 \leq i \leq k$? I am asking for interesting properties one can put on $f_i$ to make this true.

This is equivalent to a seemingly simpler question: let $A$ be a set and take functions $f : A^n \rightarrow A$ and $g: A^m \rightarrow A$. Take a set $S$ which is closed under $g$. What are some interesting properties we can put on $f$ and $g$ so that $c_f (S)$ closed under $g$?

Here are some very familiar examples:

Example: Let $G$ be a group. For a subset $S \subset G$, we can form a subgroup of $G$ by adding $e$ (closing under the $0$-ary function that corresponds to the group identity), closing under inverses, and then closing under the group multiplication. The resulting set is then closed under all of these operations.

Example: Let $R$ be a ring. For a subset $S \subset R$, we can form a subring of $R$ by adding $0$ and $1$, (closing under the $0$-ary functions corresponding to $0$ and $1$), closing under products, and then closing under sums.

Example: Take a set $A$ and operations $\sigma : A^2 \rightarrow A$ and $\mu : A^2 \rightarrow A$. Suppose that $\mu(a, \sigma(b, c)) = \sigma(\mu(a, b) , \mu(a, c))$ and $\mu(\sigma(a, b), c) = \sigma(\mu(a, c), \mu(b, c))$ for each $a, b, c \in A$. Then, if $S \in A$ is closed under $\mu$, then $c_{\sigma}(S)$ is closed under $\mu$.

  • 5
    $\begingroup$ Another interesting example, from universal algebra: the HSP monoid. Let $H, S, P$ be the operators on classes of structures closed under isomorphism, given by closing under homomorphic images, substructures, and (arbitrarily indexed) products, respectively. Then $HSP=SHSP=PHSP=HHSP$. On the other hand, order matters: e.g. $PSH$ applied to the class containing only the two-element Boolean algebras doesn't contain any atomless Boolean algebras, which are in HSP applied to that class. $\endgroup$ Apr 28, 2018 at 21:28
  • 1
    $\begingroup$ Adding to @NoahSchweber 's comment, Pigozzi found the 17 different closure operators coming from $H, S$, and $P$ in his paper ``On some operations on classes of algebras.'' $\endgroup$
    – Eran
    Apr 28, 2018 at 21:45
  • 3
    $\begingroup$ I am not seeing how this is different from generating subalgebras. One can consider this from the viewpoint of lattices of subalgebras. If g is part of the clone of f, then g adds nothing to the concept. Have you studied closure operators in general? Gerhard "I Recommend 'Algebras, Lattices, Varieties'" Paseman, 2018.04.28. $\endgroup$ Apr 28, 2018 at 23:42
  • 2
    $\begingroup$ @GerhardPaseman By "the clone of f", do you mean (as I would) the smallest clone of operations on $A$ that has f as a member? If so, then your comment is correct but doesn't apply to the examples in the question or the one in Noah Schweber's comment. For example, in a group, the operation of taking inverses is not generally in the clone of multiplication. $\endgroup$ Apr 29, 2018 at 11:31


You must log in to answer this question.

Browse other questions tagged .