Fixed Points on Abstract Structures without the Equality Test

Margarita Korovina

The aim of this talk is to present a study of definability properties of fixed points of effective operators on abstract structures without the equality test. The question of definability of fixed points of Sigma-operators on abstract structures with equality was first studied by Gandy, Barwise, Moschovakis and others. One of the most fundamental theorems in the area is Gandy theorem which states that the least fixed point of any positive Sigma-operator is Sigma-definable. This theorem allows us to treat inductive definitions using Sigma-formulas. Until now there has been no Gandy-type theorem known for such structures. Let us note that in all proofs of Gandy theorem that have been known so far it is the case that even when the definition of a Sigma-operator does not involve equality, the resulting Sigma-formula usually does. We show that Gandy theorem holds for the structures without the equality test, in particular for the real numbers.