|
This article is cited in 13 scientific papers (total in 13 papers)
Degrees of presentability of structures. II
A. I. Stukachev Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences
Abstract:
We show that the property of being locally constructivizable is inherited under Muchnik reducibility, which is weakest among the effective reducibilities considered over countable structures. It is stated that local constructivizability of level higher than 1 is inherited under $\Sigma$-reducibility but is not inherited under Medvedev reducibility. An example of a structure $\mathfrak M$ and a relation $P\subseteq M$ is constructed for which $\underline{(\mathfrak M,P)}\equiv\underline{\mathfrak M}$ but $(\mathfrak M,P)\not\equiv_\Sigma\mathfrak M$. Also, we point out a class of structures which are effectively defined by a family of their local theories.
Keywords:
admissible set, semilattice of degrees of $\Sigma$-definability.
Received: 23.08.2006
Citation:
A. I. Stukachev, “Degrees of presentability of structures. II”, Algebra Logika, 47:1 (2008), 108–126; Algebra and Logic, 47:1 (2008), 65–74
Linking options:
https://www.mathnet.ru/eng/al349 https://www.mathnet.ru/eng/al/v47/i1/p108
|
|