Exchange Principle

From ProofWiki
Jump to navigation Jump to 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$