Are there finitely many sieves on each object in the distributive lattice cube category?

Question

Define the distributive lattice cube category or Dedekind cube category $\square_{\land\lor}$ to be the full subcategory of the category of posets and monotone maps consisting of objects of the form $[1]^n \triangleq \{0 < 1\}^n$ for $n \ge 0$. Morphisms $[1]^m \to [1]^n$ in this category correspond to $n$-tuples of terms in $m$ variables in the theory of bounded distributive lattices, hence the name. (In terms of generators, every morphism can be written as a composite of face maps, degeneracies, permutations, diagonals, and min- and max-connections─this fact appears on the logical side as the disjunctive/conjunctive normal form presentations.)

The presheaf category $\mathrm{PSh}(\square_{\land\lor})$ is then one of many variations on "cubical sets". I'd like to know whether the following finiteness property is satisfied by the representable cubes in this category:

Question: In the presheaf category $\mathrm{PSh}(\square_{\land\lor})$, does every representable object have finitely many subobjects up to isomorphism? Equivalently, are there finitely many sieves on every object of $\square_{\land\lor}$?

In general, say that a category $\mathcal{C}$ has the finite sieve property if there are finitely many sieves on each object of $\mathcal{C}$. Recall that a sieve on an object $A$ in category $\mathcal{C}$ is a set $\mathcal{S}$ of arrows into $A$ such that if $g : B \to A$ is in $\mathcal{S}$ and $f : C \to B$ is an arbitrary arrow, then $g \circ f$ is in $\mathcal{S}$. To show that the set of sieves on some $A$ is finite, it suffices to show there are finitely many principal sieves, that is, sieves of the form $\langle g \rangle \triangleq \{g \circ f \mid f : C \to B\}$ for some $g : B \to A$. Using this and some specifics of $\square_{\land\lor}$, we can thus give the following more concrete reformulations:

Equivalent Question: Fix $k \ge 0$. Does there exist $\ell \ge 0$ such that every $f : [1]^n \to [1]^k$ generates the same principal sieve as some $f' : [1]^\ell \to [1]^k$?

Equivalent Question 2: Fix $k \ge 0$. Does there exist $\ell \ge 0$ such that for every $f : [1]^n \to [1]^k$, there are maps $[1]^n \overset{g}\to [1]^\ell \overset{h}\to [1]^n$ with $f \circ h \circ g = f$? (If this is so, then $\langle f \rangle = \langle f \circ h \rangle$.)

I'm interested in this cube category because of its relevance to modelling cubical type theories. In work with Christian Sattler we're in the process of writing up, we've found that finite product categories with the finite sieve property can be embedded in generalized Reedy categories in a useful way. We used this to characterize a certain model structure on $\square_\lor$ (the subcategory with just one connection, see remarks below), but don't know if any of the arguments apply with $\square_{\land\lor}$.

---

Some partial and related answers

The remainder of this post just collects special cases and related results that might or might not be helpful.

Remark: Any Eilenberg-Zilber category $\mathcal{C}$ in which there are finitely many face maps into any object has the finite sieve property.

Proof: Any $f : B \to A$ generates the same sieve as the degree-raising map of its Reedy factorization, as the degree-lowering map is a split epimorphism. $\blacksquare$

In particular, the simplex category and cartesian cube category (the wide subcategory of $\square_{\land\lor}$ generated by face maps, degeneracies, permutations, and diagonals) have the finite sieve property. If we add one connection to the latter, we get a category that is not generalized Reedy but still has the finite sieve property.

Proposition: The wide subcategory $\square_\lor$ of $\square_{\land\lor}$ consisting of maps generated by face maps, degeneracies, permutations, diagonals, and the max-connection $\lor$ has the finite sieve property. (Note: this is equivalently the wide subcategory of join-preserving maps.)

