BUILDING PROOFS : A Practical Guide

Title:

Personal Author:

Oliveira, Suely

Physical Description:

x, 164 pages : illustrations ; 24 cm.

ISBN:

9789814641296

Subject Term:

Proof theory

Logic, Symbolic and mathematical

Mathematics

Added Author:

Stewart, David E., (David Edward), 1961-

Available:*

Library	Item Barcode	Call Number	Material Type	Item Category 1	Status
Searching... Razak School	33000000002343	QA9.54 O46 2015	Open Access Book	Book	Searching... Unknown

This book introduces students to the art and craft of writing proofs, beginning with the basics of writing proofs and logic, and continuing on with more in-depth issues and examples of creating proofs in different parts of mathematics, as well as introducing proofs-of-correctness for algorithms. The creation of proofs is covered for theorems in both discrete and continuous mathematics, and in difficulty ranging from elementary to beginning graduate level.Just beyond the standard introductory courses on calculus, theorems and proofs become central to mathematics. Students often find this emphasis difficult and new. This book is a guide to understanding and creating proofs. It explains the standard "moves" in mathematical proofs: direct computation, expanding definitions, proof by contradiction, proof by induction, as well as choosing notation and strategies.

Preface	p. v
1 Getting started	p. 1
1.1 A first example	p. 1
1.2 The starting line: definitions and axioms	p. 4
1.2.1 Definitions	p. 5
1.2.2 Axioms	p. 6
1.3 Matching and dummy variables	p. 7
1.3.1 Matching up expressions	p. 7
1.3.2 Moving to the goal	p. 9
1.3.3 Dummy variables	p. 11
1.4 Proof by contradiction	p. 13
1.5 "If and only if"	p. 17
1.6 Drawing pictures	p. 18
1.6.1 Pythagoras' theorem - picture version	p. 18
1.6.2 Eulerian paths and the bridges of Koenigsberg	p. 20
1.7 Notation	p. 22
1.7.1 Choosing names	p. 22
1.7.2 Introducing new notation	p. 23
1.7.3 Sub-scripts, super-scripts, and decorations	p. 24
1.8 More examples of proofs*	p. 24
1.8.1 Composition of continuous functions	p. 24
1.8.2 Sums of squares	p. 26
1.9 Exercises	p. 27
2 Logic and other formalities	p. 31
2.1 Propositional calculus	p. 32
2.1.1 Propositional logic and truth tables	p. 32
2.1.2 Precedence	p. 33
2.1.3 Truth tables	p. 34
2.1.4 Tautologies	p. 34
2.1.5 Rules of inference	p. 35
2.1.6 Implication via assumption*	p. 36
2.1.7 Inference steps	p. 36
2.1.8 The algebra of propositions	p. 37
2.1.9 Boolean algebra	p. 38
2.2 Expressions, predicates, and quantifiers	p. 39
2.3 Rules of inference	p. 41
2.3.1 Rules of inference for propositional calculus	p. 41
2.3.2 Rules of inference with quantifiers	p. 41
2.4 Axioms of equality and inequality	p. 42
2.5 Dealing with sets	p. 43
2.5.1 Set operations	p. 44
2.5.2 Special sets	p. 45
2.5.3 Functions	p. 45
2.6 Proof by induction	p. 46
2.6.1 Some sums	p. 48
2.6.2 Fibonacci numbers	p. 49
2.6.3 Egyptian fractions	p. 50
2.7 Proofs and algorithms	p. 52
2.7.1 Correctness by design*	p. 56
2.8 Exercises	p. 59
3 Discrete and continuous	p. 63
3.1 Inequalities	p. 63
3.1.1 Some classic inequalities	p. 64
3.1.2 Convex functions	p. 66
3.2 Some proofs in number theory	p. 69
3.2.1 Division algorithm and gcd	p. 69
3.2.2 Prime numbers	p. 73
3.2.3 "There are infinitely many primes"	p. 74
3.3 Calculate the same thing in two different ways	p. 75
3.3.1 Sums of degrees in graphs	p. 76
3.3.2 The integral $$$ exp(-x 2 ) dx	p. 77
3.4 Abstraction and algebra	p. 78
3.5 Swapping sums, swapping integrals	p. 82
3.5.1 The exponential function	p. 82
3.5.2 Taylor's theorem with remainder	p. 84
3.6 Emphasizing the important	p. 86
3.6.1 Equivalence relations and well-defined definitions	p. 86
3.7 Graphs and networks	p. 90
3.8 Real numbers and convergence	p. 96
3.8.1 The Least Upper Bound property	p. 96
3.8.2 Convergence of infinite sums	p. 98
3.8.3 Different kinds of convergence	p. 100
3.8.4 "Give an e of room..."	p. 102
3.9 Approximating or building "bad" things with "nice" tilings	p. 103
3.10 Exercises	p. 107
4 More advanced proof-making	p. 113
4.1 Counterexamples and proofs	p. 113
4.1.1 Minimizing functions of one variable	p. 113
4.1.2 Interchanging limits	p. 115
4.2 Dealing with the infinite	p. 116
4.2.1 Rearrangements of conditionally convergent series	p. 116
4.2.2 Shift operators	p. 118
4.3 Bootstrapping	p. 119
4.3.1 For square matrices, det(AB) = dct(A) det(B)	p. 120
4.4 Impredicative definitions	p. 121
4.5 Diagonal proofs	p. 126
4.5.1 Russell paradox	p. 127
4.5.2 Godel's incompleteness theorem	p. 128
4.6 Using duality	p. 129
4.6.1 Duality in linear algebra	p. 130
4.7 Optimizing	p. 132
4.7.1 Holder inequalities	p. 133
4.7.2 Huffman coding	p. 136
4.8 Generating function	p. 141
4.8.1 Recurrences and generating functions	p. 141
4.8.2 Catalan numbers	p. 143
4.9 Exercises	p. 144
5 Building theories	p. 149
5.1 Choosing definitions	p. 149
5.2 What am I modeling?	p. 150
5.2.1 Generalizing known concepts	p. 151
5.3 Converting one kind of mathematics into another	p. 152
5.4 What is an interesting question?	p. 153
5.5 Exercises	p. 155
Bibliography	p. 159
Index	p. 161

Available:*

On Order

Summary

Summary

Table of Contents