Ramsey’s theorem in stable structures

Doug Ensley Department of Math and Computer Science Shippensburg University Shippensburg, PA 17257 Rami Grossberg Department of Mathematical Sciences Carnegie Mellon University Pittsburgh, PA 15213

May 15, 1997

Abstract

We prove some results on the border of Ramsey theory (finite partition calculus) and model theory. In particular, we demonstrate bounds on the size of finite sets that assure the existence therein of sequences indiscernible with respect to a formula and how those bounds are improved by stability assumptions.

1 Introduction

In his fundamental paper Frank Ramsey was interested in “a problem of formal logic.” (See [9] and pages 18-27 of [4].) He proved the result now known as “(finite) Ramsey’s theorem” which essentially states

For all k, r < ω, there is an n < ω such that however the r – subsets of {1, 2, …, n} are 2 – colored, there will exist a k – element subset of {1, 2, …, n} which has all its r – subsets the same color.

(We will let n(k, r) denote the smallest such n.) Ramsey proved this theorem in order to construct a finite model for a given finite universal theory so that the universe of the model is canonical with respect to the relations in the language. (For model theorists “canonical” means Δ – indiscernible as in Definition 2.1).

Much is known about the order of magnitude of the function n(k, r) and some of its generalizations (see [3], for example). An upper bound on n(k, r) is an (r − 1) – times iterated exponential of a polynomial in k. Many feel that the upper bound is tight. However especially for r ≥ 3 the gap between the best known lower and upper bounds is huge.

In 1956 A. Ehrenfeucht and A. Mostowski [2] rediscovered the usefulness of Ramsey’s theorem in logic and introduced the notion we now call indiscernibility. Several people continued exploiting the connections between partition theorems and logic, predominant among them M. Morley (see [7] and [8]) and S. Shelah (see [11] among many others). Morley [8] used indiscernibles to construct models of large cardinality (relative to the cardinality of the reals) — specifically, he proved that the Hanf number of L_{ω_{1},ω} is ℶ_{ω_{1}}.

The major goal of this paper is to study Ramsey numbers for definable colorings inside models of a stable theory. This can be viewed as a direct extension of Ramsey’s work, namely by taking into account the first order properties of a structure. One example is the field of complex numbers ⟨C, +, ·⟩. It is well known that its first order theory has many nice properties — it is ℵ_{1} – categorical and thus is ℵ_{0} – stable and has neither the order property nor the finite cover property.

We will be most interested in the following general situation:

Given a first order (complete) theory T, and (an infinite) model M ⊧ T. Let k and r be natural numbers, and let F be a coloring of a set of r – tuples from M by 2 colors which is definable by a first order formula in the language L(T) (maybe with parameters from M). Let n =^{def} n_{F} (k, r) be the least natural number such that for every S ⊆ |M| of cardinality n, if F : [S]^{r} → 2 then there exists S^{∗} ⊆ S of cardinality k such that F is constant on [S^{∗}]^{r}.

It turns out that for stable theories (or even for theories just without the independence property) we get better upper bounds than for the general Ramsey numbers. This indicates that one can not improve the lower bounds by looking at stable structures.

Shelah [11] proved that instability is equivalent to the presence of either the strict order property or the independence property. In a combinatorial setting, stability of a formula ϕ implies that there is a natural number k so that for arbitrarily large sets A, the number of ϕ-types over A is at most |A|^{k}. We shall restrict our attention to when the number of ϕ-types over a finite set A is bounded by a polynomial in |A|.

First we establish the degree of the polynomial bound on the number of ϕ-types given to us by the absence of the strict order or independence properties. Once we have these sharper bounds we can find sequences of indiscernibles in the spirit of [11]. It should be noted here that everything we do is “local”, involving just a single formula (or equivalently a finite set of formulas). We then work through the calculations for uniform hypergraphs as a case study. This raises questions about “stable” graphs and hypergraphs which we begin to answer.

Notation: Everything is standard. We will typically treat natural numbers as ordinals (i.e., n = {0, 1, …, n − 1}). Often x, y, and z will denote free variables, or finite sequences of variables — it should be clear from the context whether we are dealing with variables or with sequences of variables. When x is a sequence, we let l(x) denote its length. L will denote a similarity type (a.k.a. language or signature), Δ will stand for a finite set of L formulas. M is an infinite L - structure, |M| is the universe of the structure M, and ∥M∥ the cardinality of the universe of M. Given a fixed structure M, subsets of its universe will be denoted by A, B, C and D. So when we write A ⊆ M we really mean that A ⊆ |M|, while N ⊆ M stands for “N is a submodel of M”. When M is a structure then by a ∈ M we mean a ∈ |M|, and when a is a finite sequence of elements, then a ∈ M stands for “all the elements of the sequence a are elements of |M|”. When we write L(M) we mean L-formulas (i.e., formulas from L) with parameters from M (equivalently, formulas from the language of L with added constants for the elements of M).

Since all of our work will be inside a given structure M all the notions are relative to it. For example for a ∈ M and A ⊆ M we denote by tp_{Δ}(a, A) the type tp_{Δ}(a, A, M) which is {ϕ(x; b) : M ⊧ ϕ[a; b], b ∈ A, ϕ(x; y) ∈ Δ} and if A ⊆ M then S_{Δ}(A, M) =^{def} {tp_{Δ}(a, A) : a ∈ M}. Note that in [11] S_{Δ}(A, M) denotes the set of all complete Δ -types with parameters from A that are consistent with T h(⟨M, c_{a}⟩_{a∈A}). It is usually important that Δ is closed under negation, so when Δ = {ϕ, ¬ϕ}, instead of writing tp_{Δ}(⋯) and S_{Δ}(⋯) we will write tp_{ϕ}(⋯) and S_{ϕ}(⋯), respectively.

2 The effect of the order and independence properties on the number of local types

In this section, we fix some notation and terms and then define the first important concepts. In the following definition, parts (1)−(3) are from [11],

(4) is a generalization of a definition of Shelah, and (5) is from Grossberg and Shelah [6].

Definition 2.1 1. For a set Δ of L – formulas and a natural number n, a \underline{(Δ, n) – type over a set} A is a set of formulas of the form ϕ(x; a) where ϕ(x; y) ∈ Δ and a ∈ A with l(x) = n. If Δ = L, we omit it, and we just say “ϕ – type” for a ({ϕ(x; y), ¬ϕ(x; y)}, l(x)) – type.

2. Given a (Δ, n) – type p over A, define dom(p) = {a ∈ A : for some ϕ ∈ Δ, ϕ(x; a) ∈ p}.

3. A type p \underline{(Δ_{0}, Δ_{1}) – splits over} B ⊆ dom(p) if there is a ϕ(x; y) ∈ Δ_{1} and b, c ∈ dom(p) such that tp_{Δ_{0}}(b, B) = tp_{Δ_{0}}(c, B) and ϕ(x; b), ¬ϕ(x; c) ∈ p. If p is a Δ – type and Δ_{0} = Δ_{1} = Δ, then we just say p \underline{splits over B}.

4. We say that (M, ϕ(x; y)) has \underline{the k - independence property} if there are {a_{i} : i < k} ⊆ M, and {b_{w} : w ⊆ k} ⊆ M, such that M ⊧ ϕ[a_{i}; b_{w}] if and only if i ∈ w.

5. (M, ϕ(x; y)) has \underline{the n – order property} (where l(x) = l(y) = k) if there exists a set of k – tuples {a_{i} : i < n} ⊆ M such that i < j if and only if M ⊧ ϕ[a_{i}, a_{j}] for all i, j < n.

6. We say that (M, ϕ) does not have \underline{the d - cover property} if for every n ≥ d and {b_{i} : i < n} ⊆ M, if

(∀w ⊆ n [|w| < d ⇒ M ⊧ ∃x ⋀_{i∈w} ϕ(x; b_{i})])

then

M ⊧ ∃x ⋀_{i<n} ϕ(x; b_{i}).

Warning: This use of “order property” corresponds to neither the order property nor the strict order property in [11]. The definition comes rather from [5].

Example 2.2 If M = (M, R) is the countable random graph, then (M, R) fails to have the 2 – cover property. If M is the countable universal homogeneous triangle-free graph, then (M, R) fails to have the 3 – cover property.

The following monotonicity property is immediate from the definitions.

Fact 2.3 For sets B ⊆ C ⊆ A and a complete (Δ, n) – type p with Dom(p) ⊆ A, if p does not split over B, then p does not split over C.

Shelah (see [11]) established that for complete first order theory T is unstable if and only if T has a model which has the ω− order property. This along with the compactness theorem gives us the following.

Fact 2.4 Let T be a stable theory, and suppose that M ⊧ T is an infinite model.

1. For every ϕ(x, y) ∈ L(M) there exists a natural number n_{ϕ} such that (M, ϕ) does not have the n_{ϕ} – order property.

2. For every ϕ(x, y) ∈ L(M) there exists a natural number k_{ϕ} such that (M, ϕ) does not have the k_{ϕ} – independence property.

3. If T is categorical in some cardinality greater than |T |, then for every ϕ(x, y) ∈ L(M) there exists a natural number d_{ϕ} such that (M, ϕ) does not have the d_{ϕ} – cover property.

We first establish that the failure of either the independence property or the order property for ϕ implies that there is a polynomial bound on the number of ϕ− types. The more complicated of these to deal with is the failure of the order property. At the same time this is perhaps the more natural property to look for in a given structure. The bounds in this case are given in Theorem 2.9. The failure of the independence property gives us a far better bound (i.e., smaller degree polynomial) with less work. This is hardly surprising since the independence property entails the order property in this sense. Theorem 2.11 reproduces this result of Shelah paying attention to the specific connection between the bound and where the independence property fails.

This first lemma is a finite version of Lemma 5 from [5].

Lemma 2.5 Let ϕ(x; y) be a formula in L, n a positive integer, t = max{l(y), l(x)}, and ψ(y; x) = ϕ(x; y). Suppose that {A_{i} ⊆ M : i ≤ 2n} is an increasing chain of sets such that for every B ⊆ A_{i} with |B| ≤ 3tn, every type in S_{ϕ}(B, M) is realized in A_{i+1}. Then if there is a type p ∈ S_{ϕ}(A_{2n}, M) such that for all i < 2n, p|A_{i+1} (ψ, ϕ) – splits over every subset of A_{i} of size at most 3tn, then (M, ρ) has the n− order property, where

ρ(x_{0}, x_{1}, x_{2}; y_{0}, y_{1}, y_{2}) =^{def} [ϕ(x_{0}; y_{1}) ↔ ϕ(x_{0}; y_{2})]

Proof. Since p is a finite consistent set of formulas over |M|, we may choose d ∈ M realizing p. Define {a_{i}, b_{i}, c_{i} ∈ A_{2i+2} : i < n} by induction on i. Assume for j < n that we have defined these for all i < j. Let B_{j} = ⋃{a_{i}, b_{i}, c_{i} : i < j}. Notice that |B_{j}| ≤ 3tj < 3tn, so by the assumption, p|A_{2j+1} (ψ, ϕ) – splits over B_{j}. That is, there are a_{j}, b_{j} ∈ A_{2j+1} such that

tp_{ψ}(a_{j}, B_{j}, M) = tp_{ψ}(b_{j}, B_{j}, M),

and

M ⊧ ϕ[d; a_{j}] ∧ ¬ϕ[d; b_{j}].

Now choose c_{j} ∈ A_{2j+1} realizing tp_{ϕ}(d, B_{j} ∪ {a_{j}, b_{j}}, M) (which can be done since |B_{j} ∪ {a_{j}, b_{j}}| ≤ 3tj + 2t < 3t(j + 1) ≤ 3tn). This completes the inductive definition.

