Discrete math with computers_3

180	CHAPTER 7. PREDICATE LOGIC

7.3.4Existential Elimination {E}

Recall the {E} inference rule of propositional logic; this says that if you know a b, and also that c follows from a and c follows from b, then you can infer c.

If the universe is finite, then x.F (x) can be expressed in the form F (p1)

. . . F (pn), where the universe is {p1, . . . , pn}. We could extend the {E} rule so that if we know that F (pi) holds for some i, and furthermore that A must hold if F (x) holds for arbitrary x, then A can be inferred.

The existential elimination rule {E} captures this idea, and it provides a much more convenient tool for reasoning than repeated applications of {E}. Its fundamental importance, however, is that {E} may also be used if the universe is infinite. This means it is more powerful than {E}, as that can be used only for an expression with a finite number of terms. (Recall that a proof must have a finite length.)

	x.F (x)	F (x) A {x arbitrary}		E
			{		}
		A

The following theorem gives an example of {E}. It says that if P (x) always implies Q(x), and also that P (x) holds for some x, then Q(x) also holds for some x.

Theorem 65. x . P (x), x . P (x) → Q(x) x . Q(x)

Proof.

x . P (x) → Q(x)

{ E}

P (c) P (c) → Q(c)

{→E}

x . P (x)

Q(c)

{ E}

Q(c)

{ I}

x . Q(x)

The following theorem says that a directly inside an can be brought outside the .

Theorem 66. x. y. F (x, y) y. x. F (x, y)

Proof.

y. F (p, y)

{ E}

F (p, q)

{ I}

x. F (x, q)

{ I}

x. y. F (x, y)

y. x. F (x, y)

{ E}

y. x. F (x, y)

7.4. ALGEBRAIC LAWS OF PREDICATE LOGIC				181
	Table 7.1: Algebraic Laws of Predicate Logic
	x. f (x)	→	f (c)	(7.3)
	f (c)	→	x. f (x)	(7.4)
	x. ¬ f (x)	=	¬ x. f (x)	(7.5)
	x. ¬ f (x)	=	¬ x. f (x)	(7.6)
	Provided that x does not occur free in q:
	( x. f (x)) q	=	x. (f (x) q)	(7.7)
	( x. f (x)) q	=	x. (f (x) q)	(7.8)
	( x. f (x)) q	=	x. (f (x) q)	(7.9)
	( x. f (x)) q	=	x. (f (x) q)	(7.10)
	( x. f (x)) ( x. g(x))	=	x. (f (x) g(x))	(7.11)
	( x. f (x)) ( x. g(x))	→	x. (f (x) g(x))	(7.12)
	x. (f (x) g(x))	→	( x. f (x)) ( x. g(x))	(7.13)
	( x. f (x)) ( x. g(x))	=	x. (f (x) g(x))	(7.14)

Exercise 10. Prove x. y. F (x, y) y. x. F (x, y).

Exercise 11. The converse of Theorem 66 is the following:

y. x. F (x, y) x. y. F (x, y) Wrong!

Give a counterexample that demonstrates that this statement is not valid.

Exercise 12. Prove x.(F (x) G(x)) ( x.F (x)) ( x.G(x)).

7.4Algebraic Laws of Predicate Logic

The previous section presented predicate logic as a natural deduction inference system. An alternative style of reasoning is based on a set of algebraic laws about propositions with predicates, listed in Table 7.1.

This is not the minimal possible set of laws; some of them correspond to inference rules, and others are provable as theorems. The focus in this section, however, is on practical calculations using the laws, rather than on theoretical foundations.

The following two laws express, in algebraic form, the {E} and {I} inference rules. As they correspond to inference rules, these laws are logical implications, not equations.

182	CHAPTER 7. PREDICATE LOGIC

x. f (x)	→	f (c)	(7.3)
f (c)	→	x. f (x)	(7.4)

In both of these laws, x is bound by the quantifier, and it may be any element of the universe. The element c is any fixed element of the universe. Thus the first law says that if the predicate f holds for all elements of the universe, it must hold for a particular one c, and the second law says that if f holds for an arbitrarily chosen element c, then it must hold for all elements of the universe.

The following theorem combines these two laws and is often useful in proving other theorems. Its proof uses the line-by-line style, which is standard when reasoning about predicate logic with algebraic laws.

