Tag: proof tutorial

Proof Tutorial 2: Proving Square Root of 2 is Irrational by Contradiction

College Mathematics, Number Theory, Problem Solving and Proofs

One of the most difficult proof strategies in mathematics is proof by contradiction. If P, for example, is a statement or a conjecture, one strategy to prove that P is true is to assume that P is not true  and find a contradiction so that the statement not P does not hold. If not P does not hold, it follows that P is true.

One well-known proof that uses proof by contradiction is proof of the irrationality of \sqrt{2}.  If we consider P to be the statement “\sqrt{2} is irrational”, then not P is the opposite statement or “\sqrt{2} is rational”.  To use proof by contradiction, we assume that \sqrt{2} is rational, and find a contradiction somewhere. If this happens, then we would have shown that \sqrt{2} is indeed irrational.

Before proceeding, recall that a rational number is a fraction with non-zero denominator.  We know that all fractions can be expressed in lowest term.  A fraction in \displaystyle\frac{a}{b} is said to be in lowest term if a and b have no common divisors except 1.

On the other hand, irrational numbers cannot be expressed as fractions. They are decimal numbers that do not end and do not repeat. For example, 0.10100100010000... is an irrational number (the three dots means and so on which means that the number does not end). The most popular irrational number is \pi.

Now, we prove our conjecture.

Conjecture: The \sqrt{2} is irrational.

Proof:

Suppose \sqrt{2} is rational, then it can be expressed in fraction form \displaystyle\frac{a}{b} . Let us assume that our fraction is in lowest term, i.e., their only common divisor is 1. Then,

\sqrt{2} = \displaystyle\frac{a}{b}

Squaring both sides, we have

2= \displaystyle\frac{a^2}{b^2}

Multiplying both sides by b^2 yields

2b^2= a^2*

Since a^2 = 2b^2, we can conclude that a^2 is even because whatever the value of b^2 has to be multiplied by 2. If a^2 is even, then a is also even. Since a is even, no matter what the value of a is, we can always find an integer that if we divide a by 2, it is equal to that integer. If we let that integer be k, then \displaystyle\frac{a}{2} = k which means that a = 2k.

Substituting the value of 2k to a in *, we have 2b^2= (2k)^2 which means that 2b^2=4k^2.  Dividing both sides by 2, we have b^2 = 2k^2. That means that the value b^2 is even, since whatever the value of k you have to multiply it by 2.  Again, if b^2 is even, then b is even.

This implies that both a and b are even, which means that both the numerator and the denominator of our fraction are divisible by 2. This contradicts our assumption that \displaystyle\frac{a}{b} has no common divisor except 1. Since we found a contradiction, our assumption is, therefore, false. Hence, the theorem is true.

Notice that I have highlighted the word suppose and assume in the proof. This is one unique feature of proof by contradiction. You can always assume, most of the time, the opposite of the conjecture as long as the following statements are logically valid.

Leave a comment , , , , , , , , ,

Proof Tutorial 1: Introduction to Mathematical Proofs

College Mathematics, High School Mathematics, Problem Solving and Proofs

Introduction

Routine problems in mathematics usually require one or many answers . If we are asked to find the smallest of the three consecutive integers whose sum is 18, then our answer would be 5. If we are asked to find the equation of a line passing through (2,3), we can have many answers.

Proofs, however, is different. It requires us to think more and to reason with valid arguments. It requires us to be explicit and logical. It requires us to convince our readers and most of all ourselves.

Unless a proof problem is already given, finding mathematical statements to prove requires us to see patterns, generalize, and make conjectures about them. The problem stated above about consecutive integers does not require us to reason much or generalize at all.

The success of proof writing requires intuition, mathematical maturity, and experience. Contrary to mathematical proofs written in books, the ideas behind arriving at a proof are not “cut and dried” and elegant.  Mathematicians do not reveal the process they go through, or the ideas behind their proofs. This is also a skill that mathematicians and persons who are good in mathematics possess: they are able to read proofs. The skills of reading proofs may be achieved by learning how to write them.

 

Proving in higher mathematics, on the other hand, requires formal training. For instance, we have to know how to use logical connectives like and, or, not, and must understand how conditional and biconditional connectives work. Basic set theory concepts are also important. Moreover, we also have to learn proof strategies like direct proof and proof by contradiction to name some.

For now, we will not be discussing these things . Most of the proofs in basic mathematics only require a little intuition and good reasoning.

In the tutorial below, I tried to recreate (amateurishly) the process on how mathematicians see patterns, arrive at a conjecture, and how they prove their conjectures.  Of course, in reality, problems mathematicians encounter are a lot harder. In fact, some of the hardest problems take hundreds of years to be solved. For example, no mathematician has proved the Fermat’s Last Theorem for more than 300 years, and the mathematician who proved it solved it for eight years.

The proof that we are about to do below is very elementary. For now, we will highlight the process and not the difficulty. The titles of the processes below are not necessarily in order.

Recognizing Patterns and Making Conjectures

