|
This article is cited in 1 scientific paper (total in 1 paper)
Descriptive properties on admissible sets
V. G. Puzarenko Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk, Russia
Abstract:
Relations are treated between the following descriptive properties on admissible sets: enumerability, uniformization, reduction, separation, extension. Moreover, in the setting of these properties, we consider existence problems for a universal computable function and for a computable function universal for $\{0;1\}$-valued computable functions. It is shown that all relations between the given properties are strict. Also we look into algorithmic complexity of admissible sets lending support to the specified relations. It is stated that the reduction principle fails in some admissible sets over classical structures.
Keywords:
admissible set, descriptive property, universal function.
Received: 27.07.2008 Revised: 30.09.2009
Citation:
V. G. Puzarenko, “Descriptive properties on admissible sets”, Algebra Logika, 49:2 (2010), 238–262; Algebra and Logic, 49:2 (2010), 160–176
Linking options:
https://www.mathnet.ru/eng/al438 https://www.mathnet.ru/eng/al/v49/i2/p238
|
|