Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-25T01:29:47.520Z Has data issue: false hasContentIssue false

A note on direct sums of Friedbergnumberings

Published online by Cambridge University Press:  12 March 2014

Martin Kummer*
Affiliation:
Institut für Logik, Komplexität und Deduktionssysteme, Universität Karlsruhe, D-7500 Karlsruhe 1, West Germany

Extract

We show that a translator ƒ: ωω from a Gödelnumbering φ into a direct sum η of a r.e. family of Friedbergnumberings satisfies ƒ ≰T0′. In particular, η cannot be a Gödelnumbering.

In the following we use standard notation (cf.[3]): for i ≥ 1, Pi (respectively, Ri) is the set of partial (total) recursive i-place functions; φ is a Gödel numbering of P1. By φi, s we denote a recursive standard approximation for φi, i.e., φi, s is a finite function, φi, sφi, s + 1, φi, sφi, φi = ⋃ {φi, ss ≥ 0}, and a canonical index for φi, s can be computed uniformly in i, s (cf.[3, p. 16 f]).

We call vP2 a numbering of P1 iff {λx.v(i, x)}iω = P1; we denote λx.v(i, x) by vi. Let v and γ be numberings of P1. A total function g: ωω is called a translator from v into γ iff ∀i: vi = γg(i).

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1989

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Friedberg, R. M., Three theorems on recursive enumeration: I. Decomposition, II. Maximal set, III. Enumeration without duplication, this Journal, vol. 23 (1958), pp. 309316.Google Scholar
[2]Schinzel, B., On decomposition of Gödelnumberings into Friedbergnumberings, this Journal, vol. 47 (1982), pp. 267274.Google Scholar
[3]Soare, R. I., Recursively enumerable sets and degrees, Springer-Verlag, Berlin, 1987.CrossRefGoogle Scholar