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 |