Theorem 67. x. f (x) → x. f (x)

Proof.

x. f (x)

→ f (c) {7.3} → x. f (x) {7.4}

The next two laws state how the quantifiers combine with logical negation. The first one says that if f (x) is always false, then it is never true; the second says that if f (x) is ever untrue, then it is not always true.

x. ¬ f (x)	=	¬ x. f (x)	(7.5)
x. ¬ f (x)	=	¬ x. f (x)	(7.6)

The following four laws show how a predicate f (x) combines with a proposition q that does not contain x. These are useful for bringing constant terms into or out of quantified expressions.

( x. f (x)) q	=	x. (f (x) q)	(7.7)
( x. f (x)) q	=	x. (f (x) q)	(7.8)
( x. f (x)) q	=	x. (f (x) q)	(7.9)
( x. f (x)) q	=	x. (f (x) q)	(7.10)

The final group of laws concerns the combination of quantifiers with and . It is important to note that two of them are equations (or double implications), whereas the other two are implications. Therefore they can be used in only one direction, and they must be used at the top level, not on subexpressions.

7.5. SUGGESTIONS FOR FURTHER READING

183

x. f (x) x. g(x)	=	x. (f (x) g(x))	(7.11)
x. f (x) x. g(x)	→	x. (f (x) g(x))	(7.12)
x. (f (x) g(x))	→	x. f (x) x. g(x)	(7.13)
x. f (x) x. g(x)	=	x. (f (x) g(x))	(7.14)

Example 9. The following equation can be proved algebraically:

x. (f (x) ¬g(x)) = x.f (x) ¬x. g(x)

This is established through a sequence of steps. Each step should be justified by one of the algebraic laws, or by another equation that has already been proved. When the purpose is actually to prove a theorem, the justifications should be written explicitly. Often this kind of reasoning is used informally, like a straightforward algebraic calculation, and the formal justifications are sometimes omitted.

x. (f (x) ¬g(x))			{7.11}
=	x. f (x)	x. ¬g(x)
=	x.f (x)	¬x. g(x)	{7.5}

Example 10. The following equation says that if f (x) sometimes implies g(x), and f (x) is always true, then g(x) is sometimes true.

x. (f (x) → g(x)) ( x. f (x)) → x. g(x)

The first step of the proof replaces the local variable x by y in the expression. This is not actually necessary, but it may help to avoid confusion; whenever the same variable is playing di erent roles in di erent expressions, and there seems to be a danger of getting them mixed up, it is safest just to change the local variable. In the next step, the expression is brought inside the ; in the following step it is now possible to pick a particular value for y: namely, the x bound by .

x. (f (x) → g(x)) ( x. f (x))					{7.9}
=	x.	(f (x) → g(x))	( y. f (y))
=	x. (f (x) → g(x))		y. f (y)		change of variable
= x.		(f (x) → g(x))	f (x)		{7.3}
→ x.		g(x)			{Modus Ponens}

7.5Suggestions for Further Reading

The books on logic recommended at the end of Chapter 6 also cover predicate logic. Those citations are not repeated here; instead, two excellent books on style and elegance in mathematical proofs are suggested.

184	CHAPTER 7. PREDICATE LOGIC

Mathematical Writing, by Knuth, Larrabee and Roberts [20], is filled with good advice about how to write mathematics in a style which is clear, rigorous and lively. This short book is based on a course on mathematical writing given by the authors at Stanford.

A rigorous proof is careful, and it covers scrupulously all the relevant aspects of the problem. Routine, straightforward issues may be treated lightly in a rigorous proof, but they really must be sound. In contrast, a formal proof takes no short cuts at all; it does everything using the rules of some formal system, such as the logical inference rules. Formal proofs are good for machine checking and generally fit well with computing applications. Proofs that are informal but rigorous should be written in a clear, elegant style that is convincing to a knowledgeable reader.

Proofs from THE BOOK, by Aigner and Ziegler [3], is an outstanding collection of elegant and rigorous proofs written in normal (but particularly good) mathematical style. It is worth looking at for its beauty, although some of its contents are rather advanced. The book was inspired by an idea of Paul Erd˝os, one of the leading mathematicians of the twentieth century. Erd˝os imagined The Book, which contains the most elegant proofs of the most interesting theorems. The Book doesn’t actually exist; it is an ideal to which real people can only aspire, but it is nevertheless inspiring to mathematicians to find the best approximation to it that they can. Proofs from THE BOOK is such an e ort, and it is likely to become a mathematical classic.

7.6Review Exercises

Exercise 13. Suppose the universe contains 10 elements. How many times will F occur when x. y. z. F (x, y, z) is expanded into quantifier-free form? How large in general are expanded expressions?

Exercise 14. Prove ( x. f (x)) ( x. g(x)) x. (f (x) g(x)).

Exercise 15. Prove ( x. f (x)) ( x. g(x)) x. (f (x) g(x)).

Exercise 16. Prove the converse of Theorem 63.

Exercise 17. Find counterexamples that show that Laws 7.12 and 7.13, which are implications, would not be valid as equations.

Exercise 18. Prove the following implication:

x. f (x) → h(x) x. g(x) → h(x)

→x. (f (x) g(x) → h(x))

Exercise 19. Define a predicate (with the natural numbers 0, 1, 2, . . . as its universe) that expresses the notion that all of the elements that occur in either of the sequences supplied as operands to the append operator

7.6. REVIEW EXERCISES

185

(++) also occur as elements of the sequence it delivers. That is, the predicate states that under certain constraints on the number of elements in the sequence xs, any element that occurs in either the sequence xs or the sequence ys also occurs in the sequence xs ++ ys. Hint: Take ’x occurs in xs’ to mean y. ys.(xs = (y : ys) (x = y) (x occurs in ys)). That is, the proposition ’x occurs in xs’ always has the same value as the proposition y. ys.(xs = (y : ys) (x = y) (x occurs in ys)). Denote the predicate ’x occurs in xs’ by the formula ’x xs’ (overloading the ’ ’ symbol used to denote set membership).

Chapter 8

Set Theory

Set theory is one of the most fundamental branches of mathematics. Many profound advances in mathematics over the past century have taken place in set theory, and there is a deep connection between set theory and logic. More importantly for computer science, it has turned out that the notation and terminology of elementary set theory is extremely useful for describing algorithms, and nearly every branch of computing uses sets from time to time.

This chapter introduces the concepts from set theory that you will need for computer science. Section 8.1 begins by describing what sets are and giving several notations for describing them. There are many useful operations that can be performed on sets, and these are presented in Section 8.2. In Section 8.3, we consider a particular kind of set that is well suited for computing applications: the finite sets with equality. Next, in Section 8.4 we study a variety of mathematical laws that describe properties of sets that are useful in computing. The chapter concludes with a summary of the notations and the main theorems of set theory.

8.1Notations for Describing Sets

We will not define formally what a set is. The reason for this is that set theory was intended originally to serve as the foundation for all of mathematics: everything else in mathematics is to be defined—at least in principle—in terms of sets. As sets are the lowest level concept, there is nothing more primitive that could be used to define them formally.

Informally, a set is just a collection of objects called members or elements. You can think of a set as a group of members, or a collection, or a class, etc. However, these words are just synonyms—they don’t constitute a precise definition of a set. One way to describe a set is to write down all its members inside braces { }. Here are some examples:

189

190	CHAPTER 8. SET THEORY

A = {dog, cat, horse}

B= {canary, eagle}

C= {0, 1, 2, 3, 4}

D= {0, 1, . . . , 100}

E= { }

N= {0, 1, 2, 3, . . .}

Z= {3, {dog, 7}, horse}

Any particular thing can appear only once in a set; this means that it makes sense to ask whether x is a member of a set S—the answer must be yes or no— but it doesn’t make sense to ask how many times x occurs in S. It is bad notation to write a set with some element appearing several times, because the extra occurrences of the element are meaningless, and they might be confusing. You can always remove the redundant copies of an element without changing the set.

A set can have any number of elements. For example, A has three elements, E has zero elements, and N has an infinite number of elements.

It is common to use lower-case letters (a, b, . . .) to refer to members of a set and to use upper-case letters (A, B, . . .) as names for sets themselves. This is just a convention, not an ironclad rule, and of course it breaks down when one set is a member of another set.

An important special case is the empty set { }. Often the special symbol is used to denote the empty set.

