Perhaps you can see the intuitive argument that tells us the conclusion 2* > z will be true whenever x > 4. We already saw that it is true for x - 4. As X grows larger than 4, the left side, 2 doubles each time x increases by 1. However, the right side, , grows by tfie ratio () If x > 4, then (x + I)fx cannot be greater tiian 1.25, and therefore () cannot be bigger than 1.5625. Since 1.5625 < 2, each time x increases above 4 the left side 2 grows more than the right side x. Thus, as long as we start from a value like X - 4 where the inequality 2 > x is already satisfied, we can increase x as much as we like, and the inequality will still be satisfied.

We have now completed an informal but accurate proof of Theorem 1.3. We shall return to the proof and make it more precise in Example 1.17, after we introduce inductive proofs.

Theorem 1.3, like all interesting theorems, involves an infinite number of related facts, in this case the statement if a; > 4 then 2 > x for all integers X. In fact, we do not need to assume x is an integer, but the proof talked about repeatedly increasing x by 1, starting at x - 4, so we really addressed only the situation where x is an integer.

Theorem 1.3 can be used to help deduce other theorems. In the next example, we consider a complete deductive proof of a simple theorem that uses Theorem 1.3.

Theorem 1.4: If зг is the sum of the squares of four positive integers, then 2 > x.

PROOF: The intuitive idea of the proof is that if the hypothesis is true for x., that is, X is the sum of the squares of four positive integers, then x must be at least 4. Therefore, the hypothesis of Theorem 1.3 holds, and since we believe that theorem, we may state that its conclusion is also true for x. The reasoning can be expressed as a sequence of steps. Each step is either the hypothesis of the theorem to be proved, part of that hypothesis, or a statement that, follows from one or more previous statements.

By follows we mean that if the hypothesis of some theorem is a previous statement, then the conclusion of that theorem is true, and can bo written down as a statement of our proof. This logical rule is often called modus poneris; i.e., if we know H is true;, and we know if H then C is true, wo may conclude that С is true. We also allow certain other logical steps to be used in creating a statement that follows from one or more previous statements. For instance, if A and В are two previous statements, then we can deduce and write down the statement A and B.

Figure 1.3 shows the sequence of statements we need to prove Theorem 1.4. While we shall not generally prove theorems in such a stylized form, it helps to think of proofs as very explicit lists of statements, each with a precise justification. In step (1), we have repeated one of the given statements of the theorem: that X is the sum of the squares of four integers. It often helps in proofs if we name quantities that are referred to but not named, and we have done so here, giving the four integers the names a. b, c, and d.

Figure 1.3: A formal proof of Theorem 1,4

In step (2), we put down the other part of the hypothesis of the theorem: that the. viums being squared are each at least 1. Technically, this statement represents four distinct statements, one for each of the four integers involved. Then, ill step (3) we observe that if a number is at least 1, then its square is also at least 1. We use as a justification the fact that statement (2) holds, and properties of arithmetic. That is, we assume the reader knows, or can prove simple statements about how inequalities work, such as the statement if у > 1, then y > 1.

Step (4) uses statements (i) and (3). The first statement tells us that x is the sum of the four squares in question, and statement (3) tells us that each of the squares is at least 1. Again using well-known properties of arithmetic, we conclude that x is at least 1 + 1 + 1-1-1, or 4.

At the final step (5), we use statement (4), which is the hypothesis of Theorem 1.3. The theorem itself is the justification for writing down its conclusion, since it.4 hypothesis is a previous statement. Since the statement (5) that is the conclusion of Theorem 1,3 is also the conclusion of Theorem 1.4, we have now proved Theorem 1,4. That is, we have started with the hypothesis of that theorem, and have managed to deduce its conclusion. □

1.2.2 Reduction to Definitions

In the previous two theorems, the hypotheses used terms that should have been familiar: integers, addition, and multipUcation, for instance. In many other theorems, including many from automata theory, the terms used in the statement may have implications that are less obvious. A useful way to proceed in many proofs is:

If you are not sure how to start a proof, convert all terms in the hypothesis to their definitions.

Here is an example of a theorem that is simple to prove once we have expressed its statement in elementary terms. It uses the following two definitions:

1. A set S is finite, if there exists an integer n such that S has exactly n elements. We write 5[ = n, where S is used to denote the number

Figure 1.4: Restating the givens of Theorem 1,5

We aie stiJl stuck, so we need to use a common proof technique called proof by contradiction. In this proof method, to be discussed further in Section 1.3.3, we assume that the conclusion is false. We then use that assumption, together with parts of the hypothesis, to prove the opposite of one of the given statements of the hypothesis. We have then shown that it is impossible for all parts of the hypothesis to be true and for the conclusion to be false at tlie same time. The only possibility that remains is for the conclusion to be true whenever the hypothesis is true. That is, the theorem is true.

In the case of Theorem 1.5, the contradiction of the conclusion is T is finite. Let us assume T is finite, along wdth the statement of the hypothesis that says S is finite; i.e., S = n for some integer n. Similarly, we can restate the assumption that T is finite as = m for some integer m.

Now one of the given statements tells us that S U T - U, and S C\T = That is, the elements of U are exactly the elements of S and T. Thus, there must be n + m elements of U. Since n + m is an integer, and we have shown \\U\l = n + m, it follows that U is finite. More precisely, we showed the number of elements in U is some integer, which is the definition of finite. But the statement that U is finite contradicts the given statement that U is infinite. We have thus used the contradiction of our conclusion to prove the contradiction

of elements in a set S. If tlie set S is not finite, we say S is infinite. Intuitively, an infinite set is a set that contains more than any integer number of elements,

2. If 5 and T are both subsets of some set U. then T is the complement of S (with respect to 6) \i SuT U and 5 П T й- That is, each element of и is in exactly one of S and T: put another way, T consists of exactly those elements of U that are not in S.

Theorem 1.5: Let 5 be a finite subset of some infinite set U. Let T be the complement of S with respect to U. Then T is infinite.

PROOF: Intuitively, this theorem says tliat if you have an infinite supply of something {U), and you take a finite amount away (S), then you still have an infinite amount loft. Lot us begin by restating the facts of the theorem as in Fig. 1,4,