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:
- for all $f\in I$ and each $a\in\mathfrak A$ there is $g\in I$ extending $f$ with $a\in\operatorname{dom}(g)$
- 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.