of one of tho givoTi statements of the hypothesis, and by the principle of proof by contradiction we may conclude the theorem is true, □

Proofs do not have to be so wordy. Having seen the ideas behind the proof, let us reprove the theorem in a few lines.

PROOF: (of Theorem 1.5) know that SUT = U and S and T are disjoint, so 5 + - Suice S is faiite, 5 - n for some integer n, and since U is infinite, there is no integer p such that \\U\\ - p. So assume that T is finite; that is, jT - m for some integer m. Then \\U\\ = \\S\\ + \\T\\ - тг + ш, which coiitradif:ts the given statement that there is no integer p equal to \\U\\. □

1.2.3 Other Theorem Forms

The if-then form of theorem is most common in typical areas of mathematics. However, we see other kinds of statements proved as theorems also. In this section, we sliaJl examine the most common forms of statement and what we usually need to do to prove them.

Ways of Saying If-Then

First, there are a immber of lands of theorem statements that look different from a simple if H then C form, but are in fact saying the same thing: if hypothesis H is true for a given value of the parameter(s), then the conclusion С is true for the same value. Here are some of the other ways in which if H then C might appear.

1. H implies C.

2. Я only if C.

3. С if Я.

4. Whenever H holds, С follows.

We also see many variants of form (4), sucli as if Я holds, then С follows, or whenever Я holds, С holds.

Example 1.6: The statement of Theorem 1.3 would appear in these four forms as:

1. X >4 implies 2= > a;.

2. a; > 4 only if 2 > x.

3. 2 > Ж- if a; > 4.

4. Whenever x r! 4, 2 > follows.

□

Statements With Quantifiers

Many theorems involve statements that use the quantifiers for all and there exists, or similar variations, such as for every instead of for all. The order in which these quantifiers appear affects what the statement means. It is often helpful to see statements with more than one quantifier as a game between two players - for-ail and there-exists - who take turns specifying values for the parameters mentioned in the theorem. For-all must consider all possible choices, so for-alls choices are generally left as variables. However, there-exists only has to pick one value, which may depend on the values picked by the players previously. The order in which the quantifiers appear in the statement determines who goes first. If the last player to make a choice can always find some allowable value, then the statement is true.

For example, consider an alternative definition of infirnte set : set S is infinite if and only if for all integers n, there exists a subset Г of 5 with exactly n members. Here, for-all precedes there-exists, so we must consider an aibitrary integer n. Now, there-exists gets to pick a subset T, and may use the knowledge of n to do so. For instance, if 5 were the set of integers, there-exists could picJc the subset T = {1,2,... ,n} and thereby succeed regardless of n. That is a proof that the sct of mtegers is infinite.

The following statement looks like the definition of infinite. but is incorr-ect because it reverses the order of the quantifiers: there exists a subset T of set S such that for all n, set T has exac;tly n members. Now, given a set S such as the integers, player there-exists can pick any set T; say {1,2,5} is picked. For this choice, player for-ali must show that Г has n members for every possible n. However, for-all cannot do so. For instance, it is false for n - 4, or in fact for any n 3.

In addition, in formal logic one often sees the operator -) in place of if-then. That is, the statement if H then C could appear as Я -* С in some mathematical literature; we shall not use it here.

If-And-Only-If Statements

Sometimes, we find a statement of the form A if and only if S. Other forms of this statement are A iff Б, A is equivalent to Z?, or A exactly when B. This statement is actually two if-then statements: if A then B, and if В then A. We prove A if and oidy if B by proving these two statements:

4fr, short for if and only if, is a non-word that is uml in some mfithonuit.ica! iroatise.; for suctinctnoss.

How Formal Do Proofs Have to Be?

The answer to this question is not easy. The bottom hne regarding proofs is that their purpose is to convince someone, whether it is a grader of your class work or yourself, about the correctness of a strategy you are using in your code. If it is convincing, then it is enough; if it fails to convince the consumer of the proof, then the proof has left out too much.

Part of the uncertainty regarding proofs comes from the different knowledge that the consumer may have. Thus, in Theorem 1.4, we assumed you knew all about arithmetic, and would believe a statement like if у > 1 then > 1. If you were not familiar with arithmetic, we would have to prove that statement by some steps in our deductive proof.

However, there are certain things that are required in proofs, and tmiitting them surely makes the proof inadequate. For instance, any deductive proof that uses statements which are not justified by the given or previous statements, cannot be adequate. When doing a proof of an if and only if statement, we must surely have one proof for the if part and another proof for tlie only-if part. As an additional example, inductive proofs (discussed in Section 1.4) require proofs of the basis and induction piu-ts.

1. The ifpaii: li В then and

2, The only-if part: if .4 then B which is often stated in the equiralent form .4 only if Br

Th(! proofs can be presentcd in either order, bi many theorems, one part is decidedly easier than the other, and it is customary to present the easy direction first a.nd get it out of the way.

In formal logic, one may see the operator or = to denote an if-and-only-if statement. That is, Л = В and A В mean the same us A if and only if B.

When proving an if-and-only-if statement, it is important to remember that yon snust prove both the if and only-if parts. Sometimes, you vrill find it helpful to break an if-and-only-if int() a succession of several equivalences. That is, to prove .4 if and only if B. you might first prove Л if and only if C, and th(;n prove C if and only if B. That method works, as long as you remember that each if-and-only-if sttp must be proved in both directions. Proving any one step in only one of the directions invalidates the entire proof.

The following is an example of a simple if-and-only-if proof. It uses the notations:

1. [x\, the floor of real number x, is the greatest integer equal to or lass than