[Coq-Club] [Agda] Re: [HoTT] newbie questions about homotopy theory & advantage of UF/Coq

[Matthieu Sozeau]

I agree with you Andrej, and the (well founded) transitive closure of
the subterm relation can easily be defined for computational inductive
families (all inductive types if you remove prop), avoiding
the computation of ordinals. That's precisely the "semantic"
(maybe "evidence-based"?) explanation that C. Paulin used in her
habilitation thesis to justify recursive definitions and the most general
one for users (it does not even need to be attached to an inductive type).
Equations can derive this subterm relation automatically for (non-mutual,
non-nested) inductive families, and prove its wellfoundedness. Extending
this to the other cases is a matter of thinking and engineering. The Below
predicate of Epigram gives you similar access to every subterm you can
recurse on "logically". The only culprit is reduction behavior/efficiency
using this machinery, but that should be optimizable.

Best,
-- Matthieu

Le mercredi 8 janvier 2014, Andrej Bauer a écrit :

> I would just like to point out that ordinals are an inherently
> classical notion. The correct constructive and computationally
> meaningful replacement is that of a well-founded relation, i.e., a
> relation < on a set X satisfying, for all properties P,
>
>  (forall y, ((forall x < y, P x) -> P y)) -> forall z, P z.
>
> This is all well known, and of course you can recognize the
> recursor/eliminator in the above formula. So if we are to take
> computation seriously, we ought to think about inductive definitions
> which are justified by a more general notion of well foundedness, not
> just ordinals. The ordinals are bound to go wrong when we push them a
> little bit.
>
> Also, the HoTT experience has thought us (at least me) the value of
> semantic notions over syntactic ones. I am referring to HoTT hProp vs.
> CiC Prop. The former delineates the concept of "proposition" with a
> semantic condition, while the latter does it formalistically. It would
> seem sensible to me to go the same route with inductive definitions,
> namely, rely on semantic justifications rather than syntactic ones. [I
> may be misusing the words "semantic" and "syntactic" here, but I
> cannot think of better ones.]
>
> With kind regards,
>
> Andrej
>
> --
> 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 at googlegroups.com <javascript:;>.
> For more options, visit https://groups.google.com/groups/opt_out.
>


-- 
-- Matthieu
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.chalmers.se/pipermail/agda/attachments/20140109/4ba61cd7/attachment.html