[Agda] Proof irrelevance and self-realizing formulas
wren ng thornton
wren at freegeek.org
Thu May 28 04:59:16 CEST 2009
Thorsten Altenkirch wrote:
> Hi Andrej,
>
> > Let us temporarily forget the interpretation
> >
> > "P is proof irrelevant" = "all proofs of P are equal"
> >
> > because we don't like equality of proofs.
>
> Why?
I believe that's a presupposition: people who care about
proof-irrelevance are people who don't like equality of proofs.
At least that's the case for all the discussions I've seen on the topic.
The need to discuss or determine (in)equality between different proofs
of the same theorem can lead to difficulties. The desire for
proof-irrelevance is the desire to escape those difficulties, which
means finding some way of abandoning proof equality.
> > An alternative
> > interpretation of "P is proof irrelevant" is:
> >
> > "Anything that can be computed using a proof p : P, can also be
> > computed without it."
> >
> > The extreme case of this is that an inhabitant of P can be computed
> > without using p, i.e., an inhabitant of P can be constructed out of
> > thin air, provided P has inhabitants.
>
> How do we explain that we are using the fact that p has inhabitants w.o.
> looking at them?
>
> I mean this is exactly what is achieved by saying P has at most one
> proof, hence there is no information in knowing that proof.
That's the idea. The difficulties mentioned above happen because we *do*
have information in knowing the proof, but we don't want it (we only
want to know *that* P is inhabited, without knowing how or by what).
Proof-irrelevance is a way of erasing that information, which in turn
erases a lot of fiddly details.
--
Live well,
~wren
More information about the Agda
mailing list