1. ## Fol 8

Enderton 2.2.17

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

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

Thanks.

2. ## Re: Fol 8

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

3. ## Re: Fol 8

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

Then,

$\displaystyle \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))$.

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

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

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

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

Is this correct?

Thank you.

4. ## Re: Fol 8

Originally Posted by logics
$\displaystyle A \equiv B$ implies that if $\displaystyle \models_A \sigma$, then $\displaystyle \models_B \sigma$. Therefore, the cardinality of B is the same with A, since $\displaystyle \sigma$ ought to be true in its model B by assumption.
The fact that $\displaystyle \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, $\displaystyle |A| = \{a_1, a_2, \ldots, a_n\}$, and $\displaystyle |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 $\displaystyle P(m,n)$ for some relation $\displaystyle P$ on numbers, I could say, "without loss of generality, $\displaystyle m\ge n$." This means that

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

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

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

$\displaystyle (a_s, a_t) \in P^A$ iff $\displaystyle (h(a_s), h(a_t) \in P^B$.
In the previous step, you have already given names $\displaystyle a_i$ and $\displaystyle b_i$ to the elements of |A| and |B|, and there is no reason to expect that h such that $\displaystyle 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 $\displaystyle \sigma=\exists v_1 \exists v_2 \exists v_3 \ldots \exists v_n\tau(v_1,\dots,v_n)$. We have $\displaystyle \models_A\sigma$ and $\displaystyle \models_B\sigma$, i.e., $\displaystyle \models_A\tau[(v_1,\dots,v_n|a_1,\dots,a_n)]$ and $\displaystyle \models_B\tau[(v_1,\dots,v_n|b_1,\dots,b_n)]$ for some $\displaystyle a_1,\dots,a_n\in|A|$ and $\displaystyle b_1,\dots,b_n\in|B|$. Then $\displaystyle (a_i,a_j)\in P^A$ iff $\displaystyle (b_i,b_j)\in P^B$, so h such that $\displaystyle h(a_i)=b_i$ for $\displaystyle 1\le i\le n$ is an isomorphism.