3
$\begingroup$

In section 4 of the article on Generalised Quantifiers in the Stanford Encyclopedia of Philosophy http://plato.stanford.edu/entries/generalized-quantifiers/ the author writes:

"Modern predicate logic fixes the meaning of $\forall$ and $\exists$ with the respective clauses in the truth definition, which specifies inductively the conditions under which a formula $\phi (y1,…,yn)$ (with at most y1,…,yn free) is satisfied by corresponding elements b1,…,bn in a model $M = (M, I)$ (where $M$ is the universe and $I$ the interpretation function assigning suitable extensions to non-logical symbols): $M \vDash \phi(b1,…,bn)$. The clauses are

$M \vDash \forall x \psi(x, b1,…,bn)$ iff for each $a \in M$, $M \vDash \psi(a, b1,…, bn)$

$M \vDash \exists x \psi(x, b1,…, bn)$ iff there is some $a \in M$ s.t. $M \vDash \psi(a, b1,…, bn)$

To introduce other quantifiers, one needs to appreciate what kind of expressions $\forall$ and $\exists$ are. Syntactically, they are operators binding one variable in one formula. To see how they work semantically it is useful to rewrite (1) and (2) slightly. First, every formula $\psi(x)$ with one free variable denotes in a model $M$ a subset of $M$; the set of individuals in $M$ satisfying $\psi(x)$."

Why is it important that he write "(with at most y1,…,yn free)" and "every formula $\psi(x)$ with one free variable". Why should there be free variables?

$\endgroup$
2
$\begingroup$

Suppose we want to fix the truth-value for, e.g., $\forall x\exists yRxy$ with respect to the model $M$. Let's do this without invoking free variables for a moment, using new constants instead.

Start with two very intuitive, very natural, thoughts about the semantics of quantifiers:

$\forall x\varphi(x)$ is true if whatever in the domain we pick out and dub '$a$', $\varphi(a)$ is true, so long as $a$ is a new name.

$\exists x\varphi(x)$ is true if for some object in the domain, if we pick it out and dub it with the new name '$b$', $\varphi(b)$ is true.

So, applying the first, $M \vDash \forall x\exists yRxy$ iff every $M'$ which extends $M$ by assigning an object to the new constant $a$ is such that $M' \vDash \exists yRay$.

And given an $M'$, when does $M' \vDash \exists yRay$? Applying the second idea, that holds when we can in some way or other extend $M'$ to $M''$ by assigning an object to '$b$' such that $M'' \vDash Rab$

Now note at the second stage in this story, we need to apply our rule for the existential quantifier to a wff which already contains the new constant '$a$' (some would call '$a$' here a parameter). Therefore we must indeed allow our rules for dealing with the quantifications $\forall x\varphi(x)$, $\exists x\varphi(x)$ to apply even when the $\varphi$ contains parameters.

There really should be nothing at all mysterious about this so far -- after all, the guiding thoughts behind the rules for interpreting quantifiers are surely entirely natural.

Unfortunately perhaps, many logicians (always tempted by Bauhaus austerity) prefer not to use new constants or parameters which are typographically distinguished from variables, but prefer (on the grounds of economy) to re-use the same letters both for 'real' variables tying quantifiers to slots in predicates and for free variables serving the role of parameters. It isn't necessary to do this as we have seen, but it is probably the majority practice (which reflects informal mathematical usage).

And now, if we do make double uses of our $x$s and $y$s, then the entirely natural thought that our rules for the quantifiers have to apply even when $\varphi$ contains temporary constants/parameters transmutes into the slightly less transparent requirement that the rules have to apply even when $\varphi$ contains free variables. But in fact this is still just the old unmysterious first thought about quantifier rules under a very thin typographical disguise.

$\endgroup$
1
$\begingroup$

The reason for saying "with at most $y_1,\dots,y_n$ free" is to make sure that the list $b_1,\dots,b_n$ provides values for all the free variables (and to implicitly say which of the values $b_i$ is to be understood as associated with which free variable $y_i$).

The reason for $\psi(x)$ to have only the one free variable $x$ will presumably show up in the next part of the text after what you quoted. The universal and existential quantifiers embody properties of subsets of the model, namely the property of being the whole model (for $\forall$) and the property of being nonempty (for $\exists$). The next part of the text will presumably be about whether the subset defined by $\psi(x)$ has one of these properties. If $\psi$ had $k>1$ free variables, it would not define a subset of the model but rather a $k$-ary relation, so the properties corresponding to the quantifiers wouldn't apply to it.

$\endgroup$
0
$\begingroup$

A formula can have free variables and bounded variables (attention, e.g. in $\varphi:=\ '(x=y)\lor \forall x\,\exists z\,(x=z)'$ both $x$ and $y$ are free). So, the assumption that $\varphi$ has some free variables and naming them as $y_1,..,y_k$ is clear: $Var(\varphi)=\{y_1,\dots,y_k\}$. If we want to define/construct something inductively on formulas, consider that it is already done on $\varphi$ and on $\psi$, then the set of free variables of $\varphi\land\psi$ or $\varphi\lor\psi$ is the union of $Var(\varphi)$ and $Var(\psi)$. That's why it may have benefit to originally prove/construct whatever we want with a condition like $Var(\varphi)\subseteq \{y_1,..,y_n\}$.

For the other question, as I see, the semantic interpretation of quantifiers is being told in the text, so for that we consider formulas of the form $\forall x \psi$. Of course, it is possible that $x$ is not present/not free in $\psi$, in this case the quantifier doesn't do anything new. So, for the important case we can assume that $x$ is free in $\psi$. Observe also, that from the context, this $\forall x\,\psi$ is a subformula of $\varphi$, hence $Var(\psi)\subseteq\{x,y_1,y_2,..,y_n\}$, and the $y_i$'s are considered already evaluated by the $b_i\in M$ values.

$\endgroup$

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.