Skip to main content
"quine" seems more evocative of the idea
Source Link
David Spivak
  • 8.7k
  • 1
  • 28
  • 64

Can a non-free monad have non-trivial "self-descriptor""quine"?

Let $\mathbf{Poly}$ denote the category of polynomial functors on $\mathbf{Set}$, and let $\mathfrak{m}\colon\mathbf{Poly}\to\mathbf{Poly}$ be the free monad monad, i.e. the functor that sends every polynomial $p$ to the free monad $(\mathfrak{m}_p,\eta,\mu)$, $$ \mathfrak{m}_p\colon\mathbf{Set}\to\mathbf{Set} \qquad \eta_p\colon\text{id}_\mathbf{Set}\to \mathfrak{m}_p \qquad \mu_p\colon \mathfrak{m}_p\circ \mathfrak{m}_p\to \mathfrak{m}_p $$ on $p$. One can think of the underlying functor $\mathfrak{m}_p$ as the coproduct over all $p$-syntax trees of the functor represented by the leaves.

Let $(t,\eta,\mu)$ denote an arbitrary polynomial monad on $\mathbf{Set}$. This means $t$ comes equipped with an algebra structure $\alpha\colon\mathfrak{m}_t\to t$ satisfying a unit law $\alpha\circ\eta_t=\text{id}_t$ and a similar composition law. We define a self-descriptorquine transformation of $t$ to be a section $$ \beta\colon t\to\mathfrak{m}_t$$ of the algebra map, i.e.\ a natural transformation with $\alpha\circ\beta=\mathrm{id}_t$. We say that the self-descriptorquine transformation $\beta$ is trivial if $\beta=\eta_t$, and we say it is nontrivial if $\beta\neq\eta_t$.

Note that a free monad $\mathfrak{m}_p$ always has a nontrivial self-descriptorquine transformation, namely $$ \mathfrak{m}_p\xrightarrow{\mathfrak{m}_{\eta_{\,p}}}\mathfrak{m}_{\mathfrak{m}_p} $$ which is indeed nontrivial because $\mathfrak{m}_{\eta_p}\neq\eta_{\mathfrak{m}_p}$.

Question: If a polynomial monad $t$ on $\mathbf{Set}$ has a non-trivial self-descriptorquine transformation, does that imply that $t$ is free, $t=^?\mathfrak{m}_p$ on some polynomial $p$? Or, instead, does there exist a non-free monad that has a non-trivial self-descriptorquine?

(Note: some people restrict polynomial monads to be the Cartesian ones, i.e. those for which $\eta_t$ and $\mu_t$ are Cartesian natural transformations; e.g. this is the case for any free monad $\mathfrak{m}_p$. For this question, however, I would be happy with either Cartesian or non-Cartesian polynomial monads, as long as they are not free and have a nontrivial self-descriptorquine.)

Can a non-free monad have non-trivial "self-descriptor"?

Let $\mathbf{Poly}$ denote the category of polynomial functors on $\mathbf{Set}$, and let $\mathfrak{m}\colon\mathbf{Poly}\to\mathbf{Poly}$ be the free monad monad, i.e. the functor that sends every polynomial $p$ to the free monad $(\mathfrak{m}_p,\eta,\mu)$, $$ \mathfrak{m}_p\colon\mathbf{Set}\to\mathbf{Set} \qquad \eta_p\colon\text{id}_\mathbf{Set}\to \mathfrak{m}_p \qquad \mu_p\colon \mathfrak{m}_p\circ \mathfrak{m}_p\to \mathfrak{m}_p $$ on $p$. One can think of the underlying functor $\mathfrak{m}_p$ as the coproduct over all $p$-syntax trees of the functor represented by the leaves.

Let $(t,\eta,\mu)$ denote an arbitrary polynomial monad on $\mathbf{Set}$. This means $t$ comes equipped with an algebra structure $\alpha\colon\mathfrak{m}_t\to t$ satisfying a unit law $\alpha\circ\eta_t=\text{id}_t$ and a similar composition law. We define a self-descriptor of $t$ to be a section $$ \beta\colon t\to\mathfrak{m}_t$$ of the algebra map, $\alpha\circ\beta=\mathrm{id}_t$. We say that the self-descriptor $\beta$ is trivial if $\beta=\eta_t$, and we say it is nontrivial if $\beta\neq\eta_t$.

