Intrinsically \(\Sigma ^ 0_{\alpha}\) relations (Q1106203): Difference between revisions

A relation R on a recursive structure \({\mathfrak A}\) is called intrinsically \(\Sigma^ 0_{\alpha}\) if under every Gödel numbering of \({\mathfrak A}\) as a recursive structure, R is represented by a \(\Sigma^ 0_{\alpha}\) set. Ash and Nerode had found, under certain side conditions, a syntactic characterization of the intrinsically \(\Sigma^ 0_ 1\) relations on a structure. The present paper generalizes that result to an arbitrary constructive ordinal \(\alpha\). Several examples, many of them related to recursive orderings, are presented.