Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Coq has a type Prop of proof irrelevant propositions which are discarded during extraction. What are the reason for having this if we use Coq only for proofs. Prop is impredicative, so Prop : Prop, however, Coq automatically infers universe indexes and we can use Type(i) instead everywhere. It seems Prop complicates everything a lot.

I read that there're philosophical reasons for separating Set and Prop in Luo's book, however, I didn't find them in the book. What are they?

share|improve this question
4  
“if we use Coq only for proofs”: I think you've identified a key point here. Coq isn't used only for proofs. –  Gilles Mar 31 at 14:48
add comment

3 Answers 3

up vote 4 down vote accepted

$\mathrm{Prop}$ is impredicative, which create a very expressive proof system. However it is "too" expressive in the following sense:

$$ \mathrm{impredicative\ Prop} + \mathrm{large\ elimination} + \mathrm{excluded\ middle} $$

is inconsistent. Usually you want to keep the possibility to add the excluded middle, so one solution is to keep large elimination and make Prop predicative. The other is to suppress large elimination.

Coq did both! They renamed the predicative Prop to Set, and disabled large elimination in Prop.

The expressiveness gained by impredicativity is "reassuring" in the sense 99% of "reasonable" mathematics can be formalized with it, and it is known to be consistent relative to set theory. This makes it likely they won't weaken it to something like Agda, which only has predicative universes.

share|improve this answer
1  
Oh and I forgot to mention: it is not the case that Prop : Prop, that would be inconsistent. Rather quantifications over all propositions is again a proposition. –  cody Apr 1 at 21:31
add comment

$\mathtt{Prop}$ is very useful for program extraction because it allows us to delete parts of code that are useless. For example, to extract a sorting algorithm we would prove the statement "for every list $\ell$ there is a list $k$ such that $k$ is ordered and $k$ is a permutatiom of $\ell$". If we write this down in Coq and extract without using $\mathtt{Prop}$, we will get:

  1. "for all $\ell$ there is $k$" will give us a map sort which takes lists to lists,
  2. "such that $k$ is ordered" will give a funciton verify which runs through $k$ and checks that it is sorted, and
  3. "$k$ is a permutation of $\ell$" will give a permutation pi which takes $\ell$ to $k$. Note that pi is not just a mapping, but also the inverse mapping together with programs verifying that the two maps really are inverses.

While the extra stuff is not totally useless, in many applications we want to get rid of it and keep just sort. This can be accomplished if we use $\mathtt{Prop}$ to state "$k$ is ordered" and "$k$ is a permutation of $\ell$", but not "for all $\ell$ there is $k$".

In general, a common way to extract code is to consider a statement of the form $\forall x : A \,.\, \exists y : B \,.\, \phi(x, y)$ where $x$ is input, $y$ is output, and $\phi(x,y)$ explains what it means for $y$ to be a correct output. (In the above example $A$ and $B$ are the types of lists and $\phi(\ell, k)$ is "$k$ is ordered and $k$ is a permutation of $\ell$.") If $\phi$ is in $\mathtt{Prop}$ then extraction gives a map $f : A \to B$ such that $\phi(x, f(x))$ holds for all $x \in A$. If $\phi$ is in $\mathtt{Set}$ then we also get a function $g$ such that $g(x)$ is the proof that $\phi(x, f(x))$ holds, for all $x \in A$. Often the proof is computationally useless and we prefer to get rid of it, especially when it is nested deeply inside some other statement. $\mathtt{Prop}$ gives us the possibility to do so.

share|improve this answer
add comment

Even if you are not interested in extracting programs, the fact that Prop is impredicative allows you to build some models which you can't build using a predicative tower of universes. IIRC Thorsten Altenkirch has a model of System F using Coq's impredicativity.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.