2.1 Discrete duality

This is the most basic duality we use, and it provides a correspondence between powerset Boolean algebras (these are the complete and atomic Boolean algebras) and sets. Given such Boolean algebra $\mathcal{B}$ , its dual is its set of atoms (i.e., the set of nonzero minimal elements), denoted ${\rm At}(\mathcal{B})$ and, given a set X, its dual is the Boolean algebra $\mathcal{P}(X)$ . Clearly going back and forth yields isomorphic objects. If $h\colon\mathcal{A}\to\mathcal{B}$ preserves arbitrary meets and joins, the dual of h, denoted ${\rm At}(h)\colon{\rm At}(\mathcal{B})\,{\to}\,{\rm At}(\mathcal{A})$ , is given by the adjunction:

\begin{equation*} \forall \ a\,{\in}\, \mathcal{A},\ x\,{\in}\, {\rm At}(\mathcal{B}) \quad\left({\rm At}(h)(x)\leq a \iff x\leq h(a)\right).\end{equation*}

For example, if $\iota\colon\mathcal{A}\rightarrowtail\mathcal{P}(X)$ is the inclusion of a finite Boolean subalgebra of a powerset, then ${\rm At}(\iota):X\twoheadrightarrow{\rm At}(\mathcal{A})$ is the quotient map corresponding to the finite partition of X given by the atoms of $\mathcal{A}$ . Conversely, given a function $f{\colon} X{\to} Y$ , the dual is just $f^{-1}{\colon}\mathcal{P}(Y){\to}\mathcal{P}(X)$ .

2.2 Stone duality

Since it will be useful in the next section, we will present Stone duality as a restriction of a dual adjunction between Boolean algebras and topological spaces.

Generally Boolean algebras do not have enough atoms, and we have to consider ultrafilters instead (which may be seen as “searches downwards” for atoms). Given an arbitrary Boolean algebra $\mathcal{B}$ , an ultrafilter of $\mathcal{B}$ is a subset $\gamma$ of $\mathcal{B}$ satisfying:

• ○ $\gamma$ is an upset, that is, $a\,{\in}\, \gamma$ and $a\leq b$ implies $b\,{\in}\, \gamma$ ;

• ○ $\gamma$ is closed under finite meets, that is, $a,b\,{\in}\,\gamma$ implies $a\wedge b\,{\in}\, \gamma$ ;

• ○ for all $a\in\mathcal{B}$ exactly one of a and $\neg a$ is in $\gamma$ .

We will denote the set of ultrafilters of $\mathcal{B}$ by $X_\mathcal{B}$ , and we will consider it as a topological space equipped with the topology generated by the sets $\widehat{a}=\{\gamma\in X_\mathcal{B}\mid a\in\gamma\}$ for $a\in\mathcal{B}$ . The last property in the definition of ultrafilters implies that these basic open sets are also closed (and thus clopen). The resulting spaces are compact, Hausdorff, and have a basis of clopen sets. Such spaces are called Boolean spaces. Given a homomorphism $h\colon\mathcal{A}\to\mathcal{B}$ between Boolean algebras, the inverse image of an ultrafilter is an ultrafilter and thus $h^{-1}$ induces a map $f:X_\mathcal{B}\to X_\mathcal{A}$ . Since $f^{-1}(\widehat {a}) = \widehat {h(a)}$ for every $a \in \mathcal{A}$ , this map is continuous.

Conversely, given any topological space X, its clopen subsets form a Boolean algebra ${\sf Clopen}(X)$ , and given a continuous function $f\colon X\to Y$ , the inverse map $f^{-1}$ restricts and co-restricts to a homomorphism ${\sf Clopen}(Y) \to {\sf Clopen}(X)$ of Boolean algebras.

These assignments define a dual adjunction between Boolean algebras and topological spaces. When seen as an adjunction between the opposite category of Boolean algebras and that of topological spaces, the counit at a Boolean algebra $\mathcal{B}$ , and unit at a topological space X are, respectively, given by:

\[\varepsilon_\mathcal{B}:\mathcal{B} \to {\sf Clopen}(X_\mathcal{B}), \qquad a \mapsto \widehat a\]

and

(1) \begin{equation}\eta_X: X \to X_{{\sf Clopen}(X)}, \qquad x \mapsto \{K \in {\sf Clopen}(X) \mid x \in K\}.\end{equation}

One can show that $\varepsilon_\mathcal{B}$ is always an isomorphism, while $\eta_X$ is an isomorphism if and only if X is a Boolean space. Thus, this adjunction restricts to a duality between Boolean algebras and Boolean spaces: the so-called Stone duality.

2.3 Compactification of topological spaces

We consider two compactifications of topological spaces: the Čech–Stone and the Banaschewski compactifications, the latter being defined only for zero-dimensional spaces. We also relate them with the dual spaces of suitable Boolean algebras.

Let X be a topological space. Then, the Čech–Stone compactification of X is the unique (up to homeomorphism) compact Hausdorff space $\beta (X)$ together with a continuous function $e: X\to \beta (X)$ satisfying the following universal property: every continuous function $f: X \to Z$ into a compact Hausdorff space Z uniquely determines a continuous function $\beta f: \beta (X) \to Z$ making the following diagram commute:

