An Informaticist Looks at Math Proofs, Part III: Three Common Proof Techniques

by Jerome Carter on March 17, 2014 · 0 comments

Well, it is finally time to talk about proofs.   This might seem to be a rather esoteric topic for an EHR-focused blog, but actually it is quite relevant.   Software consists of a series of algorithms, and each algorithm is intended to work correctly 100% of the time.   Creating algorithms is very much a process of ordering a set of steps then proving those steps will always result in the expected outcome.  Thus, each algorithm is a type of proof.    Clinical information systems, especially if they provide decision support, may have many rules that fit the IF-THEN template (e.g., If Calcium level > X, THEN…, IF Gender=X and Age > Y, THEN…).    Thinking through these rules logically and assuring their application always results in an acceptable outcome requires the same attention to detail as proofs do.

One benefit that I have personally realized from learning how to write proofs is a much greater appreciation for mathematics.   Since discrete mathematics is usually taught to math and computer science majors, most students are never exposed to it.   It was refreshing and eye-opening to discover mathematics that described things from everyday life that I was interested in studying.   Health care is full of sets (patients, medicines, problems), graphs (workflows, relationships), logic (rules), relations (problem lists, medication lists) and algorithms (diagnostics workup plan). Discovering that it was possible to describe many aspects of health care mathematically has proven to be a wonderful epiphany.  Now, on with the show…

A little number theory
Demonstrating proof techniques requires a few easy-to-understand math definitions to play with and, as unlikely as it sounds, number theory is a good choice.  Number theory is an area of pure mathematics that deals with the properties of integers.  Since everyone knows about integers, it is a good way to learn about proofs without having to learn new mathematics (or at least not much).

Here are a few definitions and principles (based on Epp):

Every integer is either even or odd.

An integer n is even if, and only if, it equals twice some integer (n=2k)
Example: 0= 2*0, 2=2*1, 4=2*2, 6=2*3…

An integer n is odd, if and only if, it equals twice some integer plus 1 (n=2k+1)
Example: 1=2*0+1, 3=2*1+1, 5=2*2+1…

Integers are closed under addition, subtraction, and multiplication.  (Whenever integers are added, subtracted, or multiplied, the result is always another integer)

Universal implications, redux
In looking at proof techniques, my goal is not to try and teach you how to do proofs, but rather to show how proofs are applied logic and that there is no magic involved.  The most common techniques make use of universal implications.  For example, “For all integers x, If x is even Then x2 is even,” is a universal implication that makes a statement about the squares of even integers.

Recall that implications may have four forms: original implication, contrapositive, inverse, and converse.   The contrapostive is logically-equivalent to the original implication, and because of this, the contrapositive may be used in proofs in place of the original implication.

An implication and its negation cannot both be true.  This fact provides another strategy for proving an implication.  If one can prove that the negation of an implication is false, it is the same as proving the implication itself is true.   Thus, we have three proof techniques: Direct proof of an implication, indirect proof of an implication by proving that its contrapositive is true (proof by contrapostion), and indirect proof of an implication by proving that its negation is false (proof by contradiction).   Let’s get started.

Original implication:  For all integers x, If x is even, Then x2 is even.

even x org

Direct proof
For a direct proof we will use the original implication.   Since we are making a statement about every possible even integer, the strategy of the direct proof is to select at random an even integer and prove that if the implication holds for it, it holds for any even integer.   A common mistake is trying to prove this implication by substituting numbers into the implication (i.e., testing if it is true with 2, 4, 6, 8…). The problem with this approach is that the set of even integers is infinite, so there is no way to test them all.  However, with limited sets, this might work and is referred to as the method of exhaustion.

We need a different strategy.   One approach is to make use of the definitions from number theory.  From the definition we know that every even integer is twice some other integer. Using this fact, we can approach the proof as follows:

  1. For all integers x, If x is even Then x2 is even.
  2. Let x be an arbitrarily selected even integer.
  3.  This means that x can be represented as x = 2r by the definition of an even integer)
  4. x2= 4r2  (algebra)
  5. x2= 2(2r2)  (factor out 2)
  6. Let  m=(2r2).  Since 2 and r2 are both integers, this means that m is an integer(products of integers are integers).
  7. Hence, x2= 2m.
  8.  Since an even integer is, by definition, twice another integer, this shows that x2 is even since it equals 2m, which was to be proven.

Proof by contradiction
Proof by contradiction is an indirect proof strategy.  We know that an implication and its negation cannot both be true.  We can use this fact to prove the original.  Here is the negation:

Original implication
:  For all integers x, If x is even, Then x2 is even.

Negation:  There is an integer x such that:  x is even and x2 is NOT even.  Once again, using the fact that every integer is either odd or even, we can restate the negation as:

Final Negation:  There is an integer x such that:  x is even and x2 is odd.

even odd x

We start by assuming the negation is true and that when x is even, x2 is odd.

Now, let x be an arbitrarily-selected even integer.
x = 2r (by definition of even).
x2 = 4r2 (algebra).
x2= 2(2r2) (factor out 2 ).
Let m=2r2(products of integers are integers)

This makes x2= 2m, which is the definition of an even number. Yet, at the outset we assumed that x2was odd.   Since x2 is an integer and, by definition, an integer cannot be both odd and even, this contradicts the original assumption that x2   is odd.  The negation is proven false, and as a result, the original implication is proven true.

For some reason, I have a special fondness for proof by contradiction.  It’s fun—yes, I said that out loud. Moving on…

Proof by contraposition
Proof by contraposition is another indirect proof strategy.   Using this technique, the original implication is replaced by its contrapositive, and then the direct proof method is used as outlined above. Why would anyone do this?  Well, sometimes, the contrapositive is easier to prove.

Contrapositive: For all integers x, If  x2 is NOT even, Then x is NOT even.  Using the fact that every integer is either odd or even, we can restate the contrapositive as:

Final Contrapositive: For all integers x, If x2 is odd , Then x is odd.

This contrapositive cannot be proven with the definitions given above (it requires adding definitions concerning divisibility).  So, in this case, using the contrapositive does not make life easier.

What can a non-mathematician learn from proofs?
I don’t expect anyone to haul off and start doing proofs because of this post.   However, there are real benefits to be derived from learning logic, rules of inference, and proof strategies.  The most obvious being that they force one to learn to assess problems in a consistent and deliberate manner.  Being able to follow proofs in books and articles is another plus. For those who write code, better constructed algorithms and improved program structure are also likely benefits.

One interesting effect of leaning proof techniques that I have noticed is that I can now spot universal implications easily in everyday communications, and I have learned to test them quickly by looking for counterexamples.  And you know what? It’s scary how often perfectly valid and obvious counterexamples are available.   Try it.

Pick your favorite “X” and substitute:

“X saves money.”
“X lowers costs.”
“X improves quality. “

See what I mean?

Until next week…

__________

Epp, Susanna S. Discrete Mathematics with Applications. Belmont, CA: Thomson-Brooks/Cole, 2011.

Facebooktwitterpinterestlinkedinmail

Leave a Comment

{ 0 comments… add one now }

Previous post:

Next post: