1. ## Fol 8

Enderton 2.2.17

Consider a language with equality whose only parameter (aside from $\forall$) is a two-place predicate symbol $P$. Show that if $A$ is finite and $A \equiv B$ ( $A$ is elementary equivalent to $B$), $A$ is isomorphic to $B$.
Suggestion: Suppose the universe of $A$ has size $n$. Make a single sentence $\sigma$ of the form $\exists v_1 \cdots \exists v_n \theta$ that describes $A$ "completely". That is, on the one hand, $\sigma$ must be true in $A$. And on the other hand, any model of $\sigma$ must be exactly like (i.e., isomorphic to) $A$.

====================
To get started, how do I make a single sentence $\sigma$ of the form $\exists v_1 \cdots \exists v_n \theta$ that describes $A$ "completely"?

Thanks.

2. ## Re: Fol 8

First, say that all $v_i$'s are distinct. Second, that they are the whole universe, i.e., any other $v$ is equal to one of $v_i$'s. Finally, for each pair $(v_i, v_j)$ say whether $P$ holds on $(v_i, v_j)$.

3. ## Re: Fol 8

Let $R \subset |A| \times |A|$ be the binary relation to which two place predicate symbol $P$ is assigned by $A$.

Then,

$\sigma = \exists v_1 \exists v_2 \exists v_3 \ldots \exists v_n( (v_1 \neq v_2 \wedge v_1 \neq v_3 \wedge \ldots \wedge v_1 \neq v_n \wedge v_2 \neq v_3 \wedge \ldots \wedge v_2 \neq v_n \wedge \ldots \wedge v_{n-1} \neq v_n) \wedge (\bigwedge_{(i,j) \in R} P(v_i, v_j) \wedge \bigwedge_{(i,j) \notin R} \neg P(v_i, v_j))$.

$A \equiv B$ implies that if $\models_A \sigma$, then $\models_B \sigma$. Therefore, the cardinality of B is the same with A, since $\sigma$ ought to be true in its model B by assumption.

Without loss of generality, $|A| = \{a_1, a_2, \ldots, a_n\}$, and $|B|=\{b_1, b_2, \ldots, b_n\}$.

The required isomorphism $h: |A| \rightarrow |B|$ is given by $h(a_i) = b_i$ for $1 \leq i \leq n$ satisfying

$(a_s, a_t) \in P^A$ iff $(h(a_s), h(a_t) \in P^B$.

Is this correct?

Thank you.

4. ## Re: Fol 8

Originally Posted by logics
$A \equiv B$ implies that if $\models_A \sigma$, then $\models_B \sigma$. Therefore, the cardinality of B is the same with A, since $\sigma$ ought to be true in its model B by assumption.
The fact that $\models_B\sigma$ implies that the cardinality of B is at least n, but not necessarily exactly n.

Originally Posted by logics
Without loss of generality, $|A| = \{a_1, a_2, \ldots, a_n\}$, and $|B|=\{b_1, b_2, \ldots, b_n\}$.
Strictly speaking, the phrase "without loss of generality" is used to claim a proposition, not to make a definition or introduce a notation. For example, when I am proving $P(m,n)$ for some relation $P$ on numbers, I could say, "without loss of generality, $m\ge n$." This means that

$(\forall m',n'.\,m'\ge n'\to P(m',n'))\to P(m,n)$

is easy to prove (for example, because $P$ is symmetric and $m\ge n\lor n\ge m$ holds), and so I only need to show $m\ge n\to P(m,n)$.

Originally Posted by logics
The required isomorphism $h: |A| \rightarrow |B|$ is given by $h(a_i) = b_i$ for $1 \leq i \leq n$ satisfying

$(a_s, a_t) \in P^A$ iff $(h(a_s), h(a_t) \in P^B$.
In the previous step, you have already given names $a_i$ and $b_i$ to the elements of |A| and |B|, and there is no reason to expect that h such that $h(a_i)=b_i$ is an isomorphism. Also, when you say, "consider x satisfying P(x)" for some property P, you need to explain why such x exists. The idea is clear, of course, but I would say as follows.

Let's denote $\sigma=\exists v_1 \exists v_2 \exists v_3 \ldots \exists v_n\tau(v_1,\dots,v_n)$. We have $\models_A\sigma$ and $\models_B\sigma$, i.e., $\models_A\tau[(v_1,\dots,v_n|a_1,\dots,a_n)]$ and $\models_B\tau[(v_1,\dots,v_n|b_1,\dots,b_n)]$ for some $a_1,\dots,a_n\in|A|$ and $b_1,\dots,b_n\in|B|$. Then $(a_i,a_j)\in P^A$ iff $(b_i,b_j)\in P^B$, so h such that $h(a_i)=b_i$ for $1\le i\le n$ is an isomorphism.