In the case where X is a completely regular $T_1$ space, the map e is in fact an embedding (Willard Reference Willard2004, Section 19). This is for instance the case of discrete and of Boolean spaces. It may be proved that, for a set S, the dual space of $\mathcal{P}(S)$ is the Čech–Stone compactification of the discrete space S. This fact has been extensively used in the topo-algebraic approach to nonregular languages over finite alphabets (see e.g., Gehrke et al. Reference Gehrke, Grigorieff and Pin2010, Reference Gehrke, Petrişan and Reggio2016). However, as already mentioned, in the present work, we also consider languages over profinite alphabets. For that reason, we will be handling dual spaces of Boolean algebras of the form ${\sf Clopen}(X)$ , for spaces X that are not discrete. In the case where X is zero-dimensional, the dual space of ${\sf Clopen}(X)$ is known as the Banaschewski compactification (Banaschewski 1995, Reference Banaschewski1964) of X, and it is denoted by $\beta_0(X)$ . At the level of morphisms, $\beta_0$ assigns to each continuous map the dual of the Boolean algebra homomorphism taking inverse image on clopens. Moreover, for a zero-dimensional space X, the unit (1) of the dual adjunction between Boolean algebras and topological spaces is an embedding $\eta_X: X \rightarrowtail\beta_0(X)$ with dense image (see e.g., (see e.g., Porter and Woods Reference Porter and Woods1988, Section 4.7, Proposition (b)), and it is easy to see that for every continuous function $f: X \to Y$ between zero-dimensional spaces the following diagram commutes:

There are some cases where the Čech–Stone and the Banaschewski compactifications coincide, for example, for discrete spaces as mentioned above. More generally, we have the following:

A space is said to have Čech-dimension zero provided that each finite open cover admits a finite clopen refinement. In particular, every compact zero-dimensional space, and so, every Boolean space, has Čech-dimension zero.

Theorem 2.1. (Banaschewski 1995, Theorem 4). A zero-dimensional space X is of Čech-dimension zero if and only if it is normal and the Čech–Stone and Banaschewski compactifications of X coincide.

This is of interest to us as it shows that $\beta$ is given by duality not only for discrete spaces but more generally for spaces of Čech-dimension zero such as $Y^*$ for Y a profinite alphabet (cf. Lemma 3.5 and Theorem 3.6).

2.4 Projective and direct limits

A projective limit system (also known as an inverse limit system, or a cofiltered diagram) $\mathcal{F}$ of sets assigns to each element i of a directed partially ordered set I, a set $S_i$ , and to each ordered pair $i\geq j$ in I, a map $f_{i,j}:S_i \to S_j$ so that for all $i, j, k \in I$ with $i \ge j \ge k$ we have $f_{i,i} = id_{S_i}$ and $f_{j,k}\circ f_{i,j} = f_{i,k}$ . The projective limit (or inverse limit or cofiltered limit) of $\mathcal{F}$ , denoted $\lim\limits_{\longleftarrow} \mathcal{F}$ , comes equipped with projection maps $\pi_i: \lim\limits_{\longleftarrow} \mathcal{F}\to S_i$ compatible with the system. That is, for $i,j\in I$ with $i\geq j$ , $f_{i,j} \circ \pi_i= \pi_j$ . Further, it satisfies the following universal property: whenever $\{\pi_i':S' \to S_i\}_{i \in I}$ is a family of maps satisfying $f_{i,j} \circ \pi'_i= \pi'_j$ for all $i\geq j$ , there exists a unique map $g: S'\to\lim\limits_{\longleftarrow} \mathcal{F}$ satisfying $\pi_i' = \pi_i \circ g$ , for all $i \in I$ .

The notion dual to projective limit, obtained by reversing the directions of the maps, is that of direct limit (also known as an injective limit, inductive limit, or filtered colimit).

There are several things worth noting about these notions. First, the projective limit of $\mathcal{F}$ may be constructed as follows:

(2) \begin{equation} \lim\limits_{\longleftarrow} \mathcal{F} = \left\{(s_i)_{i \in I} \in \prod_{i \in I}S_i \mid f_{i,j} (s_i) = s_j \text{ whenever $i \ge j$}\right\}.\end{equation}

Second, projective limits of finite sets, called profinite sets, are equivalent to Boolean spaces. If each $S_i$ is finite, then it is a Boolean space in the discrete topology, and the projective limit is a closed subspace of the product and thus again a Boolean space. Conversely, a Boolean space is the projective limit of the projective system of its finite continuous quotients, corresponding via duality to the fact that Boolean algebras are locally finite and, thus, direct limits of their finite subalgebras.

Third, one also has projective systems and projective limits of richer structures than sets, being the connecting maps required to be morphisms of the appropriate kind. In this work, we will use the description of projective limits in the categories of topological spaces and of monoids. A very useful fact is that, in these settings, projective limits are given as for sets with the obvious enriched structure.

2.5 Biactions and semidirect products of monoids

Let S be a set and M a monoid. We denote the identity of M by 1. A biaction of M on S is a family of functions:

\[\lambda_m: S \to S, \qquad \text{and}\qquad \rho_m: S \to S,\]

for each $m \in M$ , that satisfy the following conditions:

• ○ $\{\lambda_m\}_{m \in M}$ induces a left action of M on S, that is, $\lambda_1$ the identity function on S, and for every $m, m' \in M$ , the equality $\lambda_m \circ \lambda_{m'} = \lambda_{m m'}$ holds;

• ○ $\{\rho_m\}_{m \in M}$ induces a right action of M on S, that is, $\rho_1$ the identity function on S, and for every $m, m' \in M$ , the equality $\rho_{m'} \circ \rho_{m} = \rho_{mm'}$ holds;

• ○ $\{\lambda_m\}_{m \in M}$ and $\{\rho_m\}_{m \in M}$ are compatible, that is, for every $m, m' \in M$ , we have $\lambda_m \circ \rho_{m'} = \rho_{m'} \circ \lambda_m$ .

In the case where S is also a monoid, we have the notion of a monoid biaction. In order to improve readability, we shall denote the operation on S additively, although S is not assumed to be commutative. A monoid biaction of M on S is a biaction of M on the underlying set of S, satisfying the following additional properties:

• • $\lambda_{m_1} \circ \rho_{m_2} (s_1 + s_2) = \lambda_{m_1} \circ \rho_{m_2} (s_1 ) + \lambda_{m_1} \circ \rho_{m_2} (s_2)$ , for all $m_1,m_2\in M$ , and $s_1, s_2 \in S$ ;

• • $\lambda_{m_1} \circ \rho_{m_2} (0) = 0$ , for all $m_1,m_2 \in M$ .

Finally, given such a biaction, we may define a new monoid, called the (two-sided) semidirect product of S and M, usually denoted by $S{**}M$ . The monoid $S{**}M$ has underlying set $S \times M$ , and its binary operation is defined by:

\[(s_1, m_1)(s_2, m_2) = (\rho_{m_2}(s_1) + \lambda_{m_1}(s_2),\, m_1m_2).\]

2.6 Formal languages

Let A be a set, which we call an alphabet. A word over A is an element of the A-generated free monoid $A^*$ , and a language over A is a set $L \subseteq A^*$ of words, that is, an element of the powerset $\mathcal{P}(A^*)$ . Whenever we write $w = a_0\dots a_{n-1}$ for a word, we are assuming that each of the $a_i$ ’s is a letter. If $w = a_0\dots a_{n-1}$ is a word, then we say that w has length n, denoted $\left\lvert w\right\rvert = n$ . The fact that $A^*$ is a monoid means in particular that $A^*$ is equipped with a biaction of itself. By discrete duality, it follows that $\mathcal{P}(A^*)$ also is equipped with a biaction of $A^*$ given as follows. The left (respectively, right) quotient of a language L by a word w is the language $w^{-1}L = \{u \in A^* \mid wu \in L\}$ (respectively, $Lw^{-1} = \{u \in A^* \mid uw \in L\}$ ). We say that a set of languages is closed under quotients if it is invariant under this biaction.

In the discrete duality between complete atomic Boolean algebras and sets, the complete Boolean subalgebras closed under quotients of the powerset $\mathcal{P}(M)$ , where M is a monoid, correspond to the monoid quotients of M (Gehrke Reference Gehrke2016, Theorem 3.26) (see also Dekkers Reference Dekkers2008, Theorem 8.13). In particular, given a language $L \subseteq A^*$ , the discrete dual of $\mathcal{B}_L$ , the complete Boolean subalgebra closed under quotients generated by L, is a monoid quotient $\mu_L: A^*\twoheadrightarrow M_L$ . The monoid $M_L$ is called the syntactic monoid of L, and $\mu_L$ is the syntactic homomorphism of L. The quotient map $\mu_L$ is given by the corresponding congruence relation, known as the syntactic congruence of L, which, by the definition of $\mu_L$ , is given by:

\[ u \sim_L v \iff (\forall x,y \in A^*, \ xuy \in L \iff xvy \in L).\]

Notice that it follows that $L = \mu_L^{-1}(\mu_L[L])$ , that is, L is recognized by $M_L$ via $\mu_L$ . More generally, given a monoid M, a language $L \subseteq A^*$ is said to be recognized by M provided there exists a homomorphism $\mu\colon A^* \to M$ and a subset $P \subseteq M$ satisfying $L =\mu^{-1}(P)$ , or equivalently, provided $L = \mu^{-1}(\mu[L])$ . By duality, the set of languages recognized by $\mu$ is a complete Boolean subalgebra closed under quotients which contains L. Since it must contain $\mathcal{B}_L$ , the syntactic homomorphism of L factors through any homomorphism $\mu$ which recognizes L. That is, the syntactic monoid and homomorphism of L can be thought as the “optimal” recognizer of L.

For a set of languages $\mathcal{S} \subseteq \mathcal{P}(A^*)$ , it is then natural to wonder about the existence of an “optimal” recognizer for all the languages of $\mathcal{S}$ . This leads to the notion of syntactic monoid, homomorphism, and congruence of $\mathcal{S}$ , which are defined via discrete duality for the complete Boolean subalgebra closed under quotients generated by $\mathcal{S}$ . Explicitly, the syntactic congruence of $\mathcal{S}$ , denoted $\sim_\mathcal{S}$ , is the intersection of all the syntactic congruences of the languages of $\mathcal{S}$ , the syntactic monoid is the quotient $M_\mathcal{S} = A^* / {\sim_\mathcal{S}}$ , and the syntactic homomorphism is the canonical projection $\mu_\mathcal{S}: A^* \twoheadrightarrow M_\mathcal{S}$ . The homomorphism $\mu_\mathcal{S}$ is “optimal” in the sense that if $\mu: A^* \to M$ is a homomorphism recognizing every language of $\mathcal{S}$ , then it factors through $\mu_\mathcal{S}$ .

Finally, regular languages are those recognized by finite monoids. It is not hard to see that regular languages over an alphabet A form a Boolean algebra closed under quotients. Beyond regularity, the discrete notion of recognition introduced here is not adequate. In particular, any infinite monoid recognizes uncountably many languages. Recognition of Boolean algebras of (not necessarily regular) languages closed under quotients require the introduction of topology. This will be addressed in Section 4.

So far, we did not require A to be a finite set. In this paper, we will consider languages over profinite alphabets, where the topology of the alphabet will be taken into account (finite alphabets are simply viewed as discrete spaces). Languages over profinite alphabets will be the subject of Section 3. Unless specified otherwise, we will use the letters $A, B, \dots$ to denote finite alphabets, and $X, Y, \dots$ for profinite (not necessarily finite) ones.

2.7 lp-strains and lp-varieties of languages

A homomorphism between free monoids is said to be length-preserving (also called an lp-morphism) provided it maps generators to generators. Therefore, lp-morphisms $A^* \to B^*$ are in a bijection with functions $A \to B$ . Given a map $h:A \to B$ , we use $h^*$ to denote the unique lp-morphism $h^*:A^* \to B^*$ whose restriction to A is h. As we will see in Section 2.10, lp-morphisms are important in the treatment of fragments of logic on words.

Combining Pippenger (Reference Pippenger1997) and Straubing’s (2002) terminology, we call lp-strain of languages an assignment, for each finite alphabet A, of a Boolean algebra $\mathcal{V}(A)$ of languages over A such that, for every lp-morphism $h^*:B^* \to A^*$ , if $L \in \mathcal{V}(A)$ then $(h^*)^{-1}(L)\in \mathcal{V}(B)$ . Since $(h \circ g)^* = h^*\circ g^*$ whenever f and g are composable set functions, each lp-strain of languages defines a presheaf $\mathcal{V}: {\bf Set}_{fin}^{\rm op} \to {\bf BA}$ of Boolean algebras. Moreover, the presheaves obtained in this way are precisely the sub-presheaves of the presheaf $\mathcal{P}: {\bf Set}_{fin}^{\rm op} \to{\bf BA}$ defined by the lp-strain assigning the full powerset $\mathcal{P}(A^*)$ to each finite alphabet A. This notion allows us to extend languages to profinite alphabets (cf. Section 3), which is crucial when handling infinite Boolean algebras of formulas (cf. Section 5.2). Notice that, if $\mathcal{V}$ is an lp-strain of languages, then every function $h: B \to A$ induces dually a continuous function $\widehat h: X_{\mathcal{V}(B)} \to X_{\mathcal{V}(A)}$ making the following diagram commute:

where $A^* \to X_{\mathcal{V}(A)}$ and $B^* \to X_{\mathcal{V}(B)}$ are the maps with dense image obtained by dualizing and restricting the embeddings $\mathcal{V}(A) \rightarrowtail \mathcal{P}(A^*)$ and $\mathcal{V}(B) \rightarrowtail\mathcal{P}(B^*)$ , respectively. This is a particular case of Lemma 3.9, for which we will provide a detailed proof.

In the case where $\mathcal{V}(A)$ is closed under quotients for every alphabet A, we call $\mathcal{V}$ an lp-variety of languages.

2.8 Logic on words

We shall consider classes of languages that are definable in fragments of first-order logic. Variables are denoted by $x,y,z, \ldots$ , and we fix a finite alphabet A. Our logic signature consists of:

• ○ (unary) letter predicates ${\sf P}_a$ , one for each letter $a \in A$ ;

• ○ a set $\mathcal{N}$ of numerical predicates R, each of finite arity. A k-ary numerical predicate R is given by a subset $R \subseteq {\mathbb{N}}^k$ . For instance, the usual (binary) numerical predicate $<$ formally corresponds to the predicate $R = \{(i,j) \mid i,j \in {\mathbb{N}}, \ i < j\}$ ;

• ○ a set $\mathcal{Q}$ of (unary) quantifiers Q, each one being given by a function $Q:\{0,1\}^* \to \{0,1\}$ . For instance, the existential quantifier $\exists$ corresponds to the function mapping $\varepsilon_0 \dots \varepsilon_{n-1} \in \{0,1\}^*$ to 1 exactly when there exists an i so that $\varepsilon_i = 1$ .

Then, (first-order) formulas are recursively built as follows:

• ○ for each letter predicate ${\sf P}_a$ and variable x, there is an atomic formula ${\sf P}_a(x)$ ;

• ○ if $R \in \mathcal{N}$ is a k-ary numerical predicate and $x_1, \dots, x_k$ are (possibly nondistinct) variables, then $R(x_1, \dots, x_k)$ is an atomic formula;

• ○ Boolean combinations of formulas are formulas, that is, if $\phi$ and $\psi$ are formulas, then so are $\phi \wedge \psi$ , $\phi \vee \psi$ , and $\neg \phi$ ;

• ○ if Q is a quantifier, x a variable and $\phi$ a formula, then $Q x \ \phi$ is also a formula.

An occurrence of a variable x in a formula is said to be free provided it appears outside of the scope of a quantifier Q x. A sentence is a formula with no free occurrences of variables.

A context x is a finite set of distinct variables. Given disjoint contexts x and y, we denote by ${\bf x}{\bf y}$ the union of x and y. Whenever we mention union of contexts, we will assume they are disjoint without further mention. Also, we simply write x to refer to the context $\{x\}$ so that by ${\bf x} x$ we mean the context ${\bf x} \cup \{x\}$ . We denote by $\left\lvert{\bf x}\right\rvert$ the cardinality of x. The models of a formula will always be considered in a fixed context. We say that $\phi$ is in context x provided all the free variables of $\phi$ belong to x. Notice that, if $\phi$ is in context x, then it is also in every other context containing x.

Models of sentences in the empty context are words over A. More generally, models of formulas in the context $\bf x$ are given by $ {\bf x}$ -marked words, that is, words $w \in A^*$ equipped with an interpretation $ {\bf i} \in \{0, \dots, \left\lvert w\right\rvert -1\}^{\bf x}$ of the context x. We identify maps from x to $\{0, \dots, \left\lvert w\right\rvert - 1\}$ with $\left\lvert{\bf x}\right\rvert$ -tuples ${\bf i} = (i_1, \dots, i_{\left\lvert{\bf x}\right\rvert }) \in \{0, \dots, \left\lvert w\right\rvert -1\}^{\left\lvert{\bf x}\right\rvert} \subseteq {\mathbb{N}}^{\left\lvert{\bf x}\right\rvert}$ . We denote the set of all $ {\bf x}$ -marked words by $A^* \otimes {\mathbb{N}}^{ {\bf x}}$ . Given a word $w \in A^*$ and a vector ${\bf i} = (i_1, \dots, i_{\left\lvert{\bf x}\right\rvert })\in \{0, \dots, \left\lvert w\right\rvert -1\}^{\left\lvert{\bf x}\right\rvert}$ , we denote by $(w,{\bf i})$ the marked word based on w equipped with the map given by i. Moreover, if x and y are disjoint contexts, ${\bf i} = (i_1,\dots, i_{\left\lvert{\bf x}\right\rvert}) \in \{0, \dots, \left\lvert w\right\rvert - 1\}^{\left\lvert{\bf x}\right\rvert}$ and ${\bf j} = (j_1, \dots, j_{\left\lvert{\bf y}\right\rvert}) \in \{0, \dots, \left\lvert w\right\rvert -1\}^{\left\lvert{\bf y}\right\rvert}$ , then $(w, {\bf i}, {\bf j})$ denotes the ${ {\bf z}}$ -marked word $(w, {\bf k})$ , where ${\bf z} = {\bf x}{\bf y}$ and ${\bf k} = (i_1, \dots, i_{\left\lvert{\bf x}\right\rvert}, j_1, \dots, j_{\left\lvert{\bf y}\right\rvert})$ .

The semantics of a formula in context ${\bf x} = \{x_1, \dots, x_k\}$ is defined inductively as follows. We let $w \in A^*$ be a word and ${\bf i} = (i_1, \dots, i_k) \in \{0, \dots, \left\lvert w\right\rvert - 1\}^{\left\lvert{\bf x}\right\rvert}$ . Then,

• ○ the marked word $(w, {\bf i})$ satisfies ${\sf P}_{a}(x_j)$ if and only if its $i_j$ -th letter is an a. As a consequence, for all $j \in \{1, \dots, k\}$ , there exists exactly one letter $a \in A$ such that $(w, {\bf i}) \models {\sf P}_a(x_j)$ ;

• ○ the marked word $(w, {\bf i})$ satisfies the formula $R(x_{j_1}, \dots, x_{j_\ell})$ given by a numerical predicate R if and only if $(i_{j_1}, \dots, i_{j_\ell}) \in R$ ;

• ○ the Boolean connectives and $\wedge$ , or $\vee$ , and not $\neg$ are interpreted classically;

• ○ the marked word $(w, {\bf i})$ satisfies the formula $Q x \ \phi$ , for a quantifier $Q: \{0,1\}^* \to \{0,1\}$ , if and only if $Q((w, {\bf i}, 0) \models \phi, \dots, (w, {\bf i}, \left\lvert w\right\rvert -1)\models \phi ) = 1$ , where “ $(w, {\bf i}, i)\models \phi$ ” denotes the truth value of “ $(w, {\bf i}, i)$ satisfies $\phi$ .”

Important examples of quantifiers are given by the: existential quantifier $\exists$ mentioned above and its variant $\exists !$ (there exists a unique); modular quantifiers $\exists_q^r$ , for each $q \in {\mathbb{N}}$ and $0\leq r<q$ , mapping a word of $\{0,1\}^*$ to 1 if and only if its number of 1’s is congruent to r modulo q; and the majority quantifiers ${\sf Maj}_k$ , for each $k \in {\mathbb{N}}$ , sending an element of $\{0,1\}^*$ to 1 if and only if it has strictly k more occurrences of 1 than of 0. Finally, given a formula $\phi$ in context x, we denote by $L_{\phi}$ the set of marked words that are models of $\phi$ .

Given a finite alphabet A, a context $\bf x$ , a set of numerical predicates $\mathcal{N}$ , and a set of quantifiers $\mathcal{Q}$ , we denote by ${\mathcal{Q}}_{A,{\bf x}}[\mathcal{N}]$ the corresponding set of first-order formulas in context $\bf x$ , up to semantic equivalence. The set of sentences ${\mathcal{Q}}_{A,\emptyset}[\mathcal{N}]$ in the empty context is simply denoted by $\mathcal{Q}_A[\mathcal{N}]$ . Notice that, as long as ${\mathcal{Q}}_{A,{\bf x}}[\mathcal{N}]$ is nonempty, say it contains a formula $\phi$ , it will also contain the always-true formula ${\bf 1}$ , which is semantically equivalent to $\phi \vee \neg\phi$ , and the always-false formula ${\bf 0}$ , which is semantically equivalent to $\phi \wedge \neg \phi$ . In particular, we have $L_{{\bf 1}} = A^* \otimes {\mathbb{N}}^{ {\bf x}}$ and $L_{{\bf 0}} = \emptyset$ , and taking the set of models of a given formula defines an embedding of Boolean algebras:

\[{\mathcal{Q}}_{A,{\bf x}}[\mathcal{N}]\rightarrowtail \mathcal{P}(A^* \otimes {\mathbb{N}}^{ {\bf x}}).\]

In formal language theory, one usually considers languages that are subsets of a free monoid, as presented in the previous paragraph. However, formulas in a nonempty context ${\bf x} = \{x_1,\dots, x_k\}$ define languages of marked words. Nevertheless, there is a natural injection $A^* \otimes {\mathbb{N}}^{ {\bf x}} \rightarrowtail (A\times2^{\bf y})^*$ whenever y is a context containing x. Here, we make a slight abuse of notation by writing $2^{{\bf y}}$ to actually mean the set $\mathcal{P}({\bf y})$ . Indeed, let $(w, {\bf i})$ be a marked word, where $w =a_0 \dots a_{n -1}$ and ${\bf i} = (i_1, \dots, i_k)$ . Then, $(w, {\bf i})$ is completely determined by the word $(a_0, S_0)\dots (a_{n-1},S_{n-1})$ over $(A \times 2^{\bf y})$ , where $S_i = \{x_{j} \mid i_j =i\}$ . Thus, we will often regard the language defined by a formula in a context x as a language over an extended alphabet $A \times 2^{\bf y}$ for some ${\bf y} \supseteq {\bf x}$ . Note that words of the form $(a_0,S_0)\dots (a_{n-1}, S_{n-1})$ as above are usually called x-structures (cf. Straubing Reference Straubing1994, Chapter II).

2.9 Marked words

We now consider the case where x consists of a single variable x, as this will play an important role in the remaining paper (cf. Sections 4.2 and 6). Note, however, that a similar treatment is possible in general.

When ${\bf x} = \{x\}$ , the set of x-marked words may be described as:

\begin{equation*} A^* \otimes {\mathbb{N}} = \{(w, i) \mid w \in A^*, \ i \in \{0, \dots, \left\lvert w\right\rvert - 1\}\},\end{equation*}

and we have an embedding $A^*\otimes {\mathbb{N}} \rightarrowtail (A \times2)^*$ defined by:

\[(w, i) \mapsto (a_0, 0) \dots (a_{i-1}, 0) (a_i, 1) (a_{i+1}, 0) \dots (a_{n-1}, 0),\]

for every word $w = a_0 \dots a_{n-1}$ and $i \in \{0, \dots, n-1\}$ .

Identifying the elements of $A^* \otimes{\mathbb{N}}$ with their images in $(A\times 2)^*$ , we may compute the Boolean algebra closed under quotients generated by this language. It is not difficult to see that $A^* \otimes{\mathbb{N}}$ is a regular language in $(A \times 2)^*$ , and that its syntactic monoid is the three-element commutative monoid $\{e,m,z\}$ satisfying $m^2 = z$ , with z acting as zero and e its identity element. The syntactic morphism of the language $A^* \otimes{\mathbb{N}}$ is $\mu: (A \times 2)^*\twoheadrightarrow \{e,m,z\}$ given by $\mu(a,0) =e$ and $\mu(a, 1) = m$ , and we have

\[A^* = \mu^{-1}(e), \quad A^*\otimes {\mathbb{N}} = \mu^{-1}(m), \quad \text{and} \quad A_z = \mu^{-1}(z),\]

where we identify $A^*$ with $(A\times\{0\})^*$ and $A_z= (A \times2)^* \setminus (A^* \cup A^* \otimes {\mathbb{N}})$ .

2.10 Classes of sentences

Given a function $\zeta: A \to B$ , we may define a map $\zeta^*_{\bf x}:A^* \otimes {\mathbb{N}}^{ {\bf x}} \to B^* \otimes{\mathbb{N}}^ {\bf x}$ by setting $\zeta^*_{\bf x}(w,{\bf i}) = (\zeta^*(w), {\bf i})$ , for every $w \in A^*$ and ${\bf i}\in \{0, \dots, \left\lvert w\right\rvert - 1\}^{\bf x}$ . By discrete duality, $\zeta_{\bf x}^*$ yields a homomorphism of Boolean algebras $(\zeta^*_{\bf x})^{-1}: \mathcal{P}(B^*\otimes {\mathbb{N}}^{ {\bf x}}) \to \mathcal{P}(A^* \otimes {\mathbb{N}}^{ {\bf x}})$ . By identifying fragments of logic with the set of languages they define, we may show that, for every set of quantifiers $\mathcal{Q}$ and every set of numerical predicates $\mathcal{N}$ , the homomorphism $(\zeta^*_{\bf x})^{-1}$ restricts and co-restricts to a homomorphism ${\mathcal{Q}}_{B,{\bf x}} [\mathcal{N}] \to {\mathcal{Q}}_{A,{\bf x}}[\mathcal{N}]$ . Indeed, for x consisting of a single variable x, we have

\[\zeta_x(w, i) \models {\sf P}_b(x) \iff (w, i) \models \bigvee_{\zeta(a) = b} {\sf P}_a(x),\]

for every $w \in A^*$ and $i \in \{0, \dots, \left\lvert w\right\rvert - 1\}$ . Note that, since A is finite, $\bigvee_{\zeta(a) = b} {\sf P}_a(x)$ is a well-defined formula of ${\mathcal{Q}}_{A,{\bf x}}[\mathcal{N}]$ . With a routine structural induction on the construction of formulas, we can then show that $(\zeta^*_{\bf x})^{-1}$ sends the language defined by a formula $\phi\in{\mathcal{Q}}_{B,{\bf x}}[\mathcal{N}]$ to the language defined by the formula obtained from $\phi$ by substituting, for every occurrence of a predicate ${\sf P}_b(x)$ with $b\in B$ , the formula $\bigvee_{\zeta(a)=b}{\sf P}_a(x)$ . Note that if b is not in the image of $\zeta$ , then ${\sf P}_b(x)$ is replaced by the empty join, which is logically equivalent to the always-false proposition. We denote by $\zeta_{\mathcal{Q}_{\bf x}[\mathcal{N}]}$ this restriction and co-restriction of $(\zeta_{\bf x}^*)^{-1}$ , so that the following diagram commutes

(3)

In particular, $\mathcal{Q}_{\_,{\bf x}}[\mathcal{N}]$ defines a presheaf $\mathcal{Q}_{\_,{\bf x}}[\mathcal{N}]: {\bf Set}_{fin}^{\rm op} \to {\sf BA}$ and, as so, it takes right (respectively, left) inverses to left (respectively, right) inverses and thus surjections (respectively, injections) on finite sets to embeddings (respectively, quotients) in Boolean algebras.

A class of sentences is, intuitively speaking, the notion corresponding to that of an lp-strain of languages in the setting of logic on words. This notion models what is usually referred to as a fragment of logic. Formally, a class of sentences $\Gamma$ is a map that associates with each finite alphabet A a set of sentences $\Gamma(A)\subseteq\mathcal{Q}_{A}[\mathcal{N}]$ which satisfies the following properties:

(LC.1) Each set $\Gamma(A)$ is closed under Boolean connectives $\wedge$ and $\neg$ (and thus, under $\vee$ );

(LC.2) For each map $\zeta\colon A\to B$ between finite alphabets, the homomorphism $\zeta_{\mathcal{Q}[\mathcal{N}]}: \mathcal{Q}_B[\mathcal{N}] \to \mathcal{Q}_A[\mathcal{N}]$ restricts and co-restricts to a homomorphism $\zeta_{\Gamma}: \Gamma(B)\to \Gamma(A)$ .

Since we consider sentences up to semantic equivalence, by (LC.1), each $\Gamma(A)$ is a Boolean algebra, and (LC.2) simply says that the assignment $A \mapsto\mathcal{V}_\Gamma(A) = \{L_\phi\mid\phi\in\Gamma(A)\}$ defines an lp-strain of languages.

4.1 Languages over profinite alphabets

Let Y be a profinite alphabet and $\mathcal{B} \subseteq {\sf Clopen}(Y^*)$ be a Boolean algebra of languages. If $\mathcal{B}$ is closed under quotients, then for every word w over Y, the homomorphisms

\[\ell_{w}:{\sf Clopen}(Y^*) \to {\sf Clopen}(Y^*), \qquad L \mapsto w^{-1}L\]

and

\[r_w:{\sf Clopen}(Y^*) \to {\sf Clopen}(Y^*), \qquad L \mapsto Lw^{-1}\]

restrict and co-restrict to endomorphisms of $\mathcal{B}$ . Thus, we have the two following commutative diagrams:

Dually, we have the following commutative diagrams of continuous functions:

(5)

We make a few remarks about these diagrams. First, notice that concatenation of words over Y turns $Y^*$ into a topological monoid. Indeed, the multiplication $m: Y^* \times Y^* \to Y^*$ is continuous because, if $C_1, \dots, C_n \subseteq Y$ are (cl)open subsets of Y, then

\[m^{-1}(C_1 \times \dots \times C_n) = \bigcup_{i = 0}^n (C_1 \times \dots C_i) \times (C_{i+1} \times \dots \times C_n) \]

is a (cl)open subset of $Y^* \times Y^*$ . Moreover, since for every $u, v \in Y^*$ we have $\ell_u \circ r_v = r_v \circ \ell_u$ , we also have $\widetilde\ell_u \circ \widetilde r_v = \widetilde r_v \circ\widetilde\ell_u$ . Therefore, the monoid structure on $Y^*$ induces a biaction with continuous components of $Y^*$ on $X_\mathcal{B}$ which is given by:

(6) \begin{equation} Y^* \times X_\mathcal{B} \to X_\mathcal{B}, \quad (u, x) \mapsto \widetilde\ell_u(x)\qquad\text{and}\qquad X_\mathcal{B} \times Y^* \to X_\mathcal{B}, \quad (x, v) \mapsto \widetilde r_v(x).\end{equation}

However, $X_\mathcal{B}$ itself does not necessarily inherit a monoid structure. Indeed, as it was shown in Gehrke et al. (Reference Gehrke, Grigorieff and Pin2010), Gehrke (Reference Gehrke2016), when A is a finite alphabet, this is case if and only if $\mathcal{B}$ consists of regular languages. Nevertheless, (6) induces a monoid structure on the dense subspace $M= \pi[Y^*]$ of $X_\mathcal{B}$ , which is given by:

(7) \begin{equation} \pi(u) \cdot \pi(v) = \pi(uv),\end{equation}

for every $u,v \in Y^*$ . Indeed, with a routine computation we may derive the following equalities:

(8) \begin{equation} \widetilde\ell_u(\pi(v)) = \pi(uv) = \widetilde r_v(\pi(u)).\end{equation}

These not only show that (7) is well defined in the sense that $\pi(uv) = \pi(u'v')$ whenever $\pi(u) = \pi(u')$ and $\pi(v) =\pi(v')$ , but also show that the monoid structure on M is indeed inherited from (6). In fact, it is not hard to see that $\pi: Y^* \twoheadrightarrow M$ is precisely the syntactic homomorphism of $\mathcal{B}$ as defined in Section 2.6. Moreover, since M is dense in $X_\mathcal{B}$ , (8) also shows that whenever $\pi(u) = \pi(u')$ (respectively, $\pi(v) = \pi(v')$ ), the continuous functions $\widetilde\ell_u$ and $\widetilde\ell_{u'}$ (respectively, $\widetilde r_v$ and $\widetilde r_{v'}$ ) coincide on all of $X_\mathcal{B}$ . Therefore, the natural biaction of M on itself extends to a biaction of M on $X_\mathcal{B}$ given by:

