Mathematical Proof and the Principles of Mathematics/Logic/Quantifiers and predicates

So far we've only talked about the logic of statements. But mathematics also talks about things, for examples sets and numbers. We need to extend our system of logic to include reasoning with statements about things as well. At this point, the way logic is usually presented diverges somewhat from the way it commonly used is mathematics. Our task is to describe the latter, so our notation and proof layout will differ a bit from what you may see in a logic textbook.

Universe of discourse

Recall that a predicate can be thought of as a function whose values are either True or False. More specifically, they take objects in our 'universe of discourse' as inputs, and produce truth values as outputs. In mathematics the universe of discourse consists of mathematical objects such as the sets and numbers mentioned above. Notice that logic does require this, nor does it require that universe of discourse have anything to do with the actual universe. So there is no logical reason to make the assumption that there are any objects in the universe of discourse at all. Whether the actual universe has any objects is a matter for physicists to decide.

Notation for predicates

We'll use the notation $P(x)$, $Q(x)$, ... to stand for a predicates, where $x$ is meant to stand for an object in our universe of discourse. The choice of the letter $x$ is somewhat arbitrary, so we could also use $P(y)$ to mean a predicate. Similarly, we'll use $R(x,y)$, $S(x,y)$, $T(x,y,z)$... to stand for relations in two variables (for $R$ and $S$), three variables (for $T$), and so on. It's usual to use letters from near the end of the alphabet in this context.

Since the choice of the letter $x$ in $P(x)$ is arbitrary, it might be more correct to a more generic placeholder and write the predicate as $P(\cdot )$ for example. This becomes ambiguous for more complex expressions though. For example if you combine the two predicates with a logical connective, as in $P(\cdot )$ implies $Q(\cdot )$, it may mean the predicate $P(x)$ implies $Q(x)$, or it may mean the relation $P(x)$ implies $Q(y)$.

Note that the usual notation in logic does not use parentheses, so a predicate would be written $Px$. We're using parentheses to emphasize that a predicate is a type of function.

Variables and constants

There's an old saw (known as Osborn's Law) that "variables don't and constants aren't." Fully written out it says variables don't always vary and constants aren't always constant. The upshot is that the distinction between a variable and constant is blurry at best and much depends on the context. Generally though, a variable is taken to represent something arbitrary or nonspecific, while constant is assumed to represent some specific thing. Grammatically, it's similar to the distinction between an improper noun and a proper noun. It's customary to use letters near the beginning of the alphabet for constants and letters near the end of the alphabet for variables.

So, for example, the notation $P(x)$ represents a predicate which has different values depending on a variable $x$. But the notation $P(a)$, where $a$ is a constant, represents a specific value of either True or False. In other words $P(a)$ is considered a statement.

Combining predicates

We've already used this above, but it's worth stating that predicates and relations can be combined using the logical connectives just as statements can. So, for example, given predicates $P(x)$ and $Q(x)$ you can create a new predicate $P(x)$ implies $Q(x)$ and a relation $P(x)$ implies $Q(y)$. Similarly, predicates and relations can be combined with statements, for example $R(x,y)$ iff S.

The universal quantifier

There are two new logical connectives which can be applied to predicates and relations. The first of these is called the universal quantifier which is applied to a predicate to form a statement. The universal quantifier applied to a predicate $P(x)$ is written

For all $x$, $P(x)$

and is True when $P(x)$ has the value True no matter what the value of $x$. In symbols this is written

$\forall xP(x)$

though

$(x)P(x)$

is also used. In the order of operations, the phrase "For all $x$" ranks equally with negation.

As an example we'll look the predicate here is "x is beautiful." Applying the universal quantifier to this produces

For all $x$, $x$ is beautiful.

This is the same as the Ray Stevens line

Everything is beautiful.

One way to interpret the universal quantifier logically is to say that

For all $x$, $P(x)$

is the same as the conjunction of all the statements $P(a)$, where $a$ takes on every value in the universe of discourse. If the universe is discourse is finite then this can be written out explicitly. So if the universe of discourse consists of two objects 'a' and 'b', then

For all $x$, $P(x)$

is the same as

$P(a)$ and $P(b)$.

It might also be interpreted as

$P(b)$ and $P(a)$

but since these are equivalent it makes no difference which interpretation you choose.

If the universe of discourse has only a single object 'a' then

For all $x$, $P(x)$

is simply

$P(a)$.

If the universe of discourse has no objects at all then

For all $x$, $P(x)$

is

$True$.

This may seem a bit counterintuitive, but if there are no objects then there is no object for which the statement $P(a)$ can be False, and so the statement

For all $x$, $P(x)$

is vacuously True.

If the universe of discourse has three or more objects then multiple interpretation are possible. For example if the universe of discourse has three objects 'a', 'b', and 'c', then some possible interpretations of

For all $x$, $P(x)$

are

($P(a)$ and $P(b)$) and $P(c)$

$P(a)$ and ($P(b)$ and $P(c)$)

($P(c)$ and $P(b)$) and $P(a)$.

But repeated applications of

$P$ and $Q$ iff $Q$ and $P$

and

($P$ and $Q$) and $Q$ iff $P$ and ($Q$ and $Q$)

both of which we've already proved, show that all these interpretations are equivalent.

So if the number of objects in the universe of discourse is known and finite then we really haven't added anything new. Otherwise, we have added something new, though we can use this interpretation to help decide what the rules of inference for the universal quantifier should be.

Bound and unbound variables

Logic texts usually make a distinction between bound and unbound variable. Variables which appear in connection with a quantifier are 'bound', and those that appear more or less at random, not connected to a quantifier are considered unbound or free. This distinction usually doesn't appear in mathematical proofs so we won't say much more about it. Instead, we'll just stress the difference between a predicates and statements. An expression like

$x$ is beautiful

with an unbound variable is considered a predicate since it depends on the variable $x$. On the other hand expressions like

For all $x$, $x$ is beautiful

and

Alice is beautiful

are considered statements since they are either True or False.

Some expressions, such as

For all $x$, $R(x,y)$

involve both free and bound variables. In this case the truth of the expression depends only on the value of $y$, so it can be taken to be predicate in the variable $y$. In general, if an expression involves several variables $x,y,z,\dots ,$ then putting the phrase 'For all $x$' in front of it creates an expression which only depends on $y,z,\dots .$

You could also add the phrase 'For all $x$' to an expression which does not involve $x$. Technically, what the expression

For all $x$, $Q$

does is to implicitly create a predicate $Q(x)$ whose value is always $Q$, then replace the statement with

For all $x$, $Q(x)$.

One might think that

For all $x$, $Q$

would be logically equivalent to $Q$, and it would be if the universe of discourse has at least one object, but if there are no objects then

For all $x$, $Q$

is always True while $Q$ may be False. This is where you can starting seeing the nature of universe of discourse reflected in logical statements. The question of whether the universe has any objects is settled by determining whether the statement

For all $x$, $False$

or its negation

Not for all $x$, $False$

is True.