Intrinsically \(\Sigma ^ 0_{\alpha}\) relations
type: Item
instance of: scholarly article
title: Intrinsically \(\Sigma ^ 0_{\alpha}\) relations
zbMATH Open document ID: 0651.03034
DOI: 10.1016/0168-0072(88)90014-0
author: S. H. Smith
published in: Annals of Pure and Applied Logic
publication date: 1988-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 03D45
zbMATH DE Number: 4061222
zbMATH Keywords: recursive structure
zbMATH Keywords: recursive orderings
reviewed by: Leon Harkleroad
MaRDI profile type: Publication
full work available at URL: 0168-0072(88)90014-0
OpenAlex ID: W2087519684
cites work: Stability of recursive structures in arithmetical degrees
cites work: Recursive Labelling Systems and Stability of Recursive Structures in Hyperarithmetical Degrees
cites work: Q3919698
cites work: Q5573961
description: scientific article; zbMATH DE number 4061222