How can a formula have nontrivial alternation number?

91 Views Asked by At

I'm trying to understand the basic properties of indiscernible sequences, and it seems like I'm not understanding the definition correctly, because it seems like the alternation number of a formula should be trivial by the definition of indiscernible sequences.

Background

Conventions: $\phi(x;y)$ denotes a "partitioned" formula: w/ variables $x$ and parameters $y$

The definition of indiscernible sequence from "A Guide to NIP Theories":

We will typically denote sequences of tuples by $I = (a_i : i \in \mathcal{J})$ where $\mathcal{J}$ is some linearly-ordered set. The order on $\mathcal{J}$ [is] $<_{\mathcal{J}}$ [...]

Let $\Delta$ be a finite set of formulas and $A$ a set of parameters. A (possibly finite) sequence $I = (a_i : i \in \mathcal{J})$ is $\Delta$-indiscernible over $A$, if for every integer $k$ and two increasing tuples $i_1 <_{\mathcal{J}} ... <_{\mathcal{J}} i_k$ and $j_1 <_{\mathcal{J}} ... <_{\mathcal{J}} j_k$, $b \in A$ and formula $\phi(x_1, ..., x_k ; y) \in \Delta,$ we have $\phi(a_{i_1}, ..., a_{i_k} ; b) \leftrightarrow \phi(a_{j_1}, ..., a_{j_k} ; b).$ An indiscernible sequence is an infinite sequence which is $\Delta$-indiscernible for all $\Delta$.

So I interpret an indiscernible sequence to mean:

For $\mathcal{J}$ a linearly-ordered set,

$I = (a_i | i : J)$ Indiscernible over a set of parameters $A$

$:\iff$

$\forall \phi(x_1, ..., x_k; y) : \text{Partitioned Formula in L}, k : \mathbb{N}, (i), (j) : k-\operatorname{Chain}(\mathcal{J}), b : A,$

$\phi(a_{i_1}, ..., a_{i_k}; b) \leftrightarrow \phi(a_{j_1}, ..., a_{j_k}; b),$

where by $L$ I mean the ambient language $L$ for the formulas.

The definition of alternation number of a formula $\phi$ from "Introduction to theories without the independence property":

$\operatorname{alt}(\phi(\bar{x}; \bar{y})) = \max \big\{ n < \omega \; \big| \; \exists (\bar{a}_i)_{i < \omega} \; \textit{indiscernible} \; \exists \bar{b} \; \forall i < n - 1 \; \big[ \models \phi(\bar{a}_i; \bar{b}) \leftrightarrow \neg \phi(\bar{a}_{i+1}; \bar{b}) \big] \big\}$

if the maximum exists, or $\infty$ otherwise

That is, it's the maximum over indiscernible sequences of the number of alternations of the formula $\phi$ on the sequence.

(And "Introduction to theories without the independence property" says "the alternation number of $\phi(\bar{x}; \bar{y})$ counds the maximal number of segments into which an instance $\phi(\bar{x}; \bar{b})$ of $\phi$ can cut an indiscernible sequence")

Problem

The point of indiscernibility seems to be you can't use any formula in $L$ to distinguish two subsequences of the same length against the same element of the parameter set. Thus, intuitively, it shouldn't be possible to make the formula alternate on the sequence. And we have:

Prop) Let $I = (a_i | i : \mathcal{J})$ indiscernible over $A$,

$2 \leq n : \mathbb{N},$

$i : n-\operatorname{Chain}(\mathcal{J}),$

$b : A,$

$\phi(x_1; y) : \text{Partitioned Formula in L in one variable}$.

Then $\forall (t < u : n), \phi(a_{i_t}; b) \leftrightarrow \phi(a_{i_u}; b).$

Proof:

If $t, u : n$, then $(i_t), (u_t) : 1-\operatorname{Chain}{\mathcal{J}}$.

But $I$ indiscernible over $A$, hence in the special case $k=1$,

$\forall \tilde\phi(x_1; y) : \text{Partitioned Formula in L}, (\tilde i), (\tilde j) : 1-\operatorname{Chain}(\mathcal{J}), b : A,$

$\tilde\phi(a_{\tilde i_1}; b) \leftrightarrow \tilde\phi(a_{\tilde j_1}; b).$

Thus, in the special cases $\tilde\phi = \phi$, $(\tilde i) = (i_t)$, $(\tilde j) = (i_u)$,

$\phi(a_{i_t}; b) \leftrightarrow \phi(a_{i_u}; b).$

Corrollary) The alternating number of every single-variable formula in $L$ is 1.

i.e., for every $I = (a_i | i : \mathcal{J})$ indiscernible over $A$, $( \phi(a_{i_1}; b) \leftrightarrow \neg \phi(a_{i_2}; b) ) \rightarrow ( \phi(a_{i_2}; b) \leftrightarrow \phi(a_{i_1}; b) \leftrightarrow \neg \phi(a_{i_2}; b) )$.

Nontrivial examples

In "Introduction to theories without the independence property," two examples are given, but no proof. I can't then see how the limit is attained and thus distinguish what allows a formula to alternate on an indiscernible sequence:

For example, the alternation number of a formula with constant truth value, like $x = x \wedge y = y,$ is 1, the alternation number of a linear order is 2, and $\operatorname{alt}(x = y) = 3.$

I would expect these are to be implemented as formulas in one parameter (y) and one variable (x), like the divisibility example for the independence property.

Refs

P. Simon, A Guide to NIP Theories.

H. Adler, Introduction to theories without the independence property.

1

There are 1 best solutions below

7
On BEST ANSWER

The $\overline{a}$s are being distinguished by the tuple $\overline{b}$, but $\overline{b}$ is not required to be a tuple from the parameter set over which the $\overline{a}$s are indiscernible.

So, for example, consider:

  • The structure is $(\mathbb{Q}, <)$ and our parameter set is $A=\emptyset$.

  • Our indiscernible sequence is $a_i=i$ - the natural numbers. It's easy to see that this is in fact an $A$-indiscernible sequence.

  • $b={1\over 2}$.

  • $\varphi(x;y)$ is "$x<y$."

Then we have $\varphi(a_0; b)$ but $\neg\varphi(a_1; b)$; this shows that the alternating number of "$x<y$" is at least $2$. And it's easy to see that in fact it has to be exactly $2$, since the indiscernible sequence has to be monotone.

In particular, note that while the sequence of $a_i$s above is indiscernible over $\emptyset$