Cantor's theorem, unclear generalization

Question

Feferman and Barwise show here (20MB pdf) (Feferman Barwise Model theretic logics, page 58) in the Theorem 4.3.1. that Counatble partially isomorphic structures are isomorphic. Then they claim in a Remark We see from theorem 4.3.1. that $\cong_p$ is strictly stronger than elementary equivalence. I do not see how this Remark follows from the theorem 4.3.1. which speaks only about countable structures (and so it is not in general strictly stronger) and at the same time not about elementary equivalence but about an isomorphism.

Answer 1

EDIT: For additional clarity, here's a summary of the answer below:

• $\cong$ always implies $\cong_p$ and $\equiv$; this is trivial.

• $\cong_p$ always implies $\equiv$; this can be proved via the characterization of $\equiv$ via Ehrenfeucht-Fraisse games.

• For countable structures, $\cong_p$ implies (hence by bulletpoint 1, is equivalent to) $\cong$; this is Cantor's argument.

• For general structures, $\cong_p$ is strictly weaker than $\cong$: that is, there are uncountable $\mathcal{A},\mathcal{B}$ such that $\mathcal{A}\not\cong\mathcal{B}$ but $\mathcal{A}\cong_p\mathcal{B}$. The example I give below is a pair of ordinals, but there are many others.

  • Note that this, together with the second bulletpoint, implies that $\equiv$ is strictly weaker than $\cong$ for general structures. In fact, $\equiv$ is strictly weaker than $\cong$ even for countable structures, via much simpler examples (e.g. the linear orders $\mathbb{N}$ vs. $\mathbb{N}+\mathbb{Z}$).

So in general, we have $$\cong\implies \cong_p\implies\equiv,$$ with no implications reversing; if we restrict to countable structures, we have $$\cong\iff\cong_p\implies\equiv$$ (and the "$\implies$" remains strict).

---

The text (by Ebbinghaus, in a volume edited by Barwise and Feferman) correct.

The fact that $\cong_p$ implies $\equiv$ is an immediate corollary of the stronger theorem that $\equiv$ is characterized by Ehrenfeucht-Fraisse games (see Corollary 4.2.4 in Barwise/Feferman), the point being that any winning strategy for Duplicator in the "full back-and-forth game" associated to $\cong_p$ is automatically a winning strategy for Duplicator in each finite-length back-and-forth game.

(If you're unfamiliar with the game description of $\cong_p$, let me know and I'll elaborate.)

So $\cong_p$ implies $\equiv$. Meanwhile, there are elementarily equivalent structures which are not partially isomorphic: take any two elementarily equivalent countable non-isomorphic structures. So $\equiv$ does notimply $\cong_p$.

Putting these facts together shows that indeed $\cong_p$ is strictly stronger than $\equiv$. However, it does focus on countable structures in a possibly-unsatisfying way, and we can ask:

Does $\cong_p$ properly strengthen $\equiv$ even for uncountable structures?

That is:

Are there uncountable structures $\mathcal{A},\mathcal{B}$ which are elementarily equivalent but not partially isomorphic?

The answer to this question is again "yes," but the proof is less trivial. Off the top of my head, the simplest example is a pair of distinct uncountable ordinals which, when viewed as linear orders, are elementarily equivalent. (Such a pair must exist by a standard pigeonhole argument.) The key fact now is the following (which I believe is folklore):

• Theorem: no two distinct ordinals (again, viewed as linear orders) are partially isomorphic.

If you prefer: $\cong_p$ is just $\cong$ when restricted to well-orderings. This is not too hard to prove, but let me know if you want me to add details here.

Putting all this together, we get:

• Corollary: there are uncountable, elementary equivalent well-orderings which are not partially isomorphic.

Indeed, we can even demand that they have any prescribed uncountable cardinality: e.g. there are elementarily equivalent non-partially-isomorphic well-orderings $\mathcal{A},\mathcal{B}$ of cardinality $\aleph_2$ and $\aleph_\omega$, respectively. This takes a bit more thought, however.

---

Incidentally, the following theorem - I believe due to Barwise - may be of interest to you:

• Theorem: the following are equivalent:

  • $\mathcal{A}\cong_p\mathcal{B}$.

  • $\mathcal{A}\equiv_{\infty\omega}\mathcal{B}$ (that is, they agree on all $\mathcal{L}_{\infty\omega}$-sentences).

  • There is some generic extension of the universe in which $\mathcal{A}\cong\mathcal{B}$.

  • In every generic extension of the universe in which both $\mathcal{A}$ and $\mathcal{B}$ are countable we have $\mathcal{A}\cong\mathcal{B}$.

The last two conditions, while quite useful, rely on the technique of forcing; if you're not familiar with forcing, you should ignore them for now.