Not signed in (Sign In)

Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

  • Sign in using OpenID

Discussion Tag Cloud

Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.

Welcome to nForum
If you want to take part in these discussions either sign in now (if you have an account), apply for one now (if you don't).
    • CommentRowNumber1.
    • CommentAuthorMike Shulman
    • CommentTimeJan 27th 2011

    Created complete small category, and moved the proof of Freyd’s theorem to there from adjoint functor theorem.

    • CommentRowNumber2.
    • CommentAuthorTobyBartels
    • CommentTimeJan 27th 2011

    I added to the latter that the adjoint functor theorem for posets still holds constructively, despite the classical reasoning that precedes it. (After all, the classical stuff was only going the other way, but it still confused me for a minute as to whether you had actually proved the theorem constructively.)

    • CommentRowNumber3.
    • CommentAuthorMike Shulman
    • CommentTimeJan 28th 2011


    • CommentRowNumber4.
    • CommentAuthorMike Shulman
    • CommentTimeSep 10th 2011

    I just realized that the proof of Freyd’s theorem, in addition to being non-constructive, at least appears to be evil. We need the collection of all morphisms in the category to be a set (or a class, or something with an equality relation), which appears to require that the collection of all objects in the category be also a set, i.e. that the category be strict.

    It looks even eviller if you beta-reduce the application of Cantor’s theorem by diagonalization. Then you get something like this: assuming r,s:xyr,s \colon x\to y, define a morphism g:x fMor(D)yg\colon x \to \prod_{f\in Mor(D)} y whose f thf^{th} component is rr if ff is a morphism x fMor(D)yx \to \prod_{f\in Mor(D)} y whose f thf^{th} component is ss, and ss otherwise. Then the g thg^{th} component of gg is rr if it’s ss and ss if it’s rr, hence r=sr=s. But now in the definition of gg there is an explicit equality test on the domain and codomain of each fMor(D)f\in Mor(D).

    Is this evil irredeemable?

    (Personal story: last night I read the corresponding beta-reduced proof of the generalized version for factorization structures, and spent a while feeling ill about its evilness. Eventually I realized it was a beta-reduced version of a generalization of Freyd’s theorem, which simultaneously made me feel more comfortable with the proof for factorization structures, and less comfortable with Freyd’s proof.)

    • CommentRowNumber5.
    • CommentAuthorSam Staton
    • CommentTimeDec 7th 2018

    Added two references and a slightly longer discussion of models of impredicative type theory.

    • CommentRowNumber6.
    • CommentAuthorMike Shulman
    • CommentTimeJun 27th 2019

    Added discussion of strong vs weak completeness, and a reference to the important Hyland-Robinson-Rosolini paper.

    diff, v6, current

    • CommentRowNumber7.
    • CommentAuthorMike Shulman
    • CommentTimeJun 27th 2019

    I’m not convinced that this “alternative approach” of using a replete full subcategory of SetSet actually works. The repletion of a weakly complete full subcategory of SetSet is certainly a strongly complete one, which is indeed still essentially small if the original one was actually small. However, it seems to me that to model polymorphic type theory you need the category to be actually small, not just essentially so. Doesn’t a polymorphic type like X.B\forall X. B have to be modeled by the product over all objects in the category, not just a skeleton thereof? it seems to me that it does, because a term t:X.Bt : \forall X. B has to have an application t(A):B[A/X]t(A) : B[A/X] for any type AA, not just those whose interpretation belongs to the skeleton.

    The Møgelberg-Simpson paper seems to gloss over this: they define the interpretation of X.B\forall X.B (Figure 3, page 12) as a product over all objects in their skeleton C\mathbf{C} (so that this product exists), but then they define the interpretation of t(A)t(A) (Figure 4, page 19) by evaluating the interpretation of tt at the interpretation of AA, and I can’t find any claim that the latter must in fact be in the skeleton (nor would I expect it to be in general). Of course it’s isomorphic to an object of the skeleton, but the whole point is that we don’t have a function choosing such an isomorphism.

    • CommentRowNumber8.
    • CommentAuthorMike Shulman
    • CommentTimeJun 27th 2019

    Added some more references, and mentioned that to model polymorphic type theory one doesn’t really need completeness, only products over the set of objects.

    diff, v7, current

    • CommentRowNumber9.
    • CommentAuthorSam Staton
    • CommentTimeJul 8th 2019
    • (edited Jul 8th 2019)

    Regarding #7. I think there may be a typo in Fig 4 of the Møgelberg-Simpson paper. If you look instead at this Rosolini-Simpson paper, which the Møgelberg-Simpson paper cites, they instead interpret

    [[t(τ)]] γ,ρ=gpd(σ,γ,i)(([[t]] γ,ρ) D) [[ t(\tau)]] _{\gamma,\rho} = gpd(\sigma, \gamma, i)(([[ t]]_{\gamma,\rho})_D)

    where DD is in the small category and i:D[[τ]] γi:D\multimap [[ \tau]]_\gamma is iso. Of course, there is something to check about the groupoids working out, but they seem to have thought about it. (Lemma 5.4, says everything is well-formed; Lemma 5.2 says that the iso is canonical; proofs are omitted, though.) Does that help?

    • CommentRowNumber10.
    • CommentAuthorMike Shulman
    • CommentTimeJul 8th 2019

    Ah, I think I see! Their interpretation of X.B\forall X.B builds in invariance under (iso)morphism: instead of X.X\forall X.X being the product of all objects in the category, it’s more like the initial object of the category (the limit of the identity functor). And the way they do this is by feeding the relational-parametricity part of the model (the interpretation of types as relations) back into the interpretation of types as objects/sets, so that unlike in an ordinary relational model the two levels are all mixed up inductively. In particular, there’s no “underlying” interpretation of types as sets that they’re then building a relational model on top of; the simultaneous relational interpretation is crucial to making the set interpretation work. Does that seem right?

    • CommentRowNumber11.
    • CommentAuthorSam Staton
    • CommentTimeJul 10th 2019

    More about the Rosolini-Simpson model

    diff, v9, current

    • CommentRowNumber12.
    • CommentAuthorSam Staton
    • CommentTimeJul 10th 2019
    • (edited Jul 10th 2019)

    Thanks, that seems right. I have tried to summarize this in the article. I wonder two things.

    (1) In these articles, the effects/recursion make things a little bit more complicated. If we drop them, as I tried to do in the nlab article just now, does it become clearer / kind-of obvious?

    (2) In the interpretation of \forall, does it still work if we just use bijective relations instead of arbitrary relations? Lemma 5.2 in Rosolini-Simpson seems to only use the graph of a bijection, not an arbitrary relation. (And if so, is the interpretation really living in something like presheaves on the underlying groupoid of C\mathbf{C}?) Obviously relational parametricity might not hold, but it might still be a model.

    • CommentRowNumber13.
    • CommentAuthorThomas Holder
    • CommentTimeJul 26th 2020

    Reference added to

    diff, v11, current

    • CommentRowNumber14.
    • CommentAuthormaxsnew
    • CommentTimeAug 26th 2022

    I have a small confusion about this page. I just read Hyland’s paper “A small complete category” and he claims that his construction is enough to interpret the calculus of constructions.

    On this page at the end of section 4 it says it is not known if there is a topos with a “strongly complete small category” and at the end of section 5 it says a “a true complete small category” would be needed to model the calculus of constructions. Am I correct in reading that “true” there should not be interpreted as “strong”, due to Hyland’s result?

    • CommentRowNumber15.
    • CommentAuthorvarkor
    • CommentTimeJun 8th 2023

    Mention that it suffices to have powers, rather than products.

    diff, v15, current