2
$\begingroup$

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 ...

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.