Proof: Let $f : [1]^n \to [1]^k$. Such a morphism corresponds to a tuple of $k$ terms in $n$ variables in the theory of bounded join-semilattices. We can assume without loss of generality that no component $f_j : [1]^n \to [1]$ for $1 \le j \le k$ is constant $1$. Then for each $f_j$, we have a normal form $f_j(x_1,\ldots,x_n) = \bigvee S_j$ for some $S_j \subseteq \{x_1,\ldots,x_n\}$. For $1 \le i \le n$, define $T_i = \{j \mid x_i \in S_j\} \subseteq \{1,\ldots,k\}$. If $n > 2^k$, then we must have $T_i = T_{i'}$ for some $i,i'$. Without loss of generality, say $T_1 = T_2$. Then $x_1$ and $x_2$ appear as disjuncts in the same components, so we have $f \circ d \circ c = f$ where $c : [1]^n \to [1]^{n-1}$ maps $(x_1,\ldots,x_n) \mapsto (x_1 \lor x_2, x_3, \ldots, x_n)$ and $d : [1]^{n-1} \to [1]^n$ maps $(y_1,\ldots,y_{n-1}) \mapsto (y_1,y_1,y_2, \ldots, y_{n-1})$. Thus $\langle f \rangle = \langle f \circ d \rangle$. By repeatedly reducing in this way, we find that $\langle f \rangle = \langle f' \rangle$ for some $f' : [1]^{2^k} \to [1]^k$. $\blacksquare$

Lemma: The finite sieve property holds for the objects $[1]^k$ with $k \le 2$ in $\square_{\land\lor}$.

Proof: The $k = 0$ case is obvious. For $k = 1$, any $f : [1]^n \to [1]$ is either constant $0$, constant $1$, or (we can see from the disjunctive normal form) satisfies $f \circ \Delta \circ f = f$ where $\Delta : [1] \to [1]^n$ is the diagonal $x \mapsto (x,\ldots,x)$.

Now $k = 2$, a bit sketchily. Suppose we have $f : [1]^n \to [1]^2$ and neither component is constant $0$ or $1$ (in which case we could reduce to the $k = 1$ case). We can write each component in disjunctive normal form, $f_j(x_1,\ldots,x_n) = \bigvee_{i \in I_j} \bigwedge C^j_i$ where $I_j$ is nonempty and each $C^j_i$ is a nonempty set of variables. If there exists some $C^1_i$ which is not a superset of any $C^2_{i'}$, choose one and call this $K_1$; otherwise choose an arbitrary $C^1_i$ to be $K_1$. (Note that in the latter case $f_1 \le f_2$.) Likewise, choose $K_2$ among the $C^2_i$ which is not a superset of any $C^1_{i'}$ if possible. Define $g : [1]^2 \to [1]^n$ by $$ g(u_1,u_2)_i \triangleq \bigvee \{u_j \mid x_i \in K_j \} $$ Then $f \circ g \circ f = f$. $\blacksquare$

In the $k \le 2$ case, we always get $f \circ g \circ f = f$ for some $g$. But this does not happen in general, as demonstrated by the following lower bound:

Proposition: For any $k \ge 1$, there exists some $f : [1]^n \to [1]^k$ such that $\langle f \rangle \neq \langle g \rangle$ for every $g : [1]^\ell \to [1]^k$ with ${\ell \choose {\lfloor \ell/2 \rfloor}} < 2^{k-1}$.

Proof: For any $v \in [1]^k$, write $\#_v \in [1]^{\lvert [1]^k \rvert}$ for the vector taking value $1$ in all coordinates except the $v$th. We define a monotone map $f : [1]^{\lvert [1]^k \rvert} \to [1]^k$. $$ \begin{align*} f(\top) &\triangleq \top \\ f(\#_v) &\triangleq v \\ f(\_) &\triangleq \bot &\text{otherwise} \end{align*} $$ Suppose we have $\langle f \rangle = \langle g \rangle$ for some $g : [1]^\ell \to [1]^k$, so there exist $h : [1]^n \to [1]^\ell$ and $t : [1]^\ell \to [1]^n$ with $f \circ t \circ h = f$ (and $g = f \circ t$). Then because $f^{-1}(v) = \{\#_v\}$ for $v \in [1]^k\setminus\{\bot,\top\}$, we must have $(t \circ h)(\#_v) = \#_v$ for these $v$. As $\#_v$ and $\#_w$ are incomparable for $v \neq w$, so must be $h(\#_v)$ and $h(\#_w)$. Thus $[1]^\ell$ must contain a set of at least $\lvert [1]^k\setminus\{\bot,\top\} \rvert = 2^{k-1}$ pairwise-incomparable vectors. The maximal antichain in $[1]^\ell$ has ${\ell \choose {\lfloor \ell/2 \rfloor}}$ elements, so ${\ell \choose {\lfloor \ell/2 \rfloor}} \ge 2^{k-1}$. $\blacksquare$

In particular, there is a principal sieve on $[1]^3$ not generated by any $f : [1]^3 \to [1]^3$.

Answer 1

$\newcommand{\Pos}{\mathbf{Pos}}$ $\square_{\land\lor}$ does not have the finite sieve property. The following paper provided the key lemma:

Imrich, Wilfried; Kalinowski, Rafał; Lehner, Florian; Pilśniak, Monika, Endomorphism breaking in graphs, Electron. J. Comb. 21, No. 1, Research Paper P1.16, 13 p. (2014). ZBL1300.05100.

Write $C_n$ for the cycle graph on vertices $\{0,\ldots,n-1\}$. We can regard $C_{2n}$ as a bipartite graph, with the even numbers in one part and the odd numbers in the other, and thereby as a poset with $i < j$ iff $i$ is even, $j$ is odd, and $i-j = \pm 1 \bmod 2n$.

From the paper above, I just want the following (simple) fact, which is in their proof of Lemma 2.

Proposition 1. For any $n \ge 3$, there exists a 2-coloring of $C_{2n}$ such that the only color-preserving graph endomorphism of $C_{2n}$ is the identity function.

Corollary 2. For any $n \ge 3$, there exists a poset map $f_n \colon C_{2n} \to C_4$ such that the only endomorphism of $f_n \in \Pos/C_4$ is the identity function.

Proof. Choose a 2-coloring $c \colon C_{2n} \to \{0,1\}$ as in the proposition. Define $f \colon C_{2n} \to C_4$ by $f(i) \triangleq 2c(i) + i \mathbin{\%} 2$.

We have an embedding of posets $\iota \colon C_4 \hookrightarrow [1]^4$ defined as follows. \begin{align*} 0 &\mapsto 0001 & 1 &\mapsto 0111 \\ 2 &\mapsto 0010 & 3 &\mapsto 1011 \end{align*} Given $i \in \mathbb{N}$, write $\chi_i \in [1]^n$ for the element with $1$ at index $i \bmod n$ and $0$ elsewhere. For any $n \ge 3$, we have a poset embedding $z_n \colon C_{2n} \hookrightarrow [1]^n$ defined as follows. \begin{align*} z_n(i) &\triangleq \left\{ \begin{array}{ll} \chi_{i/2} &\text{if $i$ is even} \\ \chi_{\lfloor i/2 \rfloor} \vee \chi_{\lceil i/2 \rceil} &\text{if $i$ is odd} \end{array} \right. \end{align*} For each $n \ge 3$, we define a monotone map $g_n \colon [1]^n \to [1]^4$ by cases as follows. \begin{align*} g_n(v) &\triangleq \left\{ \begin{array}{ll} \iota(f_n(i)), &\text{if $\exists i \in C_{2n}.\ v = z_n(i)$} \\ \bot, &\text{if $v = \bot$} \\ \top, &\text{otherwise} \end{array} \right. \end{align*} By construction, we have $g_n \circ z_n = \iota \circ f_n$ as well as $g_n^{-1}(\iota(C_4)) = z_n(C_{2n})$.

Now, suppose we are given an endomorphism $h : g_n \to g_n$ in $\Pos/[1]^4$. Because $h(z_n(C_{2n})) = h(g_n^{-1}(\iota(C_4))) \subseteq g_n^{-1}(\iota(C_4)) = z_n(C_{2n})$, there is a restriction $h \upharpoonright z_n : C_{2n} \to C_{2n}$ fitting into the following commuting diagram in $\Pos$. $\require{AMScd}$ \begin{CD} C_{2n} @>{h \upharpoonright z_n}>> C_{2n} \\ @V{z_n}VV @V{z_n}VV \\ {[1]^n} @>h>> {[1]^n} \\ @V{g_n}VV @V{g_n}VV \\ {[1]^4} @= {[1]^4} \end{CD}

It follows that we have $h \upharpoonright z_n \colon f_n \to f_n$ in $\Pos/C_4$, thus that $h \upharpoonright z_n = \mathrm{id}$. Thus the image of any such $h \colon g_n \to g_n$ has cardinality at least $2n$; if $h$ factors through some $[1]^\ell$, we must therefore have $\ell \ge \log_2 n + 1$.

Answer 2

Sorry, the following is nonsense -- there's no reason that $\phi$ should be a poset map. I'll leave it up for now because I hope it's at least correct in showing that if you can find such a $Q$, then the result will follow.

---

Here is a proof that the Dedekind cube category has the finite sieve property. The dependence on the Robertson-Seymour theorem makes the proof extremely ineffective. Perhaps that reliance can be eliminated, though -- it's only invoked for graphs which are equivalence relations, and surely that statement is much easier to prove!

Of course, caveat lector: there is ample possibility that I have made a mistake in the following!

Let $P \subseteq \square^k$ be a sub-poset, and let $S$ be an infinite set of morphisms from cubes $\square^n$ to $\square^k$ with image $P$. Suppose that each morphism in $S$ generates a distinct sieve on $\square^k$. Let us derive a contradiction.

For each $s : \square^n \twoheadrightarrow P$ in $S$, let $E_s \rightrightarrows \square^n$ be the kernel pair in $Set$ -- an equivalence relation on the points of $\square^n$. We may regard these equivalence relations as finite reflexive graphs.

By the Robertson-Seymour theorem, there are distinct $s : \square^m \twoheadrightarrow P$, $t : \square^n \twoheadrightarrow P$ in $S$ such that $E_s$ is a graph minor of $E_t$. So there is an induced subgraph $E \subseteq E_t$ and a map $E_t \twoheadrightarrow E_s$ which is obtained by successively contracting edges. Let $Q$ be the vertex set of $E$, and regard $P$ as an induced subposet of $\square^n$. Let $q : Q \to Q' = Q/E$ be the quotient. We have a commutative diagram of posets:

$\require{AMScd} \begin{CD} \square^m @<\phi<< Q @>\iota>> \square^n \\ @VsVV @VVqV @VVtV \\ P @<<< Q' @>>> P \end{CD}$

Here the vertical maps are quotients, the leftward maps are surjections, and the rightward maps are injections. Because $P$ is finite, it follows that $Q' = P$ and the maps on the bottom are identities. We will show that $\langle s \rangle = \langle t \rangle$, contradicting the hypothesis that each element of $S$ generates a distinct sieve.

Let $y_Q : Q \to I(Q)$ be the inclusion into the lattice of downward-closed sets (the $[1]$-enriched Yoneda embedding). Then the left Kan extension $\lambda$ of $\phi: Q \to \square^m$ is a surjective semilattice map $I(Q) \to \square^m$. Because $\square^m$ is a projective semilattice, this map splits via a section $j$. We construct the following commutative diagram, where $\pi$ is the left adjoint of the Yoneda embedding $y_n : \square^n \to I(\square^n)$.

$\require{AMScd} \begin{CD} \square^m @>j>> I(Q) @>I(\iota)>> I(\square^n) @>=>> I(\square^n) \\ @V=VV @A{y_Q}AA @A{y_n}AA @V{\pi}VV \\ \square^m @<\phi<< Q @>\iota>> \square^n @>=>> \square^n \\ @VsVV @VVqV @VVtV @VVtV \\ P @<=<< P @>=>> P @>=>> P \end{CD}$

The thing I'm having trouble drawing is the map $\lambda$, which should split the top-left square diagonally from top-right to bottom-left.

Let $q' = t\pi I(\iota) : I(Q) \to P$. Since $I(Q)$ is a finite distributive lattice, it is an object of $\square_{\vee,\wedge}$ (up to idempotent completion), so that $q'$ generates a principal sieve on $\square^k$. We have $s = q' y_Q \phi$ and $q' = s j$, so that $\langle s \rangle = \langle q' \rangle$. And from the definition of $q'$ we clearly have $\langle q' \rangle \subseteq \langle t \rangle$. Together, we have $\langle s \rangle \subseteq \langle t \rangle$, so it remains to show the reverse inclusion holds.

We also have $t = t\pi y_n$, so that $\langle t \rangle = \langle t\pi \rangle$. So it will suffice to show that $\langle t\pi \rangle \subseteq \langle q' \rangle$

Now because $\iota$ is a poset embedding, so is $I(\iota)$. Because $I(Q)$ is a lattice and hence injective with respect to poset embeddings, $I(\iota)$ has a section $\chi$. We have $q' \chi = t \pi I(\iota) \chi$, so that $\langle q' \rangle \subseteq \langle t \rangle$ as desired.