A Type Theory with Partially Defined Functions

Only can totally defined functions be introduced in conventional dependently typed systems and such functions are normally defined by eliminators. Because of the limitation of the elimination rules, many (mathematical) functions cannot be defined in these systems. This paper argues that the restriction of totality is unnecessary, and proposes a type theory that allows partially defined functions. In this type theory, functions can be introduced by means of pattern matching. It is in general undecidable in dependently typed systems whether patterns cover all the canonical objects of a type, and it is one of the big problems for implementation. Without the restriction of totality, we don't have such problem of totality checking, and hence we have more flexibility to introduce functions than we do in conventional type systems.