Affordable Access

Publisher Website

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
  • Mathematics

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.