Naive Set Theory

(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.

Categorical Loeb’s Theorem

Within an introspective theory T with internal category C, functor F : T -> C, and natural transformation N : 1_T -> F, let P be a presheaf on C, and suppose given an object X of C such that X is isomorphic to []P(X).

[TODO: Write out everything in the following rough sketch in detail, readably to others.]

Because of this X, we can write out W : P(P(1)) -> P(X) = \g : P(P(1)) -> \x : X -> g(x construed as of type []P(X), applied to F(x) : []X, to yield a []P(1)).

We can then make the Y combinator Y : P(P(1)) -> P(1) = \g : P(P(1)) -> (W g) (W g). And we derive a fixed point property from this accordingly.

This is the categorical Loeb’s theorem.

To kick this all off, though, we need an X which is isomorphic to []P(X).

This would be a solution to a fixed point equation, and we could get it therefore by re-invoking this very categorical Loeb’s theorem, when we take P to be be the presheaf which assigns to every object the slices above it (the sets indexed by it, so to speak). From this, it follows that any slice above Ob(C), interpreted as an Ob(C)-indexed set, has a fixed point, so to speak.

In this re-invocation, we’ll still need some X isomorphic to [](Slices above X), to kick off our bootstrapping.

Actually, by paying more careful attention, our categorical Loeb’s theorem doesn’t need isomorphism; it needs some sort of weaker split epimorphism type property, some quasi-isomorphism so to speak. And we can see that we can get this kind of quasi-isomorphism when X is itself Mor(C), the type of ALL slices at once. [TODO: There is something tricky here in how there seems to be some dependence on evil encoding in establishing that this has the appropriate quasi-isomorphism property; think about this more]

So from that, our bootstrapping completes, and we can drop the X ~= []P(X) explicit requirement from all instances of categorical Loeb’s theorem for general presheaves P.

Furthermore, for the specific case of the presheaf P = slice, we get our fixedpoints for slices above Ob, but what are their uniqueness properties?

We can show that if a slice above Ob comes from a presheaf with respect to Core(C), then by invoking categorical Loeb’s theorem, [](an iso between two fixed points for this slice above Ob) yields an iso between the two fixed points, and therefore, there really is an iso between them. Thus, unique fixed points.

Furthermore, if the slice above Ob comes from a covariant Set-valued functor (i.e., presheaf with respect to C^{op}), the same kind of Loeb’s theorem invoking reasoning will establish that it is both an initial algebra and a terminal coalgebra. [TODO: Look up initial/terminal coincidence in the literature and think more about that]

[TODO: We also have to be careful about the fact that Slices above – isn’t actually a functor, only a 2-functor or functor up to isomorphism or whatever. And we want a version of our P(P(1)) |- P(1) theorem that acts on setoid-valued presheaves, rather than just set-valued presheaves, so we can impose isomorphism as the appropriate equivalence relation. All just problems because we work in 1- rather than (infinity, 1)-category theory, but good to take care of.]

[TODO: There should also be something about presheaves parametrized by elements of objects of T or something?]

To Ponder

Random thoughts to ponder, which I don’t have a lot to say about yet:

What is the structure of []N, where N is a natural numbers object?

Are the theories of introspective theories or GL-categories decidable in any natural sense? (Determining equality between terms, or decidable as first-order theories in general?)

The initial algebras in things like the initial topos with NNO are initial with respect to the category, but can’t also be initial with respect to things like the slice category presheaf, or else we could define the interpretation function from []X to X by induction in general, contra Loeb’s theorem. There should thus follow some theorem like “If a lex theory has an internal initial model of itself, which is further initial with respect to the slice presheaf, then the theory is trivial”.

Loeb’s theorem is probably specific to lex theories, but the six axiom GL category axiomatization and perhaps the rest of the relationship between GL categories and introspective theories is probably true for general tree-categories, in some sense. In particular, consider the abstract tree-category that is opposite to lex categories, in the sense that we use the opposites of lex categories and a map from real set A to internal set B is a map from Hom(1, B) to A. [In other words, the natural tree-category where we talk about maps Hom(1, B) to A rather than maps A to Hom(1, B), maps go from descendants to child, rather than from child to desendant, etc]. Are introspective theories relative to this tree-category of any interest?

The fact that “Th(Introspective theories) proves []X” entails “Th(Introspective theories) proves X” has a flavor that seems like it violates Loeb’s theorem/G2IT, but it doesn’t. What’s going on is basically, T can’t prove ‘T proves X’ entails X, but T can prove ‘S proves X’ entails X for some sub-theory S of T. This means that in practice, often, when one has proven []X and wants to conclude X simpliciter, one can note that the proof of []X was actually a proof of ‘S proves X’ within a suitable sub-theory S of T for which this principle is available. And such things. One can prove something about the internal category of all categories and have it apply to the meta-category one is working within as well, in such ways.

Self-Enriched Categories

By a self-enriched category with finite limits, I mean a category with finite limits, along with a bifunctor \Box (A \to B) from this category to itself, contravariant in A and covariant and limit-preserving in B, and composition operations \Box (A \to B) \times \Box (B \to C) \times \ldots \times \Box (W \to X) \vdash \Box(A \to X) which satisfy the usual associativity relations.

In this way, this category exists both as an ordinary category C, and as a category with the same objects enriched over C.

Let us presume also that we have a transformation from \mathrm{Hom}_C(A, B) to \mathrm{Hom}_C(1, \Box(A, B)), natural in A and B, such that the functorial action of \Box(A \to B) amounts to the same thing as using this transformation and then the enriched composition operation.

An example of such structure is given by a cartesian closed category (and in this case, the last transformation is an isomorphism). But a non-cartesian-closed example of such structure is given by a general GL-category. (We can also relax the cartesian limit definition here to merely a monoidal definition). Indeed, a GL-category is basically a self-internal category, which goes beyond being a self-enriched category.

We can also talk about K4 self-enriched categories, which come with a canonical natural transformation from X to \Box X = \Box(1 \to X). Introspective theories have this structure.

We can even talk about S4 self-enriched categories, where this is the unit of \Box as a monad; thus, \Box^n X has transformations in and out of \Box X for each positive n. Nontrivial GL-categories never have this structure, but it’s common in other contexts.

None of this is necessary for my thesis, as such, but there are some concepts in my thesis which really are only about self-enriched categories.

It would be great to find a vantage point from which all these concepts are cleanly unified, as different instances of a generality.

Outline

The plan:

8 writing sections, three optional:

0.A: Tree-categories (optional)

0.B: Multiply internal categories

1.A: Introspective theories (aka, SR-categories; four axioms defining these)

1.B: Free introspective theories (aka, GL-categories; theorem on how to construct these using six axioms)

Can discuss at this point the K4 properties of GL-categories, and the analogous properties for introspective theories. The translation dictionary and observations for how these structures can be seen as interpreting K4 modal logic.

2.A: The categorical Loeb’s theorem [and related results: P(P(1)) |- P(1) as the categorical Loeb’s theorem, fixed points and their uniqueness, initial algebra/terminal coalgebra properties and coincidence.]

Can discuss at this point the GL modal logic connection.

2.B: Models [general theorems on model constructions (e.g., from theories with internal initial models for themselves), and observing specific traditional instances of Goedel’s incompleteness theorem (PA, ZFC, Joyal style arithmetic universes) as models of these structures]

Note that a syntactic analysis can show that the free GL category on one object is nontrivial. From this it follows that the free introspective theory is also nontrivial, and since every introspective theory is itself a GL-category (indeed, an introspective theory is something like the same as a GL-category where every object is in the range of []?), this tells us the free introspective theory doesn’t prove []^n False for any n.

We can also get an introspective theory of any large cardinality we like by taking the free introspective theory on suitably many constants, which compactness assures us is nontrivial; in the same way, we can get introspective theories embedding any particular theory, including uncomputable ones, etc. That is, the theory of GL-(X)es always contains the theory of Xes as an embedding, and the []^n operator I believe acts faithfully on this embedding for each n.

These are all just free constructions. We might ask how to find examples “in the wild”. Of course, everything has some presentation freely in terms of generators and relations, so finding something “in the wild” just means having some independent interest in it. But even PA, ZFC, etc, were devised as axiomatic theories; i.e., syntactic theories, free theories. It was just the fact that they Godel-coded themselves which is found in the wild (an instance of the general fact that any computable theory encoding computation Godel-codes itself, which begins to feel pretty syntactic again). So it’s not clear what models “in the wild” amounts to in the end for this sort of thing, or what’s lacking about exhibiting free models and demonstrating their suitable nontrivialities.

3.A: Applications (optional; a further exploration of doing mathematics within this framework as metalogic, and/or connections between this and modal set theory, or various lambda calculi, or programming language topics (using this to find “paradoxical” models of lambda calculus, designing a lambda calculus to model this, using this to model programming languages with reflection. Discussion about GLS logic. Thinking about the free monad extending [])

3.B: Future work (optional; gesturing at how this properly lives in the world of to (infinity, 1)-categories, and whatever I didn’t do in 3.A, and whatever other future work I want to gesture at but not do now. Writing out the details for categories which are merely enriched over themselves, rather than internal to themselves; can these two concepts be unified within the framework of tree categories?)

To be done as a series of posts and then combined into a document.

The Free Introspective Theory; aka, the theory of GL-categories

Let us say a GL-category \footnote{so named for reasons to be explained later} is a structure <L, L’, F, F’> (which, in typical abuse of language, we may sometimes identify with simply the name of L) of the following sort:

A) A lexcategory L

A’) A lexcategory L’ internal to L

B) A lexfunctor F from L to Glob(L’) \footnote{Presentational TODO: it will be useful at some point to specify a convention that a functor from an actual category to an internal category always means a functor from the former to the globalization of the latter; once establishing this convention, we can drop the distracting explicit “Glob”s of the sort here.

In a similar vein, it will also be useful to explicitly establish the convention that a lexfunctor H : C \to D can also be implicitly regarded as a homomorphism : Glob(C’) \to Glob(H[C’]) for any structure C’ internal to C in the natural way}

B’) A lexfunctor F’ from L’ to F[L’] internal to L

C) Such that F(F(x)) = F'(F(x)) for any object/morphism x in L, construed appropriately (I’m writing with some abuse of notation (see previous footnote), but this condition is similar to the third condition in the description of introspective theory homomorphisms)

C’) Such that, in the internal logic of L, we have that F'(F'(x)) = F[F’](F'(x)) for any object/morphism x in F[L’]

Note that the theory of GL-categories is essentially algebraic and can thus be identified with a lexcategory (the generic lexcategory with an internal GL-category), which for now let us call TheoryGL.

In the standard way as for any essentially algebraic theory, we also get a notion of GL-category homomorphism; a GL-category homomorphism between GL-categories <L_1, L_1′, F_1, F_1′> and <L_2, L_2′, F_2, F_2′> is

  • A lex functor H : L_1 \to L_2
  • Such that H[L_1′] = L_2′
  • Such that H[F_1(x)] = F_2(H(x)) for any object/morphism x in L_1, where the H on the left acts as a functor from Glob(L_1′) to Glob(H[L_1′]) = Glob(L_2′) in the natural fashion
  • Such that H[F_1′] = F_2′

Now observe that TheoryGL (the generic lexcategory with an internal GL-category) can be equipped as an introspective theory <TheoryGL, L, S, Q> as follows:

  • TheoryGL is the generic lexcategory with an internal GL-category <L, L’, F, F’>.
  • L, thus, is the underlying lexcategory of that internal GL-category.
  • To specify S now is, by the nature of TheoryGL and of S as a lexfunctor from TheoryGL to Glob(L), to specify an L-internal GL-category; specifically, we will take S to correspond to the L-internal GL-category <L’, F[L’], F’, F[F’]>. Note that this choice is indeed a GL-category, with structure/conditions A, B, and C in such S corresponding to structure/conditions A’, B’, and C’ in <L, L’, F, F’>, and further structure/conditions A’, B’, and C’ in S obtained by application of F to the former, respectively. [TODO: Though this is indeed a complete description of what is going on here, this language may be clunky… Perhaps reword in some fashion]
  • Finally, to specify Q is to specify a GL-category homomorphism from our generic GL-category <L, L’, F, F’> to the globalization (within TheoryGL) of the L-internal GL-category S = <L’, F[L’], F’, F[F’]>. For this, we take the underlying lexfunctor of that homomorphism to be F. Verifying that F is indeed a GL-category homomorphism requires verifying three further conditions (as in the bulleted list above), which in this case come out to F[L’] = F[L’] (trivially true), F(F(x)) = F'(F(x)) interpreted suitably (true by condition C for L as a GL-category), and F[F’] = F[F’] (again, trivially true).

This completes the definition of <TheoryGL, L, S, Q> and demonstration of it as an introspective theory.

Next, I intend to show that this is in fact the initial introspective theory; that is, that it has a unique introspective theory homomorphism into any other introspective theory <T, T’, S_2, Q_2>. [TODO: I really need to learn how to pick better names for variables…]

Such a homomorphism amounts to a lexfunctor H from TheoryGL to T satisfying certain conditions (specifically, that H[L] = T’ and that the identity H(S(x)) = S_2(H(x)) holds, suitably interpreted), which is to say (by the nature of TheoryGL) such a homomorphism amounts to a T-internal GL-category <T’, . [TODO: Finish]

[TODO: Discuss more generally the free introspective theory extending a given essentially algebraic theory extending the theory of lexcategories, given in essentially the same manner (replacing lexcat with whatever, lexfunc with whatever-homomorphism), giving rise to GL-(whatevers) (e.g., GL-toposes, GL-(lex)categories with coproducts, etc.)]

Finally, let us show that given any introspective theory <T, T’, S, Q>, we have that T can be interpreted as a GL-category as well; specifically, we will have a GL-category <T, T’, S, Q interpreted suitably> [TODO: Finish]

GLS-categories

This is a slight digression of no immediate relevance, but it’s something to mention at some point anyway:

Recall that, by design, if <T, T’, S, Q> is an introspective theory, then from every model M of T (in the sense of a lexfunctor from T to Set), we obtain another model M’ of T internal to M (this is induced by S), and a homomorphism f_M : M -> Glob(M’) (this is induced by Q). [For convenience, I shall refer to Glob(M’) as M* in the rest of this post.]

It may be that f_M is an isomorphism or not. (This corresponds to the question of whether |- []A reliably entails |- A or not). Let’s call those M with this property GLS-categories, for their connection to GLS modal logic (above and beyond mere GL).

It’s too much to hope for, for G2IT/Loeb’s theorem type reasons, that f_M be an isomorphism in every model of T. Nonetheless, this may be true in particular models. At any rate:

Given any model M of T, we obtain in the above fashion a chain M –f_M–> M* –f_{M*}–> M** –f_{M**}–> … of models of T and homomorphisms from each into the next.

Taking the colimit of this chain, we obtain a model N of T such that f_N is indeed an isomorphism (this is a consequence of the finitary nature of lex-logic: each piece of structure in N* ends up coming from M***… for some finite positive number of *s, and thus in the image of f_{M**…} for some finite number of *s, and thus in the image of f_{N}).

Conversely, of course, if f_M were already an isomorphism, the entire chain would be trivial and its colimit would be M again.

Thus, we see that the GLS-categories form a reflective full subcategory of the GL-categories, with the above process of obtaining N from M as the reflector.

Introspective Theory Homomorphisms

Recall that an introspective theory consists of four pieces of data <a lexcat T, a lexcat T’ internal to T, a lexfunctor S from T to Glob(T’), and a natural transformation Q>. The full definition was given in a previous post. Of note, the definition is essentially algebraic. Thus, in a completely standard way, we can work out a corresponding notion of homomorphism between introspective theories. The purpose of this note is to make that notion explicit, as preparation for describing free introspective theories in an upcoming note.

Given two introspective theories <T1, T1′, S1, Q1> and <T2, T2′, S2, Q2>, an introspective theory homomorphism between them consists of:

*) A lexfunctor f from T1 to T2 [footnote: this functor will be taken for our purposes to preserve lex structure on the nose (sending chosen limits to chosen limits). This is what using the standard notion of essentially algebraic to formalize lexcats yields; as noted before, we would like eventually to generalize away from this, but doing so in a fully satisfactory way would require dipping our toes into infinity categories and therefore complicate this initial exploration unduly].

