Mathematical Reasoning: Writing and Proof (PreTeXt Edition)

Subsection Some Mathematical Terminology

In Section 1.2, we introduced the idea of a direct proof. Since then, we have used some common terminology in mathematics without much explanation. Before we proceed further, we will discuss some frequently used mathematical terms.

A proof in mathematics is a convincing argument that some mathematical statement is true. A proof should contain enough mathematical detail to be convincing to the person(s) to whom the proof is addressed. In essence, a proof is an argument that communicates a mathematical truth to another person (who has the appropriate mathematical background). A proof must use correct, logical reasoning and be based on previously established results. These previous results can be axioms, definitions, or previously proven theorems. These terms are discussed below.

Surprising to some is the fact that in mathematics, there are always undefined terms. This is because if we tried to define everything, we would end up going in circles. Simply put, we must start somewhere. For example, in Euclidean geometry, the terms “point,” “line,” and “contains” are undefined terms. In this text, we are using our number systems such as the natural numbers and integers as undefined terms. We often assume that these undefined objects satisfy certain properties. These assumed relationships are accepted as true without proof and are called axioms (or postulates). An axiom is a mathematical statement that is accepted without proof. Euclidean geometry starts with undefined terms and a set of postulates and axioms. For example, the following statement is an axiom of Euclidean geometry:

Given any two distinct points, there is exactly one line that contains these two points.

A definition is simply an agreement as to the meaning of a particular term. For example, in this text, we have defined the terms “even integer” and “odd integer.” Definitions are not made at random, but rather, a definition is usually made because a certain property is observed to occur frequently. As a result, it becomes convenient to give this property its own special name. Definitions that have been made can be used in developing mathematical proofs. In fact, most proofs require the use of some definitions.

In dealing with mathematical statements, we frequently use the terms “conjecture,” “theorem,” “proposition,” “lemma,” and “corollary.” A conjecture is a statement that we believe is plausible. That is, we think it is true, but we have not yet developed a proof that it is true. A theorem is a mathematical statement for which we have a proof. A term that is often considered to be synonymous with “theorem” is proposition. Often the proof of a theorem can be quite long. In this case, it is often easier to communicate the proof in smaller “pieces.” These supporting pieces are often called lemmas. A lemma is a true mathematical statement that was proven mainly to help in the proof of some theorem. Once a given theorem has been proven, it is often the case that other propositions follow immediately from the fact that the theorem is true. These are called corollaries of the theorem. The term corollary is used to refer to a theorem that is easily proven once some other theorem has been proven.

Subsection Constructing Mathematical Proofs

To create a proof of a theorem, we must use correct logical reasoning and mathematical statements that we already accept as true. These statements include axioms, definitions, theorems, lemmas, and corollaries.

In Section 1.2, we introduced the use of a know-show table to help us organize our work when we are attempting to prove a statement. We also introduced some guidelines for writing mathematical proofs once we have created the proof. These guidelines should be reviewed before proceeding.

Please remember that when we start the process of writing a proof, we are essentially “reporting the news.” That is, we have already discovered the proof, and now we need to report it. This reporting often does not describe the process of discovering the news (the investigative portion of the process).

Quite often, the first step is to develop a conjecture. This is often done after working within certain objects for some time. This is what we did in Beginning Activity 1 when we used examples to provide evidence that the following conjecture is true:

Conjecture

Let \(a\text{,}\) \(b\text{,}\) and \(c\) by integers with \(a \ne 0\) and \(b \ne 0\text{.}\) If \(a\) divides \(b\) and \(b\) divides \(c\text{,}\) then \(a\) divides \(c\text{.}\)

Before we try to prove a conjecture, we should make sure we have explored some examples. This simply means to construct some specific examples where the integers \(a\text{,}\) \(b\text{,}\) and \(c\) satisfy the hypothesis of the conjecture in order to see if they also satisfy the conclusion. We did this for this conjecture in Beginning Activity 1.

We will now start a know-show table for this conjecture.

The backward question we ask is, “How can we prove that \(a\) divides \(c\text{?}\)” One answer is to use the definition and show that there exists an integer \(q\) such that \(c = a \cdot q\text{.}\) This could be step \(Q1\) in the know-show table.

