# Counterexample to Fraissé's Theorem for infinite signature

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?

• You can see Heinz-Dieter Ebbinghaus & Jörg Flum & Wolfgang Thomas, ,Mathematical logic (2nd ed 1994), page 251 : Exercise 2.6. – Mauro ALLEGRANZA Apr 7 '15 at 9:20
• You forgot to require that the signature is relational. – Primo Petri Apr 7 '15 at 9:36
• @PrimoPetri I dont think this is necessary, because the general case follows from the relational case. – Achilles Apr 7 '15 at 9:41
• Also the book I'm working with does not assume it to be relational (see Corollary 4.2.4 here) – Achilles Apr 7 '15 at 9:47
• Ok, probably you are right. – Primo Petri Apr 7 '15 at 9:55

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.