^{1} Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University^{2} unknown

Abstract:

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 -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 at least fixed point of any positive -operator is -definable. This theorem allows us to treat inductive definitions using -formulas. Until now there has been no Gandy-type theorem known for abstract structures without the equality text. 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 -operator does not involve equality, the resulting -formula usually does. We show that Gandy theorem holds for the structures without the equality test, in particular for the real numbers. 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 -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 -predicates. It leads to a topological characterisation of -relations on