Proof by Contradiction
Contents
Proof by Contradiction¶
Sometimes proving something is True is very difficult. Instead, it might be easier to prove that something related must be False. Remember that in logic everything must be either True or False. There is no middle ground. This basic principle gives us a special power. If we can prove something is not True then we have indirectly shown it is False. By eliminating the possibility of it being True, we are left with only one choice. It must be False.
When want to prove something is True. We need to decide between two choices:
Try to prove it is true
Try to prove it cannot be false
Those may sound the same, but one may be much easier than the other.
By StevenCrowder - Male Privilege Is A Myth | Change My Mind on YouTube, CC BY 3.0, Link
Sometimes it is impossible to try and make a convincing argument that something is always true. It may only be possible to prove it cannot be false. This is where Contradictions come in.
Contradictions¶
There are four rules related to contradictions in deduction. They all related to a common pattern. In short, we make an assumption and prove it is impossible. We then draw some conclusion from our assumption. This is a kind of thought experiment.
We can use a simple math example to show the concept before we formalize it. We want to prove the following statement:
The product of an even integer times any other integer must be even.
The first problem with proving this is the “any other integer” part. This is a very wide ranging statement. It could be any even integer for the first value and then any integer for the second.
We could take a slightly different approach. Let us assume that there exists an odd number \(t\) that is the product of an even number and another number. We create a hypothetical world where the rule we are trying to prove is broken.
We can write out \(t\) algebraically as
\( \begin{align} t = (2x)*y \end{align} \)
where \(x\) and \(y\) are integers. Writing \(2x\) makes sure the value is even. Every even integer is just some integer multiplied by 2.
We also claimed that \(t\) was odd. That means \(t=2m+1\) for some integer \(m\). It must be 1 number larger than an even value to be odd.
Note
Zero is an even number! It has all the properties of an even number. It has no remainder when divided by \(2\). It is the product of \(2\) times \(0\).
We can compare our two definitions for \(t\).
\( \begin{align} (2x)*y = 2m+1 \end{align} \)
If this equals is actually true, then our assumption holds. If this equals is impossible, then our assumption was impossible. That means our original statement must be true, it is impossible to do the opposite.
When happens when we divide both sides by 2.
\( \begin{align} \frac{(2x)*y}{2} =& \frac{2m+1}{2} \\ xy =& m+\frac{1}{2} \end{align} \)
This statement is a problem for us. The right side \(m+\frac{1}{2}\) is clearly not an integer. We assumed \(m\) was an integer, then added \(\frac{1}{2}\). It is no longer an integer. We also assumed \(x\) and \(y\) where integers. The integers are closed for multiplication, it is impossible to multiple to integers and get a non-integer. This formula cannot be true based on our assumptions. One of the three values \(x\), \(y\), or \(m\) must not be an integer.
We assumed “that there exists an odd number \(t\) that is the product of an even number and another number”. Creating an imaginary world where this was true caused something impossible to happen. That tells us that the assumption caused a contradiction. We can conclude that the opposite must be true.
Our statement has been verified because it is impossible for a situation that doesn’t follow this rule to happen.
The product of an even integer times any other integer must be even.
This is the foundation of contradiction proofs. We assume something and prove it is impossible. Then, we draw conclusions about what must be possible from our subproof.
Deduction Rules of Contradictions¶
Depending on what we assume and what we prove, there are different rules we need to use. There are four rules related to contradictions.
Negative Elimination: This is used when we want to declare that something impossible has happened. It is also known as contradiction introduction in some systems.
Negative Introduction: We assumed something was true and showed that was impossible. The opposite must be true, the assumption must be false.
Indirect Proof: We assumed something was false and showed that was impossible. The opposite of the assumption must be true.
Principle of Explosion: Once a contradiction has been reached, we can state anything within the subproof. We will see how this is useful later.
Negative Elimination¶
This is almost always used as part of a subproof, but we can give impossible premises to make it happen. There is a new special symbol \(\bot\) used for contradictions. It tells us “this proof is no longer true”.
What if we make premises \(A\) and \(\neg A\). This can never happen. The variable \(A\) cannot be true and false at the same time. This is a trivial contradiction.
Our argument is \(A, \neg A \therefore \bot\).
The negative elimination rule has the shorthand \(\neg E\). It takes two numbers. The two line numbers must reference opposite expressions. We are saying the entire proof or subproof has failed because these two lines cannot co-exist.
Negative Introduction¶
The negative elimination rule isn’t very useful alone. It works best when paired with another rule. The negative introduction rule is one of two that it works well with.
The negative introduction rule can only be used when a subproof ends in a contradiction. It allowed us to prove that the opposite of the subproof assumption is true.
This rule states that if we take the assumption that caused the contradiction and put a negation in front of it, we must have something that is true. Since we only have two boolean values, the opposite must hold.
We can show this with the following argument.
\( (P \implies (Q \vee R)), \neg (Q \vee R) \therefore \neg P \)
This argument asks us to conclude that \(P\) is false. We have no tools to do this except contradiction. We start by assuming \(P\) is true. If we show that is impossible, then \(P\) must be false.
Notice that the subproof ends in a contradiction. That imaginary world is impossible. We then draw a conclusion out of that subproof. We negate the assumption. The negative introduction rule has the shorthand \(\neg\)I. It takes a range of numbers. The range starts from the assumption and ends with the contradiction. It includes everything in between. This rule can only be used when the subproof ends in a contradiction.
Indirect Proof¶
What if instead of adding a negation, we want to take one away? We would still get the opposite. The opposite of \(\neg P\) is \(\neg \neg P\) and also \(P\). An indirect proof allows us to remove a negation instead of adding one. We still make an assumption and prove a contradiction, but we remove a negation from the assumption.
This allows us to assume a negation statement like \(\neg P\) then use it to prove \(P\).
Note
Another way to remember the rule’s name is IP is to think of it as “introduce positive.” We introduce the positive version of the variable based on contradicting the negative.
We show an indirect proof rule by proving the following argument.
\( (\neg I \implies B), (B \implies I) \therefore I \)
We want to prove \(I\), but have no useful way to get there. Instead, we assume \(\neg I\). If this is impossible, then we can conclude that \(I\) must be true.
The shorthand for an indirect proof is IP. It also takes a range of numbers. This range must reference a subproof that starts with an assumption and ends in a contradiction. You may then remove a negation sign from the assumption.
Principle of Explosion¶
In The Hitchhiker’s Guide to the Galaxy, the characters go to a restaurant called Milliways, The Restaurant at the End of the Universe [Ada80]. The slogan for this restaurant is
If you’ve done six impossible things this morning, why not round it off with breakfast at Milliways, the Restaurant at the End of the Universe.
Once we have made an assumption that causes a contradiction, we have done one impossible thing. We have created an imaginary world where a statement is both true and false at the same time. Once we have done one impossible thing, we can do as many more as we want.
This is the principle of explosion. Once the subproof is contradictory, it can explode to justify anything we want. This may sound powerful, but we can only prove whatever we want inside the subproof. Drawing conclusions from these subproofs is difficult.
The most common use of the principle of explosion is in conjunction with a disjunction elimination. We prove one side of the disjunction, then contradict and explode the other side. This gives us a way to have both subproofs end with the same expression, even through we know one side is impossible.
What if we had two premises? First, we know that \(Q \vee R\) is true. We also know \(\neg R\) is true. We can conclude from this that \(Q\) must be true. We know the other side of the disjunction is false. The question is how do we prove it?
We need to assume both sides of the disjunction. On the side that is impossible, we will use the principle of explosion to justify that \(Q\) must have been true.
We needed both subproofs to end in the same expression. That is a requirement of the disjunction elimination rule. One of the subproofs was contradictory, it was impossible. How can we make the two sides match up if one imaginary world is impossible? This is where the principle of explosion becomes our get out of jail free card. It allows us to write anything within the contradictory subproof.
Keep in mind, if we used explosion to create something that didn’t match the possible branch of disjunction elimination, we won’t be able to use it. It only works if we have one side of the disjunction with a real conclusion and one that explodes the same thing.
The principle of explosion is justified by an X symbol and a reference to the line with the contradiction. All it needs is to know that this subproof contains a contradiction.
Halting Problem¶
One famous proof in computer science uses a contradiction. In 1937, Alan Turing proved that the Halting Problem could not be solved by any computer [Tur37b]. We will look at this concept informally. This will show how proofs by contradiction can appear in computer science.
The Halting Problem can be summarized as asking “Does this program contain an infinite loop?”. Obviously, being able to detect this would be amazing. We could warn the programmer ahead of time about if a loop can run infinitely. Then they could fix it immediately. A program is said to halt if it exits after a finite amount of time.
Let us assume we have magically written a program that will solve the halting problem. We will show that this program cannot exist by using a contradiction.
We create a function codeHalts(fileName, functionName, input) that takes a source code file ,a function name, and the input we plan to give the function. It will return True if the function halts for that input. It will return False if the input causes the function to enter an infinite loop.
Of course, we have no clue how to make this function! We are just assuming it exists. To make the rest of the code readable, we can make up a fake function. Remember, we are just pretending this function works. Imagine this code is saved in the file halt.py.
#This function looks through the code in fileName.
#It finds the function given by functionName.
#It returns TRUE if function halts on input
#and FALSE if the function enters and infinite loop.
def codeHalts(fileName, functionName, input):
#We don't actually know how this function works
#It is imaginary
return False
We could then run it on different input files. We could say codeHalts("example.py","quickSort","[1,2,3,4]"). If it returned True, we would know for a fact our quicksort would exit. This would be great tool for the OS. It could avoid ever entering an infinite loop.
We can use our codeHalts function to make a new impossible function. This will create a contradiction.
def breakCode():
if codeHalts("halting.py","breakCode",""):
i=0
while True:
i=(i+1)%2
else:
return False
What does breakCode() do? If the codeHalts predicts it will halt, then it enters an infinite loop. If the codeHalts function predicts it will enter a loop, it never does.
This code does the opposite of whatever codeHalts tells us it will do. Our assumption was that codeHalts worked correctly. This function gives a situation where it does not work correctly.
We have created a contradiction. If you could write a perfect codeHalts function, then you could also write the breakCode function. This function would not match the predictions of codeHalts, therefore you cannot make a perfect function to always detect if a function will enter an infinite loop.
This is not saying that you can never detect an infinite loop. There are many algorithms that can detect some infinite loops. This proof is telling us that we can never detect all infinite loops before they happen. Being able to detect every possible infinite loop ahead of time would create a contradiction.
If we ran codeHalts("halting.py","breakCode", "") to try and determine if this source code had an potential infinite loop, it could never predict the future correctly.