[Agda] Proof irrelevance and self-realizing formulas
James McKinna
james.mckinna at cs.ru.nl
Fri May 29 10:09:08 CEST 2009
Hank,
>
> What I'm picking up from this nice discussion is the difference
> between a proof being computationally uninteresting, and intellectually
> interesting. I understand that Alex Wilkie has spent a lot of his
> considerable intellectual energy in figuring out whether Wiles' proof
> of Fermat's Last Theorem can be coded in Peano Arithmetic. Perhaps
> we should put him out of his misery and tell him it is just \x.*,
> and can be written in a very small fragment of PA?
>
To reiterate an earlier point: proof irrelevance a la Conor Thorsten for
Wiles would *not* mean that the proof is just \x.*
It means that every proof you might find of Wiles is equal to \x.p,
where p is "one" of the possible proofs. The term * need *not* be one of
them (perhaps it is consistent, albeit troubling for decidable
typechecking, to assert that it is).
But to know any one of such p (and hence all of them, because they would
then be identified), we need to do more work than simply assert "p=*"
and let the poor old typechecker try to check whether * has the claimed
type.
Maybe Andrej's RZ interpretation would allows us to claim that p=* would
do, but I imagine you still have to know a proposition phi is *true*
before you can assert that * realises it.
Can we agree to distinguish
P:Prop, p,q:P |- p = q:P
from
P,Q:Prop, p:P, q:Q |- P=Q:Prop
as, respectively "proof irrelevance" and "strong proof irrelevance" (or
some other terminology). Categorically- (and esp. topos-) minded people
seem to favour the latter principle (all true propositions are (equal
to) True) from the former, which is (clearly?!) weaker... and what I
think we have up till now been discussing (or getting confused about).
James.
More information about the Agda
mailing list