Suppose we are given some value x and a set S, and we want to know whether x is a member of S. There is a notation for this question: the expression x S is true if x is a member of S and otherwise false. The expression x S is pronounced as ‘x is a member of S’, or ‘x is an element of S’, or simply as ‘x is in S’. For example:

dog A = True

bat A = False

Another useful notation is x S, which is True if and only if x S is False:

dog A = False

bat A = True

When a set has a few elements, you can just write them out inside braces. This is how the sets A, B, and C were defined above. However, when a set has many elements this becomes tedious, and if the set has an infinite number of elements it is impossible. The set D has 101 elements, but it is more readable to use the . . . notation and omit most of them. Set N , the natural numbers, has an infinite number of elements, and we cannot write them all inside braces.

8.1. NOTATIONS FOR DESCRIBING SETS

191

There is an interesting point about the . . . notation. One of the reasons we use mathematics in computing is to be precise and formal, to be absolutely sure there is no ambiguity in what we are defining. The . . . notation is informal, and it relies on the intuition of the reader to understand and fill in the dots. It is easy to construct cases where di erent people might interpret a set defined with

. . . di erently. For example, does {2, 3, . . . , 7} mean the set of numbers from 2 through 7, {2, 3, 4, 5, 6, 7}, or does it mean the set of prime numbers {2, 3, 5, 7}? If you are aware of such a problem when describing a set, you can overcome it, but how can you ever be sure that your set is really well-defined—that there is one way, and only one way, to interpret it? The problem is not so serious for finite sets, because you could—in principle—write out all the elements, and for large sets you could provide an algorithm that produces all of them. The problem is more fundamental for infinite sets.

Another standard way to define sets is the set comprehension. In its simplest form, a set comprehension is written as

{x | p x},

where p x is simply an expression containing x which is either true or false; such an expression is called a predicate. The expression is pronounced ‘the set of x such that p x’, and it means that the set consists of exactly those objects x of which p x is true. For example, we could define the set of even numbers as

{x | x N even x}.

The predicate here is

p x = x N even x,

and it is true if and only if x is a natural number that is even. In English, we would call this ‘the set of all x such that x is a natural number and x is even’, or simply ‘the set of even natural numbers’.

A more general form of the set comprehension is

{f x | p x}.

In this case, the set consists not of the values x that satisfy the predicate, but of the results of applying the function f to those values. This form of the set comprehension is sometimes easier to use than the simpler form. For example

{√x | x {1, 2, 3, 4}}

defines the set {1.0, 1.41, 1.73, 2.0}.

It is important to state the set from which a variable derives its value. If this set is not stated explicitly, then we assume that it is U, the universe of discourse.

192	CHAPTER 8. SET THEORY

8.2Basic Operations on Sets

There is a large number of operations that can be performed on sets, in order to compare them, define new sets, and so on. This section defines the basic set operations. In the next section, we will see how to implement these operations on a computer.

8.2.1Subsets and Set Equality

There are several important relationships between two sets that are determined by the elements they share. The first of these is the subset relation. The expression A B, pronounced ‘A is a subset of B’, is true if each element of A also appears in B. This idea is expressed formally by the following definition.

Definition 18 (Subset). Let A and B be sets. Then A B if and only if

x.x A → x B.

Two sets are equal if they contain exactly the same elements. We can define this formally using the subset relation, because if A and B contain exactly the same elements, then everything in A is also in B and vice versa. This leads to the definition of set equality.

Definition 19 (Set equality). Let A and B be sets. Then A = B if and only if A B and B A.

If A is a subset of B but A = B, then all the elements of A are in B but there must be some element of B that is not in A. In this case, we say that A is a proper subset of B, which is written as A B. The notations are designed to help you remember them. Think of A B as saying that the set A is contained within B, and it is smaller than B, while A B means that possibly A = B; the symbols and are reminiscent of < and ≤.

Definition 20 (Proper subset). Let A and B be sets. Then A B if and only if A B and A = B.

8.2.2Union, Intersection, and Di erence

There are several operators that take two sets and return a set as a result; the most important of these are union, intersection, and di erence.

•The union of two sets A and B, written A B, is the set that contains all the elements that are in either A or B (or both). Every element of A B must be in A or B (or both).

•The intersection of A and B, written A ∩ B, is the set consisting of all the elements that are in both A and B.