THE AUTOMORPHISM GROUP OF THE FRAÏSSÉ LIMIT OF FINITE HEYTING ALGEBRAS

Abstract

Roelcke non-precompactness, simplicity, and non-amenability of the automorphism group of the Fraïssé limit of finite Heyting algebras are proved among others.

In the present article, we examine the Fraïssé limit L of (nontrivial) finite Heyting algebras. The existence of the model-completion $T^*$ of the theory T of Heyting algebra stems from the uniform interpolation theorem for propositional intuitionistic logic, in which the interpolant of two sentences depends on only one of the two sentences [8, 15]. The Fraïssé limit L is the prime model of $T^*$ and was used to derive an axiomatization of $T^*$ by Darnière [5]. The results in the present article complement existing literature on the automorphism groups of ultrahomogeneous lattices, e.g., the countable atomless Boolean algebra [1, 11, 17] and the universal distributive lattice [7], as our ultrahomogeneous structure is not $\omega $ -categorical.

The article is organized as follows: In the first section, we recall relevant definitions and fix notation. In the second section, we compare the automorphism of L with those of better-known ultrahomogeneous structures, especially that of the countable atomless Boolean algebra B. It will be proved that $\mathrm {Aut}(L)$ is not Roelcke precompact and thus is not realized as the automorphism group of any $\omega $ -categorical structure. Having established that, we will construct continuous embeddings of $\mathrm {Aut}(L)$ into $\mathrm {Aut}(B)$ . In the last section, we will see that $\mathrm {Aut}(L)$ is not amenable and that $\mathrm {Aut}(L)$ is simple. The argument used to prove the last claim is applicable to other Fraïssé classes of lattices with the superamalgamation property, which is of an independent interest as it characterizes the validity of the Craig interpolation theorem for nonclassical logics [13, 14].

It is an important future task to investigate the combinatorics of the age $\mathrm {Age}(L)$ of L, in particular about the existence of order expansion of $\mathrm {Age}(L)$ with the Ramsey property and the ordering property, and the metrizability of $\mathrm {Aut}(L)$ .

1 Preliminaries

We review an important construction of Heyting algebras (this material appears in, e.g., [4]). For an arbitrary poset ${\mathbb P}$ , the poset of upward closed sets, or up-sets, of ${\mathbb P}$ ordered by inclusion has a Heyting algebra structure. We call this Heyting algebra the dual of ${\mathbb P}$ . Conversely, if H is a finite Heyting algebra, then one can associate with H the poset ${\mathbb P}$ of join-prime elements of H with the reversed order. One can show that the dual of ${\mathbb P}$ is isomorphic to H.

Suppose that H and $H'$ are the duals of ${\mathbb P}$ and ${\mathbb P}'$ , respectively, and that $f : {\mathbb P} \to {\mathbb P}'$ is p-morphic, i.e., f is monotonic with

$$\begin{align*}\forall u \in \mathbb{P}\ \forall v \ge f(u)\ \exists\ w \ge u f (w) = u, \end{align*}$$

then the function $f^*$ defined on $H'$ that maps each up-set with its inverse image under f is a Heyting algebra homomorphism $H' \to H$ . We call $f^*$ the dual of f as well. If f is injective, then $f^*$ is surjective; if f is surjective, then $f^*$ is a Heyting algebra embedding.

Henceforth, L is the Fraïssé limit of all finite nontrivial Heyting algebras, which exists [9]. This structure is ultrahomogeneous in the sense that every isomorphism between finitely generated substructures, or members of the age $\mathrm {Age}(L)$ of L, extends to an automorphism on L. (Throughout the paper, Heyting algebras are structures in the language $\{0, 1, \wedge , \vee , \to \}$ unless otherwise stated.) The strong amalgamation property of the theory T of Heyting algebras was proved by Maksimova [14]; in fact, her construction establishes the superamalgamation property for the class of finite Heyting algebras. Recall that a Fraïssé class $\mathcal K$ of poset expansions has the superamalgamation property if for every diagram $A_1 \hookleftarrow A_0 \hookrightarrow A_2$ of inclusion maps in $\mathcal K$ , the amalgamation property of $\mathcal K$ is witnessed by a diagram $A_1 \hookrightarrow A \hookleftarrow A_2$ of inclusion maps in such a way that

, where

is the ternary relations for subsets of A defined as

The superamalgamation property for the class $\mathcal K$ of finite Heyting algebras follows from the superamalgamation property for T [14]. Indeed, let $A_0, A_1, A_2 \in \mathcal {K}$ with $A_0 \subseteq A_i$ ( $i = 1, 2$ ). Consider the quantifier-free sentence $\phi $ with parameters from $A_1 \cup A_2$ that is the conjunction of $\bigwedge \mathrm {Diag}(A_1)$ , $\bigwedge \mathrm {Diag}(A_2)$ , and the quantifier-free sentence expressing

, where $\operatorname {\mathrm {Diag}}(\cdot )$ denotes the diagrams of structures. By the superamalgamation property for T, we have a model of $T \cup \{\phi \}$ . By the stronger form of the finite model property for Heyting algebras that is applicable to all quantifier-free formulas [6], $\phi $ has a model in $\mathcal K$ .

