This article is cited in
1 paper
Classifications of definable subsets
S. Boyadzhiyskaa,
K. Langeb,
A. Razc,
R. Scanlon,
J. Wallbaum,
X. Zhangd a Berlin Math. School, Berlin, GERMANY
b Dep. Math., Wellesley College,
106 Central St., Wellesley, MA 02481, USA
c Dep. Math.,
Univ. Nebraska-Lincoln,
210 Avery Hall, Lincoln, NE 68588-0130, USA
d Dep. Philos., Princeton Univ.,
1879 Hall, Princeton, NJ 08544, USA
Abstract:
Given a structure
$\mathcal{M}$ over
$\omega$ and a syntactic
complexity class
$\mathfrak{C}$, we say that a subset
$A$ is
$\mathfrak{C}$-definable in
$\mathcal{M}$ if there exists a
$\mathfrak{C}$-formula
$\Theta(x)$ in the language of
$\mathcal{M}$
such that for all
$x\in\omega$, we have
$x \in A$ iff
$\Theta(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
$\mathfrak{C}$-classification of
$\mathcal{M}$: a
computable list of
$\mathfrak{C}$-formulas such that every
$\mathfrak{C}$-definable subset is defined by a unique formula in
the list. We study the connections among
$\Sigma_1^0$-,
$d$-
$\Sigma_1^0$-, and
$\Sigma_2^0$-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
$\Sigma_1^0$-classification, a
$d$-
$\Sigma_1^0$-classification, and a
$\Sigma_2^0$-classification. In equivalence structures, on the other
hand, we find a richer variety of possibilities.
Keywords:
$\Sigma_1^0$-classification, $d$-$\Sigma_1^0$-classification,
$\Sigma_2^0$-classification, unbounded computable equivalence
structure, unbounded computable injection structure.
UDC:
510.54 Received: 08.05.2018
Revised: 26.11.2019
DOI:
10.33048/alglog.2019.58.502