On the complexity of inductive definitions

摘要

We study the complexity of computable and Sigma(0)(1) inductive definitions of sets of natural numbers. For example, we show how to assign natural indices to monotone Sigma(0)(1)-definitions and then use these to calculate the complexity of the set of all indices of monotone Sigma(0)(1)-definitions that are computable. We also examine the complexity of a new type of inductive definition, which we call weakly finitary monotone inductive definitions. Applications are given in proof theory and in logic programming.