Proofs and Concepts the fundamentals of abstract mathematics by Dave Witte Morris and Joy Morris University of Lethbridge incorporating material by P.D. Magnus University at Albany, State University of New York Preliminary Version 0.92 of December 2016 This book is offered under a Creative Commons license. (Attribution-NonCommercial-ShareAlike 2.0) The presentation of Logic in this textbook is adapted from forallx An Introduction to Formal Logic P.D. Magnus University at Albany, State University of New York The most recent version of forallx is available on-line at http://www.fecundity.com/logic We thank Professor Magnus for making forallx freely available, and for authorizing derivative works such as this one. He was not involved in the preparation of this manuscript, so he is not responsible for any errors or other shortcomings. Please send comments and corrections to: [email protected] or [email protected] ⃝c 2006{2016 by Dave Witte Morris and Joy Morris. Some rights reserved. Portions ⃝c 2005{2006 by P.D.Magnus. Some rights reserved. Brief excerpts are quoted (with attribution) from copyrighted works of various authors. You are free to copy this book, to distribute it, to display it, and to make derivative works, under the following conditions: (1) Attribution. You must give the original author credit. (2) Noncommercial. You may not use this work for commercial purposes. (3) Share Alike. If you alter, transform, or build upon this work, you may distribute the resulting work only under a license identical to this one. | For any reuse or distribution, you must make clear to others the license terms of this work. Any of these conditionscanbewaivedifyougetpermissionfromthecopyrightholder. Yourfairuseandotherrights are in no way affected by the above. | This is a human-readable summary of the full license, which is available on-line at http://creativecommons.org/licenses/by-nc-sa/2.0/legalcode Preface Unlike in earlier courses, success in advanced undergraduate mathematics classes (and beyond) does not depend nearly so much on being able to (cid:12)nd the right answer to a question as it does on being able to provide a convincing explanation that the answer is correct. (Mathematicians call this explanation a proof.) This textbook is designed to help students acquire this essential skill, by developing a working knowledge of: 1)proof techniques (and their basis in Logic), and 2)fundamental concepts of abstract mathematics. We start with the language of Propositional Logic, where the rules for proofs are very straightforward. Adding sets and quanti(cid:12)ers to this yields First-Order Logic, which is the language of modern mathematics. Being able to do proofs in this setting is the main skill necessary for success in advanced mathematics. It is also important to be familiar with (and be able to prove statements about) sets and functions, which are the building blocks of modern mathematics. In addition, a chapter on Cardinality provides an introduction to the surprising notion of \uncountable sets": in(cid:12)nite sets with so many elements that it is impossible to make a list x ;x ;x ;::: of all of them (even 1 2 3 if the list is allowed to be in(cid:12)nitely long). to Harmony Contents Part I. Introduction to Logic and Proofs Chapter 1. Propositional Logic 3 x1.1. Assertions, deductions, and validity ............................................3 x1.2. Logic puzzles ---------------------------------------------------------- 6 x1.3. Using letters to symbolize assertions ...........................................7 x1.4. Connectives (:, &, _, ), ,) -------------------------------------------- 8 x1.5. Determining whether an assertion is true .....................................18 x1.6. Tautologies and contradictions ------------------------------------------ 19 x1.7. Logical equivalence ...........................................................21 x1.8. Converse and contrapositive -------------------------------------------- 24 x1.9. Some valid deductions ........................................................25 Summary ------------------------------------------------------------ 28 Chapter 2. Two-Column Proofs 29 x2.1. First example of a two-column proof ..........................................29 x2.2. Hypotheses and theorems in two-column proofs --------------------------- 31 x2.3. Subproofs for )-introduction .................................................35 x2.4. Proof by contradiction ------------------------------------------------- 41 x2.5. Proof strategies ..............................................................45 x2.6. What is a proof? ------------------------------------------------------ 47 x2.7. Counterexamples .............................................................49 Summary ------------------------------------------------------------ 51 Part II. Sets and First-Order Logic Chapter 3. Sets 55 x3.1. Propositional Logic is not enough.............................................55 x3.2. Sets, subsets, and predicates -------------------------------------------- 56 x3.3. Operations on sets............................................................65 Summary ------------------------------------------------------------ 71 Chapter 4. First-Order Logic 73 x4.1. Quanti(cid:12)ers ...................................................................73 x4.2. Translating to First-Order Logic ---------------------------------------- 74 x4.3. Negations ....................................................................80 x4.4. The introduction and elimination rules for quanti(cid:12)ers ---------------------- 84 x4.5. Some proofs about sets .......................................................89 x4.6. Counterexamples (reprise)---------------------------------------------- 91 Summary ....................................................................94 i ii Chapter 5. Sample Topics 95 x5.1. Number Theory: divisibility and congruence ..................................95 x5.2. Abstract Algebra: commutative groups --------------------------------- 100 x5.3. Real Analysis: convergent sequences .........................................105 Summary ----------------------------------------------------------- 107 Part III. Other Fundamental Concepts Chapter 6. Functions 111 x6.1. Cartesian product ...........................................................111 x6.2. Informal introduction to functions -------------------------------------- 114 x6.3. Official de(cid:12)nition ............................................................117 x6.4. One-to-one functions ------------------------------------------------- 119 x6.5. Onto functions ..............................................................123 x6.6. Bijections ----------------------------------------------------------- 126 x6.7. Inverse functions ............................................................129 x6.8. Composition of functions ---------------------------------------------- 132 x6.9. Image and pre-image ........................................................135 Summary ----------------------------------------------------------- 138 Chapter 7. Equivalence Relations 139 x7.1. Binary relations .............................................................139 x7.2. De(cid:12)nition and basic properties of equivalence relations -------------------- 141 x7.3. Equivalence classes ..........................................................144 x7.4. Modular arithmetic--------------------------------------------------- 145 x7.5. Functions need to be well-de(cid:12)ned ............................................147 x7.6. Partitions ----------------------------------------------------------- 148 Summary ...................................................................150 Chapter 8. Proof by Induction 151 x8.1. The Principle of Mathematical Induction ....................................151 x8.2. Other proofs by induction --------------------------------------------- 157 x8.3. Other versions of induction ..................................................162 x8.4. The natural numbers are well-ordered----------------------------------- 163 x8.5. Applications in Number Theory .............................................164 Summary ----------------------------------------------------------- 166 Chapter 9. Cardinality 167 x9.1. De(cid:12)nition and basic properties...............................................167 x9.2. The Pigeonhole Principle---------------------------------------------- 171 x9.3. Cardinality of a union .......................................................174 x9.4. Hotel In(cid:12)nity and the cardinality of in(cid:12)nite sets-------------------------- 176 x9.5. Countable sets ..............................................................179 x9.6. Uncountable sets ----------------------------------------------------- 183 Summary ...................................................................186 Index of De(cid:12)nitions 187 List of Notation 189 Part I Introduction to Logic and Proofs Chapter 1 Propositional Logic The grand aim of all science is to cover the greatest number of empirical facts by logical deduction from the smallest number of hypotheses or axioms. Albert Einstein (1879{1955), Nobel prize-winning physicist in Life magazine For our purposes, Logic is the business of deciding whether or not a deduction is valid; that is, deciding whether or not a particular conclusion is a consequence of particular assumptions. (The assumptions can also be called \hypotheses" or \axioms.") 1.1. Assertions, deductions, and validity We will begin our discussion of Logic by introducing three basic ingredients: assertions, deduc- tions, and validity. Here is one possible deduction: Hypotheses: (1)It is raining heavily. (2)If you do not take an umbrella, you will get soaked. Conclusion: You should take an umbrella. (The validity of this particular deduction will be analyzed in Example 1.1.10 below.) In Logic, we are only interested in sentences that can be a hypothesis or conclusion of a deduction. These are called \assertions": DEFINITION 1.1.1.An assertion is a sentence that is either true or false. OTHER TERMINOLOGY.Sometextbooksusetheterm proposition orstatement orsentence, instead of assertion. EXAMPLE 1.1.2. (cid:15)Questions The sentence \Are you sleepy yet?" is not an assertion. Although you might be sleepy or you might be alert, the question itself is neither true nor false. For this reason, questions do not count as assertions in Logic. (cid:15)Imperatives Commands are often phrased as imperatives like \Wake up!," \Sit up straight", and so on. Although it might be good for you to sit up straight or it might not, the command itself is neither true nor false. (cid:15)Exclamations \Ouch!" is sometimes called an exclamatory sentence, but it is neither true nor false. so it is another example of a sentence that is not an assertion. 3 4 1. Propositional Logic Remark 1.1.3.Roughly speaking, an assertion is a statement of fact, such as \The earth is bigger than the moon" or \Edmonton is the capital of Alberta." However, it is important to remember that an assertion may be false, in which case it is a mistake (or perhaps a deliberate lie), such as \There are less than 1,000 automobiles in all of Canada." In many cases, the truth or falsity of an assertion depends on the situation. For example, the assertion \It is raining" is true in certain places at certain times, but is false at others. In this chapter and the next, which are introductory, we will deal mostly with assertions about the real world, where facts are not always clear-cut. (For example, if Alice and Bob are almostthesameheight,itmaybeimpossibletodeterminewhetheritistruethat\Aliceistaller than Bob.") We are taking a mathematical (or scienti(cid:12)c) view toward Logic, not a philosophical one, so we will ignore the imperfections of these real-world assertions, which provide motivation and illustration, because our goal is to learn to use Logic to understand mathematical objects (not real-world objects), where there are no grey areas. Throughout this text, you will (cid:12)nd exercises that review and explore the material that has just been covered. There is no substitute for actually working through some problems, because this course, like most advanced mathematics, is more about a way of thinking than it is about memorizing facts. EXERCISES 1.1.4. Which of the following are \assertions" in the logical sense? 1) England is smaller than China. 2) Greenland is south of Jerusalem. 3) Is New Jersey east of Wisconsin? 4) The atomic number of helium is 2. 5) The atomic number of helium is (cid:25). 6) Take your time. 7) This is the last question. 8) Rihanna was born in Barbados. DEFINITION 1.1.5.A deduction is a series of hypotheses that is followed by a conclusion. (The conclusion and each of the hypotheses must be an assertion.) Ifthehypothesesaretrueandthedeductionisagoodone, thenyouhaveareasontoaccept the conclusion. EXAMPLE 1.1.6.Here are two deductions. Hypotheses: All men are mortal. 1) Socrates is a man. Conclusion: Socrates is mortal. Hypotheses: The Mona Lisa was painted by Leonardo da Vinci. 2) Neil Armstrong was the (cid:12)rst man on the moon. Conclusion: Justin Trudeau went swimming yesterday. The(cid:12)rstofthesedeductionsisveryfamous(andwasdiscussedbytheancientGreekphilosopher Aristotle), but the second one is lame. It may seem odd to even call it a deduction, because the two hypotheses have nothing at all to do with the conclusion, but, given our de(cid:12)nition, it does count as a deduction. However, it is is a very poor one, so it cannot be relied on as evidence that the conclusion is true. We are interested in the deductions that do provide solid evidence for their conclusions: