11
$\begingroup$

Let $\mathscr{C}_n$ be the lattice of clones on the $n$-element set $\{1,...,n\}$. $\mathscr{C}_2$ is complicated but countable, but $\mathscr{C}_3$ (and all higher lattices) is of size continuum.

Question: Does $\mathscr{C}_4$ embed as a lattice into $\mathscr{C}_3$?

More generally, do we know the status of any of the embeddability questions $\mathscr{C}_m\hookrightarrow\mathscr{C}_n$ for $m>n>2$? My suspicion is that $\mathscr{C}_3$ is already "wild" enough that every $\mathscr{C}_m$ embeds into it, and that the specific $4/3$ case above will be the easiest to address.


At MSE I asked a harder version of this question, but per Keith Kearnes' answer there it seems that even this weaker question may be tricky (or even open).

$\endgroup$
2
  • $\begingroup$ Is it possible that $\mathcal C_3$ has some weak universality property, where every continuum-sized lattice embeds into it? Or are there known obstructions? $\endgroup$
    – Wojowu
    Commented Jul 8, 2023 at 17:55
  • $\begingroup$ @Wojowu That was my expectation actually, which is why at MSE I originally asked about a stronger notion of embedding. But I at least don't know of such a result. $\endgroup$ Commented Jul 8, 2023 at 17:56

1 Answer 1

8
+200
$\begingroup$

This is not an answer, but a long comment. I want to post references that are relevant to a question raised in the comments, namely

  • (Wojowu) Is it possible that $\mathscr{C}_3$ has some weak universality property, where every continuum-sized lattice embeds into it?

    The answer to this is No. Let $M_{\omega}$ be the countably infinite modular lattice of height two. This is the lattice obtained from a countably infinite antichain by adding a new top element and a new bottom element. It is proved in

    Bulatov, Andrei A.
    Conditions satisfied by clone lattices.
    Algebra Universalis 46 (2001), no. 1-2, 237-241.

    that the countable lattice $M_{\omega}$ is not embeddable in $\mathscr{C}_n$ for any finite $n$ (Corollary 1.3). This is proved by showing that clone lattices on finite sets satisfy two, dual, weak semidistributivity properties called $(\omega$-$\textrm{SD}_\wedge)$ and $(\omega$-$\textrm{SD}_\vee)$. I will write the statement of $(\omega$-$\textrm{SD}_\wedge)$.

    $(\omega$-$\textrm{SD}_\wedge)$: given $\omega$-many elements $x_0, x_1, x_2, \ldots$ such that $x_i\wedge x_j=x_k\wedge x_{\ell}$ for every $i\neq j, k\neq \ell$, it is the case that $x_0 = \bigwedge_{0<i<\omega} (x_0\vee x_i)$.

    Bulatov proves that the clone lattice on any finite set satisfies the universally quantified sentences $(\omega$-$\textrm{SD}_\wedge)$ and $(\omega$-$\textrm{SD}_\vee)$. Any lattice containing $M_{\omega}$ as a sublattice will not satisfy these sentences, so $M_{\omega}$ is not embeddable in $\mathscr{C}_n$ for any finite $n$.

    Clone lattices on infinite sets do not have to satisfy $(\omega$-$\textrm{SD}_\wedge)$ and $(\omega$-$\textrm{SD}_\vee)$, and in fact $M_{\omega}$ IS embeddable in the clone lattice on any infinite set. To see this, I slightly paraphrase Theorem 1 of

    Pinsker, Michael
    Algebraic lattices are complete sublattices of the clone lattice over an infinite set.
    Fund. Math. 195 (2007), no. 1, 1-10.

    Theorem 1.
    Let $X$ be an infinite set. Every algebraic lattice with at most $2^{|X|}$ compact elements can be completely embedded into the clone lattice on $X$.

  • $\endgroup$

    You must log in to answer this question.

    Not the answer you're looking for? Browse other questions tagged .