Let’s go back to the proposition with which we started this section: “Roses are red”. This sentence is more difficult to handle than it might appear. We still can’t express it properly in logic. The problem is that this proposition is not saying something about some particular entity. It really says that all roses are red (which happens to be a false statement, but that’s what it means). Predicates can only be applied to individual entities.
Many other sentences raise similar difficulties: “All persons are mortal.” “Some roses are red, but no roses are black.” “All maths courses are interesting.” “Every prime number greater than two is odd.” Words like all, no, some, and every are called quantifiers. We need to be able to express similar concepts in logic.
Suppose that P is a predicate, and we want to express the proposition that P is true when applied to any entity in the domain of discourse. That is, we want to say “for any entity x in the domain of discourse, P(x) is true”. In predicate logic, we write this in symbols as ∀x(P(x)). The ∀ symbol, which looks like an upside-down A, is usually read ‘for all’, so that ∀x(P(x)) is read as “for all x, P(x)”. (It is understood that this means for all x in the domain of discourse for P.) For example, if R is the predicate ‘is red’ and the domain of discourse consists of all roses, then ∀x(R(x)) expresses the proposition “All roses are red”. Note that the same proposition could be expressed in English as “Every rose is red” or “Any rose is red”.
Now, suppose we want to say that a predicate, P, is true for some entity in its domain of discourse. This is expressed in predicate logic as ∃x(P(x)). The ∃ symbol, which looks like a backwards E, is usually read ‘there exists’ ,but a more exact reading would be ‘there is at least one’. Thus, ∃x(P(x)) is read as “There exists an x such that P(x)”, and it means “there is at least one x in the domain of discourse for P for which P(x) is true”. If, once again, R stands for ‘is red’ and the domain of discourse is ‘roses’, then∃x(R(x)) could be expressed in English as “There is a red rose” or “At least one rose is red” or “Some rose is red”. It might also be expressed as “Some roses are red”, but the plural is a bit misleading since ∃x(R(x)) is true even if there is only one red rose. We can now give the formal definitions:
Suppose that P is a one-place predicate. Then ∀x(P(x)) is a proposition, which is true if and only if P(a) is true for every entity a in the domain of discourse for P. And ∃x(P(x)) is a proposition which is true if and only if there is at least one entity, a, in the domain of discourse for P for which P(a) is true. The ∀ symbol is called the universal quantifier, and ∃ is called the existential quantifier.
The x in ∀x(P(x)) and ∃x(P(x)) is a variable. (More precisely, it is an entity variable, since its value can only be an entity.) Note that a plain P(x)—without the ∀x or ∃x—is not a proposition. P(x) is neither true nor false because x is not some particular entity, but just a placeholder in a slot that can be filled in with an entity. P(x) would stand for something like the statement ‘x is red’, which is not really a statement in English at all. But it becomes a statement when the x is replaced by some particular entity, such as ‘the rose’. Similarly, P(x) becomes a proposition if some entity a is substituted for the x, giving P(a).
An open statement is an expression that contains one or more entity variables, which becomes a proposition when entities are substituted for the variables. (An open statement has open ‘slots’ that need to be filled in.) P(x) and “x is red” are examples of open statements that contain one variable. If L is a two-place predicate and x and y are variables, then L(x, y) is an open statement containing two variables. An example in English would be “x loves y”. The variables in an open statement are called free variables. An open statement that contains x as a free variable can be quantified with ∀x or∃x. The variable x is then said to be bound. For example, x is free in P(x) and is bound in ∀x(P(x)) and ∃x(P(x)). The free variable y in L(x, y) becomes bound in ∀y(L(x, y))and in ∃y(L(x, y)).
Note that ∀y(L(x,y)) is still an open statement, since it contains x as a free variable. Therefore, it is possible to apply the quantifier ∀x or ∃x to ∀y(L(x,y)), giving∀x(∀y(L(x, y))) and ∃x(∀y(L(x, y))). Since all the variables are bound in these expressions, they are propositions. If L(x, y) represents ‘x loves y’, then ∀y(L(x, y)) is some- thing like “x loves everyone”, and ∃x(∀y(L(x, y))) is the proposition, “There is someone who loves everyone”. Of course, we could also have started with ∃x(L(x, y)): “There is someone who loves y”. Applying ∀y to this gives ∀y(∃x(L(x,y))), which means
“For every person, there is someone who loves that person”. Note in particular that ∃x(∀y(L(x, y))) and ∀y(∃x(L(x, y))) do not mean the same thing. Altogether, there are eight different propositions that can be obtained from L(x, y) by applying quantifiers, with six distinct meanings among them.
From now on, I will leave out parentheses when there is no ambiguity. For example, I will write ∀x P(x) instead of ∀x(P(x)) and ∃x ∃y L(x, y) instead of∃x(∃y(L(x, y))). Make sure though that when you leave out the parentheses you do so only when no ambiguity exists. In one of the problems of this chapter, you will see an example of two very similar statements where the parentheses do change the meaning significantly!
Further, I will sometimes give predicates and entities names that are complete words instead of just letters, as in Red(x) and Loves(john, mary). This might help to make examples more readable.