I'm trying to solve the exercise in the title and I think it makes no sense. Here's what it says:

An onto map $f: X \to Y$ is called an elementary partial isomorphism between $\mathcal{A}$ and $\mathcal{B}$ if $X \subseteq A$, $Y \subseteq B$ and $$(\mathcal{A},\{x\}_{x\in X}) \equiv (\mathcal{B},\{f(x)\}_{x\in X})$$ $f$ is immediately extensible if for each $a\in A$ (respectively $b\in B$) there is a $b\in B$ (respectively $a\in A$) such that $$(\mathcal{A},\{x\}_{x\in X},a) \equiv (\mathcal{B},\{f(x)\}_{x\in X},b)$$ Suppose every finite, elementary partial isomorphism between $\mathcal{A}$ and $\mathcal{B}$ is immediately extensible. Show $\mathcal{A} \equiv\mathcal{B}$.

From what I can see there are two cases:

  • either there exists a finite, elementary partial isomorphism between $\mathcal{A}$ and $\mathcal{B}$, in which case $\mathcal{A} \equiv\mathcal{B}$ simply by removing the additional constants;
  • or there isn't, so by taking $X=\emptyset$, we obtain $\mathcal{A} \not\equiv\mathcal{B}$.

In either case, the extensibility condition plays no role. Am I getting it wrong?

Also, from what I've looked up, this seems related to Ehrenfeucht–Fraïssé games, but I'm not experienced enough to translate the statement back.

Any help? Thanks.


For the first question, yes, the existence of an elementary (partial) function implies elementary equivalence.

For the second question, yes, this is related to Ehrenfeucht-Fraisse games: the Ehrenfeucht's theorem says that if $\mathcal A,\mathcal B$ are relational structures (of the same signature), then $\mathcal A\equiv \mathcal B$ if and only if every partial isomorphism (not elementary!) is immediately extensible in the analogous sense.

It seems to me like you might have misread the question: if the two structures are countable, then the condition you cited implies not just that $\mathcal A \equiv \mathcal B$, but that actually $\mathcal A\cong \mathcal B$, which is a much stronger condition. Are you sure this isn't what you're supposed to prove here?

  • $\begingroup$ Thanks! Probably, Sacks mixed up his partial isomorphisms. (I have copied the question verbatim.) $\endgroup$ – Andrei Sipoș Nov 6 '14 at 20:27
  • $\begingroup$ @AndreiSipoș: It might also be some funny convention. Bear in mind that the book is quite old. $\endgroup$ – tomasz Nov 6 '14 at 20:43

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.