首页 | 本学科首页   官方微博 | 高级检索  
     检索      


How to assign ordinal numbers to combinatory terms with polymorphic types
Authors:William R Stirton
Institution:1. Department of Philosophy, University of Edinburgh, 3 Charles Street, Edinburgh, EH8 9AD, UK
Abstract:The article investigates a system of polymorphically typed combinatory logic which is equivalent to G?del’s T. A notion of (strong) reduction is defined over terms of this system and it is proved that the class of well-formed terms is closed under both bracket abstraction and reduction. The main new result is that the number of contractions needed to reduce a term to normal form is computed by an ε 0-recursive function. The ordinal assignments used to obtain this result are also used to prove that the system under consideration is indeed equivalent to G?del’s T. It is hoped that the methods used here can be extended so as to obtain similar results for stronger systems of polymorphically typed combinatory terms. An interesting corollary of such results is that they yield ordinally informative proofs of normalizability for sub-systems of second-order intuitionist logic, in natural deduction style.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号