Sets of formulas valid in finite structures

Author:
Alan L. Selman

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

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A function is defined on the set of all subsets of so that for each set *K*, the value, , is the set of formulas valid in all structures of cardinality in *K*. An analysis is made of the dependence of on *K*, For any set **K**, let be the Kleene-Post degree to which *K* belongs. It is easily seen that for all infinite sets *K*, . On the other hand, we prove that , and use this to prove that, for any two degrees a and b, , and b r.e. a, there exists a set *K* so that and . Various similar results are also included.

**[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)**

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

Retrieve articles in all journals with MSC: 02F30

Additional Information

DOI:
https://doi.org/10.1090/S0002-9947-1973-0319730-3

Keywords:
First order formulas,
finite structures,
*K*-representation,
spectrum,
spectral functions

Article copyright:
© Copyright 1973
American Mathematical Society