# Intrinsicallygs;0alpha;relations

- Authors
- Journal
- Annals of Pure and Applied Logic 0168-0072
- Publisher
- Elsevier
- Publication Date
- Volume
- 39
- Issue
- 2
- Identifiers
- DOI: 10.1016/0168-0072(88)90014-0
- Disciplines

## Abstract

Abstract A recursive structure A consists of a recursive underlying set vb; A vb;, and recursive relations and operations on vb; A vb;. A new relation on A is called formally Σ 0 α if it has a definition as a certain type of infinitary formula involving the given relations on the structure. It is called intrinsically Σ 0 α if the corresponding relation in any isomorphic recursive structure forms a Σ 0 α set (or set of ordered tuples). In [3] it is shown that given a condition guaranteeing a certain amount of extra decidability in the structure these two notions coincide for the Σ 0 1 (recursively enumerable) case. Here we deal with the analogous result for the general case, for α a constructive ordinal. We give a direct (infinite injury) construction for the case α = 2, together with several examples, which demonstrate that the decidability conditions required are satisfiable in natural examples. Then, applying a theorem of C.J. Ash [1,2], we deal with the general case.

## There are no comments yet on this publication. Be the first to share your thoughts.