2
$\begingroup$

In some programming languages, there's functions whose output can change on the basis of changing internal state; for example, the second time you compute $f(5)$ you might get a different answer. This doesn't really happen in mathematics. Nonetheless, I'd like to better understand the extent to which mathematics relies on the "statelessness" of mathematical functions.

To this end, define:

Definition 0. Given a set $X$, view the Kleene closure $X^*$ as an $(\mathbb{N},\leq)$ presheaf as follows:

  • $X^*(n) = \{x \in X^* \mid \mathrm{length}(x) = n\} \cong X^n$
  • If $\varphi:a \leq b$, then $X^*(\varphi) : X^*(b) \rightarrow X^*(a)$ is the restriction map that takes the first $a$-many letters of the word and deletes the rest.

Definition 1. Given sets $X$ and $Y$, a stateful function $X \rightarrow Y$ is a natural transform $X^* \rightarrow Y^*$, where $X^*$ is the set of all words in $X$. Write $\mathbf{Set}^*$ for the category whose objects are sets and whose morphisms are stateful functions.

My questions are whether or not this has been studied, and in particular, whether or not there is a sensible answer to the admittedly rather vague question: "What is the internal logic of $\mathbf{Set}^*$?"

Improve this question
$\endgroup$
6
  • $\begingroup$ As you admit yourself, the question is rather vague, so I don't know how to answer. Still, in case it helps to clarify something - your $\mathbf{Set}^*$ seems to be isomorphic to the coKleisli category of the comonad structure on $\_^*$, with $\varepsilon(x_1,...,x_n)=x_n$ and $\delta(x_1,...,x_n)=((x_1),...,(x_1,...,x_n))$. $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Aug 20, 2016 at 7:53
  • $\begingroup$ This seems to be essentially the theory of polymorphic list operations ---as in functional programming--- and there's a host of categorical results there. As for the internal logic, in computer science, lists are used as naive representations for relations and so looking in that direction may be fruitful. $\endgroup$
    – Musa Al-hassy
    Commented Aug 20, 2016 at 18:51
  • $\begingroup$ It is unclear what you mean by "natural transform $X*\to Y^*$". Do you mean "natural transformations between the functors from the functor $X\mapsto X^*$ to $Y\mapsto Y^*$? If yes, note that all pairs of sets $(X,Y)$ have the same hom-set. If no, what's a natural transform? $\endgroup$
    – Thorsten
    Commented Aug 7, 2017 at 13:25
  • $\begingroup$ And in programming, stateful functions are modelled using the Kleisli-Category of the state monad. $\endgroup$
    – Thorsten
    Commented Aug 7, 2017 at 13:27
  • $\begingroup$ $\DeclareMathOperator\Hom{Hom}$@Thorsten, I think I must misunderstand your [comment](mathoverflow.net/questions/247891/…). What does "all pairs of sets $(X, Y)$ have the same hom-set" mean? Surely $\Hom_{\mathbf{Set}}(\emptyset, {*}) \ne \Hom_{\mathbf{Set}}({*}, \emptyset)$? $\endgroup$
    – LSpice
    Commented Mar 25, 2019 at 21:16

0

Reset to default

You must log in to answer this question.