Exchange Principle

From ProofWiki
Jump to: navigation, search

This article is not under active maintenance.

While the contents of this page could be useful, they are currently not being maintained.

The correctness, lay-out and usefulness of the article may be compromised, so use whatever you get from here with caution.


Theorem

Let $D$ be a strongly minimal set in $\mathcal M$.

Let $A$ be a subset of $D$.

Let $b, c \in D$.


If $b$ is algebraic over $A \cup \left\{ {c}\right\}$ but not over $A$, then $c$ is algebraic over $A \cup \left\{ {b}\right\}$.


Proof

Let $D \left({x}\right)$ be a formula defining $D$, which exists since by definition, strongly minimal sets are definable.

To simplify exposition, we will assume below that all further mentioned formulas are $\mathcal L$-formulas with parameters from $A$, in addition to whatever other parameters are supplied.


Suppose $b$ is algebraic over $A \cup \left\{ {c}\right\}$ but not over $A$.


By definition of being algebraic, there is some $\phi \left({x, c}\right)$ with $x$ free such that $\mathcal M \models \phi \left({b, c}\right)$ and $\left\{ {m \in \mathcal M: \mathcal M \models \phi \left({m, c}\right)}\right\}$ is finite.

Consequently, the subset $\{m\in \mathcal M : \mathcal M \models D \left({m}\right) \wedge \phi(m, c)\} = \{d\in D : \mathcal M \models \phi(d, c)\}$ must have some finite $n \in \N$ many elements.


Let $\psi(y)$ be the formula

$\displaystyle D(y) \wedge \exists x_1 \cdots \exists x_n \left( \left( \bigwedge_{i=1,\dots,n} D(x_i) \wedge \phi(x_i, y) \right) \wedge \forall z \left( D(z) \wedge \phi(z, y) \rightarrow \left( \bigvee_{i=1,\dots,n} z = x_i \right) \right) \right)$

which asserts that

$\{d\in D : \mathcal M \models \phi(d, y)\}$ has $n$ many elements.

Note the dependence on the free variable $y$.


We will argue that $\phi(b, x) \wedge \psi \left({x}\right))$ demonstrates the algebraicity of $c$ over $A\cup \left\{ {b}\right\}$.


Suppose (with the intent of deriving a contradiction) that $\{d\in D : \mathcal M \models \phi(b, d) \wedge \psi(d)\}$ is infinite.

Since $D$ is strongly minimal, $\{d\in D : \mathcal M \models \phi(b, d) \wedge \psi(d)\}$ is cofinite in $D$.
Thus $D - \{d\in D : \mathcal M \models \phi(b, d) \wedge \psi(d)\}$ has some finite $k \in \N$ many elements.
Define $\chi \left({x}\right)$ to be a formula which asserts that $D - \{d\in D : \mathcal M \models \phi(x, d) \wedge \psi(d)\}$ has $k$ many elements. This can be done similarly to how $\psi(y)$ was defined above.
$\chi$ cannot define a finite subset of $D$, since $\chi$ involves only parameters from $A$ and $\mathcal M \models \chi(b)$, and so this would imply that $b$ is algebraic over $A$.
Thus, $\chi$ defines an infinite subset of $D$.
So, we may let $b_1, \dots, b_{n+1}$ be distinct elements of $D$ such that $\mathcal M \models \chi(b_i)$ for each $i = 1,\dots,n+1$.
For each $i=1,\dots,n+1$, define
$C_i = \{d\in D : \phi(b_i, d) \wedge \psi(d)\}$
Then each $C_i$ is cofinite in $D$, since $\mathcal M \models \chi(b_i)$ and hence $D - \{d\in D : \mathcal M \models \phi(b_i, d) \wedge \psi(d)\}$ has $k$ many elements.
It follows that $\displaystyle \bigcap_{i=1,\dots,n+1} C_i$ is nonempty, since $D$ is infinite and the intersection excludes at most $k \cdot (n+1)$ elements of $D$.
Let $\displaystyle \hat c \in \bigcap_{i \mathop = 1, \dots, n + 1} C_i$.
By definition of each $C_i$, this means that $\mathcal M \models \psi(\hat c)$ and $\mathcal M \models \phi(b_i, \hat c)$ for $i=1,\dots,n+1$.
But this is a contradiction, since the definition of $\psi$ gives us that $\mathcal M \models \phi(d, \hat c)$ for only $n$ many $d\in D$.


Thus $\left\{ {d \in D : \mathcal M \models \phi(b, d) \wedge \psi(d) }\right\} = \left\{ {m \in \mathcal M : \mathcal M \models \phi(b, m)\wedge \psi \left({m}\right)}\right\}$ is finite.


Since $\mathcal M \models \phi \left({b, c}\right) \wedge \psi \left({c}\right)$, this means that $c$ is definable over $A \cup \left\{ {b}\right\}$.

$\blacksquare$