Note that a free monad $\mathfrak{m}_p$ always has a nontrivial self-descriptor, namely $$ \mathfrak{m}_p\xrightarrow{\mathfrak{m}_{\eta_{\,p}}}\mathfrak{m}_{\mathfrak{m}_p} $$ which is indeed nontrivial because $\mathfrak{m}_{\eta_p}\neq\eta_{\mathfrak{m}_p}$.

Question: If a polynomial monad $t$ on $\mathbf{Set}$ has a non-trivial self-descriptor, does that imply that $t$ is free, $t=^?\mathfrak{m}_p$ on some polynomial $p$? Or, instead, does there exist a non-free monad that has a non-trivial self-descriptor?

(Note: some people restrict polynomial monads to be the Cartesian ones, i.e. those for which $\eta_t$ and $\mu_t$ are Cartesian natural transformations; e.g. this is the case for any free monad $\mathfrak{m}_p$. For this question, however, I would be happy with either Cartesian or non-Cartesian polynomial monads, as long as they are not free and have a nontrivial self-descriptor.)

Can a non-free monad have non-trivial "quine"?

Let $\mathbf{Poly}$ denote the category of polynomial functors on $\mathbf{Set}$, and let $\mathfrak{m}\colon\mathbf{Poly}\to\mathbf{Poly}$ be the free monad monad, i.e. the functor that sends every polynomial $p$ to the free monad $(\mathfrak{m}_p,\eta,\mu)$, $$ \mathfrak{m}_p\colon\mathbf{Set}\to\mathbf{Set} \qquad \eta_p\colon\text{id}_\mathbf{Set}\to \mathfrak{m}_p \qquad \mu_p\colon \mathfrak{m}_p\circ \mathfrak{m}_p\to \mathfrak{m}_p $$ on $p$. One can think of the underlying functor $\mathfrak{m}_p$ as the coproduct over all $p$-syntax trees of the functor represented by the leaves.

Let $(t,\eta,\mu)$ denote an arbitrary polynomial monad on $\mathbf{Set}$. This means $t$ comes equipped with an algebra structure $\alpha\colon\mathfrak{m}_t\to t$ satisfying a unit law $\alpha\circ\eta_t=\text{id}_t$ and a similar composition law. We define a quine transformation of $t$ to be a section $$ \beta\colon t\to\mathfrak{m}_t$$ of the algebra map, i.e.\ a natural transformation with $\alpha\circ\beta=\mathrm{id}_t$. We say that the quine transformation $\beta$ is trivial if $\beta=\eta_t$, and we say it is nontrivial if $\beta\neq\eta_t$.

Note that a free monad $\mathfrak{m}_p$ always has a nontrivial quine transformation, namely $$ \mathfrak{m}_p\xrightarrow{\mathfrak{m}_{\eta_{\,p}}}\mathfrak{m}_{\mathfrak{m}_p} $$ which is indeed nontrivial because $\mathfrak{m}_{\eta_p}\neq\eta_{\mathfrak{m}_p}$.

Question: If a polynomial monad $t$ on $\mathbf{Set}$ has a non-trivial quine transformation, does that imply that $t$ is free, $t=^?\mathfrak{m}_p$ on some polynomial $p$? Or, instead, does there exist a non-free monad that has a non-trivial quine?

(Note: some people restrict polynomial monads to be the Cartesian ones, i.e. those for which $\eta_t$ and $\mu_t$ are Cartesian natural transformations; e.g. this is the case for any free monad $\mathfrak{m}_p$. For this question, however, I would be happy with either Cartesian or non-Cartesian polynomial monads, as long as they are not free and have a nontrivial quine.)

added 387 characters in body
Source Link
David Spivak
  • 8.7k
  • 1
  • 28
  • 64

Let $\mathbf{Poly}$ denote the category of polynomial functors on $\mathbf{Set}$, and let $\mathfrak{m}\colon\mathbf{Poly}\to\mathbf{Poly}$ be the free monad monad, i.e. the functor that sends every polynomial $p$ to the free monad $(\mathfrak{m}_p,\eta,\mu)$, $$ \mathfrak{m}_p\colon\mathbf{Set}\to\mathbf{Set} \qquad \eta_p\colon\text{id}_\mathbf{Set}\to \mathfrak{m}_p \qquad \mu_p\colon \mathfrak{m}_p\circ \mathfrak{m}_p\to \mathfrak{m}_p $$ on $p$. One can think of the underlying functor $\mathfrak{m}_p$ as the coproduct over all $p$-syntax trees of the functor represented by the leaves.