For each i, let d_{i} = c_{i}a_{i}b_{i}. We will check that the sequence of d_{i} and the formula

ρ(x_{0}, x_{1}, x_{2}; y_{0}, y_{1}, y_{2}) =^{def} [ϕ(x_{0}; y_{1}) ↔ ϕ(x_{0}; y_{2})]

witness the n – order property for M.

If i < j < n, then c_{i} ∈ B_{j}. By the choice of a_{j} and b_{j}, tp_{ψ}(a_{j}, B_{j}, M) = tp_{ψ}(b_{j}, B_{j}, M), so in particular,

M ⊧ ψ[a_{j}; c_{i}] ↔ ψ[b_{j}; c_{i}], or equivalently
M ⊧ ϕ[c_{i}; a_{j}] ↔ ϕ[c_{i}; b_{j}]

That is, M ⊧ ρ[d_{i}; d_{j}].

On the other hand, if j ≤ i < n, then ϕ(x; a_{j}) ∈ tp_{ϕ}(d, B_{i} ∪ {a_{i}, b_{i}}, M) and ϕ(x; b_{j}) ∉ tp_{ϕ}(d, B_{i} ∪ {a_{i}, b_{i}}, M), and so, by the choice of c_{i}, we have that

M ⊧ ϕ[c_{i}; a_{j}] ∧ ¬ϕ[c_{i}; b_{j}].

That is, M ⊧ ¬ρ[d_{i}; d_{j}] in this case. □

In order to see the relationship between this definition of the order property and Shelah’s, we mention Corollary 2.8 below. Note that it is the formula ϕ, not the ρ of Lemma 2.5, which has the weak order property in Corollary 2.8.

Definition 2.6 (M, ϕ) has \underline{the weak m – order property} if there exist \{d_{i} : i < m} ⊆ M such that for each j ≤ m,

M ⊧ ∃x ⋀_{i<m} ϕ(x; d_{i})^{if(i≥j)}

Remarks:

• The notation ϕ(x; d_{i})^{if(i≥j)} is to be interpreted as follows:

