In a direct proof we deal with If P then Q types of statements, more formally known as conditionals. An example of a conditional, is “If n is an odd integer, then n^2 is odd.” However, it might not be worded like this, it could have been, “The square of every odd integer is also odd.” But where is the if…then… format? It is sneakily hidden in it! But if you were ever to be given a proof to do, you could always just try to re-word it and see if it is of that form, because knowing the if…then… form will help a lot in starting the proof.
In a direct proof we just do a series logical deductions and then make some conclusion. For example consider a proof to our above theorem.
Let since is an odd integer. Therefore:
So in this example, we started of the fact that is odd, and did some logical things to it, and arrived at what we wanted to.
But wait, how does that prove our original statement? Well if we have a really close look at our last line, we see that our expression boils down to plus , and since this 2 times anything is even, if we add 1 to it, we will get something odd. So we can see that just by making a few mathematical deductions, and having a really close look, we can prove our statements with this direct proof method. But what about that batman symbol? Well in order to show a proof is finished, you would usually draw a square, but I have decided to use the batman symbol just for kicks. So whenever you see Batman, think “Proof Finished!”
Now that we know the process, lets look closer into all this. The conditional type statement If…Then is based on implication, i.e. something implies something else. This is written as (read A implies B) and has the following truth table. (this tells you when is true).
|Truth Table Conditional||[Fields]|
To understand this, consider the following statement, “If you eat in class (A), the teacher will kick you out (B).” Well, obviously if you eat in class and the teacher kicks you out, the statement is true and if you eat in class and the teacher does not kick you out, the statement is false. However, if you don’t eat in class, (represented by the last two rows of the table), there is no way to tell whether or not the statement is true or false, because the consequence of getting kicked out only applies if you eat in class, so you do not know whether or not your teacher would actually kick you out. Therefore, the statement in both cases is true. Weird, but it kinda makes sense, you cant go around assuming your teacher is a liar!
So according to this truth table, all we need to do now, is prove the first line is true, and we have proved the entire statement, as was the case with our first example. However be careful, with a conditional statement such as , you cannot assume that not A implies not B, or even that B implies A. But for a statement like that we need to introduce a new operator which reads “if and only if” or “iff,” and this means that and are both true and forms . It’s truth table looks something like this:
|Truth Table Biconditional||[Fields]|
Proving a statement like this requires 2 proofs in one, prove that and prove that . Here is an example for you to try at on your own, remember it is just like our example above but you need do the whole process twice!
Prove that a whole number is even iff it’s square is even.
I took a bit of linear algebra in my first semester of Uni, and in it we learnt a formula for the Inverse of a matrix.
And using this we can prove the theorem:
If the determinant of a matrix is 0, it does not have an inverse.
Have a go at this one too! And here are some questions to ponder, can this be changed into an iff statement? i.e. If a matrix is non-invertible, is its determinant zero? How would you go about proving this? Are there any other ways for a matrix to be non-invertible, other than the zero determinant?
Hopefully this all helps people out there dealing with implications and proofs. I have gathered a lot of my info from a book called “A gentle introduction to the art of Mathematics” by Joseph Fields, freely available at http://aimath.org/textbooks/approved-textbooks/.