The Power of the Depth of Iteration in Defining Relations by Induction

Abstract

In this paper we provoke the question of whether the sequence ... is strictly increasing, i.e., the question of whether increasing the depth of iteration increases the expressive power of defining by induction. Solving this question should have a deep impact on computer science as well as on mathematical logic since it is a question in a subject on the crossroads between them, namely, descriptive complexity. We shall mention a potential way of tackling the problem.