4
$\begingroup$

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.

Thank you in advance for your help.

$\endgroup$
  • $\begingroup$ 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}$? $\endgroup$ – user642796 Nov 1 '13 at 15:43
  • $\begingroup$ The implication is the other way around: $\mathfrak A \cong_p \mathfrak B$ implies $\mathfrak A \cong_f \mathfrak B$. $\endgroup$ – Levon Haykazyan Nov 1 '13 at 16:02
  • $\begingroup$ 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. $\endgroup$ – Ezra Nov 1 '13 at 18:55
  • $\begingroup$ Now I am totally confused as to what the question is. Can you clarify it? $\endgroup$ – Levon Haykazyan Nov 2 '13 at 1:39
  • $\begingroup$ 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 $\endgroup$ – Ezra Feb 11 '14 at 16:32
3
$\begingroup$

I'll try to answer with some comments.

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.

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