[TYPES] Y-combinator in Type:Type?

[Thorsten Altenkirch]

Actually, the initial PTS (Type : Type) has got no identity types but  
only Pi-types. However, we can encode an equality type using the usual  
"Leibniz encoding"

Eq : (A:Type) -> A -> A -> Type
Eq A a b = Pi P:A -> Type.P a -> P b

and this behaves like intensional equality actually worse: we cannot  
even show that equality is a groupoid (actually using eta we can show  
that it is a category but the laws involving symmetry require  
parametricity, I think).

If you add W-types with the normal elimination principle you get a  
fixpoint combinator (See Thierry's paper on the paradox of Trees).  
That's maybe cheaper then extensional equality (depending on your  
currency). The problem is that the impredicative encodings don't give  
you primitive recursion but only iteration - I'd say.

Cheers,
Thorsten

On 16 May 2008, at 16:41, Thomas Streicher wrote:

> [ The Types Forum, http://lists.seas.upenn.edu/mailman/listinfo/types-list 
>  ]
>
> But if you have Type:Type together with extensional identity types  
> then
> every type X is equal to X->X and thus provides a model for untyped
> lambda calculus and thus allows one to write down an Y-combinator of  
> type X.
>
> So the problem is open because of intensional identity types, isn't  
> it?
>
> Thomas


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.