Book of Proof

Description

This book is an introduction to the language and standard proof methods of mathematics. It is a bridge from the computational courses (such as calculus or differential equations) that students typically encounter in their first year of college to a more abstract outlook. It lays a foundation for more theoretical courses such as topology, analysis and abstract algebra. Although it may be more meaningful to the student who has had some calculus, there is really no prerequisite other than a measure of mathematical maturity. Topics include sets, logic, counting, methods of conditional and non-conditional proof, disproof, induction, relations, functions, calculus proofs and infinite cardinality. Preface Introduction I Fundamentals Sets Introduction to Sets The Cartesian Product Subsets Power Sets Union, Intersection, Difference Complement Venn Diagrams Indexed Sets Sets That Are Number Systems Russell's Paradox Logic Statements And, Or, Not Conditional Statements Biconditional Statements Truth Tables for Statements Logical Equivalence Quantifiers More on Conditional Statements Translating English to Symbolic Logic Negating Statements Logical Inference An Important Note Counting Lists The Multiplication Principle The Addition and Subtraction Principles Factorials and Permutations Counting Subsets Pascal's Triangle and the Binomial Theorem The Inclusion-Exclusion Principle Counting Multisets The Division and Pigeonhole Principles Combinatorial Proof II How to Prove Conditional Statements Direct Proof Theorems Definitions Direct Proof Using Cases Treating Similar Cases Contrapositive Proof Contrapositive Proof Congruence of Integers Mathematical Writing Proof by Contradiction Proving Statements with Contradiction Proving Conditional Statements by Contradiction Combining Techniques Some Words of Advice III More on Proof Proving Non-Conditional Statements If-and-Only-If Proof Equivalent Statements Existence Proofs; Existence and Uniqueness Proofs Constructive Versus Non-Constructive Proofs Proofs Involving Sets How to Prove aA How to Prove AB How to Prove A= B Examples: Perfect Numbers Disproof Counterexamples Disproving Existence Statements Disproof by Contradiction Mathematical Induction Proof by Induction Proof by Strong Induction Proof by Smallest Counterexample The Fundamental Theorem of Arithmetic Fibonacci Numbers IV Relations, Functions and Cardinality Relations Relations Properties of Relations Equivalence Relations Equivalence Classes and Partitions The Integers Modulo n Relations Between Sets Functions Functions Injective and Surjective Functions The Pigeonhole Principle Revisited Composition Inverse Functions Image and Preimage Proofs in Calculus The Triangle Inequality Definition of a Limit Limits That Do Not Exist Limit Laws Continuity and Derivatives Limits at Infinity Sequences Series Cardinality of Sets Sets with Equal Cardinalities Countable and Uncountable Sets Comparing Cardinalities The Cantor-Bernstein-Schröder Theorem Conclusion Solutions Index