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.