Proof theory of higher-order equations: conservativity, normal forms and term rewriting
✍ Scribed by K. Meinke
- Publisher
- Elsevier Science
- Year
- 2003
- Tongue
- English
- Weight
- 393 KB
- Volume
- 67
- Category
- Article
- ISSN
- 0022-0000
No coin nor oath required. For personal study only.
✦ Synopsis
We introduce a necessary and sufficient condition for the o-extensionality rule of higher-order equational logic to be conservative over first-order many-sorted equational logic for ground first-order equations. This gives a precise condition under which computation in the higher-order initial model by term rewriting is possible. The condition is then generalised to characterise a normal form for higherorder equational proofs in which extensionality inferences occur only as the final proof inferences. The main result is based on a notion of observational equivalence between higher-order elements induced by a topology of finite information on such elements. Applied to extensional higher-order algebras with countable first-order carrier sets, the finite information topology is metric and second countable in every type.