# 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.