Ordinary language statements like ``x > 3, x = y+3, x > x-1'' are not ``statements'' in the sense of KST because we cannot assign truth values.

But if we replace x by 4 in ``x > 3'' we get a statement. Similarly if we replace x by 1. Note that in the first case, ``4 > 3''is true whereas in the second case, ``1 > 3'' is false.

If Px represents ``x > 3'' then P4 is true, P1 is false, and
Pelephant is meaningless. In considering Px we need to agree to
what ``x''can be, i.e., to a *universe of discourse* for P.

Similarly, if Pxy is ``x = y+3'' and the universe of discourse for P is the set of pairs of integers, P4,1 is true, P3,1 is false and P[1/2],-[7/2] is not even considered.

If Px is ``x > x-1'' and the universe of discourse is the set of
real numbers, **R**, observe that Px is true for every real
number x Î **R**.

The expression P is called a *predicate*.

We have seen that one way to obtain a statement from a predicate is to
replace the variables by particular elements of the universe of
discourse. Another way is to *quantify*. The universal
quantification of Px is the statement, ``Px is true for all x in
the universe of discourse''. It is typically denoted "x Px,
or in the extended notation of our text, (Ùx |:Px) or
("x |:Px).

If Px is ``x > 3'' and the universe of discourse is **Z**,
then "x Px is false. How do we know? There is an x, e.g., 2,
such that Px is false.

If Px is ``x > x-1'' and the universe of discourse is **Z**,
then "x Px is true.

The existential quantification of Px is the statement there exists an x in the universe of discourse such that Px is true. It is typically denoted $x Px, or in the extended notation of our text, (Úx |:Px) or ($x |:Px).

Let Qxy be the predicate ``x = y+1''. Take **Z** × **Z** to be the universe of discourse. Observe that
"x $y Qxy which is parsed "x ($y Qxy)
is true whereas $y "x Qxy which is parsed $y("x Qxy) is false.

A good reference for this is Rosen, *Discrete Mathematics and Its Applications*, Chapter 1.3. This is the textbook for both Math
1190 and Math 2320 and is readily available if you want to photocopy
the section. It gives a good discussion from a semantic point of view
of universal and existential quantification. Chapter 9 of
Gries-Schneider provides the syntactic treatment which we will
follow.

We start with Chapter 8 which treats *quantification* in
general. Beware as this chapter is a mine field. We will make
extensive use of some supplementary materials prepared in previous
years by Professor Ganong for clarification.

(*x | R:P)

x is a variable name, * an operator (in the examples, * is one of Ù, Ú, +, ·),R an expression of type Boolean, P an expression whose type depends upon *. In the case of Ù and Ú, P is of type Boolean.

Examples:

- ("x | R:P) also written (Ùx | R:P).

This interprets as ``For all values of x in the universe of discourse such that R holds, P holds''. In our informal examples we understand what is meant by replacing x by a value. We will need to wait until we define*free occurrences*of variables to obtain a better formal defintion.Let the universe of discourse be

**Z**, the set of integers.

("n | n is odd : n^{2}is odd ) is true.

("n | n is odd : true) is true.

("n | true : n^{2}is odd ) is false.

("n | false : n^{2}is odd ) is true.

If we write ("x | :P) we abbreviate ("x | true:P) or what is often written "x P. - ($x | R:P) also written ($x | R:P).

This interprets as ``For some values of x in the universe of discourse such that R holds, P holds''.Let the universe of discourse be

**Z**, the set of integers.

($n | n > 0 : n^{2}= 4) is true.

($n | n > 0 : n^{2}= -1) is false.

($n | true : n^{2}= -1) is false.

($n | false : n^{2}= 4) is false.

If we write ($x | :P) we abbreviate ($x | true:P) or what is often written $x P. - (åx | R:P) also written (+ x | R:P).

This interprets as the sum obtained by adding the values of P obtained by replacing x in P (actually*free*occurrences of x in P) with each of the values of x for which R holds.

(åk | 1 £ k £ 3 : k^{2}) is 1^{2}+ 2^{2}+ 3^{2}.

(åk | 1 £ k £ n : k) is 1 + 2 + 3 + ¼+n.

File translated from T

On 28 Oct 2000, 22:43.