Degrees of indiscernibles in decidable models

Kierstead, H. A.; Remmel, J. B.

doi:10.1090/S0002-9947-1985-0779051-X

Degrees of indiscernibles in decidable models
HTML articles powered by AMS MathViewer

by H. A. Kierstead and J. B. Remmel PDF

Trans. Amer. Math. Soc. 289 (1985), 41-57 Request permission

Abstract:

We show that the problem of finding an infinite set of indiscernibles in an arbitrary decidable model of a first order theory is essentially equivalent to the problem of finding an infinite path through a recursive $\omega$-branching tree. Similarly, we show that the problem of finding an infinite set of indiscernibles in a decidable model of an $\omega$-categorical theory with decidable atoms is essentially equivalent to finding an infinite path through a recursive binary tree.

References

Model theory

A. Ehrenfeucht and A. Mostowski, Models of axiomatic theories admitting automorphisms, Fund. Math. 43 (1956), 50–68. MR 84456, DOI 10.4064/fm-43-1-50-68
Leo A. Harrington and Alexander S. Kechris, A basis result for $\Sigma ^{0}_{3}$ sets of reals with an application to minimal covers, Proc. Amer. Math. Soc. 53 (1975), no. 2, 445–448. MR 398832, DOI 10.1090/S0002-9939-1975-0398832-7
Carl G. Jockusch Jr. and Robert I. Soare, Degrees of members of $\Pi ^{0}_{1}$ classes, Pacific J. Math. 40 (1972), 605–616. MR 309722
Carl G. Jockusch Jr. and Robert I. Soare, $\Pi ^{0}_{1}$ classes and degrees of theories, Trans. Amer. Math. Soc. 173 (1972), 33–56. MR 316227, DOI 10.1090/S0002-9947-1972-0316227-0
H. A. Kierstead and J. B. Remmel, Indiscernibles and decidable models, J. Symbolic Logic 48 (1983), no. 1, 21–32. MR 693244, DOI 10.2307/2273316
James H. Schmerl, A decidable $\aleph _{0}$-categorical theory with a nonrecursive Ryll-Nardzewski function, Fund. Math. 98 (1978), no. 2, 121–125. MR 483924, DOI 10.4064/fm-98-2-121-125
Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462