We introduce notation naming structures obtained by the superamalgamation property: Let D be the diagram $B \hookleftarrow A \hookrightarrow C$ in $\mathrm {Age}(L)$ , where $\mathrm {Age}(L)$ the age of L is regarded as a category whose morphisms are the embeddings. The superamalgamation property for $\mathrm {Age}(L)$ gives rise to a subalgebra $\bigsqcup D$ of L such that there are embeddings $\iota _{\hookleftarrow }^D : B \hookrightarrow \bigsqcup D$ and $\iota _{\hookrightarrow }^D : C \hookrightarrow \bigsqcup D$ with . One can show that $\iota _{\hookleftarrow }^D(B) \setminus \iota _{\hookleftarrow }^D(A)$ and $\iota _{\hookrightarrow }^D(C) \setminus \iota _{\hookrightarrow }^D(A)$ are disjoint.

2 Comparison with known automorphism groups

In this section, we study the automorphism group of L in relation to those of better-known ultrahomogeneous structures. First of all, we find it interesting to see that $\mathrm {Aut}(L)$ is distinct from the automorphism groups of better-known ultrahomogeneous structures. In particular, we will later construct embeddings of $\mathrm {Aut}(L)$ into the automorphism group of the countable atomless Boolean algebra, but the first result of this section implies that they cannot be topological group isomorphisms.

Recall that a non-archimedean topological group G, such as $\mathrm {Aut}(L)$ , is Roelcke precompact if the set of double cosets $\{VxV \mid x \in G\}$ is finite for every open subgroup $V \le G$ (see, e.g., [18, p. 534]).

Theorem 2.1. $\mathrm {Aut}(L)$ is not Roelcke precompact. A fortiori, $\mathrm {Aut}(L)$ cannot be realized as the automorphism group of any countable $\omega $ -categorical structure.

Proof Tsankov [18] showed that a topological group is Roelcke precompact if and only if it is the inverse limit of some inverse system of oligomorphic permutation groups. The second part of the statement of this theorem follows from its first part and this result.

Since L is ultrahomogeneous, $\mathrm {Aut}(L)$ is not Roelcke precompact if and only if there are sequences $(a_i)_{i<\omega }, (b_i)_{i<\omega }$ of elements of L such that $\mathrm {tp}^L(a_i / \emptyset ) = \mathrm {tp}^L(b_i / \emptyset ) = \mathrm {tp}^L(a_j / \emptyset ) = \mathrm {tp}^L(b_j / \emptyset )$ for $i, j < \omega $ , and that $\{\mathrm {tp}^L(a_ib_i / \emptyset )\}$ is infinite. Furthermore, since $\mathrm {Th}(L)$ eliminates quantifiers, types realized in L are in one-to-one correspondence with quantifier-free types realized in L. Finally, as L is locally finite, the latter are essentially isomorphism types of subalgebras of L with distinguished generators.

With that in mind, let $F_1$ be the free Heyting algebra whose generator is x. For each term $t(x) \in F_1$ , write $L_t$ for the quotient of $F_1$ by the principal filter $\theta _t$ generated by t. Furthermore, let $L_t^*$ be the Heyting algebra obtained by adding a new minimum element $0^{L_t^*}$ below $0^{L_t}$ . For a term $t(x)$ , we define $t^*(x, y)$ to be the term obtained by replacing every occurrence of $0$ with y. One can check that $(t^*)^{L_t^*}([x]_t, 0^{L_t}) = [t(x)]_t \in L_t^*$ , where $[\cdot ]_t$ denotes the congruence class with respect to $\theta _t$ . Therefore, $L_t^*$ is generated by $0^{L_t}$ and $[x]_t$ . We have obtained 2-generated subalgebras of L of infinitely many isomorphism types. On the other hand, we have $\langle [x]_t \rangle ^{L_t^*} = \langle 0^{L_t} \rangle ^{L_t^*}$ is a 3-chain for all t.

It is well known that $\mathrm {Aut}(M)$ for a countable $\omega $ -categorical M is not locally compact [12].

Proposition 2.2. The topological group $\mathrm {Aut}(L)$ is not locally compact.

Proof It suffices to show that for every finite subset $S \subseteq L$ there is an infinite orbit in the action of $\mathrm {Aut}(L)_{(S)}$ on $ L$ . Note that for every finite subalgebra $A \subseteq L$ , there exists $a \in L \setminus A$ such that a is join-prime in $\langle Aa \rangle ^L$ . Indeed, consider the dual $\Bbb P$ of A and the disjoint union $\Bbb P' := \Bbb P \sqcup \{w\}$ , where w is a fresh element, and let a be the image of $\{w\}$ under the embedding of the dual of $\Bbb P'$ into L that fixes A pointwise. By repeatedly using this, take an $\omega $ -sequence $(a_i)_{i<\omega }$ of elements of L such that $a_i \in L \setminus \langle Sa_0a_1\dots a_{i-1}\rangle ^L$ is join-prime in $\langle Sa_0a_1\dots a_{i}\rangle ^L$ for $i < \omega $ . By construction, there exists an automorphism $\phi _i : L \to L$ fixing S pointwise such that $\phi _i(a_i) = a_{i+1}$ for $i<\omega $ . Hence, the orbit of $a_0$ under $\mathrm {Aut}(L)_{(S)}$ is infinite.

