# mathematical reasoning- writing and proof

Post on 28-Dec-2015

278 views

Embed Size (px)

TRANSCRIPT

Mathematical ReasoningWriting and Proof

Version 1.1February 16, 2014

Ted Sundstrom

Grand Valley State University

Ted Sundstrom

Department of Mathematics

Grand Valley State University

Allendale, MI 49401

mathreasoning@gmail.com

Mathematical Reasoning: Writing and Proof

Previous versions of this book were published by Pearson Education, Inc.

Changes Made in Version 1.1

There are no changes in content between version 1.0 of this book and version 1.1.

The only changes are the addition of the Note to Students immediately following

the Table of Contents, and the Creative Commons License has been changed to

the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported Li-

cense.

License

This work is licensed under the Creative Commons Attribution-NonCommercial-

ShareAlike 3.0 Unported License. The graphic

that appears throughout the text shows that the work is licensed with the Creative

Commons, that the work may be used for free by any party so long as attribution

is given to the author(s), that the work and its derivatives are used in the spirit of

share and share alike, and that no party other than the author(s) may sell this

work or any of its derivatives for profit. Full details may be found by visiting

http://creativecommons.org/licenses/by-nc-sa/3.0/

or sending a letter to Creative Commons, 444 Castro Street, Suite 900, Mountain

View, California, 94041, USA.

Contents

Note to Students iv

Preface vi

1 Introduction to Writing Proofs in Mathematics 1

1.1 Statements and Conditional Statements . . . . . . . . . . . . . . . 1

1.2 Constructing Direct Proofs . . . . . . . . . . . . . . . . . . . . . 15

1.3 Chapter 1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . 31

2 Logical Reasoning 33

2.1 Statements and Logical Operators . . . . . . . . . . . . . . . . . 33

2.2 Logically Equivalent Statements . . . . . . . . . . . . . . . . . . 43

2.3 Open Sentences and Sets . . . . . . . . . . . . . . . . . . . . . . 52

2.4 Quantifiers and Negations . . . . . . . . . . . . . . . . . . . . . . 63

2.5 Chapter 2 Summary . . . . . . . . . . . . . . . . . . . . . . . . . 80

3 Constructing and Writing Proofs in Mathematics 82

3.1 Direct Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

3.2 More Methods of Proof . . . . . . . . . . . . . . . . . . . . . . . 102

3.3 Proof by Contradiction . . . . . . . . . . . . . . . . . . . . . . . 116

3.4 Using Cases in Proofs . . . . . . . . . . . . . . . . . . . . . . . . 131

3.5 The Division Algorithm and Congruence . . . . . . . . . . . . . . 141

i

ii Contents

3.6 Review of Proof Methods . . . . . . . . . . . . . . . . . . . . . . 158

3.7 Chapter 3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . 166

4 Mathematical Induction 169

4.1 The Principle of Mathematical Induction . . . . . . . . . . . . . . 169

4.2 Other Forms of Mathematical Induction . . . . . . . . . . . . . . 188

4.3 Induction and Recursion . . . . . . . . . . . . . . . . . . . . . . 200

4.4 Chapter 4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . 213

5 Set Theory 215

5.1 Sets and Operations on Sets . . . . . . . . . . . . . . . . . . . . . 215

5.2 Proving Set Relationships . . . . . . . . . . . . . . . . . . . . . . 230

5.3 Properties of Set Operations . . . . . . . . . . . . . . . . . . . . 244

5.4 Cartesian Products . . . . . . . . . . . . . . . . . . . . . . . . . 254

5.5 Indexed Families of Sets . . . . . . . . . . . . . . . . . . . . . . 264

5.6 Chapter 5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . 277

6 Functions 281

6.1 Introduction to Functions . . . . . . . . . . . . . . . . . . . . . . 281

6.2 More about Functions . . . . . . . . . . . . . . . . . . . . . . . . 294

6.3 Injections, Surjections, and Bijections . . . . . . . . . . . . . . . 307

6.4 Composition of Functions . . . . . . . . . . . . . . . . . . . . . . 323