Before mathematicians prove theorems, they usually first see patterns. This happens when they read books, solve problems, or prove other theorems. For example, what do we see when we add two even integers? Let’s add some: 2 + 8 = 10, – 24 + 6 = -18, and – 4 + – 8 = -12. We can easily see that if we add two even integers, then their sum is always even.

From here, we might be tempted to say that if we add two integers, then their sum would always be even.  In mathematics, this kind of statement or hypothesis is called a conjecture: an educated and reasonable guess based on patterns observed. Rewriting our guess, we have

Conjecture: The sum of two even integers is always even.

If we want to disprove a conjecture, we only need one counterexample — an example that can make the conjecture false. (Can you think of one?). Note that  we only need one counterexample to disprove a conjecture.  If we want to prove it, however, we might be tempted to pair a few more integers and say that “oh, their sum is even, so it must be true”. No matter how many integers we pair, if we can’t exhaust all the pairs, then it cannot be considered as a proof.  When we say the sum of two even integers above, we mean ALL even integers.  Of course, there is no way that we can list all pairs of even integers since there are infinitely many of them.

Generalizing Patterns

Since it is impossible to enumerate all pairs of even integers, we need a representation, algebraic expression in particular, that will represent any even integer. If we can find this expression, then all the even integers would be represented. This process is called generalizing.  Like what we have done above, we generalized by representing all members of the set by a single expression. In our case, the members of our set are all even integers.

 

From the definition, we know that all even integers are divisible by 2. That means that if m is an even integer, then, when we divide m by 2, we can find a quotient which is also an integer. For instance, since 18 is an integer, we are sure that there exists an integer such that 18 divided by 2 is equal to that integer.

In general, suppose that quotient of m/2 is q, then it follows that m/2 = q, for any even integer m. Multiplying both sides of the equation by 2, we have m = 2q. That means that if m is an even integer, then there exists an integer q such that m = 2q. Hence, we may represent any even integer m with 2q for some integer q*. Note that q here is a generalized number, which means that an even integer can also be represented by 2x, 2y, 2z or any variable with the condition that they are integers.

Connecting the ideas

Proving is making logical and relevant statements from definitions, facts, assumptions and other theorems to come to a desired conclusion. Before coming up with an elegant proof, mathematicians usually have scratch work, connecting their ideas to arrive at what they want to prove.

Scratch work

From the statement above, we have shown that any even integer m, there exists an integer q, such that m = 2q. That means, that if we can show that the sum of two even integers is in the form 2q (or that the sum is divisible by 2), then we can be sure that it is always an even integer.

Since we need two integers, we let m and n are the two integers that we will add. Since both of them are even integers, then we can represent them as 2q and 2r respectively for some integers q and r. Adding both of them, we have m + n = 2q + 2r = 2(q + r). Now, q + r is an integer since q is an integer and r is an integer from our definition above. This means that 2(q + r) isof the form 2x for some integer x. This means that m + n is of the form 2x for some integer x. Therefore, m + n is even.

Writing (elegantly) the final proof

Here, we write our proof in a shorter and more elegant way. Conjectures that are proven are called theorems. So let us write the proof of our first theorem.

Theorem 1: The sum of two even integers is always even.

Proof. Let m,  n be even integers.  Then m = 2q for some integer q and n = 2r for some integer r. Now, m + n = 2q + 2r = 2(q + r). Since q + r is an integer, clearly, 2(r + s) = m + n is divisible by 2. Therefore, the sum of two even integers is even.

Most proofs are written in a concise way, leaving some details for the reader to fill in. For example, the statement “Since q + r is an integer” did not really state the reason why this is so. This is stated in our scratch work, but not in the proof.

Going Further

If m is an even integer, then m – 1 and m + 1 are odd integers. Since m = 2r, then 2r – 1 and 2r + 1 are also odd integers. In our example below, we will use 2r + 1, to prove that the sum of two odd integers is always even. As an exercise, use 2r – 1 in your proof.

Theorem 2: The sum of two odd integers is always even.

Let p, q be odd integers. Then p = 2a + 1 and q = 2b + 1 for some integers a and b. Now, adding we have p + q = 2r + 1 + 2s + 1 = 2r + 2s + 2 = 2(r + s + 1). Since r + s + 1 is an integer, then 2(r + s + 1) is divisible by 2. Hence, p + q is divisible by 2. Therefore, the sum of two odd integers is even.

Math and Hardwork

Being good in math requires hard work. Andrew Wiles worked on the Fermat’s Last Theorem for seven years, have given up several times thinking that it was impossible. In 1995, he finally thought he had proved it, and presented it in a conference.  A month later, his reviewer thought that there is a part of the proof which was vague (or wrong), so he had to review his work and found out that there was a part which was actually wrong.  He almost gave up. He worked more than a year to correct the error.

Now, he has carved his place in history.

*In technical language, the word “for some” is equivalent to the word “there exists”.

Exercises:

  1. Prove that the sum of an even number and an odd number is always odd.
  2. Prove that the difference of two odd integers is always even.
  3. Prove that the product of two even integers is always even.
  4. Prove that the product of two odd integers is always odd.
  5. Prove that the product of an even number and an odd number is always even.
Leave a comment , , , , , , ,