Let $(t,\eta,\mu)$ denote an arbitrary polynomial monad on $\mathbf{Set}$. This means $t$ comes equipped with an algebra structure $\alpha\colon\mathfrak{m}_t\to t$ satisfying a unit law $\alpha\circ\eta_t=\text{id}_t$ and a similar composition law. We define a self-descriptor of $t$ to be a section $$ \beta\colon t\to\mathfrak{m}_t$$ of the algebra map, $\alpha\circ\beta=\mathrm{id}_t$. We say that the self-descriptor $\beta$ is trivial if $\beta=\eta_t$, and we say it is nontrivial if $\beta\neq\eta_t$.

Note that a free monad $\mathfrak{m}_p$ always has a nontrivial self-descriptor, namely $$ \mathfrak{m}_p\xrightarrow{\mathfrak{m}_{\eta_{\,p}}}\mathfrak{m}_{\mathfrak{m}_p} $$ which is indeed nontrivial because $\mathfrak{m}_{\eta_p}\neq\eta_{\mathfrak{m}_p}$.

Question: If a polynomial monad $t$ on $\mathbf{Set}$ has a non-trivial self-descriptor, does that imply that $t$ is free, $t=^?\mathfrak{m}_p$ on some polynomial $p$? Or, instead, does there exist a non-free monad that has a non-trivial self-descriptor?

(Note: some people restrict polynomial monads to be the Cartesian ones, i.e. those for which $\eta_t$ and $\mu_t$ are Cartesian natural transformations; e.g. this is the case for any free monad $\mathfrak{m}_p$. For this question, however, I would be happy with either Cartesian or non-Cartesian polynomial monads, as long as they are not free and have a nontrivial self-descriptor.)

Let $\mathbf{Poly}$ denote the category of polynomial functors on $\mathbf{Set}$, and let $\mathfrak{m}\colon\mathbf{Poly}\to\mathbf{Poly}$ be the free monad monad, i.e. the functor that sends every polynomial $p$ to the free monad $(\mathfrak{m}_p,\eta,\mu)$, $$ \mathfrak{m}_p\colon\mathbf{Set}\to\mathbf{Set} \qquad \eta_p\colon\text{id}_\mathbf{Set}\to \mathfrak{m}_p \qquad \mu_p\colon \mathfrak{m}_p\circ \mathfrak{m}_p\to \mathfrak{m}_p $$ on $p$. One can think of the underlying functor $\mathfrak{m}_p$ as the coproduct over all $p$-syntax trees of the functor represented by the leaves.

Let $(t,\eta,\mu)$ denote an arbitrary polynomial monad on $\mathbf{Set}$. This means $t$ comes equipped with an algebra structure $\alpha\colon\mathfrak{m}_t\to t$ satisfying a unit law $\alpha\circ\eta_t=\text{id}_t$ and a similar composition law. We define a self-descriptor of $t$ to be a section $$ \beta\colon t\to\mathfrak{m}_t$$ of the algebra map, $\alpha\circ\beta=\mathrm{id}_t$. We say that the self-descriptor $\beta$ is trivial if $\beta=\eta_t$, and we say it is nontrivial if $\beta\neq\eta_t$.

Note that a free monad $\mathfrak{m}_p$ always has a nontrivial self-descriptor, namely $$ \mathfrak{m}_p\xrightarrow{\mathfrak{m}_{\eta_{\,p}}}\mathfrak{m}_{\mathfrak{m}_p} $$ which is indeed nontrivial because $\mathfrak{m}_{\eta_p}\neq\eta_{\mathfrak{m}_p}$.

Question: If a polynomial monad $t$ on $\mathbf{Set}$ has a non-trivial self-descriptor, does that imply that $t$ is free, $t=^?\mathfrak{m}_p$ on some polynomial $p$? Or, instead, does there exist a non-free monad that has a non-trivial self-descriptor?

Let $\mathbf{Poly}$ denote the category of polynomial functors on $\mathbf{Set}$, and let $\mathfrak{m}\colon\mathbf{Poly}\to\mathbf{Poly}$ be the free monad monad, i.e. the functor that sends every polynomial $p$ to the free monad $(\mathfrak{m}_p,\eta,\mu)$, $$ \mathfrak{m}_p\colon\mathbf{Set}\to\mathbf{Set} \qquad \eta_p\colon\text{id}_\mathbf{Set}\to \mathfrak{m}_p \qquad \mu_p\colon \mathfrak{m}_p\circ \mathfrak{m}_p\to \mathfrak{m}_p $$ on $p$. One can think of the underlying functor $\mathfrak{m}_p$ as the coproduct over all $p$-syntax trees of the functor represented by the leaves.

