next up previous
Next: Tuesday, February 15 Up: Lecture Notes Previous: Friday, February 11

Monday, February 14

Happy Valentine's Day!

February 14 Notes

Quantifiers Made Official

First, we allow sentences without logical connectives to be more 
complex.  Up until now, the simple sentences of our language have
been propositional letters P.  We now allow them to take the more
general form P(x_1,...,x_n):

P
Q(x)
R(x,y)
S(x,y,z,w,u,v)

are all legal atomic sentences, and they can also be written

P
Qx
Rxy
Sxyzwuv

as long as the arguments are just letters.

In these atomic sentences, the components Q,R,S (and one may suppose
even the propositional letter P) are called ``predicates''; each predicate
has a predetermined number of arguments which it always takes (its
``arity''); we will not have both L(x) and L(x,y) in the same context.

If our language has complex names like x+y, then sentences like

P(x+y,z) are allowed.

Predicates are ``verbs'' and arguments are ``nouns''.

Now that we have facilities for putting names of objects into propositions,
we can introduce the quantifiers:  if S is a sentence of our language
(a formula) then

(Ax.S) and (Ex.S) are sentences, read ``for all x, S'' and ``for some x, S''
(or ``there exists an x such that S'').

I thought of using \-/ for the universal quantifier, but I thought
better of it :-)

Before talking about the quantifier rules, I will talk about the semantics
of the quantifiers.  I want to make the point that quantifiers can be
thought of as ``infinitary'' conjunctions and disjunctions (or as real
conjunctions and disjunctions if the universe is finite).  I also want
to make points about trivial quantifiers and about nested quantifiers
which can best be made in combination with a view of quantifiers as
conjunctions/disjunctions.  Allude to the fact that it is possible to
extend our Boolean algebra with rules that will cover quantifiers, but
we will not do it!

Also, talk about locutions like ``All men are mortal''.

The Official Rules for quantifiers are as follows:

(Ax.S)
--------  universal quantifier elimination (instantiation)
S[T/x]

S[T/x]
--------  existential quantifier introduction (witness elimination)
(Ex.S)

These rules are easy, and easy to understand.  If ``for all x, S'' is
true, then we should expect that S[T/x], in which a particular T
replaces all occurrences of x, will be true.  Notice that T may be a
complex term.

1. (Ax.x = x) premise
(1'. (x=x)[3+4/x] line 1)
2. 3+4 = 3+4 univ. elim. line 1 (or 1').

1. 3+4 = 3+4
(1'. (x=x)[3+4/x] line 1)
2. (Ex.x=x) exist. intro. line 1 (or 1').

If S[T/x] is true, we see that there exists an x (namely a) such that
S.  Line 1' is optional; it depends how formal one wants to be...

The only complication here (and the example from the previous lecture
which we now repeat shows that it really is a complication!) is that
one needs to be careful about carrying out substitutions in the
presence of variable binding constructions.

1. (Aa . (x|->a)(3) = a)  premise
2. ((x|->a)(3) = a)[x/a]  univ. elim. line 1
3. (x|->x)(3) = a         ``line 2''

is not a valid proof (which is fortunate, because we could use
it to prove that everything is equal to 3!) because line 3 is not
really equivalent to line 2.  The substitution shown in line 2 cannot
be carried out unless the bound variable x is first changed to something
else so that it will not interfere with the substitution of a free variable
x for a.  A correct line 3 would be

3. (y|->x)(3) = a  line 2 --note the change of bound variable in the function.



Randall Holmes
2000-05-05