6.5 Inverse Functions . . . . . . . . . . . . . . . . . . . . . . . . . . 334

6.6 Functions Acting on Sets . . . . . . . . . . . . . . . . . . . . . . 349

6.7 Chapter 6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . 359

7 Equivalence Relations 362

7.1 Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362

7.2 Equivalence Relations . . . . . . . . . . . . . . . . . . . . . . . . 375

7.3 Equivalence Classes . . . . . . . . . . . . . . . . . . . . . . . . . 387

Contents iii

7.4 Modular Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . 400

7.5 Chapter 7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . 411

8 Topics in Number Theory 414

8.1 The Greatest Common Divisor . . . . . . . . . . . . . . . . . . . 414

8.2 Prime Numbers and Prime Factorizations . . . . . . . . . . . . . 426

8.3 Linear Diophantine Equations . . . . . . . . . . . . . . . . . . . 439

8.4 Chapter 8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . 449

9 Finite and Infinite Sets 452

9.1 Finite Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 452

9.2 Countable Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . 462

9.3 Uncountable Sets . . . . . . . . . . . . . . . . . . . . . . . . . . 476

9.4 Chapter 9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . 490

A Guidelines for Writing Mathematical Proofs 492

B Answers for the Progress Checks 497

C Answers and Hints for Selected Exercises 536

D List of Symbols 563

Index 566

Note to Students

This book may be different than other mathematics textbooks you have used since

one of the main goals of this book is to help you to develop the ability to construct

and write mathematical proofs. So this book is not just about mathematical content

but is also about the process of doing mathematics. Along the way, you will also

learn some important mathematical topics that will help you in your future study

of mathematics.

This book is designed not to be just casually read but rather to be engaged. It

may seem like a cliche (because it is in almost every mathematics book now) but

there is truth in the statement thatmathematics is not a spectator sport. To learn and

understandmathematics, you must engage in the process of doingmathematics. So

you must actively read and study the book, which means to have a pencil and paper

with you and be willing to follow along and fill in missing details. This type of

engagement is not easy and is often frustrating, but if you do so, you will learn a

great deal about mathematics and more importantly, about doing mathematics.

Recognizing that actively studying a mathematics book is often not easy, sev-

eral features of the textbook have been designed to help you become more engaged

as you study the material. Some of the features are:

Preview Activities. With the exception of Sections 1.1 and 3.6, each sectionhas exactly two preview activities. Some PreviewActivitieswill review prior

mathematical work that is necessary for the new section. This prior work

may contain material from previous mathematical courses or it may contain

material covered earlier in this text. Other preview activities will introduce

new concepts and definitions that will be used when that section is discussed

in class. It is very important that you work on these preview activities before

starting the rest of the section. Please note that answers to these preview

activities are not included in the text. This book is designed to be used for

a course and it is left up to the discretion of each individual instructor as to

how to distribute the answers to the preview activities.

iv

Note to Students v

Progress Checks. Several Progress Checks are included in each section.These are either short exercises or short activities designed to help you de-

termine if you are understanding the material as it is presented. As such, it is

important to work through these progress checks to test your understanding,

and if necessary, study the material again before proceeding further. An-

swers to the Progress Checks are provided in Appendix B.

Chapter Summaries. To assist you with studying the material in the text,there is a summary at the end of each chapter. The summaries usually list

the important definitions introduced in the chapter and the important results

proven in the chapter. If appropriate, the summary also describes the impor-

tant proof techniques discussed in the chapter.

Answers for Selected Exercises. Answers or hints for several exercises areincluded in an appendix. Those exercises with an answer or a hint in the

appendix are preceded by a star .?/.

Although not part of the textbook, there are now 107 online ideos with about

14 hours of content that span the first seven chapters of this book. These videos

are freely available online at Grand Valleys Department of Mathematics YouTube

channel on this playlist:

http://www.youtube.com/playlist?list=PL2419488168AE7001

These online videos were created and developed by Dr. Robert Talbert of Grand

Valley State University.

There is also a web site for the textbook at

https://sites.google.com/site/mathematicalreasoning3ed/

You may find some things there that could be of help. For example, there currently

i