An intensional type theory: motivation and cut-elimination Export

@article{citeulike:323065, abstract = {Abstract. By the theory TT is meant the higher order predicate logic with the following recursively defined types: (1) 1 is the type of individuals and [] is the type of the truth values; (2) [τ1 , . . . , τn ] is the type of the predicates with arguments of the types τ1 , . . . , τn . The theory ITT described in this paper is an intensional version of TT. The types of ITT are the same as the types of TT, but the membership of the type 1 of individuals in ITT is an extension of the membership in TT. The extension consists of allowing any higher order term, in which only variables of type 1 have a free occurrence, to be a term of type 1. This feature of ITT is motivated by a nominalist interpretation of higher order predication. In ITT both well-founded and non-well-founded recursive predicates can be defined as abstraction terms from which all the properties of the predicates can be derived without the use of non-logical axioms. The elementary syntax, semantics, and proof theory for ITT are defined. A semantic consistency proof for ITT is provided and the completeness proof of Takahashi and Prawitz for a version of TT without cut is adapted for ITT; a consequence is the redundancy of cut.}, author = {Gilmore, Paul C.}, citeulike-article-id = {323065}, citeulike-linkout-0 = {http://www.cs.ubc.ca/spider/gilmore/jslnewtypeset.pdf}, comment = {This may have some connection with staged programming. }, journal = {Journal of Symbolic Logic}, keywords = {logic, type-theory}, posted-at = {2005-09-17 03:51:39}, priority = {2}, title = {An intensional type theory: motivation and cut-elimination}, url = {http://www.cs.ubc.ca/spider/gilmore/jslnewtypeset.pdf} }

TY - JOUR ID - citeulike:323065 L3 - citeulike-article-id:323065 N2 - Abstract. By the theory TT is meant the higher order predicate logic with the following recursively defined types: (1) 1 is the type of individuals and [] is the type of the truth values; (2) [τ1 , . . . , τn ] is the type of the predicates with arguments of the types τ1 , . . . , τn . The theory ITT described in this paper is an intensional version of TT. The types of ITT are the same as the types of TT, but the membership of the type 1 of individuals in ITT is an extension of the membership in TT. The extension consists of allowing any higher order term, in which only variables of type 1 have a free occurrence, to be a term of type 1. This feature of ITT is motivated by a nominalist interpretation of higher order predication. In ITT both well-founded and non-well-founded recursive predicates can be defined as abstraction terms from which all the properties of the predicates can be derived without the use of non-logical axioms. The elementary syntax, semantics, and proof theory for ITT are defined. A semantic consistency proof for ITT is provided and the completeness proof of Takahashi and Prawitz for a version of TT without cut is adapted for ITT; a consequence is the redundancy of cut. JF - Journal of Symbolic Logic TI - An intensional type theory: motivation and cut-elimination KW - logic KW - type-theory N1 - This may have some connection with staged programming. AU - Gilmore, Paul UR - http://www.cs.ubc.ca/spider/gilmore/jslnewtypeset.pdf ER -