ϕ(x; d_{i})^{if(i≥j)} = \{ \begin{matrix}ϕ(x; d_{i}) & if i ≥ j \\ ¬ϕ(x; d_{i}) & otherwise \end{matrix}

• Definition 2.6 is what Shelah [11] calls the m – order property.

Definition 2.7 We write x → (y)_{b}^{a} if for every partition Π of the a - element subsets of {1, …, x} with b parts, there is a y - element subset of {1, …, x} with all of its a – element subsets in the same part of Π.

Corollary 2.8 1. If in addition to the hypotheses of Lemma 2.5 we have that (2n) → (m + 1)_{2}^{2}, then ϕ has the weak m – order property in M.

2. If in addition to the hypotheses of Lemma 2.5 we have that n ≥ \frac{2^{2m−1}}{πm}, then ϕ has the weak m – order property in M.

Proof. (This is essentially [11] I.2.10(2))

1. Let a_{i}, b_{i}, c_{i} for i < n be as in the proof of Lemma 2.5. For each pair i < j ≤ n, define

χ(i, j) := \{ \begin{matrix}1 & if M ⊧ ϕ[c_{i}; a_{j}] \\ 0 & if M ⊧ ¬ϕ[c_{i}; a_{j}] \end{matrix}

Since (2n) → (m+1)_{2}^{2}, we can find a subset I of 2n of cardinality m+1 on which χ is constant which we can enumerate as I = {i_{0} < ⋯ < i_{m}}.

If χ is 1 on I, then (keeping in mind the definition of a_{i}, b_{i}, c_{i} from Lemma 2.5) for every k with 1 ≤ k ≤ m + 1

{ϕ(x; b_{i_{j}})^{if(j≥k)} : 1 ≤ j ≤ m}

is realized by c_{i_{k−1}}. Therefore, the sequence {b_{i_{1}}, …, b_{i_{m}}} witnesses the weak m – order property of ϕ in M.

On the other hand, if χ is 0 on I, then (keeping in mind the definition of a_{i}, b_{i}, c_{i} from Lemma 2.5) for every k with 1 ≤ k ≤ m + 1

{¬ϕ(x; a_{i_{j}})^{if(j≥k)} : 1 ≤ j ≤ m}

is realized by c_{i_{k−1}}. Therefore, the sequence {a_{i_{1}}, …, a_{i_{m}}} witnesses the weak m – order property of ¬ϕ in M. (Of course, it is equivalent for ϕ and ¬ϕ to have the weak m – order property in M.)

2. By Stirling’s formula, n ≥ \frac{2^{2m−1}}{πm} implies that n ≥ \frac{1}{2}( \begin{matrix}2m \\ m \end{matrix} ), and from

[4], n ≥ \frac{1}{2}( \begin{matrix}2m \\ m \end{matrix} ) implies that (2n) → (m + 1)_{2}^{2}.

□

We can now establish the relationship between the number of types and the order property.

Theorem 2.9 If ϕ(x; y) ∈ L(M) is such that

ρ(x_{0}, x_{1}, x_{2}; y_{0}, y_{1}, y_{2}) =^{def} [ϕ(x_{0}; y_{1}) ↔ ϕ(x_{0}; y_{2})]

does not have the n – order property in M, then for every set A ⊆ M with |A| ≥ 2, we have that |S_{ϕ}(A, M)| ≤ 2n|A|^{k}, where k = 2^{(3nt)^{t+1}} and t = max{l(x), l(y)}.

Proof. Suppose that there is some A ⊆ M with |A| ≥ 2 so that |S_{ϕ}(A, M)| > (2n)|A|^{k}. Let ψ(y; x) = ϕ(x; y), m = |A|, and let {a_{i} : i ≤ (2n)m^{k}} ⊆ M be witnesses to the fact that |S_{ϕ}(A, M)| > (2n)m^{k}. (That is, each of these tuples realizes a different ϕ – type over A.) Define {A_{i} : i < 2n}, satisfying

1. A_{0} = A

2. A ⊆ A_{i} ⊆ A_{i+1} ⊆ M,

3. |A_{i}| ≤ c^{e_{i}}m^{(3nt)^{i}},where c := 2^{2+(3nt)^{t}} and e_{i} := \frac{(3nt)^{i+1}−1}{3nt−1}, and

4. for every B ⊆ A_{i} with |B| ≤ 3tn, every p ∈ S_{ϕ}(B, M) ⋃ S_{ψ}(B, M) is realized in A_{i+1}.

To see that this can be done, we need only check the cardinality constraints. Notice that condition (3) is met for i = 0 since |A| = m. Now since there are at most |A_{i}|^{3tn} subsets of A_{i} with cardinality at most 3tn, and over each such subset B, there are at most 2^{(3tn)^{t}} types in each of S_{ψ}(B, M) and S_{ϕ}(B, M), then there are at most 2^{1+(3tn)^{t}} types in S_{ψ}(B, M) ⋃ S_{ϕ}(B, M) for each such B. Therefore, A_{i+1} can be defined so that

|A_{i+1}| ≤ |A_{i}| + (2^{1+(3tn)^{t}})|A_{i}|^{3tn}
≤ (2^{2+(3tn)^{t}})|A_{i}|^{3tn}
= c|A_{i}|^{3tn}
≤ c(c^{e_{i}}m^{(3nt)^{i}})^{3tn}
= c^{1+e_{i}(3tn)}m^{(3tn)^{i+1}}
= c^{e_{i+1}}m^{(3tn)^{i+1}}

Claim 1 There is a j < (2n)m^{k} such that for every i < 2n and every B ⊆ A_{i} with |B| ≤ 3tn, tp(a_{j}, A_{i+1}) (ψ, ϕ) – splits over B.

Proof. (Of Claim 1) Suppose not. That is, for every j ≤ (2n)m^{k}, there is an i_{j} < 2n and a B ⊆ A_{i_{j}} with |B| ≤ 3tn, so that tp(a_{j}, A_{i_{j}+1}) does not (ψ, ϕ) – split over B. Since i is a function from the ordinal 1 + (2n)m^{k} to the ordinal 2n, there must be a subset S of 1 + (2n)m^{k} with |S| > m^{k}, and an integer i^{∗} < 2n such that for all j ∈ S, i_{j} = i^{∗}. Now similarly, there are less than |A_{i^{∗}}|^{3tn} subsets of A_{i^{∗}}, with cardinality at most 3tn, so there is a T ⊆ S with

|T | > \frac{m^{k}}{|A_{i^{∗}}|^{3tn}}

and a B_{0} ⊆ A_{i^{∗}}, with |B_{0}| ≤ 3tn such that for all j ∈ T, tp(a_{j}, A_{i^{∗}+1}) does not (ψ, ϕ) – split over B_{0}. Since |A_{i^{∗}}| ≤ c^{e_{i^{∗}}} m^{(3nt)^{i^{∗}}} ≤ (cm)^{(3tn)^{2n}}, then

|T | ≥ \frac{m^{k}}{(cm)^{(3tn)^{2n}}}  (1)

Let C ⊆ A_{i^{∗}+1} be obtained by adding to B_{0}, realizations of every type in S_{ϕ}(B_{0}, M) ⋃ S_{ψ}(B_{0}, M). This can clearly be done so that |C| ≤ 3nt + 2^{(3nt)^{r}} + 2^{(3nt)^{s}}. The maximum number of ϕ – types over C is at most 2^{|C|^{t}} ≤ 2^{c^{t}}.

Claim 2 m^{k−(3nt)^{2n}} > (2^{c^{t}})(c^{(3nt)^{2n}})

Proof. (Of Claim 2) Since c = 2^{2+(3nt)^{t}}, we have c^{t} + (3nt)^{2n}(2 + (3nt)^{t}) as the exponent on the right-hand side above. Since m ≥ 2, it is enough to show that

k > (c^{t} + (3nt)^{2n}(2 + (3nt)^{t}) + (3nt)^{2n}
= 2^{t(2+(3nt)^{t})} + (3nt)^{2n}(3 + (3nt)^{t})

This follows from the definition of k (recall that k = 2^{(3nt)^{t+1}}), so we have established Claim 2. □_{2}

Now by (1) and Claim2, |T | is greater than the number of ϕ – types over C, so there must be i ≠ j ∈ T such that tp_{ϕ}(a_{i}, C) = tp_{ϕ}(a_{j}, C). Since tp_{ϕ}(a_{i}, A) ≠ tp_{ϕ}(a_{j}, A) (by the original choice of a_{i}’s), we may choose a ∈ A so that M ⊧ ϕ[a_{i}, a] ∧ ¬ϕ[a_{j}, a]. Now choose a′ ∈ C so that tp_{ψ}(a, B_{0}) = tp_{ψ}(a′, B_{0}) (this is how C is defined after all). Since tp_{ϕ}(a_{i}, A_{i^{∗}+1}) and tp_{ϕ}(a_{j}, A_{i^{∗}+1}) each do not (ψ, ϕ) – split over B_{0}, we have that

ϕ(x; a) ∈ tp_{ϕ}(a_{i}, A_{i^{∗}+1}) if and only if ϕ(x; a′) ∈ tp_{ϕ}(a_{i}, A_{i^{∗}+1})

so M ⊧ ϕ[a_{i}, a′]∧¬ϕ[a_{j}, a′], contradicting the fact that tp_{ϕ}(a_{i}, C) = tp_{ϕ}(a_{j}, C) and thus completing the proof of Claim 1. □_{1}

Now letting j be as in Claim 1 and applying Lemma 2.5 completes the

proof of Theorem 2.9.  □_{2.9}  □

Theorem 2.11 below gives a better result under under stronger assumptions. The next lemma is II, 4.10, (4) in [11]. It comes from a question due to Erdős about the so-called “trace” of a set system which was answered by Shelah and Perles [10] in 1972. Proofs in the language of combinatorics can also be found in most books on extremal set systems (e.g., Bollobas [1]).

Lemma 2.10 If S is any family of subsets of the finite set I with

|S| > ∑_{i<k} ( \begin{matrix}|I| \\ i \end{matrix} )

then there exist α_{i} ∈ I for i < k such that for every w ⊆ k there is an A_{w} ∈ S so that i ∈ w ⇔ α_{i} ∈ A_{w}. (The conclusion here is equivalent to trace(I) ≥ k in the language of [1].)

Theorem 2.11 If ϕ(x; y) ∈ L(M) (r = l(x), s = l(y)) does not have the k− independence property in M, then for every finite set A ⊆ M, if |A| ≥ 2, then |S_{ϕ}(A, M)| ≤ |A|^{s(k−1)}.

Proof. (Essentially [11], II.4.10(4)) Let F be the set of ϕ – formulas over A. Then

|F | < |A|^{s}.

So if |S_{ϕ}(A, M)| > |A|^{s(k−1)}, then certainly

|S_{ϕ}(A, M)| > ∑_{i<k} ( \begin{matrix}|F | \\ i \end{matrix} ) ,

in which case Lemma 2.10 can be applied to F and S_{ϕ}(A, M) to get witnesses to the k – independence property in M, a contradiction. □

The “moral” of Theorem 2.9 and Theorem 2.11 is that when ϕ has some nice properties, there is a bound on the number of ϕ – types over A which is polynomial in |A|. Note that the difference between the two properties is that the degree of the polynomial in the absence of the k – independence property is linear in k while in the absence of the n – order property the degree is exponential in n. Also the bounds on ϕ – types in the latter case hold when a formula ρ related to ϕ (as opposed to ϕ itself) is without the n – order property.

3 Indiscernible sequences in large finite sets

Note: The next definition is a version of Shelah’s [11], I.2.3, and Ramsey’s notion of canonical sequence.

Definition 3.1 1. A sequence I = ⟨a_{i} : i < n⟩ ⊆ M is called a (Δ, m) – \underline{indiscernible sequence over} A ⊆ M (where Δ is a set of L(M) – formulas) if for every i_{0} < … < i_{m−1} ∈ I, j_{0} < … < j_{m−1} ∈ I we have that tp_{Δ}(a_{i_{0}} ⋯ a_{i_{m−1}}, A, M) = tp_{Δ}(a_{j_{0}} ⋯ a_{j_{m−1}}, A, M)

2. A set I = \{a_{i} : i < n\} ⊆ M is called a (Δ, m) – \underline{indiscernible set over} A ⊆ M if and only if for every {i_{0}, …, i_{m−1}}, {j_{0}, …, j_{m−1}} ⊆ I we have

tp_{Δ}(a_{i_{0}} ⋯ a_{i_{m−1}}, A, M) = tp_{Δ}(a_{j_{0}} ⋯ a_{j_{m−1}}, A, M).

3. If Δ = {ϕ}, then we will just write (ϕ, m)− indiscernible ...

4. For a formula ϕ(x_{0}x_{1} … x_{m−1}; b) and each i with 1 ≤ i ≤ m we define the formula ϕ_{i} = ϕ(x_{0}x_{1} … x_{i−1}; x_{i} … x_{m−1}b) (so ϕ_{m} = ϕ) , and we define the set

Δ_{ϕ} = {ϕ_{i} : 1 ≤ i ≤ m}

Note that if ϕ(x; b) ∈ tp_{Δ}(a_{0} … a_{m−1}, B, M), then necessarily l(x) = m · l(a_{0}).

Example 3.2 1. In the model M_{n}^{m} = ⟨m, 0, 1, χ⟩ (n ≤ m < ω) where χ is function from the increasing n – tuples of m to {0, 1}, any increasing enumeration of a monochromatic set is an example of a (Δ, 1) – indiscernible sequence over ∅ where Δ = {χ(x) = 0, χ(x) = 1}.

2. In a graph (G, R), cliques and independent sets are examples of (R, 2) – indiscernible sets over ∅.

Recall that in a stable first order theory, every sequence of indiscernibles is a set of indiscernibles. In our finite setting this is also true if the formula fails to have the n – order property. The argument below follows closely that of Shelah [11].

Theorem 3.3 Assume that M does not have the n – order property. If I = ⟨a_{i} : i < n + m − 1⟩ ⊆ M is a sequence of (ϕ, m) – indiscernibles over B ⊆ M, then {a_{i} : i < n + m − 1} a set of (ϕ, m) – indiscernibles over B.

Proof. Since any permutation of {1, …, n} is a product of transpositions (k, k+1), and since I is a (ϕ, m)− indiscernible sequence over B, it is enough to show that for each b ∈ B and k < m,

M ⊧ ϕ[a_{0} ⋯ a_{k−1}a_{k+1}a_{k} ⋯ a_{m−1}; b] ↔ ϕ[a_{0} ⋯ a_{k−1}a_{k}a_{k+1} ⋯ a_{m−1}; b].

Suppose this is not the case. Then we may choose b ∈ B and k < m so that

M ⊧ ¬ϕ[a_{0} ⋯ a_{k−1}a_{k+1}a_{k} ⋯ a_{m−1}; b] ∧ ϕ[a_{0} ⋯ a_{k−1}a_{k}a_{k+1} ⋯ a_{m−1}; b].

Let c = a_{0} ⋯ a_{k−1} and d = a_{n+k+1} ⋯ a_{n+m−2} (making l(c) = k and l(d) = m − k − 2). By the indiscernibility of I,

M ⊧ ¬ϕ[ca_{k+1}a_{k}d; b] ∧ ϕ[ca_{k}a_{k+1}d; b].

For each i and j with k ≤ i < j < n+k, we have (again by the indiscernibility of the sequence I) that

M ⊧ ¬ϕ[ca_{j}a_{i}d; b] ∧ ϕ[ca_{i}a_{j}d; b].

Thus the formula ψ(x, y; cdb) =^{def} ϕ(c, x, y, d; b) defines an order on ⟨a_{i} : k ≤ i < n + k⟩ in M, a contradiction. □

The following definition is a generalization of the notion of end-homogenous set in combinatorics (see section 15 of [3]) to the context of Δ – indiscernible sequences.

Definition 3.4 A sequence I = ⟨a_{i} : i < n⟩ ⊆ M is called a (Δ, m)

– \underline{end-indiscernible sequence over} A ⊆ M (where Δ is a set of L(M) – formulas) if for every {i_{0}, …, i_{m−2}} ⊆ n and j_{0}, j_{1} < n both larger than max{i_{0}, …, i_{m−2}}, we have

tp_{Δ}(a_{i_{0}} ⋯ a_{i_{m−2}}a_{j_{0}}, A, M) = tp_{Δ}(a_{i_{0}} ⋯ a_{i_{m−2}}a_{j_{1}}, A, M)

Definition 3.5 For the following lemma, let F : ω → ω be given, and fix the parameters α, r, m and k. We define the function F_{α,r,k,m}^{∗} (which we write simply as F^{∗} when the parameters are understood) as follows:

• F^{∗}(0) = 1,

• F^{∗}(j + 1) = 1 + F^{∗}(j) · F (α + m · r · (j + 1)) for j < k − 2 − m, and

• F^{∗}(j + 1) = 1 + F^{∗}(j) for k − 2 − m ≤ j < k − 2.

We will not need j ≥ k − 2.

Lemma 3.6 If for every B ⊆ M, |S_{ϕ}(B, M)| < F (|B|), and I = {c_{i} : i ≤ F_{α,r,k,m}^{∗}(k − 2)} ⊆ M (where l(c_{i}) = l(x_{i}) = r, α = |A|), then there is a J ⊆ I such that |J| ≥ k and J is a (ϕ, m) – end-indiscernible sequence over A.

Proof. (For notational convenience when we have a subset S ⊆ I, we will write min S instead of the clumsier c_{min{i : c_{i}∈S}}.) We first construct A_{j} = {a_{i} : i ≤ j} ⊆ I and S_{j} ⊆ I by induction on j < k − 1 so that

1. S_{0} = I

2. a_{j} = min S_{j},

3. S_{j+1} ⊆ S_{j},

4. |S_{j}| > F^{∗}(k − 2 − j), and

5. whenever {i_{0}, …, i_{m−1}} ⊆ j and b ∈ S_{j},

tp_{ϕ}(a_{i_{0}} ⋯ a_{i_{m−2}}a_{j}, A, M) = tp_{ϕ}(a_{i_{0}} ⋯ a_{i_{m−2}}b, A, M).

The construction is completed by taking an arbitrary a_{k−1} ∈ S_{k−2} − {a_{k−2}}. (which is possible by (4) since F^{∗}(0) = 1), and letting J = ⟨a_{i} : i < k⟩. We claim that J will be the desired (ϕ, m) – end-indiscernible sequence over A.

To see this, let {i_{0}, …, i_{m−2}, j_{0}, j_{1}} ⊆ k with max{i_{0}, …, i_{m−2}} < j_{0} < j_{1} < k be given. Certainly then {i_{0}, …, i_{m−2}} ⊆ j_{0} and a_{j_{1}} ∈ S_{j_{0}}, so by (5) we have that

tp_{ϕ}(a_{i_{0}} ⋯ a_{i_{m−2}}a_{j_{0}}, A, M) = tp_{ϕ}(a_{i_{0}} ⋯ a_{i_{m−2}}a_{j_{1}}, A, M).

To carry out the construction, first for j ≤ m − 1 set a_{j} = c_{j} and S_{j} = {c_{i} : j ≤ i ≤ F^{∗}(k − 2)}. Clearly we have satisfied all conditions in this. Now assume for some j ≥ m that A_{j−1} and S_{j−1} have been defined satisfying the conditions.

Define the equivalence relation ∼ on S_{j−1} − {a_{j−1}} by c ∼ d if and only if for all {i_{0}, …, i_{r−1}},

tp_{ϕ}(a_{i_{1}} ⋯ a_{i_{m−1}}c, A, M) = tp_{ϕ}(a_{i_{1}} ⋯ a_{i_{m−1}}d, A, M)

Let ψ(w; z) = ϕ(x_{1}, …, x_{m−1}, w; y) (so z = x_{1} ⋯ x_{m−1}y). The number of ∼ − classes then is at most |S_{ψ}(A∪A_{j})| ≤ |S_{ϕ}(A∪A_{j})| < F (α+m·r·(j+1)). Therefore, at least one class S_{j} has cardinality at least \frac{|S_{j−1}|−1}{F (α+m·r·(j+1))}. Let

a_{j} = min S_{j}. By definition of F^{∗}, \frac{F^{∗}(k−2−j+1)}{F (α+m·r·(j+1))} > F^{∗}(k − 2 − j), so we have that |S_{j}| > F^{∗}(k − 2 − j). It is easy to see that condition (5) is satisfied. □

For the following lemma, we once again need a function defined in terms of the parameters of the problem. For fixed parameters α, r and k, let f_{i} = F_{α,r,k,i}^{∗} from Lemma 3.6 (so f_{i} is effectively the F^{∗} for the formula ϕ_{i}), and define

g_{i} := \{ \begin{matrix}id & if i = 0 \\ f_{i} ∘ (g_{i−1} − 2) & otherwise \end{matrix}

Lemma 3.7 Let α = |A| and r = l(a_{0}). If J = {a_{i} : i ≤ g_{m−1}(k−1)} ⊆ M is a (Δ_{ϕ}, m)− end-indiscernible sequence over A ⊆ M, then there is a J′ ⊆ J with |J′| ≥ k and J′ is a (ϕ, m)− indiscernible sequence over A.

Proof. We prove by induction on i ≤ m that there is such a J′ which is a (ϕ_{i}, i)− end-indiscernible sequence over A. Since ϕ_{m} = ϕ, the result will follow. Note first that if i = 1, there is nothing to do since (ϕ_{1}, 1)− end-indiscernible is the same as (ϕ_{1}, 1)− indiscernible. Now let i ≥ 1 be given, and assume that every long (Δ_{ϕ}, m)− end-indiscernible sequence over A ⊆ M has a subsequence of length k which is a (ϕ_{i}, i)− indiscernible sequence over A.

Let a sequence J of (Δ_{ϕ}, m)− end-indiscernible sequences over A of length at least g_{i}(k − 1) = f_{i}(g_{i−1}(k − 1) − 2). Let c be the last element in J. It follows that

M ⊧ ϕ_{i}[a_{0}, …, a_{i−1}; cb] if and only if M ⊧ ϕ_{i+1}[a_{0} ⋯ a_{i−1}c; b] (2)

for all a_{0}, …, a_{m−1} ∈ J, b ∈ M. (Note that for all i, |S_{ϕ_{i}}(B, M) ≤ |S_{ϕ}(B, M)| for all B ⊆ M, so we can use the same F for ϕ_{i} as for ϕ. This result could be improved by using a sharper bound on the number of ϕ_{i}− types.) By Lemma 3.6, there must be a subset J′′ of J with cardinality at least g_{i−1}(k − 1) which is ϕ_{i}− end-indiscernible over A. By the inductive hypothesis, there is a subsequence of J′′ with cardinality at least k − 1 which is (ϕ_{i}, i)− indiscernible over A. Form J′ by adding c to the end of this sequence. It follows from (2), the (Δ_{ϕ}, m)− end-indiscernibility of J, and the (ϕ_{i}, i)− indiscernibility of J′′ that J′ is (ϕ_{i+1}, i + 1)− indiscernible over A. □

Theorem 3.8 For any A ⊆ M and any sequence I from M with |I| ≥ g_{m}(k − 1), there is a subsequence J of I with cardinality at least k which is (ϕ, m) – indiscernible over A.

Proof. By Lemmas 3.6 and 3.7. □

Our goal now is to apply this to theories with different properties to see how the properties affect the size of a sequence one must look in to be assured of finding an indiscernible sequence. First we will do a basic comparison between the cases when we do and do not have a polynomial bound on the number of types over a set. In each of these cases, we will give the bound to find a sequence indiscernible over ∅. We will use the notation log^{(i)} for

\underbrace{log_{2} ∘ log_{2} ∘ ⋯ ∘ log_{2}}
i times

Corollary 3.9 1. If F (i) = 2^{i^{m}} (which is the worst possible case), then log^{(m)} g_{m}(k − 1) ≤ 4k.

2. If F (i) = i^{p}, then log^{(m)} g_{m}(k − 1) ≤ 2mk + log_{2} k + log_{2} p.

We now combine part (2) above with the results from the previous section to see what happens in the specific cases of structures without the n – order property and structures without the n – independence property. We define by induction on i the function

ℶ(i, x) = \{ \begin{matrix}x & if i = 0 \\ 2^{ℶ(i−1,x)} & if i > 0 \end{matrix}

Recall that for the formula ϕ(x; y) we have defined the parameters r = l(x), s = l(y), and t = max{r, s}.

Corollary 3.9 3. If (M, ϕ) fails to have the n – independence property and I = {a_{i} : i < ℶ(m, 2k+log_{2} k+log_{2} n+log_{2} m)} ⊆ M, then there is a J ⊆ I so that |J| ≥ k and J is a (ϕ, m) – indiscernible sequence over ∅.

4. If (M, ρ) fails to have the n – order property and I = {a_{i} : i < ℶ(m, 2k + log_{2} k + (3nt)^{t+1})} ⊆ M, then there is a J ⊆ I so that |J| ≥ k and J is a (ϕ, m) – indiscernible sequence over ∅. (Recall that ρ(x_{0}, x_{1}, x_{2}; y_{0}, y_{1}, y_{2}) = [ϕ(x_{0}; y_{1}) ↔ ϕ(x_{0}; y_{2})].)

Finally, note that with the additional assumption of failure of the d – cover property, if d is smaller than n, then from the assumptions in (3) and (4) above, we could infer a failure of the d – independence property or the d – order property improving the bounds even further.

4 Ramsey’s theorem for finite hypergraphs

In this section we look to graph theory to illustrate an applications. We can improve (for the case of hypergraphs without the n – independence property) the best known upper bounds for the Ramsey number n_{r}(a, b). This indicates that if examples are to be sought of hypergraphs with only small cliques and independent sets (the existence of which improves the lower bounds for Ramsey’s Theorem), then one should look to graphs which have the n – independence property for n as large as possible. First however we should say what all of this means.

Definition 4.1 1. An r – graph is a set of vertices V along with a set of r – element subsets of V called edges. The edge set will be identified in the language by the r – ary predicate R.

2. A complete r – graph is one in which all r – element subsets of the vertices are edges. An empty r – graph is one in which none of the r – element subsets of the vertices are edges.

3. n_{r}(a, b) denotes the smallest positive integer N so that in any r – hypergraph on N vertices there will be an induced subgraph which is either a complete r – graph on a vertices or an empty r – graph on b vertices.

4. We say that an r – graph G has the n – independence property if (G, R(x)) does (where l(x) = r).

Remark. We will assume that G is a countable graph although all results are on large finite sets in G so they could be applied to an appropriately constructed large finite graph.

Note that Lemma 3.6 can be improved in this situation since the edge relation is symmetric. With this in mind, we can make the following computations.

Lemma 4.2 1. In an r – graph G, F is given by F (i) = 2^{q} where q =

( \begin{matrix}i \\ r − 1 \end{matrix} ). Consequently, F^{∗}(k) ≤ 2^{k^{r}} in this case.

2. In an r – graph G which does not have the n – independence property, F is defined by

F (i) := \{ \begin{matrix}1 & for i < r \\ i^{(r−1)(n−1)} & otherwise \end{matrix}

Consequently F^{∗}(k) ≤ k^{(r−1)(n−1)k} in this case.

We should now see how this improvement shows up at the end of the process. To do this we first need to adapt the g_{m} function from Lemma 3.7 to this specific task. For a fixed natural number p, define the functions E_{p}^{(j)} by

• E^{(1)} = E = (α ↦ (α + 1)^{p(α+1)}), and

• E^{(i+1)} = E ∘ E^{(i)} for i ≥ 1.

Theorem 4.3 Let n ≥ 2 and k ≥ 3 be given, and let p = (r − 1)(n − 1). If an r – graph G on at least E_{p}^{(r−1)}(k − 1) vertices does not have the n – independence property, then G has an induced subgraph on k vertices which is either complete or empty.

Proof. This is simply Theorem 3.8 specifically taking into account the function F for r− hypergraphs without the n− independence property as well as the symmetry of the edge relation. □

Remark: Another way to say this is that in the class of r – graphs without the independence property n_{r}(k, k) ≤ E_{p}^{(r−1)}(k − 1).

Comparing upper bounds for r = 3

Note that for r = 3 in Theorem 4.3, we have p = 2(n − 1), and so we get E_{p}^{(2)}(k −1) = (2^{2k} +1)^{p(2^{2k}+1)} which is roughly 2^{nk(2^{2k}+2)}. The upper bound for R_{3}(k, k) in [3] is roughly 2^{2^{4k}}. So log_{2} log_{2}(their bound) = 4k and

log_{2} log_{2}(our bound) = log_{2} p + log_{2} k + (2k + 2)

which is smaller than 4k as long as 2k − 2 − log_{2} k > log_{2} n, which is true as long as n < 2^{2k−2}/k.

For example, for k = 10 our bound is about 2^{c(n−1)} where c is roughly 4 × 10^{7} and theirs is about 2^{2^{40}}. Since 2^{40} is roughly 10^{12}, this shows some improvement in the exponent for 3− hypergraphs without the n – independence property.

Comparing upper bounds in general

Let a_{r} be the upper bound for R_{r}(k, k) given in [3] and b_{r} be the upper bound as computed for the class of r – graphs without the n – independence property in Theorem 4.3 (both as a function of k, the size of the desired indiscernible set). Since we have b_{r+1} ≤ b_{r}^{(p)(b_{r})}, we get the relationship

log^{(r)} b_{r+1} ≤ log^{(r−1)}[p b_{r}(log b_{r})]
= log^{(r−2)}(log(r − 1) + log(n − 1) + log b_{r} + log log b_{r})

for r ≥ 3, log log b_{3} = 2k + log_{2} k + log_{2} n + log_{2} r, and log b_{2} = 2k. It follows that log^{(r)} b_{r+1} is less than (roughly) 2k + log_{2} k + log_{2} n for every r.

In [3], the bounds a_{r} satisfy log a_{2} = 2k, log log a_{3} = 4k, and for r ≥ 3,

log^{(r)} a_{r+1} = log^{(r−1)}(a_{r}^{r}) =
log^{(r−2)}(r log a_{r}) = log^{(r−3)}[log r + log log a_{r}].

We can then show that log^{(r−1)} a_{r} < 4k + 2 for all r.

Clearly for each r ≥ 3, \frac{b_{r}}{a_{r}} → 0 as m gets large.

Remark: On a final note, the above comparison is only given for r – graphs with r ≥ 3 because the technique enlisted does not give an improvement in the case of graphs. This has not been pursued in this paper because it seems to be of no interest in the general study. However, the techniques may be of interest to the specialist in graph theory.

References

[1] Bela Bollobás, Combinatorics: Set Systems, Hypergraphs, Families of Vectors, and Combinatorial Probability, Cambridge University Press, 1986 Cambridge.

[2] A. Eherenfeucht and A. Mostowski, Models of axiomatic theories admitting automorphisms, Fund. Math., 43, 1956, pages 50–68.

[3] Paul Erdős, A. Hajnal,A. Máté, & R. Rado, Combinatorial Set Theory: Partition Relations for Cardinals, North-Holland, Amsterdam 1984.

[4] R. Graham, B. Rothschild, & J. Spencer, Ramsey Theory,1990, J. Wiley, New York.

[5] Rami Grossberg, Indiscernible Sequences in a Model Which Fails to Have the Order Property, Journal of Symbolic Logic, 56, 1991, pages 115–123.

[6] Rami Grossberg and Saharon Shelah, On the number of non-isomorphic models for an infinitary logic which has the infinitary order property, Part A, Journal of Symbolic Logic, 51, 1986, pages 302–322.

[7] Michael Morley, Categoricity in power, Trans. A.M.S., 114 (1965), 514– 538.

[8] Michael Morley, Omitting classes of elements, The Theory of Models, edited by Addison, Henkin and Tarski, North-Holland Publishing Co (1965) pages 265–273.

[9] Frank P. Ramsey, On a problem of formal logic, Proc. London Math. Soc. Ser. 2, 30, 1930, pages 264–286.

[10] Saharon Shelah, A Combinatorial Problem: Stability and Order for Theories and Models in Infinitary Languages, Pacific Journal of Mathematics, 41, 1972, 247–261.

[11] Saharon Shelah, Classification Theory and the Number of Nonisomorphic Models, Rev. Ed., North-Holland, 1990.