Fixed Points on Abstract Structures without the Equality Test

Margarita Korovina

June 2002


In this paper we present a study of definability properties of fixed points of effective operators on abstract structures without the equality test. In particular we prove that Gandy theorem holds for abstract structures. This provides a useful tool for dealing with recursive definitions using $\Sigma$-formulas.

One of the applications of Gandy theorem in the case of the reals without the equality test is that it allows us to define universal $\Sigma$-predicates. It leads to a topological characterisation of $\Sigma$-relations on ${\rm I\!R}$

Available as PostScript, PDF, DVI.


Last modified: 2003-07-18 by webmaster.