On \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$ p $\end{document}-Universal and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$ p $\end{document}-Minimal Numberings

被引:0
作者
M. Kh. Faizrahmanov
机构
[1] Kazan (Volga Region) Federal University,
关键词
computable numbering; -computable numbering; -reducibility; universal numbering; -universal numbering; -minimal numbering; 510.57;
D O I
10.1134/S0037446622020148
中图分类号
学科分类号
摘要
We study the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$ p $\end{document}-reducibility of numberings which was introduced and first studied by Degtev. \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$ p $\end{document}-Reducibility is an effectively bounded version of the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$ e $\end{document}-reducibility of numberings. Also, we prove that for every set \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$ A $\end{document} there exists an \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$ A $\end{document}-computable family without universal numberings but admitting \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$ p $\end{document}-universal numberings and obtain a criterion for the existence of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$ p $\end{document}-universal numberings of finite families of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$ A $\end{document}-c.e. sets. Finally, we show that every \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$ A $\end{document}-computable family, with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$ \varnothing^{\prime\prime}\leq_{T}A $\end{document}, has infinitely many pairwise non-\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$ p $\end{document}-equivalent \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$ p $\end{document}-minimal \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$ A $\end{document}-computable numberings.
引用
收藏
页码:365 / 373
页数:8
相关论文
共 17 条
[1]  
Degtev AN(1981)On reducibilities of numerations Math. USSR-Sb. 40 193-204
[2]  
Degtev AN(1993)On Ann. Pure Appl. Log. 63 57-60
[3]  
Degtev AN(2001)-reducibility of numerations Math. Notes 69 28-31
[4]  
Degtev AN(2008)On Sib. Math. J. 49 239-245
[5]  
Platonov ML(1997)-reducibility of computable numerations Algebra Logic 36 359-369
[6]  
Goncharov SS(2014)-Principal numberings Algebra Logic 53 355-364
[7]  
Sorbi A(1968)Generalized computable numerations and nontrivial Rogers semilattices Z. Math. Logik Grundlag. Math. 14 159-166
[8]  
Badaev SA(2018)Generalized computable universal numberings Algebra Logic 57 275-288
[9]  
Goncharov SS(2017)The degrees of hyperimmune sets Algebra Logic 56 337-347
[10]  
Miller W(2001)Some absolute properties of Algebra Logic 40 283-291