Hostname: page-component-586b7cd67f-t8hqh Total loading time: 0 Render date: 2024-11-23T14:34:28.724Z Has data issue: false hasContentIssue false
  • English
  • Français

On sets of relations definable by addition

Published online by Cambridge University Press:  12 March 2014

James F. Lynch
James F. Lynch*
Affiliation:
Clarkson College of Technology, Potsdam, New York 13676
Get access Rights & Permissions [Opens in a new window]

Abstract

For every κ ∈ ω, there is an infinite set Aκ ⊆ ω and a d(κ) ∈ ω such that for all Q0, Q1, ⊆ Aκ where ∣Q0∣ = ∣ Q1∣, or d(κ) < ∣Q0∣, Q1∣ < ℵ0, the structures ‹ω, +, Q0› and ‹ω, +, Q1› are indistinguishable by first-order sentences of quantifier depth κ whose atomic formulas are of the form u = v, u + v = w, and Q(u), where u, v, and w are variables.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 47 , Issue 3 , September 1982 , pp. 659 - 668
Copyright
Copyright © Association for Symbolic Logic 1982

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] Benda, M., Infinite words as universes (to appear).Google Scholar
[2] Büchi, J. R., Weak second-order arithmetic and finite automata, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 6 (1960), pp. 66–92.CrossRefGoogle Scholar
[3] Ehrenfeucht, A. and Mostowski, A., Models of axiomatic theories admitting automorphisms, Fundament a Mathematicae, vol. 43 (1957), pp. 50–68.CrossRefGoogle Scholar
[4] Ehrenfeucht, A., An application of games to the completeness problem for formalized theories, Fundament a Mathematicae, vol. 49 (1961), pp. 129–141.CrossRefGoogle Scholar
[5] Elgot, C.C., Decision problems of finite-automata design and related arithmetics, Transactions of the American Mathematical Society, vol. 98 (1961), pp. 21–51.CrossRefGoogle Scholar
[6] Fagin, R., Generalized first-order spectra and polynomial-time recognizable sets, Complexity of computation (Karp, R.M., Editor), American Mathematical Society, Providence, RI, 1974, pp. 43–73.Google Scholar
[7] Fagin, R., Monadic generalized spectra, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 21 (1975), pp. 89–96.CrossRefGoogle Scholar
[8] Fagin, R., Probabilities on finite models, this Journal, vol. 41 (1976), pp. 50–58.Google Scholar
[9] Gaifman, H., Concerning measures in first-order calculi, Israel Journal of Mathematics, vol. 2(1964), pp. 1–17.CrossRefGoogle Scholar
[10] Immerman, N., Number of quantifiers is better than number of tape cells, Journal of Computer and Systems Sciences (to appear).Google Scholar
[11] Jones, N. D. and Selman, A. L., Turing machines and the spectra of first-order formulas with equality, this Journal, vol. 39 (1974), pp. 139–150.Google Scholar
[12] Lynch, J. F., Almost sure theories, Annals of Mathematical Logic, vol. 18 (1980), pp. 91–135.CrossRefGoogle Scholar
[13] Lynch, J. F., Complexity classes and theories of finite models, Mathematical Systems Theory (to appear).Google Scholar
[14] Makkai, M. and Mycielski, J., An Lω1ω complete and consistent theory without models, Proceedings of the American Mathematical Society, vol. 62 (1977), pp. 131–133.Google Scholar
[15] Mckenzie, R., Mycielski, J. and Thompson, D., On boolean functions and connected sets, Mathematical Systems Theory, vol. 5 (1971), pp. 259–270.CrossRefGoogle Scholar
[16] Monk, J. D., Mathematical logic, Springer-Verlag, New York, 1976.CrossRefGoogle Scholar
[17] Rabin, M. O., Decidability of second-order theories and automata on infinite trees, Transactions of the American Mathematical Society, vol. 141 (1969), pp. 1–35.Google Scholar
[18] Reyes, G. E., Local definability theory, Annals of Mathematical Logic, vol. 1 (1970), pp. 95–137.CrossRefGoogle Scholar
[19] Robinson, J., Definability and decision problems in arithmetics, this Journal, vol. 14 (1949), pp. 98–114.Google Scholar