15
$\begingroup$

The most useful way I know to show that two structures are elementarily equivalent is Ehrenfeucht-Fraisse games. These are quite nice and intuitive, and even when I can't use them to solve my problem E-F games usually give me a much better understanding of the structures I'm working with.

In principle, though, one could also use the Keisler-Shelah ultrapower theorem - "Two structures are elementarily equivalent iff they have isomorphic ultrapowers by some ultrafilter" (see Ultrafilters arising from Keisler-Shelah ultrapower characterisation of elementary equivalence; one direction is trivial, Keisler proved the other direction under GCH, and Shelah brought the proof down to ZFC). However, I know of no setting in which this is actually a better way to approach the specific problem of showing elementary equivalence. So, my question is:

If we want to show $\mathcal{A}\equiv\mathcal{B}$, is it ever efficient to go through the Shelah-Keisler ultrapower theorem?

I'm asking about Keisler-Shelah specifically, as opposed to some other result about elementary equivalence, because any K-S based approach to establishing elementary equivalence would presumably involve some set-theoretic combinatorics, and I'm generally interested in set theory cropping up in "concrete"(ish) questions. My suspicion is that the answer is "no," and that the work involved in showing that two structures have isomorphic ultrapowers would always subsume the work involved in establishing elementary equivalence, but I have no real evidence for this.

Improve this question
$\endgroup$
5
  • 5
    $\begingroup$ (You are using the easy direction of the Keisler-Shelah theorem. Feels funny to refer to it as Keisler-Shelah, which is really the converse.) $\endgroup$
    – Andrés E. Caicedo
    Commented Feb 25, 2014 at 3:50
  • 3
    $\begingroup$ That's a good point. Whoops. (I guess I should just be citing Los' Theorem.) $\endgroup$
    – Noah Schweber
    Commented Feb 25, 2014 at 4:34
  • 2
    $\begingroup$ While it is not an example of the sort you want, Robinson’s joint consistency theorem has a slick two-line proof using the Keisler–Shelah theorem. What I like about it is that unlike most applications of ultraproducts one encounters (which usually go through with any saturated models, and sometimes are just a glorified appeal to the compactness theorem), this one essentially relies on specific properties of ultrapowers (namely, that it is a uniform construction commuting with reducts). $\endgroup$
    – Emil Jeřábek
    Commented Feb 25, 2014 at 12:17
  • 1
    $\begingroup$ The slick two line proof of Robinson's joint consistency theorem can also be proven using a weaker (and easier to prove) version of the Keisler-Shelah isomorphism theorem stating that two elementary equivalent structures have isomorphic direct limits of ultrapowers. $\endgroup$
    – Joseph Van Name
    Commented Feb 26, 2014 at 4:19
  • $\begingroup$ Sorry I neglected this question for so long - thanks to everyone for the nice answers! I've accepted Benjamin's answer because I found it the most impressive, but all of them were cool. $\endgroup$
    – Noah Schweber
    Commented Mar 8, 2014 at 23:39

4 Answers 4

Reset to default
18
$\begingroup$

People in algebra use Keisler-Shelah a lot. For example, Malcev proved that for fields $F,K$ one has $GL_m(F)$ is elementary equivalent to $GL_n(K)$ iff $m=n$ and $F$ is elementarily equivalent to $K$. The idea is first you prove that this is equivalent to $M_m(F)$ is elementarily equivalent to $M_n(K)$. Then you take ultrapowers and use that taking matrices commutes with ultrapowers to deduce that $M_m(F)$ and $M_n(K)$ have isomorphic ultrapowers iff $m=n$ and $F,K$ have isomorphic ultrapowers, i.e. $F,K$ are elementarily equivalent.

There are other examples like this in algebra. A good reference is the paper On Malcev's theorem on elementary equivalence of linear groups by Beidar and Mikhalev (Contemp. Math. 131 Part I (1992), 29-35).

I believe Sohrabi and Miasnikov also use Keisler-Shelah in their work on elementary equivalence of nilpotent groups.

Improve this answer
$\endgroup$
14
$\begingroup$

Here is an instance where it seems fine to use Keisler-Shelah.

Let ${\cal A}$ be the graph consisting of a single infinite beaded chain, or more concretely, the integers under adjacency. That is, ${\cal A}=\langle\mathbb{Z},\sim\rangle$, where $n\sim m$ just in case they differ by exactly one.