\[M \times X_\mathcal{B} \to X_\mathcal{B}, \quad (m, x) \mapsto \lambda_m(x)\qquad\text{and}\qquad X_\mathcal{B} \times M \to X_\mathcal{B}, \quad (x, m) \mapsto \rho_m(x),\]

with continuous components at each $m \in M$ . Here, for each $m \in M$ , $\lambda_m$ (respectively, $\rho_m$ ) denotes the continuous function $\widetilde \ell_u$ (respectively, $\widetilde r_u$ ) where $u\in Y^*$ is any word satisfying $\pi(u)= m$ .

The following definition, which captures duality for Boolean subalgebras of languages closed under the quotient operations, originates in Gehrke et al. (Reference Gehrke, Petrişan and Reggio2016), where it was used for recognition over finite alphabets. The above considerations verify that it remains the appropriate notion for recognition over profinite alphabets.

Definition 4.2. A Boolean space with an internal monoid (BiM) is a triple (M, p, X) where X is a Boolean space equipped with a biaction of a monoid M whose right and left components at each $m\in M$ are continuous and an injective function $p\colon M\rightarrowtail X$ which has dense image and is a morphism of sets with M-biactions. That is, for each $m\in M$ , there are continuous functions $\lambda_m, \rho_m: X \to X$ that make the following diagrams commute:

