Sets of formulas valid in finite structures

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.