Sets of formulas valid in finite structures
Alan L. Selman · Transactions of the American Mathematical Society · 1973
A function V \mathcal {V} is defined on the set of all subsets of ω \omega so that for each set K, the value, V K {\mathcal {V}_K} , is the set of formulas valid in all structures of cardinality in K. An analysis is made of the dependence of V K {\mathcal {V}_K} on K, For any set K, let d ( K ) {\text {d}}(K) be the Kleene-Post degree to which K belongs. It is easily seen that for all infinite sets K, d ( K ) ∨ 1 ≤ d ( V K ) ≤ d ( K ) ′ {\text {d}}(K) \vee 1 \leq d({\mathcal {V}_K}) \leq {\text {d}}(K)’ . On the other hand, we prove that d ( V K ∨ J ) = d ( V K ) ∨ d ( V J ) {\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, a ≥ 1 , a ≤ b ≤ a ′ {\text {a}} \geq 1,{\text {a}} \leq {\text {b}} \leq {\text {a}}’ , and b r.e. a, there exists a set K so that d ( K ) = a {\text {d}}(K) = {\text {a}} and d ( V K ) = b {\text {d}}({\mathcal {V}_K}) = b . Various similar results are also included.