1
$\begingroup$

One can define several maps between given structures in order to portray similarities or differences. The concept of isomorphism displays a deep structural overlapping, while for instance an homomorphism carries a weaker, one-directional mirroring.

Let us now take two first-order structures for a signature $S$, say $\mathfrak A$ and $\mathfrak B$, such that $\mathfrak A \cong_p \mathfrak B$ (i.e. structures are partially isomorphic): if the first-order signature $S$ is relational, $(\mathbb Q,<)\cong_p(\mathbb R,<)$ is an example of two partially isomorphic structures. Given the case that the domains of $\mathfrak A$ and $\mathfrak B$ are countable, if $\mathfrak A \cong_p \mathfrak B$ then $\mathfrak A \cong \mathfrak B$ (there is a famous theorem to prove it).

When we introduce into the picture the concept of two structures being finitely ($\mathfrak A \cong_f \mathfrak B$)or $\omega$-isomorphic (that is, $\forall n\leq \omega$ there is a chain of sets of partial isomorphisms $(I_n)$ such that $\mathfrak A \cong_\omega \mathfrak B$) we have that: $\mathfrak A \cong_p \mathfrak B$ $\Rightarrow$ $\mathfrak A \cong_f \mathfrak B$ but the converse isn't (usually) true.

Could you please provide an example of two elementary structures that are finitely isomorphic but not partially isomorphic? Thank you for the support.

$\endgroup$
1
$\begingroup$

I think the prototypical example would be $( \mathbb{Z} , < )$ and $( \mathbb{Z} + \mathbb{Z} , < )$ (where the second structure consists of two copies of $\mathbb{Z}$ after one another).

To see that they are finitely isomorphic, let $I_n$ consist of all finite order-preserving functions $f \mathrel{;} \mathbb{Z} \to \mathbb{Z} + \mathbb{Z}$ such that for all $k < \ell$ in the domain of $f$:

  1. if $\ell - k < 2^n$, then $f(k), f(\ell)$ belong to the same half of $\mathbb{Z} + \mathbb{Z}$, and $f(\ell) - f(k) = \ell - k$; and
  2. if $\ell - k \geq 2^n$, then either $f(k), f(\ell)$ belong to different halves of $\mathbb{Z} + \mathbb{Z}$, or belong to the same half and $f(\ell) - f(k) \geq 2^n$.

The basic idea is for each $n$ you want there to be a notion of "closeness", and you want to map things that are close to things that are the same distance apart, but things that are far apart just need to be mapped to things that are far apart. You also want this notion to have the additional properties that (1) if $k < \ell$ are far apart (in the sense of $n+1$) and $j$ between $k,\ell$ is close (in the sense of $n$) to one, then it if far (in the sense of $n$) to the other, and (2) if $k < j < \ell$ are such that $j$ is far away from both $k$ and $\ell$ (in the sense of $n$), then $k,\ell$ are far apart (in the sense of $n+1$).

To see that they are not partially isomorphic, note that if $I$ were a back-and-forth set then there must be some $f \in I$ whose range contains elements of both copies of $\mathbb{Z}$. Let $k$ be greatest such that $f(k)$ belongs to the first copy, and $\ell$ be least such that $f(\ell)$ belongs to the second copy. Now try to extend this function $(\ell - k)+1$ times to include each of $f(k) + 1$, $\ldots$, $f(k) + (\ell - k)$, $f(k) + ( \ell -k + 1 )$ into the range.

(As you have noted, if if two countable structures are partially isomorphic, then they are really isomorphic. Using this it is easy to deduce that $( \mathbb{Z} , < )$, $( \mathbb{Z} + \mathbb{Z} , < )$ are not partially isomorphic.)

$\endgroup$
  • $\begingroup$ Interestingly, $\Bbb{Z+Z\neq 2Z}$! :-) $\endgroup$ – Asaf Karagila Apr 9 '14 at 4:27
  • $\begingroup$ @AsafKaragila: Obviously, ${\bf Z}+{\bf Z}={\bf Z}$! $\endgroup$ – tomasz Apr 9 '14 at 7:32

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.