Title: Degrees of Presentability of Structures. II

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.

PDF (Russian)
PDF (English)