Write Your Own Proofs. Amy Babich

established is that subsets of known sets really are sets. With set builder notation, we define new sets as subsets of known sets. Thus we are assured that the new set we are defining really is a set.

      For the same reason, we like to be sure that all the sets in any particular discussion are subsets of some set X, which may be called a universe of discourse for the discussion. For example, the set of real numbers is a universe of discourse for first-semester calculus, and the set of integers is a universe of discourse for much of number theory. For any particular problem, a universe of discourse is a set X such that all sets involved in the problem are subsets of X.

      Definitions. Let X be a universe of discourse and let A and B be subsets of X.

      (i) The intersection of A and B, denoted by A ∩ B. is the set {x ∈ X | x ∈ A and x ∈ B}.

      (ii) The union of A and B, denoted by A ∪ B. is the set {x ∈ X | x ∈ A or x ∈ B}.

      (iii) The relative complement of B in A, denoted by A – B, is the set {x ∈ X | x ∈ A and x ∉ B}.

      Convention. Let X be an acknowledged universe of discourse, and let A be a subset of X . The relative complement of A in X is often simply called the complement of A and denoted by AC.

      Example (2.2) Let X = {1, 3, 5, 7, 9}. Let A = {1, 3, 5}. Let B = {5, 9}. Then A ∩ B = {5}, A ∪ B = {1, 3, 5, 9}, A – B = {1, 3}, B – A = {9}, AC = {7, 9}, and BC = {1, 3, 7}.

       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