An obvious strategy to study $\mathrm {Aut}(L)$ is to relate it to $\mathrm {Aut}(B)$ , where B is the countable atomless Boolean algebra. The following lemma gives rise to a topological embedding of the former into the latter. Recall that an interior operator on a Boolean algebra B is a function from B to B that is decreasing, monotonic, idempotent, and commuting over meets. We write interior operators in superscripts so that $B^\circ $ is the image of an interior operator ${}^\circ : B \to B$ . For every interior operator ${}^\circ : B \to B$ , the image $B^\circ $ with the induced order is isomorphic to some Heyting algebra (see, e.g., [2]).

Lemma 2.3.

1. 1. Let $f:H \to H_1$ be a Heyting algebra homomorphism between finite algebras. There are finite Boolean algebras $B(H)$ and $B(H_1)$ , interior operators ${}^{\circ }, {}^{\circ _{1}}$ on $B(H), B(H_1)$ , respectively, and a unique Boolean algebra homomorphism $B(f) : B(H) \to B(H_1)$ such that $B(H)^{\circ } \cong H$ , $B(H_1){}^{\circ _{1}} \cong H_1$ and that $B(f)$ extends f. If f is injective, so is $B(f);$ if f is surjective, so is $B(f)$ .

2. 2. There is an interior operator ${}^{\circ }$ on the countable atomless Boolean algebra B such that $B^{\circ }$ is isomorphic to the universal ultrahomogeneous countable Heyting algebra L.

Proof

1. 1. Let P and $P_1$ be the dual posets of H and $H_1$ , respectively. There is a p-morphism $D(f) : P_1 \to P$ that is the dual of f. $D(f)$ is surjective if f is injective. Let $B(H) = \mathscr {P} (P)$ and $B(H_1) = \mathscr {P}(P_1)$ . $D(f)$ induces a Boolean algebra homomorphism $B(f) : B(H) \to B(H_1)$ . $B(f)$ is injective if $D(f)$ is surjective. Likewise, $B(f)$ is surjective if f is. Let ${}^{\circ }, {}^{\circ _{1}}$ be the operations that take a subset to the maximal up-set contained by that set.

2. 2. Let $(L_i)_{i<\omega }$ be a chain of finite Heyting algebras used in the construction of L; so $\bigcup _i L_i = L$ . Let $B_i = B(L_i)$ as above and ${}^{\circ _{i}}$ be an interior operator such that $B_i{}^{\circ _{i}} \cong L_i$ . We may take $B_i \subseteq B_{i+1}$ for $i < \omega $ . Then ${}^{\circ _{i+1}}$ extends ${}^{\circ _{i}}$ . Let $B = \bigcup _i B_i$ and ${}^{\circ } = \bigcup {}^{\circ _{i}}$ . Then $B{}^{\circ } = \left ( \bigcup _i B_i \right ){}^{\circ } = \bigcup _i B_i{}^{\circ _{i}} = \bigcup _i L_i = L$ . It remains to show that B is atomless. Take an arbitrary $a \in B$ that is nonzero. Take $i < \omega $ such that $a \in B_i$ . Let $P_i$ be the poset dual to $L_i$ ; then a is a nonempty subset of $P_i$ . Take some $w \in a$ . Let $P'$ be the poset obtained from $P_i$ by replacing w with the 2-chain $\{w_1 < w_2\}$ . Let $\pi : P' \twoheadrightarrow P_i$ be the surjection that maps the chain to $\{w\}$ and is the identity elsewhere. This is a p-morphism, and it induces $\iota : L_i \hookrightarrow L'$ , where $L'$ is the dual of $P'$ . Take $k < \omega $ such that there is an embedding $\iota ': L' \hookrightarrow L_k$ such that $\iota ' \circ \iota $ is the identity on $L_i$ . Let $b = (a \setminus \{w \}) \cup \{w_1\}$ . Then $b \in B_k = B(L_k) \subseteq B$ and $0 < b < a$ .

Theorem 2.4. An automorphism $L \to L$ can be extended $($ as a function between pure sets $)$ to an automorphism $B \to B$ . This extension is unique. Moreover, this defines an injective group homomorphism $\mathrm {Aut}(L) \hookrightarrow \mathrm {Aut}(B)$ that is a homeomorphism onto its image.

