Statements Equivalent to Non-Dividing Type

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $T$ be a complete $\mathcal L$-theory.

Let $\mathfrak C$ be a monster model for $T$.

Let $A$ be a subset of the universe of $\mathfrak C$.


The following are equivalent:

$(1): \quad$ $\operatorname{tp}(\bar c / A,\bar{b})$ does not divide over $A$.
$(2): \quad$ For every $\{\bar b_i : i \in I\}$ containing $\bar b$ which is order indiscernible over $A$, there is some $\bar c'$ with $\operatorname{tp}(\bar c' / A,\bar b) = \operatorname{tp}(\bar c / A,\bar b)$ such that $\{\bar b_i : i \in I\}$ is order indiscernible over $A,\bar c'$.
$(3): \quad$ For every $\{\bar b_i : i \in I\}$ containing $\bar b$ which is order indiscernible over $A$, there is some $A,\bar b$-automorphism $f$ such that $\{f(\bar b_i) : i \in I\}$ is order indiscernible over $A,\bar c$.


Note

To help understand statements $(2)$ and $(3)$, suppose you wanted all sequences which are order-indiscernible over $A$ to be order-indiscernible over $A, c$. These statements say this "almost" happens, but we need to change $c$ or the sequence using some automorphism that fixes $A$ and at least one element from the order-indiscernible set.

Statement $(2)$ asserts that all order-indiscernible sequences over $A$ are order-indiscernible over $A, c'$ where $c'$ of the same type as $c$ over $A, b$ with $b$ in the sequence. Note that such $c$ and $c'$ are conjugates under some automorphism fixing $A, b$.

Statement $(3)$ asserts that all order-indiscernible sequences over $A$ can be sent to some other sequence which is order-indiscernible over $A, c$ using an automorphism that fixes $A, b$ with $b$ in the original sequence.


Proof

$(1)\implies (2)$:

Let $\{\bar b_i : i \in I\}$ containing $\bar b$ be order indiscernible over $A$.


Suppose $\displaystyle \bigcup_{i\in I} \operatorname{tp}(\bar c / A,\bar b_i)$ is not satisfiable.

By compactness, some finite subset $\{\phi_1(x, \bar b_{i_1}), \dots, \phi_k(x, \bar b_{i_k})\}$ is not satisfiable.
Let $\phi$ be $\phi_1 \wedge \cdots \wedge \phi_k$.
Note that $\phi(x, \bar b)$ is in $\operatorname{tp}(\bar c / A,\bar b)$.
$\{\phi(x, \bar b_i ) : i\in I\}$ is not satisfiable since it implies $\{\phi_1(x, \bar b_{i_1}), \dots, \phi_k(x, \bar b_{i_k}))$.
Again by compactness, some finite subset $\{\phi(x, \bar b_{j_1}), \dots, \phi(x, \bar b_{j_h})\}$ is inconsistent.
Since all of the $b_i$ are order-indiscernibles, this means that any cardinality $h$ subset of $\{\phi(x, \bar b_i ) : i\in I\}$ is not satisfiable.
This contradicts the assumption that $\operatorname{tp}(\bar c / A,\bar b)$ does not divide over $A$.


Thus $\displaystyle \bigcup_{i\in I} \operatorname{tp}(\bar c / A,\bar b_i)$ is satisfiable, and since $\mathfrak C$ is a monster model, it is satisfiable in $\mathfrak C$.


By Infinite Ramsey's Theorem and indiscernibility of $\{\bar b_i : i \in I\}$ over $A$, for each finite set $\Delta$ of formulas with parameters from $A$, there is some $\bar c_\Delta$ such that:

$\bar c_\Delta$ realizes $\displaystyle \bigcup_{i\in I} \operatorname{tp}(\bar c / A, \bar b_i)$, and
for any $i_1 < \cdots < i_k$ and $j_1 < \cdots < j_k$ in $I$, $\mathfrak C \models \phi(b_{i_1}, \dots, b_{i_k}, \bar c_\Delta) \leftrightarrow \phi(b_{j_1}, \dots, b_{j_k}, \bar c_\Delta)$ for all $\phi \in \Delta$.


Since $b$ is one of the $b_i$, we have that each $c_\Delta$ realizes $\operatorname{tp}(\bar c / A, \bar b)$.


