<p>In this paper, we construct a computable family <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10849_2025_9430_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="19" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mathcal {R}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">R</mi> </math></EquationSource> </InlineEquation> of r.e. sets whose every computable numbering <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10849_2025_9430_Article_IEq2.gif" Format="GIF" Height="10" Rendition="HTML" Resolution="72" Type="Linedraw" Width="14" /> </InlineMediaObject> <EquationSource Format="TEX">\(\alpha \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>α</mi> </math></EquationSource> </InlineEquation> is complete and encodes the Gödel numbering <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10849_2025_9430_Article_IEq3.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="62" /> </InlineMediaObject> <EquationSource Format="TEX">\(x\mapsto W_x\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>x</mi> <mo>↦</mo> <msub> <mi>W</mi> <mi>x</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> of the family of all r.e. sets within itself in the sense that there exists a recursive function <i>r</i> such that for every <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10849_2025_9430_Article_IEq4.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="42" /> </InlineMediaObject> <EquationSource Format="TEX">\(b\in \mathbb N\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>b</mi> <mo>∈</mo> <mi mathvariant="double-struck">N</mi> </mrow> </math></EquationSource> </InlineEquation> there is a <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10849_2025_9430_Article_IEq5.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="50" /> </InlineMediaObject> <EquationSource Format="TEX">\(B\subseteq \mathbb N\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>B</mi> <mo>⊆</mo> <mi mathvariant="double-struck">N</mi> </mrow> </math></EquationSource> </InlineEquation> with <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10849_2025_9430_Article_IEq6.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="132" /> </InlineMediaObject> <EquationSource Format="TEX">\(\alpha (r(b))=B\oplus W_b\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>α</mi> <mrow> <mo stretchy="false">(</mo> <mi>r</mi> <mrow> <mo stretchy="false">(</mo> <mi>b</mi> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mi>B</mi> <mo>⊕</mo> <msub> <mi>W</mi> <mi>b</mi> </msub> </mrow> </math></EquationSource> </InlineEquation>. Then we prove that, for all <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10849_2025_9430_Article_IEq7.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="43" /> </InlineMediaObject> <EquationSource Format="TEX">\(n\geqslant 2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>⩾</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>, every non-trivial <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10849_2025_9430_Article_IEq8.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="21" /> </InlineMediaObject> <EquationSource Format="TEX">\(\Sigma ^0_n\)</EquationSource> <EquationSource Format="MATHML"><math> <msubsup> <mi mathvariant="normal">Σ</mi> <mi>n</mi> <mn>0</mn> </msubsup> </math></EquationSource> </InlineEquation>-computable family has a non-complete (and even non-cylindrical) <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10849_2025_9430_Article_IEq8.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="21" /> </InlineMediaObject> <EquationSource Format="TEX">\(\Sigma ^0_n\)</EquationSource> <EquationSource Format="MATHML"><math> <msubsup> <mi mathvariant="normal">Σ</mi> <mi>n</mi> <mn>0</mn> </msubsup> </math></EquationSource> </InlineEquation>-computable numbering, but there exists a <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10849_2025_9430_Article_IEq8.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="21" /> </InlineMediaObject> <EquationSource Format="TEX">\(\Sigma ^0_n\)</EquationSource> <EquationSource Format="MATHML"><math> <msubsup> <mi mathvariant="normal">Σ</mi> <mi>n</mi> <mn>0</mn> </msubsup> </math></EquationSource> </InlineEquation>-computable family <InlineEquation ID="IEq11"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10849_2025_9430_Article_IEq11.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="18" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mathcal {A}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">A</mi> </math></EquationSource> </InlineEquation> whose every <InlineEquation ID="IEq12"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10849_2025_9430_Article_IEq8.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="21" /> </InlineMediaObject> <EquationSource Format="TEX">\(\Sigma ^0_n\)</EquationSource> <EquationSource Format="MATHML"><math> <msubsup> <mi mathvariant="normal">Σ</mi> <mi>n</mi> <mn>0</mn> </msubsup> </math></EquationSource> </InlineEquation>-computable numbering <InlineEquation ID="IEq13"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10849_2025_9430_Article_IEq13.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="15" /> </InlineMediaObject> <EquationSource Format="TEX">\(\beta \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>β</mi> </math></EquationSource> </InlineEquation> has the fixed point property (i.e., for every recursive function <i>f</i> there is a <InlineEquation ID="IEq14"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10849_2025_9430_Article_IEq14.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="44" /> </InlineMediaObject> <EquationSource Format="TEX">\(p\in \mathbb N\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>p</mi> <mo>∈</mo> <mi mathvariant="double-struck">N</mi> </mrow> </math></EquationSource> </InlineEquation> with <InlineEquation ID="IEq15"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10849_2025_9430_Article_IEq15.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="109" /> </InlineMediaObject> <EquationSource Format="TEX">\(\beta (f(p))=\beta (p)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>β</mi> <mo stretchy="false">(</mo> <mi>f</mi> <mo stretchy="false">(</mo> <mi>p</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> <mo>=</mo> <mi>β</mi> <mo stretchy="false">(</mo> <mi>p</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>) and encodes within itself the numbering <InlineEquation ID="IEq16"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10849_2025_9430_Article_IEq16.gif" Format="GIF" Height="24" Rendition="HTML" Resolution="72" Type="Linedraw" Width="89" /> </InlineMediaObject> <EquationSource Format="TEX">\(x\mapsto W^{\emptyset ^{(n-1)}}_x\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>x</mi> <mo>↦</mo> <msubsup> <mi>W</mi> <mi>x</mi> <msup> <mi mathvariant="normal">∅</mi> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>-</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </msup> </msubsup> </mrow> </math></EquationSource> </InlineEquation>.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A Family Whose Computable Numberings are All Complete

  • Marat Faizrahmanov

摘要

In this paper, we construct a computable family \(\mathcal {R}\) R of r.e. sets whose every computable numbering \(\alpha \) α is complete and encodes the Gödel numbering \(x\mapsto W_x\) x W x of the family of all r.e. sets within itself in the sense that there exists a recursive function r such that for every \(b\in \mathbb N\) b N there is a \(B\subseteq \mathbb N\) B N with \(\alpha (r(b))=B\oplus W_b\) α ( r ( b ) ) = B W b . Then we prove that, for all \(n\geqslant 2\) n 2 , every non-trivial \(\Sigma ^0_n\) Σ n 0 -computable family has a non-complete (and even non-cylindrical) \(\Sigma ^0_n\) Σ n 0 -computable numbering, but there exists a \(\Sigma ^0_n\) Σ n 0 -computable family \(\mathcal {A}\) A whose every \(\Sigma ^0_n\) Σ n 0 -computable numbering \(\beta \) β has the fixed point property (i.e., for every recursive function f there is a \(p\in \mathbb N\) p N with \(\beta (f(p))=\beta (p)\) β ( f ( p ) ) = β ( p ) ) and encodes within itself the numbering \(x\mapsto W^{\emptyset ^{(n-1)}}_x\) x W x ( n - 1 ) .