RUS  ENG
Full version
JOURNALS // Algebra i logika // Archive

Algebra Logika, 2008 Volume 47, Number 1, Pages 108–126 (Mi al349)

This article is cited 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.

UDC: 510.5

Received: 23.08.2006


 English version:
Algebra and Logic, 2008, 47:1, 65–74

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024