Saying If-And-Only-If for Sets

As we rnontioned, theorems that state equivalences of expressions about sets are if-and-only-if statements. Thus, Theorem 1.10 could have been stated: an element i is in Я U (S П T) if and only if x is in

{RU S)r\{RuT)

Another common expression of a set-equivalence is with the locution all-and-only. For instance. Theorem 1Л0 could as well have been stated the elements of Я U (S П T) are all and only the elements of

(Яи5)П{ЯиТ)

The Converse

Do not <:onfuse the terms contrapositive and converse. The converse of an if-then statement is the other direction ; that is, the converse of if Я then C is if С then Unlike the contrapositive, which is logically equivalent to the original, the converse is not equivalent to the original statement. In fact, the two parts of an if-and-only-if proof are always some statement and its converse.

Example 1Л1: Recall Theorem 1.3, whose statement was: if x > 4, then 2* > x. The contrapositive of this statement is if not 2 > x then not X > 4. In more colloquial terras, making use of the fact that not a > b is the same as a < b, the contrapositive is if 2 < x then x < 4. □

When we are asked to prove an if-and-only-if theorem, the use of the contrapositive in one of the parts allows us several options. For instance, suppose we want to prove the set equivalence E = F. Instead of proving if x is in JS then X is in F and if x is in F then x is in E we could also put one direction in the contrapositive. One equivalent proof form is:

If ж is in E then x is in F, and if x is not in E then x is not in F.

We could also interchange E and F in the statement above.

1.3.3 Proof by Contradiction

Another way to prove a statement of the form if H then C is to prove the statement

H and not С implies falsehood.

That is, start by assuming both the hypothesis Я and the negation of the conclusion C. Complete the proof by showing that something known to be false follows logically from Я and not C. This form of proof is called proof by contradictton.

Example 1.12: Recall Theorem 1.5, where we proved the if-then statement with hypothesis Я = С/ is an infinite set, 5 is a finite snbset of U, and T is the complement of S with respect to U. The conclusion С was T is infinite. We proceeded to prove this theorem by contradiction. We assumed not C ; that is, we assumed T was finite.

Our proof was to derive a falsehood from Я and not C. We first showed from tlie assumptions that S and T are both finite, that U also must be finite. But since и is stated in the hypothesis Я to be infinite, and a .set cannot be both finite and infinite, we have proved the logical statement false. In logical terms, we have both a proposition p {U is finite) and its negation, not p {U is infinite). We th(!n use the fact that p сшс1 not p is logically equivalent to false. □

To see why proofs by contradiction are logit:aIlj- correct, recall from Section 1.3.2 that there arc four combinations of truth values for Я and C. Only the second case, Я true and С false, makes the statement if Я then C false. By showing that Я and not С leads to falsehood, we are showing that case 2 cannot occur. Thus, the only possible combinations of truth values for Я and С are the three combinations that make if Я then C true.

1.3.4 Counterexamples

111 real life, we are not told to prove a theorem, Ratluir, we are faced with something that seems true a strategy for implementing a program for example - -and we need to decide whether or not the theorem is true. To resolve the question, we may alternately try to prove the theorem, and if we cannot, try to prove that its statement is false.

Theorems generally are statements about an infinite number of cases, perhaps all values of its parameters. Indeed, strict mathematical convention will only dignify a statement with the title theorem if it has an infinite number of cases; statements that have no parameters, or that apply to only a finite number of values of its pararaeter(s) are called observations. It is sufficient to show that an alleged theorem is false in any one case in order to show it is not a theorem. The situation is analogous to programs, since a program is generally considered to have a bug if it fails to operate correctly for even <jne input on which it was expected to work.

It often is easier to prove that a statement is not a tJieorem than to prove it is a theorem. As we mentioned, if S is any statement, then the statement 5 is not a theorem is itself a statement лvithout parameters, and thus can

In the process of finding the counterexample, we have in fact discovered the exact conditions under which the alleged theorem holds. Here is the correct version of the theorem, and its proof.

Theorem 1.15: a mod b = b mod a if and only if a = ii.

1)0 regarded as an observation rather than a theorem. The following are two examples, first of an obvious nontheorein, and the second a statement that just misses being a tfieorem and that requires some hivestigation before resolving the question of whether it is a theorem or not.

Alleged Theorem 1.13: All primes are odd. (More formally, we might say: if integer i is a prime, then x is odd.)

DISPROOF: The integer 2 is a prime, but 2 is even. □

Now, let us discuss a theorem involving modular arithmetic. There is an essential definition that we must first establish. If о and b are positive integers, then Й mod &is the remainder when a is divided by b, that is, the unique integer r between 0 and Ь - 1 such that a = 6 + г for some integer q. For example, 8 mod 3 - 2, and 9 mod 3 = 0. Our first proposed theorem, which we shall determine to be false, is:

Alleged Theorem 1.14: There is no pair of integers о and b such that

a mod b = b mod о

□

When asked to do things with pairs of objects, such as a and b here, it is often possible to simplify the relationship between the two by taking advantage of symmetry. In this case, we can focus on the case where a < b, since if Ь < a we can swap a and b and get the same equation as in Alleged Theorem 1.14. we must be careful, however, not to forget the third case, where a - b. This case turns out to be fatal to our proof attempts.

Let us a-ssume a < b. Then a mod b = a, since in the definition of о mod b we have = 0 and г = a. That is, when a < 6 we have a = 0 x b + a. But b mod a < a, since anything mod a is between 0 and a - 1. Thus, when a <b, b mod a < a mod b, so a mod b = b mod a is impossible. Using the argument of symmetry above, we also know that a mod bb mod о when b < a.

However, consider the third case: a = ft. Since x mod x = 0 for any integer X, we do have о mod b = b mod о if a = ft. We thus have a disproof of the alleged theorem:

DISPROOF: (of Alleged Theorem 1.14) Let о = Ь = 2. Then

a mod ft = 6 mod a = 0