# Model-theory : questions regarding partial isomorphism

I'm having problems with the first pages of Bruno Poizat, A Course in Model: Theory An Introduction to Contemporary Mathematical Logic (ed or 1985), specifically with local isomorphism and back- and forth-conditions [page 2].

I'm trying to supplement it with Jouko Väänänen, Models and Games (2011), in order to find some examples which help me to understand the definition.

I'll state preliminarly some basic definitions [see pages 54-on] :

Definition 5.1 An $L$-structure is a pair $\mathcal M = (M, Val_M)$, where $M$ is a non-empty set called the universe (or the domain) of $\mathcal M$, [...]. If $L = \emptyset$, an $L$-structure $(M)$ is a structure with just the universe and no structure in it.

Definition 5.3 $L$-structures $\mathcal M$ and $\mathcal M'$ are isomorphic if there is a bijection

$$\pi : M \rightarrow M'$$

such that [...].

Definition 5.10 An $L$-structure $\mathcal M$ is a substructure of another $L$-structure $\mathcal M'$, in symbols $\mathcal M \subseteq \mathcal M'$, if [...].

See page 63 :

Lemma 5.11 Suppose $L$ is a vocabulary, $\mathcal M$ an $L$-structure, and $X \subseteq M$. Suppose furthermore that either $L$ contains constant symbols or $X \ne \emptyset$. There is a unique $L$-structure $\mathcal N$ such that:

1. $\mathcal N \subseteq \mathcal M$.

2. $X \subseteq N$.

3. If $\mathcal N' \subseteq \mathcal M$ and $X \subseteq N'$, then $\mathcal N \subseteq \mathcal N'$.

Proof Let $X_0 = X \cup \{ c^M : c \in L \}$ and inductively [closure with respect to operations]. The set $N = \bigcup X_n$ is the universe of the unique structure $\mathcal N$ claimed to exist in the lemma.

We call the unique structure $\mathcal N$ of Lemma 5.11 the substructure of $\mathcal M$ generated by $X$ and denote it by $[X]_{\mathcal M}$.

Lemma 5.12 Suppose $L$ is a vocabulary. Suppose $\mathcal M$ and $\mathcal N$ are $L$-structures and $\pi : M \rightarrow N$ is a partial mapping. There is at most one isomorphism $\pi^* : [dom(\pi)]_{\mathcal M} \rightarrow [rng(\pi)]_{\mathcal N}$ extending $\pi$ .

Definition 5.13 Suppose $L$ is a vocabulary and $\mathcal M, \mathcal M'$ are $L$-structures. A partial mapping $\pi : M \rightarrow M'$ is a partial isomorphism $\mathcal M \rightarrow \mathcal M'$ if there is an isomorphism $\pi^* : [dom(\pi)]_{\mathcal M} \rightarrow [rng(\pi)]_{\mathcal M'}$ extending $\pi$.

Questions

Related to Lemma 5.11

(1) Consider $L = \{ < \}$, $\mathbb N = \{ 0,1,2, \ldots \}$ and $\mathcal M =(\mathbb N, <)$.

With $X = \{ 0 \} \subseteq \mathbb N$, what is $\mathcal N = [X]_{\mathcal M}$ ? There are no constants in the language, nor functions; thus, if we apply the above construction with $X_0 = X = \{ 0 \}$, we get $N = \bigcup X_n = \{ 0 \}$.

Thus, $\mathcal N = [X]_{\mathcal M} = (\{ 0 \}, <)$, and, in general, for $X \subseteq \mathbb N$ : $\mathcal N = [X]_{\mathcal M} = (X, <)$.

Is it true ?

(2) Consider $L = \{ \overline 0, <, + \}$ and $X = \{ 5 \}$.

$X_0 = X \cup \{ \overline 0^M \} = \{ 0, 5 \}$ and $N = \bigcup X_n = \{ 5n : n \in \mathbb N \}$.

Thus, $\mathcal N = [X]_{\mathcal M} = (\{ 5n : n \in \mathbb N \}, \overline 0, <, +)$.

Is it true ?

Related to Lemma 5.12 and Definition 5.13

(3) Consider $L = \{ < \}, \mathbb N, \mathbb Z_+ = \{ 1,2,3, \ldots \}$ and $\pi : = \mathbb N \rightarrow \mathbb Z_+$ such that $\pi = \{ (0,1) \}$.

$\pi$ is a partial mapping and I think that $[dom(\pi)]_{\mathcal M} = [\{ 0 \}]_{\mathcal M} = \{ 0 \}$ and $[rng(\pi)]_{\mathcal N} = [\{ 1 \}]_{\mathcal N} = \{ 1 \}$.

I think that the unique isomorphism $\pi^* : [dom(\pi)]_{\mathcal M} \rightarrow [rng(\pi)]_{\mathcal N}$ extending $\pi$ is $\pi^* = \{ (0,1) \}$.

Is it true ?

(4) Consider again $L = \{ \overline 0, <, + \}$ and $X = \{ 5 \}$.

$X \subseteq \mathbb N$ and $X \subseteq \mathbb Z_+$.

For $\mathcal M = (\mathbb N, \overline 0, <, + \}$ and $\mathcal N = (\mathbb Z_+, \overline 0, <, + \}$ we have respectively :

$[X]_{\mathcal M} = (\{ 5n : n \in \mathbb N \}, \overline 0, <, +)$ [if I'm right - see Q_2 above]

and :

$[X]_{\mathcal N} = (\mathbb Z_+, \overline 0, <, +)$, because $X_0 = X \cup \{ \overline 0^N \} = \{ 1, 5 \}$ and $N = \bigcup X_n = \mathbb Z_+$.

Consider the mapping $\pi : = \mathbb N \rightarrow \mathbb Z_+$ such that $\pi = \{ (5,5) \}$.

Is it a partial isomorphism between $[X]_{\mathcal M}$ and $[X]_{\mathcal N}$ ?

Clearly there is a bijection between $\{ 0,5,10, \ldots \}$ and $\{ 1,2,3, \ldots \}$ which "preserve" the order relations.

But the sum is not preserved :

$+^{\mathcal N}(\pi(x),\pi(y)) \ne \pi(+^{\mathcal M}(x,y))$.

Consider $0,5$; in $[X]_{\mathcal M}$, which are "mapped to" $1,2$ in $[X]_{\mathcal N}$. We have $0+5=5$, and $5$ is "mapped to" $2$, while in $[X]_{\mathcal N}$ we have $1+2=3$ and $3 \ne 2$.

Thus, the "obviuos" extension of $\pi$ to $\pi^*$ does not work.

Is it possible to find $\pi^* : [X]_{\mathcal M} \rightarrow [X]_{\mathcal N}$ which extend the partial mapping $\pi = \{ (5,5) \}$ ?

I think not ...

## 1 Answer

1,2,3 seems fine. 4 shouldn't be possible since the theories of the structures are not the same (with $\mathbb{N}$ you have an additive identity but not so in $\mathbb{Z}_+$ under the standard interpretation.)

Also the theorem says at most one, so I guess this is an example where you don't have an extension.