A TALK ON ‘DEPENDENT PAIRS’

AYHAN GÜNAYDIN

1. A crash course on ‘Dependent theories’

Throughout T denotes a complete theory in the language L and 𝕄 is a sufficiently saturated model of T. Also x, y denote tuples of variables whose lengths will not be specified unless it is really needed. Likewise a, b will denote tuples of elements from 𝕄. Also if x is of length m, then 𝕄_{x} denotes 𝕄^{m}.

Let ϕ(x, y) be an L-formula. Remember that ϕ is said to be unstable if there are two sequences (a_{i} : i ∈ ℕ) and (b_{i} : i ∈ ℕ) from 𝕄_{x} and 𝕄_{y} respectively such that for every i, j ∈ ℕ

𝕄 ⊧ ϕ(a_{i}, b_{j}) ⟺ i < j.

Also T is called stable if there are no unstable formulas. Very roughly this says that we cannot ‘define ordering’ within T.

The original definition of dependent is a generalization of this, saying vaguely that we cannot ‘define elementship’ within T. Here is the precise definition.

Definition 1.1. (1) A formula ϕ(x, y) is independent if there are two sequences (a_{i} : i ∈ ℕ) and (b_{I} : I ⊆ ℕ) of tuples of elements from 𝕄 such that for every i ∈ ℕ and I ⊆ ℕ

𝕄 ⊧ ϕ(a_{i}, b_{I}) ⟺ i ∈ I.

(2) The theory T is dependent if there are no independent formulas.

It is easy to see that stable theories are dependent: If there are a formula ϕ(x, y) and sequences (a_{i} : i ∈ ℕ) and (b_{I} : I ⊆ ℕ) as in the first part of the definition, then we can define b′_{j} to be b_{I_{j}}, where I_{j} := {k ∈ ℕ : k < j}. Now the sequences (a_{i} : i ∈ ℕ) and (b′_{j} : j ∈ ℕ) witness that ϕ(x, y) is unstable. Moreover stable is equivalent to simple+dependent.

How about the o-minimal theories? For this we need to know the following:

Facts. (1) In order to check that T is dependent it is enough to check that every formula ϕ(x, y) where x is of length one is dependent.

(2) A formula ϕ(x, y) is independent if and only if for every finite set F and A ∈ P(F) there is a tuple b from 𝕄 such that A = F ∩ ϕ(𝕄_{x}, b). (This is the -so called- Vapnik-Chervonenkis property)

Date: Thursday 11^{th} March, 2010,13:51.

Now let T be an o-minimal theory and ϕ(x, y) an L-formula where the length of x is one. There is a natural number N such that given tuple b from 𝕄, the definable set ϕ(𝕄, b) has at most N components. Now let F = {f_{1}, …, f_{2N+1}} be a set of cardinality 2N + 1, and let

A = {f_{2k+1} : k = 0, …, N}.

It is easy to see that there is no way of ‘cutting’ A out of F using ϕ(𝕄, b).

There is yet another condition equivalent to T being dependent. Actually that is the only condition we use in the sequel.

Fact. The theory T is dependent if and only if for every formula ϕ(x, y), every indiscernible sequence (a_{i} : i ∈ ℕ) from 𝕄_{x}, and every b ∈ 𝕄_{y} the set

{i ∈ ℕ : 𝕄 ⊧ ϕ(a_{i}, b)}

is either finite or cofinite.

The main aim of this talk is to illustrate certain structures are dependent (a structure is dependent if its theory is).

From now on A = (A, <, …) is an o-minimal expansion of a densely ordered abelian group in the language L and B a subset of A. We consider the structure (A, B) in the language L(U) := L ∪ {U}, where U is a unary relation symbol not in L. We basically have two cases according to B being dense or discrete in its convex hull in A. We handle these cases separately.

2. Dense case

Let B be dense in A and define T_{B} to be the theory of (A, B). Our main theorem in this case is is as follows.

Theorem 2.1. Suppose that for every model (M, N) of T_{B} the following hold:

(i) every subset of N^{n} definable in (M, N) is a boolean combination of sets of the form S ∩ K, where S ⊆ M^{n} is definable in M and K ⊆ M^{n} is ∅-definable in (M, N),

