Division of Informatics
Forrest Hill & 80 South Bridge

Research Paper #560
Title:	On the Use of the Constructive Omega-Rule Within Automated Deduction
Authors:	Baker,S; Ireland,A; Smaill,AD
Date:	1991
Presented:	Submitted to CADE-11, 1991
Keywords:
Abstract:	The cut elimination theorem for predicate calculus states that every proof may be replaced by one which does not involve use of the cut rule. This theorem no longer holds when the system is extended with Peano's axioms to give a formalisation for arithmetic. The problem of generalisation results, since arbitrary formulae can be cut in. This makes theorem-proving very difficult - one solution is to embed arithmetic in a stronger system, where cut elimination holds. ........ This paper describes a system based on the omega rule, and shows that certain statements are provable in this system which are not provable in Peano arithmetic without cut. Moreover, an important application is presented in the form of a new method of generalisation by means of "guiding proofs" in the stronger system, which sometimes succeeds in producing proofs in the original system when other methods fail. The implementation of such a system is also described.
Download:	POSTSCRIPT COPY

Division of InformaticsForrest Hill & 80 South Bridge