[FOM] Proof Identity
Milos Adzic
madzic at EUnet.yu
Wed Nov 23 08:29:19 EST 2005
Hello everyone,
I have some questions concerning the identity criteria for proofs
(whether in intuitionistic, classical, BCK or some other logic;
although my focus mainly lies on classical and intuitionistic logic,
and on sequent calculi and natural deduction calculi systems of
deduction for these). I am aware that in the literature there have been
two main (as I find them) proposals. First is the all-well-known
Normalization Conjecture made by Prawitz which says that two derivations
denote the same proof iff they are equivalent (where the equivalence in
question being the reflexive, symmetric and transitive closure of
immediate reducibility relation). Of course the formal system in
question is natural deduction system of Prawitz`s /Natural Deduction/.
Second is the Generality Conjecture, proposed first by Lambek, treated
by Szabo, and, finally, elaborated and characterized with sufficient
precision by Dosen . The conjecture says: Two derivations are
equivalent iff they have the same generality.Two derivations have the
same generality when every generalization of one of them leads to a
generalization of the other, so that in
the two generalizations we have the same assumptions and conclusion.
Generalizations of derivations are considered that diversify variables
without changing the rules of inference.(For details, see Dosen:
"Identity of Proofs based on Normalization and Generality",The Bulletin
of Symbolic Logic, vol. 9 (2003), pp. 477-503).
I skip the technical details of these two conjectures (although, I
presume, the details of the former are well known), knowing that it is
the technical side of the two conjectures that sheds light on the
questions related to the topic; but, there is no great need for that in
this point of time. My question is, simply, what are Your views on these
two conjectures? Do You think they present the important aspects of
proofs represented by derivations in mentioned formal systems (If we
think of systems of deduction mentioned, say Gentzen`s LK(J) and NK(J),
as being the semantics of intuitive mathematical proofs. We can also
think the other way around, as suggested by Kreisel)? And, if You think
that this is not the proper setting for discussing identity of proofs,
what are the main problems that You find with these two conjectures? I
have some second thoughts concerning the first conjecture, but I would
really welcome Your opinion on the topic.
Best wishes.
Milos
More information about the FOM
mailing list