Statements Equivalent to Non-Dividing Type

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $T$ be a complete $\LL$-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$ $\map {\mathrm {tp} } {\bar c / A, \bar b}$ does not divide over $A$.
$(2): \quad$ For every $\set {\bar b_i : i \in I}$ containing $\bar b$ which is order indiscernible over $A$, there is some $\bar c'$ with $\map {\mathrm {tp} } {\bar c' / A, \bar b} = \map {\mathrm {tp} } {\bar c / A, \bar b}$ such that $\set {\bar b_i : i \in I}$ is order indiscernible over $A,\bar c'$.
$(3): \quad$ For every $\set {\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 $\set {\map f {\bar b_i} : i \in I}$ is order indiscernible over $A, \bar c$.


Motivation

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 $\set {\bar b_i : i \in I}$ containing $\bar b$ be order indiscernible over $A$.


Aiming for a contradiction, suppose $\ds \bigcup_{i \mathop \in I} \map {\mathrm {tp} } {\bar c / A, \bar b_i}$ is not satisfiable.

By the Compactness Theorem, some finite subset $\set {\map {\phi_1} {x, \bar b_{i_1} }, \dots, \map {\phi_k} {x, \bar b_{i_k} } }$ is not satisfiable.

Let $\phi$ be $\phi_1 \wedge \cdots \wedge \phi_k$.

Note that $\map \phi {x, \bar b}$ is in $\map {\mathrm {tp} } {\bar c / A, \bar b}$.

$\set {\map \phi {x, \bar b_i}: i \in I}$ is not satisfiable since it implies $\set {\map {\phi_1} {x, \bar b_{i_1} }, \dots, \map {\phi_k} {x, \bar b_{i_k} } }$.

Again by the Compactness Theorem, some finite subset $\set {\map \phi {x, \bar b_{j_1} }, \dots, \map \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 $\set {\map \phi {x, \bar b_i} : i \in I}$ is not satisfiable.

This contradicts the assumption that $\map {\mathrm {tp} } {\bar c / A, \bar b}$ does not divide over $A$.


Thus $\ds \bigcup_{i \mathop \in I} \map {\mathrm {tp} } {\bar c / A, \bar b_i}$ is satisfiable.

Because $\mathfrak C$ is a monster model, it is satisfiable in $\mathfrak C$.


By Infinite Ramsey's Theorem and indiscernibility of $\set {\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 $\ds \bigcup_{i \mathop \in I} \map {\mathrm {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 \map \phi {b_{i_1}, \dots, b_{i_k}, \bar c_\Delta} \leftrightarrow \map \phi {b_{j_1}, \dots, b_{j_k}, \bar c_\Delta}$ for all $\phi \in \Delta$.


Because $b$ is one of the $b_i$, we have that each $c_\Delta$ realizes $\map {\mathrm {tp} } {\bar c / A, \bar b}$.


By the Compactness Theorem, since there is a $c_\Delta$ with $\mathfrak C \models \map \phi {b_{i_1}, \dots, b_{i_k}, \bar c_\Delta} \leftrightarrow \map \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 $\map {\mathrm {tp} } {\bar c / A, \bar b}$ and which satisfies $\mathfrak C \models \map \phi {b_{i_1}, \dots, b_{i_k}, \bar c'} \leftrightarrow \map \phi {b_{j_1}, \dots, b_{j_k}, \bar c'}$ for all $\phi$.

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


$(2)\implies (1)$:

We prove this case by contradiction.

Aiming for a contradiction, suppose $\map {\mathrm {tp} } {\bar c / A, \bar b}$ divides over $A$.


By definition, this means that $\map {\mathrm {tp} } {\bar c / A, \bar b}$ implies some $\map \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 $\sequence {\bar b_i}_{i \mathop \in \N}$ such that $\map {\mathrm {tp} } {\bar b_i / A} = \map {\mathrm {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 $\set {\map \phi {\bar x, \bar b_{i_1} }, \dots, \map \phi {\bar x, \bar b_{i_k} } }$ is not satisfiable in $\mathfrak C$.

Since $\map {\mathrm {tp} } {\bar{b}_i / A} = \map {\mathrm {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 $\set {\bar b_i : i \in I}$ is order-indiscernible over $A$.

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


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

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

This contradicts the non-satisfiability of $\set {\map \phi {\bar x, \bar b_{i_1} }, \dots, \map \phi {\bar x, \bar b_{i_k} } }$.


Thus, $\map {\mathrm {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 $\set {\map f {\bar b_i} : i \in I}$ be the image of $\set {\bar b_i : i \in I}$.

$\set {\map 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:

\(\ds \mathfrak C \models \map \phi {\map f {\bar b_{i_1} }, \dots, \map f {\bar b_{i_k} }, \bar c}\) \(\leadstoandfrom\) \(\ds \mathfrak C \models \map \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$)
\(\ds \) \(\leadstoandfrom\) \(\ds \mathfrak C \models \map \phi {\bar b_{j_1}, \dots, \bar b_{j_k}, \bar c'}\) as the original sequence is order-indiscernible over $A, \bar c'$
\(\ds \) \(\leadstoandfrom\) \(\ds \mathfrak C \models \map \phi {\map f {\bar b_{j_1} }, \dots, \map f {\bar b_{j_k} }, \bar c}\) as $f$ is an automorphism


$(3)\implies (2)$:

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

$\set {\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:

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

$\blacksquare$