[HoTT] Re: [Agda] Higher inductive-recursive definitions?
Peter LeFanu Lumsdaine
p.l.lumsdaine at gmail.com
Sat May 24 13:13:22 CEST 2014
Actually, if I am not mistaken, this is not a problem after all — because
one has to also add a corresponding extra clause for eqU in the recursive
definition of El, which one adds as
ap El (eqU p) == p
and from this, one can prove that El is an equivalence on paths. (Thorsten
and I have been discussing this in a little more detail off-list; I think
he will be posting a longer follow-up email later.)
–p.
On Fri, May 23, 2014 at 5:27 PM, Guillaume Brunerie <
guillaume.brunerie at gmail.com> wrote:
> Hi Thorsten,
>
> I don't know about the elimination rule, but I just wanted to point out
> that you won't get a univalent universe in this way because eqU refl and
> refl won't be identified, and similarly for concat (eqU p) (eqU q) and eqU
> (concat p q).
> And the obvious way to fix requires something like defining
> semi-simplicial types internally...
>
> Guillaume
> Le 23 mai 2014 15:23, "Altenkirch Thorsten" <
> psztxa at exmail.nottingham.ac.uk> a écrit :
>
>> I would like to combine higher inductive definitions (I.e. have path
>> constructors) with induction-recursion. One application would be to define
>> a closed universe which is univalent. However, I cannot see any reasonable
>> way to define an eliminator.
>>
>> Ok, I start with a simple universe(using Agda) - an inductive recursive
>> definition
>>
>> data U : Set
>> El : U -> Set
>>
>> data U where
>> nat : U
>> pi : (a : U)(b : El a -> U) -> U
>>
>> El nat = Nat
>> El (pi a b) = (x : El a) -> El (b x)
>>
>> Now I can define an eliminator for the universe which allows me to define
>> dependent functions by recursion over type codes:
>>
>> ElimU : (X : U -> Set)
>> -> (X nat)
>> -> ((a : U) -> X a -> (b : El a -> U) -> ((x : El a) -> X (b x))
>> -> X (pi a b))
>> -> (a : U) -> X a
>> ElimU X n p nat = n
>> ElimU X n p (pi a b) = p a (ElimU X n p a) b (λ x -> ElimU X n p (b x))
>>
>> However, I also would like to add a path constructor, which identifies
>> codes if the have the same semantics:
>>
>> postulate
>> eqU : forall {a b} -> El a == El b -> a == b
>>
>> But I don't see a good way to modify the Eliminator. It seems that this
>> corresponds to a condition on the eliminator as a whole.
>>
>> An alternative is to quotient the universe afterwards. However, the
>> problem is that in this case I cannot lift the pi constructor to the
>> quotiented universe – the usual problem when quotienting infinitary
>> constructors. This can usually be overcome by defining the path
>> constructors mutually..
>>
>> Any ideas? Maybe the whole thing doesn't make sense semantically?
>>
>> Thorsten
>>
>> This message and any attachment are intended solely for the addressee and
>> may contain confidential information. If you have received this message in
>> error, please send it back to me, and immediately delete it. Please do
>> not use, copy or disclose the information contained in this message or in
>> any attachment. Any views or opinions expressed by the author of this
>> email do not necessarily reflect the views of the University of Nottingham.
>>
>> This message has been checked for viruses but the contents of an
>> attachment may still contain software viruses which could damage your
>> computer system, you are advised to perform your own checks. Email
>> communications with the University of Nottingham may be monitored as
>> permitted by UK legislation.
>>
>>
>> _______________________________________________
>> Agda mailing list
>> Agda at lists.chalmers.se
>> https://lists.chalmers.se/mailman/listinfo/agda
>>
>> --
> 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.
> For more options, visit https://groups.google.com/d/optout.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.chalmers.se/pipermail/agda/attachments/20140524/4fa66721/attachment.html
More information about the Agda
mailing list