[Agda] Proof irrelevance and self-realizing formulas
Shin-Cheng Mu
scm at iis.sinica.edu.tw
Fri May 29 10:24:22 CEST 2009
Hi,
I've been eavesdropping this interesting discussion for 2 days,
while building up courage to interrupt and ask novice questions
again... :)
Is what I say below correct?
There are now at least 3 interpretations of "proof irrelevance"
I have heard of:
1. The CC/Coq approach. Prop is impredicative and therefore,
in any set theoretic model, Prop could have only one
member -- *.
Therefore not only proofs of equal propositions are equal,
but all proofs are equal. Some work went to length
(e.g. [1]) talking about unifying (\x -> *) and *.
I think it is under this interpretation that I can
prove the law of excluded middle [2], is it?
(If I take equality on propositions to be "if and only if".)
2. The Conor/Thorsten/OTT approach. Prop is embedded into Set
in the usual way -- Sigma for conjunction, Pi for implication, etc.
Proofs of the same proposition are equal, but not all proofs are *.
Is it only in this interpretation that we'd better not have
disjunction in Prop, to avoid having two proofs of P \/ P?
3. Prop and Set live in separate spaces, mainly to distinguish
computationally interesting parts from uninteresting parts
of a program/proof. Quoting Andrej:
"Anything that can be computed using a proof p : P, can also be
computed without it."
Is this interpretation mostly correlated with 1.?
sincerely,
Shin
[1] A. Miquel and B. Werner. The not so simple proof-irrelevant
model of CC.
[2] A blog post of mine
http://www.iis.sinica.edu.tw/~scm/?p=133
with information assembled from various places...
More information about the Agda
mailing list