Reducibility on families

被引：0
作者：
I. Sh. Kalimullin∗
V. G. Puzarenko∗∗
机构：
[1] Kazan State University,Institute of Mathematics, Siberian Branch
[2] Russian Academy of Sciences,undefined
来源：
Algebra and Logic | 2009年 / 48卷
关键词：
family of subsets of natural numbers; admissible set; reducibility;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$ \sum_3^0 $\end{document}, generalizing Friedberg’s completeness theorem for a suitable reducibility on admissible sets, etc.
引用
收藏
页码：20 / 32
页数：12
相关论文
共 13 条
[1]  
Goncharov SS(2005)Enumerations in computable structure theory Ann. Pure Appl. Log. 136 219-246
[2]  
Harizanov VS(2009)A reducibility on admissible sets Sib. Mat. Zh. 50 2-320
[3]  
Knight JF(2004)Σ-subsets of natural numbers Algebra Logika 43 291-1099
[4]  
McCoy C(1972)Degrees in which the recursive sets are uniformly recursive Can. J. Math. 24 1092-266
[5]  
Miller RG(1969)On the degrees of index sets. II Trans. Am. Math. Soc. 135 249-532
[6]  
Solomon R(1971)Minimal numerations of families of recursively enumerable sets Dokl. Akad. Nauk SSSR 198 530-350
[7]  
Puzarenko V. G.(1971)Arithmetical reducibilities. I Z. Math. Log. Grund. Math. 17 335-undefined
[8]  
Morozov AS(undefined)undefined undefined undefined undefined-undefined
[9]  
Puzarenko VG(undefined)undefined undefined undefined undefined-undefined
[10]  
Jockusch CG(undefined)undefined undefined undefined undefined-undefined
12