Hostname: page-component-6bf8c574d5-9nwgx Total loading time: 0 Render date: 2025-02-21T00:30:46.952Z Has data issue: false hasContentIssue false
  • English
  • Français

On the complexity of inductive definitions

Published online by Cambridge University Press:  11 October 2006

DOUGLAS CENZER  and
JEFFREY B. REMMEL
DOUGLAS CENZER
Affiliation:
Department of Mathematics, University of Florida, P.O. Box 118105, Gainesville, Florida 32611, U.S.A.
JEFFREY B. REMMEL
Affiliation:
Department of Mathematics, University of California at San Diego, La Jolla, CA 92093, U.S.A.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 16 , Issue 5 , October 2006 , pp. 763 - 788
Copyright
2006 Cambridge University Press