Generalized Hyperarithmetical Computability Over Structures

Standard

Generalized Hyperarithmetical Computability Over Structures. / Stukachev, A. I.

In: Algebra and Logic, Vol. 55, No. 6, 01.01.2017, p. 507-526.

Research output: Contribution to journal › Article › peer-review

Harvard

Stukachev, AI 2017, 'Generalized Hyperarithmetical Computability Over Structures', Algebra and Logic, vol. 55, no. 6, pp. 507-526. https://doi.org/10.1007/s10469-017-9421-1

APA

Stukachev, A. I. (2017). Generalized Hyperarithmetical Computability Over Structures. Algebra and Logic, 55(6), 507-526. https://doi.org/10.1007/s10469-017-9421-1

Vancouver

Stukachev AI. Generalized Hyperarithmetical Computability Over Structures. Algebra and Logic. 2017 Jan 1;55(6):507-526. doi: 10.1007/s10469-017-9421-1

Author

Stukachev, A. I. / Generalized Hyperarithmetical Computability Over Structures. In: Algebra and Logic. 2017 ; Vol. 55, No. 6. pp. 507-526.

BibTeX

@article{7b83d5119f084a4ea822098c8d174f59,

title = "Generalized Hyperarithmetical Computability Over Structures",

abstract = "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.",

keywords = "admissible sets, approximation spaces, computability theory, computable analysis, constructive models, hyperarithmetical computability, PRESENTABILITY",

author = "Stukachev, {A. I.}",

note = "Publisher Copyright: {\textcopyright} 2017, Springer Science+Business Media New York.",

year = "2017",

month = jan,

day = "1",

doi = "10.1007/s10469-017-9421-1",

language = "English",

volume = "55",

pages = "507--526",

journal = "Algebra and Logic",

issn = "0002-5232",

publisher = "Springer US",

number = "6",

}

RIS

TY - JOUR

T1 - Generalized Hyperarithmetical Computability Over Structures

AU - Stukachev, A. I.

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