Hostname: page-component-586b7cd67f-rcrh6 Total loading time: 0 Render date: 2024-11-22T05:20:30.876Z Has data issue: false hasContentIssue false

Mixed systems

Published online by Cambridge University Press:  12 March 2014

C. J. Ash
Affiliation:
Department of Mathematics, Monash University, Clayton, Victoria 3168, Australia
J. F. Knight
Affiliation:
Department of Mathematics, University of Notre Dame, Notre Dame, Indiana 46556

Extract

In [A1]–[A4] there is an abstract description, in terms of “α-systems”, of the object of a nested priority construction, and there is a metatheorem listing conditions which guarantee the success of the construction. The metatheorem has different versions, with later versions becoming simpler and more general. The information needed to meet the requirements is enumerated by a function, where α is an arbitrary recursive ordinal. All other objects associated with the α-system are r.e. In the basic metatheorem, the requirements must all be at level α, although there is a special result, for limit α, which allows one requirement at each level in an increasing sequence with limit α. There are other abstract descriptions of nested priority arguments in [K1], [K2], [K3], and [L-L].

A typical use of α-systems is that in [B], where it is shown that, for a relation R on a recursive structure , under suitable assumptions, if R does not have a “recursive Σα” definition in , then there is a recursive isomorphic copy of in which the image of R is not . There is no difficulty in generalizing this to make each of infinitely many relations not , when the assumptions are uniformly satisfied and each relation has no recursive Σα definition. However, the metatheorems for α-systems do not apply to the situation where we have several (even two) relations Ri, which do not have recursive Σβi definitions and whose images we wish to make not for distinct βi. An even more basic problem is to construct a recursive copy of a recursive structure via an isomorphism whose restriction to various sets Ui, is not If βi, = α for all i, then we can use an (α + 1)-system; otherwise, the old metatheorems do not apply.

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1994

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

[A1]Ash, C. J., Stability of recursive structures in arithmetical degrees, Annals of Pure and Applied Logic, vol. 32 (1986), pp. 113135.CrossRefGoogle Scholar
[A2]Ash, C. J., Recursive labelling systems and stability of recursive structures in hyperarithmetical degrees, Transactions of the American Mathematical Society, vol. 298 (1986), pp. 497514; Corrections, Recursive labelling systems and stability of recursive structures in hyperarithmetical degrees, Transactions of the American Mathematical Society, vol. 310 (1988), p. 851.CrossRefGoogle Scholar
[A3]Ash, C. J., Labelling systems and r.e. structures, Annals of Pure and Applied Logic, vol. 47 (1990), pp. 99119.CrossRefGoogle Scholar
[A4]Ash, C. J., A construction for recursive linear orderings, this Journal, vol. 56 (1991), pp. 673683.Google Scholar
[A-K]Ash, C. J. and Knight, J. F., Pairs of recursive structures, Annals of Pure and Applied Logic, vol. 46 (1990), pp. 211234.CrossRefGoogle Scholar
[B]Barker, E., Intrinsically relations, Annals of Pure and Applied Logic, vol. 39 (1988), pp. 105130.CrossRefGoogle Scholar
[K1]Knight, J. F., A metatheorem for constructions by finitely many workers, this Journal, vol. 55 (1990), pp. 787804.Google Scholar
[K2]Knight, J. F., Constructions by transfinitely many workers, Annals of Pure and Applied Logic, vol. 46 (1990), pp. 211234.Google Scholar
[K3]Knight, J. F., Requirement systems, this Journal (to appear).Google Scholar
[L-L]Lempp, S. and Lerman, M., Priority arguments using iterated trees of strategies, Recursion theory week, Oberwolfach, 1989 (Ambos-Spies, K.et at., editors), Lecture Notes in Mathematics, vol. 1432, Springer-Verlag, Berlin, 1990, pp. 277296.Google Scholar