2
$\begingroup$

If $\mathcal L$ is a first order language and $\mathcal T$ is theory over $\mathcal L$, then a model $\mathcal M$ of $\mathcal T$ is pseudofinite if it satisfies all sentences satisfied by all finite models of $\mathcal T$. Does anyone know a good reference for pseudofinite model theory?

In particular, googling I have found that each infinite pseudofinite order is of the form positive integers + copies of Z + negative integers and each of these is elementarily equivalent. Does anybody know a reference with the proof of this?

Basically I want to learn techniques to work with pseudofinite models.

Thanks!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

Being away from home, I can't easily check references, but here's an outline of the proofs for what you quoted from googling: Finite linear orders satisfy the statements

  • There is a first element and there is a last element.

  • Each element except the last has an immediate successor.

  • Each element except the first has an immediate predecessor.

Any infinite linear order satisfying these will be of the form you described, $\mathbb N+(X\cdot\mathbb Z)+\mathbb N^*$ (where $\cdot$ denotes lexicographically ordered product and where $X$ is an arbitrary, possibly empty, linear order). To see that all linear orders of this form are elementarily equivalent, you could use quantifier elimination after expanding the language with constants for the first and last element and binary relation symbols for "$y$ is the $n$-th element after $x$" (one such symbol for each natural number $n$). Alternatively, you could use Ehrenfeucht-Fraïssé games; the duplicator's winning strategy is to match the relative positions of the chosen elements in the two structures. Here "relative position" means not only the ordering relation but also how far apart the elements are, except that, $k$ moves before the end of the game, all distances greater than $2^k$ count as infinite. (The E-F games for first-order elementary equivalence have a pre-specified number of moves, so "$k$ moves before the end" makes sense.)

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks. Are Ehrenfeucht-Fraisse games in general a good way to check if two pseudofinite structures are elementarily equivalent? $\endgroup$
    – Benjamin Steinberg
    Commented Aug 1, 2011 at 10:36
  • $\begingroup$ I should add I was pretty sure that the theory of finite orders meant exactly first and last element and that any other element had a predecessor and successor. Is it completely obvious that all such orders have the form stated. I guess so. The first N is all successors of the first guy, the last N* is all predecessors of the last guy and for each other guy, its predecessors and successors from a copy of Z. $\endgroup$
    – Benjamin Steinberg
    Commented Aug 1, 2011 at 10:39
  • $\begingroup$ How does one prove that all formulas satisfied by finite orders are consequences of the 3 axioms you give? Or alternatively, how do you see each order of the above form is an ultraproduct of finite orders? I'm very far from model theory, so although I'm sure this is elementary it would be nice to see it (or a reference). $\endgroup$
    – Benjamin Steinberg
    Commented Aug 1, 2011 at 11:33
  • $\begingroup$ @Benjamin: denote the theory (i.e., the three axioms + the axioms of linear orders) as $T$, and let $A$ be a sentence valid in all finite orders. Then $A$ is valid in all finite models of $T$. By compactness, it is also valid in some infinite model of $T$. By Andreas’ argument, it is then valid in all infinite models of $T$, hence in all models of $T$. $\endgroup$
    – Emil Jeřábek
    Commented Aug 1, 2011 at 13:17
  • $\begingroup$ @Benjamin, concerning your first comment: My experience with pseudofiniteness is quite limited, but so far, yes, I've found E-F games to be a good way to think about elementary equivalence (in that context and also in other situations). Concerning your second comment: I'd say the theory of finite orders means all the first-order sentences true in all finite orders; it is then a theorem that this theory is axiomatized by these three axioms plus the defining axioms for linear orders. $\endgroup$
    – Andreas Blass
    Commented Aug 1, 2011 at 13:57

You must log in to answer this question.

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