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

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ünter Asser, Das Repräsentantenproblem im Prädikatenkalkül der ersten Stufe mit Identität, Z. Math. Logik Grundlagen Math. 1 (1955), 252–263 (German). MR 0077468
  • [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. Symb. Logic 22 (1957), 159–160. MR 0098025
  • [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] Stephen Cole Kleene, Introduction to metamathematics, D. Van Nostrand Co., Inc., New York, N. Y., 1952. MR 0051790
  • [6] Gerald E. Sacks, Degrees of unsolvability, Princeton University Press, Princeton, N.J., 1963. MR 0186554
  • [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 0105355,
  • [10] B. A. Trahtenbrot, The impossibility of an algorithm for the decision problem for finite domains, Doklady Akad. Nauk SSSR (N.S.) 70 (1950), 569–572 (Russian). MR 0033784

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