Answer Happy

18. A universal (₁) formula is one of the form Vx₁x₁0, where is quantifier-free. An existential (3₁) formula is of the dual form 3x₁3x0. Let 2 be a substructure of B, and let s : V → |A|. (a) Show that if [s] and is existential, then = [s]. And if 3 [s] and is universal, then = 4[s]. (b) Conclude that the sentence 3x Px is not logically equivalent to any universal sentence, nor Vx Px to any existential sentence. Remark: Part (a) says (when is a sentence) that any univer- sal sentence is "preserved under substructures." Being universal is a syntactic property-it has to do with the string of symbols. In contrast, being preserved under substructures is a semantic property it has to do with satisfaction in structures. But this semantic property captures the syntactic property up to logical equivalence (which is all one could ask for). That is, if o is a sentence that is always preserved under substructures, then o is logically equivalent to a universal sentence. (This fact is due to Łoś and Tarski.)