CHAPTER 3Methods of Proofs1. Logical Arguments and Formal Proofs1.1. Basic Terminology.• An axiom is a statement that is given to be true.• A rule of inference is a logical rule that is used to deduce one statementfrom others.• A theorem is a proposition that can be proved using definitions, axioms,other theorems, and rules of inference.DiscussionIn most of the mathematics classes that are prerequisites to this course, suchas calculus, the main emphasis is on using facts and theorems to solve problems.Theorems were often stated, and you were probably shown a few proofs. But it isvery possible you have never been asked to prove a theorem on your own. In thismodule we introduce the basic structures involved in a mathematical proof. One ofour main objectives from here on out is to have you develop skills in recognizing avalid argument and in constructing valid mathematical proofs.When you are first shown a proof that seemed rather complex you may think toyourself “How on earth did someone figure out how to go about it that way?” As wewill see in this chapter and the next, a proof must follow certain rules of inference,and there are certain strategies and methods of proof that are best to use for provingcertain types of assertions. It is impossible, however, to give an exhaustive list ofstrategies that will cover all possible situations, and this is what makes mathematicsso interesting. Indeed, there are conjectures that mathematicians have spent muchof their professional lives trying to prove (or disprove) with little or no success.1.2. More Terminology.• A lemma is a “pre-theorem” or a result which is needed to prove a theorem.• A corollary is a “post-theorem” or a result which follows from a theorem(or lemma or another corollary).561. LOGICAL ARGUMENTS AND FORMAL PROOFS 57DiscussionThe terms “lemma” and “corollary” are just names given to theorems that playparticular roles in a theory. Most people tend to think of a theorem as the mainresult, a lemma a smaller result needed to get to the main result, and a corollaryas a theorem which follows relatively easily from the main theorem, perhaps as aspecial case. For example, suppose we have proved the Theorem: “If the productof two integers m and n is even, then either m is even or n is even.” Then we havethe Corollary: “If n is an integer and n2is even, then n is even.” Notice that theCorollary follows from the Theorem by applying the Theorem to the special case inwhich m = n. There are no firm rules for the use of this terminology; in practice,what one person may call a lemma another may call a theorem.Any mathematical theory must begin with a collection of undefined terms andaxioms that give the properties the undefined terms are assumed to satisfy. This mayseem rather arbitrary and capricious, but any mathematical theory you will likelyencounter in a serious setting is based on concrete ideas that have been developedand refined to fit into this setting. To justify this necessity, see what happens if youtry to define every term. You define a in terms of b, and then you define b in termsof c, etc. If a, b, c, ... are all different terms, you are lead to an infinite chain ofdefinitions; otherwise, one of them is repeated and you are left with a circular chainof definitions. Neither of these alternatives is logically acceptable. A similar criticismcan be made for any attempt to prove every assertion. Here are a few importantexamples of mathematical systems and their basic ingredients.In plane geometry one takes “point” and “line” as undefined terms and assumesthe five axioms of Euclidean geometry.In set theory, the concept of a “set” and the relation “is an element of,” or “∈”,are left undefined. There are five basic axioms of set theory, the so-called Zermelo-Fraenkel axioms, which we will use informally in this course, rather than giving thema rigorous exposition. In particular, these axioms justify the “set builder” notationwe discussed in Module 1.1: Sets and the existence of the “power set” of a set, whichwe shall discuss later in Module 4.1: Set Operations.The real number system begins with the four Peano Postulates for the positiveintegers, taking the elements, “numbers,” in the set of positive integers as undefined,as well as the relation “is a successor of” between positive integers. (To say “x is asuccessor of y” turns out to mean that x = y + 1.) The fourth Peano Postulate isthe Principle of Mathematical Induction, which we shall use extensively in the nextmodule. From these modest beginnings, and with a little help from set theory, onecan construct the entire set of real numbers, including its order and completenessproperties. As with our treatment of set theory, we shall, with the one exceptionmentioned above, use these axioms informally, assuming the familiar model of the real1. LOGICAL ARGUMENTS AND FORMAL PROOFS 58number line together with its important subsets, the natural numbers, the integers,and the rational numbers.Once we have the undefined terms and axioms for a mathematical system, we canbegin defining new terms and proving theorems (or lemmas, or corollaries) within thesystem.1.3. Formal Proofs. To prove an argument is valid:• Assume the hypotheses are true.• Use the rules of inference and logical equivalences to show that the conclusionis true.DiscussionWhat is a proof?A proof is a demonstration, or argument, that shows beyond a shadow of a doubtthat a given assertion is a logical consequence of our axioms and definitions. Thus, inany problem in which you are asked to provide a proof, your solution will not simplybe a short answer that you circle. There are certain rules that must be followed(which we will get to shortly), and certain basic knowledge must be assumed. Forexample, one may assume the axioms and any previously stated theorems (unless theinstructions state otherwise). A large number of proofs simply involve showing thata certain definition is satisfied.In almost every case, the assertions we will be proving are of the form “if p, thenq”, where p and q are (possibly compound) propositions. The proposition p is thehypothesis and q is the conclusion. It is almost always useful to translate a statementthat must be proved into an “if ..., then ...” statement if it is not already in that form.To begin a proof we assume the hypotheses. For example, consider the argumentEvery dog will have his day.Fido is a