You are previewing An Introduction to Mathematical Reasoning.
O'Reilly logo
An Introduction to Mathematical Reasoning

Book Description

The purpose of this book is to introduce the basic ideas of mathematical proof to students embarking on university mathematics. The emphasis is on helping the reader in understanding and constructing proofs and writing clear mathematics. This is achieved by exploring set theory, combinatorics and number theory, topics which include many fundamental ideas which are part of the tool kit of any mathematician. 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 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. Over 250 problems include questions to interest and challenge the most able student as well as plenty of routine exercises to help familiarize the reader with the basic ideas.

Table of Contents

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