From: Thomas Streicher <stre...@mathematik.tu-darmstadt.de>
To: Peter LeFanu Lumsdaine <p.l.lu...@gmail.com>
Cc: Dimitris Tsementzis <dtse...@princeton.edu>,
Homotopy Type Theory <HomotopyT...@googlegroups.com>,
Univalent Mathematics <univalent-...@googlegroups.com>
Subject: Re: [HoTT] A small observation on cumulativity and the failure of initiality
Date: Fri, 13 Oct 2017 10:10:56 +0200 [thread overview]
Message-ID: <20171013081056.GB18718@mathematik.tu-darmstadt.de> (raw)
In-Reply-To: <CAAkwb-kaWf0=SROtXVnHvN5Xb9RJOoQYjXu6i5tonzq0J3o4TQ@mail.gmail.com>
unnotated cumulativity just means that we syntactically omit the
inclusions of U_n into U_{n+1} but semantically they are there
and have to be inserted when interpreting syntax
that's similar to universes `a la Russell which are just a shorthand
for universes `a la Tarski
but what is true is that there are syntaxes where terms don't have
unique types, but those always consider terms together with a type
but generally in CS and logic one distinguishes between typing `a la
Church and `a la Curry, the first is used in ML-like type theories,
the latter when typing terms of out of an untyped collection of
preterms
Thomas
On Fri, Oct 13, 2017 at 10:03:06AM +0200, Peter LeFanu Lumsdaine wrote:
> On Thu, Oct 12, 2017 at 8:43 PM, Dimitris Tsementzis <dtse...@princeton.edu
> > wrote:
>
> > Dear all,
> >
> > Let???s say a type theory TT is *initial* if its term model C_TT is initial
> > among TT-models, where TT-models are models of the categorical semantics of
> > type theory (e.g. CwFs/C-systems etc.) with enough extra structure to model
> > the rules of TT.
> >
>
> I like the examples, but I would give a different analysis of what they
> tell us.
>
> The definition of ???initial??? presupposes that we have already defined what
> ???TT-models??? means ??? i.e. what the categorical semantics should be. There
> is as yet no proposed general definition of this (as far as I know).
>
> Heuristically, there???s certainly a large class of type theories where we
> understand what the categorical semantics are, and all clearly agree. But
> rules like un-annotated cumulativity are *not* in this class. It???s not
> clear what should correspond to un-annotated cumulativity, as a rule in
> CwA???s (or CwF???s, C-systems, etc). A certain operation on terms? An
> operation, plus the condition that it???s mono? An assumption that terms of
> one type are literally a subset of terms of the other? Some of these will
> make initiality clearly false; others may make it true but very
> non-obviously so (that is, more non-obviously than usual).
>
> So I don???t think we can say ???These theories aren???t initial.??? ??? but more
> like ???We???re not sure what the correct initiality statement is for these
> theories, and some versions one might try are false.??? But I definitely
> agree that they show
>
> > the claim that e.g. Book HoTT or 2LTT is initial cannot be considered
> obvious
>
> ???p.
>
>
>
> Then we have the following, building on an example of Voevodsky???s.
> >
>
>
>
>
> > *OBSERVATION*. Any type theory which contains the following rules
> > (admissible or otherwise)
> >
> > ?? |- T *Type*
> > ???????????????????????? (C)
> > ?? |- B(T) *Type*
> >
> > ?? |- t : T
> > ???????????????????????? (R1)
> > ?? |- t : B(T)
> >
> > ?? |- t : T
> > ???????????????????????? (R2)
> > ?? |- p(t) : B(T)
> >
> > together with axioms that there is a type T0 in any context and a term t0
> > : T0 in any context, is not initial.
> >
> > *PROOF SKETCH.* Let TT be such a type theory. Consider the type theory
> > TT* which replaces (R1) with the rule
> >
> > ?? |- t : T
> > ???????????????????????? (R1*)
> > ?? |- q(t) : B(T)
> >
> > i.e. the rule which adds an ???annotation??? to a term t from T that becomes a
> > term of B(T). Then the category of TT-models is isomorphic (in fact, equal)
> > to the category of TT*-models and in particular the term models C_TT and
> > C_TT* are both TT-models. But there are two distinct TT-model homomorphisms
> > from C_TT to C_TT*, one which sends p(t0) to pq(t0) and one which sends
> > p(t0) to qp(t0) (where p(t0) is regarded as an element of Tm_{C_TT} (empty,
> > B(B(T0))), i.e. of the set of terms of B(B(T0)) in the empty context as
> > they are interpreted in the term model C_TT).
> >
> > *COROLLARY. *Any (non-trivial) type theory with a ???cumulativity" rule for
> > universes, i.e. a rule of the form
> >
> > ?? |- A : U0
> > ???????????????????????? (U-cumul)
> > ?? |- A : U1
> >
> > is not initial. In particular, the type theory in the HoTT book is not
> > initial (because of (U-cumul)), and two-level type theory 2LTT as presented
> > here <https://arxiv.org/abs/1705.03307> is not initial (because of the
> > rule (FIB-PRE)).
> >
> > The moral of this small observation, if correct, is not of course that
> > type theories with the guilty rules cannot be made initial by appropriate
> > modifications to either the categorical semantics or the syntax, but rather
> > that a bit of care might be required for this task. One modification would
> > be to define their categorical semantics to be such that certain identities
> > hold that are not generally included in the definitions of
> > CwF/C-system/???-gadgets (e.g. that the inclusion operation on universes is
> > idempotent). Another modification would be to add annotations (by replacing
> > (R1) with (R1*) as above) and extra definitional equalities ensuring that
> > annotations commute with type constructors.
> >
> > But without some such explicit modification, I think that the claim that
> > e.g. Book HoTT or 2LTT is initial cannot be considered obvious, or even
> > entirely correct.
> >
> > Best,
> >
> > Dimitris
> >
> > PS: Has something like the above regarding cumulativity rules has been
> > observed before ??? if so can someone provide a relevant reference?
> >
> >
> >
> >
> >
>
next prev parent reply other threads:[~2017-10-13 8:10 UTC|newest]
Thread overview: 47+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-10-12 18:43 Dimitris Tsementzis
2017-10-12 22:31 ` [HoTT] " Michael Shulman
2017-10-13 4:30 ` Dimitris Tsementzis
2017-10-13 15:41 ` Michael Shulman
2017-10-13 21:51 ` Dimitris Tsementzis
2017-10-13 0:09 ` Steve Awodey
2017-10-13 0:44 ` Alexander Altman
2017-10-13 15:50 ` Michael Shulman
2017-10-13 16:17 ` Steve Awodey
2017-10-13 16:23 ` Michael Shulman
2017-10-13 16:36 ` Matt Oliveri
2017-10-14 14:56 ` Gabriel Scherer
2017-10-15 7:45 ` Thomas Streicher
2017-10-15 8:37 ` Thierry Coquand
2017-10-15 9:26 ` Thomas Streicher
2017-10-16 5:30 ` Andrew Polonsky
2017-10-15 10:12 ` Michael Shulman
2017-10-15 13:57 ` Thomas Streicher
2017-10-15 14:53 ` Michael Shulman
2017-10-15 16:00 ` Michael Shulman
2017-10-15 21:00 ` Matt Oliveri
2017-10-16 5:09 ` Michael Shulman
2017-10-16 12:30 ` Neel Krishnaswami
2017-10-16 13:35 ` Matt Oliveri
2017-10-16 15:00 ` Michael Shulman
2017-10-16 16:34 ` Matt Oliveri
2017-10-16 13:45 ` Matt Oliveri
2017-10-16 15:05 ` Michael Shulman
2017-10-16 16:20 ` Matt Oliveri
2017-10-16 16:37 ` Michael Shulman
2017-10-16 10:01 ` Thomas Streicher
2017-10-15 20:06 ` Matt Oliveri
2017-10-13 8:03 ` Peter LeFanu Lumsdaine
2017-10-13 8:10 ` Thomas Streicher [this message]
2017-10-14 7:33 ` Thorsten Altenkirch
2017-10-14 9:37 ` Andrej Bauer
2017-10-14 9:52 ` Thomas Streicher
2017-10-14 10:51 ` SV: " Erik Palmgren
2017-10-15 23:42 ` Andrej Bauer
2017-10-15 10:42 ` Thorsten Altenkirch
2017-10-13 22:05 ` Dimitris Tsementzis
2017-10-13 14:12 ` Robin Adams
[not found] <B14E498C-FA19-41D2-B196-42FAF85F8CD8@princeton.edu>
2017-10-14 9:55 ` [HoTT] " Alexander Altman
2017-10-16 10:21 Thorsten Altenkirch
2017-10-16 10:42 ` Andrew Polonsky
2017-10-16 14:12 ` Thorsten Altenkirch
2017-10-16 10:21 Thorsten Altenkirch
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20171013081056.GB18718@mathematik.tu-darmstadt.de \
--to="stre..."@mathematik.tu-darmstadt.de \
--cc="HomotopyT..."@googlegroups.com \
--cc="dtse..."@princeton.edu \
--cc="p.l.lu..."@gmail.com \
--cc="univalent-..."@googlegroups.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).