Proof Let $f : L \to L$ be an automorphism. Let $f_k : L_k \to L_k'$ be the restriction of f to $L_k$ where $L_k' = f(L_k)$ . Each $f_k$ is an isomorphism. By the fact above, $f_k$ induces a Boolean algebra isomorphism $B(f_k) : B(L_k) \to B(L_k')$ for each $k < \omega $ ; and by construction $B(f_j)$ extends $B(f_k)$ for each $k < j < \omega $ . Let $\hat f = \bigcup _k B(f_k)$ . Then $\hat f$ is an isomorphism $B \to B$ .

Let $g : L \to L$ be another isomorphism. We have $\hat f \circ \hat g = (f \circ g){\hat {}}$ because each side of the equation extends $f \circ g$ .

Let $\iota : \mathrm {Aut}(L) \to \mathrm {Aut}(B)$ be the map $f \mapsto \hat f$ . The map $\iota $ is a group homomorphism as seen above, and it is clearly injective.

Next, we prove that $\iota $ is continuous. Let $\bar b$ be a tuple in B. It suffices to show that for an automorphism $f : L \to L$ the value of $\hat f(\bar b)$ is determined by the value of $f(\bar a)$ for a tuple $\bar a$ in L. There exists $k < \omega $ such that $\bar b$ is in $B_k = B(L_k)$ . Let $f_k : L_k \to L_k'$ be an isomorphism that is a restriction of f. Then $\hat f(\bar b) = B(f_k)(\bar b)$ . Let $\bar a$ be an enumeration of the finite algebra $L_k$ ; then $\bar a$ is what we needed.

Finally, we show that the image $\iota (U)$ is open in $\operatorname {ran} \iota \subseteq \mathrm {Aut}(B)$ for an arbitrary basic open set U of $\mathrm {Aut}(L)$ . Indeed, let U be the set of $f : L \to L$ fixing the values of f at $\bar a \in L$ ; then $\hat g \in \iota (U)$ if and only if $\hat g \upharpoonright B_0 = \hat f \upharpoonright B_0$ for $g : L \to L$ , where $B_0$ is the Boolean subalgebra of B generated by $\bar a$ .

Note that the structure L is not interpretable in B because the latter is $\aleph _0$ -categorical whereas the former is not.

There is another way $\mathrm {Aut}(B)$ and $\mathrm {Aut}(L)$ can be related. Recall that a relativized reduct is a special kind of interpretation where the domain of the interpreted structure is a $0$ -definable subset of the domain (as opposed to powers thereof) of the interpreting structure.

Lemma 2.5. There is an atomless Boolean algebra which is a relativized reduct B of L, where every element L is a finite join of elements of B.

Proof The set B of fixed points of $\neg \neg$ in L is a Boolean algebra by setting $a \vee ^B b = \neg \neg (a \vee ^L b)$ and the remaining operations of B the restrictions of the corresponding operations of L. (Note that B is not a substructure of L.) By [9, Proposition 4.28(ii)], B is atomless.

Let $a \in L$ be arbitrary. Take a finite subalgebra $H \subseteq L$ such that $a \in H$ , and let ${\mathbb P}$ be the dual poset of H so we may identify an element of H with an up-set of ${\mathbb P}$ . Possibly by replacing L by another finite Heyting algebra into which L embeds, we may assume that ${\mathbb P}$ is a forest. Furthermore, without loss of generality, we may assume that a is principal as an up-set in ${\mathbb P}$ , generated by $x \in {\mathbb P}$ . If x is a root, then a itself is in B, so there remains nothing to be shown. Suppose not, and let $x^-$ be the predecessor of x. Let ${\mathbb P}_1, {\mathbb P}_2$ be disjoint posets isomorphic to that induced by $a \subseteq {\mathbb P}$ . Let ${\mathbb P}' := ({\mathbb P} \setminus a) \sqcup {\mathbb P}_1 \sqcup {\mathbb P}_2$ whose partial order is the least containing those of the summands and $x^- \le {\mathbb P}_1$ , $x^- \le {\mathbb P}_2$ . Consider the surjective p-morphism ${\mathbb P}' \twoheadrightarrow {\mathbb P}$ that collapses $\{\min {\mathbb P}_1, \min {\mathbb P}_2\}$ to x, and let $i :H \hookrightarrow H'$ be the Heyting algebra embedding it induces. (See also Figure 1.) Note that ${\mathbb P}_i \in H'$ is in B for $i = 1, 2$ and that $i(a) = {\mathbb P}_1 \vee {\mathbb P}_2$ . Let $H_r(a)$ be a subalgebra of L such that there is an isomorphism $\phi : H' \to H_r(a)$ that extends the identity map on H. Let $r_1(a) := \phi ({\mathbb P}_1)$ and $r_2(a) := \phi ({\mathbb P}_2)$ . We have $a = r_1(a) \vee r_2(a)$ and $r_i(a) \in B (i = 1,2)$ as promised.

Proposition 2.6. Let $h_{\neg \neg } : \mathrm {Aut}(L) \to \mathrm {Aut}(B)$ be the continuous homomorphism induced by the interpretation of the lemma above. This is injective and is a homeomorphism onto its image. However, $h_{\neg \neg }$ is not surjective, and its image is a non-dense non-open subset of $\mathrm {Aut}(B)$ .

Proof The first claim is immediate. We show that $h_{\neg \neg }$ is not surjective.

Consider the three-element chain $C_3$ , which can be regarded as a Heyting algebra, and let $a \in C_3$ be such that $0 < a < 1$ . Note that a does not have $\neg \neg a = a$ and a principal up-set in the dual finite poset of $C_3$ . Let D be the diagram $C_3 \hookleftarrow \mathbf 2 \hookrightarrow C_3$ , where $\mathbf 2$ is the two-element Heyting algebra. Let $a_0 = \iota _{\hookleftarrow }^D(a)$ , $a_{1.5} = \iota _{\hookrightarrow }^D(a)$ , and $H = H_r(a_{1.5})$ . Next, let $D'$ be the diagram $H \hookleftarrow \iota _{\hookleftarrow }^D(C_3) \hookrightarrow H$ . Let $a_{1i} = \iota _{\hookleftarrow }^{D'}(r_i(a_{1.5}))$ , $a_{2i} = \iota _{\hookrightarrow }^{D'}(r_i(a_{1.5}))$ , and $a_{0i} = r_i(a_0)$ for $i=1,2$ . Refer to Figure 2 for this construction.

Figure 1 Construction of $H'$ .

Figure 2 Construction by amalgamation.

The Boolean subalgebra $B_6$ generated by $a_{ji}$ ( $0 \le j \le 2, 1 \le i \le 2$ ) in B has six atoms, each permutation of which extends to an automorphism of B. Consider the permutation $a_{ji} \mapsto a_{(j + 1 \bmod 3)i}$ , which extends to an automorphism of $B_6$ , which in turn extends to $\phi \in \mathrm {Aut}(B)$ by ultrahomogeneity of B. By construction,

$$\begin{align*}\bigvee_L \phi(\{a_{11}, a_{12}\}) \neq \bigvee_L \phi(\{a_{21}, a_{22}\}),\end{align*}$$

showing that $\phi $ is not in the image of $h_{\neg \neg }$ .

The last paragraph also shows that the image of $h_{\neg \neg }$ is not dense. To see that $\operatorname {\mathrm {ran}} h_{\neg \neg }$ is not open, let $\overline b$ be an arbitrary tuple in B, and we prove that $\mathrm {Aut}(B)_{(\overline b)} \setminus \operatorname {\mathrm {ran}} h_{\neg \neg } \neq \emptyset $ . Take a finite subalgebra K of L such that K generates $\langle \overline b\rangle ^B$ as a Boolean algebra. Let $D''$ be the diagram ¹ $K \hookleftarrow \mathbf 2 \hookrightarrow \bigsqcup D^\prime$ such that the image $\operatorname {\mathrm {ran}} \iota _{\hookrightarrow }^{D''}$ generates a copy $B^{\prime }_6$ of $B_6$ . Take an automorphism $\psi _0$ on $\bigsqcup D''$ such that $\psi _0 \upharpoonright B^{\prime }_6$ is as constructed in the preceding paragraph and that $\psi _0 \upharpoonright \operatorname {\mathrm {ran}} \iota _{\hookleftarrow }^{D''}$ is the identity. ² The automorphism $\psi _0$ extends to another $\phi \in \mathrm {Aut}(B)$ , which is in $\mathrm {Aut}(B)_{(\overline b)} \setminus \operatorname {\mathrm {ran}} h_{\neg \neg }$ .

3 Amenability and simplicity

We now proceed to showing the non-amenability of $\mathrm {Aut}(L)$ .

Definition 3.1. Let H be a finite nondegenerate Heyting algebra. For $b \in H\!$ , we write $I(b)$ for the set of join-prime elements below or equal to b. Let $\prec $ be an arbitrary linear extension of the partial order on $I(1)$ induced from H. We define a total order $\prec ^{\mathrm {alex}}$ on H extending $\prec $ by the following:

$$\begin{align*}a \prec^{\mathrm{alex}} a' \iff \max_\prec (I(a) \mathbin{\triangle} I(a')) \in I(a'). \end{align*}$$

This is clearly a total order, which is known as the anti-lexicographic order. We call this a natural ordering on H.

An expansion of a finite nondegenerate Heyting algebra H by a natural total order is called a finite Heyting algebra with a natural ordering.

It is easy to check that if $(H, \prec )$ is a finite Heyting algebra with a natural ordering, and H happens to be a Boolean algebra, then $(H, \prec )$ is a finite Boolean algebra with a natural ordering in the sense of Kechris, Pestov, and Todorčević [10]. Recall from the same paper that an order expansion $\mathcal C^*$ of a Fraïssé class $\mathcal C$ is reasonable if there exists some admissible order $\prec _2$ on $M_2$ , i.e., an order such that $(M_2, \prec _2) \in \mathcal {C}^*$ , which extends $\prec _1$ whenever $M_1, M_2 \in \mathcal C$ with $M_1$ a subalgebra of $M_2$ , and $\prec _1$ is admissible on $M_1$ .

Proposition 3.2. The class $\mathcal K^*$ of finite Heyting algebras with a natural ordering is a reasonable Fraïssé expansion of $\mathrm {Age}(L)$ .

Proof We show that $\mathcal K^*$ is reasonable and that $\mathcal K^*$ has the amalgamation property. (Other claims are clear.) In what follows, for a totally ordered set $(X, <)$ and $Y, Z \subseteq X$ , we write $Y < Z$ to mean that $y < z$ whenever $y \in Y$ and $z \in Z$ .

Let $H_1 \subseteq H_2$ be finite Heyting algebra, and let $\prec _{1}^{\mathrm {alex}}$ be an arbitrary admissible total order on $H_1$ . We show that there exists an admissible order on $H_2$ extending $\prec _{1}^{\mathrm {alex}}$ . Let $\pi : {\mathbb P}_2 \twoheadrightarrow {\mathbb P}_1$ be the surjective p-morphism dual to the inclusion map $H_1 \hookrightarrow H_2$ . Note that with $I(1_{H_i})$ and ${\mathbb P}_i$ identified as pure sets, an admissible total order of $H_i$ extends the order-theoretic dual of the order of ${\mathbb P}_i$ for $i = 1,2$ .

Suppose that for $p,q \in {\mathbb P}_1$ we have $p \prec _1 q$ . Since $\prec _{1}^{\mathrm {alex}}$ is admissible, $p \not \le q$ . Take arbitrary $p', q' \in {\mathbb P}_2$ such that $\pi (p') = p$ and that $\pi (q') = q$ . Since $\pi $ is order-preserving a fortiori, we have $p' \not \le q'$ .

Let $R = (\mathord {\le } \setminus \Delta ) \cup \{(p',q') \mid \pi (p') \prec _2 \pi (q')\}$ be a binary relation on ${\mathbb P}_2 = I(1_{H_2})$ , where $\Delta $ is the diagonal relation. It can be shown by induction from the fact in the preceding paragraph that R contains no cycle. Therefore, R can be extended to a total order $\prec _2$ . Furthermore, for $p, q \in {\mathbb P}_1$ , we have $\pi ^{-1}(p) \prec _2 \pi ^{-1}(q)$ ; a fortiori, $\pi ^{-1}(p) \prec _{2}^{\mathrm {alex}} \pi ^{-1}(q)$ . This shows that $\prec _{2}^{\mathrm {alex}}$ extends $\prec _{1}^{\mathrm {alex}}$ .

Next, we prove the amalgamation property for $\mathcal K^*$ . Let D be the diagram $H_1 \hookleftarrow H_0 \hookrightarrow H_2$ in $\mathrm {Age}(L)$ and let $\prec _{i}^{\mathrm {alex}}$ be an arbitrary admissible ordering on $H_i$ for $i = 1,2$ . Recall the dual poset ${\mathbb P}$ of $\bigsqcup D$ is a sub-poset of the product order ${\mathbb P}_1 \times {\mathbb P}_2$ , where ${\mathbb P}_i$ is the dual of $H_i$ ( $i = 1, 2$ ) [14]. Take a total order $\prec $ on ${\mathbb P}$ so it extends the product order of $\prec _1$ and $\prec _2$ .

We first show that $\prec $ extends the dual of the order of ${\mathbb P}$ . Assume that $(p_1,p_2) \le (q_1, q_2)$ for $(p_i,q_j) \in {\mathbb P}$ and $1 \le i, j \le 2$ . (Recall that $p_i, q_i \in {\mathbb P}_i$ .) Since the order of ${\mathbb P}$ is induced by the product of those of ${\mathbb P}_1$ and ${\mathbb P}_2$ , we have $p_i \le q_i$ for $i = 1,2$ . Because $\prec _i$ extends the dual of the order of ${\mathbb P}_i$ , we have $p_i \succ _i q_i$ ( $i = 1, 2$ ). By the construction of $\prec $ , we have $(p_1,p_2) \succ (q_1, q_2)$ as desired.

We then prove that $(\bigsqcup D, \prec ^{\mathrm {alex}})$ witnesses the amalgamation property. Because of the strong amalgamation property of $\mathrm {Age}(L)$ , it suffices to show that $\prec ^{\mathrm {alex}}$ extends $\iota _{\hookleftarrow }^D(\prec _{1}^{\mathrm {alex}})$ and $\iota _{\hookrightarrow }^D(\prec _{2}^{\mathrm {alex}})$ . Take $p, p' \in {\mathbb P}_1$ , and assume that $p \prec p'$ (the other case can be handled in a similar manner). Since $\iota _{\hookleftarrow }^D$ is induced by the projection $\pi _1 : {\mathbb P} \twoheadrightarrow {\mathbb P}_1$ , it suffices to show that $\pi ^{-1}(p) \prec ^{\mathrm {alex}} \pi ^{-1}(p')$ . Now, it is easy to see that, in fact, $\pi ^{-1}(p) \prec \pi ^{-1}(p')$ by the construction of $\prec $ .

Corollary 3.3. $\mathrm {Aut}(L)$ is not amenable.

Proof We will make use of the following proposition:

Proposition [11, Proposition 2.2]

Let $\mathcal C$ be a Fraïssé class and $\mathcal C^*$ a Fraïssé order expansion of $\mathcal C$ that is reasonable and has the ordering property. Moreover, suppose that there are $A, B \in \mathcal C$ and an embedding $\iota _< : A \to B$ for each admissible ordering $<$ on A with the following properties $:$

1. (i) There is an admissible ordering $<'$ on B such that for every admissible ordering $<$ on A, the function $\iota _<$ does not embed $(A, <)$ into $(B, <');$

