Write Your Own Proofs. Amy Babich. Читать онлайн. Newlib. NEWLIB.NET

Автор: Amy Babich
Издательство: Ingram
Серия: Dover Books on Mathematics
Жанр произведения: Математика
Год издания: 0
isbn: 9780486843575
Скачать книгу
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 AB. is the set {xX | xA and xB}.

      (ii) The union of A and B, denoted by AB. is the set {xX | xA or xB}.

      (iii) The relative complement of B in A, denoted by A – B, is the set {xX | xA and xB}.

      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 AB = {5}, A ∪ B = {1, 3, 5, 9}, A – B = {1, 3}, B – A = {9}, AC = {7, 9}, and BC = {1, 3, 7}.

image

       Figure 2.3

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

      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 Ø image A. Since Ø image A, there exists x ∈ Ø such that xA. 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 (¬pc) ⟶ p is a tautology. To write an indirect proof, we assume ¬p and show that ¬pc, 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 Ø image A. Thus we begin by writing: “By way of contradiction, suppose that there exists a set A such that Ø image A.”

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

      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

      Конец ознакомительного фрагмента.

      Текст предоставлен ООО «ЛитРес».

      Прочитайте эту книгу целиком, купив полную легальную версию на ЛитРес.

      Безопасно оплатить книгу можно банковской картой Visa, MasterCard, Maestro, со счета мобильного телефона, с платежного терминала, в салоне МТС или Связной, через PayPal, WebMoney, Яндекс.Деньги, QIWI Кошелек, бонусными картами или другим удобным Вам способом.

/9j/4AAQSkZJRgABAQEBLAEsAAD/4gxYSUNDX1BST0ZJTEUAAQEAAAxITGlubwIQAABtbnRyUkdC IFhZWiAHzgACAAkABgAxAABhY3NwTVNGVAAAAABJRUMgc1JHQgAAAAAAAAAAAAAAAAAA9tYAAQAA AADTLUhQICAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABFj cHJ0AAABUAAAADNkZXNjAAABhAAAAGx3dHB0AAAB8AAAABRia3B0AAACBAAAABRyWFlaAAACGAAA ABRnWFlaAAACLAAAABRiWFlaAAACQAAAABRkbW5kAAACVAAAAHBkbWRkAAACxAAAAIh2dWVkAAAD TAAAAIZ2aWV3AAAD1AAAACRsdW1pAAAD+AAAABRtZWFzAAAEDAAAACR0ZWNoAAAEMAAAAAxyVFJD AAAEPAAACAxnVFJDAAAEPAAACAxiVFJDAAAEPAAACAx0ZXh0AAAAAENvcHlyaWdodCAoYykgMTk5 OCBIZXdsZXR0LVBhY2thcmQgQ29tcGFueQAAZGVzYwAAAAAAAAASc1JHQiBJRUM2MTk2Ni0yLjEA AAAAAAAAAAAAABJzUkdCIElFQzYxOTY2LTIuMQAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAWFlaIAAAAAAAAPNRAAEAAAABFsxYWVogAAAAAAAAAAAAAAAA AAAAAFhZWiAAAAAAAABvogAAOPUAAAOQWFlaIAAAAAAAAGKZAAC3hQAAGNpYWVogAAAAAAAAJKAA AA+EAAC2z2Rlc2MAAAAAAAAAFklFQyBodHRwOi8vd3d3LmllYy5jaAAAAAAAAAAAAAAAFklFQyBo dHRwOi8vd3d3LmllYy5jaAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAABkZXNjAAAAAAAAAC5JRUMgNjE5NjYtMi4xIERlZ