For a tuple of functions $\overline{p}$ on a set $Y$, let $cl_{\overline{p}}$ be the associated closure operation: $cl_{\overline{p}}(Z)$ is the smallest subset of $Y$ containing $Z$ and closed under each of the operations in $\overline{p}$. For $\overline{p}, Y$ as above and $A\subseteq Y$, let $\sharp_{\overline{p},Y}(A)$ be the size of the smallest set $\subseteq\mathcal{P}(Y)$ contianing $A$ as an element and closed under complementation and $cl_{\overline{p}}$.

Given an algebra $\mathcal{A}$ (in the sense of universal algebra), let the Kuratowski spectrum of $\mathcal{A}$ be the set of cardinals $n$ with the following property:

For some $\mathcal{B}\in\mathsf{HSP}(\mathcal{A})$ and some finite set $\overline{p}=p_1,...,p_k$ of polynomials (= terms with parameters) in $\mathcal{B}$, there is an $X\subseteq\mathcal{B}$ with $\sharp_{\overline{p}, \mathcal{B}}(X)=n$.

Hammer proved (see the introduction to Shallit/Willard) a general result that implies that we always have the Kuratowski spectrum is a subset of $[14]=\{1,2,...,14\}$. Meanwhile, $2$ is always in the Kuratowski spectrum (consider the trivial algebra), and it's easy to whip up examples of algebras with Kuratowski spectrum either of the extremes $[14]$ or $\{2\}$.

($1$ is impossible for the silly reason that the empty set isn't allowed as a carrier set of an algebra. If we do allow empty algebras, then every Kuratowski spectrum contains $\{1,2\}$, and the interesting question is what happens between $\{1,2\}$ and $[14]$.)

I'm generally curious about what the Kuratowski spectrum tells us about an algebra. One natural question here is which subsets of $[14]$ occur as Kuratowski spectra, but that seems difficult. I'm hoping the following will be easier to answer:

Question 1: Are there nontrivial algebras with Kuratowski spectrum $\not=[14]$?

In case the answer is yes, the natural follow-up question is:

Question 2: Are there algebras with incomparable (with respect to $\subseteq$) Kuratowski spectra?


1 Answer 1


This is an affirmative answer to the first question.

Let $\mathcal{A}$ be any algebra whose fundamental operations are constant. Let $\mathcal{B}\in\mathsf{HSP}(\mathcal{A})$ be any algebra. The fundamental operations of $\mathcal{B}$ will also be constant, so the polynomial operations of $\mathcal{B}$ will be constant operations or projection operations.

Fix a sequence $\overline{p}=(p_1,\ldots,p_k)$ of polynomial functions of $\mathcal{B}$. Let $C$ be the set of images of the constant functions in the sequence $\overline{p}$. For any subset $Z\subseteq B$, one verifies that $cl_{\overline{p}}(Z)=Z\cup C$.

If we start with any subset $X\subseteq B$ and close under $cl_{\overline{p}}$ and complementation ($Z\mapsto Z^c := B-Z$), we can only generate:

$$ \{X, X^c, X\cup C, X^c\cup C, X\cap C^c, X^c\cap C^c\}. $$

Thus, at most 6 sets can be generated from $X$ by $cl_{\overline{p}}$ and complementation, not 14.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.