2. (ii) For any two distinct admissible orderings $<_1$ , $<_2$ on A, there exists an admissible ordering $<'$ on B such that at least one of $\iota _{<_1}$ and $\iota _{<_2}$ fails to embed $(A, <_1)$ or $(A, <_2)$ , respectively, into $(B, <')$ .

Then, the automorphism of the Fraïssé limit of $\mathcal C$ is not amenable.

Consider the following construction appearing in [10, Remark 3.1]. Let A be the finite Boolean algebra with the atoms a and b and B with x, y, and z. For the order $<_1$ which extends $a <_1 b$ , define

$$ \begin{align*} \pi_{<_1}(a) := x,&& \pi_{<_2}(b) := y \vee z. \end{align*} $$

Moreover, for the order $<_2$ which extends $b <_2 a$ ,

$$ \begin{align*} \pi_{<_2}(a) := y, && \pi_{<_2}(b) := x \vee z. \end{align*} $$

Let $<'$ be defined as extending $z <' y <' x$ . The objects defined above witness the conditions (i) and (ii). We conclude that $\mathrm {Aut}(L)$ is not amenable.

Finally, we study the aspects of the combinatorics of $\mathrm {Age}(L)$ pertaining to the extreme amenability of $\mathrm {Aut}(L)$ . The Kechris–Pestov–Todorčević correspondence concerns order expansions of the ages of ultrahomogeneous structures with the ordering property [10]. One can make an empirical observation that many arguments establishing the ordering property of an order expansion of a Fraïssé class fall into two categories: one based on a lower-dimensional Ramsey property and the other rather trivially using the order-forgetfulness of the expansion. The former is applied to many classes of relational structures such as graphs, whereas the latter is used with the countable atomless Boolean algebras and the infinite-dimensional vector space over a finite field. Our structure L is similar to the latter classes of structures. However, we see the following.

