The aim of this paper is to enrich the algebraic-axiomatic approach to recursion theory developed in [1] by an analogue to the classical arithmetical hierarchy and an abstract notion of degree. The results presented here are rather initial and elementary; indeed, the main problem was the very choice of right abstract concepts.

We study logical systems for reasoning about equations involving recursive definitions. In particular, we are interested in "propositional" fragments of the functional language of recursion FLR [18, 17], i.e., without the value passing or abstraction allowed in FLR. The "pure," propositional fragment FLR 0 turns out to coincide with the iteration theories of [1]. Our main focus here concerns the sharp contrast between the simple class of valid identities and the very complex consequence relation over several natural classes of models.