Proofs by Contradiction — Proof Techniques in Theory of Computation -

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

A proof by contradiction works like this:

Start by assuming the statement you want to prove is false.
Follow logical steps using this assumption.
Reach a contradiction — something that cannot be true.
Conclude that the assumption must be wrong.
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):

Assume the opposite:
( \sqrt{2} ) is rational.
So it can be written as ( p/q ) in lowest terms.
Square both sides:
( 2 = p^2 / q^2 ) → ( p^2 = 2q^2 ).
This shows p is even.
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.
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:

Assume the opposite:
A DFA can recognize a language that needs infinite memory.
But DFAs have a finite number of states.
They cannot count arbitrarily large numbers or match patterns like ( a^n b^n ).
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.
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.