And let ${\cal B}$ consist of two (or more) disconnected copies of ${\cal A}$.

It is easy to see that the ultrapower of either ${\cal A}$ or ${\cal B}$ by any ultrafilter on a countable index set consists of continuum many such beaded chains. Thus, the structures ${\cal A}$ and ${\cal B}$ have isomorphic ultrapowers, and so they are elementary equivalent by Keisler-Shelah.

(Essentially the same argument came up in my answer to Stefan Geschke's queston Is non-connectedness of graphs first order axiomatizable?, but I had used Löwenheim-Skolem there rather than Keisler-Shelah, so this example may not satisfy run afoul of your requirements. But I think the argument from Keisler-Shelah is no harder or easier than the argument from Löwenheim-Skolem.)

Improve this answer
$\endgroup$
9
  • $\begingroup$ I like this! Ideally, I'd love an example where the E-F proof is noticeably harder (or, more likely, just messier) than the K-S approach, but this is cool! $\endgroup$
    – Noah Schweber
    Commented Feb 25, 2014 at 3:38
  • $\begingroup$ For a contrasting perspective, let me confess that I almost never use E-F to show elementary equivalence. Perhaps I should learn more about that... $\endgroup$
    – Joel David Hamkins
    Commented Feb 25, 2014 at 3:52
  • 1
    $\begingroup$ The theory of the adjacency relation is kind of trivial, as it is uncountably categorical. What I find more fun is that a similar argument also occasionally applies to non-categorical theories, such as discrete linear orders. In particular, the nonexistence of a sentence distinguishing finite linear orders of even and odd length can be shown by taking ultraproducts of an increasing sequence of even orders on one side and odd orders on the other side, and giving a simple explicit isomorphism (leave the constant functions unchanged, and increase the values of other functions by one). $\endgroup$
    – Emil Jeřábek
    Commented Feb 25, 2014 at 11:23
  • 1
    $\begingroup$ Emil, that example is very nice. I agree that this theory is trivial, in the sense that it is uncountably categorical---and this is essentially what the ultrapower argument is using---but I think it is still a forceful example, since without those uncountable considerations, it is not immediately clear that these two models should be elementarily equivalent. But perhaps Noah will counter this perspective with some E-F game... $\endgroup$
    – Joel David Hamkins
    Commented Feb 26, 2014 at 2:30
  • $\begingroup$ The standard E–F argument here is to show by induction on $n$ that the Duplicator has a winning strategy in the $n$-round game for $(A,a_1,\dots,a_m)$ and $(B,b_1,\dots,b_m)$ if for each $i,j$, the distance between $a_i$ and $a_j$ equals the distance between $b_i$ and $b_j$, or both distances are (infinite or) at least $2^n$ or some such number. The proof is straightforward, but I don’t see how to avoid the explicit numerical estimate which makes the argument messier than using uncountable categoricity. ... $\endgroup$
    – Emil Jeřábek
    Commented Feb 26, 2014 at 12:10
9
$\begingroup$

As in Benjamin Steinberg’s answer, these are examples related to algebra.

The Ax–Kochen–Ershov principle states that two unramified henselian valued fields are elementarily equivalent iff their value groups and their residue fields are respectively elementarily equivalent. (There are many variations and extensions of the statement in the literature.) An outline of the proof is as follows: we may assume the two fields are countable and that CH holds. We take ultrapowers over a uniform ultrafilter on $\omega$: the value groups and residue fields of the ultrapowers are then isomorphic, and one can use this and the saturation of the ultrapowers to construct a valued field isomorphism by a back-and-forth transfinite sequence of countable partial isomorphisms.

Likewise, a crucial part in Ax’s analysis of the theory of finite and pseudofinite fields is the result that two pseudofinite fields with the same absolute numbers (i.e., the relative algebraic closure of the prime field) are elementarily equivalent. Again, this is shown by a back-and-forth construction of an isomorphism of their ultrapowers.

Improve this answer
$\endgroup$
4
$\begingroup$

You may also look at

Lelek’s conjecture,

where Shelah's theorem is used in an essential way (the questions at the end of the paper ask if one can give an easier (more direct) proof of the results without using Shelah’s theorem).

Of course this answer is not along the lines you want, but possibly the other direction.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .