# How can be a set of partial isomorphisms defined from a n-back-and-forth system?

While studying partial Ebbinghaus-Flum's Mathematical Logic, I came across the partial isomorphism definition, as build upon an $n$-back-and-forth system. Consequently, the question I raise in the title.

Now I quote from the textbook:

«$\mathfrak{A}$ and $\mathfrak{B}$ are said to be finitely isomorphic, written $\mathfrak{A}\cong_{f}\mathfrak{B}$, iff there is a sequence $\left(I_{n}\right)_{n\in\mathbb{N}}$ with the following properties:

• Every $I_{n}$ is a nonempty set of partial isomorphism form $\mathfrak{A}$ to $\mathfrak{B}$.

• (Forth property) For every $p\in I_{n+1}$ and $a\in A$, there is $q\in I_{n}$ s.t. $\left(q\supset p\right)$ and $a\in dom\left(q\right)$.

• (Back property) For every $p\in I_{n+1}$ and $b\in B$, there is $q\in I_{n}$ s.t. $\left(q\supset p\right)$ e $b\in rg\left(q\right)$.»

This definition entails the following one (I quote again):

«$\mathfrak{A}$ and $\mathfrak{B}$ are said to be partially isomorphic, written $\mathfrak{A}\cong_{p}\mathfrak{B}$, iff there is a sequence I such that:

• $I$ is a nonempty set of partial isomorphisms form $\mathfrak{A}$ to $\mathfrak{B}$.

• (Forth property) For every $p\in I$ and $a\in A$, there is $q\in I$ s.t. $\left(q\supset p\right)$ and $a\in dom\left(q\right)$.

• (Back property) For every $p\in I$ and $b\in B$, there is $q\in I$ s.t. $\left(q\supset p\right)$ e $b\in rg\left(q\right)$.»

As far as I can understand, it is a matter of cardinality: two structures $\mathfrak{A}$ and $\mathfrak{B}$ may be uncountable, and yet be partially isomorphic (i.e. countable isomorphic), and in this case I is the set of all partial isomorphisms from $\mathfrak{A}$ to $\mathfrak{B}$; while the chain $\left(I_{n}\right)_{n\in\mathbb{N}}$ indicates the precise $n\in\mathbb{N}$ for which extensions are allowed. However, even if my take on this is correct, I still feel uncomfortable considering the set $I$ as a single set of extended maps.

• In the definition of the "back-and-forth sequence" do Ebbinghaus and Flum also assume that $I_{n+1} \subseteq I_n$ for all $n \in \mathbb{N}$? – user642796 Nov 1 '13 at 15:43
• The implication is the other way around: $\mathfrak A \cong_p \mathfrak B$ implies $\mathfrak A \cong_f \mathfrak B$. – Levon Haykazyan Nov 1 '13 at 16:02
• No, they don't assume the property holds for all $n\in\mathbb{N}$ in $\left(I_{n}\right)_{n\in\mathbb{N}}$: there are very few more details left to the reader, and then the book turns to other - yet related - arguments. That is correct, we deduce finite isomorphism from partial isomorphism; however, the book basically offers a classical (structural) definition of partial isomorphism at first, then introduces the back-and-forth method, with which the notion of finite isomorphism is made precise, and eventually re-defines partial isomorphism in terms of back-and-forth. – Ezra Nov 1 '13 at 18:55
• Now I am totally confused as to what the question is. Can you clarify it? – Levon Haykazyan Nov 2 '13 at 1:39
• I find myself exhuming this particular topic, even though a long meantime has been through, because I really couldn't clear up the nitty gritty. As far as my knowledge extends, Ebbinghaus and Flum's "finite isomorphism" formulation is rather unique among the dedicated literature, so I would ask to whomever may want to shed some light on the argument what is actually a finite isomorphism, how differentiates a partial isomorphism and -if it's not asking too much- what structures are indeed finitely isomorphic but not partially so. Thank you sincerely – Ezra Feb 11 '14 at 16:32

This approach to structures origins with Roland Fraïssé.

In Heinz-Dieter Ebbinghaus & Jörg Flum & Wolfgang Thomas, Mathematical logic (2nd ed, 1984), we have :

XI.1.1 Definition [page 180] : Let $\mathfrak A$ and $\mathfrak B$ be ($S$)-structures and let $p$ be a map. $p$ is said to be a partial isomorphism from $\mathfrak A$ to $\mathfrak B$ [...].

And :

XI.1.3 Definition [page 182] : [Two structures] $\mathfrak A$ and $\mathfrak B$ are said to be finitely isomorphic, written $\mathfrak A \cong_f \mathfrak B$, iff there is a sequence $(I_n)_{n \in \mathbb N}$ with the following properties :

