Abstract

It is shown that over any countable first-order structure, IND programs with dictionaries accept exactly the Π 1 1 relations. This extends a result of Harel and Kozen 118) relating IND and Π 1 1 over countable structures with some coding power, and provides a computational analog of a result of Barwise et al. 108) relating the Π 1 1 relations on a countable structure to a certain family of inductively definable relations on the hereditarily finite sets over that structure