Proof method: Direct Proof

In my first post on my journey for improving my mathematical rigour I said that I would go through a few different techniques for conducting proofs.

The first one I want to dabble into is direct proofs.  This is the “simplest” method and sometimes it can seem that the proof isn’t there at all.

It will often go something like “if a then b”. So using some definition of a, we can show that b follows as a direct consequence through an unbroken line of logical arguments such that

a -> … -> b

Lets try it out on some sample problems

Example 1

Definition: If a and b are two natural numbers, we say that a divides b if there is another natural number k such that b = ak.

Theorem: If a divides b and a divides c then a divides b + c.

Proof: If we follow the flow chart from last, we need to read an understand the problem.  We need to prove that if there exists a k1 and k2 such that ak1 = b and ak2 = c then there exists a number k3 such that ak3 = b+c. This is just a rewrite of the problem to spell it out a bit more, and show that we need to prove one part to prove this – we need to prove existence of k3.

Since there is only one part, we want go directly to choosing a method, which in this blog post is obvious, since we are dealing with direct proofs. So lets try to apply it:

Which proofs that there exists a k3 = k1 +k2. The first step is using the definition of “a divides b” to rewrite b and c. The second step uses the distributive property of multiplication.

This was pretty simple. Lets try another example.

Example 2

Theorem: The product of two consecutive integers plus the larger of the two integers is a perfect square.

As a first thing, lets try it out on an example just to see if it at least holds true for an example – otherwise we have provided a counterexample which falsifies the claim. In the example lets use 3 and 4.

So at least it holds true for one example.

Proof: In the general case it should hold true for all n and n+1

So using simple arithmetic we can show that it holds true for every two consecutive integers.

From these two examples we could be tempted to think that we can write it as one line of equalities that is not necessarily the case. We just need to have a direct line of reasoning.

Example 3

For this example I will change to the topic of functions. So lets start with the definitions we need.

Definition: A function is a rule that produces a correspondence between the elements of two sets: D ( domain ) and R ( range ), such that to each element in D there corresponds one and only one element in R. This can be written as f:D->R such that the function f maps D to R.

Definition: A function is called one-to-one if no two different elements in D have the same element in R. This is the same as for any pair a,b in X such that f(a) = f(b) then a = b. (As a note, this is also called an injective function)

Theorem: If two one-to-one functions can be composed then their composition is one-to-one. For the two function h(x) = g(f(x)) is one-to-one.

Proof: Let a,b in D and assume that h(a) = h(b). Thus g(f(a)) = g(f(b)),  since g is one-to-one follows that f(a) = f(b). Since f is also one-to-one we may conclude that a = b. Thereby proving that the composite function h = g(f(x)) is one-to-one.

Wrapping up

I have shown you a few examples, and in my search I found a few good sources on this technique. Richard Hammack wrote a book on the topic of proofs in which he spends a chapter on direct proofs. The book is free, so you can grab it if you like. I can really recommend it, especially because it contains exercises and solutions for them.

Bruce Ikenaga’s home page contains notes on various interesting topics, among those a 5 page note on direct proofs.

Posted by Kristian

3 comments

Proofs often contain lemmas. Could you explain that in your next post?

Hi SuprDewd

Thanks for the brilliant suggestion for a post. I will definitely go through the different terms regarding theorems and proofs, and not least Lemmas 🙂

/Kristian

That would be awesome. Thanks Kristian.

Leave a Reply