We now have to prove that a certain integer \(q\) exists, so we ask the question, “How do we prove that this integer exists?” When we are at such a stage in the backward process of a proof, we usually turn to what is known in order to prove that the object exists or to find or construct the object we are trying to prove exists. We often say that we try to “construct” the object or at least prove it exists from the known information. So at this point, we go to the forward part of the proof to try to prove that there exists an integer \(q\) such that \(c = a \cdot q\text{.}\)

The forward question we ask is, “What can we conclude from the facts that \(a \mid b\) and \(b \mid c\text{?}\)” Again, using the definition, we know that there exist integers \(s\) and \(t\) such that \(b = a \cdot s\) and \(c = b \cdot t\text{.}\) This could be step \(P1\) in the know-show table.

The key now is to determine how to get from \(P1\) to \(Q1\text{.}\) That is, can we use the conclusions that the integers \(s\) and \(t\) exist in order to prove that the integer \(q\) (from the backward process) exists. Using the equation \(b = a \cdot s\text{,}\) we can substitute \(a \cdot s\) for \(b\) in the second equation, \(c = b \cdot t\text{.}\) This gives

The last step used the associative property of multiplication. (See Table 1.9.) This shows that \(c\) is equal to \(a\) times some integer. (This is because \(s \cdot t\) is an integer by the closure property for integers.) So although we did not use the letter \(q\text{,}\) we have arrived at step \(Q1\text{.}\) The completed know-show table follows.

Notice the similarities between what we did for this proof and many of the proofs about even and odd integers we constructed in Section 1.2. When we try to prove that a certain object exists, we often use what is called the construction method for a proof. The appearance of an existential quantifier in the show (or backward) portion of the proof is usually the indicator to go to what is known in order to prove the object exists.

We can now report the news by writing a formal proof.

Subsection Writing Guidelines for Equation Numbers

We wrote the proof for Theorem 3.1 according to the guidelines introduced in Section 1.2, but a new element that appeared in this proof was the use of equation numbers. Following are some guidelines that can be used for equation numbers.

If it is necessary to refer to an equation later in a proof, that equation should be centered and displayed. It should then be given a number. The number for the equation should be written in parentheses on the same line as the equation at the right-hand margin as in shown in the following example.

Since \(x\) is an odd integer, there exists an integer \(n\) such that

Later in the proof, there may be a line such as

Then, using the result in equation (3), we obtain ….

Subsection Using Counterexamples

In Section 1.2 and so far in this section, our focus has been on proving statements that involve universal quantifiers. However, another important skill for mathematicians is to be able to recognize when a statement is false and then to be able to prove that it is false. For example, suppose we want to know if the following proposition is true or false.

For each integer \(n\text{,}\) if 5 divides \(\left(n^2 - 1 \right)\text{,}\) then 5 divides \(\left( n - 1 \right)\text{.}\)

Suppose we start trying to prove this proposition. In the backward process, we would say that in order to prove that 5 divides \(\left( n - 1 \right)\text{,}\) we can show that there exists an integer \(k\) such that

For the forward process, we could say that since 5 divides \(\left(n^2 - 1 \right)\text{,}\) we know that there exists an integer \(m\) such that

The problem is that there is no straightforward way to use \(P_1\) to prove \(Q_1\text{.}\) At this point, it would be a good idea to try some examples for \(n\) and try to find situations in which the hypothesis of the proposition is true. (In fact, this should have been done before we started trying to prove the proposition.) The following table summarizes the results of some of these explorations with values for \(n\text{.}\)

We can stop exploring examples now since the last row in the table provides an example where the hypothesis is true and the conclusion is false. Recall from Section 2.4 (see Counterexamples and Negations of Conditional Statements) that a counterexample for a statement of the form \(\left( \forall x \in U \right) \left( P(x) \right)\) is an element \(a\) in the universal set for which \(P(a)\) is false. So we have actually proved that the negation of the proposition is true.

When using a counterexample to prove a statement is false, we do not use the term “proof” since we reserve a proof for proving a proposition is true. We could summarize our work as follows:

Subsection Congruence

What mathematicians call congruence is a concept used to describe cycles in the world of the integers. For example, the day of the week is a cyclic phenomenon in that the day of the week repeats every seven days. The time of the day is a cyclic phenomenon because it repeats every 12 hours if we use a 12-hour clock or every 24 hours if we use a 24-hour clock. We explored these two cyclic phenomena in Beginning Activity 2.