A morphism $(M, p, X) \to (N, q, W)$ of ${\sf{BiM}}$ s is a pair $(g, \varphi)$ , where $g: M \to N$ is a monoid homomorphism, $\varphi: X \to W$ is a continuous function, and the following diagram commutes

We say that $(g, \varphi)$ is a quotient provided g is surjective (and consequently, so is $\varphi$ ).

Given a profinite alphabet Y, we say that a language $L \subseteq{\sf Clopen}(Y^*)$ is recognized by the BiM (M, p, X) if there exists a homomorphism $\mu: Y^* \to M$ such that $p \circ \mu$ is continuous, and a clopen subset $C \subseteq X$ satisfying $L = (p\circ \mu)^{-1}(C)$ . Notice that, since X is a Boolean space, $p\circ \mu$ may be uniquely extended to a continuous function $\varphi:\beta(Y^*) \to X$ , and so, if $e: Y^* \rightarrowtail \beta(Y^*)$ denotes the Čech–Stone compactification of $Y^*$ , then the homomorphisms $\mu: Y^* \to M$ for which $p \circ \mu$ is continuous are in a bijective correspondence with the BiM morphisms $(Y^*,\,e,\, \beta(Y^*)) \to (M, p, X)$ . Moreover, the dual of the function $\varphi$ is the homomorphism of Boolean algebras $(p \circ\mu)^{-1}: {\sf Clopen}(X) \to {\sf Clopen}(\beta(Y^*)) = {\sf Clopen}(Y^*)$ whose image consists of the languages recognized by (M, p, X) via $\mu$ . Finally, since p is a morphism of sets with M-biactions and the biaction of M on X has continuous components, the Boolean algebra of languages recognized by (M, p, X) via $\mu$ is closed under quotients. Indeed, if $L = (p \circ \mu)^{-1}(C)$ for some clopen subset $C \subseteq X$ , and $u, v, w \in Y^*$ , then we have

\begin{align*} w \in u^{-1}Lv^{-1} & \iff p\circ \mu(uwv) \in C \iff p (\mu(u)\, \mu(w)\,\mu(v)) \in C \\ & \iff \lambda_{\mu(u)}\circ \rho_{\mu(v)} \circ p \circ \mu(w) \in C \\ & \iff w \in (p \circ \mu)^{-1}((\lambda_{\mu(u)}\circ \rho_{\mu(v)})^{-1}(C)).\end{align*}

Thus, $u^{-1}Lv^{-1} = (p \circ \mu)^{-1}((\lambda_{\mu(u)}\circ\rho_{\mu(v)})^{-1}(C))$ is recognized by the clopen $(\lambda_{\mu(u)}\circ \rho_{\mu(v)})^{-1}(C) \subseteq X$ .

In order to handle lp-varieties (i.e., lp-strains closed under quotients), it is useful to refine the notion of BiM. In the regular setting, this corresponds to the notion of stamp (Pin and Straubing Reference Pin and Straubing2005). The idea is to consider BiMs with a chosen profinite set of generators for the monoid component and constrain the set of languages we recognize accordingly. Formally, a BiM-stamp (called BiM presentation in Borlido et al. Reference Borlido, Czarnetzki, Gehrke and Krebs2017) is a tuple ${\sf R} = (Y,\mu,M,p, X)$ , where $\mu: Y^* \twoheadrightarrow M$ is a monoid quotient, (M, p, X) is a BiM, and $p \circ \mu$ is a continuous function. By the observations made in the preceding paragraph, BiM-stamps $(Y,\mu,M, p, X)$ may also be understood as BiM quotients $(Y^*, e, \beta (Y^*)) \twoheadrightarrow (M, p, X)$ . We remark that each Boolean algebra closed under quotients $\mathcal{B}\subseteq {\sf Clopen}(Y^*)$ naturally defines a BiM-stamp:

\[Y^* \twoheadrightarrow M = \pi[Y^*] \rightarrowtail X_\mathcal{B},\]

as described in the beginning of this section. This is called the syntactic BiM-stamp of $\mathcal{B}$ , and it is denoted by ${\sf Synt}(\mathcal{B}) =(Y, \mu_\mathcal{B}, M_\mathcal{B}, p_\mathcal{B}, X_\mathcal{B})$ .

BiM-stamps encode two types of behavior: algebraic behavior given by the triple $(Y, \mu, M)$ and topological behavior given by the continuous function $p \circ \mu: Y^* \to X$ . The interplay between these two plays a central role in this paper. We say that a language L is recognized by the BiM-stamp ${\sf R} = (Y, \mu, M, p, X)$ provided L is recognized by the BiM (M, p, X) via $\mu$ . As observed above, the set of all languages recognized by a BiM-stamp forms a Boolean algebra closed under quotients. Similarly to what happens in the regular setting, the syntactic BiM-stamp of a given Boolean algebra closed under quotients is the “optimal” BiM-stamp recognizing that Boolean algebra, in the following sense:

Proposition 4.4. A BiM-stamp ${\sf R} = (Y, \mu, M, p, X)$ recognizes a Boolean algebra closed under quotients $\mathcal{B}$ if and only if the syntactic BiM-stamp of $\mathcal{B}$ factors through ${\sf R}$ , that is, there is a commutative diagram:

where g is a homomorphism and $\varphi$ a continuous function.

A morphism between BiM-stamps ${\sf R} = (Y, \mu, M, p, X)$ and ${\sf S} =(Z, \nu, N, q, W)$ is a triple $\Phi = (h, g, \varphi)$ , where $h: Y^*\to Z^*$ is a continuous homomorphism and $(g, \varphi)$ is a morphism between the corresponding BiM components of ${\sf R}$ and ${\sf S}$ , so that the following diagram commutes:

When h is an lp-morphism, we say that $\Phi$ is an lp-morphism of BiM-stamps. Note that when h is onto, then so are g and $\varphi$ . If moreover h is length-preserving, then we will call $\Phi$ an lp-quotient. It is worth mentioning that every lp-quotient $\Phi = (h, g, \varphi):{\sf R} \twoheadrightarrow {\sf S}$ induces the following commutative diagram of continuous functions:

Thus, taking preimages yields the following commutative diagram of homomorphisms of Boolean algebras:

Therefore, ${\sf S}$ being an lp-quotient of ${\sf R}$ means that every language recognized by ${\sf S}$ is also recognized by ${\sf R}$ , under the identification ${\sf Clopen}(Z^*) \subseteq {\sf Clopen}(Y^*)$ .

Finally, we show that BiM-stamps over profinite alphabets can be described in terms of certain projective limits of BiM-stamps over finite alphabets. Although a bit technical, the proof mostly uses standard arguments used in the computation of projective limits in set-based categories.

Proof. We give the general idea of the proof. All the missing details are routine computations. Let $\mathcal{F} = \{{\sf R}_i = (Y_i, \mu_i, M_i, p_i, X_i)\}_{i \in I}$ be a projective system in the category of BiM-stamps with lp-morphisms. For $i \ge j$ , we denote by $\Phi_{i,j} = (h_{i,j}^*, g_{i,j}, \varphi_{i,j}): {\sf R}_i \to {\sf R}_j$ the corresponding connecting morphism, with $h_{i,j}: Y_i \to Y_j$ a continuous function. Then, each of the families $\{Y_i\}_{i \in I}$ , $\{M_i\}_{i \in I}$ , and $\{X_i\}_{i \in I}$ forms itself a projective system, with the maps $h_{i,j}$ , $g_{i,j}$ and $\varphi_{i,j}$ as connecting morphisms, respectively. We set

(9) \begin{equation} Y = \lim\limits_{\longleftarrow}\ \{Y_i \mid i \in I\}, \qquad M_0 = \lim\limits_{\longleftarrow}\ \{M_i \mid i \in I\}, \qquad \text{and}\qquad X_0 = \lim\limits_{\longleftarrow}\ \{X_i \mid i \in I\}, \end{equation}

and for each $i \in I$ , we denote by $h_i: Y \twoheadrightarrow Y_i$ , $\zeta_i: M_0 \twoheadrightarrow M_i$ , and $\pi_i: X_0 \twoheadrightarrow X_i$ the corresponding projections.

Using the explicit description of projective limits displayed in (2), we may check that there are well-defined maps:

(10) \begin{equation} \mu_0: Y^* \to M_0, \ z \mapsto (\mu_i \circ h_i^*(z))_{i \in I}\qquad\text{and} \qquad p_0: M_0 \rightarrowtail X_0, \ m \mapsto (p_i\circ \zeta_i(m))_{i \in I}. \end{equation}

Graphically, we have the following commutative diagram:

Moreover, by continuity of $p_i\circ \mu_i \circ h_i^*$ , for every $i \in I$ , the map $p_0 \circ \mu_0$ is also continuous. We set

\[M = \mu_0 [Y^*] \qquad \text{and} \qquad X = \overline{p_0[M]}.\]

Co-restricting $\mu_0$ to M, we have an onto homomorphism $\mu: Y^* \twoheadrightarrow M$ , and the restriction and co-restriction of $p_0$ to M and to X, respectively, yields a map $p:M \rightarrowtail X$ with dense image. We claim that ${\sf R} = (Y, \mu, M, p, X)$ is the projective limit of $\mathcal{F}$ . The fact that ${\sf R}$ satisfies the universal property of projective limits is inherited from the universal properties satisfied by Y, $M_0$ , and $X_0$ .