By compactness, since there is a $c_\Delta$ with $\mathfrak C \models \phi(b_{i_1}, \dots, b_{i_k}, \bar c_\Delta) \leftrightarrow \phi(b_{j_1}, \dots, b_{j_k}, \bar c_\Delta)$ for all $\phi \in \Delta$ for each finite $\Delta$, there is a $\bar c'$ with type $\operatorname{tp}(\bar c / A, \bar b)$ and which satisfies $\mathfrak C \models \phi(b_{i_1}, \dots, b_{i_k}, \bar c') \leftrightarrow \phi(b_{j_1}, \dots, b_{j_k}, \bar c')$ for all $\phi$.

But this holding for every $\phi$ means that $\{b_i : i\in I\}$ is order-indiscernible over $A,\bar c'$.


$(2)\implies (1)$:

We prove this case by contradiction.

Suppose $\operatorname{tp}(\bar c / A,\bar{b})$ divides over $A$.


By definition, this means that $\operatorname{tp}(\bar c / A,\bar{b})$ implies some $\phi(x, \bar{b})$ with parameters from $A$ which divides over $A$.

By definition of dividing, this means that for some $k \in \N$ there is a sequence $(\bar{b}_i)_{i\in \N}$ such that $\operatorname{tp}(\bar{b}_i / A) = \operatorname{tp}(\bar{b} / A)$ for each $i\in\N$, and for any distinct $k$-many terms $\bar b_{i_1}, \dots, \bar b_{i_k}$ of the sequence, the set $\{\phi(\bar{x}, \bar{b}_{i_1}), \dots, \phi(\bar{x}, \bar{b}_{i_k})\}$ is not satisfiable in $\mathfrak C$.

Since $\operatorname{tp}(\bar{b}_i / A) = \operatorname{tp}(\bar{b} / A)$ for each $i$, we can assume (using an argument involving Infinite Ramsey's Theorem and partitions based on the formula satisfied by the $b_i$) that $\{\bar b_i : i\in I\}$ is order-indiscernible over $A$.

Then, by $(2)$, there is $\bar c'$ with $\operatorname{tp}(\bar c' / A,\bar b) = \operatorname{tp}(\bar c / A,\bar b)$ such that $\{\bar b_i : i\in I\}$ is order-indiscernible over $A,\bar c'$.


However, $\operatorname{tp}(\bar c' / A,\bar b) = \operatorname{tp}(\bar c / A,\bar b)$ gives us that $\mathfrak C \models \phi(\bar c', \bar{b})$.

So, $\{\bar b_i : i\in I\}$ being order-indiscernible over $A,\bar c'$ gives us that $\mathfrak C \models \phi(\bar c', \bar{b_i})$ for all $i$.

This contradicts the non-satisfiability of $\{\phi(\bar{x}, \bar{b}_{i_1}), \dots, \phi(\bar{x}, \bar{b}_{i_k})\}$.


Thus, $\operatorname{tp}(\bar c / A,\bar{b})$ does not divide over $A$.


$(2)\implies (3)$:

Since $c$ and $c'$ have the same type over $A,b$, the function $\bar c' \mapsto \bar c$ is partial elementary.

Since $\mathfrak C$ is homogeneous, there is an $A, b$-automorphism $f$ which extends $\bar c' \mapsto \bar c$.

Let $\{f(\bar b_i) : i \in I\}$ be the image of $\{\bar b_i : i \in I\}$.

$\{f(\bar b_i) : i \in I\}$ is order-indiscernible over $A,\bar c$ since if $i_1 < \cdots < i_k$ and $j_1 < \cdots < j_k$, then:

\(\displaystyle \mathfrak C \models \phi(f(\bar b_{i_1}), \dots, f(\bar b_{i_k}), \bar c)\) \(\leadstoandfrom\) \(\displaystyle \mathfrak C \models \phi(\bar b_{i_1}, \dots, \bar b_{i_k}, \bar c')\) as $f$ is an automorphism (fixing any parameters in $\phi$ from $A, b$)
\(\displaystyle \) \(\leadstoandfrom\) \(\displaystyle \mathfrak C \models \phi(\bar b_{j_1}, \dots, \bar b_{j_k}, \bar c')\) as the original sequence is order-indiscernible over $A, \bar c'$
\(\displaystyle \) \(\leadstoandfrom\) \(\displaystyle \mathfrak C \models \phi(f(\bar b_{j_1}), \dots, f(\bar b_{j_k}), \bar c)\) as $f$ is an automorphism


$(3)\implies (2)$:

Let $\bar c' = f^{-1}(\bar c)$.

$\{\bar b_i : i \in I\}$ is order-indiscernible over $A, \bar c'$ since if $i_1 < \cdots < i_k$ and $j_1 < \cdots < j_k$, then:

\(\displaystyle \mathfrak C \models \phi(\bar b_{i_1}, \dots, \bar b_{i_k}, \bar c')\) \(\leadstoandfrom\) \(\displaystyle \mathfrak C \models \phi(f(\bar b_{i_1}), \dots, f(\bar b_{i_k}), \bar c)\) as $f$ is an automorphism (fixing any parameters in $\phi$ from $A, b$)
\(\displaystyle \) \(\leadstoandfrom\) \(\displaystyle \mathfrak C \models \phi(f(\bar b_{j_1}), \dots, f(\bar b_{j_k}), \bar c)\) as the image sequence is order-indiscernible over $A, \bar c$.
\(\displaystyle \) \(\leadstoandfrom\) \(\displaystyle \mathfrak C \models \phi(\bar b_{j_1}, \dots, \bar b_{j_k}, \bar c')\) as $f$ is an automorphism

$\blacksquare$