Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Sets of formulas valid in finite structures

Author: Alan L. Selman
Journal: Trans. Amer. Math. Soc. 177 (1973), 491-504
MSC: Primary 02F30
MathSciNet review: 0319730
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A function $ \mathcal{V}$ is defined on the set of all subsets of $ \omega $ so that for each set K, the value, $ {\mathcal{V}_K}$, is the set of formulas valid in all structures of cardinality in K. An analysis is made of the dependence of $ {\mathcal{V}_K}$ on K, For any set K, let $ {\text{d}}(K)$ be the Kleene-Post degree to which K belongs. It is easily seen that for all infinite sets K, $ {\text{d}}(K) \vee 1 \leq d({\mathcal{V}_K}) \leq {\text{d}}(K)'$. On the other hand, we prove that $ {\text{d}}({\mathcal{V}_{K \vee J}}) = {\text{d}}({\mathcal{V}_K}) \vee {\text{d}}({\mathcal{V}_J})$, and use this to prove that, for any two degrees a and b, $ {\text{a}} \geq 1,{\text{a}} \leq {\text{b}} \leq {\text{a}}'$, and b r.e. a, there exists a set K so that $ {\text{d}}(K) = {\text{a}}$ and $ {\text{d}}({\mathcal{V}_K}) = b$. Various similar results are also included.

References [Enhancements On Off] (What's this?)

  • [1] G. Asser, Das Represäntantenproblem in Prädikatenkalkül der ersten Stufe mit Identität, Z. Math. Logik Grundlagen Math. 1 (1955), 252-263. MR 17, 1038. MR 0077468 (17:1038c)
  • [2] J. Bennett, On spectra, Doctoral Dissertation, Princeton University, Princeton, N. J., 1962.
  • [3] Richard Friedberg, A criterion for completeness of degrees of unsolvability, J. Symbolic Logic 22 (1957), 159-160. MR 20 #4488. MR 0098025 (20:4488)
  • [4] N. D. Jones and A. L. Selman, Turing machines and the spectra of first-order formulas with equality, Fourth ACM Sympos. on Theory of Computing, 1972, pp. 157-167.
  • [5] S. Kleene, Introduction to metamathematics, 5th ed., Van Nostrand, Princeton, N. J., 1950. MR 0051790 (14:525m)
  • [6] Gerald E. Sacks, Degrees of unsolvability, Ann. of Math. Studies, no. 55, Princeton Univ. Press, Princeton, N. J. 1963. MR 32 #4013. MR 0186554 (32:4013)
  • [7] A. L. Selman, First order formulas true in structures of arbitrary finite cardinality, Notices Amer. Math. Soc. 17 (1970), 140. Abstract #672-202.
  • [8] -, Arithmetical reducibilities and sets of formulas valid in finite cardinality, Ph.D. Thesis, Pennsylvania State University, University Park, Pa., 1970.
  • [9] J. R. Shoenfield, On degrees of unsolvability, Ann. of Math. (2) 69 (1959), 644-653. MR 21 #4097. MR 0105355 (21:4097)
  • [10] B. A. Trahtenbrot, The impossibility of an algorithm for the decision problem for finite domains, Dokl. Akad. Nauk SSSR 70 (1950), 569-572. MR 11, 488. (Russian) MR 0033784 (11:488a)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 02F30

Retrieve articles in all journals with MSC: 02F30

Additional Information

Keywords: First order formulas, finite structures, K-representation, spectrum, spectral functions
Article copyright: © Copyright 1973 American Mathematical Society

American Mathematical Society