Hostname: page-component-586b7cd67f-gb8f7 Total loading time: 0 Render date: 2024-11-28T00:59:58.408Z Has data issue: false hasContentIssue false
  • English
  • Français

A note on universal sets

Published online by Cambridge University Press:  12 March 2014

A. H. Lachlan
A. H. Lachlan*
Affiliation:
Simon Fraser University
Get access Rights & Permissions [Opens in a new window]

Extract

In this note is proved the following:

Theorem. Iƒ A × B is universal and one oƒ A, B is r.e. then one of A, B is universal.

Let α, τ be 1-argument recursive functions such that x goes to (σ(χ), τ(χ)) is a (1–1) map of the natural numbers onto all ordered pairs of natural numbers. A set A of natural numbers is called universal if every r.e. set is (many-one) reducible to A; A × B is called universal if the set

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 31 , Issue 4 , December 1966 , pp. 573 - 574
Copyright
Copyright © Association for Symbolic Logic 1997

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

[1]Smullyan, R. M., Theory of Formal Systems, Annals of Mathematics Studies, No. 47, Princeton University Press, Princeton, N.J., 1961.CrossRefGoogle Scholar