# Suppose $R \sim_\omega R'$. Then for every $k$-tuple $a$ in $E$ and every natural number $p$, there is a $k$-tuple $b$ in $E'$ such that $a \sim_p b$

Sorry to bother you guys again with a Poizat question, but I'm struggling a little bit with the material (as it must be obvious) and I want to check if I got the main idea correctly or if I'm totally off. I'll give the basic definitions again and proceed to my question, which is basically about Exercise 1.1 from Poizat's A Course in Model Theory (sorry for the repition, but it's my understanding that questions in this site must be self-contained).

Poizat defines an isomorphism $s$ from a relation $R$ to a relation $R'$ as a bijection from $E$ to $E'$ (where these denote the respective underlying sets, or universes) which preserves the given relation (i.e. a sequence $\vec{a}$ satisfies $R$ iff the sequence $s(\vec{a})$ also satisfies $R'$). After defining the notion of a local isomorphism from $R$ to $R'$ as an isomorphism between finite restrictions of $R$ to $R'$ (where a finite restriction is a restriction of the relation to a finite subset of the original universe), he proceeds to define the set $S_p(R, R')$ of $p$-isomorphisms between $R$ and $R'$ ($p$ is a non-negative integer). The definition is recursive: $S_0(R,R')$ is defined as the set of all local isomorphisms between $R$ and $R'$ and, for $p>0$, we say that a local isomorphism $s$ belongs to the set $S_{p+1}(R,R')$ according to the following conditions:

