Why can't a function be universally generalised on?

137 Views Asked by At

To universally generalise on a constant term, the constant must occur arbitrarily. I have read that the values of a function may be restricted to only part of an interpretation's domain. This means that a term such as '$f(a)$' can never be said to occur arbitrarily. The book defines a constant term as arbitrary in a derivation if it does not occur in any premises or assumptions governing it.

If a function does not occur in any of the premises or governing assumptions, and we derive something like $Bf(a)$ where $B$ is a predicate, why can't we universally generalise on $f(a)$ if we don't know that the values of the function are restricted?

1

There are 1 best solutions below

4
On BEST ANSWER

The natural "general" form of universal quantification breaks down when we try to apply it to terms more complicated than constant symbols. A more limited form of it is admissible, but we generally don't present it due to the potential for misuse.

Incidentally, this is a great example of how semantic analyses make everything much easier.


First, let me dispose of the general form:

The sentence $$(*)\quad\exists x(f(x)=f(a))$$ is a tautology: it's true in every model. However, the sentence $$(**)\quad\forall y\exists x(f(x)=y)$$ we get by trying to "universally generalize out" the "$f(a)$" is very much not.

The issue is that a term of the form "$f(a)$" has a bit of nontrivial information: $f(a)$ isn't just any old element of our ambient structure, it's an element in the range of $f$. And this means the term "$f(a)$" is dangerous, from the point of view of universal generalization - things which are true of elements of the range of $f$ might not be true of arbitrary objects.


That said, a restricted form of it does hold. You mention specifically the case of a single unary predicate symbol, but we can go a bit further (below "$f$" is a unary function symbol):

Suppose $\Gamma$ is a set of formulas not using $f$, $\varphi(z)$ is a formula not using $f$, and $\Gamma\models\varphi(f(a))$. Then $\Gamma\models\forall z(\varphi(z))$.

We can see this semantically quite quickly. Suppose otherwise. Let $M\models\Gamma\cup\exists z(\neg\varphi(z))$. Pick a witness of this in $M$ - that is, $M\models\neg\varphi(m)$. Now consider the expansion $M'$ of $M$ gotten by interpreting $f$ as the constant function sending everything to $m$. Since $\Gamma\models\varphi(f(a))$, we know that $M'\models\varphi(m)$, but then $M\models\varphi(m)$ as well.

(Crucial here is the fact that $\varphi$ makes sense in $M$ alone - this relies on $f$ not occurring in $\varphi$. In the example $(*)$ above, the corresponding formula $\varphi$ is $\exists x(f(x)=z)$, and so this same "expand-reduce" idea doesn't work.)