RUS  ENG
Full version
JOURNALS // Sibirskii Matematicheskii Zhurnal // Archive

Sibirsk. Mat. Zh., 2004 Volume 45, Number 3, Pages 634–652 (Mi smj1096)

This article is cited in 16 papers

On the relation of $\Sigma$-reducibility between admissible sets

A. S. Morozov

Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences

Abstract: Reducibility on admissible sets is studied which is a stronger version of the usual $\Sigma$-presentability of models. One of its informal prototypes is the interpretability of one computational device in the other. We obtain criteria of reducibility for recursively listed and pure sets, introduce the notion of jump, and prove exact boundaries for the ordinals of jumps. We also show that this reducibility is lifted to $\mathbb{HYP}$-superstructures. Several results are proven on the relations of this reducibility to some known reducibilities.

Keywords: definability, computability, reducibility, admissible set.

UDC: 510.56

Received: 24.06.2003


 English version:
Siberian Mathematical Journal, 2004, 45:3, 522–535

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025