Discrete Math

Subsection 5.1.1 Introduction to Proof

The goal of a proof is to logically convince the reader that the statement is true.

In fact, the history of proofs goes back to the ancient Greeks. The ancient Greeks were one of the first to believe that it was desirable to prove statements and theorems from more simpler facts.

Subsection 5.1.2 Proof Terminology

For example, some axioms could be:

• The sum, difference, and product of integers, is an integer. In other words, if \(n, m \in \mathbb{Z}\text{,}\) then \(n + m, n - m, -n, -m, nm \in \mathbb{Z}\text{.}\)

• If \(x \in \mathbb{R}\text{,}\) then \(x^2 \geq 0\text{.}\)

• If \(a, b \in \mathbb{R}\text{,}\) and \(a \neq 0\) and \(b \neq 0\text{,}\) then \(ab \neq 0\text{.}\)

“A proof, in mathematics, is an impeccable argument, using only the methods of pure logical reasoning, which enables one to infer the validity of a given mathematical assertion from the pre-established validity of other mathematical assertions, or from some particular primitive assertions--the axioms--whose validity is taken to be self-evident. Once such a mathematical assertion has been established in this way, it is referred to as a theorem.”―Roger Penrose (1931-)

Subsection 5.1.3 General Proof-Writing Techniques

Proofs are constructed using definitions, axioms, and previously established theorems and facts. In this way, ability to write proofs is closely connected with knowledge of definitions and theorems. A good proof is (a) correct, (b) clear, and (c) concise.

Subsection 5.1.4 Constructing a Proof

• Understand the problem. First, this requires understanding what the meaning of all of the words in the problem. It can also be helpful to rewrite the hypotheses given in the statement, and the conclusion is to be proved, ideally in a more convenient form. Sometimes, this requires translating words to symbols. The hypotheses are what you have to work with, and the conclusion is the goal to be proved.

• Consider special cases. When proving general statements, it can be helpful to first consider special cases of the statement. This makes the statement more concrete and less abstract. This can spark intuition about how the general case will behave like.

• Sketch a diagram. It is often helpful to sketch a diagram of the situation involved.

Subsection 5.1.5 Structure of a Proof

First, write a brief introduction.

• Define terms. Any variables used in the proof should be defined before they are used. Typically, we use words like “Let...” or “Consider...”. For example, “Let \(n\) be a natural number”, or “Consider an arbitrary point \((x,y)\)”.

• Sometimes, it is helpful to review relevant definitions or facts.

• If the solution is particularly complicated, it is helpful to state the overall direction of the general steps of the proof.

In the main body, derive the solution with a clear logical layout.

• Use complete English sentences. This is still true even if the solution is mostly made up of equations and mathematical expressions.

• Use connective words such as “Then, ...”, “Therefore, ...”, “Now we see that...”, “Observe that...”, “Thus, ...”.

• Sometimes, a diagram can be helpful, but typically “picture” proofs are not sufficient. If you do include a diagram, utilize a straightedge when drawing straight lines.

• If a solution is particularly complicated, structure your solution appropriately. For example, at the beginning, say “First, we will show that...”. Then, “Next, we will show that...”. And, “Finally, ...”.

After completing the proof, state a concise summary of what you proved, addressing the original statement. Clearly indicate what the answer is, if there is one.

Subsection 5.1.6 Other Tips

• Write neatly, are write large enough, to make it easy for the reader.

• If necessary, typeset your work (use LaTeX) and print it.

• If you cannot fully solve a question, be honest about it, and state what you have done.

Subsection 5.1.7 Proof by Cases

Many proofs require two or more cases, each with slightly different assumptions. This is somewhat a “brute force” method, especially if there are many cases.

Subsection 5.1.8 Proof Intuition

In a proof, we must start from assumptions and definitions, and successively deduce statements, towards the final conclusion. However, when actually discovering or developing a proof, it is often helpful to proceed both forwards and backwards, trying to find links between the premises and conclusion.

Also, in general in mathematics, intuition comes first, and rigor comes later. Intuition, imagination, and creativity plays a larger role than many believe. This is partly because math textbooks are finished mathematics that has been refined for often hundreds of years.