Introduction To Mathematical Structures And Proofs Solutions Pdf

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.

Solutions to Selected Problems from the Book

Chapter 1
Chapter 2
Chapter 3
Chapter 4
Chapter 5: COMING LATER.
Chapter 6
Chapter 7

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.