Lambda Calculus,Conservative Extension and Structural Induction

The issue of whether embedding algebraic theories in higher-order theories such as the simply typed and polymorphic lambda calculi is of interest in programming language design. The establishment of such a conservative extension result permits modularity in the verification of the correctness of datatype and function implementations. In earlier work [Breazu-Tannen & Meyer 1987a], [Breazu-Tannen & Meyer 1987b] and [Breazu-Tannen 1988], conservative extension results have been obtained for algebraic theories. However, in modelling inductive datatypes, the principle of structural induction needs to be admitted in the inference system, and the question of whether conservative extension holds in the presence of the principle of structural induction needs to be addressed. In this paper we look at the question of whether inductive algebraic theories are conservatively extended when embedded in the simply typed lambda calculus.