31 | August | 2010 | Logicians do it with Models

Archive for August 31st, 2010

Beth’s Definability Theorem

August 31, 2010

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.

Posted in Beth's Theorem, Definability, Elementary Model Theory | Leave a Comment »

M	T	W	T	F	S	S
« Jun				Sep »
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

Logicians do it with Models

Archive for August 31st, 2010

Beth’s Definability Theorem

Categories

Archives

Twitter

Mathematics and Philosophy Links

Follow “Logicians do it with Models”