Thus, it remains to check that M continuously bi-acts on X.

We denote by $\lambda_{i,m_i}: X_i \to X_i$ the (continuous) component at $m_i \in M_i$ of the left action of $M_i$ on $X_i$ . Then, for $m = (m_i)_{i \in I} \in M$ , setting

\[\lambda_m: X \to X, \qquad x = (x_i)_{i \in I} \mapsto (\lambda_{i,m_i}(x_i))_{i \in I}\]

defines a continuous map which induces a left action of M on X. Indeed, for every $m, m' \in M$ , we may compute $\lambda_m \circ p(m') = p (mm')$ , using the analogous property for each $\lambda_{i,m_i}$ . This proves not only that $\lambda_m$ is well defined (because $\lambda_m[X] = \lambda_m\left[\overline{p[M]}\right] \subseteq \overline{p[M]} = X$ ) but also that p is a morphism of sets with a left M-action. Similarly, we can define the right action of M on X. The compatibility between the left and right actions is inherited from the compatibility between the left and right actions for each ${\sf R}_i$ . Thus, ${\sf R}$ is a BiM-stamp.

Finally, that each BiM-stamp is the projective limit of all its lp-quotients over finite alphabets is an easy consequence of the explicit computation of projective limits just made.

We remark that, even though each of the maps $\mu_i \circ h_i^*$ is onto, since $Y^*$ is not compact, the map $\mu_0$ defined in (10) is not onto in general (cf. Almeida and Weil Reference Almeida and Weil1995, Lemma 1.2). To see this, consider for instance, for each integer n, the BiM-stamp $(\{0\}^* \twoheadrightarrow {\mathbb{Z}}_n\xrightarrow {id} {\mathbb{Z}}_n)$ . Then, we have a projective limit system $\mathcal{F} = \{(\{0\}^* \twoheadrightarrow {\mathbb{Z}}_n \xrightarrow{id} {\mathbb{Z}}_n)\}_{n \in {\mathbb{N}}}$ and $M_0$ (which equals $X_0$ ) defined in (9) is the additive profinite group $\widehat {\mathbb{Z}}$ (seen as a monoid). The map $\mu_0$ is then the inclusion $\{0\}^*\rightarrowtail \widehat {\mathbb{Z}}$ , which is not surjective. Finally, the projective limit of $\mathcal{F}$ is the BiM-stamp $(\{0\}^*\twoheadrightarrow {\mathbb{N}} \rightarrowtail \widehat {\mathbb{N}})$ , where $\widehat{\mathbb{N}}$ denotes the closure of ${\mathbb{N}}$ in $\widehat {\mathbb{Z}}$ .

4.2 Languages of marked words and quotienting operations

Recall that the set $A^* \otimes{\mathbb{N}}$ of marked words may be seen as a regular language in $(A \times 2)^*$ . The fact that the syntactic morphism of this language is $\mu: (A\times 2)^*\to\{e,m,z\}$ given by $(a,0)\mapsto e$ and $(a,1)\mapsto m$ corresponds to saying that

\[ (A\times 2)^*\cong A^* \,\uplus\, (A^* \otimes{\mathbb{N}})\,\uplus\, A_z,\]

as defined in Section 2.9, and that concatenation on $(A \times 2)^*$ decomposes as follows: it yields biactions of $A^*$ on each of these components, thus accounting for all pairs involving an element of $A^*$ , and any other pair is sent to $A_z$ .

Dually, the above disjoint union decomposition of $(A\times 2)^*$ yields the following Cartesian product decomposition:

\[\mathcal{P}((A\times 2)^*)\cong \mathcal{P}(A^*) \,\times\, \mathcal{P}(A^* \otimes{\mathbb{N}})\,\times\, \mathcal{P}(A_z),\]

We are interested in Boolean subalgebras $\mathcal{D}$ of $\mathcal{P}((A \times2)^*)$ . Dual to the inclusions of the disjoint components, we get projections of $\mathcal{D}$ onto

\[ \mathcal{D}_0=\{L\cap A^*\mid L\in \mathcal{D}\}, \quad \mathcal{D}_1=\{L\cap (A^* \otimes{\mathbb{N}})\mid L\in \mathcal{D}\},\quad \text{and}\quad\mathcal{D}_z=\{L\cap A_z\mid L\in \mathcal{D}\},\]

respectively. While $\mathcal{D}$ is always contained in $\mathcal{D}_0\times\mathcal{D}_1\times\mathcal{D}_z$ it is not difficult to see that we have equality if and only if $\mathcal{D}$ contains the language $A^*\otimes {\mathbb{N}}$ and its orbit under the biaction of $(A\times 2)^*$ .

We will be particularly interested in such algebras for which $\mathcal{D}_z=2$ . In this case, any component of the dual biaction by quotients on $\mathcal{P}((A\times 2)^*)$ with domain $\mathcal{P}(A_z)$ just sends the bounds to bounds of the appropriate component. The remaining components are as follows. First, we have the biactions of $A^*$ on $\mathcal{P}(A^*)$ and on $\mathcal{P}(A^* \otimes {\mathbb{N}})$ given, for $u\in A^*$ , respectively, by:

(11) \begin{gather} \begin{aligned} \ell^0_u: \mathcal{P}(A^*) &\to \mathcal{P}(A^*) \qquad\qquad & r^0_u: \mathcal{P}(A^*) &\to \mathcal{P}(A^*), \\ L \ \ &\mapsto u^{-1}L & L\ \ &\mapsto Lu^{-1} \end{aligned}\end{gather}

and by

(12) \begin{gather} \begin{aligned} \ell^1_u: \mathcal{P}(A^* \otimes {\mathbb{N}}) &\to \mathcal{P}(A^* \otimes {\mathbb{N}}) \qquad\qquad & r^1_u: \mathcal{P}(A^* \otimes {\mathbb{N}}) &\to \mathcal{P}(A^* \otimes {\mathbb{N}}). \\ L\ \ &\mapsto u^{-1}L & L\ \ &\mapsto Lu^{-1} \end{aligned}\end{gather}

For every marked word $(w,i)$ , the biaction of $A^*$ on $A^* \otimes {\mathbb{N}}$ also induces two functions $A^* \to A^* \otimes {\mathbb{N}}$ , which are given by left and by right multiplication by (w,i). Dually, these define

(13) \begin{gather} \begin{aligned} \ell^1_{(w,i)}:\mathcal{P}(A^* \otimes {\mathbb{N}}) & \to \mathcal{P}(A^*)\qquad\qquad& r^1_{(w,i)}: \mathcal{P}(A^* \otimes {\mathbb{N}}) & \to \mathcal{P}(A^*).\\ L\ \ &\mapsto (w,i)^{-1}L & L\ \ &\mapsto L(w,i)^{-1} \end{aligned}\end{gather}

Proof. Suppose we have (a). If $A_z \in \mathcal{D}$ then, as $\mathcal{D}$ is closed under quotients,

\[ (a,1)^{-1}A_z=(A^* \otimes {\mathbb{N}})\cup A_z\in\mathcal{D}, \]

and thus $A^*\otimes {\mathbb{N}}\in\mathcal{D}$ . Since $\mathcal{D}$ contains the language $A^*\otimes {\mathbb{N}}$ and is closed under quotients, it also contains its orbit under the biaction of $(A\times 2)^*$ . Thus, we have that $\mathcal{D}$ is isomorphic to $\mathcal{D}_0\times\mathcal{D}_1\times \mathcal{D}_z$ which, by hypothesis, is $\mathcal{D}_0\times\mathcal{D}_1\times 2$ . The rest of the assertion in (b) follows from $\mathcal{D}$ being closed under quotients and the splitting of the biaction of $(A\times 2)^*$ on $\mathcal{P}((A\times 2)^*)$ as given by (11), (12), and (13).

Conversely, let us assume that (b) holds. Notice that having $\mathcal{D}\cong\mathcal{D}_0\times\mathcal{D}_1\times \mathcal{D}_z$ amounts to having that, for every $L_1, L_2, L_3 \in \mathcal{D}$ , there exists some $L \in \mathcal{D}$ such that

\[L_1 \cap A^* = L \cap A^*, \qquad L_2 \cap (A^* \otimes {\mathbb{N}}) = L \cap (A^*\otimes {\mathbb{N}}), \qquad \text{and} \qquad L_3 \cap A_z = L \cap A_z.\]

So, in particular, by taking $L_1 = L_3 = \emptyset$ and $L_2 = (A \times 2)^*$ , we may conclude that $A^* \otimes {\mathbb{N}} \in \mathcal{D}$ . To show that $\mathcal{D}$ is closed under quotients, it suffices to consider quotients by letters. Also, since quotient operations are homomorphisms, it suffices to consider languages belonging to each component. By hypothesis, $\mathcal{D}_0$ and $\mathcal{D}_1$ are closed under quotients by letters $a\in A$ and clearly so is 2 within $\mathcal{P}(A_z)$ . Also by hypothesis, $(a,1)^{-1}L,\ L(a,1)^{-1}\in \mathcal{D}_0$ for $L\in\mathcal{D}_1$ . Finally, for $L\in\mathcal{D}_0$ , we have

\[ (a,1)^{-1} L=L(a,1)^{-1}=\emptyset\in\mathcal{D} \qquad \text{and} \qquad (a,1)^{-1} A_z=A_z(a,1)^{-1}=(A^*\otimes{\mathbb{N}})\cup A_z\in\mathcal{D}. \]

Notice that in the case where $\mathcal{D}$ satisfies the equivalent conditions of Lemma 4.6, the Boolean subalgebra with atoms $A^*$ , $A^*\otimes{\mathbb{N}}$ , and $A_z$ is a subalgebra of $\mathcal{D}$ . Also note that the Boolean subalgebra of $\mathcal{P}((A \times 2)^*)$ generated by $A^*$ is closed under quotients, and it is such that $\mathcal{D}_z = 2$ , but it does not satisfy the equivalent conditions of the the lemma.

Corollary 4.7. Let $\mathcal{C}\subseteq \mathcal{P}(A^* \cup (A^* \otimes {\mathbb{N}}))$ be a Boolean subalgebra. Then, the Boolean subalgebra $\mathcal{D}$ of $\mathcal{P}((A \times 2)^*)$ closed under quotients generated by $\mathcal{C}$ is generated, as a lattice, by $\mathcal{S}_0 \cup \mathcal{S}_1 \cup \{A_z\}$ , where

\begin{multline*} \mathcal{S}_0 = \{u^{-1}Lv^{-1} \mid u, v \in A^*, \ L \in \mathcal{C}_0\} \\ \cup\ \{(w,i)^{-1} L u^{-1},\ u^{-1}L(w,i)^{-1} \mid u \in A^*, (w,i)\in A^* \otimes {\mathbb{N}}, \ L \in\mathcal{C}_1\} \subseteq \mathcal{P}(A^*) \end{multline*}

and

\[\mathcal{S}_1 = \{u^{-1}L v^{-1}\mid u, v \in A^*, \ L \in \mathcal{C}_1\} \subseteq \mathcal{P}(A^* \otimes {\mathbb{N}}).\]

Proof. Since the quotient operations are Boolean homomorphisms, ${\mathcal{D}}$ is generated as a Boolean algebra by the quotients of the languages in $\mathcal{C}$ . Also, since, for $a\in A$ and $L\subseteq A^* \cup (A^* \otimes {\mathbb{N}})$ , we have

\[ a^{-1}L\subseteq A^* \cup (A^* \otimes {\mathbb{N}})\ \text{ and }\ (a,1)^{-1}L\subseteq A^*, \]

it follows that ${\mathcal{D}}_z=2$ . Also, since $\mathcal{C}$ is a Boolean subalgebra of $\mathcal{P}(A^* \cup (A^*\otimes {\mathbb{N}}))$ , it contains $A^* \cup (A^*\otimes {\mathbb{N}})$ and thus ${\mathcal{D}}$ contains $A_z$ . It follows that Lemma 4.6 applies to ${\mathcal{D}}$ and the conclusion of the corollary easily follows.

Another immediate consequence of the equivalence between 4.6 and 4.6 in Lemma 4.6 is the following:

Corollary 4.8. Let $\mathcal{D} \subseteq \mathcal{P}((A \times 2)^*)$ be a Boolean subalgebra closed under quotients that contains $A^* \otimes {\mathbb{N}}$ and such that $\mathcal{D}_z = 2$ . We let $\pi: (A \times 2)^* \to M_\mathcal{D}$ denote the syntactic morphism of $\mathcal{D}$ and we set

\[M = \pi[A^*] \qquad\text{and}\qquad T= \pi[A^* \otimes {\mathbb{N}}].\]

Then,

1. (a) the biaction of $M_{\mathcal{D}}$ on $X_{\mathcal{D}}$ restricts and co-restricts to a biaction of M on $X_{\mathcal{D}_0}$ and to a biaction of M on $X_{\mathcal{D}_1}$ ;

2. (b) for every $t \in T$ , the components of the biaction of $M_\mathcal{D}$ on itself at t restrict and co-restrict as follows:

   \[\lambda_{t}: X_{\mathcal{D}_0} \to X_{\mathcal{D}_1} \qquad \text{and}\qquad\rho_{t}: X_{\mathcal{D}_0} \to X_{\mathcal{D}_1}.\]

We remark that, if $\mathcal{D} \subseteq \mathcal{P}((A \times 2)^*)$ is a Boolean subalgebra closed under quotients then $\mathcal{D}_0$ , seen as a Boolean subalgebra of $\mathcal{P}(A^*)$ , is also closed under quotients: it is so because, for every $u, v \in A^*$ and $L \in \mathcal{D}$ , the following equality holds

\[u^{-1}(L \cap A^*) v^{-1} = (u^{-1}Lv^{-1}) \cap A^*.\]

Moreover, since the quotient $\mathcal{P}((A \times 2)^*) \twoheadrightarrow\mathcal{P}(A^*)$ restricts and co-restricts to a quotient $\mathcal{D}\twoheadrightarrow \mathcal{D}_0$ , the syntactic morphism of $\mathcal{D}_0 \subseteq\mathcal{P}(A^*)$ is a restriction and co-restriction of the syntactic morphism of $\mathcal{D} \subseteq \mathcal{P}((A \times 2)^*)$ . In particular, the monoid M defined in Corollary 4.8 is the syntactic monoid $M_{\mathcal{D}_0}$ of $\mathcal{D}_0$ and the biaction of M on $X_{\mathcal{D}_0}$ is simply the natural biaction of $M_{\mathcal{D}_0}$ on $X_{\mathcal{D}_0}$ .

5.1 Substitution with respect to finite Boolean algebras

As an example, consider the sentence $\psi = \exists x \phi(x)$ . Then, $\psi$ may be obtained from the sentence $\exists x {\sf P}_b(x)$ by replacing ${\sf P}_b(x)$ by $\phi(x)$ , and, thus, understanding $\psi$ amounts to understanding both the sentence $\exists x \ {\sf P}_b(x)$ and the formula $\phi(x)$ . If we want to substitute away several subformulas in this way, we must account for their logical relations. For instance, suppose that $\phi(x)$ is the conjunction $\phi_1(x)\wedge\phi_2(x)$ , and that $\phi_1(x)$ and $\phi_2(x)$ are the simpler subformulas we wish to consider. Should $\psi$ be obtained from a simpler sentence as above, such a sentence would be $\exists x \ ({\sf P}_{b_1}(x) \wedge{\sf P}_{b_2}(x))$ for two letters $b_1, b_2$ . But, since $\phi_1$ and $\phi_2$ may be related we would then need to impose relations on letters. Then, no complexity is removed. Thus instead, we will consider a finite Boolean algebra of formulas to be substituted away. These can all be accounted for by having a letter predicate for each atom of this finite Boolean algebra. The fact that letter predicates model the atoms of a finite Boolean algebra of formulas in a free variable is built into their interpretation. This explains why, when substituting a formula of a given finite set $\mathcal{F}$ for each occurrence of a letter predicate from a corresponding alphabet in a sentence, we should only consider sets $\mathcal{F}$ of formulas that have the same logical behavior as letter predicates, meaning that $\mathcal{F}$ satisfies

1. (A.1) $\bigvee_{\phi \in \mathcal{F}}\ \phi$ is the always-true proposition;

2. (A.2) for every $\phi_1, \phi_2 \in \mathcal{F}$ distinct, $\phi_1 \wedge \phi_2 $ is the always-false proposition.

In other words, we require that $\mathcal{F}$ is the set of atoms of the finite Boolean algebra it generates.

We now formalize this concept of substitution. Throughout this section, we fix a context x and a variable x which does not belong to x. Moreover, $\Gamma$ will be a fixed class of sentences and $\Delta \subseteq {\mathcal{Q}}_{A,{\bf x} x}[\mathcal{N}]$ a finite Boolean subalgebra. We regard the set of atoms of $\Delta$ as a finite alphabet, and in order to emphasize both the fact that it is an alphabet and the fact that it is determined by $\Delta$ , we will denote it by $C_{\Delta}$ . On the other hand, when we wish to view an element c of $C_{\Delta}$ as a formula of $\Delta$ , we will write $\phi_c$ instead of c.

Definition 5.1. The $\Gamma$ -substitution given by $\Delta$ (with respect to the variable x) is the map:

\[\sigma_{\Gamma, \Delta}: \Gamma(C_{\Delta}) \to{\mathcal{Q}}_{A,{\bf x}}[\mathcal{N}]\]

sending a sentence to the formula in context x obtained by substituting for each occurrence of a letter predicate ${\sf P}_c(z)$ , the formula $\phi_c[x/z]$ (i.e., the formula obtained by substituting z for x in the formula $\phi_c\in {\rm At}(\Delta)$ ). Note that here we assume (without loss of generality) that the variables occurring in $\psi \in \Gamma(C_\Delta)$ , such as z, do not occur in the formulas of $\Delta$ . When $\Gamma$ is clear from the context, as will very often be the case, we will simply write $\sigma_\Delta$ instead of $\sigma_{\Gamma, \Delta}$ .

Since the only constraints on the interpretation of letters in a word are given by the properties (A.1) and (A.2), it follows by a simple structural induction that $\sigma_{\Delta}$ is a homomorphism of Boolean algebras. We denote the image of this homomorphism by $\Gamma \odot \Delta$ . In the sequel, we will consider $\sigma_\Delta$ as denoting the co-restriction of the substitution to its image, that is,

\[\sigma_\Delta: \Gamma(C_\Delta) \twoheadrightarrow \Gamma \odot \Delta.\]

Next we describe the languages of $\Gamma \odot \Delta$ via those of $\Gamma$ and those of $\Delta$ . Since $\Gamma(C_\Delta)$ and $\Gamma\odot \Delta$ define, respectively, a Boolean algebra of languages over $C_\Delta$ and a Boolean algebra of marked words over A, we have embeddings:

Our first goal is to prove that the substitution map $\sigma_\Delta$ extends to a complete homomorphism of Boolean algebras $\mathcal{P}(C^*_\Delta)\to \mathcal{P}(A^* \otimes {\mathbb{N}}^{ {\bf x}})$ . Formulated dually, this means we are looking for a map on the level of (marked) words $\tau_\Delta: A^* \otimes {\mathbb{N}}^{ {\bf x}} \to C^*_\Delta$ making the following diagram commute:

Here, the maps $p_\Delta\colon C_{\Delta}^*\to X_{\Gamma{(C_{\Delta})}}$ and $q_\Delta\colon A^* \otimes {\mathbb{N}}^{ {\bf x}} \to X_{\Gamma \odot \Delta}$ are, respectively, the restrictions of the dual maps of the embeddings $\Gamma{(C_{\Delta})}\rightarrowtail \mathcal{P}(C_{\Delta}^*)$ and $\Gamma\odot \Delta \rightarrowtail\mathcal{P}(A^* \otimes {\mathbb{N}}^{ {\bf x}})$ .

In order to be able to define the map $\tau_\Delta$ , we need to understand the Boolean algebra $\Delta$ via duality. Recall that ${\mathcal{Q}}_{A,{\bf x} x}[\mathcal{N}]$ embeds in $\mathcal{P}(A^* \otimes {\mathbb{N}}^{ {{\bf x} x}})$ as a Boolean subalgebra, and therefore, so does $\Delta$ :

\[\Delta \rightarrowtail {\mathcal{Q}}_{A,{\bf x} x}[\mathcal{N}] \rightarrowtail \mathcal{P}(A^* \otimes {\mathbb{N}}^{ {{\bf x} x}}).\]

Applying discrete duality to this composition, we obtain a map:

\[\xi_\Delta: A^* \otimes {\mathbb{N}}^{ {{\bf x} x}} \twoheadrightarrow C_\Delta = {\rm At}(\Delta) \]

defined, for $w\in A^* \otimes {\mathbb{N}}^{ {\bf x}}$ , $i<|w|$ , $c\in C_\Delta$ , and $\phi_c$ the atom of $\Delta$ corresponding to c, by:

(14) \begin{equation} \xi_\Delta(w, i) = c \ \iff \ (w, i)\in L_{\phi_c} \ \iff \ (w, i)\vDash \phi_c .\end{equation}

Proposition 5.3. Let $\Gamma$ be a class of sentences, $\Delta$ a finite Boolean subalgebra of ${\mathcal{Q}}_{A,{\bf x}x}[\mathcal{N}]$ , and $\sigma_\Delta:\Gamma(C_\Delta)\to\Gamma\odot\Delta$ the associated substitution as defined above. Then, the function ${\tau_\Delta: A^* \otimes {\mathbb{N}}^{ {\bf x}} \to C_{\Delta}^*}$ defined by $\tau_\Delta(w) = \xi_\Delta(w, 0) \cdots \xi_\Delta(w, \left\lvert w\right\rvert - 1)$ makes the following diagram commute:

Proof. We show that the dual diagram:

commutes. To this end, let $w \in A^* \otimes {\mathbb{N}}^{ {\bf x}}$ , $i<|w|$ , and $c\in C_\Delta$ with $\phi_c$ the corresponding atom of $\Delta$ . First, we argue that

\[(\tau_\Delta(w), i) \models {\sf P}_c(x) \ \iff \ (w, i) \models \phi_c.\]

This is so because, by the definition of letter predicates, the marked word over $C_\Delta^*$ , $(\tau_\Delta(w), i)$ , is a model of ${\sf P}_c(x)$ if and only if its i-th letter is a c. By definition of $\tau_\Delta$ , this is equivalent to having $\xi_\Delta(w, i) = c$ , which, by (14), means that $(w, i) \models \phi_c$ , as required.

Now, since the validity in a marked word of a quantified formula $Qx\ \psi$ is fully determined once we know the truth value of the given formula $\psi$ at each point of the marked word, and since $\psi\in\Gamma(C_\Delta)$ and $\sigma_\Delta(\psi)$ are built up identically once the substitutions of ${\sf P}_c(x)$ by $\phi_c$ have been made, it follows that, for all $\psi\in\Gamma(C_\Delta)$ , we have

(15) \begin{equation} \tau_\Delta(w) \in L_\psi \ \iff \ w \in L_{\sigma_\Delta(\psi)}.\end{equation}

However,

\[ w \in L_{\sigma_\Delta(\psi)}\quad\iff\quad L_{\sigma_\Delta(\psi)}\in p_\Delta(w)\quad\iff\quad L_\psi\in \Sigma_\Delta( p_\Delta(w))\]

so that

\[ \tau_\Delta(w) \in L_\psi \ \iff \ L_\psi\in \Sigma_\Delta( p_\Delta(w))\]

and thus $\Sigma_\Delta( p_\Delta(w))=q_\Delta(\tau_\Delta(w))$ as required.

The existence of the map $\tau_\Delta$ defined in Proposition 5.3 yields the next result.

Remark 5.5. We warn the reader that the operator $(\_\odot\_)$ just defined does not coincide with the operator $(\_\circ\_)$ considered both in Borlido et al. (2017) and in the regular version of Tesson and Thérien (2007). The relationship between these operators is expressed by the following equality:

\[\Gamma \circ \Delta = \langle (\Gamma \odot \Delta) \cup \Delta_{\bf x}\rangle_{\sf BA},\]

where $\Delta_{\bf x}$ denotes the set of formulas of $\Delta$ in context x (i.e., those whose free variables belong to x). We choose to first study the operator $(\_\odot\_)$ in order to emphasize the role of Stone duality in the Substitution Principle. It should be clear for the reader how to state the corresponding results for $(\_\circ\_)$ .

5.2 The extension to arbitrary Boolean algebras using profinite alphabets

As the reader may have noticed, the context x fixed along the previous section is not playing an active role. For that reason, and in order to simplify the notation, we now assume that x is the empty context. Later, in Section 5.3, we will see that this assumption may be done without the loss of generality.

Here, we show that substitution as defined in Section 5.1 extends to arbitrary Boolean algebras in a meaningful way. Fix a class of sentences $\Gamma$ . We start by comparing the substitution maps obtained for two finite Boolean algebras, one contained in the other. To this end, suppose $\Delta_1\rightarrowtail \Delta_2$ is such an inclusion of finite Boolean subalgebras of ${\mathcal{Q}}_{A,x}[\mathcal{N}]$ and let $\zeta: C_2\twoheadrightarrow C_1$ be the dual of the inclusion. Recall that the semantics of logic on words provides embeddings of $\Gamma(C_i)$ in $\mathcal{P}(C_i^*)$ and that, since $\Gamma$ is a class of sentences, the surjection $\zeta$ yields an embedding $\zeta_\Gamma\colon\Gamma(C_1)\rightarrowtail\Gamma(C_2)$ making the following diagram commute (cf. diagram (3) and LC.2):

(16)

We also have

Lemma 5.6. The following diagram is commutative:

Proof. We first recall from Proposition 5.3 that, for $i = 1, 2$ , and $w \in A^*$ , we have

\[\tau_{\Delta_i}(w) = \xi_i(w, 0) \dots \xi_i(w, \left\lvert w\right\rvert -1),\]

where $\xi_i: A^* \otimes {\mathbb{N}} \twoheadrightarrow C_i$ is the quotient dual to the embedding $\Delta_i \rightarrowtail \mathcal{P}(A^* \otimes {\mathbb{N}})$ . On the other hand, by hypothesis, we have a commutative diagram:

which dually gives

It then follows that

\begin{align*} \tau_{\Delta_1}(w) & = \xi_1(w, 0) \dots \xi_1(w, \left\lvert w\right\rvert - 1) \\ & = \zeta^*(\xi_2(w, 0) \dots \xi_2(w, \left\lvert w\right\rvert - 1)) = \zeta^* (\tau_{\Delta_2}(w)), \end{align*}

that is, the statement of the lemma is true.

As a straightforward consequence of diagram (16), Lemma 5.6, and Proposition 5.3, we have the following:

Theorem 5.7. Let $\Delta_1 \rightarrowtail \Delta_2$ be an embedding of finite Boolean subalgebras of ${\mathcal{Q}}_{A,x}[\mathcal{N}]$ , and let $\zeta: C_2 \twoheadrightarrow C_1$ be its dual map. Then, the following diagram commutes:

Thus, we have a direct system of Boolean subalgebras of $\mathcal{Q}_A[\mathcal{N}]$ and $\Gamma\odot \Delta_1\subseteq\Gamma\odot \Delta_2$ .

This leads to the following definition.

Definition 5.9. For an arbitrary Boolean subalgebra $\Delta \subseteq {\mathcal{Q}}_{A,{x}}[\mathcal{N}]$ , we set

(17) \begin{equation} \Gamma \odot \Delta = \lim\limits_{\longrightarrow} \ \{\Gamma\odot \Delta'\mid \Delta' \subseteq \Delta \text{ is a finite Boolean subalgebra}\}. \end{equation}

Note that $\Gamma \odot \Delta$ is simply given by the union of all Boolean subalgebras $\Gamma\odot \Delta' \subseteq \mathcal{Q}_A[\mathcal{N}]$ . In particular, it is also a Boolean subalgebra of $\mathcal{Q}_A[\mathcal{N}]$ .

In turn, on the side of Boolean spaces, we have a projective limit system formed by the maps $\tau_{\Delta'}$ .

Corollary 5.10. For every Boolean subalgebra $\Delta \subseteq {\mathcal{Q}}_{A,x}[\mathcal{N}]$ , the set of maps

(18) \begin{equation} \{\tau_{\Delta'}: A^* \to C_{\Delta'}^* \mid \Delta' \subseteq \Delta\text{ is a finite Boolean subalgebra}\} \end{equation}

forms a projective limit system, where the connecting morphisms are the homomorphisms of monoids $C_{\Delta_{2}}^* \twoheadrightarrow C_{\Delta_1}^*$ induced by the dual maps of inclusions $\Delta_1 \rightarrowtail \Delta_2$ of finite Boolean subalgebras of $\Delta$ . Moreover, the limit of this system is the map $\tau_\Delta: A^* \to X_{\Delta}^*$ sending a word $w \in A^*$ to the word $\gamma_0 \cdots \gamma_{\left\lvert w\right\rvert - 1}$ with $\gamma_i = \{\phi \in \Delta \mid (w, i) \text{ satisfies } \phi\}$ . In other words, $\gamma_i$ is the projection to $X_{\Delta}$ of the principal (ultra)filter of $\mathcal{P}(A^*\otimes {\mathbb{N}})$ generated by (w, i).

The reader should now recall the extension of an lp-strain of languages $\mathcal{V}$ to profinite alphabets presented in Section 3, and in particular that such extension yields an embedding $\mathcal{V}(Y) \rightarrowtail {\sf Clopen}(Y^*)$ for every profinite alphabet Y.

Corollary 5.11. Let $\Gamma$ be a class of sentences and $\Delta \subseteq {\mathcal{Q}}_{A,{x}}[\mathcal{N}]$ be a Boolean subalgebra. Then, the Boolean algebra $\Gamma \odot \Delta$ is a quotient of $\mathcal{V}_\Gamma(X_{\Delta})$ , or equivalently, $X_{\Gamma \odot \Delta}$ is isomorphic to a closed subspace of $X_{\mathcal{V}_\Gamma(X_\Delta)}$ . More precisely, there exist commutative diagrams:

which are dual to each other.

Proof. We prove that the left-hand diagram commutes. Let L be a language of $\Gamma\odot \Delta$ . By Definition 5.9 of $\Gamma \odot \Delta$ , this means that there exists a finite Boolean subalgebra $\Delta' \subseteq \Delta$ such that L belongs to $\Gamma \odot \Delta'$ . Denote by $C_{\Delta'}$ the alphabet consisting of the atoms of $\Delta'$ . Using the local version of the Substitution Principle (cf. Corollary 5.4), this is equivalent to the existence of some language $K \in \mathcal{V}_\Gamma(C_{\Delta'})$ such that $L = \tau_{\Delta'}^{-1}(K)$ . But by Lemma 3.1 and Corollary 5.10, this amounts to having that L belongs to $\tau_\Delta^{-1}(\mathcal{V}_\Gamma(X_\Delta))$ . So, we just proved that the image of the following composition:

is precisely $\Gamma \odot \Delta$ . That is, we have a commutative diagram as in the left-hand side of the statement.

We can now state the already announced global version of the Substitution Principle, which is simply a rephrasing of the commutativity of the left-hand diagram of Corollary 5.11.

5.3 Using an alphabet to encode free variables

We now explain how free variables may be encoded in an alphabet, provided the logic at hand is expressive enough. The idea is that a formula $\phi\in {\mathcal{Q}}_{A,x}[\mathcal{N}]$ may be regarded as a sentence over the extended alphabet $(A \times 2)$ ; in the same way, we may regard marked words as words over $(A \times 2)$ via the embedding $A^*\otimes {\mathbb{N}} \rightarrowtail (A \times 2)^*$ . More generally, given two disjoint contexts x and y, we will define two functions:

\[\varepsilon_{{\bf x}, {\bf y}} :{\mathcal{Q}}_{A,{\bf x}{\bf y}}[\mathcal{N}] \to \mathcal{Q}_{A \times 2^{\bf x}, {\bf y}}[\mathcal{N}] \quad \text{and}\quad \delta_{{\bf x},{\bf y}}: \mathcal{Q}_{A \times 2^{\bf x}, {\bf y}}[\mathcal{N}] \to {\mathcal{Q}}_{A,{{\bf x}{\bf y}}}[\mathcal{N}],\]

which we call, respectively, the encoding and the decoding function. As the name suggests, $\varepsilon_{{\bf x} {\bf y}}$ “encodes” the variables from x in the extended alphabet $A \times2^{\bf x}$ , while $\delta_{{\bf x},{\bf y}}$ reverts this process (see Corollary 5.20 for a precise statement).

Given contexts x and y, we let

\[\iota_{{\bf x}}:A^* \otimes {\mathbb{N}}^{ {\bf x}} \rightarrowtail (A \times 2^{\bf x})^*\]

denote the natural embedding of $ {\bf x}$ -marked words into the set of words over $(A \times 2^ {\bf x})$ , and

\[\iota_{{\bf x},{\bf y}}: A^* \otimes {\mathbb{N}}^{ {{\bf x}{\bf y}}} \rightarrowtail (A \times 2^{\bf x})^* \otimes {\mathbb{N}}^{ {\bf y}}\]

be defined by $\iota_{{\bf x}, {\bf y}}(w, {\bf i}, {\bf j}) = (\iota_{\bf x}(w, {\bf i}), {\bf j})$ , for every $(w, {\bf i}, {\bf j}) \in A^* \otimes{\mathbb{N}}^{ {{\bf x}{\bf y}}}$ .

In order to keep the notation simple, we first consider the case where x consists of a single variable x.

To define the encoding function, we need to assume that the quantifier $\exists!$ (there exists a unique) and the numerical predicate $=$ (formally given by $\{(n,n) \mid n \in {\mathbb{N}}\}$ ) are expressible in our logic. This assumption is needed so that we are able to define the set of all marked words $A^* \otimes {\mathbb{N}}$ as a language over $(A \times 2)$ . Indeed, one can easily check that the models of the sentence:

(19) \begin{equation} \Phi= \exists ! z\ \bigvee_{a \in A} {\sf P}_{(a,1)}(z)\end{equation}

are precisely the words of $(A \times 2)^*$ having exactly one letter of the form (a, 1), that is, those that belong to the image of $\iota_x: A^* \otimes {\mathbb{N}} \rightarrowtail (A \times 2)^*$ . More generally, if $\Phi$ is seen as a formula in a given context y, then its models are the y-marked words in the image of $\iota_{x, {\bf y}}: A^* \otimes {\mathbb{N}}^{ {x{\bf y}}} \rightarrowtail (A \times 2)^* \otimes{\mathbb{N}}^{ {\bf y}}$ .

By a routine structural induction on the construction of a formula, we can show the following:

Lemma 5.14. Let $\phi$ be a formula in context $x{\bf y}$ over the alphabet A. Then, for every $w \in A^*$ , $i \in \{0, \dots, \left\lvert w\right\rvert - 1\}$ , and ${\bf j} \in \{0, \dots,\left\lvert w\right\rvert - 1\}^{\left\lvert{\bf y}\right\rvert}$ , we have

\[(w, i, {\bf j}) \models \phi \iff \iota_{x, {\bf y}}(w, i,{\bf j}) \models \phi^x.\]

Corollary 5.15. Let $\Phi$ be the formula defined in (19). Then, there is a well-defined lattice homomorphism:

\[\varepsilon_{x, {\bf y}}: {\mathcal{Q}}_{A,x{\bf y}} [\mathcal{N}] \to {\mathcal{Q}}_{A\times 2,{\bf y}} [\mathcal{N}], \qquad \phi \mapsto \phi^x \wedge \Phi,\]

which makes the following diagram commute:

That is, for every $\phi \in {\mathcal{Q}}_{A,x{\bf y}} [\mathcal{N}]$ , we have $L_{\varepsilon_{x,{\bf y}}(\phi)} = \iota_{x,{\bf y}}[L_{\phi}]$ .

We call encoding function (with respect to $x, {\bf y}$ ) the map $\varepsilon_{x {\bf y}}: {\mathcal{Q}}_{A,x{\bf y}}[\mathcal{N}] \to {\mathcal{Q}}_{A\times 2,{\bf y}}[\mathcal{N}]$ of Corollary 5.15. Note that, if ${\bf y}'$ is a context containing y (so that $ {\mathcal{Q}}_{A,x{\bf y}}[\mathcal{N}] \subseteq {\mathcal{Q}}_{A,x{\bf y}'}[\mathcal{N}]$ and $ {\mathcal{Q}}_{A \times 2,{\bf y}}[\mathcal{N}] \subseteq {\mathcal{Q}}_{A\times 2,{\bf y}'} [\mathcal{N}]$ ) then $\varepsilon_{x, {\bf y}}$ is the restriction and co-restriction of $\varepsilon_{x, {\bf y}'}$ .

Conversely, a formula $\psi$ over $(A \times 2)$ in context y may be regarded as a formula over A in context $x{\bf y}$ as follows:

Of course, we are assuming that things have been arranged so that the variable x does not occur in $\psi$ .

Again, a structural induction on construction of formulas shows the following:

Lemma 5.17. Let $\psi$ be a formula in context y over the alphabet $(A \times 2)$ . Then, for every $w \in A^*$ , $i \in \{0, \dots, \left\lvert w\right\rvert - 1\}$ , and ${\bf j} \in \{0, \dots,\left\lvert w\right\rvert - 1\}^{\left\lvert{\bf y}\right\rvert}$ , we have

\[(w, i,{\bf j}) \models \psi_x \iff \iota_{x, {\bf y}}(w, i, {\bf j}) \models \psi.\]

The next result is a straightforward consequence of Lemma 5.17.

Corollary 5.18. There is a well-defined Boolean algebra homomorphism:

\[\delta_{x,{\bf y}}: {\mathcal{Q}}_{A\times 2,{\bf y}} [\mathcal{N}] \to {\mathcal{Q}}_{A,x{\bf y}}[\mathcal{N}], \qquad\psi \mapsto \psi_x,\]

which makes the following diagram commute:

That is, for every $\psi \in {\mathcal{Q}}_{A\times 2,{\bf y}}[\mathcal{N}]$ , we have $L_{\delta_{x,{\bf y}} (\phi)} = \iota_{x,{\bf y}}^{-1}(L_{\phi})$ .

The decoding function (with respect to $x, {\bf y}$ ) is then the map $\delta_{x,{\bf y}}: {\mathcal{Q}}_{A\times 2,{\bf y}} [\mathcal{N}] \to {\mathcal{Q}}_{A,x{\bf y}}[\mathcal{N}]$ defined in Corollary 5.18. Similarly to what happens for $\varepsilon_{x, {\bf y}}$ , if ${\bf y}'$ is a context containing y, then $\delta_{x, {\bf y}}(\psi)$ is the restriction and co-restriction of $\delta_{x, {\bf y}'}(\psi)$ .

Let us now define $\varepsilon_{{\bf x}, {\bf y}}$ and $\delta_{{\bf x}, {\bf y}}$ , for all contexts x and y. We write ${\bf x} = \{x_1, \dots, x_k\}$ and, for each $i \in \{0, \dots, k\}$ , we let ${\bf x}_i$ denote the context $\{x_{1}, \dots, x_i\}$ (in particular, ${\bf x}_0$ denotes the empty context and ${\bf x}_k = {\bf x}$ ). Then, for each $i \in \{1, \dots, k\}$ , we have defined:

\[\varepsilon_{x_i, {\bf x}_{i-1}{\bf y}}: {\mathcal{Q}}_{{A\times 2^{k-i}},{\bf x_i}{\bf y}}[\mathcal{N}] \to {\mathcal{Q}}_{A\times 2^{k-i+1},{\bf x}_{i-1}{\bf y}}[\mathcal{N}]\]

and

\[\delta_{x_i, {\bf x}_{i-1}{\bf y}}:{\mathcal{Q}}_{A\times 2^{k-i+1},{\bf x}_{i-1}{\bf y}} [\mathcal{N}] \to {\mathcal{Q}}_{A\times 2^{k-i},{\bf x}_i{\bf y}}[\mathcal{N}].\]

An iteration of these maps yields two functions:

\[ \varepsilon_{{\bf x}, {\bf y}}: {\mathcal{Q}}_{A,{\bf x}{\bf y}}[\mathcal{N}] \to \mathcal{Q}_{A \times 2^{\bf x},{\bf y}}[\mathcal{N}] \quad \text{and}\quad \delta_{{\bf x},{\bf y}}: \mathcal{Q}_{A \times 2^{\bf x},{\bf y}}[\mathcal{N}] \to {\mathcal{Q}}_{A,{\bf x}{\bf y}}[\mathcal{N}],\]

which are given, respectively, by $\varepsilon_{{\bf x}, {\bf y}} =\varepsilon_{x_1,{\bf x}_0{\bf y}} \circ \dots \circ\varepsilon_{x_k,{\bf x}_{k-1}{\bf y}}$ and by $\delta_{{\bf x},{\bf y}} =\delta_{x_k,{\bf x}_{k-1}{\bf y}} \circ \dots \circ \delta_{x_1,{\bf x}_0{\bf y}}$ . In particular, $\varepsilon_{{\bf x}, {\bf y}}$ is a lattice homomorphism, while $\delta_{{\bf x}, {\bf y}}$ is a Boolean algebra homomorphism. Moreover, when x consists of a single variable x, the functions $\varepsilon_{x, {\bf y}}$ and $\delta_{x, {\bf y}}$ are precisely those previously defined.

By Corollaries 5.15 and 5.18, we have the following:

Proposition 5.19. Let x and y be disjoint contexts. Then, the following diagrams commute:

An immediate, but important, consequence of Proposition 5.19 is the following:

In particular, $\varepsilon_{{\bf x}, {\bf y}}$ is a lattice embedding, and $\delta_{{\bf x}, {\bf y}}$ is a quotient of Boolean algebras.

We finally show that it suffices to consider substitution with respect to a single variable.

Proposition 5.21. Let $\Gamma$ be a class of sentences, and let $\Delta \subseteq {\mathcal{Q}}_{A,{\bf x} x}[\mathcal{N}]$ be a finite Boolean subalgebra. Then, there exist a finite Boolean subalgebra $\Delta' \subseteq {\mathcal{Q}}_{A \times 2^{\bf x},x}[\mathcal{N}]$ , and an embedding $\zeta:{\rm At}(\Delta) \rightarrowtail {\rm At}(\Delta')$ , for which the following diagram commutes:

where $C_{\Delta} = {\rm At}(\Delta)$ and $C_{\Delta'} = {\rm At}(\Delta')$ . In particular, since $\zeta_\Gamma$ is surjective, we have

\[\Gamma \odot \Delta = \delta_{{\bf x}, \emptyset}[\Gamma \odot \Delta'].\]

Proof. We take $\Delta' = \{\psi \in {\mathcal{Q}}_{A \times 2^{\bf x},x} [\mathcal{N}] \mid \delta_{{\bf x} x}(\psi) \in \Delta\}$ . Since $\delta_{{\bf x} x}$ is a Boolean algebra homomorphism, $\Delta'$ is a Boolean algebra. Moreover, $\delta_{{\bf x} x}$ restricts and co-restricts to a Boolean algebra quotient $\delta_{{\bf x} x}': \Delta' \twoheadrightarrow \Delta$ . We let $\zeta: {\rm At}(\Delta) \rightarrowtail {\rm At}(\Delta')$ be its dual. Let us show that the diagram of the statement commutes. Let $w \in A^* \otimes {\mathbb{N}}^{ {\bf x}}$ and $\phi \in \Gamma(C_{\Delta'})$ . Then, we have

and

Therefore, the diagram commutes provided the equality

(20) \begin{equation} \zeta^* \circ \tau_\Delta(w) = \tau_{\Delta'}\circ \iota_{{\bf x}}(w) \end{equation}

holds. We first note that both sides of this equality are words over $C_{\Delta'} = {\rm At}(\Delta')$ of length $\left\lvert w\right\rvert$ . So, we fix $i \in \{0, \dots, \left\lvert w\right\rvert -1\}$ . We let $c_\ell$ and $c_r$ denote, respectively, the i-th letter of the left and of the right-hand side of (20). We also let $\psi_{c_\ell}$ and $\psi_{c_r}$ denote the atoms of $\Delta'$ represented by the letters $c_\ell$ and $c_r$ , respectively. Now, since $\zeta$ is dual to $\delta_{{\bf x}, x}$ , we have that $\psi_{c_\ell}$ is determined by the condition $(\tau_\Delta(w))_i \leq \delta_{{\bf x}, x}(\psi_{c_\ell})$ where, by (14), $(\tau_\Delta(w))_i$ the unique atom of $\Delta$ satisfying $(w,i)\models (\tau_\Delta(w))_i$ . In particular, we have $(w, i) \models \delta_{{\bf x}, x}(\psi_{c_\ell})$ . On the other hand, by (14), $\psi_{c_r}$ is the unique atom of $\Delta'$ satisfying $(\iota_{{\bf x}}(w), i) \models \psi_{c_r}$ . Since $(\iota_{{\bf x}}(w), i) = \iota_{{\bf x}, x}(w,i)$ , by Proposition 5.19, this is equivalent to $(w, i) \models \delta_{{\bf x}, x}(\psi_{c_r})$ . Thus, we have $\psi_{c_\ell} = \psi_{c_r}$ as required.

Using the definition of $(\Gamma\odot \Delta)$ when $\Delta$ is an arbitrary Boolean algebra, we may easily derive the following result from Proposition 5.21 and from its proof:

Corollary 5.22. Let $\Gamma$ be a class of sentences, and let $\Delta \subseteq {\mathcal{Q}}_{A,{\bf x} x}[\mathcal{N}]$ be a Boolean subalgebra. Then, there exists a Boolean subalgebra $\Delta' \subseteq {\mathcal{Q}}_{A \times 2^{\bf x},x}[\mathcal{N}]$ , namely, $\Delta' = \{\psi \in {\mathcal{Q}}_{A \times 2^{\bf x},x}[\mathcal{N}] \mid \delta_{{\bf x}, x}(\psi) \in \Delta\}$ , such that

\[\Gamma \odot \Delta = \delta_{{\bf x}, \emptyset}[\Gamma \odot \Delta'].\]

5.4 Applications to logic on words

In this section, we show the utility of the Substitution Principle in handling the application of one layer of quantifiers to a Boolean algebra of formulas. As we will see, this allows for a systematic study of fragments of logic via smaller subfragments (cf. Proposition 5.25 below). Before stating it, we show how we can assign to a given set of quantifiers a class of sentences.

Lemma 5.23. Let $\mathcal{Q}$ be a set of quantifiers. The assignment

\[\Gamma_\mathcal{Q}: A \mapsto \mathcal{Q}_A[\emptyset] = \left\langle \left\{Q x \bigvee_{a \in B} {\sf P}_a(x) \mid Q \in \mathcal{Q}, \ B \subseteq A\right\}\right\rangle_{\sf BA}\]

defines a class of sentences.

The following is an immediate consequence of the definitions of $\Gamma_\mathcal{Q}$ and of $(\_\odot\_)$ , and it shows that $\Gamma_\mathcal{Q}$ -substitutions model the application of a layer of quantifiers to a given Boolean algebra.

Lemma 5.24. Let A be a finite alphabet, $\mathcal{Q}$ a set of quantifiers, $\mathcal{N}$ a set of numerical predicates, and $\Delta \subseteq \mathcal{Q}_{A, x}[\mathcal{N}]$ a Boolean subalgebra. Then,

\[\Gamma_\mathcal{Q}\odot \Delta = \langle\{Q x\ \phi \mid \phi \in \Delta\}\rangle_{\sf BA}.\]

Finally, an iteration of Lemma 5.24 yields the following:

Proposition 5.25. Let A be a finite alphabet, $\mathcal{Q}$ a set of quantifiers, and $\mathcal{N}$ a set of numerical predicates. For each $n > 0$ , let $\Delta_n$ be the Boolean algebra of quantifier-free formulas in the context ${\bf x} = \{x_1, \ldots, x_n\}$ . Then, a sentence of $\mathcal{Q}_A[\mathcal{N}]$ has quantifier-depth n if and only if it belongs to

\[\underbrace{\Gamma_{\mathcal{Q}} \odot (\dots \odot(\Gamma_{\mathcal{Q}}}_{n\text{ times}} \odot \ \Delta_n)\dots).\]

In particular, we have

\[\mathcal{Q}_A [\mathcal{N}] = \bigcup_{n \in {\mathbb{N}}} \underbrace{\Gamma_{\mathcal{Q}} \odot (\dots \odot(\Gamma_{\mathcal{Q}}}_{n\text{ times}} \odot \ \Delta_n)\dots).\]