An Introduction To Abstract Mathematics Bond Keane Pdf

• 9,281,071 books books
• 84,837,646 articles articles
• ZLibrary Home
• Home

Main An Introduction to Abstract Mathematics

An Introduction to Abstract Mathematics

Robert J. Bond, William J. Keane

How much do you like this book?

What's the quality of the file?

Download the book for quality assessment

What's the quality of the downloaded files?

Bond and Keane explicate the elements of logical, mathematical argument to elucidate the meaning and importance of mathematical rigor. With definitions of concepts at their disposal, students learn the rules of logical inference, read and understand proofs of theorems, and write their own proofs--all while becoming familiar with the grammar of mathematics and its style. In addition, they will develop an appreciation of the different methods of proof (contradiction, induction), the value of a proof, and the beauty of an elegant argument. The authors emphasize that mathematics is an ongoing, vibrant discipline--its long, fascinating history continually intersects with territory still uncharted and questions still in need of answers. The authors' extensive background in teaching mathematics shines through in this balanced, explicit, and engaging text, designed as a primer for higher-level mathematics courses. They elegantly demonstrate process and application and recognize the byproducts of both the achievements and the missteps of past thinkers. Chapters 1-5 introduce the fundamentals of abstract mathematics and chapters 6-8 apply the ideas and techniques, placing the earlier material in a real context. Readers' interest is continually piqued by the use of clear explanations, practical examples, discussion and discovery exercises, and historical comments.

Publisher:

Waveland Pr Inc

The file will be sent to your email address. It may take up to 1-5 minutes before you receive it.

The file will be sent to your Kindle account. It may takes up to 1-5 minutes before you received it.

Please note: you need to verify every book you want to send to your Kindle. Check your mailbox for the verification email from Amazon Kindle.

You may be interested in Powered by Rec2Me

