 Last updated
 Save as PDF
 Page ID
 99062
 Bob Dumas and John E. McCarthy
 University of Washington and Washington University in St. Louis
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}}}\)
\( \newcommand{\vecd}[1]{\overset{\!\!\rightharpoonup}{\vphantom{a}\smash{#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\ #1 \}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\ #1 \}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}}}\)
\( \newcommand{\vectorC}[1]{\textbf{#1}}\)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}}\)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}}\)
\( \newcommand{\vectE}[1]{\overset{\!\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}}}\)
\( \newcommand{\vecd}[1]{\overset{\!\!\rightharpoonup}{\vphantom{a}\smash{#1}}} \)
The primary activity of research mathematicians is proving mathematical claims. Depending on the depth of the claim, the relationship of the claim to other mathematical claims, and various other factors, a mathematical statement that has been proved is generally called a theorem, proposition, corollary or lemma. A mathematical statement that has not been proved, but that is expected to be true, is commonly called a conjecture. A statement that is accepted as a starting point for arguments without being proved is called an axiom.
Some mathematical results are so fundamental, deep, difficult, surprising or otherwise noteworthy that they are named. Part of your initiation as a member of the community of mathematicians is becoming familiar with some of these named statements  and we shall prove a few of them in this book.
It is likely that most of the mathematics you have studied has been the application of theorems to deriving solutions of relatively concrete problems. Here we begin learning how to prove theorems. Most students find the transition from computational mathematics to mathematical proofs very challenging.
The nature of a mathematical proof depends on the context. There is a formal notion of a mathematical proof:
A finite sequence of formal mathematical statements such that each statement either

is an axiom or assumption, or

follows by formal rules of logical deduction from previous statements in the sequence.
Most mathematicians do not think of mathematical proofs as formal mathematical proofs, and virtually no mathematician writes formal mathematical proofs. This is because a formal proof is a hopelessly cumbersome thing, and is generally outside the scope of human capability, even for the most elementary mathematical statements. Rather, mathematicians write proofs that are sequences of statements in a combination of natural language and formal mathematical symbols (interspersed with diagrams, questions, references and other devices that are intended to assist the reader in understanding the proof) that can be thought of as representing a purely formal argument. A good practical definition of a mathematical proof is:
An argument in favor of a mathematical statement that will convince the preponderance of knowledgeable mathematicians of the truth of the mathematical statement.
This definition is somewhat imprecise, and mathematicians can disagree on whether an argument is a proof, particularly for extremely difficult or deep arguments. However, for virtually all mathematical arguments, after some time for careful consideration, the mathematical community reaches a unanimous consensus on whether it is a proof.
The notion of a mathematical proof for the student is similar to the general idea of a mathematical proof. The differences are due to the type of statement that the student is proving, and the reasons for requesting that the student prove the statement. The statements that you will be proving are known to professional mathematicians or can be proved with relatively little effort by your instructors. Clearly the statements you will be proving require different conditions for a satisfactory proof than those stated above for the professional mathematician. Let’s define a successful argument by the student as follows: An argument for a mathematical statement that

the instructor can understand

the instructor cannot refute

uses only assumptions that the instructor considers admissible.
Note that refuting an argument is not the same as refuting the original claim. The sentence "The square of every real number is nonnegative because all real numbers are nonnegative." is a false proof of a true statement. The sentence "The square of every real number is nonnegative because all triangles have three sides." fails the first test: while both statements are true, your instructor will not see how the first follows from the second.
In this book, the solutions to the problems will be an exposition in natural language enhanced by mathematical expressions. The student is expected to learn the conventions of mathematical grammar and argument, and use them. Like most conventions, these are often determined by tradition or precedent. It can be quite difficult, initially, to determine whether your mathematical exposition meets the standards of your instructor. Practice, with feedback from a reader experienced in reading mathematics, is the best way to develop good proofwriting skills. Remember, readers of mathematics are quite impatient with trying to decipher what the author means to say  mathematics is sufficiently challenging when the author writes precisely what he or she intends. Most of the burden of communication is on the author of a mathematical proof, not the reader. A proof can be logically correct, but so difficult to follow that it is unacceptable to your instructor.
Why are proofs the primary medium of mathematics? Mathematicians depend on proofs for certainty and explanation. Once a proof is accepted by the mathematical community, it is virtually unheard of that the result is subsequently refuted. This was not always the case: in the \(19^{\text {th }}\) century there were serious disputes as to whether results had really been proved or not (see Section \(5.3\) for an example, and the book [4] for a very extensive treatment of the development of rigor in mathematical reasoning). This led to our modern notion of a "rigorous" mathematical argument. While one might argue that it is possible that in the \(21^{\text {st }}\) century a new standard of rigor will reject what we currently consider to be proofs, our current ideas have been stable for over a century, and most mathematicians (including the authors of this book) do not expect that there will be a philosophical shift.
For very complicated results, writing a detailed proof helps the author convince himself or herself of the truth of the claim. After a mathematician has hit upon the key idea behind an argument, there is a lot of hard work left developing the details of the argument. Many promising ideas fail as the author attempts to write a detailed argument based on the idea. Finally, proofs often provide a deeper insight into the result and the mathematical objects that are the subject of the proof. Indeed, even very clever proofs which fail to provide mathematical insights are held in lower regard, by some, than arguments that elucidate the topic.
Mathematical proofs are strongly related to formal proofs in a purely logical sense. It is supposed that the existence of an informal mathematical proof is overwhelming evidence for the existence of a formal mathematical proof. If it is not clear that the informal proof could conceivably be interpreted into a formal argument, it is doubtful that the informal argument will be accepted by the mathematical community. Consequently, mathematical arguments have a transparent underlying logical structure.
For this reason we shall begin our discussion of mathematical proofs with a brief discussion of propositional logic. Despite its abstractness, the topic is straightforward, and most of the claims of this section may be confirmed with some careful, patient thinking.