Beth's Definability Theorem

Beth’s Definability Theorem

We’ll set this up in the most general way and later see how Hellman’s account in terms of $\phi$ and $\psi$ applies.

Letting $\textup{L}$ be a language with $p$ a $k$ -ary relation symbol not appearing in the relation-symbol set of $\textup{L}$ , $\textup{L}^{+}$ is the language that extends $\textup{L}$ and which includes $p$ . $\textup{T}^{+}$ is a theory in $\textup{L}^{+}$ .

We say that $p$ is explicitly definable if, and only if, there is an $\textup{L}$ formula $\theta$ with free variables $x_{0}\dots x_{k-1}$ such that $\textup{T}^{+} \models p x_{0}\dots x_{k-1} \leftrightarrow \theta$ . And we say that $p$ is implicitly definable if, and only if, for any $\textup{L}$ - structure $\mathfrak{A}$ and any $\textup{P}, \textup{Q} \subseteq \ \vert \mathfrak{A}\vert^{k}$ (i.e., the universe of the structure), if both $(\mathfrak{A}, \textup{P})$ , and $(\mathfrak{A}, \textup{Q})$ are models of $\textup{T}^{+}$ , then $\textup{P} = \textup{Q}$ .

Beth’s definability theorem says that if $\textup{L}$ a language with $p$ a $k$ -ary relation symbol not appearing in the relation-symbol set of $\textup{L}$ , $\textup{L}^{+}$ is the language that extends $\textup{L}$ and which includes $p$ and $\textup{T}^{+}$ is a theory in $\textup{L}^{+}$ , then $p$ is explicitly definable if, and only if, $p$ is implicitly definable.

To prove that explicit definability implies implicit definability is straightforward. Assume $\textup{T}^{+} \models p x_{0}\dots x_{k-1} \leftrightarrow \theta$ . Show for $\textup{P}, \textup{Q} \subseteq \ \vert \mathfrak{A}\vert^{k}$ , if $(\mathfrak{A}, \textup{P}), (\mathfrak{A}, \textup{Q}) \in \textup{M} od (\textup{T}^{+}) \rightarrow \textup{P} = \textup{Q}$ . Since we’re assuming $\textup{T}^{+} \models p x_{0}\dots x_{k-1} \leftrightarrow \theta$ , $\textup{P}$ is definable over $\mathfrak{A}$ (i.e., for $k$ -ary $p$ , $\textup{P} = \phi^{\mathfrak{A}}$ , for $\phi$ with $k$ free variables. Let $\phi = \theta$ . So $\textup{P} = \theta$ ; but $\textup{Q} \subseteq \ \vert \mathfrak{A}\vert^{k}$ and $(\mathfrak{A},\textup{Q})$ models $\textup{T}^{+}$ . So $\textup{P} = \theta^{\mathfrak{A}}$ $\square$ .

To prove that implicit definability implies explicit definability takes just a bit longer, but it’s simple; using the Compactness Theorem and the Craig Interpolation Theorem.

Next time I’ll turn to how Hellman deals with the problems posed by this theorem.

About these ads

This entry was posted on August 31, 2010 at 8:32 AM and is filed under Beth's Theorem, Definability, Elementary Model Theory. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Logicians do it with Models

Beth’s Definability Theorem

Like this:

Leave a Reply Cancel reply

Follow “Logicians do it with Models”