Generalized Hyperarithmetical Computability Over Structures

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)507-526
Number of pages20
JournalAlgebra and Logic
Volume55
Issue number6
DOIs
Publication statusPublished - 1 Jan 2017

Keywords

  • admissible sets
  • approximation spaces
  • computability theory
  • computable analysis
  • constructive models
  • hyperarithmetical computability
  • PRESENTABILITY

Fingerprint

Dive into the research topics of 'Generalized Hyperarithmetical Computability Over Structures'. Together they form a unique fingerprint.

Cite this