Re: [HoTT] Re: Why do we need judgmental equality?

[Nicolai Kraus <nicolai.kraus@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 6083 bytes --]

I agree with everything Martin said below, but I want to go a step further
and argue that judgmental equality is potentially holding us back, in terms
of meta-theoretical results AND usability of the type theory.

I can understand that, for programming, we want built-in computation.
However, for a foundational system, I think we should strive for something
as minimalistic as possible without arbitrary additional features.

It might be a bit controversial to call judgmental equality an "arbitrary
additional feature", but there is certainly some arbitrariness involved
(why else would Sigma have judgmental eta in some systems and not in
others?). It seems to me that the cleanest, most minimalistic, and most
canonical choice would be a type theory without judgmental equalities *at
all*. This would also be much more in line with the approach of category
theory, and I expect that it could make the lives of those of us working
with models easier. Is there a deep theoretical reason for the necessity of
judgmental equality?

Of course, we want convenience and usability. I just fail to see why this
means that judgmental equality has to be a built-in thing (one could say:
why does it have to be part of the core). It's possible that, if we do
*not* insist on built-in judgmental equality, we could even get *more*
convenience. What I mean is this: Let's write WTT for a "weak type theory"
without any judgmental equalities (since we're doing HoTT, maybe with some
axioms such as univalence, but let's not specify this here). Let's say we
know that a certain set A of judgmental equalities does not change WTT,
i.e. that (WTT+A) is a conservative extension of WTT (conservative in a
constructive sense). We could now have a proof assistant which uses WTT as
core but which allows us to "load" the conservativity proof of A. Then, at
the beginning of a module, a user can tell the proof assistant that in this
module, they pretend that the type theory is (WTT+A); i.e. for the user, it
looks as if they are working in (WTT+A) but, in the background, the proof
assistant translates everything to WTT. In another module, the user can
pretend they are working in (WTT+B) instead, if (WTT+B) is conservative
over WTT as well. The idea here is that some proofs benefit more from one
set of judgmental equalities, while other proofs benefit more from others.
Being able to choose which equalities one wants could lead to increased
convenience. (I think WTT+A+B is not necessarily conservative over WTT, so
we cannot just always assume all equalities for maximum convenience.)

For example, let's consider a cubical type theory. I'm aware that we don't
really know many conservativity properties of cubical type theories yet,
but I would be interested in knowing some. Maybe some cubical type theory
gives us a set C which our WTT-based proof assistant can load. In other
words, instead of saying "hey, we have found a new cubical type theory with
amazing computational behaviour, an implementation is on GitHub", people
could say "hey, we have found a new set of judgmental equalities, on GitHub
is the conservativity proof that you can load into your proof assistant to
use it".

I don't think this is something that we will manage to get anytime soon,
and I find it very difficult in general to find conservativity results, but
is there a theoretical reason which makes this impossible?

Nicolai


On Fri, Feb 8, 2019 at 9:19 PM Martín Hötzel Escardó <
escardo.martin@gmail.com> wrote:

> I would also like to know an answer to this question. It is true that
> dependent type theories have been designed using definitional equality.
>
> But why would anybody say that there is a *need* for that? Is it
> impossible to define a sensible dependent type theory (say for the purpose
> of serving as a foundation for univalent mathematics) that doesn't mention
> anything like definitional equality? If not, why not? And notice that I am
> not talking about *usability* of a proof assistant such as the *existing*
> ones (say Coq, Agda, Lean) were definitional equalities to be removed. I
> don't care if such hypothetical proof assistants would be impossibly
> difficult to use for a dependent type theory lacking definitional
> equalities (if such a thing exists).
>
> The question asked by Felix is a very sensible one: why is it claimed that
> definitional equalities are essential to dependent type theories?
>
> (I do understand that they are used to compute, and so if you are
> interested in constructive mathematics (like I am) then they are useful.
> But, again, in principle we can think of a dependent type theory with no
> definitional equalities and instead an existence property like e.g. in
> Lambek and Scott's "introduction to higher-order categorical logic". And
> like was discussed in a relatively recent message by Thierry Coquand in
> this list,)
>
> Martin
>
>
> On Wednesday, 30 January 2019 11:54:07 UTC, Felix Rech wrote:
>>
>> In section 1.1 of the HoTT book it says "In type theory there is also a
>> need for an equality judgment." Currently it seems to me like one could, in
>> principle, replace substitution along judgmental equality with explicit
>> transports if one added a few sensible rules to the type theory. Is there a
>> fundamental reason why the equality judgment is still necessary?
>>
>> Thanks,
>> Felix Rech
>>
> --
> You received this message because you are subscribed to the Google Groups
> "Homotopy Type Theory" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to HomotopyTypeTheory+unsubscribe@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
>

-- 
You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group.
To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[-- Attachment #2: Type: text/html, Size: 7175 bytes --]