PROPOSITIONAL FUNCTIONS AND QUANTIFIER SCOPE

With a quantification defined, we may now define a propositional function in terms of it. This will replace the provisional definition we gave in chapter 16, which is adequate only to the single-quantifier quantifications we were considering there.

A propositional function Φx is a formula containing at least one variable x that results when one or more quantifiers are deleted from the front of a quantification.

A quantification, as defined on the previous page, is a wff generated by application of clause (iv) last. As usual, this definition is also understood to apply to the variables ó and z too.

Here are some examples:

We used the notion of a propositional function, it will be remembered, in stating our rules of inference for predicate logic. We could have stated them without it, though, at the cost of a little elegance. But where the notion of a propositional function is really useful is in helping to clarify the idea of quantifier scope:

The scope of a quantifier in variable x is the shortest propositional function immediately following the quantifier that is not itself immediately followed by either a variable or a name.

Thus the scope of Ξx inis just Gx; whereas the scope of

The reason for this is thatis a wff by the application

of clause (iv) last, making it a universal quantification, and thus making _xx the shortest propositional function in x following the quantifier. _x is not a wff, so ^ς(Gx^, is not a propositional function.

A formula is a wff only if each variable in it occurs within the scope of a quantifier in the same variable.

We may rephrase this by giving the definitions Qifree and bound variables promised earlier:

A variable x occurring within the scope of a quantifier Vx or 3x is said to be bound by the corresponding quantifier.

and

A variable x not occurring within the scope of any quantifier is said to be free.

Thus any formula in which a variable occurs free—e.g., a propositional function—is not a wff. Again, no variable in a wff can be bound by more than one quantifier.

EXERCISES 19.3

21. Identify which of the following formulas are wffs, giving a brief explanation for your

22. Which of the following are propositional functions, according to the above defini­tion ?

320 Asyllogistic arguments

23. (CHALLENGE) Identify the scope of the quantifier 3x in each Ofthefollowing wffs: