Counterexample to Fraissé's Theorem for infinite signature

Question

Let S be a finite signature and $\mathfrak{A}, \mathfrak{B}$ S-structures. Fraissé's Theorem states: $$\mathfrak{A} \equiv \mathfrak{B} \Leftrightarrow\mathfrak{A} \cong_f \mathfrak{B}$$ Where $\equiv$ means elementarily equivalent and $\mathfrak{A} \cong_f \mathfrak{B}$ means $\mathfrak{A},\mathfrak{B}$ finitely isomorphic, i.e. there is a sequence $(I_n)_{n\in\mathbb{N}}$ where

a) Every $I_n$ is a nonempty set of partial isomorphisms from $\mathfrak{A}$ to $\mathfrak{B}$

b) If $\sigma \in I_{n+1}, a \in A, b \in B$ there are extensions $\tau, \tau'$ of $\sigma$ in $I_n$ with $a \in dom(\tau), b\in im(\tau')$

I'm looking for a counterexample for infinite S, that is two S-structures $\mathfrak{A}, \mathfrak{B}$ with $\mathfrak{A} \equiv \mathfrak{B}$ but not $\mathfrak{A} \cong_f \mathfrak{B}$.

I fear there might be a trivial example which I'm not seeing, can someone hint me in the right direction?

In general what is a good strategy for proving two structures are not finitely isomorphic?

Answer 1

Let $L$ be the language consisting unary predicates "$n \in$" for every $n \in \omega$. Let $T$ be the theory asserting that every boolean combination of these predicates is realized. $T$ is complete and has quantifier elimination. Consider the following two $L$-structures, both with the natural interpretations of "$n \in$":

• $M$ consists of the finite subsets of $\omega$
• $N$ consists of all subsets of $\omega$.

$N$ and $M$ both model $T$, so are elementarily equivalence since $T$ is complete. $N$ and $M$ are not finitely isomorphic: $N$ contains an element realizing all the unary predicates, while $M$ does not.