Proposition 3.4. There is no Fraïssé order class of isomorphism types that expands the class of finite Heyting algebras and is order-forgetful.

Proof Suppose that such a class $\mathcal K^*$ exists. Let H be an arbitrary finite Heyting algebra, and consider the action of $\mathrm {Aut}(H)$ on the set of binary relations on H. Since $\mathcal K^*$ is closed under isomorphism types, the set of admissible orderings $A_H$ on H is a union of orbits. Since $\mathcal K^*$ is order-forgetful, $A_H$ consists of a single orbit.

Now consider the poset ${\mathbb P}'$ that is the disjoint union of two 2-chains, with its quotient ${\mathbb P}$ obtained by collapsing one of the 2-chains into a point. The canonical surjection ${\mathbb P}' \twoheadrightarrow {\mathbb P}$ is p-morphic, which induces a Heyting algebra embedding $H \hookrightarrow H'$ . Let $a, b \in H'$ correspond to the two 2-chains. Clearly, H is rigid whereas there is an automorphism $\phi : H' \to H'$ under which a and b are conjugates. Consider an admissible ordering $\prec $ on $H'$ ; without loss of generality, we may assume $a \prec b$ . Writing the action of $\mathrm {Aut}(H')$ by superscripts, we have $b \prec ^\phi a$ . Since $\mathcal K^*$ is a Fraïssé class, the restrictions of $\prec $ and $\prec ^\phi $ to H, respectively, are admissible orderings on H. Now, we have $\mathord {\prec } \cap H^2 \neq \mathord {\prec ^\phi } \cap H^2$ , as witnessed by $(a,b)\in H^2$ . These cannot belong to the same orbit of $A_H$ as H is rigid.