Most frequently terms

                An Introduction to Abstract Mathematics  An Introduction to Abstract Mathematics Robert  J. Bond  Boston College  William  J. Keane  Boston College  WAVElAND  PRESS, INC. Long Grove, Illinois  For information about this book, contact: Waveland Press, Inc. 4180 IL Route 83, Suite 101 Long Grove, IL 60047-9580 (847) 634-0081 info@waveland.com www .waveland.com  Copyright © 1999 by Robert  J.  Bond and W illiam  J.  Keane  Reissued 2007 by Waveland Press, Inc. lO-digit ISBN 1-57766-539-2 13-digit ISBN 978-1-57766-539-7  All rights reserved. No part of this book may be reproduced, stored in a retrieval system, or  transmitted in any form or by any means without permission in writing from the publisher. Printed in the United States of America 7  6  5  4  3  To Ann and Sarah, for their love and constant support for what at times seemed an endless journey. To Liz and Matt, for the first time, and to France, always.  CONTENTS  Mathematical Reasoning  2  1  4  1.1  Statements  1.2  Compound Statements  2  1.3  Implications  1.4  Contrapositive and Converse  16  29 38  49  Sets 2.1  Sets and Subsets  2.2  Combining Sets  2.3  Collections of Sets  49 61 72  81  Functions 3.1  Definition and Basic Properties  3.2  Surjective and Injective Functions  81  3.3  Composition and Invertible Functions  97  Binary Operations and Relations 4.1  Binary Operations  4.2  Equivalence Relations  110  123  123 139  vii  CONTENTS  viii  5  Axioms and Basic Properties Induction  5.3  The Division Algorithm and Greatest Common  5.4  Primes and Unique Factorization  5.5  Congruences  5.6  Generalizing a Theorem  159 175  8  1 82  189 200  209  I nfinite Sets 6.1  Countable Sets  210  6.2  Uncountable Sets, Cantor's Theorem, and the  6.3  Collections of Sets  Schroeder-Bernstein Theorem  7  151  5.1 5.2  Divisors  6  151  The Integers  220  229  235  The Real and Compl ex Numbers 7.1  Fields  7.2  The Real Numbers  235  7.3  The Complex Numbers  243 251  Pol ynomial s  263  8.1  Polynomials  8.2  Unique Factorization  263  8.3  Po; lynomials over C, R, and  273  Q  285  Answers and Hints to Selected Exercises Bibliography Index  319  317  295  PREFACE FOR THE INSTRUCTOR  This book evolved from a course that has been taught at Boston College for many years in many different forms. The course, taken primarily by sophomore mathematics majors, has always been intended to prepare those students for the "abstract mathematics" of the title, for the rigor, careful argument, and logical precision that, although merely glimpsed in calculus, would be linchpins of all further study. Most students will have had two or three semesters of calculus and a semester of linear algebra so that they will have attained a reasonable degree of mathematical sophistication before starting this book. Our choice of topics is motivated by the fact that students take introduc­ tory courses in abstract algebra and real analysis in their junior or senior years as mathematics majors. In order to be able to handle these courses effectively, they need to know the rules of logic and the rudiments of set theory as well as some basic properties of functions between sets: injective and surjective functions, image and inverse image, and invertible functions. The book divides naturally into two (overlapping, to be sure) parts. • Chapters 1-5 introduce the fundamentals of abstract mathematics. Logic, set theory, relations, functions, and operations lead to a careful study of one axiom system, the integers. These chapters form the core of the book. We always cover this material in our course, and we use it to introduce our students to the language of mathematics and to prepare them for their undergraduate careers in mathematics. • Chapters 6-8 apply the ideas and techniques of the earlier material. These chapters for the most part are independent, and we choose which ones to cover as time permits and interests lead. The topics, though, are ones that we feel our students should know, will not find completely alien,  ix  x  PREFACE FOR THE INSTRUCTOR  and will stand them in good stead later: infinite sets and cardinality; the properties of the real and complex numbers; and the important properties of polynomials over those fields, such as unique factorization. Each section contains a wealth of examples and exercises. For the most part, especially in the early chapters, these concern familiar properties of the integers as well as some concepts from calculus, such as continuity and differentiability. (We do not define these latter topics rigorously, for they belong more properly in a course in real analysis.) A major goal of the text is for students to write mathematical proofs coherently and correctly, so we reinforce the logic developed in Chapter 1 throughout the book. In many exercises students must negate a statement or write a converse or a contrapos­ itive. Some of the exercises build on the examples in the section, while others are a bit more challenging. We often leave some details of a proof as exercises, but only if, by then, students should find them routine. We think it is essential that instructors encourage (require?) students to fill in these gaps. We have also included some "Discussion and Discovery Exercises" that are designed to have the students think a bit more deeply about what they have learned. In some of these exercises, they may propose a conjecture and then try to prove it or they may criticize a given proof for logical fallacies or lack of clarity. At the end of each section we have included "Historical Comments" or a "Mathematical Perspective," which attempt to put some of the subject matter in a wider historical and mathematical context. We do not mean them merely as supplemental biographies but intend them to give students some sense of the kinds of problems mathematicians have struggled with over the centuries, from the time of Euclid to the present day. The topics in these commentaries are the authors' personal choices, not meant to represent what every math major should know, but rather to be samples of some interesting material that can stimulate further study. Students can consult the list of references at the end of the book if they wish to learn more. Chapter 1 introduces the rules of logic that students need to know in order to understand written proofs and to write their own. This means that we discuss nuts and bolts: statements, propositions, quantifiers, rules of inference, and the like. Since this book is not designed for a full-fledged course in mathematical logic, we strive not to be too technical, while main­ taining an appropriate level of rigor. The goal from the beginning is for students to write mathematics with the proper style and notation and with the correct "grammar" and connecting phrases, so that the end product is lucid, logical, and mathematically correct. Chapter 2 presents the rudiments of set theory: subsets, complements, union, and intersection, as well as infinite families of sets and partitions. An important goal of this chapter, in addition to a familiarity with the language of sets, is for students to learn how to prove (or disprove) that two sets are equal. Our experience tells us that students often have difficulty just begin­ ning such a proof, so we provide many examples and exercises of this type.  PREFACE FOR THE INSTRUCTOR  xi  (You will find such examples and exercises not only in this chapter, but also as they appear in context in other chapters.) If Chapter 6 is not covered, the instructor can omit Section 2.3 on infinite families of sets. Chapter 3 begins the study of functions as mappings between sets. We use the more informal definition of function as a rule rather than as a set of ordered pairs because it is an approach students are familiar with, involves no significant loss of rigor, and is the way functions actually are used. We discuss the notions of injective, surjective, and invertible functions thoroughly since they are basic to any understanding of abstract algebra. We give exam­ ples involving image and inverse image since they are part of the language of analysis. We show how the tools of calculus (the Intermediate Value Theorem, for example) can be used to prove whether or not a function is invertible; we invite students to review some of the concepts from their calculus courses. We also want students to think in terms of sets of functions, so that binary operations on these sets will not seem so strange when we introduce them. Chapter 4 presents binary operations and relations, two relatively inde­ pendent topics that are prerequisites for any abstract algebra course and for Chapter 5. Some of the exercises in Chapter 4 are similar to problems students do in a beginning abstract or linear algebra course, problems that are fairly routine but can be difficult for some students when seen for the first time. For example, a standard problem in group theory is to show that the intersec­ tion of two subgroups of a group is itself a subgroup. This problem involves a special case of a problem in Section 4. 1; namely, to prove that if two subsets of a set with a binary operation are closed with respect to that operation, then their intersection is closed. As an optional topic at the end of the chapter, we use equivalence relations to give a formal construction of the rational numbers from the integers. In Chapter 5, we bring together many of the ideas of previous chapters in the context of the set of integers. We begin with an axiomatic approach so that students can appreciate the distinctions among definitions, axioms, and theorems. We introduce mathematical induction in Section 5.2 as a consequence of the Well-Ordering Principle which is taken as an axiom. We prove the Unique Factorization Theorem in Section 5.4 via the standard approach of introducing greatest common divisors and properties of primes. Section 5.5 discusses congruences in some detail, defines the set Zn of congru­ ence classes of integers mod n, and proves its algebraic properties. Section 5.6 gives the students an example of how mathematicians extend results: by trying special cases and then conjecturing suitable generalizations. The mathematics in this section is not difficult but it does give the students some exposure to the creative process. Chapter 6 introduces the theory of infinite sets and discusses countable and uncountable sets and cardinality. The mathematics is admittedly more difficult in this chapter and students should have developed a good mastery of the topics in Chapters 2 and 3. Sections 5.5 and 5.6 are not prerequisite  xii  PREFACE FOR THE INSTRUCTOR  for this chapter. Induction (Section 5.2) needs to have been studied, of course; the Division Algorithm (Section 5.3) is mentioned in the proof of Theorem 6.1.8 and prime factorization (Section 5.4) in the proof of Theorem 6.1.11. (Some alternative proofs of the latter don't use prime factorization.) Chapter 7 introduces ordered fields and compares and contrasts such fields with the integers as developed in Section 5.1. Section 7.2 on the real numbers gives the students some of the flavor of a beginning real analysis course, presenting topics such as the Least Upper Bound Axiom, the Archi­ medean Principle, and the fact that between any two real numbers are infinitely many rational numbers. Preparation for Section 7.2 does not require all of Section 7.1. Section 7.3 is a standard introduction to complex numbers including DeMoivre's Theorem and roots of unity. Except for the definition of field, this section is independent of Sections 7.1 and 7.2. The goal of Chapter 8 is for students to learn some techniques for solving polynomial equations, a topic often neglected. The chapter begins with a study of polynomials over an arbitrary field and the relation between zeros of polynomials and their linear factors. We state and prove unique factoriza­ tion and note analogies with the integers. We then discuss (without proof) the Fundamental Theorem of Algebra and give some methods for finding rational roots of a polynomial with integer coefficients. Unquestionably, we provide too much material for a single semester. The majority of the core, Chapters 1-5, is essential; instructors can choose topics from the later chapters as time permits or can include them in an honors version of the course. But the goal of the entire book is to show our students how mathematicians think as well as some of the fascinating things they think about.  Acknowledgments  This book has been in development for several years and has been used in our transition course for almost as long. In that time, we have had the enormous benefit of our colleagues at BC who have taught from previous versions, contributed comments, suggested problems, and engaged in spir­ ited, frank, and occasionally hilarious conversations. The book would be much different and much less, as would we, without them: Dan Chambers, Rob Gross, Richard Jenson, Peg Kenney, Charlie Landraitis, Harvey Mar­ golis, Rennie Mirollo, Nancy Rallis, Ned Rosen, and John Shanahan. Special thanks are due to Rennie Mirollo for carefully reading the text and pointing out numerous inaccuracies. Any that escaped his diligent analysis are the responsibility of the authors. We thank our independent reviewers, Edward Azoff, The University of Georgia; Gerald Beer, California State University-Los Angeles; Ron Dotzel, University of Missouri-Saint Louis; David Feldman, University of New Hampshire; Sherry Gale, University of North Carolina at Asheville; John  PREFACE FOR THE INSTRUCTOR  xiii  Robertson, Georgia College; Michael Stecher, Texas A & M University­ College Station; and Mark Watkins, Syracuse University. An instructor's manual, consisting of solutions of all of the exercises, is available. Robert Bond William Keane  INTRODUCTION FOR THE STUDENT  This text and others like it are often described as transition books, primers for higher-level mathematics. What do we mean by a transition book and why is such a book necessary? By now, you have seen a significant amount of mathematics, including at least a year or two of calculus and possibly some linear algebra. The mathematics in these courses is quite sophisticated. Calculus, for example, as developed by Newton and Leibniz, is the greatest mathematical achieve­ ment of the seventeenth century. The tremendous scientific advances of the last 300 years would not have been possible without the formulas and algorithms that follow from the theory of the integral and the derivative. Soon, you will take additional courses in such fields as probability, combinato­ rics, dynamical systems, linear programming, or topology, to list just a few examples. Given that calculus involves such high level mathematics, why does a math major need a transition course? Why not just plunge right into these so-called advanced courses? One reason stems from the history of calculus itself. In the seventeenth and eighteenth centuries, mathematicians would manipulate infinite series much like ordinary finite sums. The results were usually quite correct, but the methods often led to errors. Here is an example: The MacLaurin series expansion of In(1 + x ) is given by: In(1+x)=x-  x2 x3 X4 + - +.... "2 "3 "4  This series converges for -1 <  x  (*)  :5 1.Differentiating both sides of (*) gives:  1 __ = 1- x+x2- x3+.... 1+x  xv  xvi  INTRODUCTION FOR THE STUDENT  If we substitute x = 1 in (**), we get 1 2=1 - 1+1-1+. . . . The right-hand side of the equation, however, is not a convergent series. What has gone wrong here is the indiscriminate differentiation of a power series, term by term, as if it were the same as a finite sum. Sometimes this can be done and sometimes it cannot. In fact, (**) is a true equation for all x such that - 1 < x < 1. What becomes important is to prove under what conditions a power series can be differentiated term by term. Another example is provided by letting x = 1 in (*) above, giving the true equation:  Now if we rearrange the terms of the infinite series on the right-hand side, we obtain the equation:  ( (  � �  )-G ) G  In(2) = 1+ + +. . .  � �  = 1+ + +. . . +  � � ...)  + +  � �  ) G  + + ··· -2  � �  + + ···  )  =0. Since we know that In(2) # 0, we have an apparent contradiction. The contradiction is resolved by noting that the right-hand side of (***) is a conditionally convergent series; that is, the series converges but if the terms of the series are replaced by their absolute values then the resulting series diverges. It can be proven that a rearrangement of a conditionally convergent series will not necessarily converge to the same sum as the original series. In fact, a conditionally convergent series can be rearranged to converge to any given number or even to diverge. In both of these examples, mistakes are made by treating an infinite sum the same as a finite sum. In trying to determine which rules that apply to finite sums also apply to finite series, it is necessary first to define carefully what we mean by an infinite series and then prove properties of series using that definition. As each property is verified, it can be used to prove subsequent properties. Mathematicians of earlier centuries commonly manipulated formulas and symbols indiscriminately without regard for whether or not those manipula­ tions were justified. Nevertheless, often these "missteps" actually led to  xvii  INTRODUCTION FOR THE STUDENT  true formulas or provided insights into why something was true. The great mathematician Leonhard Euler (1707-1783) is famous for making discover­ ies in a totally nonrigorous way. Here is an example. You may recall that the infinite series  :f n\ is a convergent series by the  n=1  so-called p-test. But knowing that the series converges does not tell you to  what number the series converges. In fact, this series converges to  2  �.  Euler's "proof" of this fact goes like this: the MacLaurin series expansion of sin x is X  - + +.... 1- + - +.... -±1T, ±21T, ±31T, x  3  x  3!  5  -  5!  x  7  7!  Dividing by x gives the equation: sin x  --  x  x  -  =  If we set  2  sin x  =  x  6  4 X  x  5'.  7'.  -  3'.  0, the roots are:  . . . .  If we treat the infinite series as if it were a polynomial, as Euler did, then we can factor it as  since this infinite product has the same roots and the same constant term as the infinite series. So we get: sin x --  x  1 - +... (1-;)(1 +;)(1- ;1T)(1 + ;1T)(1-;1T)(1 + ;1T) . ( - ;:)( - :;2) ( ;;2) .... x  =  =  =  --  2  3'.  +  1  4 X  5'.  x  6  7'.  1  ..  1-  If we mUltiply out this last infinite product, as we would a finite product, we see that the coefficient of the x 2 term is the infinite series 1  1 1  On the other hand, the  x  2  term of the MacLaurin series is  Multiplying both expressions by -1T2 gives us Euler's result.  - ; - �. !  =  xviii  INTRODUCTION FOR THE STUDENT  We emphasize that Euler was not indifferent to the idea of convergence of an infinite series and, of course, he knew that a power series was not the same as a polynomial. His insight and cleverness produced significant 00 1 1T 2 mathematics. He was later able to give a proof that 2: "2 that is consid­ 6 n=! n ered rigorous by today's standards. One of the important byproducts of finding a rigorous proof of a mathe­ matical theorem is that it can often lead to new results or even to generaliza­ tions of the theorem, generalizations that may be impossible to discover by informal methods such as the ones employed by Euler. =  For example, if you change the exponent in the series  'i n\ from a 2 to  n=!  another integer such as 3, 4 . . and so forth, you may well ask to what numbers these different series converge. There is a long history of attempts to answer this question. .  'i nIs for s a real number greater than 1, so that C(2) is the series we considered above and C(2) � (Note: the First, we define a function C(s)  =  n=!  2  =  .  symbol C is the Greek letter zeta and the function C(s) is known as the Riemann zeta function, named after the mathematician Bernhard Riemann (1826-1866). You may recall the name Riemann from the study of Riemann sums in calculus.) Euler derived a formula for C(s) when s is an even positive integer. The formula involves a power of 1T and the so-called Bernoulli numbers, which we won't define here. No formula for C(s), when s is an odd positive integer, is known. In 1978, the French mathematician R. Apery proved that C(3) is irrational, but not much else is known about these num­ bers. This and countless other examples show that mathematics is not a closed subject. Many unsolved problems and even new areas of mathematics await the budding mathematician. A transition book such as this one, then, is an introduction to the logic and rigor of mathematical thinking and is designed to prepare you for more advanced mathematical subjects. We designed our course and this book with three goals in mind. First and foremost of these is to show you the elements of logical, mathematical argument, to have you understand exactly what mathematical rigor means and to appreciate its importance. You will learn the rules of logical inference, be exposed to definitions of concepts, be asked to read and understand proofs of theorems, and write your own proofs. At the same time, we want you to become familiar with both the grammar of mathematics and its style. We want you to be able to read and construct correct proofs, but also to appreciate different methods of proof (contradiction, induction), the value of a proof, and the beauty of an elegant argument. A second goal is for you to learn how to do mathematics in a context,  INTRODUCTION FOR THE STUDENT  xix  by studying real, interesting mathematics and not just concentrating on form. We have chosen topics that do not overlap significantly with other courses (such as the properties of the integers, the nature of infinite sets, and the complex numbers), that are essentially self-contained, and that will be useful to you later when you are exposed to more specialized, advanced mathe­ matics. Finally, we want you to realize that mathematics is an ongoing enterprise, with a long, fascinating, and sometimes surprising history. The notes sprin­ kled throughout the text are deliberately eclectic. "Historical Comments" give you pictures of the tremendous successes (and equally spectacular fail­ ures) of brilliant mathematicians of the past. "Mathematical Perspectives" may spotlight questions that are still unanswered and are the subject of current research, or that simply show an interesting further aspect of the material you have just studied.  MATHEMATICAL REASONING  1  Introduction: Early Mathematics  Mathematics in one form or another has probably existed in every civilization. Many cultures flourished in the area of the Tigris and Euphrates rivers known as Mesopotamia in what is now Iraq. The Babylonian civilization of that area has left us records of mathematical activity as far back as the years 1 800-1600 B.C Writing on clay tablets, they recorded solutions of algebraic problems and compiled tables of squares, cubes, square roots, and cube roots, even some logarithms. They also listed Pythagorean triples, numbers such as 3, 4, 5 and 5, 12, 13, which make up the sides of a right triangle ( using of course their own symbols and number system ) . So the Babylonians knew the Pythagorean Theorem more than a thousand years before the time of Pythagoras ! Even earlier than the Babylonians, the so-called Middle Kingdom of Egypt (2000-1800 B.C ) produced some sophisticated calculations of areas and volumes. One of their great achievements was the calculation of the volume of a truncated pyramid with square base and square top. ( See Exercise D4 of Section 1 .3.) Beginning in about the sixth century B.C in Greece, an extraordinary new chapter in the history of mathematics began. For the first time ( at least as far as we know ) the methods of reasoning and logical deduction, as opposed to trial and error calculations, were employed to arrive at new mathematical truths. Prior to the Greeks, in Egypt and Babylonia for exam­ ple, geometric results and algebraic formulas were discovered by empirical methods; that is, by trying special cases and then extrapolating to the general case. This empirical method, called inductive reasoning, has been used by mathematicians throughout history. It is not merely a perfectly acceptable method of making new discoveries but is really an indispensable way to arrive at new results. But the Greeks insisted that any new results had to be proved and that meant using the rules of logic. This method is called deductive reasoning. In this chapter we introduce some of the important ideas of logic that are frequently used in mathematics.  2  CHAPTER  1.1  I  MATHEMATICAL REASO N I NG  STATEMENTS The Notion of Proof  Contrary to popular opinion, mathematics is not just computations and equa­ tions. It might be better described as an attempt to determine which state­ ments are true and which are not. The subject matter may vary from numbers to geometric figures to just about anything, but the form is always the same. The process of discovery in mathematics is twofold. First comes the formulation of a mathematical statement or conjecture. This formulation often comes after much hard work that usually includes a trial-and-error process, many false starts, and sometimes extensive calculation. The second part of the process is the verification or proof that the statement that we have formulated is true or false. This part too can involve much trial and error and long, hard work. It is this part of the process that we will study in this text. To begin to prove a mathematical statement it is necessary to begin with certain statements that we accept as given, called axioms, and try to logically deduce other statements from them. These deductions are called proposi­ tions, or, if they're particularly important, theorems. The arguments, the logic we use to make the deductions, are called proofs. The beauty of mathematics often comes from the fact that propositions are not always obvious, and can in fact be surprising. Moreover, proofs may not be easy to construct, and may require insight and cleverness. They certainly require a little experience, especially some familiarity with the most commonly used logical methods. This "sophistication" won't come overnight; it's one of the major goals of this book. Let's begin with an example. EXAM P L E I  Suppose that the following question were posed to you: Is the square of an even integer itself an even integer? You might start by trying some calcula­ tions: 62  =  36,  82  =  64,  102  =  1 00.  Each one of these examples gives a positive answer to the question. Do these answers constitute a proof? If the problem asked us to show that the squares of some even integers are even, we would be done. But that is not the question. There is an implied universality about the question. Is the square of every even integer even? Clearly, more must be done than trying a few examples. In fact just working out examples will not suffice, because no matter how many we do, there will always be an infinite number of cases that we haven't done. So how do we proceed? The first step might be to reword the question as a statement.  1.1  3  STATEMENTS  "The square of every even integer is even. " Now let's reword the statement using symbols: "If n is an integer and n is even, then n2 is even. " In order to begin a proof, we have to ask ourselves: What does it mean for an integer to be even? Well, we know that an integer is even if it is two times an integer. That is the definition of even integer. Now we need to translate this definition into symbols:  "n is an even integer if n  =  2m for some integer m . "  Now let's think about what we're trying t o prove. We want t o show that the square of the even integer n is even. So we start by letting n be an even integer and try to show that n2 is twice an integer. We do the obvious algebra step; we write n = 2m and square both sides. We get n2 = 4m2 = 2(2m2). Since 2m2 is an integer, this shows that n 2 is twice an integer and therefore n2 is even. The proof is now complete. This is an example, admittedly not a complicated one, of the proof of a mathematical statement. Note that in this last example, we made some assumptions about multipli­ cation of integers; namely, that multiplication satisfies a commutative law and an associative law and that the product of integers is still an integer. These laws make up some of the axioms of the integers and will be discussed in Chapter 5. For the purpose of examples in this and later chapters, we will assume the well-known arithmetic properties of the integers and real numbers. (See Section 5 . 1 for properties of the integers and Section 7 . 1 for properties of the real numbers. ) The notion of multiples of an integer is used in some examples. An integer x is called a multiple of an integer n if x = kn for some integer k. So the even integers are the multiples of 2. The multiples of 3 consist of the integers 0, ±3, ±6, ±9, and so on. Statements  In the course of this chapter, we will discuss many of the rules of logic and inference needed in the previous example and others like it in mathematics. In the previous example, we used the word "statement" several times. In this text, the word will have a specific meaning. Definition 1.1.1 A statement is any declarative sentence that is either or false.  true  4  CHAPTER I  MATH EMATICAL REASO NING  A statement then will have a truth value. It is either true or false. It cannot be neither true nor false and it cannot be both true and false. Some examples of statements are given next: EXAM PLE 2  John Fitzgerald Kennedy was the 35th president of the United States.  EXAM P L E 3  Marie Curie did not win the Nobel Prize.  EXAM P L E 4  3 + 1  =  4.  The fourth example is a mathematical statement, which of course is true. We commonly write mathematical statements with symbols for convenience, although you should think of them not as "formulas," but as full-fledged sentences, with a subject, a verb, and possibly other parts of speech. In the rest of this chapter, we examine what mathematical statements can look like and some methods that can be used to prove them. For conve­ nience, we often use letters, most often P or Q, to denote statements. EXAM P L E 5  Some sentences, even some mathematical ones, are not statements. For example, consider a typical sentence from algebra: x + 1 2. Here, x is a variable; it's a symbol that stands for an undetermined number. The sentence is a statement if we specify what number x stands for. It's a true statement if x stands for 1, and it's false for any other x. We could label this sentence P(x) because it depends on the variable x. So P(l ) is a true statement and P(x) is a false statement if x =F l . Note, however, that if x i s not specified, then P(x) i s not a statement. =  We will call any sentence like the one from the previous example an  open sentence. Definition 1.1.2 An open sentence is any declarative sentence  taining one or more variabl es statement when the  variables  that is  are  not a statement  con­  but becomes a  assigned values.  The values that can be assigned to the variables of an open sentence will depend on the context. They may come from the real numbers as in the 2 or from the complex numbers or even just the positive example x + 1 integers. The values do not even have to be mathematical. For example, the sentence "He was the 16th president of the United States" is an open sentence containing the variable "he" and is therefore a true statement when "he" is assigned the value "Abraham Lincoln" and is false otherwise. =  1.1  5  STATEMENTS  An open sentence is usually written P(x), P(x, y), P(x, y, z), and so on, depending on the number of variables used. Quantifiers  An open sentence like x + 1 = 2 can, as we have seen, be made into a statement by substituting a value for the variable or, in the case of an open sentence with more than one variable, by substituting a value for each of the variables. Another way an open sentence can be made into a statement is by 2, we introducing quantifiers. For example, for the open sentence x + 1 could say: For every real number x, x + 1 2. This sentence is now a mathematical statement that happens to be false. The quantifier introduced here is the phrase "for every real number x" and is called a universal quantifier. Another way to modify P(x) is to write: there is a real number x such that x + 1 = 2. Note that this statement is true. The quantifier in this example, "there is a real number x," is called existential. Once a quantifier is applied to a variable, then the variable is called a bound variable. In the example "For every real number x, x + 1 2" of the previous paragraph, then, the variable x is a bound variable. A variable that is not bound is called a free variable. If P(x) is an open sentence, then the statement: "For all x, P(x) " means that for every assigned value a of the variable x, the statement Pea) is true. The statement "For some x, P(x)" means that for some assigned value of the variable x, say x a, the statement Pea) is true. This statement may also be worded: "There exists a value of x such that P(x). " Sometimes, i n a statement containing universal quantifiers, the words "for all" or "for every" are not actually in the sentence but are implied by the meaning of the words. Here are some examples. =  =  =  =  EXAM P L E 6  If  n  is an even integer, then  n  2  is even.  On the surface, this sentence might seem to be an open sentence rather than a statement since it contains the variable n. However, implicit in the wording is the meaning: for every integer n, if n is even, then n 2 is even. So the variable n has been modified by a universal quantifier and is now a bound variable, making the sentence a statement. As we saw in Example 1 , it is actually a true statement. EXAM P L E 7  A triangle has three sides. This statement contains a universal quantifier since it is really asserting that every triangle has three sides. Another way to word this statement is "For every plane figure T, if T is a triangle, then T has three sides," or more simply "If T is a triangle, then T has three sides."  6  CHAPTER I  EXAM PLE 8  MATHEMATI CAL REAS O N ING  The square of a real number is nonnegative. Again this statement has a universal quantifier since it is saying that the square of every real number is nonnegative. It could also be written as: "If x is a real number, then  EXA M P L E 9  x  2  �  0."  All triangles are isosceles. This statement has a universal quantifier as well. It just happens to be false. We will sometimes use the symbol 'r/ to mean "for all" or "for every." Example 8 can be rewritten: "'r/ x , if x is real, then x 2 � 0. " The following examples give some of the forms that a statement with an existential quantifier can take.  EXA M P L E 10  Some even numbers are multiples of 3. First note that even though this statement is written in plural form ( "some even numbers" ) , it may be phrased: "There exists an even integer that is a multiple of 3." To prove this statement, one need only find one even number that is a multiple of 3. Since 6 is such a number, the proof is complete.  EXAM P L E I I  Some real numbers are irrational. This statement asserts something about some, but not all, real numbers. It may be reworded as: "There exists a real number x such that x is irrational." It is a true statement provided that there is at least one real number that is not rational. In Section 1.4, we will prove this statement by showing that v2 is irrational.  EXAM P L E 12  There is a real number whose square is negative. This statement also makes an assertion about some real numbers. Note that it is a false statement. The symbol 3 is used to mean "there exists" or "there is. " The symbol :3 is read "such that." Example 1 1 then can be expressed as: 3 x, x real, :3 x is irrational. A statement of course may have more than one quantifier.  EXAM P L E 13  For every real number  x,  there is an integer  n  such that  n > x.  This statement contains both a universal and an existential quantifier.  1.1  EXAM PLE 1 4  7  STATE M ENTS  The following statement, which is a definition from calculus, also has both a universal and an existential quantifier: A real-valued function f(x) is bounded on the closed interval [a, b] if f(x) is defined on [a, b] and there exists a positive real number M such that If(x) I :s M for all x E [a, b]. For example, the function f(x) x2 + 1 is bounded on [0, 2] because If(x) I :s 5 for all x E [0, 2]. =  The order in which quantifiers appear in a statement is important. If  P(x, y) is an open sentence in the variables x and y, then the statement 't/x, 3y  3  P(x, y)  does not always mean the same as the statement 3y  3  't/x, P(x, y).  To see this, consider the following example. EXA M P L E 15  The statement "Every real number has a cube root" can be written in the form:  't/ real numbers x, 3 a real number y  3  y3  =  X.  This statement is true and is a consequence of the Intermediate Value  Theorem of Calculus. However, the statement 3 a real number y  3  't/ real numbers x, y3  =  X  means that every real number x is the cube of a single number y and is clearly false. Negations  Two of the statements just given, "All triangles are isosceles" and "There is a real number whose square is negative," were noted to be false. To prove that they are false it is necessary to prove that the negations of these statements are true. Definition ;1 �,,3 If P � s�t�m�llttlh� DelJafio� of P, Wtlttilln ...,P (an4· r.ead ':'not P"); is' the state��nt "P iS f�se�'2 .  i,s  .  .  ..  .  .  ..  .. ..  There are several alternative ways to express -,P. For example, "P is not true" and " It is not true that P" are the same as our definition. In addition,  8  CHAPTER I  MATH EMATICAL REASO N I NG  it is often possible to express the negation of a sentence more elegantly by using better English style. Note however that the negation of a statement P must be phrased in such a way that exactly one of the statements P or -,P is true and one is false. Some examples follow: EXAM P L E 16  P: -,P:  John Fitzgerald Kennedy was the 35th president of the United States. John Fitzgerald Kennedy was not the 35th president of the United States.  Notice ( it's obvious ! ) that exactly one of P and -,P is true, the other false. EXA M P L E 17  P: -,P:  Marie Curie did not win the Nobel Prize. Marie Curie won the Nobel Prize.  We really have a double negative here, the negation of a negatively phrased statement, that is better stated positively. EXAM P L E 18  P: -,P:  3 3  + +  1 4. 1 ¥= 4. =  As this example shows, symbolic mathematical statements can often be negated symbolically. We can also talk about the negation of open sentences P(x), P(x, y) , P(x, y, z), . . . in one or more variables. To use the one-variable case as an example, we will write -,P(x) , read "not P(x) ," to mean the open sen­ tence in the variable x that becomes the statement -,P(a) when x is as­ signed the value a. The negation of open sentences with more than one variable is defined in a similar fashion. In writing such sentences, we use whatever form good English or mathematical usage would dictate. EXAM PLE 1 9  EXAM PLE 2 0  EXAM P L E 2 1  1 = 2. 1 ¥= 2.  P(x) : -,P(x) :  x x  P(x): -,P(x):  x> 5. x:::; 5.  pen, m ) : -,P(n, m) :  + +  n n  + +  m is even. m is odd.  In the next example, we consider the negation of a statement with a universal quantifier.  1.1  EXAM PLE 2 2  9  STATEMENTS  P: -,P:  If n is an even integer, then n 2 is even. It is not true that if n is an even integer, then  n  2  is even.  Every statement can be negated by simply putting the phrase "it is not true that" in front of it. Usually, though, expressing the negation this way does not convey what the negated statement actually means. In this example, P contains the universally quantified variable n and can be written: For all integers  n,  if n is even, then  n  2  is even.  Therefore, P is false if there is some even integer whose square is not even. So -,P must be the statement For some even integer n, n 2 is not even or There exists an even integer n such that n2 is odd. Note that in negating P, the universal quantifier is replaced by an existen­ tial quantifier. EXAMPLE 2 3  P:  Every day this week was hot.  The negation of this statement is not "Every day this week was not hot," since these two statements do not cover all possibilities. There can be a week in which some days are hot and some are not. To negate P, it is sufficient that there be at least one day that is not hot. So we can write the negation as: Some day this week was not hot or There was a day this week that was not hot. EXAM P L E 2 4  P: -,P:  Every polynomial function is continuous everywhere. There exists a polynomial function that is not continuous some­ where.  There are really two universal quantifiers in statement P. It says that all polynomial functions are continuous at all real numbers. So the negation should say that some polynomial functions are not continuous at some real numbers. EXAM PLE 25  The negation of the statement "All Red Sox players are slow" is "There is a Red Sox player who is not slow," or equivalently, "Not all Red Sox players are slow. " An incorrect way to negate this statement is "All Red Sox players are not slow. " We make no comment about which of these statements is true. If we negate a statement with an existential quantifier, then a universal quantifier is required.  10  CHAPTER I  There is a real number whose square is negative.  P:  EXA M P L E 26  MATH E M ATICAL REASONING  Statement P says that we can find a real number whose square is negative. The negation of P means that we cannot find such a number. In other words, the negation of P is The square of every real number is not negative. To negate P by saying "There is a real number whose square is nonnega­ tive" would not be correct because this statement and P could, theoretically at least, both be true. P:  EXA M P L E 27  Some real-valued functions are not integrable.  -, P:  Every real-valued function is integrable.  As Examples  22-27  show, there are thus two basic rules about negating  statements with quantifiers.  Rule 1:  The negation of the statement "For all x, P(x)" is the statement  "For some x, -, P( x)."  Rule 2:  The negation of the statement "For some x, P(x)" is the state­  ment "For all x, -, P(x)."  Of course, if a statement contains both universal and existential quantifi­ ers, then in order to negate the statement, it is necessary to apply both of these rules. If a statement S has the form "For all x, 3y 3 P(x, y)" then the negation of  S  is "For some x, -,( 3y 3 P(x, y»" by Rule  1.  Since Rule  2  tells us that  the negation of " 3y 3 P(x, y)" is "For all y, -,(P(x, y»," then the negation of Sbecomes "For some x, for ally, -,(P(x,y»" or " 3x 3 for ally, -,( P(x,y». " Similarly, the negation o f " 3x 3 V y , P(x, y)" i s "Vx, 3y 3 -,(P(x, y»." EXA M P L E 28  P: -, P:  For every real number x, there is an integer n such that n > x. There is a real number x such that for every integer n, n � x.  The statement in this last example is known as the Archimedean Principle. See the Historical Comments at the end of Section EXAM P L E 29  1 .2.  P:  There is a continuous real-valued function f(x) such that f(x) is  -, P:  For every continuous real-valued function [(x), there is a real  not differentiable at any real number number  c  c.  such that [(x) is differentiable at  c.  1.1  II  STAT E M E N TS  Surprisingly, statement  P  of Example  29  is true. There are continuous  functions that are not differentiable at any point! An example, due to  K.  Weierstrass, is  f(x)  =  �'" 21n cos (( 1 5 ) n  1TX) .  This is a function that is continuous everywhere but differentiable nowhere.  Writing Proofs As you start to read and write proofs, you will see that they require a certain writing style to ensure clarity and readability. Take, for example, the proof in Example  1,  that if  n  is an even integer, then  n2  is even. Suppose that a  proof were written as follows:  n = even = 2t. n2 4t2 = even. =  This rather brief proof has the correct mathematical steps, but is lacking in explanation and hence in clarity and also suffers from poor notation. One should begin by clearly stating the assumption: "Let suppose that  n  n  be an integer and  is even." Then it can be noted that this means that  for some integer  t. "  But writing  "n  "n= 2t  = even" is sloppy notation. The word  "even" is an adjective and should precede a noun; in this case, the word "number." But even the expression  "n  =  even number" is not appropriate.  The phrase "even number" does not belong in an equation. Equations should only contain numbers and symbols. After writing  "n  =  2t for some integer t"  an explanation should be given  for the next step: "Squaring both sides, we get  n2  =  4t2  =  2(2t2) . "  Then  finally, one should note that "since 2t2 is an integer, it follows that n2 is even."  .1'  HISTORICAL COMMENTS: EARLY GREEK MATHEMATICS  A history of early Greek mathematics was written by Eudemus in the fourth century B.C. Although this book is now lost, a summary of it was written by Proclus in the fifth century  A.D.  According to Proclus's work, the earliest  known mathematician to use the deductive method was Thales of Miletus. Thales founded the earliest Greek school of mathematics and philosophy. Among the results attributed to Thales are: the base angles of an isosceles triangle are congruent; triangles with corresponding angles equal have pro­ portional sides; and an angle inscribed in a semicircle is a right angle. Each of these results was proven by deductive methods. About sixty to eighty years after Thales, an important school of mathe­ matics and philosophy was founded in southern Italy by Pythagoras (ca.  585-497  B.C. ) . One of the great contributions of the Pythagoreans, as the  12  CHAPTER I  MATHEMATICAL REASONING  members of this school were known, is the idea that mathematical entities such as numbers and geometrical figures are in fact abstractions distinct from the material world. To the Pythagoreans the concept of number was the key to understanding the mysteries of the universe. By numbers they always meant whole numbers. Although they worked with ratios of whole numbers, which we call fractions, they did not consider them numbers per se. The Pythagoreans are credited with discovering the Pythagorean Theorem but probably did not give a formal proof of it. And as the records left behind by the Babylonians indicate, the Pythagoreans were not the first to use it. Exercises 1.1  1. Determine whether each of the following sentences is a statement, an open sentence, or neither. ( a) The Boston Celtics have won 16 NBA championships. (b ) The plane is leaving in five minutes. ( c) Get a note from your doctor. ( d) Is that the best you can do? ( e) Excessive exposure to the sun may cause skin cancer. ( f) 5 + 2 6. ( g) Someone in this room is the murderer. ( h) x2 + 1 � o. ( i) For every real number x, x 2 + 1 � o. (j) The equation of a circle of radius 1 with center at the origin is x2 + y2 1. ( k) If nand m are even integers, then nm is even. =  =  2. For each of the following statements, determine if it has any universal or existential quantifiers. If it has universal quantifiers, rewrite it in the form "for all . . . . " If it has existential quantifiers, rewrite it in the form, "there exists . . . such that . . . . " Introduce variables where appropriate. ( a) The area of a rectangle is its length times its width. ( b) A triangle may be equilateral. ( c ) 8 8 o. ( d) The sum of an even integer and an odd integer is even. ( e) For every even integer, there is an odd integer such that the sum of the two is odd. ( f ) A function that is continuous on the closed interval [a, b] is integrable on [a, b]. ( g) A function is continuous on [a, b] whenever it is differentiable on [a, b]. ( h) A real-valued function that is continuous at 0 is not necessarily differentiable at O. ( i ) All positive real numbers have a square root. (j) 1 is the smallest positive integer. -  =  1.1  3.  4.  13  STATEM ENTS  Write the negation of each statement in Exercise  2.  Write the negation o f each o f the following statements. (a) All triangles are isosceles. (b) Some even numbers are multiples of three. (c) Every door in the building was locked. (d) All new cars have something wrong with them. (e) Some angles of a triangle are greater than  90  degrees.  (f) There are sets that contain infinitely many elements.  5.  Write the negation of each of the following statements. (a) There is a real number x such that x2 + x + (b) Every real number is less than  1  =  o.  1 00.  (c) If f is a polynomial function, then f is continuous at  O.  (d) If f is a polynomial function, then f is continuous everywhere. (e) V x, x real, 3 a real number y 3 Y = x3• ( f) There is a real-valued function f(x) such that f(x) is not continuous at any real number x.  6.  Consider the following statement divisible by  P:  " The square of an even integer is  4."  P a s a statement i n the form, " for all ... , i f ... , then ... ." P. Prove P or .. P. Explain any inductive reasoning you use to conjec­ ture that P is true or that P is false.  (a) Write  (b) Write the negation of (c)  7.  Consider the following statement divisible by (a) Write  P  P:  " The sum of two even integers is  4." as a statement i n the form " for all . .. , i f ... , then ... ."  P. P or ..P. Explain any inductive reasoning you use to conjec­ that P is true or that P is false.  (b) Write the negation of (c) Prove ture  8.  In Example  14  the definition of a bounded function was given.  (a) Write the negation of this definition; that is, complete the following statement: " A real-valued function f(x) is interval  [a, b] if  not bounded on the closed  . .. ."  (b) Give an example of a bounded function on  [0, 1]. Justify your answer  by determining a value for M. (c) Give an example of an unbounded function on  [0,  1]. Justify your  answer. (d) Suppose the definition of bounded function were worded this way:  bounded on the closed [a, b], there exists a positive real number  " A real-valued function f(x) is said to be interval  [a, b] if for all x  M such that i f(x)i  ::s  E  M." Does this definition mean the same as the  one given in Example 14? If not, explain how they differ. Could this new definition make sense as the definition of a bounded func­ tion? Explain.  14  CHAPTER I  9.  MATH EMATI CAL REASON I N G  A real-valued function f(x) is said to be increasing on the closed interval  [a, b] if for all Xl, X2 E [a, b], if Xl < X2 , then f(XI) < f(X2)' (a) Write the negation of this definition. (b) Give an example of an increasing function on  [0, 1].  [0, 1]. State a definition for a real-valued function f(x) to be decreasing on a closed interval [a, b].  (c) Give an example of a function that is not increasing on  10.  (a)  (b) Give the negation of this definition. (c) Give an example of a decreasing function on  [0, 1]  (d) Give an example of a function on  [0, 1].  that is neither increasing  nor decreasing.  11.  Prove the following corollary of the Archimedean Principle.( See Example  28 for the statement.)For every positive real number e, there exists a posi­ tive integer  N such that lin  <  e  for all  n  2::  N. (Note: this exercise is the i, i, . . } converges to 0.)  basis for the formal proof that the sequence {1, !,  .  12 . Use the Archimedean Principle t o prove the following: i f X i s a real number, then there exists a positive integer  13.  n  such that  -n  < X <  n.  Prove that i f X i s a positive real number, then there exists a positive integer  n  such that  1:. < X n  n.  <  D is c u s sion a n d Disc overy E xercises  D 1.  Consider the following question. What positive integers n can be written as the difference of two squares? For example, 5 52 - 12. The following table lists the expression values of X and y. Since x  y  xl-y2  n  n  = =  32  - 22 and  is positive, we assume that x > y 2::  X  Y  xl-y2  X  24  =  x2 - y2 for varying  Y  0. xl-yl  1  0  1  5  4  9  8  0  64  2  0  4  6  0  36  8  1  63  2  1  3  6  1  35  8  2  60  3  0  9  6  2  32  8  3  55  3  1  8  6  3  27  8  4  48  3  2  5  6  4  20  8  5  39  4  0  16  6  5  11  8  6  28  4  1  15  7  0  49  8  7  15  4  2  12  7  1  48  9  0  81 80  4  3  7  7  2  45  9  1  5  0  25  7  3  40  9  2  77  5  1  24  7  4  33  9  3  72  5  2  21  7  5  24  9  4  65  5  3  16  7  6  13  9  5  56  1.1  15  STATE M E NTS  (a) Based o n the table, conjecture a theorem that states exactly which positive integers can be written as the difference of two squares. (b) Try to prove your conjecture. (c) Notice that some integers appear more than once as the difference of two squares. What accounts for this? Is it possible that an integer will appear infinitely often on this list? Give a reason for your answer. D2. Reread Example 1. Explain what part of that example involves inductive reasoning and what part involves deductive reasoning. See the introduc­ tion to this chapter for a discussion of the difference between inductive and deductive reasoning.  D3. Use inductive reasoning to find a statement about whether or not the sum of two consecutive even integers is divisible by 4. Then prove your statement.  D4. Criticize the following "statement" of the Fundamental Theorem of Calculus: f(x) dx = F(b) - F(a).  J:  D5. Criticize the following "proof" of the fact that if n and m are even then n +  m  is even.  We know that n = 2t and m Therefore, n + m is even.  =  2t, so n  +  m =  2t  +  2t  =  4t.  Write out a correct proof.  D6. Is the following a valid proof that every integer multiple of 4 is even? If not, explain what you think is wrong with it and then write your own proof. Every multiple of 4 has a 4 in it and 4 has a 2 in it. Therefore, every multiple of 4 has a 2 in it and therefore a multiple of 4 is even.  D7. Consider the following statement P: If n is an integer and n2 is a multiple of 4, then n is a multiple of 4. The following is a "proof " that P is a false statement:  62 = 36 and 36 is a mUltiple of 4 but 6 is not a multiple of 4. Therefore, P is false. Is this proof valid? Give your reasons and if you think it is not a valid proof, write a correct one.  D8. Consider the following "proof" of the fact that if n is an integer and n 2 is even, then n is even.  16  CHAPTER I  MATH EMATI CAL REAS O N ING  By Example 1 , the square of an even integer is even. Therefore n can't be odd and hence must be even. Is this proof correct? Give reasons for your answer. If you think the proof is invalid, write a correct one. D9. Find a proof of the Pythagorean Theorem and write it out. What assump­ tions are used in the proof?  1.2  COMPOUND STATEMENTS Conjunctions and Disjunctions  Statements, especially in mathematics, are often complicated but can be seen as built up from simpler statements. Such compound statements can be constructed in several different ways, at least two of which are very easy.  Definition 1.2.1 Let 1.  P and Q be  statements.  The conjunction of P and Q, written P /\ Q (and read "P and Q"), is the statem en t "Both P and Q are true."  2. The disjunction of P and Q, writtenP v Q is the statement "P is true or.Q is true."  (and read "P or Q"),  Obviously, P /\ Q is true if P is true and Q is true. Notice, though, that there are three ways for P /\ Q to be false: if P is true but Q is false, if P is false but Q is true, and if both P and Q are false. The disjunction is sometimes referred to as "the inclusive or": it's all right for both statements to be true. There is only one way for P v Q to be false: both P and Q must be false. That there are three ways for P v Q to be true is inherent in the definition. If P(x) and Q(x) are open sentences in the variable x, we can write P(x) /\ Q(x), read P(x) and Q(x) , to mean the open sentence in the variable x that becomes the statement P(a) /\ Q(a) when x is assigned the value a. Similarly, P(x) v Q(x), read P(x) or Q(x), means the open sentence in the variable x that becomes the statement P(a) v Q(a) when x is assigned the value a. The conjunction and disjunction of open sentences containing more than one variable are defined in like fashion.  1.2  EXAM PLE I  P:  Q: Here EXAM PLE 2  Josef Stalin was the leader of the Soviet Union in 1 940. Germany invaded the Soviet Union in 1 941 . P  and Q are both true, so both P  P:  7  Q:  3-2=1.  <  P:  Q: Both EXAM PLE 4  1\  Q and  P  v  Q are true as well.  5.  Since P is false, EXAM PLE 3  17  COMPOUND STATEM ENTS  P  1\  Q is false, and since Q is true,  P  v  Q is true.  The Red Sox have won a World Series since World War I ended. F. Scott Fitzgerald wrote "For Whom the Bell Tolls." P  and Q are false, so both  P  1\  Q and  P  v  Q are also false.  A statement or open sentence may be compound but not obviously so. For example, if x is a real number, then the open sentence Ixl < 3 can be written without the absolute value sign as -3 < x < 3, and this sentence is the conjunction x < 3 and x > 3. -  EXAM PLE 5  The open sentence Ixl  >3  can be written as the disjunction x  >3  or x  <  -3.  Truth Tables  Note that the preceding comments about the truth or falsity of P 1\ Q and P v Q apply to any statements substituted for P and Q. For example, if P and Q are any statements for which P is true and Q is false, then P 1\ Q is false and P v Q is true. For this reason, it makes sense to consider expressions of the form P 1\ Q, P v Q, or -. P where P and Q are variables representing unspecified statements. Such expressions are called statement forms. They are not really statements themselves but become statements when the variables P and Q are replaced by statements. We can summarize the comments made previously about the truth values of P 1\ Q and P v Q by means of truth tables for their statement forms. P  Q  T  T  T F F  F  P  Q  PvQ  T  T  T  T  F  F  T  F  T  T  F  F  T  T  F  F  F  F  18  CHAPTER I  MATH EMAT I CAL REASONI N G  Note that the first two columns of each table list all of the different combinations of truth values for the variables P and Q. Each combination then determines a corresponding truth value of the statement form. Truth tables for other statement forms can be constructed in this way. EXAM P L E 6  Let P be a statement form. Then the truth table for -,P is:  p ffi EXAM P L E 7  T  F  F  T  If P and Q are statement forms, the truth table for P  /\  -,Q is:  P /\ -,Q  p  Q  T  T  F  T  F  T  F  T  F  F  F  F  Negatin g Conjun ction s an d Disjunction s  Sometimes a compound statement formed from two or more statements can be expressed in different ways but mean the same thing. For example, con­ sider the statement It is not true that today is sunny and warm. In order for the statement "Today is sunny and warm" to be false, it is only necessary that one of the two conditions fail to happen; namely, it not be sunny or not be warm. Therefore, the statement "It is not true that today is sunny and warm" means the same as It is not sunny or it is not warm. If one is true then the other is true and vice versa. If we let P be the statement "Today is sunny" and Q the statement "Today is warm," then we are saying that if -,(P /\ Q) is a true state­ ment, then (-,P) v (-,Q) is true and conversely if (-,P) v (-,Q) is true, then -,(P /\ Q) is true. In fact, for any statements P and Q, -,(P /\ Q) and (-,P) v (-,Q) mean the same thing. This follows from the fact that the statement forms -,(P /\ Q) and (-,P) v (-,Q) have the same truth tables.  1.2  19  C O M PO U N D STATEM ENTS  P  Q  T  T  T  F  F  T  F  F  -,( PAQ )  -,Q  PAQ  F  F  T  F  F  F  T  F  T  T  T  F  F  T  T  T  T  F  T  T  -,P  -,P  V  -,Q  Logically Equivalen t Statemen ts  Statements and statement forms like the preceding ones are said to be  logically equivalent. Here is a formal definition. Definition 1.1.2 We say thadwo statemellts are.iogically equivmem or just equivalent if they are both true or both. false... We say that two statemehtforms,are logically eqQivalent if the su:bsti� t�tion of statements for the varialJlesin the foIpls,always "-eJ<Js logically equivalent �t\itements. . .  Note:  ..  .  .  .  If two statement forms have the same truth tables then they are logically  equivalent.  The preceding truth table shows that the statement forms -,(P /\ Q) and (-,P) v (-,Q) are logically equivalent. In other words, given any two state­ ments P and Q, P /\ Q is false exactly when P or Q is false. Similarly, P v Q is false exactly when both P and Q are false, so -,(P v Q) is logically equivalent to -,P /\ -,Q. A comparison of their truth tables will verify this fact as well. P  Q  -,P  -,Q  PvQ  -,( PvQ )  -,P A-,Q  T  T  F  F  T  F  F  T  F  F  T  T  F  F  F  T  T  F  T  F  F  F  F  T  T  F  T  T  (P -,(P  P: Q: Q): Q):  The earth is flat. The earth revolves around the sun. The earth is flat and revolves around the sun. (False) The earth is not flat or it does not revolve around the sun. (True) The earth is flat or it revolves around the sun. (True) The earth is not flat and it does not revolve around the sun. (False)  EXAM P L E 8  /\ /\  P v Q: -,(P v Q):  20  CHAPTER I  MATH E M ATI CAL REAS O N I N G  In Section 1 . 1 , we saw two other examples of logically equivalent state­ ment forms: (a) -{"Ix P(x» is logically equivalent to 3x 3 (-,P(x» . (b) -,(3x 3 P(x» is logically equivalent to Yx (-,P(x». If we combine these two examples with the logical equivalences associated with negating conjunctions and disjunctions, we obtain the following equiva­ lent statement forms: (c) (d) (e) (f)  -,(Yx (P(x) v Q(x » ) is equivalent to 3x 3 ((-,P(x» 1\ (-,Q(x» ). -,(Yx (P(x) 1\ Q(x))) is equivalent to 3x 3 ((-,P(x» v (-,Q(x))). -,(3x 3 (P(x) v Q(x» ) i s equivalent t o Yx ((-, P(x» 1\ (-,Q(x» ) . -,(3x 3 (P(x) 1\ Q(x» ) i s equivalent t o Yx ((-,P(x» v (-,Q (x » ) .  These equivalences are illustrated b y the following examples. EXAM P L E 9  P: -,P:  Every day this week was sunny or hot. Some day this week was not sunny and not hot.  EXA M P L E 1 0  P: -,P:  There is a real number x such that x > 4 and x If x is a real number, then x :s 4 or x ;::: 10.  EXA M P L E I I  P: -,P:  Every multiple of 6 is even and is not a multiple of 4. There is a multiple of 6 that is odd or is a multiple of 4.  <  10.  Sometimes statements that appear to be logically equivalent are not. For example, suppose that P(x) and Q (x) are open sentences containing the variable x and let S and T be the following statements: S:  T:  For all x, P(x) or Q(x). For all x, P(x) or for all x, Q(x) .  Both of these statements have universal quantifiers and involve a disjunc­ tion with respect to the statements P(x) and Q(x). At first glance, they appear to be saying the same thing and therefore should be logically equivalent. But consider the following example: let P(x) be the open sentence "x > 2" and Q(x) the open sentence "x < 5 . " Letting x be assigned values from the real numbers, S and T become: S:  T:  For all real numbers x, x For all real numbers x, x  > >  2 or x < 5 . 2 or for all real numbers x, x  <  5.  It is clear that S is a true statement but T is a false statement. Therefore S and T are not logically equivalent.  1.2  21  C O M POU ND STATE ME NTS  A s another example, consider Example 9. The statement "Every day this week was sunny or hot" does not mean the same as "Every day this week was sunny or every day this week was hot," because for the first statement to be true, every day of the week had to be sunny or hot, so some could have been sunny and cool and others cloudy but hot. But the second statement is only true if every day was sunny or if every day was hot. Now let's consider the following statements, again assuming that P(x) and Q(x) are open sentences containing the variable x. s:  T:  There exists x such that P(x) or Q(x) . There exists x such that P(x) or there exists x such that Q(x) .  In this case, S and T are logically equivalent. To prove this we must show that S and T are either both true or both false. First, suppose that S is a true statement. Then there is an assigned value of x, say x = a, for which pea) is a true statement or Q(a) is a true statement. Since there are two possibilities, we'll look at each one separately. Suppose that pea) is true. It follows that the statement There exists x such that P(x) is true and therefore the disjunction There exists x such that P(x) or there exists x such that Q(x) is true also. So statement T is true in this case. On the other hand, if Q(a) is true, then the statement There exists x such that Q(x) is true, and thus T is true in this case also. Now suppose that T is true. Then there is an x such that P(x) or there is an x such that Q(x) . If there is an x such that P(x), then there is an assigned value of x, say x a, such that pea) is true. It follows that there is an assigned value of x, namely x = a, such that pea) or Q(a) is true. Thus there exists an x such that P(x) or Q(x), so S is true. On the other hand, if there is an x such that Q(x) , then there is an assigned value of x, say x = b, such that Q(b) is true. Hence there is an b, such that P(b) or Q(b) is true. So there assigned value of x, namely x is an x such that P(x) or Q(x) and again S is true. Therefore if T is true, then S is true. This proves that S and T are logically equivalent. =  =  22  CHAPTER I  EXAM PLE 12  MATH EMATI CAL REASO N I N G  The statement There was a day this week that was sunny or hot is logically equivalent to the statement There was a day this week that was sunny or there was a day this week that was hot.  EXAM PLE 1 3  The following statements are equivalent:  P: Q:  There is a real number x such that x > 2 or there is a real number x such that x < 5. There is a real number x such that x > 2 or x < 5 .  Our examples o f compound statements given i n this section s o far have been formed from two given statements or statement forms P and Q. We can, of course, construct statements from three or more given statements. EXAM PLE 14  Consider the statement According to today's weather forecast, tomorrow will be cold and cloudy or cold and rainy. Let P, Q, and R be the statements:  P: Q: R:  Tomorrow will be cold. Tomorrow will be cloudy. Tomorrow will be rainy.  Then the original statement has the form: According to today's weather forecast, (P  A  Q)  v  (P  A  R) .  If we analyze the meaning of this statement, then we see that it could be rephrased as According to today's weather forecast, tomorrow will be cold and it will be cloudy or rainy. In this form our statement becomes According to today's weather forecast, P  A  (Q  v  R).  1.2  EXAM PLE 1 5  23  CO M PO U N D STATE MENTS  The last example suggests that the statement forms ( P /\ Q) v ( P /\ R ) and P /\ (Q v R) are logically equivalent. To prove this we will examine their respective truth tables. Since there are three statements involved, the truth tables will have eight rows corresponding to all possible combinations of truth or falsity of P, Q, and R. ( PAQ )  P  Q  R  PAQ  PAR  T  T  T  T  T  T  T  T  F  T  F  T  T  F  T  F  T  T  T  F  F  F  F  F  F  T  T  F  F  F  F  T  F  F  F  F  F  F  T  F  F  F  F  F  F  F  F  F  P  Q  R  Q vR  T  T  T  T  T  T  T  F  T  T  T  F  T  T  T  T  F  F  F  F  F  T  T  T  F  F  T  F  T  F  F  F  T  T  F  F  F  F  F  F  V  ( PAR)  PA(Q vR)  Since the truth tables of (P /\ Q) v (P /\ R) and P /\ ( Q v R) are the same, they must be logically equivalent. We now give a mathematical example of the equivalence in the previ­ ous example. EXA M P L E 16  Let x be a real number. Suppose that we wish to write the statement  x> -10 and Ixl > 5 in a simpler form without using absolute value signs. The inequality Ixl> 5 is equivalent to the statement x> 5 or x < - 5 . By the previous example, the statement  x> -10 and (x> 5 or x < -5)  24  CHAPTER I  MATHEMATICAL REASO N I NG  is equivalent to the statement  (x> - 10 and X>5) or (X> -10 and x < -5). Because any real number x that is greater than 5 is also greater than - 10, the statement x> - 10 and x> 5 is equivalent to x > 5. Finally, we can reword our statement as  x>50r -1O < x < -5. Tautologies and Contradictions  Sometimes a statement form will always be true no matter what statements are substituted for the variables. Such a statement form is called a tautology. A simple example is the statement form P v -,P. This statement form is true when P is true and it is true when P is false. A statement form is a tautology if each of its truth table values is true. A statement form that is always false is called a coutradictiou. The state­ ment form P 1\ -,P is an example. A statement form is a contradiction if each of its truth table values is false. Note that if S is a tautology then -,S is a contradiction and if S is a contradiction then -,S is a tautology. We will see other examples of tautolo­ gies and contradictions in this chapter. HISTORICAL COMMENTS: EUCLID'S AXIOMS  In Example 28 of Section 1 . 1 , the following statement was given: For every real number x, there is an integer n such that n> x. This is a true statement. It is in fact a property of the real numbers called the Archimedean Principle. An immediate consequence is that there is no "largest" real number. Although this fact may seem obvious from our intu­ itive grasp of the real number line, a formal proof of the Archimedean Principle depends on an axiom of the real numbers called the Least Upper Bound Axiom. ( A discussion of the Least Upper Bound Axiom and a proof of the Archimedean Principle is given in Section 7.2.) You will often find that statements that seem obvious require not so obvious proofs. The starting point of such proofs are axioms, statements that we assume as given. You probably first encountered axioms in your study of plane geometry in high school. And that of course brings us to Euclid. Euclid lived about 300 B.C. and although not much is known about his personal life, he is famous for his text Elements. In it Euclid lists five postulates or axioms that form the basis of his study of geometry. In all, the Elements consists of 13 books and contains 467 propositions. The proof of each proposi­ tion is based on earlier propositions and the postulates. The great achieve-  1.2  COMPOUND STATEMENTS  25  ment of Euclid's E lements is the use of logic and deduction to advance the knowledge of mathematics. The E lements is not without its defects, however. Sometimes proofs are incomplete or assumptions are made without proof. For example, in one of his propositions Euclid implicitly uses without proof a statement equiva lent to the Archimedean Principle. Archimedes (287-212 B.C.), perhaps the greatest mathematician of ancient Greece, used it himself without proof (hence the attachment of his name to it) and the Greek mathematician Eudoxus ( ca. 408-355 B.c. ) used it also. These are the five postulates: 1. 2. 3. 4. 5.  A straight line can be drawn from any point to any point. A finite straight line can be produced continuously in a straight line. A circle may be described with any center and distance. All right angles are equal to one another. If a straight line falling on two straight lines makes the interior angles on the same side together less than two right angles, the two straight lines, if produced indefinitely, meet on that side on which the angles are together less than two right angles.  Euclid's fifth postulate, known as the Parallel Postulate, is the most famous of all of the axioms. What strikes one about these postulates is that the first four seem quite straightforward and obvious. The fifth postulate, however, is of a different nature. It reads more like a theorem. One has to read it carefully in order to understand it. Even then it does not seem readily apparent. It seems more like a statement one should try to prove rather than accept as given. In fact many mathematicians from Euclid's time and later felt the same way and numerous attempts were made to prove the fifth postulate. However, all attempts at a proof failed. Usually when someone claimed to have a proof of the fifth postulate, it would turn out that some­ where in the proof, an assumption had been made that was in fact logically equivalent to the fifth postulate. One of the earliest attempts, for instance, was made by the Greek astronomer Claudius ptolemy in about 150 A.D. But Ptolemy assumed the following statement: Given a point P in the plane and a line L that does not intersect P, there is one and only one line that passes through P and is parallel to L. This statement is actually equivalent to Euclid's fifth postulate and is the version of the fifth postulate that actually appears in most high school geometry texts. The following statements, familiar to students of plane geometry, are also equivalent to the Parallel Postulate: 1. There exist two triangles that are similar but not congruent. 2. There exists a triangle the sum of whose angles is 180 degrees. 3. Through any three points not lying on a straight line there is a circle.  26  CHAPTER I  MAT H E MATICAL REASO NING  Exercises 1 . 2  1. Let P b e a statement form. Prove that P and -.(--,p) are logically equiv­ alent.  2. Let P and Q be statement forms. Write the truth tables for the following statement forms. ( a ) (-,P) v Q. ( b ) -,(P v Q) . ( d ) «-,P) /\ (-,Q » v Q. ( c ) -,«-,P) /\ Q » .  3. Prove that the statement forms -,«-,P) v Q) and P  /\  (-,Q) are logi­  cally equivalent. 4. Write the negation of the following statements. ( a ) August is a hot month and September is sometimes cool. ( b ) Every member of the baseball team is complaining and not hitting. ( c ) Some cars are comfortable and not expensive. ( d ) Math tests are long or difficult.  5. Write the negation of the following statements. ( a) If x and y are real numbers such that xy 0, then x = 0 or y O. ( b ) For every integer x, x2 is odd and x3 1 is divisible by 4. ( c ) Vn, n an integer, 3 an integer k such that n = 2k or n = 2k + 1 . ( d ) 3 a rational number r :3 1 < r < 2. ( e ) A real number can be greater than 2 or less than 1. ( f) Some functions are neither differentiable at 0 nor continuous at O. =  =  -  6. Let P be the statement "Every mUltiple of 6 is even and is not a multiple of 4" of Example 1 1 in this section. ( a ) Write P in the form, "for all . . . , if . . . , then . . . . " Use variables. ( b ) Write the negation of P. Use variables. ( c ) Prove P or -,P. 7. Repeat Exercise 6 if P is the statement "If the product of two integers is even, then both of the integers are even. " 8 . Let n, m E Z . Write the negation o f the statement "Exactly one o f the integers n or m is odd. " 9. Consider the following statement P: "If n is an odd integer, then there exists an integer x such that n = 4x + 1 or n = 4x + 3 . " ( a ) Write the negation o f P. ( b ) Prove P or -,P.  10. Let P and Q be statement forms. ( a ) Prove that P /\ Q is logically equivalent to Q /\ P. ( b ) Prove that P v Q is logically equivalent to Q v P. 1 1 . Let P(x) and Q(x) be open sentences containing the variable x. In each part of this problem, determine if the given statements S and T are  1.2  27  C O M P O U N D STATE M ENTS  logically equivalent. If they are, give a proof. If they are not, give an example of open sentences P(x) and Q(x) for which S and T are not logically equivalent. ( a ) S: Yx, (P(x) 1\ Q(x» .  T : (Yx, P(x» 1\ (Yx, Q(x» . ( b ) S: 3x 3 (P(x) 1\ Q(x» . T : ( 3x 3 P(x» 1\ ( 3x 3 Q(x».  12. Let P, Q, and R be statement forms. Write the truth tables for the following statement forms. ( a ) (P 1\ -,Q) v ( -,R) . (b ) (-,P)  1\  ( R 1\ (-,Q».  (Reminder: To do this problem, it is necessary to list all possible combinations of truth values for P, Q, and R. There are eight of them.)  13. Let P, Q, and R be statement forms. ( a) Prove that (P v Q) v R and P  v (Q v R) are equivalent state­ ment forms. ( b ) Prove that (P 1\ Q) 1\ R and P 1\ (Q 1\ R) are equivalent state­ ment forms. ( c ) Prove that P v (Q 1\ R) and (P v Q) 1\ (P v R) are equivalent statement forms.  14. Characterize all real numbers x such that x > 1 or Ixl  < 3. Express your answer in the simplest possible way without using absolute value signs.  1 5 . Let P, Q, R, and S be statement forms. ( a ) Prove that P v « Q 1\ R) 1\ S » and (P v Q) equivalent statement forms. ( b ) Prove that P 1\ « Q v R) v S » and (P equivalent statement forms.  1\  Q)  1\  (P v R)  1\  (P V S ) are  v  (P 1\ R)  v  (P 1\ S ) are  16. Let P and Q be statement forms. ( a ) Prove that (P 1\ Q) v (P 1\ -,Q) V (-,P 1\ Q) v (-,P 1\ -,Q) is a tautology. ( b ) Prove that (P v Q) 1\ (P v -,Q) 1\ (-,P v Q) 1\ (-,P V -,Q) is a contradiction. D i s c u s s i o n a n d D i s c ov e ry E x e r c i s e s  Dl. Consider the following "proof" that i f n o r m is a n odd integer, then nm is an even integer. Suppose that n is odd and m is even. Then m 2t for some integer t. Therefore nm = n(2t) = 2nt, which is even. Next suppose that n is even and m is odd. We can write n = 2s for some integer s. Thus nm = 2sm, which is also even. In both cases, we get that nm is even. =  Thus the statement is proved. Is the proof valid? If you think it is not, explain.  28  CHAPTER I  MATH EMATICAL REASO N I N G  D2. Consider the following two statements:  P: Q:  For every real number x , x2 2::: O. Lyndon Johnson was elected president in 1 964.  Are these statements logically equivalent? Explain. D3. Using the five statements below as clues, match Sarah, Ann, and Bob with their respective occupations (teacher, entomologist, or poet) and the color of their houses (brown, white, or green). Explain how you arrived at your answer and mention any rules of logic that you use. Assume that no two people have the same occupation or the same color house. The first three clues are true statements: 1 . Sarah or Ann is the poet. 2. Sarah's or Bob's house is green. 3. Ann's house is green or white. The next two clues are false statements: 4. The teacher's house is green. 5. Sarah is the poet or Bob is the entomologist.  D4. Consider the following two statements: P: Q:  For every even integer n , there i s a n odd integer m such that n + m is odd. There is an odd integer m such that for every even integer n , n + m is odd.  (a) Do these statements mean the same thing? If not, explain the difference. (b) Write the negations of P and Q. (c) Discuss the truth or falsity of statements P and Q. Give proofs. (d) Are these statements logically equivalent? Give reasons for your answer. DS. Repeat the previous problem for the following statements:  P: Q:  For every real number x between 0 and 1 , there is a real number y between 1 and 2 such that x + y < 2. There is a real number y between 1 and 2 such that for every real number x between 0 and 1 , x + Y < 2.  D6. Euclid's fourth postulate says: "All right angles are equal to one an­ other. " Isn't it obvious that all right angles are equal? What do you think Euclid meant by right angle? Why does he consider it necessary to include this postulate?  1 .3  1 .3  29  I M PLI CATI O N S  I MP L I CATIONS I m p lication: Definition and Exam p les  In mathematics, as we have noted before, we are interested in whether a given statement is true or false. Usually such a statement will be proven true (or false) because it (or its negation) can be seen to follow logically from prior statements that we know to be true. Those prior statements may be propositions already proven or they may be axioms. Axioms are statements that we take to be given without proof and serve as the starting point of a particular subject. In Chapter 5, for example, we will list a number of axioms of the integers and then deduce properties of the integers from them. In the previous two sections, many of the statements we looked at took the form: "If . . . , then . . . " or "For all . . . , if . . . , then . . . . " The "if-then" part of such a statement is called an implication. Most theorems will take this form. In Example 1 of Section 1 . 1 , we considered the statement: " If n is an even integer, then n2 is even. " The "if" part of the statement gives the premise or assumption that is made. In this example, we assume that n is an even integer. The "then" part is the conclusion that is asserted to follow from the premise. The statement "n2 is even" is asserted to be a true statement under the assumption that "n is even . " So in order to prove such a statement as "if n is an even integer, then n2 is even," one starts, as was done in Example 1 of Section 1 . 1 , by assuming that n is an even integer and then proves that n2 is even. We begin with a formal definition of implication and then do some ex­ amples. Defi n ition 1 . 3 . 1 Le t P and Q be statements. The impUeation P =* (read "P implies Q,,) i� the $tatement � 'If Pis ttuel then 'Q is true."  Q .  P: Q: P � Q:  3 + 2 = 5. 3 + 1 + 1 = 5. If 3 + 2 = 5, then 3 + 1 + 1  EXAM PLE 2  P: Q: P � Q:  4 is an even integer. 42 is an even integer. If 4 is an even integer, then 42 is an even integer.  EXAM PLE 3  P: Q: P � Q:  The function f(x) = x2 is differentiable at O. The function f(x) = x2 is continuous at O. If the function f(x) = X l is differentiable at 0, then it is continuous at O.  EXAM PLE I  =  5.  30  CHAPTER I  MATH EMATICAL REAS O N I N G  Tru th Table for an Im p lication  Before we consider when an implication might be true, an important distinc­ tion must be made. For a mathematician, there is no sense of causality in the statement P � Q; we leave this question to philosophers. P might be (apparently) entirely unrelated to Q. Rather, the statement simply means that in all circumstances under which P is true, Q is also true. Very loosely, whenever P "happens," Q also "happens" ; we don't care whether P seems to cause Q or not. With this in mind, when would P � Q be false? We would need P to "happen" (P true) and Q not to "happen" (Q false) . This is the only case. Seen another way, P � Q can't be false (so must be true) if P is false. Even if P and Q are both false the implication P � Q is true. If P is true, though, Q must also be true for P � Q to be true. In summary, whether P � Q is true or false depends only on the truth or falsity of P and of Q, so there are four cases, just as with conjunction and disjunction. The following table gives the truth values of the statement form  P � Q.  EXA M P L E 4  p  Q  P�Q  T  T  T  T  F  F  F  T  T  F  F  T  P: Q:  3 3  + +  2 1  =  +  5. 1 = 5.  In this case, both P and Q are true, so P � Q is true as well. Intuitively, P "forces" Q to be true, since 2 = 1 + 1 , but the truth of the two statements is sufficient. EXAM P L E 5  P: Q:  Gerald Ford was vice president under Jimmy Carter.  2  <  7.  Here, P is false and Q is true, so P � Q is true. Notice that if R is the statement 7 < 2, P � R is also true; a false statement implies anything ! EXAM P L E 6  P: Q:  The American Revolution ended in 178 1 . George Washington served three terms as president.  P is true and Q is false; however related the statements might be, the statement P � Q is false.  1.3  P: Q:  EXAM PLE 7  31  I M PLI CATI O N S  4 is an even integer. 42 is an even integer.  Since P and Q are both true, P � Q is true. Example 1 of Section 1 . 1 does imply that there i s a causality between statements P and Q but the mere fact that P and Q are both true statements is sufficient to establish that P � Q is true.  P: Q:  EXA M P L E 8  The function f(x) The function f(x)  = =  x2 is differentiable at O. x2 is continuous at O.  Both P and Q are true statements verified in calculus. So the implication Q is true. There is a causality between P and Q, since a theorem from calculus shows that differentiability implies continuity. But again this causality, although it is certainly helpful to use, is not needed to establish the truth of P � Q.  P  EXAM PLE 9  �  P: Q:  The function f(x) The function f(x)  = =  x2 is continuous at O. x2 is differentiable at O.  Here there is no causality between P and Q since continuity does not in general imply differentiability. Nevertheless, the implication P � Q is true since P and Q are both true. Proving Statements Containing Im p lications  Most often we will be interested in establishing the truth of ( proving ) state­ ments of the form \;Ix, P(x) � Q(x) where P(x) and Q (x) are open sentences. Since P(x) and Q(x) are not statements, the expression P(x) � Q(x) is not a statement either. P(x) � Q(x) is the open sentence in the variable x that becomes the statement pea) � Q(a) when x is assigned the value a. But recall that the expression \;Ix, P(x) � Q(x) is a statement because the variable x has been quantified. ( For simplicity of notation, we assume there is only one variable involved but in fact the same principles apply no matter how many variables are being used. ) Since, for an assigned value a of x, the statement P( a) � Q( a) will always be true if pea) is false, we ne'ed not consider this case. Rather, we can assume that, if the variable x is assigned a value a, then pea) is true and proceed from there to prove Q(a). pea) is called the hypothesis, and Q(a) the conclu­ sion. We use a letter, in this case a, to denote the assigned value of the variable x rather than give a specific value to x like 0 or 2, since we must prove that pea) � Q(a) for every possible assigned value of x. Here are some examples.  32  CHAPTER I  EXAM PLE 1 0  MATH EMATICAL REAS O N I N G  The statement "The square of every even integer is even" can be written " If n is an even integer, then n2 is even." This statement contains a universal quantifier. Recall from Example 6 of Section 1 . 1 that the sentence can be reworded "For every integer n, if n is even, then n2 is even. " This statement has the form V integers n, pen) � Q(n) where pen) is the open sentence "n is even" and Q(n) is the open sentence "n2 is even." The proof of this statement would start as follows: Let a be an integer and suppose a is even. The statement "a is even" is the hypothesis. We are thus starting out by asserting the truth of the hypothesis pea). The conclusion is the statement "a2 is even. " The remainder of the proof involves verifying that the statement Q(a) is now true. The details of this proof were done in Example 1 of Section 1 . 1 . When w e start this proof by saying "Let a b e a n integer and suppose a is even," we are assigning the variable n an even integer value but without specifying exactly what that value is. The letter a thus stands for any even integer and once it is proven that a2 is even, the truth of the statement pea) � Q(a) is established for every integer a. Note:  In practice, it is usually simpler t o use the same letter for t h e variable and its  assigned value. So we could use just the letter n in the proof of Example 1 0 without confusion. B ut remember, once we say " Let n be an integer," then P(n) is a statement.  EXAM PLE I I  Prove or disprove the statement S: "If n and m is even." This statement can be reworded For all integers n and  m,  P  �  m  are odd integers, then n +  Q  where P is the open sentence "n and m are odd integers" and Q is the open sentence: "n + m is even. " Note that statement S contains two variables. We should more properly write pen, m ) and Q (n, m ) , since P and Q depend on the variables n and m, but for the sake of simplicity of notation, we will simply write P and Q. Because the truth or falsity of S is not immediately clear, we might begin by making a conjecture as to whether or not it is true. A good way to start is to try a few examples. Our hypothesis is that n and m are odd integers, so we'll try some odd integers aqd see if their sums are even or odd:  3 + 5  =  8,  1 1 + 17  =  59 + 43  28 ,  =  102.  In each of these cases, the sum is even. These examples do not prove that the statement is true since the statement contains a universal quantifier. We must prove that for all odd integers n and m, the sum n + m is even. But it certainly seems reasonable to conjecture that S is true.  Now let's prove it! To begin our proof, let n and  m  be odd integers. This means that we can  1.3  33  I M PL I CATIONS  write n a s 2t + 1 and m a s 2s + 1 , where t and s are integers. Note that if we write n = 2t + 1 , then we cannot write m = 2t + 1 since n and m are not necessarily the same integer. We must use another letter besides t and so we arbitrarily chose the letter s. Thus n +  m  =  (2t  +  1)  +  (2s  +  1)  =  2t + 2s  and since t + s + 1 i s an integer, n +  m  +  2  =  2(t  +  s  +  1)  i s even. The proof i s complete.  Note that we started our proof by letting n and m be odd integers. The variables n and m stand for any pair of odd integers, not specific ones. So the fact that n + m is even has been established for all pairs of odd integers n and m. This method of proof is necessary since the statement has a univer­ sal quantifier. Negating an I m p lication: Counterexam p les  Sometimes a statement containing an implication may be false. In that case, it becomes necessary to state its negation in a coherent fashion in order to prove that it is false. EXAM P LE 1 2  Consider the statement "If a real-valued function I is continuous at 0, then I is differentiable at 0. " This statement from calculus is false. To see how to write its negation, we break it down into its simple components. Let P(f) be the open sentence "I is continuous at 0" and Q(f) the open sentence "I is differentiable at 0. " (Note that the variable in this example is f.) So our statement is "For every real-valued function f, P(f) =::} Q(f) . " As we saw in Section 1 . 1 , the negation must be the statement "There is some real­ valued function I such that -,(P(f) =::} Q(f) ) . " A s w e have seen, i f P and Q are statements, then the only way for P =::} Q to be false is that P be true and Q be false. Thus the negation must take the form "There is an assigned value of the variable I, say I = g, such that peg) is true and Q(g) is false." More simply, using just the letter f, "There is a real-valued function I that is continuous at 0 but not differentiable at 0." Since the absolute value function I defined by I(x) Ixl is such a function, the proof is complete. This function is called a counterexample because it serves to disprove a statement with a universal quantifier. =  Given the previous example, it should not be surprising that if P and Q are statement forms, then -,(P =::} Q) is logically equivalent to P /\ -,Q. We leave it as an exercise to show that these statements have the same truth tables. It follows then that if P(x) and Q(x) are open sentences, the negation of the statement "For all x, P(x) =::} Q(x) " is the statement "There exists x such that P(x) /\ -,Q(x)," or in other words, "For some x, P(x) is true and Q(x) is false."  34  CHAPTER  I  MATH EMATICAL REAS O N I N G  The value assigned to the variable x that makes P(x) true and Q(x) false is called a counterexample to the statement "For all x, P(x) => Q(x) . "  Note that the negation of a n implication is not a n implication! EXAM P L E 1 3  Consider the statement "The sum of two perfect squares is a perfect square. " T o prove o r disprove this statement, let's first write i t a s a statement that has a universal quantifier and contains an implication: "For every pair of integers n and m, if n and m are perfect squares, then n + m is a perfect square. " Symbolically, we can write this as "\I integers n and m, P => Q " where P i s the open sentence "n and m are perfect squares" and Q i s the open sentence "n + m is a perfect square. " The negation of this statement would be "There exist integers n and m such that P 1\ -,Q." In other words, "There exist integers n and m such that n and m are perfect squares but n + m is not a perfect square. " Since 4 and 9 are perfect squares, but 4 + 9 = 13 i s not a perfect square, the negation must be true and the original statement false. Again we have used a counterexample to disprove a statement with a universal quantifier.  Necessary an d Sufficien t Con dition s  Given statements P and Q, the implication P => Q means, as we have seen, that if P is true, then Q is true. We say then that P is a sufficient condition for Q. In other words, in order for Q to be true, it is sufficient that P be true. Also, if P => Q is a true statement, we say that Q is a necessary condition for P, meaning that Q must be true in order for P to be true. In other words, if Q is false, then P is false. The statement -,Q => -,P is logically equivalent to P => Q. This equivalence will be discussed in the next section. Note however that if P => Q is a true statement, then it is not necessary that P be true in order for Q to be true. Similarly, Q is not a sufficient condition for P. In other words, even if Q is true, P may be false. EXA M P L E 1 4  Let x be a real number. Let P be the statement "x>5" and Q the statement "x > 0." It is clear from properties of inequalities of real numbers that P => Q is true. So x> 5 is a sufficient condition for x> O. But it is not a necessary condition. x need not be greater than 5 for x to be greater than o. On the other hand, x > 0 is a necessary condition for x > 5; that is, if x> 0 is false, then x> 5 is false. We can also easily see that x> 0 is not a sufficient condition for x> 5.  EXAM PLE 1 S  Let f be a real-valued function. It follows from Example 12 that f being continuous at 0 is a necessary but not sufficient condition for f to be differen­ tiable at O. On the other hand, f being differentiable at 0 is a sufficient but not necessary condition for f to be continuous at O.  1 .3  :ili.  I M PLICATI O N S  35  HISTO RICA L COMME N TS : LOBACHEVSKIA N GEOMET RY  I n Section 1.2 w e discussed the attempts t o prove Euclid's fifth postulate and how all such attempts failed. Then, in the 1 9th century, three mathematicians, Nicolai Lobachevsky (1793-1856), Johann Bolyai (1802-1860) , and Carl Friedrich Gauss (1777-1 855) arrived at the same conclusion independently: that Euclid's fifth postulate was indeed an independent axiom and could not be deduced from the other axioms. This assertion followed from the realiza­ tion that by altering Euclid's fifth postulate, a new consistent geometry could be created. Their revised postulate was the following: given a point P and a line L that does not contain P, there is more than one line that passes through P and is parallel to L ( that is, does not intersect L). From this postulate, together with the other Euclidean axioms, a new non-Euclidean geometry was born. This geometry has come to be known as Lobachev­ skian geometry. Lobachevskian geometry has some interesting and surprising theorems. In this geometry, the sum of the angles of any triangle is less than 1 80 degrees and if two triangles are similar, then they must be congruent. A model for Lobachevskian geometry is the interior of a circle where "lines" are defined to be chords of the circle with the endpoints excluded. In the accompanying figure, we see that we can draw infinitely many lines through the point P that do not intersect the line L .  L  Exercises 1 . 3  1 . Express the following statements in the form "for all . . . , if . . . then . . . " using symbols to represent variables. Then write their negations, again using symbols. ( a ) Every hexagon has 6 sides. ( b ) An integer is odd or even. ( c ) A function that is differentiable at 0 is continuous at O. ( d ) All positive real numbers have a square root.  2. Repeat Exercise 1 for the following statements. ( a ) All angles of an equilateral triangle are equal.  36  CHAPTE R I  MATH EMATI CAL REAS O N I N G  ( b ) 1 is the smallest positive integer. ( c ) When the product of two integers is even, then both integers are even. ( d ) Between any two real numbers there is a rational number. 3. Let P and Q be statements. ( a ) Prove that -,(P => Q) is logically equivalent to P 1\ -,Q. (b ) Prove that -,(P => Q) is not logically equivalent to -,P => -,Q. ( c ) Give an example of statements P and Q such that -,P => -,Q is true and -,(P => Q) is false. ( d ) Explain why it is impossible to give an example of statements P and Q such that -,(P => Q) is true and -,P => -,Q is false. 4. Consider the following statement: "The product of an even integer with any integer is always even. " ( a ) Rewrite the statement in the form "for all . . . , if . . . , then . . . " using symbols to represent variables. ( b ) Write the negation of the statement, again using symbols. ( c ) Prove the statement if you think it is true or disprove it if you think it is false.  5. Repeat Exercise 4 for the statement "The cube of an odd integer is odd. " 6. Repeat Exercise 4 for the statement "The sum of the squares of two consecutive integers is odd. "  7. Repeat Exercise 4 for the statement "The sum of the squares of three consecutive integers is even. "  8. Repeat Exercise 4 for the statement: "If the square root of a positive integer is an even integer, then the integer itself is even. "  9. Prove that the statement form (P  =>  Q)  v  (Q  =>  P) is a tautology.  10. Let P, Q, and R be statements. Prove that if the statement P => Q is true and the statement Q => R is true, then the statement P => R is true. 1 1 . Let P(x), Q(x) , and R(x) be open sentences containing the variable x. Prove that if the statement (Vx(P(x) => Q(x ») 1\ (Vx(Q(x) => R(x») is true, then the statement Vx(P(x) => R(x » is true. 12. Let P, Q, and R be statement forms. Prove that the statement form P => (Q v R) is logically equivalent to the statement form (P 1\ -,Q) => R. 13. Let P, Q, and R be statement forms. Is the statement form P => (Q v R) logically equivalent to the statement form (P => Q) v (P => R) ? Justify your answer.  14. Let P, Q, and R be statement forms. Prove that the statement form P => (Q 1\ R) is logically equivalent to the statement form (P => Q) 1\ (P => R).  1.3  37  I M PLI CATI O N S  15. Let x and y b e real numbers. Consider the statement S : " If xy x = 0 or y = 0."  =  0 , then  (a) Show that S can be expressed in the form P � ( Q v R) for appropriate statements P, Q, and R. (b) Rewrite statement S using its logically equivalent form (P /\ -,Q) � R. (See Exercise 12.) (c) Using the revised form of statement S from part (b) and some properties of the real numbers, prove statement S.  16. Let P(x), Q (x), and R(x) be open sentences containing the variable x. If the statement (3 x :3 (P(x) � Q(x») /\ (3 x :3 ( Q (x) � R(x») is true, does it follow that the statement 3 x :3 (P(x) � R(x» is true also? If you think it does, give a proof. If you think it does not, give an example of open sentences P(x) , Q(x), and R(x) for which the statement (3 x :3 (P(x) � Q(x» ) /\ (3 x :3 (Q(x) � R(x») is true and the state­ ment 3 x :3 (P(x) � R(x» is false. be an integer. Let P be the statement " n is a multiple of 4" and Q be the statement " n 2 is a multiple of 4." Which of the following are true statements? Prove your answers. (a) P is a sufficient condition for Q. (b) P is a necessary condition for Q. (c) Q is a sufficient condition for P. (d) Q is a necessary condition for P.  17. Let  n  Repeat Exercise 1 7 where P is the statement " n and m are odd integers" and Q is the statement " n + m is even. " See Example 1 1 of this section.  18. Let n ,  m E Z.  D i s c u s s i o n a n d D i s c o v e ry E x e rc i s e s s " i s used. Write a short explanation of what the word "arbitrarily" means in this context.  D l . I n Example 11, the phrase "we arbitrarily chose the letter  D2. Write out the truth table for -,P � -,Q and show that it is logically equivalent to P v -,Q. Write out an informal explanation of why this equivalence makes sense.  D3. (a) Prove that if n is a positive integer, then 1 + 2 + 22 + 23 + . . . 2n = 2n+1 - l .  +  (b) Suppose that you place a piece o f paper o n a table, then place 2 pieces on top of it, then 4 pieces on top of that, then 8 pieces, then 16 pieces, and so on, doubling the number of pieces each time. Assuming that you do this doubling 50 times, how many pieces of paper are in the pile?  38  C H APTER I  MATH EMATICAL REASO N I N G  (c) Assuming that each piece is l IZ00th of an inch thick, estimate how tall the pile is. (d) Use a calculator to give a good approximation of the size of the pile. Express your answer in inches, feet, or miles, whatever seems most appropriate. How good was your estimate? (e) How does this problem fit the theme of this chapter? Explain.  D4. The ancient Egyptians were able to find a formula for the volume of a truncated pyramid with square base and square top. Although we don't know how they arrived at the formula, it is an ingenious application of inductive reasoning and perhaps of deductive reasoning as well, if in fact they were able to prove their result. If the base has side b, the top has side a, and the vertical height is h, find the formula for the volume V of the truncated pyramid. Justify your answer. (Recall that the volume of a full pyramid is one-third the area of the base times the height.)  1 .4  CONTRAPOS I T I VE AND CONVERSE Contrapositive  An alternative way to prove statements of the form P => Q is to verify the statement --.Q => --.P. This would mean showing that whenever Q is false then P is false. Then it would follow that if P is true, Q could not be false (because Q false implies P false) and thus Q is true. Another way to see this is to note that the statements P => Q and --.Q => --.P are logically equivalent. We leave it as an exercise to verify that they have the same truth tables. Besides the formalism of showing that the truth tables are the same, it is important to understand in an intuitive way why these statements are logically equivalent. It should make sense that they mean the same thing. Let's take a non mathematic

An Introduction To Abstract Mathematics Bond Keane Pdf

Source: https://b-ok.global/book/2483618/e41e9a

Posted by: mcgaugheytrachattee.blogspot.com

Share this post