This article is cited in 5 papers

Mathematical logic, algebra and number theory

Undecidability of elementary theory of Rogers semilattices in analytical hierarchy

M. V. Dorzhieva

Novosibirsk State University, st. Pirogova, 2 630090, Novosibirsk, Russia

Abstract: We prove that the elementary theory of any nontrivial Rogers semilattice for analytical sets of bounded complexity is hereditarily undecidable. We also prove some results on the existence of minimal numberings in such lattices.

Keywords: analitycal hierarchy, computable numberings, minimal numberings, Rogers semilattices.

UDC: 512.5

MSC: 13A99

Received April 10, 2014, published March 16, 2016

DOI: 10.17377/semi.2016.13.013

Bibliographic databases:

•