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

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ü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**, https://doi.org/10.2307/1970028**[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**

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