Proof by Contradiction in Discrete Mathematics

---

---

Contradiction means negating a statement or when something false we care about. Proof by Contradiction is one of the most powerful methods used in discrete mathematics, especially when we are working on statements that are difficult to prove directly. The idea of this method lies in its simplicity; it assumes the opposite of what we are trying to prove, and shows how it leads to a contradiction.

In this chapter, we will explain Proof by Contraction in detail, discussing its basic framework and providing practical examples for a better understanding of this concept.

What is Proof by Contradiction?

Proof by Contradiction operates on the following logical principle: to prove a statement P, assume that P is false (i.e., assume ¬P, the negation of P is true), and then show that this assumption leads to a contradiction. The contradiction arises when two mutually exclusive facts or statements are derived. Since the assumption ¬P leads to a contradiction, the original statement P must be true.

The basic structure of a proof by contradiction follows these steps −

• Assume the negation of the statement we are trying to prove.
• Develop the argument, using logical steps and known facts.
• Arrive at a contradiction, a situation where a logical inconsistency arises.
• Conclude that the original statement must be true because the assumption that it was false leads to an impossible scenario.

Why Use Proof by Contradiction?

This is also an interesting question which seeks the answer that why we need the help of contradiction where we can prove them directly? There are many cases where proving a statement directly can be challenging. However, by assuming the opposite and working towards a contradiction. The steps may become more intuitive or simpler.

Proof by Contradiction is useful when we are working with universal statements, the theorems involving inequalities, or proving the existence of something that cannot be easily demonstrated by construction.

Let us now understand the concept with the help of a set of examples.

Example 1: Proving √2 is Irrational

One of the most famous examples of proof by contradiction is the proof that √2 is irrational. The statement to be proved is −

"The square root of 2 is irrational."

Step 1: Assume the negation

Assume the opposite, i.e., that √2 is rational. We know by definition of rationality, this means that −

$$\mathrm{\sqrt{2} \:=\: \frac{a}{b}}$$

where a and b are integers, and the fraction is in its simplest form (i.e., a and b have no common divisors other than 1).

Step 2: Develop the argument

By squaring both sides, we get −

$$\mathrm{2 \:=\: \frac{a^2}{b^2}}$$

which implies that −

$$\mathrm{a^2 \:=\: 2b^2}$$

This equation tells us that a² is an even number (because it is equal to 2b²). From this, it follows that A itself must also be even (because the square of an odd number is odd, and the square of an even number is even). So, we can write −

$$\mathrm{a \:=\: 2k}$$

for some integer k. Substituting this into the equation a² = 2b² we get −

$$\mathrm{(2k)^2 \:=\: 2b^2}$$

$$\mathrm{\Rightarrow\: 4k^2 \:=\: 2b^2}$$

$$\mathrm{\Rightarrow \: b^2 \:=\: 2k^2}$$

Thus, b² is also even, meaning that b is even.

Step 3: Arrive at the contradiction

At this point, we have an idea that that both a and b are even. But, this contradicts our original assumption that $\mathrm{\frac{a}{b}}$ is in its simplest form (because if both A and B are even, then they share at least 2 as a common divisor). Therefore, our assumption that √2 is rational must be False.

Step 4: Conclude

Since the assumption led to a contradiction, we conclude that √2 is irrational.

Example 2: No Integer Solutions for x² = 4y + 2

Let us consider another example of a quadratic equation,

"Prove that there are no integers x and y such that x2 = 4y + 2"

Step 1: Assume the negation

Assume that there are integers x and y such that −

$$\mathrm{x^2 \:=\: 4y \:+\: 2}$$

Step 2: Develop the argument

We can rewrite this equation as −

$$\mathrm{x^2 \:=\: 2(2y \:+\: 1)}$$

This shows that x² is an even number. If x² is even, then x must also be even. This is because the square of an odd number is odd).

So, let x = 2k for some integer k. Substituting this into the equation, we get −

$$\mathrm{(2k)^2 \:=\: 2(2y \:+\: 1)}$$

$$\mathrm{\Rightarrow \: 4k^2 \:=\: 2(2y \:+\: 1)}$$

$$\mathrm{\Rightarrow \: 2k^2 \:=\: 2y \:+\: 1}$$

Step 3: Arrive at the contradiction

The equation 2k² = 2y + 1 implies that the left-hand side is even (since 2k² is divisible by 2), but the right-hand side is odd (since 2y + 1 is an odd number). This is a contradiction because an even number cannot equal an odd number.

Step 4: Conclude

Thus, the assumption that there exist integers x and y satisfying x² = 4y + 2 leads to a contradiction. So, no such integers exist.

Example 3: The Pigeonhole Principle

Let us see our third example, which is one of the most famous problem in discrete mathematics. The Problem of Pigeonhole Principle. It states that if more than n objects are placed into n containers, at least one container must hold more than one object. Here, how we can prove it using contradiction:

"If more than n pigeons fly into n pigeonholes, at least one pigeonhole must contain more than one pigeon."

Step 1: Assume the negation

Assume the opposite, that no pigeonhole contains more than one pigeon. In other words, each pigeonhole contains at most one pigeon.

Step 2: Develop the argument

If each pigeonhole contains at most one pigeon, then the total number of pigeons that can fit into the n pigeonholes is at most n (Each pigeonhole holds no more than one pigeon).

Step 3: Arrive at the contradiction

We have assumed that there are more than n pigeons. This gives a contradiction, because if there are more pigeons than pigeonholes, at least one pigeonhole must contain more than one pigeon.

Step 4: Conclude

Thus, the assumption that no pigeonhole contains more than one pigeon leads to a contradiction. Therefore, at least one pigeonhole must contain more than one pigeon.

There are some other examples where we use this method of contradiction to prove something. In automata theory, a special branch of discrete math and computation, we use the concept called pumping lemma for regular languages and contextfree languages. For them as well, we use the method of contradiction to prove some expression is not falling under regular language or context free language.

Conclusion

Proof by Contradiction is a widely used method in Discrete Mathematics. We started by explaining the logical framework of this technique. This method assumes the negation of the statement to be proven and showing that this leads to a contradiction.

We then explored three practical examples: the proof that is irrational, the problem involving no integer solutions for x² = 4y + 2, and the application of the pigeonhole principle.