Hello, and welcome back, and today we’re going to be pausing our discussion of Pascal’s triangle temporarily, and discussing some proof writing! (Don’t worry, this will only be a 2 part series, so we will be back on to Pascal’s triangle in no time!)
What is proof?
A proof is a series of statements, each following from a given, from a proven theorem, from a definition, or is an assumption. For example, take the following proof that an odd number squared is an odd number:
Proof: Let x be an arbitrary odd number. Then, by the definition of an odd number, x=2a+1 for some a in the natural numbers. Then, x2=(2a+1)2=4a2+4a+1=2(2a2+2a)+1. Thus by the definition of an odd number, x2 is an odd number.
The above is what is known as a direct proof, as it makes no assumptions at all. There are 2 main types of direct proof when it comes to if, then statements, the one shown above doesn’t have a name, so I will just call it a ‘normal’ proof. But, we can also use a method of proof known as contrapositive:
Before we dive into proof by contrapositive, we most first know what the contrapositive is. The contrapositive of an if then statement ‘If a then b’ is the if, then statement ‘If not b, then not a.’ It turns out these statements are logically equivalent, i.e. if the statement is true, then the contrapositive is true, and if the statement is false, the contrapositive follows. To prove this, we will need to dive deep into the world of mathematical logic.
And, Or, and more!
A mathematical statement is either true, or false. It cannot be both, and it cannot be neither. For example, ‘1+1=3,’ ‘2×2=4,’ and ‘The Riemann Hypothesis is true’ are all mathematical statements, but ‘This statement is false,’ is not a mathematical statement. We can preform certain operations on mathematical statements, the simplest of which are and and or. These operations are usually written as a upside down v and a normal v respectively, but in this blog I will just say ‘And’ or ‘Or’ wherever the operation goes. These operations are fairly explanatory. For ‘And,’ the statement ‘a And b’ is true only if both a and b are true, and false if either one is false. For ‘Or,’ the statement ‘a Or b’ is true if either a or b is true, and false otherwise. ‘Or’ is sometimes tricky because if BOTH a and b are true, then ‘a Or b’ IS true, which is not exactly how the word or is used in normal language. Finally, we have the ‘Not’ operation, which is very simple. ‘Not a’ is true if a is false, and is false if a is true. We now have the tools required to build the “If, then” statement.
If, then statements
Before we formally define the If, then statement, lets quickly outline what we want it to do.
The statement ‘If a, then b’, should be true if:
a is false and b is true
a is false and b is false
a is true and b is true
The statement should be false if:
a is true and b is false.
Now, we define the ‘If, then’ statement as follows:
The statement ‘If a, then b’ is logically equivalent to the statement ‘(Not a) Or b.’
This fits all the requirements defined above, since:
If a is false and b is true, then Not a is true, meaning ‘(Not a) Or b’ is true.
If a is false and b is false, then Not a is true, meaning ‘(Not a) Or b’ is true.
If a is true and b is true, then b is true, meaning ‘(Not a) Or b’ is true.
If a is true and b is false, then Not a is false, and b is false, meaning ‘(Not a) Or b’ is false.
Now, we finally have the tools required to prove that the contrapositive is equivalent to the original statement.
Let the original statement be ‘If a then b.’ Then, ‘(Not a) Or b’ is equivalent to the original statement. ‘(Not a) Or b’ is equivalent to ‘b Or (Not a).’ This in turn, is equivalent to ‘(Not (Not b)) Or (Not a).’ Converting this back to an ‘If, then’ statement, we get ‘If Not b, then Not a,’ which is the contrapositive.
We now have proved this method of proof, so let’s use it!
Let’s prove the following statement:
If x2 is even, then x is even, for all integers x
Proof: We shall prove this by contrapositive, so let a=x be an integer that is not even. Then, a is odd. Since the square of an odd number is odd, we have that a2 is odd. So we have proved that ‘If x is not even, then x2 is not even for all integers x.’ Thus by contrapositive, ‘If x2 is even, then x is even, for all integers x’ is true.
Some more about And, Or and Not
Here are a few quick properties about And, Or, and Not, which I will not prove today for time’s sake, but most are fairly self-explanatory:
(Not a) And (Not b) is equivalent to Not (a Or b)
(Not a) Or (Not b) is equivalent to Not (a And b)
a And (b Or c) is equivalent to (a And b) Or (a And c)
a Or (b And c) is equivalent to (a Or b) And (a Or c)
a And (b And c) is equivalent to (a And b) And (a And c)
a Or (b Or c) is equivalent to (a Or b) Or (a Or c)
(If a then b) And (If b then c) is equivalent to (If a then c)
If (a Or b) then c is equivalent to (If a then c) And (If b then c)
This blog we laid the framework of logic, and proved that proof by contradiction is indeed valid. Next blog we will discuss induction, contradiction, and casework. But for now, that’s all!