Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2025-01-03T11:55:05.419Z Has data issue: false hasContentIssue false
  • English
  • Français

Ed-regressive sets of order n

Published online by Cambridge University Press:  12 March 2014

Seth Catlin
Seth Catlin*
Affiliation:
Eastern Oregon State College, Lagrande, Oregon 97850
Get access Rights & Permissions [Opens in a new window]

Extract

A number is a nonnegative integer, and E is the set of numbers. In [3], J. C. E. Dekker introduced the concept of a regressive set of order n as the range of a one-one function f of n arguments such that (i) domain f ⊆ En and, if (x 1, …, xn ) ∈ domain f, and yi ≤ ≤ xi for 1 ≤ i ≤ n, then (y 1, …, yn ) ∈ domain f, and (ii) if 1 ≤ i ≤ n and (x 1, …, xn ) ∈ domain f, then f(x 1 … x i−1, xi ∸ 1, x i+1 … xn ) can be found effectively from f(x 1 … xn ). (0 ∸ 1 = 0 and, for m ≥ 1, m ∸ 1 = m − 1.) Since one can take the view, as Dekker did when first introducing regressive functions in [1], that a regressive set of order one is the range of a function of the above type which is of order one and everywhere defined, it seems natural to study the n-dimensional analogue in which (i) is replaced by “domain f = En .” It is the purpose of this paper to study such sets.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 41 , Issue 1 , March 1976 , pp. 146 - 152
Copyright
Copyright © Association for Symbolic Logic 1976

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] Dekker, J. C. E., Infinite series of isols, Proceedings of the Symposia in Pure Mathematics, vol. 5, American Mathematical Society, Providence, R.I., 1962, pp. 77–96.Google Scholar
[2] Dekker, J. C. E., The minimum of two regressive isols, Mathematische Zeitschrift, vol. 83 (1964), pp. 345–366.CrossRefGoogle Scholar
[3] Dekker, J. C. E., Closure properties of regressive functions, Proceedings of the London Mathematical Society (3), vol. 15 (1965), pp. 226–238.CrossRefGoogle Scholar
[4] Dekker, J. C. E. and Myhill, J., Retraceable sets, Canadian Journal of Mathematics, vol. 10 (1968), pp. 357–373.CrossRefGoogle Scholar
[5] Dekker, J. C. E. and Myhill, J., Recursive equivalence types, University of California Publ. Math. (New Series), vol. 3 (1960), pp. 67–214.Google Scholar
[6] Richter, W. H., Regressive sets of order n, Mathematische Zeitschrift, vol. 86 (1965), pp. 372–374.CrossRefGoogle Scholar
[7] Sacks, G. E., Degrees of unsolvability, Annals of Mathematics Studies, no. 55, Princeton, New Jersey.Google Scholar