From this point on, we study $\mathrm {Aut}(L)$ as an abstract group, and show that it is simple. Our argument is based on the technique by Tent and Ziegler [16]. Our ternary relations are reminiscent of the stationary independence relation on the random poset defined in [3], but note that our setting is different as our language is algebraic.

Lemma 3.5. If M is a countable ultrahomogeneous structure with $\mathrm {Age}(M)$ having the superamalgamation property, then M has an automorphism $g : M \to M$ that moves almost maximally with respect to in the sense of Tent and Ziegler [16, Lemma 5.3].

Proof A back-and-forth construction. Enumerate M as $(a_i)_{i<\omega }$ and all the realized 1-types over all finite subsets of M as $(p_i)_{i < \omega }$ . We construct g as the union of the chain $\emptyset = g_0 \subseteq g_1 \subseteq \cdots $ , each of which is a partial isomorphism with a finite domain. Along the way, we construct a chain $\emptyset = S_0 \subseteq S_1 \subseteq \cdots $ of realized 1-types. Suppose that $g_j$ has been constructed. To construct $g_{j+1}$ , one does the following:

If $j = 3i$ . If $a_i$ is in $\operatorname {\mathrm {dom}} g_j$ , then $g_{j+1} := g_j$ . Otherwise, let $g_{j+1}$ extend $g_j$ so $g_{j+1}(a_i)$ may be a realization of $g_j(p)$ outside $\operatorname {\mathrm {ran}} g_j$ , which exists due to the strong amalgamation, where p is the type of $a_i$ over $\operatorname {\mathrm {dom}} g_j$ .

If $j = 3i+1$ . Similar as above, but switch the roles of images and domains.

