An Introduction to Mathematical Reasoning: Numbers, Sets and Functions

✍ Scribed by Peter J. Eccles

• Publisher: Cambridge University Press
• Year: 1998
• Tongue: English
• Leaves: 365
• Edition: 1
• Category: Library

✦ Synopsis

This book eases students into the rigors of university mathematics. The emphasis is on understanding and constructing proofs and writing clear mathematics. The author achieves this by exploring set theory, combinatorics, and number theory, topics that include many fundamental ideas and may not be a part of a young mathematician's toolkit. This material illustrates how familiar ideas can be formulated rigorously, provides examples demonstrating a wide range of basic methods of proof, and includes some of the all-time-great classic proofs. The book presents mathematics as a continually developing subject. Material meeting the needs of readers from a wide range of backgrounds is included. The over 250 problems include questions to interest and challenge the most able student but also plenty of routine exercises to help familiarize the reader with the basic ideas.

✦ Table of Contents

Cover
Publication Data
Contents
Preface
Part I: Mathematical statements and proofs
1. The language of mathematics
1.1 Mathematical statements
1.2 Logical connectives
Exercises
2. Implications
2.1 Implications
2.2 Arithmetic
2.3 Mathematical truth
Exercises
3. Proofs
3.1 Direct proofs
3.2 Constructing proofs backwards
Exercises
4. Proof by contradiction
4.1 Proving negative statements by contradiction
4.2 Proving implications by contradictions
4.3 Proof by contrapositive
4.4 Proving 'or' statements
Exercises
5. The induction principle
5.1 Proof by induction
5.2 Changing the base case
5.3 Definition by induction
5.4 The strong induction principle
Exercises
Problems I: Mathematical statements and proofs
Part II: Sets and functions
6. The language of set theory
6.1 Sets
6.2 Operations on sets
6.3 The power set
Exercises
7. Quantifiers
7.1 Universal statements
7.2 Existential statements
7.3 Proving statements involving quantifiers
7.4 Disproving statements involving quantifiers
7.5 Proof by induction
7.6 Predicates involving more than one free variable
7.7 Quantifiers
Exercises
8. Functions
8.1 Functions and formulae
8.2 Composition of functions
8.3 Sequences
8.4 The image of a function
8.5 The graph of a function
Exercises
9. Injections, surjections and bijections
9.1 Properties of functions
9.2 Bijections and inverses
9.3 Functions and subsets
Exercises
Problems II: Sets and functions
Part III: Numbers and counting
10. Counting
10.1 Counting finite sets
10.2 Two basic counting principles
Exercises
11. Properties of finite sets
11. The pigeonhole principle
11.2 Finite sets of real numbers
11.3 Two applications of finiteness
Exercises
12. Counting functions and subsets
12.1 Counting sets of functions
12.2 Counting sets of subsets
12.3 The binomial theorem
Exercises
13. Number systems
13.1 The rational numbers
13.2 The irrationality of √2
13.3 Real numbers and infinite decimals
Exercises
14. Counting infinite sets
14.1 Countable sets
14.2 Denumerable sets
14.3 Uncountable sets
Exercises
Problems III: Numbers and counting
Part IV: Arithmetic
15. The division theorem
15.1 The division theorem
15.2 Some applications
Exercises
16. The Euclidean algorithm
16.1 Finding the greatest common divisor
16.2 The Euclidean algorithm
Exercises
17. Consequences of the Euclidean algorithm
17.1 Integral linear combinations
17.2 An alternative definition of the greatest common divisor
17.3 Coprime pairs
Exercises
18. Linear diophantine equations
18.1 Diophantine equations
18.2 A condition for the existence of solutions
18.3 Finding all the solutions - the homogeneous case
18.4 Finding all the solutions - the general case
Exercises
Problems IV: Arithmetic
Part V: Modular arithmetic
19. Congruence of integers
19.1 Basic definitions
19.2 The remainder map
19.3 Division in congruences
Exercises
20. Linear congruences
20.1 A criterion for the existence of solutions
20.2 Linear congruences and diophantine equations
Exercises
21. Congruence classes and the arithmetic of remainders
21.1 Congruence classes
21.2 The arithmetic of congruence classes
21.3 The arithmetic of remainders
21.4 Linear diophantine equations
Exercises
22. Partitions and equivalence relations
22.1 Partitions
22.2 Equivalence relations
22.3 Equivalence relations and partitions
Exercises
Problems V: Modular arithmetic
Part VI: Prime numbers
23. The sequence of prime numbers
23.1 Definition and basic properties
23.2 The sieve of Eratosthenes
23.3 The fundamental theorem of arithmetic
23.4 Applications of the fundamental theorem of arithmetic
23.5 The distribution of prime numbers
Exercises
24. Congruence modulo a prime
24.1 Fermat's little theorem
24.2 Wilson's theorem
24.3 Looking for primes
Exercises
Problems VI: Prime numbers
Solutions to exercises
Bibliography: suggestions for further reading
List of symbols
Index
Corrections