As we said of Aristotle's theory of logic, sentential logic is expressively deficient. Whereas we can express sentences like: a is a large cube and b a small tetrahedron, we cannot express all sorts of important notions in mathematics, e.g.,

Consider the definition of even. A number P is even if there is some whole number Q such that P = 2Q. Suppose we had another concept we wanted to define called supereven: A number P is supereven if for all whole numbers Q, P = 2Q. You can see that the two concepts are different because in one (even) we only need a single Q such that P = 2Q, but in the other (supereven) we need to look at all Q and check that P = 2Q for each. We cannot express the difference in sentential logic because we have no quantifiers.

In sentential logic, we had predicates of arbitrary arity which took constants for arguments. For example, a sentence in Tarski's world in sentential logic is: backof(a,b). Here a and b are individual constants that name particular objects. The sentence a=b is true just in case a and b name the same object. If a or b didn't stand for particular objects, but were variables that stood for a range of objects but no particular objects, then we would no longer have a sentence. For example, let x be a variable that ranges over all natural numbers {0,1,2, ...}. Then x=7 is atomic, but no longer a sentence that is true or false. If we stick in 7 for x, then it is true, but if we stick anything else in for x, it is false. Such objects are called formulae, and if they have free variables like this formulae, they are neither true nor false. Quantifiying over the free variable makes it bound, and turns it into a sentence, i.e., an object that is true or false in a particular domain. For example, by the using the universal quantifier ", we turn this formulae into a false sentence.

x=7 ® "x(x = 7)

The sentence is to be read: For all x, x = 7. We can also use the existential quantifier $ to turn it into a true sentence:

x=7 ® $x(x = 7)

Now this sentence reads: There exists some x such that x = 7.

In sentential logic, we could tell if atomic sentences were true in a world, and then we could use semantics to determine the truth or falsity of compound sentences from the truth or falsehood of the atomics out of which they were composed. We want the same thing for quantified sentences in full first order logic. In this case we need to identify a domain over which the quantified variables can range. For simplicity, consider a very simple example with a finite domain containing only two elements.

Domain = {1,2}

Predicates >

Claims:

1) "x(2>x)

2) $x(2>x)

Intuitively, you can see that the first claim is false in this domain and the second true. But we want a procedure for evaluating all quantified claims from simpler things we already know how to do. One way to go about it is to take any quantified sentence

"x Sx, where Sx is any formula involving x as a variable, and remove the quantifier part, leaving Sx. Now we can say that for each particular object a in our domain, a satisfies the sentence Sa if Sa is true and it doesn't satisfy it if Sa is false. For example, begin with the sentence "x(x = 2) with the domain {1,2}. We take off the quantifier and have two possible objects to stick in for x. Which gives us:

1=2

2=2

The number 2 satisfies the formula but the number 1 does not. A universally quantified sentence "x Sx is true just in case every object a in the domain satisfies the sentence Sa. An existentially quantified sentence $xSx is true just in case some object a in the domain satisfies the sentence Sa.

If the domain is finite, then we can see the ideas of quantifiers by replacing " with & and $with v. So in the above case, for example,

"x(2>x) Þ (2>1) & (2>2)

$x(2>x) Þ (2>1) v (2>2)

where I have underlined the ojects I have put in for the variable x.

If there were three elements in the domain {1,2,3}, then it would be:

"x(2>x) Þ (2>1) & (2>2) & (2 > 3)

$x(2>x) Þ (2>1) v (2>2) v (2 > 3)

and again the first is false and the second is true.

1) Domain = {1,2}

Evaluate "x"y(x > y v y > x)

Here we have to evaluate the sentence in two stages. In the first we replace the sentence with "x as the quantifier with a conjunction in which there is a conjunct for each of the elements of the domain replacing every occurrence of x:

1) "x"y(x > y v y > x) Þ "y(1 > y v y > 1) & "y(2 > y v y > 2)

In the second stage we replace each occurrence of a sentence with "y as the quantifier with a conjunction in which there is a conjunct for each of the elements of the domain replacing every occurrence of y

2a) "y(1 > y v y > 1) Þ (1 > 1 v 1 > 1) & (1 > 2 v 2 > 1)

&

2b) "y(2 > y v y > 2) Þ (2 > 1 v 1 > 2) & (2 > 2 v 2 > 2)

So the overall sentence is:

(1 > 1 v 1 > 1) & (1 > 2 v 2 > 1) & (2 > 1 v 1 > 2) & (2 > 2 v 2 > 2)

2) Difference between "$ and $"

The order of the quantifier matters, as in expressing 1) for every number, there is a bigger one, or 2) there is a smallest number.

1) "x$y(x < y)

2) $x"y(x < y)

That there claims are different, and that the truth of quantified claims depends on the domain can be seen readily. Consider the domain above: {1,2}. Then both are false. The first claim can is true if the domain is the natural numbers N = {0,1,2,3,......}, but the second is false in N, because even 0 is not smaller than itself. In fact, if it is the case that for any object x, its not the case that x is smaller than itself (x<x), then the 2nd claim cannot be true in any domain. The first claim cannot be true in any finite domain. How would you prove it?