THE RATIONALS HAVE AN AZ-ENUMERATION

Abstract

Let M be an ω-categorical structure (that is, M is countable and Th(M) is ω-categorical). A nice enumeration of M is a total ordering [pr ] of M having order-type ω and satisfying the following. Whenever a_i, i<ω, is a sequence of elements from M, there exist some i<j<ω and an automorphism σ of M such that σ(a_i) = a_j and whenever b[pr ]a_i, then σ(b)[pr ]a_j.

Such enumerations were introduced by Ahlbrandt and Ziegler in [1] where they showed that any Grassmannian of an infinite-dimensional projective space over a finite field (or of a disintegrated set) admits a nice enumeration; this combinatorial property played an essential role in their proof that almost strongly minimal totally categorical structures are quasi-finitely axiomatisable.

Recall that if M is ω-categorical and a is a k-tuple of distinct elements from M (with tp(a) non-algebraic), then the Grassmannian Gr(M; a) is defined as follows. The domain of Gr(M; a) is the set of realisations of tp(a) in M^k, modulo the equivalence relation xEy if x and y are equal as sets. This is a 0-definable subset of M^eq, and now the relations on Gr(M; a) are by definition precisely those which are 0-definable in the structure M^eq. (In particular, Gr(M; a) is also ω-categorical.)

Notice that it is by no means clear that if M admits a nice enumeration, then so do Grassmannians of M. However, there is a strengthening of the notion of nice enumeration for which this is the case.