11
$\begingroup$

I've noticed that for every natural number $n\in\mathbb{N}$, there is a finite Heyting algebra with cardinality $C(n)$, where $C(n)$ is the $n$th Catalan number, $$1,1,2,5,14,42,132,\ldots$$ I'm looking for a reference, if this fact is known (to be known).

Below I will explain where the Heyting algebra structure comes from, in case it helps. When $n=0$ or $n=1$, we have $C(n)=1$, and there is a unique Heyting algebra structure on a set with one element, so suppose $n\geq 2$.

For any $m\in\mathbb{N}$, let $[m]:=\{0,1,\ldots,m\}$ and for any $0\leq a\leq b\leq m$, write $[a,b]$ for the subinterval $\{a,a+1,\ldots,b\}\subseteq[m]$. These subintervals form a poset, which we consider as a topological space with the Alexandrov topology: points are subintervals $[a,b]$ and open sets are down-closed subsets. Write $\Omega[m]$ for the poset of open sets in this space, so it has the structure of a Heyting algebra. It remains to show that the cardinality of $\Omega[m]$ is $C(m+2)$.

It is well-known that the Catalan number $C(n)$ counts the Dyck paths of length $2n$. These are paths in a triangle of dots (see below for $n=5$), starting at the southwest point, ending at the northeast point, where each edge in the path moves one unit either northward or eastward.

Position the elments of $[m]$ in the $(m+2)$-triangle, as shown here in the case $m=3$: $$ \begin{array}{ccccccccccc} \bullet&&\bullet&&\bullet&&\bullet&&\bullet&&\bullet\\ &&&&&&&3\\ \bullet&&\bullet&&\bullet&&\bullet&&\bullet\\ &&&&&2\\ \bullet&&\bullet&&\bullet&&\bullet\\ &&&1\\ \bullet&&\bullet&&\bullet\\ &0\\ \bullet&&\bullet\\ \\ \bullet\\\\ \end{array} $$ In this setup, a Dyck path $p$ of length $m+2$ can be identified with a downclosed subset, $S(p)\in\Omega[m]$. For example, the Dyck path $p_0$ shown below $$ \begin{array}{ccccccccccc} \bullet&&\bullet&&\bullet&&\bullet&-&\bullet&-&\bullet\\ &&&&&&|&3\\ \bullet&&\bullet&-&\bullet&-&\bullet&&\bullet\\ &&|&&&2\\ \bullet&&\bullet&&\bullet&&\bullet\\ &&|&1\\ \bullet&&\bullet&&\bullet\\ &0&|\\ \bullet&-&\bullet\\ |\\ \bullet\\\\ \end{array} $$ represents the set $S(p_0)=\mathord{\downarrow}[1,2]\cup\mathord{\downarrow}[3]$.

In fact, all these Heyting algebras $\Omega[m]$ fit together in a single topos, as we now explain. Consider the additive monoid of natural numbers as a category $BN$ with one object. Let $\mathbf{Int}:=\mathrm{Tw}(BN)$ be the twisted arrow category, and consider the presheaf topos $\mathrm{Psh}(\mathbf{Int})$. The subobject classifier for this topos is a functor $$\Omega'\colon\mathbf{Int}^\mathrm{op}\to\mathbf{Set}.$$ so for each object $n\in\mathbb{N}=\mathrm{Ob}(\mathbf{Int})$, we have a set $\Omega'(n)$. Moreover this set carries the structure of a Heyting algebra. Finally, $\Omega'(n)$ has a well-known description in terms of sieves, i.e. subfunctors of the representable functor $\mathbf{Int}(-,n)$. Unwrapping the definition, these are exactly the open sets of $[n]$. In other words, we have a bijection $\Omega'(n)\cong\Omega[n]$.

$\endgroup$
  • $\begingroup$ Interesting! Aren't presheaves over $\mathbf{Int}$ something like set-theoretical operads? (They supposedly correspond to sequences $\left(S_0, S_1, S_2, \ldots\right)$ equipped with a map $S_n \to S_m$ for any quadruple $\left(a,n,b,m\right) \in \mathbb{N}^4$ satisfying $a+n+b=m$.) That said, there is no guarantee I haven't gotten the directions of the arrows wrong, nor that the axioms are the right ones... $\endgroup$ – darij grinberg Jun 17 '17 at 17:17
  • 1
    $\begingroup$ I don't see how these are sufficient to provide an operad structure. You need, for any $n,k_1,\ldots,k_n$ a function $$S_n\times S_{k_1}\times\cdots\times S_{k_n}\longrightarrow S_K$$ where $K=k_1+\cdots+k_n$. $\endgroup$ – David Spivak Jun 17 '17 at 18:10
  • $\begingroup$ Does anyone know how "Dyck" is supposed to be pronounced? For example, does it rhyme with "Rick" or "Like" or "Meek"? $\endgroup$ – David Spivak Jun 17 '17 at 18:13
  • 1
    $\begingroup$ It rhymes with "Rick" (at least this is how every mathematician I have encountered pronounces the name). $\endgroup$ – Sam Hopkins Jun 17 '17 at 18:16
  • $\begingroup$ @DavidSpivak: There are several equivalent ("cryptomorphic") definitions of operads. The one you cite tells you how to "graft many little trees onto one tree simultaneously" (a.k.a. how to "substitute" the values of some "functions" for the "arguments" of another "function"). But this is, in a sense, wasteful: It suffices to tell how to "graft one little tree into a tree" (a.k.a. how to "substitute" a value of a "function" for one of the "arguments" of another function). See, e.g., §2.1 of Benoit Fresse's ... $\endgroup$ – darij grinberg Jun 17 '17 at 18:44
6
$\begingroup$

I found a reference: "Dyck algebras, interval temporal logic and posets of intervals", which discusses these Heyting algebras (though not from a topos-theoretic perspective).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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