*) Such that f[T1′] = T2′

*) And such that Glob(f) . S1 = S2 . f, where Glob(f) : Glob(T1′) -> Glob(T2′) is the functor induced by f in the obvious way.

(In other words, for any morphism (or object, but it suffices to consider morphisms) in T1, we get the same result whether we first turn it into a global section of Mor(T1′) by applying S1, then turning it into a global section of Mor(T2′) by applying f, as we do if we first turn it into a morphism of T2 by applying f, then turn it into a global section of Mor(T2′) by applying S2.

In other words, we have a commutative square where the top-left node is Mor(T1), the top-right node is Hom_{T_1}(1, Mor(T1′)), the bottom-left node is Mor(T2), and the bottom-right node is Hom_{T_2}(1, Mor(T2′)). The map from top-left to top-right is the action of S1 on morphisms. The map from bottom-left to bottom-right is the action of S2 on morphisms. And on both sides there are maps from top to bottom being the action of f on morphisms (that this is “well-typed” on the right follows from the previous condition that f[T1′] = T2′)

[At some point, for this and other commutative diagrams, I will either draw them out by hand and upload a photo, make diagrams nicely with Paul Taylor’s package and upload a photo, or learn how to make diagrams nicely with some other package that directly interfaces with the WordPress blog])

*) And, finally, such that for any object A in T1, we have that f(Q1_A) = Q2_{f(A)}.

