Not signed in (Sign In)

Start a new discussion

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.

Add your comments
  • Please log in or leave your comment as a "guest post". If commenting as a "guest", please include your name in the message as a courtesy. Note: only certain categories allow guest posts.
  • To produce a hyperlink to an nLab entry, simply put double square brackets around its name, e.g. [[category]]. To use (La)TeX mathematics in your post, make sure Markdown+Itex is selected below and put your mathematics between dollar signs as usual. Only a subset of the usual TeX math commands are accepted: see here for a list.

  • (Help)