Similar to what we saw in Beginning Activity 2, if it is currently Monday, then it will be Wednesday 2 days from now, 9 days from now, 16 days from now, 23 days from now, and so on. In addition, it was Wednesday 5 days ago, 12 days ago, 19 days ago, and so on. Using negative numbers for time in the past, we generate the following list of numbers:

Notice that if we subtract any number in the list above from any other number in that list, we will obtain a multiple of 7. For example,

Using the concept of congruence, we would say that all the numbers in this list are congruent modulo 7, but we first have to define when two numbers are congruent modulo some natural number \(n\text{.}\)

This means that in order to find integers that are congruent to \(b\) modulo \(n\text{,}\) we only need to add multiples of \(n\) to \(b\text{.}\) For example, to find integers that are congruent to 2 modulo 5, we add multiples of 5 to 2. This gives the following list:

We can also write this using set notation and say that

We will study the concept of congruence modulo \(n\) in much more detail later in the text. For now, we will work with the definition of congruence modulo \(n\) in the context of proofs. For example, all of the examples used in Progress Check 3.4 should provide evidence that the following proposition is true.

Subsection Additional Writing Guidelines

We will now be writing many proofs, and it is important to make sure we write according to accepted guidelines so that our proofs may be understood by others. Some writing guidelines were introduced in Chapter 1. The first four writing guidelines given below can be considered general guidelines, and the last three can be considered as technical guidelines specific to writing in mathematics.

1. Know Your Audience.

   Every writer should have a clear idea of the intended audience for a piece of writing. In that way, the writer can give the right amount of information at the proper level of sophistication to communicate effectively. This is especially true for mathematical writing. For example, if a mathematician is writing a solution to a textbook problem for a solutions manual for instructors, the writing would be brief with many details omitted. However, if the writing was for a students' solution manual, more details would be included.

2. Use complete sentences and proper paragraph structure.

   Good grammar is an important part of any writing. Therefore, conform to the accepted rules of grammar. Pay careful attention to the structure of sentences. Write proofs using complete sentences but avoid run-on sentences. Also, do not forget punctuation, and always use a spell checker when using a word processor.

3. Keep it simple.

   It is often difficult to understand a mathematical argument no matter how well it is written. Do not let your writing help make it more difficult for the reader. Use simple, declarative sentences and short paragraphs, each with a simple point.

4. Write a first draft of your proof and then revise it.

   Remember that a proof is written so that readers are able to read and understand the reasoning in the proof. Be clear and concise. Include details but do not ramble. Do not be satisfied with the first draft of a proof. Read it over and refine it. Just like any worthwhile activity, learning to write mathematics well takes practice and hard work. This can be frustrating. Everyone can be sure that there will be some proofs that are difficult to construct, but remember that proofs are a very important part of mathematics. So work hard and have fun.

5. Do not use \(*\) for multiplication or ^ for exponents.

   Leave this type of notation for writing computer code. The use of this notation makes it difficult for humans to read. In addition, avoid using \(/\) for division when using a complex fraction.

   For example, it is very difficult to read \(\left(x^3 -3x^2 + 1/2 \right)\!/\!\left(2x/3 - 7\right)\text{;}\) the fraction

   \begin{equation*} \frac{x^3 - 3x^2 +\dfrac{1}{2}}{\dfrac{2x}{3} - 7} \end{equation*}

   is much easier to read.

6. Do not use a mathematical symbol at the beginning of a sentence..

   For example, we should not write, “Let \(n\) be an integer. \(n\) is an odd integer provided that … .” Many people find this hard to read and often have to re-read it to understand it. It would be better to write, “An integer \(n\) is an odd integer provided that … .”

7. Use English and minimize the use of cumbersome notation.

   Do not use the special symbols for quantifiers \(\forall\) (for all), \(\exists\) (there exists), \(\mathrel\backepsilon\) (such that), or \(\therefore\) (therefore) in formal mathematical writing. It is often easier to write, and usually easier to read, if the English words are used instead of the symbols. For example, why make the reader interpret

   \begin{equation*} \left( \forall x \in \R \right) \left( \exists y \in \R \right)\left( x + y = 0 \right) \end{equation*}

   when it is possbile to write

   For each real number \(x\text{,}\) there exists a real number \(y\) such that \(x + y = 0\text{,}\)

   or, more succinctly (if appropriate),

   Every real number has an additive inverse.