Classifications of Definable Subsets

S. Boyadzhiyska*, K. Lange, A. Raz, R. Scanlon, J. Wallbaum, X. Zhang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


Given a structure ℳ over ω and a syntactic complexity class E, we say that a subset is E-definable in ℳ if there exists a C-formula Θ(x) in the language of ℳ such that for all x ∈ ω, we have x ∈ A iff Θ(x) is true in the structure. S. S. Goncharov and N. T. Kogabaev [Vestnik NGU, Mat., Mekh., Inf., 8, No. 4, 23-32 (2008)] generalized an idea proposed by Friedberg [J. Symb. Log., 23, No. 3, 309-316 (1958)], introducing the notion of a E-classification of M: a computable list of E-formulas such that every E-definable subset is defined by a unique formula in the list. We study the connections amongΣ10−, d−Σ10−, and Σ20-classifications in the context of two families of structures, unbounded computable equivalence structures and unbounded computable injection structures. It is stated that every such injection structure has a Σ10−classification, a Σ10−classification, and a Σ20-classification. In equivalence structures, on the other hand, we find a richer variety of possibilities.

Original languageEnglish
Pages (from-to)383-404
Number of pages22
JournalAlgebra and Logic
Issue number5
Publication statusPublished - 1 Nov 2019

Bibliographical note

Publisher Copyright:
© 2019, Springer Science+Business Media, LLC, part of Springer Nature.


  • d−Σ -classification
  • unbounded computable equivalence structure
  • unbounded computable injection structure
  • Σ -classification

ASJC Scopus subject areas

  • Analysis
  • Algebra and Number Theory
  • Logic


Dive into the research topics of 'Classifications of Definable Subsets'. Together they form a unique fingerprint.

Cite this