Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
Generalized Hyperarithmetical Computability Over Structures. / Stukachev, A. I.
в: Algebra and Logic, Том 55, № 6, 01.01.2017, стр. 507-526.Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
}
TY - JOUR
T1 - Generalized Hyperarithmetical Computability Over Structures
AU - Stukachev, A. I.
N1 - Publisher Copyright: © 2017, Springer Science+Business Media New York.
PY - 2017/1/1
Y1 - 2017/1/1
N2 - We consider the class of approximation spaces generated by admissible sets, in particular by hereditarily finite superstructures over structures. Generalized computability on approximation spaces is conceived of as effective definability in dynamic logic. By analogy with the notion of a structure Σ-definable in an admissible set, we introduce the notion of a structure effectively definable on an approximation space. In much the same way as the Σ-reducibility relation, we can naturally define a reducibility relation on structures generating appropriate semilattices of degrees of structures (of arbitrary cardinality), as well as a jump operation. It is stated that there is a natural embedding of the semilattice of hyperdegrees of sets of natural numbers in the semilattices mentioned, which preserves the hyperjump operation. A syntactic description of structures having hyperdegree is given.
AB - We consider the class of approximation spaces generated by admissible sets, in particular by hereditarily finite superstructures over structures. Generalized computability on approximation spaces is conceived of as effective definability in dynamic logic. By analogy with the notion of a structure Σ-definable in an admissible set, we introduce the notion of a structure effectively definable on an approximation space. In much the same way as the Σ-reducibility relation, we can naturally define a reducibility relation on structures generating appropriate semilattices of degrees of structures (of arbitrary cardinality), as well as a jump operation. It is stated that there is a natural embedding of the semilattice of hyperdegrees of sets of natural numbers in the semilattices mentioned, which preserves the hyperjump operation. A syntactic description of structures having hyperdegree is given.
KW - admissible sets
KW - approximation spaces
KW - computability theory
KW - computable analysis
KW - constructive models
KW - hyperarithmetical computability
KW - PRESENTABILITY
UR - http://www.scopus.com/inward/record.url?scp=85014996007&partnerID=8YFLogxK
U2 - 10.1007/s10469-017-9421-1
DO - 10.1007/s10469-017-9421-1
M3 - Article
AN - SCOPUS:85014996007
VL - 55
SP - 507
EP - 526
JO - Algebra and Logic
JF - Algebra and Logic
SN - 0002-5232
IS - 6
ER -
ID: 10274243