(Extracted from old emails to Dana; TODO: Rewrite)
Let us fix some theory T along the lines of PA or ZF or any such thing. For any T-definable set X, let P_T(X) denote the set of T-definable predicates on X, modulo T-provable equality. Note that P_T(X) itself can be interpreted as a T-definable set; indeed, P_T extends in a natural way to an endofunctor on the category (which I shall also call T, in slight abuse of notation) whose objects are T-definable sets, and whose morphisms are T-definable functions between those sets modulo T-provable equality. Note also that P_T(X) is automatically a singleton if T is inconsistent, for an inconsistent theory proves any two things equal.
By the general “Goedel-Loeb category” fixed point results I had developed, we can find some particular V in this category which is isomorphic to P_T(V); that is, a T-definable set V along with a T-definable bijection j from V to the T-definable predicates on V modulo T-provable equality. (This is perhaps somewhat similar in spirit to the idea at the end of your lecture about considering bijections between a countable model of ZF and the countable collection of definable classes within that model, although we are fixing only one bijection rather than considering many different ones).
[Note that it is not quite trivial to find such a V; for example, the natural numbers N are countably infinite, and if T is consistent and countable, we have that P_T(N), the collection of T-definable subsets of the naturals modulo T-provable equality, is also countably infinite, so it may seem like N is a candidate for V. However, proving P_T(N) is infinite entails proving it is not a singleton, and thus proving T is consistent; thus, T itself cannot prove the existence of a bijection between N and P_T(N), on pain of Goedel’s Second Incompleteness Theorem. This sort of pain is why it is easiest to obtain V through my general fixed point machinery, though it should in principle be possible to extract a definition of V in a way which can be understood even apart from that machinery]
Once we have our bijection j from V to P_T(V), we can interpret a modally naive set theory into T like so: take V to be the sort of sets, and interpret “x is an element of y” as “T proves that x satisfies the predicate j(y)” (this formula being internalizable in T in the usual way).
In this set theory (which is consistent just in case T is), we get a modally naive comprehension principle like so: for every definable formula phi(x), there is a definable set {x : phi(x)} such that our set theory proves “For every set x, x is an element of {x : phi(x)} if and only if []phi(x) holds” [where “[]x” is the proposition “T proves x”]. I believe this sort of modalized naive comprehension was called “Comp[]” in your lecture slides.
This set theory will not have normal extensionality, however, but rather only a narrower, modalized extensionality: specifically, the simplest extensionality principle this set theory proves is that {x : phi(x)} = {x : psi(x)} <–> [](for all x, phi(x) <–> psi(x)). [Note that this formulation only sets out a criterion of equality for those sets which are defined via comprehension; there will be extensionality-like principles for sets more generally as well, but this was the simplest to state right now]
This establishes the consistency of some sort of modalized naive set theory in provability logic. We should of course further ask whether this system is interesting or useful.
To the first point, of whether it is interesting, one phenomenon of note about this system is that, using only its comprehension principle and the modal logic K4, in trying to carry out Russell’s paradox, we end up proving not the contradiction _|_, but, rather, only the modal statement []([]_|_ -> _|_) -> []_|_ (i.e., Goedel’s Second Incompleteness Theorem); more generally, by analogous constructions, we obtain this same result with arbitrary propositions in place of _|_ (i.e., Loeb’s theorem). Thus, in this style of modally naive set theory, we need not bake the GL axiom into our modal logic, but nonetheless will recover it as a direct consequence of our modalized naive comprehension principle. This is somewhat interesting.
Another phenomenon which I find rather interesting is this: again by the general machinery of my fixed point/”categorical Loeb’s theorem” results, we will find that our model V satisfies both a modalized version of Foundation as well as a modalized version of Anti-Foundation. Specifically, V will be both an initial algebra and a terminal coalgebra for the P_T functor; the initiality is a modalized form of Foundation (ordinary Foundation amounting to the proposition that the class of sets is an initial algebra for the “small subsets of” functor) and the terminality is a modalized form of Aczel’s Anti-foundation Axiom (which ordinarily amounts to the proposition that the class of sets is a terminal coalgebra for the “small subsets of” functor). This initial algebra-terminal coalgebra coincidence is like nothing available in ordinary set theory, and something I would like to investigate further.
As for whether this model is “useful” beyond being interesting, that is less clear. Many statements which we would in any normal set theory want to be provably false (that is, provably equal to _|_) will instead become, in this model, only provably equal to []_|_, or to [][]_|_, or such things, blocked from reducing to complete falsehood by Goedel’s Second Incompleteness Theorem. (For example, the proposition “{x : _|_} = {y : y = {x : _|_}}” (the analogue of “0 = 1, as von Neumann ordinals”) comes out not to _|_, but []_|_). This could conceivably be ameliorated by adding to the theory the axioms “~[]^n _|_” for arbitrarily large n, or even stronger axioms of this sort, though the theory would have to remain unable to prove the necessitation of any of these axioms.
Note that the concern to find a fixed-point V of P_T was in order to obtain extensionality-like principles; if we are not concerned with extensionality at all, and just want Comp[] in a GL logic, then it suffices merely to have a surjection from V to P_T(V), which is easily satisfied (for typical T) by taking V to be the natural numbers. For this, no complicated fixed-point machinery is required.
I should also have noted, we get in these provability logic set theories not just Comp[], but also []Comp[].
Here is more on the first order properties of the models:
The “baby” model, where we take our domain of discourse to be the natural numbers, and simply define “x In y” to mean “x provably (within some fixed consistent background theory of the ordinary sort) satisfies the y-th formula defining a predicate on natural numbers” (in some typical context for interpreting “provably”, “y-th formula”, etc.) is actually quite illustrative. It lacks good extensionality properties, but it is very easy to grasp.
One very important observation is that, in this model, we can assign to each formula phi(x) [in the first-order language of set theory] a corresponding set {x : phi(x)}, such that every set is of this form for some phi, and such that x In {x : phi(x)} just in case []phi(x). Let’s call this “converse Comp[]”; it is the observation that, in a suitable sense, every set arises by some comprehension.
Because of Goedel’s 2nd Incompleteness Theorem, our model will never satisfy any proposition of the form []~[]p. This, in conjunction with the above, means our model will never satisfy any proposition of the form []~(x In y)
With respect to the various first-order properties considered on page 6 of “Can Modalities Save Naive Set Theory?”, we should note of this model the following:
It does satisfy the “Con” property (existence of binary intersections; that is, for all z_1 and z_2, there is a y, such that for all x, we have x In y iff both x In z_1 and x In z_2). This is easy: the intersection of {x : phi(x)} and {x : psi(x)} will be {x : phi(x) & psi(x)}. It also satisfies []Con, the necessitation of the Con property, in the same way.
With respect to the “Neg” property (existence of complements), the model doesn’t satisfy it in the ordinary sense, because there are computably enumerable sets of naturals whose complements are not computably enumerable. Relatedly, the model doesn’t satisfy []Neg because there will not be any x and y such that []~(x In y), as noted above.
However, to each set z, there is still attached a canonical set z’ which still represents its complement in some sense (taking {x : phi(x)}’ to be {x : ~phi(x)}). We will have, for example, that (x In z) & (x In z’) entails []False.
Defining <>p as ~[]~p (and let us assume we are working within a Boolean logic), we will not have Comp<> or its necessitation, for the same reasons as in the Neg case. (Note that, for a model satisfying both Comp[] and converse Comp[], there is an equivalence between Neg and Comp<>).
The model will satisfy Mem but not []Mem. It will not satisfy []Mem, because it will never satisfy any proposition of the form []~[]p. It will satisfy Mem because it satisfies every proposition of the form ~[]~(x in y).
The model will not satisfy Non, because it satisfies []Comp[], which is incompatible with Non. It will not satisfy []Non either, as this would require it to satisfy statements of the form []~[]p, which it never does.
I haven’t yet wrapped my head around what happens with Bar in this model. I hope to be able to give an answer to this soon.
I spoke of all of the above in the context of the simpler to understand baby model, where sets are given by natural numbers, we map these natural numbers surjectively onto definable sets of natural numbers in the usual way by a function I will call j, and we define x In y to mean []j(y)(x).
The more sophisticated model is like the above, but replacing “natural numbers” throughout by a more complex construction (a certain definable subset of the natural numbers), such that all of the above noted first-order properties of the baby model remain true, but we also get a suitable extensionality principle, as noted before: that {x : phi(x)} = {x : psi(x)} just in case [](for all x. phi(x) <–> psi(x)).
In this sophisticated model, it should also be noted, Equ fails; for example, the statement “{x : False} = {x : True}” is equivalent (and necessarily equivalent) to “[]False” in this model, and thus “<>({x : False} = {x : True})” is of the form ~[]~[]p, and thus satisfied, while “[]{{x : False} = {x : True})” is equivalent to [][]False, and thus not (for any typical background theory) satisfied.
The following is extracted from Slack:
It’ll be a while before we get to the naive set theory stuff properly, and I never actually got around to working out if there was much to be done with it beyond noting its existence. There’s two kinds of (pseudo-)naive set theory, actually; a pseudo-naive material set theory (in the cumulative hierarchy type sense), which is less interesting to me but should still be noted, and a pseudo-naive structural set theory, which is more interesting to me but a vaguer notion. I’ll start whetting Reid’s appetite here just by noting the basics of the former.
Consider the following formal theory:
There are things called “sets” and there is a binary relation “x in y” between them. Furthermore, to every closed predicate P(x) on sets, we associate a set which for now I will notate (\x -> P(x)), where x is here understood as a bound variable. We have that x in (\x -> P(x)) holds iff []P(x) holds. And we have that (\x -> P(x)) = (\x -> Q(x)) iff for all x, [](P(x) <–> Q(x)).
[These axioms are to be understood as necessary entailments; that is, not only do they hold, but also you are allowed to apply the necessitation rule “A |- B implies []A |- []B” to them. Necessary truths, not merely contingent ones.]
If you got rid of the []s, this theory would be naive set theory: unrestricted set comprehension with extensionality.
With the []s, this is a kind of modal set theory. An inconsistent one, in many modal logics. But if the background modal logic is GL, then I claim this is consistent (a new observation, I believe; one that hasn’t been made before). (edited)
12:04
Consistent in that it not only doesn’t entail falsehood, but doesn’t entail []False, or [][]False, or any such iteration.
12:05
Whether it’s an interesting theory beyond that remains to be seen, although there are a few more potentially interesting things I will say about it in a second.
12:05
The proof I have in mind of its consistency is via my general theory, of introspective theories, GL-categories, fixed point results in such, etc, etc. So we will not get to the proof for a while, as we must build up that background first.
12:05
But let’s at least see what goes awry if we try to construct Russell’s paradox here.
12:06
So we look at the proposition “(\x -> ~(x in x)) in (\x -> ~(x in x))”.
12:07
For convenience, let’s say R = (\x -> ~(x in x)), and use P to denote the proposition R in R.
12:07
Our basic rules tell us R in (\x -> ~(x in x)) iff []~(R in R). That is, P holds iff []~P.
12:11
If we got rid of that [], we’d have an inconsistency. But with the [] around, no inconsistency is immediate.
If we are working in a “normal modal logic” (one where [] is a product-preserving functor; for what it’s worth, these are precisely the modal logics which can be given Kripke-style possible worlds semantics), and also assume we have the modal principle 4 available (that []A entails [][]A), what we can conclude now is this:
P holds iff []~P. Since P is therefore equivalent to a []ed statement, we also have that P entails []P. Since P entails both []P and []~P, we have that P entails []False. If we furthermore knew ~[]False, we would know ~P.
By necessitation, we have that []~[]False |- []~P. But since []~P |- P |- []False, we can conclude that []~[]False |- []False.
Interpreting “[]A” as “Provably A”, this is the modal phrasing of Goedel’s 2nd Incompleteness Theorem: If it’s provably the case that manifest falsehood is not provable, then manifest falsehood is provable.
Going through the above reasoning and replacing “~A” with the implication “A -> X”, and replacing “False” with X accordingly, we get in the exact same way the conclusion that [] ([]X -> X) |- []X, which is Loeb’s theorem.
So in the context of this pseudo-naive material set theory interpreted in the normal modal logic 4, our Russell’s paradox doesn’t give us inconsistency, but gives us Loeb’s theorem. Loeb’s theorem + 4 is the modal logic GL.
I claim, though the proof will have to wait for later, that this is the only extension this pseudo-naive set theory enforces on us about our modal logic; it doesn’t force any other modal logical principles to become true, beyond those already in GL. Indeed inside any “GL-category”, interpreting the []s accordingly, we will obtain a model of this pseudo-naive set theory. (edited)
Sridhar 12:22 PM
We might also ask of this material set theory, where it falls on the spectrum between Foundation and Anti-Foundation.
12:24
A naive set theory says that the universe of sets V is a fixed point of the covariant power-set functor; that V is isomorphic to P(V).
The axiom of foundation essentially states that this isomorphism is the initial algebra of this functor.
Aczel’s axiom of anti-foundation, on the other hand, states that this isomorphism is the terminal coalgebra of this functor.
12:25
In our case, our set theory is only pseudo-naive; instead of V being isomorphic to P(V) as such, it will be isomorphic to []P(V), where the “[]” is a functor defined for general GL-categories we will investigate later.
12:26
But we will also discover the following surprise: our solution to V = []P(V) will be BOTH an initial algebra and a terminal coalgebra for the []P(-) functor. It will have both foundational and anti-foundational flavor at the same time.
12:29
Traditionally, this is inconsistent, because you can derive from the initial algebra condition that “All sets are well-founded”, and from the terminal coalgebra condition that “Some sets are not well-founded”. In our case, however, the initial algebra condition will not let us derive “All sets are well-founded”.
Indeed, we have a universal set (\x -> True), and since this is clearly in itself, we do not have that all sets are well-founded. Still, we can nonetheless define functions on sets by a modalized form of “epsilon-recursion”, and prove predicates to universally hold among them by a modalized form of “epsilon-induction” (that is what the initial algebra condition guarantees).
Alex 2:04 PM
Can you clarify the parenthetical comment above? “These axioms” refers to the entailments (1) x in (\x -> P(x)) |- []P(x), (2) []P(x) |- x in (\x -> P(x)), (3) (\x -> P(x)) = (\x -> Q(x)) |- for all x [](P(x) <–> Q(x)), (4) for all x [](P(x) <–> Q(x)) |- (\x -> P(x)) = (\x -> Q(x)) ?
2:04
By []P(x) do you mean ([]P)(x), or [](P(x)), or maybe one of these doesn’t make sense?
2:06
Is there an entailment that you’re not “allowed to” apply the necessitation rule to? i.e. is the necessitation rule not one of the rules for [] in this logic? And if it’s not, does the assertion that you’re “allowed to” do this boil down to turning the four axioms above into schemas where you can pile on as many boxes as you want?
2:06
Or maybe just one?
2:09
Regarding 2 comments ago: maybe ([]P)(x) and [](P(x)) are obviously equivalent?
2:12
Regarding initial algebra/terminal coalgebra: That’s awesome. Are there other natural examples of endofunctors for which the initial algebra and terminal coalgebra are isomorphic?
Sridhar 2:19 PM
Ah, I’ve used P in two different things above: for a predicate, and for the power set functor
2:19
the powerset functor just for the two comments at the end
2:20
When P is a predicate and I write []P(x), I mean [](P(x)). Take the proposition P(x), and apply the modal operator [] to it.
2:21
In this context, []P isn’t something people normally say, but if they did, they’d probably mean by it just the same thing in the end: that []P is the predicate which sends x to [](P(x))
Dale 2:22 PM
Can your formulate what the general consistency result is for introspective theories, so I get a taste of it?
2:22
The treatment of Russell’s paradox is very cool!
2:23
And, again, it’s not clear to me exactly how this relates to the “Intensional Set Theory” paper I sent you… can you remind me how this approach is different?
Sridhar 2:23 PM
I’d have to look at that paper again, but sure
2:25
The general consistency result for introspective theories is that we can freely construct them in every which way, and these free constructions do not become trivial. They do not become trivial because the free introspective theory is the theory of GL-categories, and all the usual things people ever think about in the context of Goedelian phenomena (PA, ZFC, etc, or the restriction of these to sigma-1 formulae, or various other such things) provide consistent models of these; models which do not validate whichever particular bad thing you do not want validated.
Dale 2:25 PM
Uploading the paper to #documents
2:25
Ah, ok!
Sridhar 2:26 PM
I have a few theorems about how to construct introspective theories or GL-categories this way or that way from this thing or that thing, which could be read as “consistency results”, but if it’s really “consistency” that one is worried about, the above is the gist. It establishes that all of these things have models where neither False, nor []False, nor [][]False, etc., are true.
Dale 2:26 PM
Also, can you upload the outline of your thesis we constructed a few months ago?
Sridhar 2:26 PM
yeah, let me find it
Alex 2:28 PM
Ah yes, thinking about it again, my question about about []P(x) was silly. What about my other questions tho?
Sridhar 2:29 PM
Yup, I will respond to them very soon, after finishing lunch.
2:30
or, well, I’ll respond to some now:
Dale 2:30 PM
Also, hi Alex!
Sridhar 2:32 PM
As for “Is there an entailment that you’re not “allowed to” apply the necessitation rule to? i.e. is the necessitation rule not one of the rules for [] in this logic? And if it’s not, does the assertion that you’re “allowed to” do this boil down to turning the four axioms above into schemas where you can pile on as many boxes as you want?”, yes, necessitation is indeed one of the rules for [], and I intend necessitation to apply to everything. I just want to clarify that I’m giving these axioms in that manner. Sometimes, people postulate modal theories where some things are given as axioms, but not axioms that necessitation is allowed to apply to. I.e., you first specify all the things that necessitation is allowed to apply to, then you specify that on top of that, there some propositions which are to be considered true but not necessarily true. I am just clarifying that I’m not doing that.
2:32
For example, you might imagine the theory which is S5 + “Trump is President”, but where the latter is meant as just a contingent fact about the world, and not one which is necessary.
2:32
this theory proves “Trump is President”, but does not prove “[]Trump is President”
Alex 2:33 PM
oh, weird, ok
5 replies
Last reply 2 years agoView thread
Sridhar 2:33 PM
Kripke-style model of such a theory could involve worlds that don’t satisfy the theory (those where Trump isn’t President), along with the one designated world that does satisfy the theory
2:34
but that’s not the sort of thing I’m doing. The sort of thing I’m doing, were it Kripke-style, would involve models where every world satisfies the theory.
Alex 2:34 PM
I see. Was I correct in interpreting the axioms as (1) – (4)?
Sridhar 2:35 PM
Ah, will respond soon, brb, mom calling me
Alex 4:16 PM
Also just a reminder that about my other question: Are there other natural examples of endofunctors for which the initial algebra and terminal coalgebra are isomorphic? I found a trivial one: the constant functor with value A has A as both its initial algebra and terminal coalgebra. Are there good non-constant examples?
Sridhar 9:09 PM
Re: https://srcat.slack.com/archives/CBDP9NDR9/p1530209044000278:
Yes, this is correct.
Alex
Can you clarify the parenthetical comment above? “These axioms” refers to the entailments (1) x in (\x -> P(x)) |- []P(x), (2) []P(x) |- x in (\x -> P(x)), (3) (\x -> P(x)) = (\x -> Q(x)) |- for all x [](P(x) <–> Q(x)), (4) for all x [](P(x) <–> Q(x)) |- (\x -> P(x)) = (\x -> Q(x)) ?
Posted in #naive_set_theory | Jun 28th, 2018 | View message
9:14
We could add more axioms to those as well, which are validated by the intended model: for example, I have not stated in these set theory axioms anything formalizing the initial algebra/terminal coalgebra business (which I don’t expect follows automatically from these axioms, though for all I know it does.)
But this is one fairly natural simple set theory, of a pseudo-naive flavor, that our models will validate. (edited)
Sridhar 9:23 PM
The comprehension principle I stated above also referenced only closed unary predicates, but I should say, it’s possible to extend it to allow for unary predicates with parameters given by other sets. I think that proceeds in precisely the expected way, though I should double-check that at some point.
9:26
Re: My own comment: “If you got rid of the []s, this theory would be naive set theory: unrestricted set comprehension with extensionality.”:
This actually isn’t quite fair as a description of the relation to fully naive set theory, because the extensionality principle given in my pseudo-naive set theory is only stated for those sets specified by comprehensions. But there is nothing forcing all sets to be equal to one given by a comprehension.
Traditionally, we have S = (\x -> x in S) as also a consequence of extensionality (in the language of lambda calculus, this is the eta rule to accompany the beta rule “x in (\x -> Phi(x)) iff Phi(x)”), so that every set is equal to one given by a comprehension (with one parameter, of the set itself). Here, these two sides will not be identified; indeed, if we ask whether x is in S, we get “x in S”, but if we ask whether x is in (\x -> x in S), we get “[](x in S)”.
—-
There is a sense, not captured in the axioms given above, in which our models will still validate something sort of like “Every set is given by a comprehension”, but it’s not literally true in that form, and I’ll have to think about how to phrase it in purely material set theory terms.
(Essentially, our fixed point V ~= []P(V) amounts to saying that V is isomorphic to the set of definable subsets of V, for our GL-category’s internal notion of “definable subsets of”. So this is something like saying that the sets are precisely as good as the comprehensions over sets… But there’s some subtleties here I have to think more about.
Again, as I said, I never actually explored the naive material set theory much, beyond just noting its existence. And I probably won’t spend too much time thinking about its details even now, until I finish clarifying the general introspective theory stuff to everyone else and also to myself again. It will be much more productive to return to it after then, I think.) (edited)
Sridhar 9:48 PM
Re: https://srcat.slack.com/archives/CBDP9NDR9/p1530216971000224
Yes, there is one famous class of examples, due to Dana Scott actually, in his work on domain theory; originally, in the context of his D_infinity construction of a model of the lambda calculus.
In “”Initial algebras and terminal coalgebras: a survey” by Adámek et al, they consider these Dana Scott/domain theory examples, and refer generally to coincidence of initial algebras and terminal coalgebras as “canonical fixed points”.
The idea is this: In general (ignoring size issues), if all colimits exist, one can construct an initial algebra for a functor F by considering the colimit of 0 -> F(0) -> F(F(0)) -> etc, iterated through transfinite ordinals until it converges. And dually, if all limits exist, the terminal coalgebra can be constructed as the limit of 1 -> F(1) -> F(F(1)) -> … . [You can consider these results as generalizations of one common proof of the order-theoretic Knaster-Tarski fixed point theorem. [There are essentially two ways to prove Knaster-Tarski, but one of them involves an iteration just like this]].
So the key thing is that sometimes these colimits and limits come out the same. What natural contexts force that to happen?
I’ll try to describe it abstractly below, though I’ve only ever really seen one application where this abstract structure comes up. If you’re interested, you should consult the Adámek et al survey for a better write-up than the gistful summary I’m giving here:
Some categories have the following properties:
1) There are two collections of special morphisms, L and R, such that an L-morphism from A to B amounts to the same thing as an R-morphism from B to A, in a functorial way, and such that a colimit cone of a chain of L-morphisms must itself be comprised of L-morphisms, and similarly for limit cones and R-morphisms.
2) The initial object and terminal object are the same (a so-called “zero object”), and every map out of it is in L, and every map into it is in R
In this case, we find that, for any functor f which takes L,R corresponding morphisms to L,R corresponding morphisms, the colimit cone of 0 -> F(0) -> F(F(0)) -> etc (built out of L-maps) has to correspond (under the L, R correspondence) to the limit cone of 1 -> F(1) -> F(F(1)) -> etc (built out of R-maps), and thus the initial algebra matches the terminal coalgebra.
As an example of a category with the properties noted above, consider the category of lattices with least elements and joins of omega-chains, and monotone maps between them which don’t have to preserve the least element but do have to preserve the omega-joins. Take the L-maps between to be the monic left-adjoints and the R-maps to be the corresponding right-adjoints. You’ll also find that this category is cartesian closed, and that any functors which are enriched with respect to that closed structure are also L, R correspondence preserving.
I could give more motivation for why one might care about this category for domain theory/lambda calculus-modeling, but it would be a digression; nonetheless, you will find it has the properties above. (edited)
Alex
Also just a reminder that about my other question: Are there other natural examples of endofunctors for which the initial algebra and terminal coalgebra are isomorphic? I found a trivial one: the constant functor with value A has A as both its initial algebra and terminal coalgebra. Are there good non-constant examples?
Posted in #naive_set_theory | Jun 28th, 2018 | View message
9:51
Another example of a context where initial algebras and terminal coalgebras coincide is in the Haskell type system; the recursively defined types there generally allow both primitive recursive definition of functions out of them (thus, are initial algebras) and, by virtue of Haskell’s “laziness”, dually corecursive definition of functions into them (thus, are terminal coalgebras).
There is almost certainly some relation between the Haskell example and the general domain theory class of examples, but I’ve never fully worked it out. (edited)
9:52
Other than those, though, I’ve never seen initial algebra/terminal coalgebra coincidence come up anywhere outside of my thing. It is surprising.
Sridhar 9:54 PM
Incidentally, I mentioned this initial algebra/terminal coalgebra coincidence to you years ago, perhaps back in 2011 when I first discovered it, and that had been your question then too. I’ve always kept my eyes open for other examples, but somehow never discovered them, even though it seems there must be a trove lurking somewhere, especially given the “canonical fixed point” name in the Adámek et al survey above.