查看“︁低基定理”︁的源代码

{{multiple issues|
{{expand|time=2014-04-18T05:31:11+00:00}}
{{expert|time=2014-04-18T05:31:11+00:00}}
{{no footnotes|time=2014-04-18T05:31:11+00:00}}
}}
'''低基定理'''是关于[[不可解度]]的定理。

== 定理 ==
设 <math>A\subseteq 2^\omega</math> 为无穷长二进制串的集合，若自然数的语言中存在[[递归公式]] <math>\theta</math>，使 <math>X\in A</math> 当且仅当 <math>\forall n\,\theta(n,X\vert n)</math>（注：<math>X\vert n</math> 是二进制串 <math>X</math> 的前 <math>n</math> 位）为真，则定义 <math>A</math> 为 <math>\Pi^0_1</math> 类。

若将无穷长二进制串的第 <math>n</math> 位理解成“<math>n</math> 是否属于该集合”，则 <math>2^\omega</math> 自然对应了自然数集合的子集集合 <math>\mathcal{P}(\mathbb{N})</math>。因此 <math>2^\omega</math> 上可以引入不可解度的关系 <math>\le_T</math>。

低基定理表明，若 <math>A</math> 是一个 <math>\Pi^0_1</math> 类，则存在 <math> G\in A</math> 使得 <math>G^\prime\le_T 0^\prime</math>（换句话说，<math>G</math> 是一个[[低不可解度]]）。称 <math>G</math> 为 <math>A</math> 的低基。

== 参考资料 ==
* {{cite book|language=en | first=Douglas | last=Cenzer | chapter=<math>\Pi^0_1</math> classes in computability theory | title=Handbook of computability theory | series=Stud. Logic Found. Math. | volume=140 | publisher=North-Holland | year=1999 | pages=37–85 | mr=1720779 | zbl=0939.03047 | editor-last=Griffor | editor-first=Edward R. | isbn=0-444-89882-4 }} 
* {{cite journal|language=en | first1=Carl G., jr | last1=Jockusch | first2=Robert I. | last2=Soare | title=&Pi;(0, 1) Classes and Degrees of Theories | journal=Transactions of the American Mathematical Society | year=1972 | jstor=1996261 | zbl=0262.02041 | volume=173 | pages=33-56 | issn=0002-9947 }}
*{{cite book|language=en | last=Nies | first=André | title=Computability and randomness | series=Oxford Logic Guides | volume=51 | location=Oxford | publisher=Oxford University Press | year=2009 | isbn=978-0-19-923076-1 | zbl=1169.03034 }}
* {{cite book|language=en|author=Robert I. Soare|title=Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets|year=2004|publisher=Springer|isbn=9780387152998}}

[[Category:数学定理]]
[[Category:递归论]]