2
$\begingroup$

In Section 5.2 of the text on Domain Theory by S. Abramsky and A. Jung, it is mentioned that:

"Suppose we are given a recursive domain equation $X \cong F(X)$ where the right hand side defines a functor on a suitable category of domains. As suggested by the example in Section 5.1.2, we want to repeat the trick which gave us fixpoints for Scott-continuous functions, namely, to take a (bi-)limit of the sequence $\mathbb{I}, F(\mathbb{I}), F(F(\mathbb{I})),\ldots$. Remember that bilimits are defined in terms of e-p-pairs. This makes it necessary that we, at least temporarily, switch to a different category."

I don't understand why we need to switch to the category of embeddings in order to compute the least fixpoint of $F$. More specifically, why don't we just apply the Smyth-Plotkin basic lemma on $F$ in the initial category in order to find the fixpoint?

$\endgroup$
6
  • $\begingroup$ Assuming you're referring to Lemma 2 in The category-theoretic solution of recursive domain equations, you have to check the condition about colimiting cocones. Have you checked it? $\endgroup$ Jan 27, 2023 at 11:32
  • $\begingroup$ Thanks for your response. Yes, I am referring to Lemma 2 of the mentioned paper. So, what you mean is that if we restrict attention to the category of embeddings, we don't need to check the requirement for the colimiting cones? $\endgroup$
    – LaR
    Jan 27, 2023 at 14:03
  • $\begingroup$ I don't actually know all possible ways in which the basic lemma can fail or succeed. What I am suggesting is that you should actually attempt to use the lemma in the way you are suggesting and see if it goes through, checking all the details. Have you done so? $\endgroup$ Jan 27, 2023 at 16:10
  • $\begingroup$ Concretely, if you keep reading all the way to Definition 3, they require that every $\omega$-chain have a colimit. This is not going to be true if we take all continuous maps as morphisms (I have not checked the details, just going on gut feeling), but will be true if take embeddings. $\endgroup$ Jan 27, 2023 at 16:17
  • $\begingroup$ But the basic lemma does not require all $\omega$-chains. It just requires a particular one which starts from $< \perp, \perp_{F(\perp)}>$, where $\perp_{F(\perp)}$ is the unique morphism from $\perp$ to $F(\perp)$. So, if I am not mistaken, the basic lemma produces at each step of its construction the same object and morphism as if we were working in the category of embeddings. $\endgroup$
    – LaR
    Jan 27, 2023 at 16:48

1 Answer 1

5
$\begingroup$

I give it a try to answer my own question after having read more carefully the material in the text by Abramsky and Jung (AJ). I believe there are two reasons why we turn to the category of embeddings:

  1. ${\bf Practicality:}$ As it is mentioned in AJ, page 71, "Continuity of a functor is a hard condition to verify. Luckily there is a property which is stronger but nevertheless much easier to check". Applying the basic lemma directly to a functor $F$ is a tedious task because verifying the condition of the lemma is very similar to verifying continuity of the functor. Instead of following this tedious road, we define the notion of local continuity (see AJ for details). It is generally straightforward to verify that an everyday functor is locally continuous: almost all the basic constructors that arise in domain equations, are locally continuous and the composition of locally continuous functors is also locally continuous. Now comes the interesting part: as it is shown in AJ (Proposition 5.2.4), a locally continuous functor $F : {\bf D} \rightarrow {\bf D}$ restricts to a continuous functor $F^e: {\bf D}^e \rightarrow {\bf D}^e$. In other words, local continuity implies continuity in the category of embeddings. Now, we can apply the Smyth-Plotkin basic lemma directly on $F^e$ (because every continuous functor satisfies the conditions of the lemma).

  2. Mixed-variant functors: The second reason we don't use directly the basic lemma is that it ony applies to covariant functors. Therefore, the basic lemma can not be applied to mixed variant functors, such as the "arrow" one, or more generally functors of the form $F: {\bf D}^{op} \times {\bf D} \rightarrow {\bf D}$. It turns out that we can define a notion of local continuity that covers such functors. Then, it can be shown that we can define a functor $F^e: {\bf D}^{e} \times {\bf D}^{e} \rightarrow {\bf D}^{e}$, ie., a covariant functor in the category of embeddings. This functor is continuous and therefore the basic lemma is again applicable.

$\endgroup$
2
  • 2
    $\begingroup$ Excellent answer, you should accept it :-) $\endgroup$ Jan 31, 2023 at 9:39
  • $\begingroup$ Thanks for pressing me to work harder :-) $\endgroup$
    – LaR
    Jan 31, 2023 at 10:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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