I think this should be a standard counterexample but I can't find it anywhere, I'm looking for examples of $L$-structures $\mathfrak A$ and $\mathfrak B$ of the same cardinality such that $\mathfrak A\cong_p \mathfrak B$ but $\mathfrak A\not\cong \mathfrak B$ (an example in a nice language with naturally arising structures would be great, but an ad hoc example would also be appreciated).

Here $\mathfrak A\cong_p\mathfrak B$ means that there is a family $I$ of finite partial isomorphisms $\mathfrak A\to\mathfrak B$ with the back and forth property, that is:

  1. for all $f\in I$ and each $a\in\mathfrak A$ there is $g\in I$ extending $f$ with $a\in\operatorname{dom}(g)$
  2. for all $f \in I$ and each $b\in\mathfrak B$ there is $g\in I$ extending $f$ with $b\in\operatorname{Im}(g)$

I know that $\mathfrak A\cong_p \mathfrak B\implies \mathfrak A\equiv \mathfrak B$ and that by Scott's isomorphism theorem $\mathfrak A\cong_p \mathfrak B\implies \mathfrak A\cong \mathfrak B$ for countable $\mathfrak A,\mathfrak B$ so we need to look at bigger structures.
The source I'm reading uses $\Bbb Q$ and $\Bbb R$ as structures in the language $L=\{<\}$ as an example of structures which are partially isomorphic but not isomorphic but they don't have the same cardinality, so what are some counterexamples?


Well, take any two dense linear orders without endpoints, then easily they are partially isomorphic.

So we are just looking for two non-isomorphic dense linear orders without endpoints. Well, for example $\Bbb R$ and $\Bbb{R\times R}$ with the lexicographic order.

  • $\begingroup$ Oh, of course, that was easy in hindsight! $\endgroup$ – Alessandro Codenotti Mar 30 '18 at 17:56
  • 2
    $\begingroup$ Well, hindsight 20/20, you know... :) $\endgroup$ – Asaf Karagila Mar 30 '18 at 17:56

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.