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?

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.