A computable structure with non-standard computability

R. R. Avdeev^a, V. G. Puzarenko<sup>ab

a</sup> Novosibirsk State University, Novosibirsk, 630090 Russia
^b Sobolev Institute of Mathematics, Novosibirsk, 630090 Russia

Abstract: We find an example of a computable admissible set whose level of computability is higher than that of the standard model of Peano arithmetic. As a byproduct, we construct a $1$ model of an undecidable submodel complete theory.

Key words: admissible set, hyperadmissible set, hereditarily finite superstructure, recursively saturated model, computable model, decidable model, $\Sigma$-reducibility, $\Sigma$-definability.

UDC: 510.5

Received: 13.09.2017

DOI: 10.17377/mattrudy.2018.21.201

 English version: Siberian Advances in Mathematics, 2019, 29:2, 77–115

Bibliographic databases:

•