Let $L$ be a first order language and $L'$ a language which comes from $L$ by adding constants. Show that if $T$ is a Skolem theory in $L$, then $T$ is a Skolem theory in $L'$ (and hence so is any theory $T\subseteq T'$ in $L'$).

This is question 3.1.1 from Hodges' Shorter Model Theory; I found a solution (as attached below) but I don't at all understand what he is doing. Specifically:

  1. What is he doing when he 'write $\phi$ as $\phi '(\bar{x},\bar{c},y)$, with $\phi' (\bar{x},\bar{z},y)$'? Supposedly $\phi$ is expanded from having only 2 variables ($\bar x, y)$ to 3 ($\bar x,\bar c,y$) because of the language expansion by constants...? But why then replace the constant $\bar c$ with $\bar z$, a new free variable?

  2. What is this lemma on constant he is citing? I have been looking all over 3.1 but I don't see any thing related. Without knowing what this lemma is, I can't understand what that step of the proof is about.

enter image description here


The point of replacing $\phi(\bar{x}, y)$ by $\phi'(\bar{x}, \bar{z}, y)$, is to get an $L$-formula (which is used in the next line of the proof). The formula $\phi(\bar{x}, y)$ is an $L'$-formula, and since we have only added constants in $L'$, the only symbols that prevent $\phi(\bar{x}, y)$ from being an $L$-formula are those constants. Another way of formulating this is that every $L'$-formula $\phi(\bar{x}, y)$ arises from some $L$-formula $\phi'(\bar{x}, \bar{z}, y)$ by filling in some tuple of constants $\bar{c}$ on the place of $\bar{z}$. So $\phi(\bar{x}, y)$ is $\phi'(\bar{x}, \bar{c}, y)$.

Your second question comes down to a more general trick in model theory. I do not have a copy of Hodges' book, but I am sure this is what he means:

For any theory $T$ and any formula $\phi(\bar{x})$, both not containing the constants $\bar{c}$, we have: $$ T \vdash \forall \bar{x} \phi(\bar{x}) \quad \Longleftrightarrow \quad T \vdash \phi(\bar{c}). $$

The implication from the left to the right is trivial (and even holds if $\phi$ or $T$ contains $\bar{c}$). The other direction is not needed for your question, but may be a nice exercise to prove. So a direct application of this lemma (left to right direction) allows you to replace $\bar{z}$ by $\bar{c}$ in that step.

  • 2
    $\begingroup$ The "lemma on constants" is Lemma 2.3.2 on p. 40 of Hodges (the proof is Exercise 2.3.4). $\endgroup$ – Alex Kruckman Jun 2 '19 at 2:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.