Fol 13

**logics** · November 16th 2011, 12:54 AM

Enderton 2.2.19

An $\exists_2$ formula is one of the form $\exists x_1 \cdots x_n \theta$ , where $\theta$ is universal.

(a) Show that if an $\exists_2$ sentence in a language not containing function symbols (not even constant symbols) is true in $A$ , then it is true in some finite substructure of $|A|$ .

(b) Conclude that $\forall x \exists y Pxy$ is not logically equivalent to any $\exists_2$ sentence.

========================
(a) We have $\models_A \theta[s(x_1|d_1)(x_2|d_2)\ldots(x_n|d_n)]$ for some $d_1, d_2, \ldots, d_n \in |A|$ by assumption. We have to show that there are some finite substructure $B$ of $A$ such that

$\models_B \theta[s(x_1|d_1)(x_2|d_2)\ldots(x_n|d_n)]$ for the above $d_1, d_2, \ldots, d_n \in |B|$ .

How do I proceed from here?

Thanks.

**emakarov** · November 16th 2011, 04:25 AM

How about taking a substructure B with $|B|=\{d_1,\dots,d_n\}$ and using problem 2.2.18 from your previous post? If the language had functional symbols, then the substructure generated by a finite number of elements may still have an infinite domain. E.g., the substructure of natural numbers with the successor function that contains 0 still has to contain all natural numbers.

For (b), consider again natural numbers where $Pxy$ is $x<y$ .

Thread: Fol 13

LinkBack

Thread Tools

Display

Fol 13

Re: Fol 13

Search Tags