An Introduction to Mathematical Proofs

Nicholas A. Loehr

• Publisher: CRC Press
• Year: 2019
• Print ISBN: 9780367338237
• eBook ISBN: 9781000709803
• Edition: 1
• Topic: Mathematics
• Subtopic: Applied Mathematics
• Index: Mathematics

An Introduction to Mathematical Proofs presents fundamental material on logic, proof methods, set theory, number theory, relations, functions, cardinality, and the real number system. The text uses a methodical, detailed, and highly structured approach to proof techniques and related topics. No prerequisites are needed beyond high-school algebra.

New material is presented in small chunks that are easy for beginners to digest. The author offers a friendly style without sacrificing mathematical rigor. Ideas are developed through motivating examples, precise definitions, carefully stated theorems, clear proofs, and a continual review of preceding topics.

Features

• Study aids including section summaries and over 1100 exercises
• Careful coverage of individual proof-writing skills
• Proof annotations and structural outlines clarify tricky steps in proofs
• Thorough treatment of multiple quantifiers and their role in proofs
• Unified explanation of recursive definitions and induction proofs, with applications to greatest common divisors and prime factorizations

About the Author:

Nicholas A. Loehr is an associate professor of mathematics at Virginia Technical University. He has taught at College of William and Mary, United States Naval Academy, and University of Pennsylvania. He has won many teaching awards at three different schools. He has published over 50 journal articles. He also authored three other books for CRC Press, including Combinatorics, Second Edition, and Advanced Linear Algebra.

1

Logic

1.1 Propositions, Logical Connectives, and Truth Tables

Many people despise mathematics, believing it to be nothing more than a confusing jumble of arcane formulas and mind-numbing computations. This depressing view of the subject is understandable, when we consider how math is presented in grade school and many calculus classes. But in truth, mathematics is a beautiful, intricately structured tower of knowledge built up from a small collection of basic statements (called axioms) using the laws of logic. In this book, we shall study the foundation of this tower, as shown here:

⋮ cardinality functions relations integers sets proofs logic

Propositions

We begin with propositional logic, which studies how the truth of a complex statement is determined by the truth or falsehood of its parts.

1.1. Definition: Propositions. A proposition is a statement that is either true or false, but not both.

Many things we say are not propositions, as seen in the next example.

1.2. Example. Which of these statements are propositions?

(a) 7 is positive.

(b) 1 + 1 = 7.

(c) Memorize all definitions.

(d) Okra tastes great.

(e) Is it raining?

(f) This sentence is false.

(g) Paris is a city and 2 + 2 is not 4, or Paris is not a city and 2 + 2 is 4.

Solution. Statement (a) is a true proposition. Statement (b) is a false proposition. Commands, opinions, and questions do not have a truth value, so statements (c) through (e) are not propositions. Statement (f) is an example of a paradox: if you assume this statement is true, then the statement itself asserts that it is false. If you instead assume the statement is false, then the statement is also true. Since propositions...

Table of contents

• Cover
• Half Title
• Series Page
• Title Page
• Copyright Page
• Dedication
• Contents
• Preface
• 1. Logic
• 2. Proofs
• Review of Logic and Proofs
• 3. Sets
• 4. Integers
• Review of Set Theory and Integers
• 5. Relations and Functions
• 6. Equivalence Relations and Partial Orders
• 7. Cardinality
• Review of Functions, Relations, and Cardinality
• 8. Real Numbers (Optional)
• Index