Reducibility on families |
| |
Authors: | I Sh Kalimullin∗ V G Puzarenko∗∗ |
| |
Institution: | (1) Kazan State University, ul. Universitetskaya 17, Kazan, Russia;(2) Institute of Mathematics, Siberian Branch, Russian Academy of Sciences, pr. Akad. Koptyuga 4, Novosibirsk, 630090, Russia |
| |
Abstract: | A reducibility on families of subsets of natural numbers is introduced which allows the family per se to be treated without
its representation by natural numbers being fixed. This reducibility is used to study a series of problems both in classical
computability and on admissible sets: for example, describing index sets of families belonging to , generalizing Friedberg’s completeness theorem for a suitable reducibility on admissible sets, etc.
*Supported by RFBR (project No. 05-01-00605) and by the Council for Grants (under RF President) and State Aid of Young Candidates
of Science (grant MK-4314.2008.1).
**Supported by RFBR (projects No. 08-01-00442 and 06-04002-DFGa), by the Council for Grants (under RF President) of Leading
Scientific Schools (grant NSh-335.2008.1), and by the Russian Foundation for Support of Domestic Science.
Translated from Algebra i Logika, Vol. 48, No. 1, pp. 31-53, January-February, 2009. |
| |
Keywords: | family of subsets of natural numbers admissible set reducibility |
本文献已被 SpringerLink 等数据库收录! |
|