Website for An Introduction to Mathematical Proofs
by Nick Loehr
The book is published by CRC Press.
You can order the book here.
Table of Contents and Preface
Book's Table of Contents and Preface.
Reader Feedback and Errata
If you have comments about the book or have discovered any errors,
please contact the author by e-mail (nloehr at vt dot edu).
List of Errata
Synopsis of Book
Chapter 1: Logic.
This chapter lays the logical foundations for the study of mathematical proofs.
First we study propositional logic, using truth tables to define the logical
connectives NOT, AND, OR, exclusive-OR, IF, and IFF. Truth tables establish
many logical rules, analogous to the laws of algebra, that help decide
when two statements are logically equivalent. Next we study properties
of IF-statements, pointing out how the converse and contrapositive are related
to the original statement. Many possible translations of IF and IFF are
presented and compared.
Then we define tautologies and contradictions, which play an important role
in propositional logic. The second part of the chapter deals with the logic
of quantifiers. Quantifying an open sentence (a sentence containing a variable)
produces a proposition that is true or false. We describe restricted and
unrestricted versions of the universal and existential quantifiers, along
with conversion rules and negation rules for these quantifiers. Many
translation examples are considered, and the issue of hidden quantifiers
is addressed. Then we develop the crucial skill of finding useful denials
of complex logical statements. The chapter ends with a discussion of uniqueness
and how this concept may be expressed in terms of simpler logical operations.
Chapter 2: Proofs.
This chapter begins with the elements of formal mathematical theories:
undefined terms, definitions, axioms, inference rules, theorems, and proofs.
After some initial advice on writing proofs, we study systematic rules
(called proof templates) for converting the logical structure of a given
statement into the outline of a proof of that statement. We examine proof
templates for proving existence statements (proof by example),
IF-statements (direct proof and contrapositive proof),
universal statements (generic-element proofs and proof by exhaustion),
IFF-statements (two-part proofs), AND-statements, and OR-statements.
Proof by contradiction is a powerful general proof method that proves
a given statement by assuming its negation and deducing a contradiction.
In contrast, we disprove a false statement by proving its negation.
Proof by cases lets us use a known or assumed OR-statement to prove
another statement. Throughout the chapter, we illustrate these proof
techniques with basic theorems and examples drawn from elementary number
theory and algebra. The chapter concludes with a detailed discussion of
rules for manipulating and proving statements that contain multiple quantifiers.
We see that the relative position of existential and universal quantifiers
has a big impact on what a statement means and how it is proved.
Chapter 3: Sets.
Set theory forms the foundation upon which all other mathematical theories
are built. This chapter covers basic concepts of set theory including
subsets, set equality, unions, intersections, product sets, power sets,
and indexed unions and intersections. After an informal introduction to sets,
we formally define basic set operations and introduce proof templates for
subset proofs and set equality proofs. We state and prove algebraic properties
of unions, intersections, and set differences. Two new proof techniques
(circle proofs and chain proofs) help prove the logical equivalence
of statements or the equality of sets. Examination of small sets (singletons,
unordered pairs, etc.) leads to the conclusion that order and repetition
do not matter for sets. Next we introduce ordered pairs and product sets
and prove their basic properties. Then we consider unions and intersections
of indexed collections of sets and describe set-builder notation. A final
optional section sketches the framework and initial axioms for a fully
axiomatic development of set theory (the Zermelo--Fraenkel--Choice system).
We formally state each axiom of ZFC (Extension, Specification, Pairs,
Power Sets, Unions, Empty Set, Infinity, Replacement, Choice, and Foundation)
and indicate the intuitive significance of the axioms and how they are used.
Chapter 4: Integers.
Mathematical induction is a powerful technique for proving statements that
hold for all positive integers. The chapter begins with a discussion of
recursive definitions, the Induction Axiom, and ordinary induction proofs.
We then develop variations of induction such as induction starting anywhere,
backwards induction, and strong induction. The second half of the chapter
uses these techniques to develop some basic results in number theory.
We prove the Division Theorem, which states that any integer can be
divided by a nonzero integer to produce a unique quotient and remainder.
This leads into a discussion of greatest common divisors and
Euclid's Algorithm (based on repeated division) for finding gcds and
writing gcd(a,b) as a linear combination of
a and b. The linear
combination property of gcds helps us prove the Fundamental Theorem
of Arithmetic, which asserts that every positive integer can be written
uniquely as a product of primes. An optional final section pursues these
ideas further, giving formulas for gcds and least common multiples in
terms of prime factorizations, proving a unique prime factorization theorem
for rational numbers, and characterizing which rational numbers have
rational nth roots.
Chapter 5: Relations and Functions.
This chapter begins with relations, which are sets of ordered pairs that
model mathematical relationships between inputs and outputs. Relations can
be visualized using arrow diagrams or graphs in the xy-plane. We study
concepts for relations including the image of a set under a relation,
identity relations, the inverse of a relation, and the composition of
relations. These concepts obey algebraic rules such as associativity,
monotonicity, and distributive laws. Next we define functions, which are
required to map each input in a given domain to exactly one output in
a given codomain. Using fractions and other examples, we show how to
check that a proposed function is well-defined (or single-valued).
Then we consider constant functions, inclusion functions,
identity functions, characteristic functions, and pointwise operations on
real-valued functions. A proof template for proving equality of functions
is developed. Next we study composition of functions, restriction of
functions, and the gluing operation. We continue by defining and proving
the basic properties of direct images, preimages, injections, surjections,
bijections, inverse functions, left inverses, and right inverses. In
particular, we show that a function is invertible iff it is a bijection.
Chapter 6: Equivalence Relations and Partial Orders.
This chapter studies equivalence relations and partial orderings,
which are abstractions of logical equality and the ordering on real numbers.
Three key properties of equality are isolated and generalized:
reflexivity, symmetry, and transitivity. Any relation with these
three properties is an equivalence relation. The set of objects
related to a given object under an equivalence relation is the
equivalence class of that object. Equivalence classes partition the
underlying set into a disjoint union of nonempty subsets. This leads
to the concept of set partitions. There is a natural correspondence
between equivalence classes on a set and set partitions of that set.
Equivalence relations can be used to build new algebraic structures.
As examples, the integers modulo n and the rational numbers are
constructed from the set of integers via appropriate equivalence relations.
The objects in these new number systems are equivalence classes.
When introducing algebraic operations on these objects, one must
check that the operations are well-defined.
The chapter also discusses partial ordering relations, which satisfy
the axioms of reflexivity, transitivity, and antisymmetry. Well-orderings
are defined, and the Induction Axiom is shown to be equivalent to
the fact that every nonempty set of positive integers has a least element.
Chapter 7: Cardinality.
The theory of cardinality provides a rigorous way to measure and compare
the size of arbitrary, possibly infinite sets. The key idea is that two
sets have the same cardinality if there is a bijection between them.
This definition has many surprising consequences for infinite sets.
On one hand, not all infinite sets have the same size; for instance,
the set of real numbers has strictly larger cardinality than the set
of integers. On the other hand, a proper subset of an infinite set
may have the same cardinality as the set itself. The chapter begins
in the more familiar setting of finite sets, proving combinatorial rules
for determining the size of the union or product of finite sets. Countably
infinite sets, which are sets in one-to-one correspondence with the set
of positive integers, are studied next. We show that finite products
and countable unions of countable sets are countable. Cantor's diagonal
argument furnishes specific examples of uncountable sets, such as sets
of sequences, intervals of real numbers, and the set of all sets of integers.
The chapter concludes by proving Cantor's Theorem and the
Schröder-Bernstein Theorem, along with the fact that there is no
set of all sets.
Chapter 8: Real Numbers.
This chapter develops algebraic and analytic properties of the real numbers
and other number systems starting from the axioms for a complete ordered field.
After laying out the undefined terms and the nineteen axioms, logical
consequences of these axioms are systematically deduced. First we prove
algebraic properties of real numbers including cancellation laws, lack
of zero divisors, sign rules, properties of multiplicative inverses,
and formulas for computing with fractions. We define the set
ℕ of natural
numbers as the intersection of all inductive subsets of
ℝ, leading to
a proof of the Induction Axiom and its variations. Then we give formal
constructions of
ℤ (the integers) and
ℚ (the rational numbers) and
prove closure properties for these number systems. Next we establish
properties of inequalities, absolute value, and distance. The final section
undertakes a detailed study of the Completeness Axiom, which states
(intuitively) that the real number system has no holes. We prove consequences
of this axiom including the Archimedean ordering property, existence
of maximum and minimum elements for bounded subsets of
ℤ, the distribution
of integers and rational numbers in
ℝ, the nested interval property,
and the existence of real square roots.
This page was last updated December 2019.