A theory on a language with a constant, an unary relation, and unary function

Question

This is one of the exercises from the lecture notes.

Let $\mathcal{L}$ have just a constant symbol $c$, a unary relation symbol $U$ and a unary function symbol $f$, and suppose that $\Sigma \vdash Ufc$ , and that $f$ does not occur in the sentences of $\Sigma$. Then $\Sigma \vdash \forall x Ux$.

Since this is my homework, I don't want any direct solution, of course. However, I couldn't understand where I should use the assumption $f$ does not occur in the sentences of $\Sigma$ . If you provide a hint for this, I would be glad.

Answer 1

It's easiest to reason semantically here: argue that if $\Sigma\vdash Ufc$ with the given hypothesis on $\Sigma$, then in every model of $\Sigma$ the predicate $U$ holds of every element. We then get the desired $\Sigma\vdash\forall xUx$ via the completeness theorem.

I'll give here the proof of a similar result, and leave the task of modifying the argument to apply to your problem as an exercise:

Suppose we have a language $\mathcal{L}$ consisting of just a unary predicate $U$ and a constant symbol $c$. If $\Sigma$ is a set of $\mathcal{L}$-sentences in which $c$ is not used (so, $\Sigma$ is in fact a set of $\{U\}$-sentences) such that $\Sigma\vdash Uc$ then in fact $\Sigma\vdash\forall xUx$.

Proof: The key point is that since $\Sigma$ only involves the symbol $U$, if $\mathfrak{A},\mathfrak{B}$ are $\mathcal{L}$-structures whose $\{U\}$-reducts are equal then $\mathfrak{A}\models\Sigma\iff\mathfrak{B}\models\Sigma$. Here for $\mathcal{L}_0\subseteq\mathcal{L}_1$, the $\mathcal{L}_0$-reduct of an $\mathcal{L}_1$-structure $\mathfrak{C}$ is the $\mathcal{L}_0$-structure gotten from $\mathfrak{C}$ by just "forgetting" the interpretations of the symbols in $\mathcal{L}_1\setminus\mathcal{L}_2$.

OK, so let $\mathfrak{A}\models\Sigma$ and fix $a\in\mathfrak{A}$. Consider the structure $\mathfrak{B}$ with the same underlying set as $\mathfrak{A}$, the same interpretation of $U$ as $\mathfrak{A}$, and with $c^\mathfrak{B}=a$. Since $\mathfrak{A}$ and $\mathfrak{B}$ have the same $\{U\}$-reducts and $\mathfrak{A}\models\Sigma$ we have $\mathfrak{B}\models\Sigma$; since $\mathfrak{B}\vdash Uc$ we have $c^\mathfrak{B}=a\in U^\mathfrak{B}$. But since $\mathfrak{B}$ and $\mathfrak{A}$ have the same interpretation of $U$, this gives $a\in U^\mathfrak{A}$.

So $U$ holds on every element in every model of $\Sigma$. This means by completeness that $\Sigma\vdash\forall xUx$.