If $j = 3i+2$ . Let k be the least such that $p_k$ is over X, that $X \subseteq \operatorname {\mathrm {dom}} g_j$ , and that $p_k \not \in S_i$ . (There may not be such k, in which case $g_{j+1} := g_j$ and $S_{i+1} := S_i$ , but there will be such k for infinitely many i because of the other two kinds of stages.) Let $S_{i+1} := S_i \cup \{p_k\}$ . If all realizers of $p_k$ are in $\operatorname {\mathrm {dom}} g_j$ , then $g_{j+1} := g_j$ . If not, apply the strong amalgamation to obtain infinitely many realizers of $p_k$ . Since $\operatorname {\mathrm {dom}} g_j$ is finite, there exists $ a \models p_k$ outside $\operatorname {\mathrm {dom}} g_j$ . Let D be the diagram $\langle aXg_j(X) \rangle \hookleftarrow {\langle Xg_j(X) \rangle } \hookrightarrow \langle aXg_j(X) \rangle $ , and let the diagram $\langle aXg_j(X) \rangle \stackrel {\text {incl.}}{\hookrightarrow } A \stackrel {\iota }{\hookleftarrow } \langle aXg_j(X) \rangle $ , where $A \subseteq M$ , witness the superamalgamation property for D. Now let $g_{j+1} := g_j \cup \{(a, \iota (a))\}$ . (Replace $\iota (a')$ by something else if need be so $\iota (a') \not \in \operatorname {\mathrm {ran}} g_j$ by considering an amalgam with more copies of $\langle aXg_j(X) \rangle $ .) By the superamalgamation property, we have .

For the next theorem, recall that structures $M_1$ and $M_2$ sharing the same domain M but of possibly different languages are definitionally equivalent if subsets of $M^n$ are $0$ -definable in $M_1$ if and only if it is $0$ -definable in $M_2$ for every $n < \omega $ .

Theorem 3.6. Let M be a countable ultrahomogeneous structure with $\mathrm {Age}(M)$ having the superamalgamation property with respect to a $0$ -definable partial order $\le $ on M. Moreover, suppose that M and $M \upharpoonright L_0$ are definitionally equivalent, where $L_0$ is a language containing $\le $ and finitely many constants naming elements of M. Then there exists $g \in \mathrm {Aut}(M)$ such that every element of $\mathrm {Aut}(M)$ is the product of at most 16 conjugates of g. A fortiori, the abstract group $\mathrm {Aut}(M)$ is simple.

Proof By the superamalgamation property of $\mathrm {Age}(M)$ , one can prove that the relation is a stationary independence relation in the sense of Tent and Ziegler [16]. In fact, the invariance of follows from the ultrahomogeneity of M. The monotonicity and the symmetry of are obvious by the shape of the definition of . To show transitivity, assume that and that . To see , take an arbitrary $a \in A$ and $d \in D$ . Suppose $a \le d$ . (The case of $d \le a$ can be handled in a similar way.) Since , there is $b \in BC$ such that $a \le b \le d$ . If $b \in B$ , we are done. Otherwise, $b \in C$ , so by , there is $b' \in B$ such that $a \le b' \le b$ . Now we have $a \le b' \le d$ . To show the existence property of , let p be a realized type over a finite set B and C a finite set. Let $\overline a$ be a tuple realizing p. Now consider the diagram D:

$$\begin{align*}\langle \overline a B\rangle \hookleftarrow \langle B \rangle \hookrightarrow \langle BC \rangle. \end{align*}$$

Let the diagram $\langle \overline a B\rangle \stackrel {\iota }{\hookrightarrow } A \stackrel {\text {incl.}}{\hookleftarrow } \langle BC \rangle $ , where $A \subseteq M$ , witness the superamalgamation property for D. It is clear that . Finally, to show the stationarity of , we may assume the original signature M is $L_0$ without loss of generality. Take two realizations $a, a' \models p$ where p is over a finite set A. We may further assume that A contains all constants in $L_0$ without loss of generality. Consider an arbitrary finite set $A' \supseteq A$ such that . The order types of $aA'$ and $a'A'$ , respectively, are determined by the order types of $aA$ , $a'A$ , and $A'$ . By the hypothesis $\mathrm {Aut}(M) = \mathrm {Aut}(M \upharpoonright L_0)$ , the first-order types of $aA'$ and $a' A'$ are determined by the order types of $aA$ , $a'A$ , and $A'$ . We conclude that $\mathrm {tp}^M(a/A') = \mathrm {tp}^M(a'/A')$ . Therefore, for g constructed in the preceding lemma, every element of $\mathrm {Aut}(M)$ is the product of 16 conjugates of g by Corollary 5.4 of [16].

Corollary 3.7. There is $g \in \mathrm {Aut}(L)$ such that every element of $\mathrm {Aut}(L)$ is the product of at most 16 conjugates of g. In particular, $\mathrm {Aut}(L)$ is simple.

By the result by Maksimova, our argument shows the simplicity of the automorphism group of the Fraïssé limit of all finite members of each of the seven nontrivial subvarieties of Heyting algebras with the (super-)amalgamation property.