(ii) every subset of M^{m} definable in (M, N) is a boolean combination of subsets of M^{m} defined by

∃y_{1} ⋯ ∃y_{n} U(y_{1}) ∧ ⋯ ∧ U(y_{n}) ∧ φ(x_{1}, …, x_{m}, y_{1}, …, y_{n}),

where φ is a quantifier-free L-formula (possibly with parameters from M),

(iii) Every open subset of M definable in (M, N) is a finite union of intervals.

Then T_{B} is dependent.

Sketch of the proof. Let ψ(x, y) be an L(U)-formula, (a_{i})_{i∈ℕ} an indiscernible sequence from 𝕄^{n} and b ∈ 𝕄^{p}. Reduction: It is enough to assume either U(a_{i}) for each i or a_{i} ∉ dcl(U(𝕄), b) for each i. Case 1: a_{i} ∈ U(𝕄) for each i. Using (i) take an L-formula φ(x, y, z), an L(U)-formula χ(x) and c ∈ 𝕄^{l} such that for every i we have

𝕄 ⊧ ψ(a_{i}, b) iff 𝕄 ⊧ φ(a_{i}, b, c) ∧ χ(a_{i}).

Since o-minimal theories are dependent and (a_{i})_{i} is indiscernible in (M, N) we have the desired result. Case 2: n = 1 and a_{i} ∉ dcl(U(𝕄), b) for every i. Using (ii) ψ(x, y) is equivalent to

∃z_{1} … ∃z_{m}( ⋀_{n=1}^{m} U(z_{n}) ∧ φ(x, y, z_{1}, …, z_{m})),

for some L-formula φ(x, y). Then for every g_{1}, …, g_{m} ∈ U(𝕄) the set

{a ∈ 𝕄 | 𝕄 ⊧ φ(a, b, g_{1}, …, g_{m})}

is a union of intervals and points. Since each a_{n} is dcl-independent from b, g_{1}, …, g_{m} we can assume that it is a finite union of open intervals and hence open. This implies that the set

{z ∈ 𝕄 | 𝕄 ⊧ ψ(z, b)}

is a union of open sets and hence open. By (iii), it is a finite union of open intervals. Hence the set

{n : 𝕄 ⊧ ψ(a_{n}, b)}

is either finite or cofinite.

Remark. We do not really need that B is dense for this theorem as it is stated; but when we assume that it is, we have shown in a later paper that the first two conditions imply the last one. So we can either assume B is dense or the last condition of the theorem.

2.1. Examples. Here we list the pairs that the theorem above can be applied to and give references for the verification of the conditions (i),(ii) and (iii).

1. Dense pairs of o-minimal structures. These are studied by L. van den Dries in [5]. Let T be a complete o-minimal theory extending the theory of ordered abelian groups. A pair (M, N) of models of T is called dense pair if N ⪯ M, N ≠ M and N is dense in M. Let T_{d} be the theory of such pairs. The conditions (i), (ii) and (iii) are Theorems 1, 2 and 5 of [5] respectively.

2. Multiplicative subgroups of a real closed field of finite rank. Let R be a real closed field and G ≤ R^{>0} be of finite rank > 1 (this means G has a finitely generated subgroup H such that G/H is a torsion group and G is dense in R^{>0}). Let T (G) be the theory of (R, G). Conditions (ii) and (iii) for T (G) are theorems from [6] and [1] respectively; and (i) follows from a quantifier elimination result from [1].

3. Multiplicative subgroups of a real closed field of finite rank and power functions. Let R and G be as above and let tau ∈ R \ ℚ. Consider the expansion R̃ of the real closed field R by the power function x ↦ x^{τ} and let T^{τ} (G) be the theory of (R̃, G). Then in [7] it is proven that the conditions (i), (ii) and (iii) hold for T^{τ} (G) for co-countably many τ’s.

3. Discrete Case

For the second case assume that A expands a real closed field. We handle this case in a different language: we extend L by a unary function symbol ϕ to get L(ϕ) (this ϕ picks up the closest element of B to a given element of a, which can be done because B is discrete; more to come later). Below T is a complete o-minimal theory with quantifier elimination and universal axiomatization.

