Can I read Stability of Recursive Structures in Arithmetical Degrees on EtoBox?

Stability of Recursive Structures in Arithmetical Degrees by C.J. Ash is a Computer Science article available to read on EtoBox.

What is Stability of Recursive Structures in Arithmetical Degrees about?

We say that a recursive structure 92 is A°-stable if, for every recursive structure ~, every isomorphism f: 92--~ is A ° in Kleene's arithmetical hierarchy.Goncharov in has obtained a necessary and sufficient recursive-syntactic condition for a structure 92 to be recursively stable [i.e. A°-stable], under the assumption that the existential diagram of 92 is recursive. This result is also obtained as a corollary in Ash & Nerode . In both cases, the proof uses a finite injury priority argument.We generalize this result by establishing, subject to further assumptions of recursiveness in 92, analogous conditions for 92 to be A°-stable, which we summarize as "92 has a formally A ° enumeration".For A°-stability the proof uses an infinite injury argument and for/t°-stability a 'monstrous' injury argument. We show how this process can be continued for all n. 114 C.J. Ash[The direct construction of recursive copies of (to n, < ) with highly nonrecursive properties is discussed in . The recursive stability of structures such as (o~, +, < ) and (~, +, -, < ) is considered in .]The notion of zl°-stability is to be carefully distinguished from that of zl°-categoricity. We define a recursive str

Who reads Stability of Recursive Structures in Arithmetical Degrees?

Author

C.J. Ash

Published

1986

Language

EN

Field

Computer Science (Physical Sciences)