Let $(t,\eta,\mu)$ denote an arbitrary polynomial monad on $\mathbf{Set}$. This means $t$ comes equipped with an algebra structure $\alpha\colon\mathfrak{m}_t\to t$ satisfying a unit law $\alpha\circ\eta_t=\text{id}_t$ and a similar composition law. We define a self-descriptor of $t$ to be a section $$ \beta\colon t\to\mathfrak{m}_t$$ of the algebra map, $\alpha\circ\beta=\mathrm{id}_t$. We say that the self-descriptor $\beta$ is trivial if $\beta=\eta_t$, and we say it is nontrivial if $\beta\neq\eta_t$.

Note that a free monad $\mathfrak{m}_p$ always has a nontrivial self-descriptor, namely $$ \mathfrak{m}_p\xrightarrow{\mathfrak{m}_{\eta_{\,p}}}\mathfrak{m}_{\mathfrak{m}_p} $$ which is indeed nontrivial because $\mathfrak{m}_{\eta_p}\neq\eta_{\mathfrak{m}_p}$.

Question: If a polynomial monad $t$ on $\mathbf{Set}$ has a non-trivial self-descriptor, does that imply that $t$ is free, $t=^?\mathfrak{m}_p$ on some polynomial $p$? Or, instead, does there exist a non-free monad that has a non-trivial self-descriptor?

(Note: some people restrict polynomial monads to be the Cartesian ones, i.e. those for which $\eta_t$ and $\mu_t$ are Cartesian natural transformations; e.g. this is the case for any free monad $\mathfrak{m}_p$. For this question, however, I would be happy with either Cartesian or non-Cartesian polynomial monads, as long as they are not free and have a nontrivial self-descriptor.)

Source Link
David Spivak
  • 8.7k
  • 1
  • 28
  • 64

Can a non-free monad have non-trivial "self-descriptor"?

Let $\mathbf{Poly}$ denote the category of polynomial functors on $\mathbf{Set}$, and let $\mathfrak{m}\colon\mathbf{Poly}\to\mathbf{Poly}$ be the free monad monad, i.e. the functor that sends every polynomial $p$ to the free monad $(\mathfrak{m}_p,\eta,\mu)$, $$ \mathfrak{m}_p\colon\mathbf{Set}\to\mathbf{Set} \qquad \eta_p\colon\text{id}_\mathbf{Set}\to \mathfrak{m}_p \qquad \mu_p\colon \mathfrak{m}_p\circ \mathfrak{m}_p\to \mathfrak{m}_p $$ on $p$. One can think of the underlying functor $\mathfrak{m}_p$ as the coproduct over all $p$-syntax trees of the functor represented by the leaves.

Let $(t,\eta,\mu)$ denote an arbitrary polynomial monad on $\mathbf{Set}$. This means $t$ comes equipped with an algebra structure $\alpha\colon\mathfrak{m}_t\to t$ satisfying a unit law $\alpha\circ\eta_t=\text{id}_t$ and a similar composition law. We define a self-descriptor of $t$ to be a section $$ \beta\colon t\to\mathfrak{m}_t$$ of the algebra map, $\alpha\circ\beta=\mathrm{id}_t$. We say that the self-descriptor $\beta$ is trivial if $\beta=\eta_t$, and we say it is nontrivial if $\beta\neq\eta_t$.

Note that a free monad $\mathfrak{m}_p$ always has a nontrivial self-descriptor, namely $$ \mathfrak{m}_p\xrightarrow{\mathfrak{m}_{\eta_{\,p}}}\mathfrak{m}_{\mathfrak{m}_p} $$ which is indeed nontrivial because $\mathfrak{m}_{\eta_p}\neq\eta_{\mathfrak{m}_p}$.

Question: If a polynomial monad $t$ on $\mathbf{Set}$ has a non-trivial self-descriptor, does that imply that $t$ is free, $t=^?\mathfrak{m}_p$ on some polynomial $p$? Or, instead, does there exist a non-free monad that has a non-trivial self-descriptor?