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

From Wikibooks, open books for an open world
Jump to navigation Jump to search

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[edit]

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[edit]

We'll use the notation , , ... to stand for a predicates, where is meant to stand for an object in our universe of discourse. The choice of the letter is somewhat arbitrary, so we could also use to mean a predicate. Similarly, we'll use , , ... to stand for relations in two variables (for and ), three variables (for ), 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 in is arbitrary, it might be more correct to a more generic placeholder and write the predicate as for example. This becomes ambiguous for more complex expressions though. For example if you combine the two predicates with a logical connective, as in implies , it may mean the predicate implies , or it may mean the relation implies .

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

Variables and constants[edit]

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 represents a predicate which has different values depending on a variable . But the notation , where is a constant, represents a specific value of either True or False. In other words is considered a statement.

Combining predicates[edit]

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 and you can create a new predicate implies and a relation implies . Similarly, predicates and relations can be combined with statements, for example iff S.

The universal quantifier[edit]

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 is written

For all ,

and is True when has the value True no matter what the value of . In symbols this is written

though

is also used. In the order of operations, the phrase "For all " 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 , 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 ,

is the same as the conjunction of all the statements , where 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 ,

is the same as

and .

It might also be interpreted as

and

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 ,

is simply

.

If the universe of discourse has no objects at all then

For all ,

is

.

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

For all ,

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 ,

are

( and ) and
and ( and )
( and ) and .

But repeated applications of

and iff and

and

( and ) and iff and ( and )

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[edit]

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

is beautiful

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

For all , is beautiful

and

Alice is beautiful

are considered statements since they are either True or False.

Some expressions, such as

For all ,

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

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

For all ,

does is to implicitly create a predicate whose value is always , then replace the statement with

For all , .

One might think that

For all ,

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

For all ,

is always True while 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 ,

or its negation

Not for all ,

is True.