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

Sibirsk. Mat. Zh., 2010 Volume 51, Number 1, Pages 217–235 (Mi smj2079)

This article is cited in 11 papers

$\Sigma$-Bounded algebraic systems and universal functions. I

A. N. Khisamiev

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

Abstract: We introduce the concept of a $\Sigma$-bounded algebraic system and prove that if a system is $\Sigma$- bounded with respect to a subset $A$ then in a hereditarily finite admissible set over this system there exists a universal $\Sigma$-function for the family of functions definable by $\Sigma$-formulas with parameters in $A$. We obtain a necessary and sufficient condition for the existence of a universal $\Sigma$-function in a hereditarily finite admissible set over a $\Sigma$-bounded algebraic system. We prove that every linear order is a $\Sigma$-bounded system and in a hereditarily finite admissible set over it there exists a universal $\Sigma$-function.

Keywords: admissible set, $\Sigma$-definability, computability, universal $\Sigma$-function, linear order.

UDC: 512.540+510.5

Received: 28.10.2008


 English version:
Siberian Mathematical Journal, 2010, 51:1, 178–192

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024