Hostname: page-component-586b7cd67f-l7hp2 Total loading time: 0 Render date: 2024-11-27T23:09:32.004Z Has data issue: false hasContentIssue false
  • English
  • Français

Nonrecursive combinatorial functions

Published online by Cambridge University Press:  12 March 2014

Erik Ellentuck
Erik Ellentuck*
Affiliation:
Rutgers, The State University, New Brunswick, New Jersey 08903
Get access Rights & Permissions [Opens in a new window]

Extract

In this paper we show how nonrecursive combinatorial functions can be used to obtain another proof of the compactness Theorem 3.1 of [6]. Our method is closely related to the argument used to show that a countable ultraproduct is ℵ1-saturated. What we do is to diagonalize in the most obvious way. The main difficulty with this approach is that the resulting diagonal function need not be recursive. Just to give an idea of how bad nonrecursive combinatorial functions are, we mention that by using frames (cf. [5]) they do not extend to Λ, and that by using normal combinatorial operators (cf. [4]) they do extend to Λ, map Λ into Λ, but in general, composition of such functions does not commute with their extension. We take care of this problem by constructing a large class of isols with respect to which the diagonal function is well behaved. The advantage of our method is that it provides the investigator with a natural and intuitive way of constructing counterexamples in his own research area.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 37 , Issue 1 , March 1972 , pp. 90 - 95
Copyright
Copyright © Association for Symbolic Logic 1972

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. and Myhill, J., Retraceable sets, Canadian Journal of Mathematics, vol. 10 (1958), pp. 357–373.CrossRefGoogle Scholar
[2]Ellentuck, E., Universal isols, Mathematische Zeitschrift, vol. 98 (1967), pp. 1–8.CrossRefGoogle Scholar
[3]Ellentuck, E., Nonrecursive relations among the isols, Proceedings of the American Mathematical Society (to appear).Google Scholar
[4]Myhill, J., Recursive equivalence types and combinatorial functions, Bulletin of the American Mathematical Society, vol. 64 (1958), pp. 373–376.CrossRefGoogle Scholar
[5]Nerode, A., Extensions to isols, Annals of Mathematics, vol. 73 (1961), pp. 362–403.CrossRefGoogle Scholar
[6]Nerode, A., Diophantine correct nonstandard models in the isols, Annals of Mathematics, vol. 84 (1966), pp. 421–432.CrossRefGoogle Scholar