Theorem 3.1. Let T (ϕ) be an L(ϕ)-theory extending the theory of A and 𝕄 a monster model of it. Suppose that

(i) the theory T (ϕ) has quantifier elimination, (ii) for every (M, ϕ) ⊧ T (ϕ) and N ⪯ M with ϕ(N) ⊆ N and every

m_{1}, …, m_{n} ∈ M

ϕ( dcl(N, m_{1}, …, m_{n}) ⊆ dcl (ϕ(N), r_{1}, …, r_{l}),

where l ≤ n and r_{1}, …, r_{l} ∈ M. (iii) for all functions f : 𝕄^{n+k} → 𝕄 and g : 𝕄^{j+l} → 𝕄, both ∅-definable

in the L-reduct of 𝕄, for every indiscernible sequence (a_{i})_{i∈ℕ} with a_{i,1}, …, a_{i,j} ∈ ϕ(𝕄), and tuples b_{1} ∈ 𝕄^{k} and b_{2} ∈ (ϕ(𝕄))^{l}, the set

{i ∈ ℕ | 𝕄 ⊧ ϕ(f(a_{i}, b_{1})) = g(a_{i,1}, …, a_{i,j}, b_{2})}

is finite or cofinite. Then T (ϕ) is dependent.

The proof of this theorem is boring, hence I will not prove it here. The applications are more interesting.

3.1. Tame pairs. Let T be a complete o-minimal theory extending the theory of real closed fields and L its language. After extending T by definitions, we can assume without loss of generality that T has quantifier elimination. Let T_{t} be the theory of all structures (A, B), where A, B are models of T such that A ≠ B, B ⪯ A and for every a ∈ A which is in the convex hull of B, there is a unique ϕ(a) ∈ B such that |a − ϕ(a)| < b for all b ∈ B^{>0}. Note that ϕ can be extended to all A by setting ϕ(a) = 0 if a is not in the convex hull of B, and we call the resulting map as the standard part map. The structures (A, B) and (A, ϕ) are interdefinable. Since T has quantifier elimination, it follows from the results from [3] that T_{t} is complete and (A, ϕ) has quantifier elimination.

The theory T_{t} of tame pairs of models of T is closely related to the theory T_{c} of pairs (A, V), where A ⊧ T and V is a T -convex subring of A and V ≠ A (here and below a T -convex subring of a model A of T is a convex subring that is closed under all the continuous ∅-definable unary functions). Since T_{c} is weakly o-minimal (see [3]), T_{c} is dependent. Note that for every model (A, B) of T_{t}, the pair (A, V) is a model of T_{c}, where V is the convex closure of B. In this case, for every b ∈ B and a ∈ A (3.1) ϕ(a) = b iff a = b or (a − b ∈ V and (a − b)^{−1} ∉ V) or (b = 0 and a ∉ V).

Since V is local subring of A, there is a valuation v : A^{×} → Γ with

V = {a ∈ A : v(a) ≥ 0}.

Further let V̄ be the residue field of v. By Theorem 2.12 of [3] the map B ↪ V → V̄ is bijective. Thus V̄ can be made into to a model of T such that the map becomes an isomorphisms of L-structures. We need the following result from [3].

Fact 1. Let A, A^{∗} be models of T such that A ⪯ A^{∗} and let a ∈ A^{∗} \ A. Suppose that W and W′ are T -convex subrings of A and A⟨a⟩ with A∩W′ = W and a ∈ W′ with ā ∉ \overline{W}. Then \overline{W′} = \overline{W} ⟨ā⟩.

Now we are in a position to prove our main result.

Theorem 3.2. T_{t} is dependent.

Proof. We will show that T_{t} satisfies the assumptions of Theorem 3.1. As already mentioned above, T_{t} satisfies (i) by Theorem 5.9 from [3]. Now we consider (iii). Let (a_{i})_{i∈ω} be an indiscernible sequence from 𝕄^{n} such that there is a positive j ≤ n with a_{i,1}, …, a_{i,j} ∈ ϕ(𝕄) for every i ∈ ω. Also let b_{1} ∈ 𝕄^{k} and b_{2} ∈ ϕ(𝕄)^{l} and further f, g be as in (iii) of Theorem 3.1. We now want to show that

J := {i ∈ ω : 𝕄 ⊧ ϕ(f(a_{i}, b_{1})) = g(a_{i,1}, …, a_{i,j}, b_{2})}

is finite or cofinite. Since ϕ(𝕄) is a model of T, we have that for every i ∈ ω

g(a_{i,1}, …, a_{i,j}, b_{2}) ∈ ϕ(𝕄).

By (3.1), there is an L(U)-formula ψ such that

T_{t} ⊧ ϕ(f(a_{i}, b_{1})) = g(a_{i,1}, …, a_{i,j}, b_{2}) ⟺ T_{c} ⊧ ψ(a_{i}, b_{1}, b_{2}).

Since T_{c} is dependent, J is finite or cofinite.

It is left to show (ii). So let (A, ϕ) ⊧ T_{t} and B ⪯ A with ϕ(B) ⊆ B and a_{1}, …, a_{n} ∈ A. Let W_{B} be the T -convex closure of ϕ(B) in B and W_{A} the T -convex closure of ϕ(A) in A. As noted before there is an isomorphism ι from ϕ(A) to \overline{W_{A}} mapping ϕ(a) to \overline{ϕ(a)} for every a ∈ A. Without loss of generality, we can assume that there is a positive l ≤ n such that a_{1}, …, a_{l} ∈ W_{A} and for every function f : A^{n} → A ∅-definable in A

(3.2)  if f(a_{1}, …, a_{n}) ∉ B⟨a_{1}, …, a_{l}⟩, then f(a_{1}, …, a_{n}) ∉ W_{A}.

Using Fact 1 inductively, we get that \overline{B⟨a_{1}, …, a_{l}⟩ ∩ W_{A}} = \overline{W_{B}}⟨ā_{1}, …, ā_{l}⟩. Now by (3.2)

B⟨a_{1}, …, a_{l}⟩ ∩ W_{A} = B⟨a_{1}, …, a_{n}⟩ ∩ W_{A}.

Therefore

\overline{B⟨a_{1}, …, a_{n}⟩ ∩ W_{A}} = \overline{W_{B}}⟨ā_{1}, …, ā_{l}⟩.

Hence dim \overline{B⟨a_{1}, …, a_{n}⟩ ∩ W_{A}}/\overline{W}_{B} ≤ n. Using the isomorphism ι, we get that

dim ϕ(B⟨a_{1}, …, a_{n}⟩) − dim ϕ(B) ≤ n.

So assumption (ii) of Theorem 3.1 also holds for T_{t}. □

3.2. Discrete groups. Let ℝ̃ be an o-minimal expansion of (ℝ, <, +, ·, 0, 1) which is polynomially-bounded with field of exponents ℚ. Let T be the theory of ℝ̃ and L be its language. We consider the structure (ℝ̃, 2^{ℤ}). Since 2^{ℤ} is discrete, we can define a function λ : ℝ → 2^{ℤ} ∪ {0} by

λ(x) := \{ \begin{matrix}g, & x > 0, g ∈ 2^{ℤ} and g ≤ x < 2g; \\ 0, & x ≤ 0. \end{matrix}

Again, it is easy to see that the structures (ℝ̃, 2^{ℤ}) and (ℝ̃, λ) are interdefinable. In [8] generalizing the results from [2], it is shown that the latter has quantifier elimination up to ℝ̃. For the following, we can assume that ℝ̃ has quantifier elimination. Let T_{disc} be the theory of (ℝ̃, 2^{ℤ}) and let L(λ) be the extension of L by a function symbol for the map λ.

One of the key properties of polynomially-bounded o-minimal structures is the Valuation Inequality. We state here a particular case for theories with field of exponents ℚ. For the general statement, see Corollary 5.6 in [4]. Let M be model of T, and define

fin M := \{x ∈ M : ∃n > 0 \frac{1}{n} ≤ x ≤ n\}.

Since T is polynomially-bounded, fin M is T -convex by Proposition 4.2 in [3]. Let v_{M} : M^{×} → Γ_{M} be the associated valuation: Let Γ_{M} = M/ ≡, where x ≡ y if and only if \frac{x}{y} ∈ fin M and v_{M}(x) := x/ ≡. Note that Γ_{M} is a ℚ-linear space on which scalar multiplication is given by q·v(x) := v(x^{q}).

Let N be a model of T with N ⪯ M. It is easy to see that fin M∩N = fin N. Hence Γ_{N} can be embedded into Γ_{M}. We will write dim_{ℚ}(Γ_{M}/Γ_{N}) for the ℚ-linear dimension of the quotient space of Γ_{M} and Γ_{N}.

Fact 2 (Valuation inequality-[4]). Let M, N be models of T with N ⪯ M. Then

dim(M/N) ≥ dim_{ℚ}(Γ_{M}/Γ_{N}).

In the following, we establish several easy corollaries of the Valuation inequality.

Corollary 3.3. Let M, N be models of T with N ⪯ M and let x_{1}, …, x_{n} ∈ M. Then there are y_{1}, …, y_{n} ∈ N ⟨x_{1}, …, x_{n}⟩ such that for every z ∈ N ⟨x_{1}, …, x_{n}⟩, there are q_{1}, …, q_{n} ∈ ℚ and there is c ∈ N with

\frac{z}{c · y_{1}^{q_{1}} … y_{n}^{q_{n}}} ∈ fin N ⟨x_{1}, …, x_{n}⟩.

Corollary 3.4. Let (N , H) ⪯ (M, G) ⊧ T_{disc}. Let x_{1}, …, x_{n} ∈ M. Then there are g_{1}, …, g_{n} ∈ G such that for every z ∈ N ⟨x_{1}, …, x_{n}⟩, there are q_{1}, …, q_{n} ∈ ℚ and there is g ∈ N ∩ G with

λ(z) = g · g_{1}^{q_{1}} … g_{n}^{q_{n}}.

We fix the following notation: Let G be a torsion-free abelian group (written multiplicatively) and let n > 0. Then G^{[n]} := {g^{n} : g ∈ G}. For a pure subgroup H of G and g_{1}, …, g_{n} ∈ G^{n}, we define H_{G}⟨g_{1}, …, g_{n}⟩ to be the smallest pure subgroup

\{(h · g_{1}^{k_{1}} ⋯ g_{n}^{k_{n}})^{\frac{1}{m}} | h ∈ H, k_{1}, …, k_{n} ∈ ℤ, m > 0, h · g_{1}^{k_{1}} ⋯ g_{n}^{k_{n}} ∈ G^{[m]}\}

of G containing H and g_{1}, …, g_{n}.

Corollary 3.5. Let (N , H) ⪯ (M, G) ⊧ T_{disc}, and let g_{1}, …, g_{n} ∈ G \ H. Then

(N ⟨g_{1}, …, g_{n}⟩, H_{G}⟨g_{1}, …, g_{n}⟩) ⪯ (M, G).

Theorem 3.6. T_{disc} is dependent.

Proof. Again, we need just to check that T_{disc} satisfies the assumption of Theorem 3.1. Quantifier elimination is shown in the proof of Theorem 3.4.2 in [8]. Assumption (ii) follows directly from Corollary 3.4. It is only left to show (iii). Therefore let 𝕄 = (M, G) be a monster model of T_{disc} and take an indiscernible sequence (a_{i})_{i∈ω} from 𝕄^{n} such that there is a positive j ≤ n with a_{i,1}, …, a_{i,j} ∈ λ(𝕄). Further let b_{1} ∈ 𝕄^{k} and b_{2} ∈ λ(𝕄)^{l}. For a contradiction, suppose that there are functions f : 𝕄^{n+k} → 𝕄 and g : 𝕄^{j+l} → 𝕄 that are ∅-definable in the L-reduct of 𝕄 such that

J := {i ∈ ω : 𝕄 ⊧ λ(f(a_{i,1}, …, a_{i,n}, b_{1})) = g(a_{i,j}, …, a_{i,n}, b_{2})}

is neither finite nor cofinite. We assume that there is a subsequence (a_{i})_{i∈I} which is indiscernible over b_{1}, b_{2} and I ⊆ J (this is not a trivial thing, but I’ll sweep it under the rug anyway). Hence for every i ∈ I we have g(a_{i,1}, … a_{i,j}, b_{2}) ∈ G. By Corollary 3.5, for every i ∈ I there are q_{1}, …, q_{j} ∈ ℚ such that

g(a_{i,1}, …, a_{i,j}, b_{2}) = a_{i,1}^{q_{1}} … a_{i,j}^{q_{j}} · bk⃗ ; 2,

where k⃗ ∈ ℤ^{l} and bk⃗ ; 2 is short for b_{2,1}^{k_{1}} ⋯ b_{2,l}^{k_{l}}. Since T is o-minimal and hence dependent, this equation holds for cofinitely many i ∈ ω. Now we need to show that for cofinitely many i ∈ ω a_{i,1}^{q_{1}} … a_{i,j}^{q_{j}} · bk⃗ ; 2 ∈ G. Therefore let m ∈ ω such that q_{1} · m, …, q_{j} · m ∈ ℤ and m · k⃗ ∈ ℤ^{l}. So we need to show that for cofinitely many i ∈ ω, we have

(3.3)  a_{i,1}^{m·q_{1}} … a_{i,j}^{m·q_{j}} ∈ b_{2}^{m·k⃗} · G^{[m]}.

G^{[m]} has only finitely many cosets in G, since |2^{ℤ} : (2^{ℤ})^{[m]})| = m. Further 1, 2, …, 2^{m−1} are representatives of this cosets. Let l ∈ {0, …, m − 1} be such that bp⃗ ; 2 is in 2^{l} · G^{[m]}. Then for every i ∈ ω, we have that (3.3) holds iff

(3.4)  a_{i,1}^{q_{1}} … a_{i,j}^{q_{j}} ∈ 2^{l} · G^{[m]}.

Since (3.3) holds for i ∈ J and (a_{i})_{i∈ω} is an indiscernible sequence, the condition (3.4) holds for all i ∈ ω. Hence for cofinitely many i ∈ ω, we have that g(a_{i,1}, … a_{i,j}, b_{2}) ∈ G. By definition of λ, we further get that the assertion that

𝕄 ⊧ λ(f(a_{i}, b_{1})) = g(a_{i,1}, … a_{i,j}, b_{2})

is equivalent to

𝕄 ⊧ 1 ≤ \frac{f(a_{i}, b_{1})}{g(a_{i,1}, … a_{i,j}, b_{2})} < 2.

Since T is dependent, the right hand side must hold for cofinitely many i ∈ ω. This a contradiction to J not being cofinite. So we have shown that assumption (iii) of Theorem 3.1 holds for T_{disc}. □

References

[1] A. Berenstein, C. Ealy, A. Günaydın, Thorn independence in the field of real numbers with a small multiplicative group, Annals of Pure and Applied Logic 150 (2007) 1-18.

[2] L. van den Dries, The field of reals with a predicate for the powers of two, Manuscripta Math. 54 (1985) 187-195.

[3] L. van den Dries, A. Lewenberg, T-convexity and tame extensions, J. Symbolic Logic (1) 60 (1995) 74-102.

[4] L. van den Dries, T-convexity and tame extensions II, J. Symbolic Logic (1) 62 (1997) 74-102.

[5] L. van den Dries, Dense pairs of o-minimal structures, Fundamenta Mathematica, 157 (1998) 61-78.

[6] L. van den Dries, A. Günaydın, The fields of real and complex numbers with a small multiplicative group, Proc. London Math. Soc. (3) 93 (2006) 43-81.

[7] P. Hieronymi, The real field with an Irrational Power Function and a Dense Multiplicative Subgroup, Preprint, arXiv:0912.2469 (2009).

[8] C. Miller, Tameness in expansions of the real field, in Logic Colloquium 2001 (Vienna), Lect. Notes Log. 20, Assoc. Symbol. Logic, (2005) 281–