Notes from a talk in a seminar series at Münster on the model theory of the
p-adics.
Based on Pierre Simon's book "A Guide to NIP Theories", and Luc Belair's
survey article "Panorama of p-adic model theory".
# NIP
Definition:
A set \A of subsets of a set X _shatters_ a subset Y (= X
iff for every Z (= Y, there exists A \in \A such that Z = A \cap Y.
Definition:
A formula \phi(x;y) in a complete theory T has _IP_
if for some M |= T,
\{ \phi(M;b) | b \in M^{|y|} \}
shatters some infinite subset of M^{|x|}.
Otherwise, \phi has _NIP_.
T has NIP iff every \phi has NIP.
A structure M has NIP iff Th(M) has NIP.
Remark:
By compactness, \phi has IP iff in any model, there are arbitrarily large
finite subsets of M^{|x|} shattered by instances of \phi in this way.
Examples:
* x|y in \Z has IP, since any finite set of primes is shattered;
* x\in y in set theory has IP;
* x: Suppose the truth value of \phi(a_i,b) alternates infinitely often.
Then for any n and any A (= \{a_0,...,a_n\},
we can find increasing i_j such that
|= \phi(a_{i_j},b) iff a_j \in A.
But then by indiscernability, it also holds of (a_0,...,a_n) that
there exists b' for which
|= \phi(a_j,b') iff a_j \in A.
So \{a_0,...,a_n\} is shattered.
n was arbitrary, so \phi has IP.
<=: Suppose \phi has IP, say (b_i)_{i\in\omega} is shattered by instances
of \phi.
Extract an indiscernable sequence (a_i)_{i\in\omega} by the above
Fact.
Then (a_i)_i is shattered by instances of \phi.
Indeed, let I_0 (= \omega; then the type
\{ \phi(a_i,y) | i \in I_0 \} \cup \{ \neg \phi(a_i,y) | i \notin I_0 \}
is consistent.
Take I_0 to be e.g. the even numbers to get b as required.
Lemma:
A Boolean combination of NIP formulae is NIP.
Proof:
Clear from previous Lemma.
# (Z;+,<) has NIP
Recall: QE in Presburger language L_pres = (0,+,<,(D_n)_{n>1})
where D_n(x) <=> n | x.
Theorem: (Z;+,<) has NIP
Suffices to show no L_pres-atomic formula \phi(x;y) has IP, and we may assume
|x|=1.
* f(x;y)=0, f Z-linear:
for a given y, this holds for all or at most one x, so can't
infinitely alternate on an indiscernable sequence.
* f(x;y)<0, f Z-linear:
given y, defines an interval, so can't infinitely alternate on an
indiscernable (hence monotone) sequence.
* D_n(f(x;y)), f Z-linear:
truth value depends only on x mod n, which is constant for an
indiscernable sequence, so can't infinitely alternate on such.
# ac_m
ac_m : Q_p^* --> (Z_p/(p^{n+1}Z_p)^* ( ~= (Z/p^{n+1}Z)^* )
ac_m(x) := res_m(p^{-v(x)}x)
where res_m : Z_p --> Z_p/p^{n+1}Z_p is the quotient map.
ac := ac_0.
Remark: ac_m is a surjective group homomorphism.
Lemma: a \in Q_p is an nth power iff v(a) is n-divisible and ac_m(a) is an nth
power, where m := 2*v(n).
Proof:
=>: clear
<=:
v(a) is n-divisible, so say v(b^n)=v(a). Replacing a with a/b^n, we
may suppose v(a)=0.
Now say \gamma^n = ac_m(a), and say ac_m(c) = \gamma, v(c)=0.
Let f(x) = x^n-a.
Then v(f(c)) = v(c^n-a) > m = 2*v(n) = 2*v(nc^{n-1}) = 2*v(f'(c)),
so by the appropriate version of Hensel's lemma,
f(x)=0 has a solution.
Lemma: ac_m is definable in the field structure (with parameters).
Proof:
Say k is the exponent of the finite group (Z/p^{n+1}Z)^*.
Then ac_m factors via quotienting by the kth powers of Q_p^*:
Q_p^* ---> Q_p^* / (Q_p^*)^(*k) ---> (Z/p^{n+1}Z)^* ;
the second map is between finite groups, so is definable (with
parameters).
Remark: If v(x) - v(y) > m, then ac(x+y) = ac(y).
# Q_p has NIP
Technicality:
Expand by the parameters needed to define the ac_m. We will prove NIP in
this expanded language, which clearly implies (and actually is easily
equivalent to) NIP in the original language.
Lemma 1:
K |= Th(Q_p);
(x_i)_{i\in \N} indiscernable sequence in K, m \in \N.
Then exists (z_i)_{i\in \N} indiscernable sequence in vK,
such that for any f(X) = \sum_i=0^d a_iX^i \in K[X],
there exist N_0\in \N, l \in \N, \gamma \in vK, b \in (Z/(p^{n+1})Z)^*,
such that for all k > N_0,
v(f(x_k)) = lz_k + \gamma
and ac_m(f(x_k)) = b.
Proof:
Case I: v(x_i) is non-constant.
Then v(x_i) is strictly monotonic, so for k>>0,
v(x_k) has constant position relative to
\{ (v(a_i)-v(a_j))/(j-i) | i,j <= d \}
(in the divisible hull of vK),
and moreover is at least m away from any of them.
Then
v(a_ix_k^i) - v(a_jx_k^j)
= v(a_i) + i*v(x_k) - v(a_j) - j*v(x_k)
= (v(a_i) - v(a_j)) - (j-i)*v(x_k)
= (j-i)*( (v(a_i)-v(a_j))/(j-i) - v(x_k) ),
so the monomials of f(x_k) have distinct valuations, separated by at
least m, and i_0 for which the valuation is least is constant with
respect to k. Also ac_m(x_k) is constant, since it is 0-definable and
(Z/p^{n+1}Z)^* is finite.
So we are done, with z_i := v(x_i),
and b := ac_m(a_{i_0}x_k^{i_0}) = ac_m(a_{i_0})ac_m(x_k)^{i_0}.
Case II: v(x_i) is constant.
Let y_i := x_i - x_0 (i>0).
Note y_i is an indiscernable sequence.
If v(y_i) is non-constant,
let g(X) := f(x_0+X) - f(x_0),
so f(x_i) = f(x_0) + g(y_i),
and we are done by Case I with f(x_0)+g(X) in place of f(X).
Else, since by indiscernability and finiteness of (Z/p^{n+1}Z)^* also
ac(y_i) is constant, v(x_2-x_1) = v(y_2-y_1) < v(y_2) = v(x_2-x_0).
Add a point x_\omega such that (x_i)_{i <= \omega} remains
indiscernable; this is possible by the Fact above.
Let z_i := x_\omega - x_i. Then by indiscernability and the above
inequality, v(z_i) is increasing.
So again we are done by Case I.
Theorem: Q_p has NIP
Proof:
By quantifier elimination, it suffices to check that no \Lmac-atomic formula
\phi(x;y) has IP, and we may assume |x|=1.
* f(x;y)=0, f a polynomial :
easy; dealt with in examples above.
* v(f(x;y)) <= v(g(x;y)), f and g polynomials,
* P_n(f(x;y)), f a polynomial :
Suppose an instance alternates infinitely on an indiscernable
sequence; then by Lemma 1 and the characterisation of P_n in terms of
v and ac_m, we get an indiscernable sequence in vK and a Presburger
formula which alternates infinitely on it, contradicting NIPity of
Presburger arithmetic.