Coming up next: an explicit (or more explicit than just “It is what it is”) construction of the free introspective theory.

Towards a Categorical Loeb’s Theorem (Pt. 1)

I’m lazy and dawdling, but here, I will start outlining the categorical Loeb’s theorem. I’ll begin with a special case and eventually expand it to the most general version we need.

(This post isn’t quite ready yet, but I’m posting it anyway to demonstrate that I’m getting at least a modicum of stuff done and perhaps buoy me to get more done in response to feedback.)

Some background and notation:

For objects A, B of an introspective theory T with designated internal category T’ and lex functor S : T -> Glob(T’), we define the object [](A -> B) of T as Hom_{T’}(S(A), S(B)). [In general, it will be convenient to suppress such uses of S where obvious and necessary to consider objects of T as objects of T’, etc.; thus, I might instead have written, as abuse of notation, Hom_{T’}(A, B)].

Note that this is genuinely a binary operation: I do not presume there is any such object as A -> B and apply some unary operator [] to it; in particular, I do not presume cartesian closure of T. I have chosen this [](A -> B) notation, which is potentially misleading in this regard, because it is nonetheless fruitfully suggestive of certain analogies with modal logic which we will explore in the future.

It will, however, be convenient to use the shorthand []A for [](1 -> A) as well. (In the special case where we DO make cartesian closure assumptions, it will turn out that the bifunctor [](A -> B) is naturally isomorphic to []Exp(A, B) (i.e., [](1 -> Exp(A, B))), where Exp(A, B) is the exponential given by the cartesian closed structure. But, again, we do not need such assumptions.)

