Sets of formulas valid in finite structures
HTML articles powered by AMS MathViewer
- by Alan L. Selman PDF
- Trans. Amer. Math. Soc. 177 (1973), 491-504 Request permission
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
- 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 77468, DOI 10.1002/malq.19550010403 J. Bennett, On spectra, Doctoral Dissertation, Princeton University, Princeton, N. J., 1962.
- Richard Friedberg, A criterion for completeness of degrees of unsolvability, J. Symbolic Logic 22 (1957), 159–160. MR 98025, DOI 10.2307/2964177 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.
- Stephen Cole Kleene, Introduction to metamathematics, D. Van Nostrand Co., Inc., New York, N. Y., 1952. MR 0051790
- Gerald E. Sacks, Degrees of unsolvability, Princeton University Press, Princeton, N.J., 1963. MR 0186554 A. L. Selman, First order formulas true in structures of arbitrary finite cardinality, Notices Amer. Math. Soc. 17 (1970), 140. Abstract #672-202. —, Arithmetical reducibilities and sets of formulas valid in finite cardinality, Ph.D. Thesis, Pennsylvania State University, University Park, Pa., 1970.
- J. R. Shoenfield, On degrees of unsolvability, Ann. of Math. (2) 69 (1959), 644–653. MR 105355, DOI 10.2307/1970028
- 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
Additional Information
- © Copyright 1973 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 177 (1973), 491-504
- MSC: Primary 02F30
- DOI: https://doi.org/10.1090/S0002-9947-1973-0319730-3
- MathSciNet review: 0319730