6
$\begingroup$

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?

$\endgroup$
2
  • 2
    $\begingroup$ It's unclear what you're asking. Do you mean that you want to go from $P(f(a))$ to $\forall x.P(x)$ or something like $P(f(a))$ to $\forall f.P(f(a))$ or what? $\endgroup$ Sep 16, 2019 at 1:34
  • 1
    $\begingroup$ @DerekElkins I want to go from $P(f(a))$ to $\forall x P(x)$. $\endgroup$
    – Lachie
    Sep 16, 2019 at 1:37

1 Answer 1

8
$\begingroup$

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.)

$\endgroup$
4
  • $\begingroup$ In the second part are you saying that we don't know whether the range of $f$ is the domain of the interpretation or not, but we can't assume that it is the whole domain so we treat $f$ as if its range is restricted, even if its range is actually the whole domain. $\endgroup$
    – Lachie
    Sep 16, 2019 at 1:58
  • $\begingroup$ @Lachie Sort of, but it sounds like you're imagining that we've already fixed a model and a particular meaning of $f$. That's backwards: when we ask "Is it the case that $\Gamma\models\theta$?," we're looking at all possible models of $\Gamma$. So rather than e.g. "even if its range is actually the whole domain," it would be better to say "even though in some models its range is the whole domain." $\endgroup$ Sep 16, 2019 at 2:02
  • $\begingroup$ Maybe more clearly (here $\Gamma=\emptyset$): if you have a structure $M$, without looking at it I know that the sentence "$\exists x(f(x)=f(a))$" is true in it, regardless of how $f$ and $a$ happen to be interpreted. I do not know however whether the sentence "$\forall y\exists x(f(x)=y)$" is true in $M$. $\endgroup$ Sep 16, 2019 at 2:06
  • $\begingroup$ Ok, I think that clears things up, thanks! $\endgroup$
    – Lachie
    Sep 16, 2019 at 2:09

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.