Recursive well-founded orderings
Recursive well-founded orderings
复制标题
有根据的递归排序
DOI：
10.1016/0003-4843(78)90001-3
复制
发表时间：
1978
期刊：
影响因子：
--
通讯作者：
Keh
中科院分区：
文献类型：
--
作者：
Keh
设W（~）表示序数小于a的自然数的递归良序的G6 del数集。Kreisel、Shoenfield和Wang [3]、Liu [4]和[5]以及Hay、Manaster和Rosenstein [1]的工作已经完全确定了集合W（a）的多1度。本文将W（a）的多1度的结果推广到所有递归序数a上。作为工具，我们首先研究了W（a）的多1度，其中W（a）是秩小于0的自然数的递归良基偏序的G6 del数的集合，~ ot是第一非递归序数。如表1和表2所示，我们得到了WF（a）和W（c~）的多-一度，其中r（w. [3+ n）= w./ 3+ 2n，n<0。
Let W (~) denote the set of G6del numbers of recursive well-orderings of natural numbers of ordinal less than a. The many-one degrees of the sets W (a) for a< o)'have been completely determined by the accumulated work of Kreisel, Shoenfield, and Wang [3], Liu [4] and [5], and Hay, Manaster and Rosenstein [1]. In this paper, we extend tne results on many-one degrees of W (a) to all recursive ordinals a, As a tool, we first investigate the many-one degrees of WF (a) for< o9~ where WF (a) is the set of G6del numbers of reeursive well-founded partial orderings of natural numbers of rank less than o: and~ ot is the first non-recursbe ordinal. We obtain the many-one degrees of WF (a) and W (c~) as in Tables 1 and2, where r (w.[3+ n)= w./3+ 2n, n< to.