Write Your Own Proofs. Amy BabichЧитать онлайн книгу.

       Figure 2.3

      Definition. Let A and B be sets. The sets A and B are equal if A ⊆ B and B ⊆ A.

      We are now ready to begin proving theorems about sets. Our first proof is an example of a proof by contradiction, or indirect proof.

      Theorem (2.1) For every set A, Ø ⊆ A.

      Proof. By way of contradiction, suppose that there exists a set A such that Ø A. Since Ø A, there exists x ∈ Ø such that x ∉ A. But Ø has no elements, so x ∉ Ø. Hence x ∈ Ø and x ∉ Ø. ⟶⟵

      Our hypothesis has led to a contradiction and is therefore false. Thus for every set A, Ø ⊆ A. Q.E.D.

      Remarks. We begin our final draft by writing down the word Theorem, followed by a period or colon. Then we write the statement of the theorem. On the next line, we write Proof, followed by a period or colon. Now we are ready to write the proof.

      To write a proof by contradiction, we begin by assuming that the proposition we wish to prove is false. Then we argue logically until we reach a contradiction, a statement that must be false. (For example, x ∈ Ø and x ∉ Ø.) The symbol ⟶⟵ means that we have arrived at a contradiction.

      The proposition (¬p ⟶ c) ⟶ p is a tautology. To write an indirect proof, we assume ¬p and show that ¬p ⟶ c, where c is a contradiction. This proves the proposition p.

      The letters Q.E.D. stand for quod erat demonstrandum. This is Latin, and means “which was to be proved,” or, more colloquially, “which is what we set out to prove in the first place.” In Latin, quod erat demonstrandum may stand alone as a sentence meaning “This is what was to be proved.” It means that the proof is finished.

      The beginning of a proof by contradiction is important. We write, “By way of contradiction, suppose . . . ” and then write the negation of the proposition we are trying to prove. We are trying to prove: For every set A, Ø ⊆ A. The negation of this proposition is: There exists a set A such that Ø A. Thus we begin by writing: “By way of contradiction, suppose that there exists a set A such that Ø A.”

      We have introduced a set A such that Ø A. We now use the definition of “subset.” Recall that (Ø A) ⟷ (∃x ∈ Ø)(x ∉ A). We write, “Since Ø A, there exists x ∈ Ø such that x ∉ A.”

      We have now introduced an x which is an element of the empty set. But this cannot be. The empty set has no elements. We have reached a contradiction.

      The proposition p that we wish to prove states that for every set A, the empty set Ø is a subset of A. We began: “By way of contradiction, suppose ¬p.” Thus ¬p is our hypothesis. We have shown that ¬p implies a contradiction. This proves that p is true.

      Proofs by contradiction are like jokes. We assume something untrue and argue logically until we reach a conclusion we recognize as ridiculous. Sometimes the conclusion is quite startling.

      We now present another proof by contradiction. This time, the statement of the theorem is of the form p