(a) Every $I_n$ is a nonempty set of partial isomorphism from $\mathfrak A$ to $\mathfrak B$.

[...].

Here condition (a) amounts to : for every $n$ there is $I_n$ such that...

Finally :

XI.1.4 Definition : $\mathfrak A$ and $\mathfrak B$ are said to be partially isomorphic, written $\mathfrak A \cong_p \mathfrak B$, iff there is a set $I$ such that

(a) $I$ is a nonempty set of partial isomorphism from $\mathfrak A$ to $\mathfrak B$.

[...].

According to Ebbinghaus' comment [page 182] :

Informally we can express (b) and (c) [the back-and-forth conditions] as follows : [a] partial isomorphisms $s \in I_{n+1}$ can be extended $(n+1)$ times; the corresponding extensions lie in $I_n, I_{n-1}, \ldots, I_1$ and $I_0$.

In order to understand the difference between $\mathfrak A \cong_f \mathfrak B$ and $\mathfrak A \cong_p \mathfrak B$ we have to see :

XI.1.5 Lemma :

(c) if $\mathfrak A \cong_f \mathfrak B$ and $\mathfrak A$ is finite, then $\mathfrak A \cong \mathfrak B$ [i.e.they are isomorphic].

(d) if $\mathfrak A \cong_p \mathfrak B$ and $A$ and $B$ are at most countable, then $\mathfrak A \cong \mathfrak B$.

All this "machinery" converges towards :

XI.2.1 Fraïssé's Theorem. Let $S$ be a finite symbol set and $\mathfrak A, \mathfrak B$ $S$-structures. Then :

$\mathfrak A \equiv \mathfrak B$ [i.e. elementary equivalent] iff $\mathfrak A \cong_f \mathfrak B$.

We may compare with Bruno Poizat, A Course in Model Theory : An Introduction to Contemporary Mathematical Logic (2000 - french ed, 1985) we can find the notion of local isomorphism between two relations $R,R'$ [page 2].

He define : $p$-isomorphism, which is a local iso "extendible" $p$ times. He use the symbol $S_p(R,R')$ to denote the set of $p$-isomorphism between $R$ and $R'$.

Poizat defines $\omega$-isomorphism (or elemetary local isomorphism) as a local iso $s$ that is a $p$-isomorphism for every $p \ge 0$.

Then he defines the relations of $p$-equivalence between $k$-tuples [page 4] and of $\omega$-equivalece : two $k$-tuples are $\omega$-equivalent if they are $p$-equivalent for every $p$.

Thus, $\omega$-equivalence corresponds to Ebbinghaus' finitely isomorphic : $\mathfrak A \cong_f \mathfrak B$.

Then Poizat defines (in a purely algebraic way, in the style of Fraïssé) elementary equivalence in terms of the following condition :

If the empty function [$f_0$] is a $p$-isomorphism from $R$ to $R'$ for every $p$ (i.e. $S_\omega(R,R')$ is nonempty).

Poizat proves [page 5] :

Th 1.3. : If $R$ is finite, defined on $p$ elements, then every relation $S$ that is $(p+1)$-equivalent to it is isomorphic to it.

which looks like Ebbinghaus' part (c) of XI.1.5 Lemma.

Poizat [page 11] extends the back-and-forth conditions for local isomorphism to ordinals, and introduces the notions of $\infty$-isomorphism and $\infty$-equivalence.

He proves [page 13] :

Th 1.14. : Two $\infty$-equivalent denumerable relations are isomorphic.

which looks like Ebbinghaus' part (d) of XI.1.5 Lemma.

Finally, he states [page 24] :

Th.2.2 (Fraïssé's Theorem). : ...

form which he derives as an immediate consequence :

two $m$-relations are elementary equivalent iff they satisfy the same sentences

which is what we may expect...

In Poizat, page 11, we can find a useful comment :

It is important not to confuse $\infty$-isomorphism with (for example) $\omega$-isomorphism. If we adopt Ehrenfucht's formulation of Fraïssé's back-and-forth method, then elementary equivalence can be characterized as follows : Consider two players, the first choosing an element in $R$ or $R'$ each round, the second replying with an element in the universe of the other relation. By definition, the second player wins the game in $p$ rounds if, at the end of $p$ choices, they have two (locally) isomorphic $p$-tuples; to say that two relations are elementary equivalent is to say that for every $p$ the second player has a strategy guaranteed to win the $p$-stage game, that is to say, a strategy, depending on $p$ [emphasis added], that is effective, provided that he knows in advance that only $p$ rounds will be played. On the other hand, in the case of $\infty$-equivalence, the second player has a uniform winning startegy [emphasis added], always the same, that makes him win no matter how many rounds are played.