Proofs by Contradiction — Proof Techniques in Theory of Computation

⭐ What Is a Proof by Contradiction? (Simple Words)

A proof by contradiction works like this:

1. Start by assuming the statement you want to prove is false.
2. Follow logical steps using this assumption.
3. Reach a contradiction — something that cannot be true.
4. Conclude that the assumption must be wrong.
5. Therefore, the original statement must be true.

It’s like pulling a loose thread on a sweater.
If the whole thing unravels, you know something was wrong with that thread.

---

⭐ Why Do We Use This Technique?

Some statements are extremely hard (or impossible) to prove directly.
But if you flip them around and assume the opposite, things suddenly become clearer.

In Theory of Computation, contradiction proofs are everywhere:

• proving some languages are not regular
• proving some problems are undecidable
• showing some machines cannot exist
• demonstrating limits of algorithms

It’s a powerful tool when direct or constructive proofs are too messy.

---

⭐ Everyday Analogy (Simple and Relatable)

Imagine you tell your friend:

“There must be a leak in the water tank.”

Your friend says:
“No, there is no leak.”

So you assume your friend is right — no leak.
Then you observe:

• the tank water keeps dropping
• the taps are closed
• there’s water on the floor

All these clues disagree with the assumption “there is no leak.”
This contradiction shows your friend must be wrong, and a leak does exist.

This is exactly how contradiction proofs work.

---

⭐ Simple Diagram: How a Contradiction Proof Flows

       Start with: Assume the statement is false
                              │
                              ▼
                   Follow logical reasoning
                              │
                              ▼
                     Reach a contradiction!
                              │
                              ▼
            Therefore, the assumption was wrong
                              │
                              ▼
             ✔ So the original statement is true

It looks like a loop of reasoning that collapses on itself.

---

⭐ A Classic Math Example (Short and Clear)

Claim:
( \sqrt{2} ) is irrational.

Proof by contradiction (simple version):

1. Assume the opposite:
   ( \sqrt{2} ) is rational.
   So it can be written as ( p/q ) in lowest terms.
2. Square both sides:
   ( 2 = p^2 / q^2 ) → ( p^2 = 2q^2 ).
   This shows p is even.
3. If p is even, write p = 2k.
   Substitute back:
   ( (2k)^2 = 2q^2 ) → ( 4k^2 = 2q^2 ) → ( q^2 = 2k^2 ).
   So q is even.
4. But p and q can’t both be even (that means the fraction wasn’t in lowest terms).

This contradiction means our starting assumption was false.
So ( \sqrt{2} ) is irrational.

This proof style appears often in Theory of Computation too.

---

⭐ Proof by Contradiction in Theory of Computation (Simple Example)

Claim:
A language that requires infinite memory cannot be recognized by any DFA.

Proof by contradiction idea:

1. Assume the opposite:
   A DFA can recognize a language that needs infinite memory.
2. But DFAs have a finite number of states.
   They cannot count arbitrarily large numbers or match patterns like ( a^n b^n ).
3. The assumption forces the DFA to handle an infinite requirement using finite states.
   That is impossible — it leads to a contradiction with the structure of a DFA.
4. So our assumption was wrong:
   A DFA cannot recognize a language requiring infinite memory.

This style of argument is used often when proving a language is not regular.

---

⭐ Another TOC Example: Halting Problem

A very famous contradiction proof shows the halting problem is undecidable.

The proof starts by assuming:

“Let’s imagine there is a machine that can solve the halting problem.”

Then, using that assumption, we build a situation where the machine contradicts itself —
a logical paradox similar to “This statement is false.”

That contradiction proves no such machine can exist.

---

⭐ Key Features of Proof by Contradiction

• You never build the actual object.
• You don’t try to prove the statement head-on.
• You simply assume the opposite is true — and let logic do its job.
• When the assumption crashes into an impossibility, the real truth emerges.

It’s one of those techniques where “being wrong on purpose” helps you find the truth.

---

About the Author

examhopeinfo@gmail.com

Administrator

Visit Website View All Posts