Note that [](A -> B) is contravariantly functorial in A, and covariantly lex-functorial in B.

Finally, recall that the fourth axiom defining an introspective theory gives us a natural transformation 4_A : A |- []A [the name “4” here serves as a coincidental pun: we obtain this natural transformation by the fourth axiom defining introspective theories, but it also corresponds to the axiom standardly considered under the name “4” in modal logic].

Alright, that is all the background we need for now. Here is the observation (again, this is a special case which we shall seek to generalize):

Suppose given a morphism e : Z |- [](Z -> A) and d : [](Z -> A) |- Z such that e . d = id. (That is, suppose that we have some [](Z -> A) as a retract of Z).

Then, let w : [](Z -> A) |- []A be defined by first constructing the map 4_Z . d : [](Z -> A) |- []Z and combining this with the identity [](Z -> A) |- [](Z -> A) to get a map [](Z -> A) |- [](Z -> A) & []Z, and finally, finishing off with the composition operator on T’ of type [](Z -> A) & [](1 -> Z) |- [](1 -> A) to get, overall, a map [](Z -> A) |- []A. (Does that make sense? Basically, w(m) = m [a morphism from Z to A] composed in T’ with 4_Z(d(m)) [a morphism from 1 to Z] to get a morphism from 1 to A which is something like “the self-application of” m).