Back: For every $a$ in the universe $E$ of $R$, there is an extension $t$ of $s$ (i.e., $\mathrm{dom}(s)\subseteq \mathrm{dom}(t)$ and $s$ is the restriction of $t$ to $\mathrm{dom}(s)$), defined at $a$, that is in $S_p(R,R')$;

Forth: For every $b$ in the universe $E'$ of $R'$, there is an extension $t$ of $s$, whose image contains $b$, that is in $S_p(R,R')$.

By an $\omega$-isomorphism, we mean a local isomorphism $\sigma$ from $R$ to $R'$ that is a $p$-isomorphism for every nonnegative integer $p$. We write $S_\omega(R, R')$ for the set of all $\omega$-isomorphisms between $R$ and $R'$, i.e. the intersection of all $S_p(R, R')$. If $S_\omega(R, R')$ is non-empty, we say that $R$ and $R'$ are elementary equivalent, in symbols, $R \sim_\omega R'$. If $f_\emptyset$ (the empty function) is a $p$-isomorphism from $R$ to $R'$, we say that they are $p$-equivalent, and denote this by $R \sim_p R'$. If there is a $p$-isomorphism from $R$ to $R'$ according to which a given $k$-tuple $\vec{a} = \langle a_1, \dots, a_k \rangle$ in the universe of $R$ corresponds to a $k$-tuple $\vec{b}=\langle b_1, \dots, b_k \rangle$ in the universe of $R'$, we say that these $\vec{a}$ and $\vec{b}$ are $p$-equivalent.

Given this, in Exercise 1.1 (p. 4), Poizat asks us to prove the following. Suppose $R$ and $R'$ are elementary equivalent. We claim that, for every $k$-tuple $\vec{a}$ in the universe of $R$ and every nonnegative integer $p$, there is a $k$-tuple $\vec{b}$ in the universe of $R'$ such that $(\vec{a}, R) \sim_p (\vec{b}, R')$.

Now, here's what I thought. The proof is by induction on$k$. For $k = 0$, since $R$ and $R'$ are elementary equivalent, $f_\emptyset$ will be in every $S_p(R, R')$, so that takes care of it. For $k=n+1$, Suppose the hypothesis of the theorem and consider an arbitrary $k$-tuple $\vec{a}_k$ and an arbitrary $p$. By the induction hypothesis, for every $n$-tuple and for every nonnegative integer $i$, there is an $n$-tuple $\vec{b}$ such that $(\vec{a}, R) \sim_i (\vec{b}, R')$. In particular, for every $n$-tuple, there is a $p+1$-isomorphism $\sigma$ from $R$ to $R'$ such that, for each $j \leq n$, $a_j \in \operatorname{dom}(\sigma)$. We can thus select an $n$-tuple $\vec{a}_n$ such that, for each $a_j \leq n$, $\vec{a}_n$ agrees with $\vec{a}_k$ and such that there is a corresponding $p+1$- isomorphism, say $\tau$, from $R$ to $R'$. Now, by the forth condition, it follows that, for every $a \in E$, there's an extension $\tau'$ of $\tau$, such that $a \in \operatorname{dom}(\tau')$ and $\tau' \in S_p(R, R')$. In particular, there's an extension $\tau'$ of $\tau$ such that $a_k \in \operatorname{dom}(\tau')$. Thus, for each $j \leq k$, $a_j \in \operatorname{dom}(\tau')$. Now, consider $\tau'(\vec{a}_k)$. This will be a $k$-tuple $\vec{b}$ in the domain of $R'$, thus completing the proof.

Is the above reasoning correct? I'm particularly concerned with the last step, namely taking $\tau'(\vec{a}_k)$. It seems that, given $\tau'$, it's possible to define the action of $\tau'$ on the tuple $\vec{a}_k$ by describing the action of $\tau'$ on each element of $\vec{a}_k$). I'm not sure, however, that this is legitimate...

Well, since nobody has answered, I'll post the answer which I have worked out.

Upon reflection, I believe that it's not necessary to proceed by induction. One can argue in this way:

Suppose the hypothesis of the theorem and consider an arbitrary $k$-tuple $\vec{a}_k$ and an arbitrary $p$. By the hypothesis of the theorem, we know that $f_\emptyset$ is a $n$-isomorphism for every nonnegative integer $n$. In particular, it's $p+k$-isomorphism. Now, by the forth condition, it follows that, for every $a \in E$, there's an extension $\tau$ of $f_\emptyset$, such that $a \in \operatorname{dom}(\tau)$ and $\tau \in S_{p+(k-1)}(R, R')$. We can therefore select a $\tau$ such that $a_1 \in \operatorname{dom}(\tau)$. Considering again the forth condition, there is an extension $\tau'$ of $\tau$ such that $\tau'$ is in $S_{p+(k-2)}(R, R')$ such that $a_2 \in \operatorname{dom}(\tau')$. Repeating this procedure $k$-times, we eventually arrive at a $p$-isomorphism $\sigma$ such that each $a_i$ ($i \leq k$) is in $\operatorname{dom}(\sigma)$. Thus, for each $a_i$, $\sigma(a_i) = b_i$ for some $b_i \in E'$. Therefore, the tuple $\vec{b} = \langle b_1, \dots, b_k \rangle$ is in $E'^k$, that is, it's in the universe of $R'$.

In the original question, I was a bit confused with the expression "the universe of $R'$"; I thought the $k$-tuple $\vec{b}$ needed to be in $E'$ (sort of), and then there was no guarantee that the $p$-isomorphism would take the tuple $\vec{a}$ to another tuple. Now I see that the only requirement is that $\vec{b}$ needs to be an element of $E'^k$, which follows clearly from the above (plus some set-theoretical assumptions, I guess).

EDIT: Thinking a bit more about the tuple issue, it seems to me that the idea is a bit more involved. Poizat does not mention that the $k$-tuple needs to be an element of $E^k$; rather, he appears to be thinking of the tuple as a function from $k$ to $E$. Thus, in order to generate the $k$-tuple $\vec{b}$, I need to index each $b$ according to the corresponding $a_i \in \vec{a}$. For instance, if the first extension $p+(k-1)$-isomorphism $\tau$ is such that $\tau(a_1) = b$, then I index $b$ as $b_1$. The next extension will give me $\tau'(a_2) = b'$, so I set $b'=b_2$, etc. This way, $a_i = a_j$ iff $b_i = b_j$ and the $p$-isomorphism $\sigma$ will be $\sigma(a_n) = b_n$ for $n \leq k$.

• I think you are right. Since a couple of months I'm struggling with Poizat's approach without being able to fully grasp it. Basically, my intuitions are : (i) to say that a local iso $s$ is $\in S_p$ "means" that we can "extend it" $p$ times. Thus, if $s$ is a $p$-iso for every $p$, we can extend it $p$ times, for every $p$. (ii) $R,R'$ are elementary equivalent iff the empty function $f_{\emptyset}$ is a $p$-iso for every $p$. Thus, the key to Ex.1.1 (I think) is that, starting with a $k$-uple $\overline a$ does not affect the "extendibility" of $f_{\emptyset}$. – Mauro ALLEGRANZA Aug 27 '14 at 8:49
• Yea, and similarly for exercise 2.2., which seems to be the "reverse" of this one (instead of using the forth condition, one must extend the isomorphism using the back condition). One thing that I don't quite get it is why these exercises deal with tuples and not just sets. Since Poizat defines the universe of a relation as its underlying set, it seems a bit strange to say that the tuple is in the universe. I suppose this may have to do with results that will be proven in what follows, but I wish he had added a few more motivational remarks in his exposition. – Nagase Aug 28 '14 at 6:02
• Incidentally, one book that has (sort of) helped me a bit with this stuff is Fraïssé's own Course of Mathematical Logic (recommended by Poizat himself). It's by no means easy, but he presents some things in more detail than Poizat. – Nagase Aug 28 '14 at 6:20
• Thanks for the suggestion; I haven't it, but I'm browsing Fraissé book : Theory of Relations (2nd ed, 2000) and it is quite "terse" ... – Mauro ALLEGRANZA Aug 28 '14 at 12:59
• @MauroALLEGRANZA: I made an edit about the tuple issue. Do you think it's better formulated now? – Nagase Aug 30 '14 at 6:27

I will add a long comment regarding the tuple issue.

Poizat's definition of universe [page 1] is "standard" :

an $m$-ary relation $R$ with universe $E$ is a subset of $E^m$.

Thus, at the very beginning of his treatise, he introduce the notion of $m$-tuple :

if the $m$-tuple $\overline a = (a_1,\ldots, a_m)$ in [the universe] $E$ belongs to $R$, we say that it satisfies the relation $R$.

[see the original french version, page 14 :

si le $m$-uple $\overline a$ extrait de $E$ appartient à $R$ on dit qu'il satisfait la relation $R$].

It seems to me that it is only a "shorthand" , and we have to read :

the $m$-tuple $\overline a$ in $E$

as :

the $m$-tuple $\overline a$ [is a finite sequence] of elements belonging to $E$.

The same issue we can find in page 19, when Poizat speaks of (first-order) formulae :

[consider] a formula in the form $f(\overline x)$, where $\overline x$ is a $n$-tuple of variables $(x_1,\ldots, x_n)$. [...] Let us consider an $m$-ary relation $R$, a formula $f(\overline x)$, and an $n$-tuple $\overline a = (a_1,\ldots, a_n)$ in the universe of $R$ [...].

There is also another way to look at a finite sequence $(a_1,\ldots, a_n)$ of $n$ elements in $A$.

We can consider it a a set of pairs : $\{ (1,a_1),\ldots, (n,a_n) \}$. This is a function defined on the set $\{ 1,\ldots, n \}$, i.e. :

$f : n_0^+ \to A$ [where $n_0 = n \backslash \{ 0 \}$ and $n^+ = n \cup \{ n \}$].