Mathematical Reasoning, Version 3

Version 3 and Version 2.1 10 Note to Students 11 Preface 13 Introduction to Writing Proofs in Mathematics 21 Statements and Conditional Statements 21 Constructing Direct Proofs 36 Chapter 1 Summary 51 Logical Reasoning 53 Statements and Logical Operators 53 Logically Equivalent Statements 63 Open Sentences and Sets 72 Quantifiers and Negations 83 Chapter 2 Summary 100 Constructing and Writing Proofs in Mathematics 102 Direct Proofs 102 More Methods of Proof 122 Proof by Contradiction 136 Using Cases in Proofs 151 The Division Algorithm and Congruence 161 Review of Proof Methods 178 Chapter 3 Summary 186 Mathematical Induction 189 The Principle of Mathematical Induction 189 Other Forms of Mathematical Induction 208 Induction and Recursion 220 Chapter 4 Summary 233 Set Theory 235 Sets and Operations on Sets 235 Proving Set Relationships 250 Properties of Set Operations 264 Cartesian Products 274 Indexed Families of Sets 284 Chapter 5 Summary 297 Functions 301 Introduction to Functions 301 More about Functions 314 Injections, Surjections, and Bijections 327 Composition of Functions 343 Inverse Functions 354 Functions Acting on Sets 369 Chapter 6 Summary 379 Equivalence Relations 382 Relations 382 Equivalence Relations 395 Equivalence Classes 407 Modular Arithmetic 420 Chapter 7 Summary 432 Topics in Number Theory 434 The Greatest Common Divisor 434 Prime Numbers and Prime Factorizations 446 Linear Diophantine Equations 459 Chapter 8 Summary 469 Finite and Infinite Sets 472 Finite Sets 472 Countable Sets 482 Uncountable Sets 496 Chapter 9 Summary 510 Guidelines for Writing Mathematical Proofs 512 Answers for the Progress Checks 517 Answers and Hints for Selected Exercises 557 List of Symbols 603 Index 603