Now suppose given f : []A |- A. We can then construct f . w . e : Z |- A.

Applying S to this (taking morphisms in T to morphisms in Glob(T’)), we get a globally defined element q = S[f . w . e] of the object [](Z -> A). [Footnote: There is a slight ambiguity/difficulty in saying things like “S[f . w . e]”, in that we can interpret this as a morphism in Glob(T’) from Z to A, or a morphism in T from 1 to [](Z -> A). In this case, it is the latter perspective I am interested in at the moment. Ideally, I would develop better language for dealing with this sort of issue…]

We can now apply f . w : [](Z -> A) |- A to q to get a globally defined element f . w . q of A.

I intend now to demonstrate that w . q = S[f . w . q], and thus we have that f . w . q is a fixed point of the map x |-> f . S[x].

To demonstrate this, observe that w . q = w . S[f . w . e] = S[f . w . e] (a global element of [](Z -> A)) composed in T’ with 4_Z . d . S[f . w . e] (a global element of []Z).

By naturality of 4, we have that 4_Z . d . x = S[d] composed in T’ with 4 x, for any global element x. [TODO: Clarify]

By functoriality of S, we have that S[f . w . e] composed in T’ with S[d] composed in T’ with 4 S[f . w . e] = S[f . w . e . d] composed in T’ with 4 S[f . w . e].

As e . d = id and S[f . w . e] = q, this comes out to S[f . w] composed in T’ with 4 q. Which comes out to S[f . w. q] as desired. [TODO: What exactly is going on here? Clarify].

This completes the proof of the stated theorem. Note that this provides a strengthened analog to Loeb’s theorem (given f : []A |- A, we conclude the existence of f . w . q : 1 |- A, but with furthermore a fixed point property which goes unnoticed in mere propositional logic where we do not care about equalities of parallel such sequents-as-morphisms).

Note also that we only ever use the object A in terms of the maps into A; we will see soon that we can generalize from A to any suitably definable presheaf.

(TODO: Talk also about how to obtain Z, [](Z -> A), e, d via bootstrapping this theorem, getting Z isomorphic to [](Z -> A) with application of this theorem to suitable presheaf. This will require also talking about generalization where e needn’t quite be a proper morphism.)