[Agda] Big indices for small types?

Thorsten Altenkirch txa at Cs.Nott.AC.UK
Mon Sep 1 15:08:46 CEST 2008


Hi Peter,

> Have you got a consistency proof (relative to set theory)?

Actually, it should be possible to model this in the calculus of  
constructions + universes (ECC). However, it seems to me that you  
would need the impredicative universe on top of the predicative  
hierarchy. But I think this is equivalent, isn't it?

I am suggesting to use Leibniz equality, I don't think that the  
inductive characterisation adds any strength.

> I don't have anything specific to say about your definition, except  
> that
> it goes against certain
> intuitions about "predicativity" (relating to concepts such as  
> "before",
> "after", "below", and "above").
> However, to me "predicativity" is a subjective notion, it's all in  
> your
> own mind, and not an objective concept, which is what really counts.

Ouch! Are there any "objective concepts" in Mathematics? I had the  
impression this has all to do with our mind. Isn't this what  
intuitionism is all about? I didn't know that you had become a bold  
Platonist?

Objective concepts: Kronecker suggested the natural numbers, otherwise  
you have to believe in some higher authority. Even the natural numbers  
are not really objective but based on a very broad agreement. My  
understanding of intuitionism (and hence predicativity) was that we  
carefully try to extend this agreement.

Classical reasoning is not based on "objective concepts" but on the  
assumption that "anything goes" unless somebody has fund a  
contradiction. Personally, I find this not only interlectually less  
satisfying than the intuitionist approach but also pragmatically less  
helpful, since a careful intuitionistic analysis often leads to better  
theories, imho.

> I propose the following plan of action when adding a new  
> construction to
> Martin-Löf type theory (Agda).
>
> 1. Prove it consistent relative to set theory
> 2. Give an informal but careful analysis why it is constructive,  
> that is,
> why it satisfies Martin-Löf's style meaning explanations.
> 3. Prove normalization and decidability of type-checking for the  
> extended
> system.

it seems we may have trouble at step 2.

Cheers,
Thorsten

> It's probably also important to have a good motivating example.
>
> Cheers,
> Peter
>
>> Just fiddling about with some ideas about stratification
>> and wondering if anyone has anything substantial to say
>> about definitions like
>>
>>   data EQ (S : Set1) : Set1 -> Set where
>>     REFL : EQ S S
>>
>> On the one hand, this doesn't exactly fit with the idea
>> of building the hierarchy up from below. On the other
>> hand, it doesn't actually store any big things inside
>> any small things.
>>
>> Of course, Agda 2's
>>
>>   data BEFORE : AFTER -> Set
>>
>> distinction isn't the usual parameter/index distinction,
>> as shown
>>
>>   data Lam (X : Set) : Set where
>>     var : X -> Lam X
>>     app : Lam X -> Lam X -> Lam X
>>     lam : Lam (Maybe X) -> Lam X
>>
>> Sizewise, it seems that anything goes as long as there's
>> no large payload.
>>
>> Is this well understood?
>>
>> Scares me.
>>
>> Cheers
>>
>> Conor
>>
>> _______________________________________________
>> Agda mailing list
>> Agda at lists.chalmers.se
>> https://lists.chalmers.se/mailman/listinfo/agda
>>
>
>
> _______________________________________________
> Agda mailing list
> Agda at lists.chalmers.se
> https://lists.chalmers.se/mailman/listinfo/agda


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.



More information about the Agda mailing list