The orbit of closure-involution operations: the case of Boolean functions (Q2143383)

In 1922, Kuratowski proved his ``closure-complement theorem'', which asserts that if \(T\) is a topological space and \(A\subseteq T\), then there are at most \(14\) different sets that can occur in the sequence \[ A, cA, kA, kcA, ckA, ckcA, kckA, \ldots, \] where \(kX=\overline{X}\) is topological closure and \(cX=T\setminus X\) is set-theoretic complementation. This paper concerns an analogue of Kuratowski's theorem. Following Kuratowski, the focus is on a set \(T\), a closure operator \(k: {\mathcal P}(A)\to {\mathcal P}(A)\) and an involution on subsets \(c: {\mathcal P}(A)\to {\mathcal P}(A)\). The goal is to determine, given \(A\subseteq T\), how many sets can be generated by \(A\) using \(k\) and \(c\). One writes \(T(k,c)=\{n_1,n_2,\ldots\}\) for the set of possible outcomes as \(A\) ranges over subsets of \(T\). Thus, \(T(k,c)=\{1,3\}\) means that, given any subset \(A\subseteq T\), one will generate either \(1\) or \(3\) different sets using \(k\) and \(c\), and that both possibilities are realized. In the first part of the paper, the topological space \(A\) of Kuratowski is replaced by the set \(\mathcal O\) of all Boolean functions, the topological closure operator \(k\) of Kuratowski is taken to be the superposition closure operator \(S\), and the set-theoretic complementation operator \(c\) of Kuratowski is taken to be one of the involutions from the set \(\{c, \neg, d\}\). Here \(c\) again denotes set-theoretic complementation, as in Kuratowski's theorem, but \(\neg\) is the negation operator (if \(A\subseteq {\mathcal O}\), then \(\neg A = \{\neg f\;|\;f\in A\}\)) and \(d\) is a conjugation by \(\neg\) (if \(A\subseteq {\mathcal O}\), then \(dA = \{\neg f(\neg x_1,\ldots,\neg x_n)\;|\;f(x_1,\ldots,x_n)\in A\}\)). The goal is to determine, given \(A\subseteq {\mathcal O}\), how many sets will be generated by \(A\) using \(S\) and one of the involutions \(i\in \{c,\neg,d\}\). The number of sets that can be generated depends on the choice of \(A\) and the choice of involution \(i\in \{c,\neg,d\}\). One writes \({\mathcal O}(S,i)=\{n_1,\ldots,n_r\}\) for the set of possible outcomes as \(A\) ranges over subsets of \({\mathcal O}\). The results of the first part of the paper are: \begin{itemize} \item \({\mathcal O}(S,c) = \{2,4,6\}\). \item \({\mathcal O}(S,d) = \{1,2,3,4\}\). \item \({\mathcal O}(S,\neg) = \{1,2,3,4,5,7\}\) or \(\{1,2,3,4,5,6,7\}\). (The paper does not resolve whether \(6\in {\mathcal O}(k,\neg)\).) \end{itemize} The results of the second part of the paper involve closure operators \(c_1, c_2^n, c_3^n\) on \(\mathcal O\) that are different from the superposition operator \(S\). These closure operators, which have complicated definitions, are created for the purpose of showing that \({\mathcal O}(S,i)\) depends strongly on \(S\). The results obtained are that \begin{itemize} \item \({\mathcal O}(c_1,d) = \{1,2,3,\infty\}\). \item \({\mathcal O}(c_2^n,d) = \{1,2,3\}\cup \{4,6,\ldots,2n+2\}\). \item \({\mathcal O}(c_3^n,d) = \{1,2,3\}\cup \{5,7,\ldots,2n+3\}\). \end{itemize} The paper ends with a section suggesting problems and generalizations.