Definition:Divide (Model Theory)

From ProofWiki
Jump to navigation Jump to search


Definition

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$.

Let $\phi \left({\bar x, \bar b}\right)$ be an $\mathcal L$-formula with free variables $\bar x$ and parameters $\bar b$ from the universe of $\mathfrak C$.

Let $\operatorname{tp} \left({\bar b / A}\right)$ denote the type of $\bar b$ over $A$.

Then $\phi \left({\bar x, \bar b}\right)$ $k$-divides in $\mathfrak C$ over $A$ if and only if:

there exists a sequence $\left\langle{\bar b_i}\right\rangle_{i \mathop \in \N}$ such that $\operatorname{tp} \left({\bar b_i / A}\right) = \operatorname{tp} \left({\bar b / A}\right)$ for each $i \in \N$

and:

for any distinct $k$-many terms $\bar b_{i_1}, \ldots, \bar b_{i_k}$ of the sequence, the set $\left\{{\phi \left({\bar x, \bar b_{i_1} }\right), \ldots, \phi \left({\bar x, \bar b_{i_k} }\right)}\right\}$ is not satisfiable in $\mathfrak C$.


Let $\pi \left({\bar x, \bar b}\right)$ be a set of formulas with parameters $\bar b$.

$\pi \left({\bar x, \bar b}\right)$ $k$-divides over $A$ if it implies a formula $\phi \left({x, \bar c}\right)$ which $k$-divides over $A$.


Formulas and sets of formulas are said to divide if they $k$-divide for some $k$.


Note

To help understand the definition, consider the following informal discussion.

We can think of $\phi \left({x, y}\right)$ as a description of $x$ in terms of $y$.

If $b$ and $b'$ have the same type over $A$, then as far as $A$ can tell, $b$ and $b'$ are the same thing, in the sense that they both satisfy the same formulas with parameters from $A$.

So $\phi \left({x, b}\right)$ $k$-dividing over $A$ means that we can find an infinite sequence of parameters $b_i$ that $A$ can't tell apart, but nevertheless, no $x$ can satisfy any $k$ of the descriptions $\phi \left({x, b_i}\right)$ at the same time.


Example

Consider the language $\mathcal L = \left\{{\sim}\right\}$ with one binary relation symbol $\sim$.


Let $\mathcal M = \left({\R^2, P}\right)$ be the $\mathcal L$-structure where $P$ is the equivalence relation defined by $\left({x_1, y_1}\right) \mathrel P \left({x_2, y_2}\right)$ if and only if $x_1 = x_2$.

That is, $P$ identifies points in the plane which project vertically to the same value on the $x$-axis.

Let $\mathfrak C$ be some monster model for $\mathcal M$.

The formula $x \sim \left({0, 0}\right)$ $2$-divides over $\varnothing$, which can be seen by considering the sequence $\left({\left({0, 0}\right), \left({1, 0}\right), \left({2, 0}\right), \left({3, 0}\right), \ldots}\right)$.

The language is not very complicated; every $\left({n, m}\right)$ has the same type over $\varnothing$, so in particular each term in this sequence has the same type as $\left({0, 0}\right)$.

However, $x \sim \left({n, 0}\right)$ and $x \sim \left({m, 0}\right)$ cannot be simultaneously satisfied for $n \ne m$, since this would imply $\left({n, 0}\right) \mathrel P \left({m, 0}\right)$, which is impossible.

The formula $x \sim \left({0, 0}\right)$ does not $k$-divide over $A = \left\{{\left({0, y}\right): y \in \R}\right\}$ for any $k$ however, since only points of the form $\left({0, y}\right)$ are of the same type as $\left({0, 0}\right)$ over $A$.