কন্ট্রাডিকশনের সাহায্যে প্রমাণ

প্রুফ বাই কন্ট্রাডিকশন হল কোনো গাণিতিক স্টেটমেন্ট প্রমাণের জন্য একটা বহুল ব্যবহৃত পদ্ধতি। কন্ট্রাডিকশন একটা ইংরেজি শব্দ। এটার ভাল বাংলা করলে দাঁড়ায় ‘বৈপরীত্য’। কিন্তু আমরা এই খটমটে শব্দটা ব্যবহার না করে এখানে কন্ট্রাডিকশন শব্দটাই ব্যবহার করব।

বেশিরভাগ ক্ষেত্রেই কন্ট্রাডিকশনের মাধ্যমে কোনো প্রমাণকে একটা ফর্ম্যাটের মধ্যে ফেলে দেওয়া যায়। কন্ট্রাডিকশনের সাহায্যে কোনো কিছু প্রমাণ করতে চাইলে প্রথমে যেটা প্রমাণ করতে হবে, আমরা তার উল্টোটা ধরে নিই। এরপর সেটা থেকে কোনো প্রকারের অসংগতি আনার চেষ্টা করি। যেহেতু উল্টো জিনিসটা থেকে অসংগতি আসে, তার মানে উল্টো জিনিসটা সত্যি হতে পারে না। বা অন্য কথায় বললে “সোজা জিনিসটা” (যেটা আমরা প্রমাণ করতে চাই, সেটা) সত্যি হতেই হবে।

যেকোনো প্রুফ টেকনিক সবচেয়ে ভাল বুঝা যায় উদাহরণের মাধ্যমে। তাই আমরা আর সময় নষ্ট না করে সরাসরি কিছু উদাহরণে চলে যাই।

আমরা শুরু করব একটা ক্লাসিক উদাহরণ দিয়ে। আমরা প্রমাণ করব যে এমন কোনো মূলদ সংখ্যা নেই যাকে বর্গ করলে $2$ পাওয়া যায়।

যেহেতু আমাদের প্রমাণ করতে হবে এমন কোনো মূলদ সংখ্যা নেই, আমরা কন্ট্রাডিকশনের খাতিরে ধরে নেব এরকম একটা মূলদ সংখ্যা আসলে আছে।

অন্যকথায়, এমন দুটো পূর্ণসংখ্যা $p$ আর $q$ আছে যেন $(\frac{p}{q})^2=2$ হয়। আমরা আরো ধরে নিতে পারি যে $\frac{p}{q}$ কে কাটাকাটি করে আর ছোট করা যায় না (সব মূলদ সংখ্যাকেই আসলে এরকম একটা ফর্মে নেওয়া যায়। তাই এই বাড়তি অ্যাসাম্পশনটা করলে কোনো ক্ষতি নেই)। তার মানে $\ p$ আর $q$ দুটোই জোড় না (দুটোই জোড় হলে তুমি এটাকে কাটাকাটি করতে পারতে। আমরা ধরে নিয়েছি এটা করা যায় না)।

এখান থেকে আমরা লিখতে পারি $p^2=2q^2$। এই সমীকরণটার ডানপক্ষ দুই দিয়ে ভাগ যায়। তার মানে বামপক্ষকেও দুই দিয়ে ভাগ যেতে হবে। অর্থাৎ $p^2$ জোড়।

যেহেতু $p$ জোড়, আমরা তাকে $2k$ আকারে লিখতে পারি যেখানে $k$ আরেকটা পূর্ণসংখ্যা (এটাই জোড় সংখ্যার সংজ্ঞা। যাকে $2\times$ (একটা পূর্ণসংখ্যা) আকারে প্রকাশ করা যায়, তাকেই জোড় সংখ্যা বলে।)।

এখান থেকে খানিকটা হিসাব করে পাওয়া যায় $4k^2=2q^2$ $\Rightarrow 2k^2=q^2$ এবার বামপক্ষটা দুই দিয়ে ভাগ যায়। একেবারে আগের মত বলা যায় যে $q^2$ জোড়।

তার মানে কী দাঁড়াচ্ছে? *$p$ আর $q$ দুটোই জোড়। *

কিন্তু মনে আছে আমরা কী বলেছিলাম শুরুতে? আমরা বলেছিলাম $p$ আর $q$ দুটোই জোড় হতে পারবে না। কিন্তু এখন দেখছি দুটোই জোড় হয়ে যাচ্ছে। একটা কন্ট্রাডিকশন!

এই ঝামেলাটা হয়েছে কারণ আমরা ধরে নিয়েছিলাম এমন একটা মূলদ সংখ্যা $\dfrac{p}{q}$ আছে যাকে বর্গ করলে $2$ হয়। আসলে এরকম কোনো মূলদ সংখ্যা নেই। আমাদের প্রমাণ শেষ!

Proof by contradiction is one of the most powerful proof techniques out there, even used by famous mathematicians such as Euler. It is a great technique to try if you are at a loss with other options.

Here is how it works: you take the statement you wish to prove true, and assume it is false. Then, you take this "proposal," and manipulate it to reach a statement we know is false (such as $1 = 0$). When that false statement is reached, we know we "made a mistake" somewhere, i.e. assuming that the statement we wanted to prove true is false. Therefore, the target statement must be true.

Note that if you wish to prove a statement to be false, simply follow the procedure above, replacing every use of "false" with "true" and every use of "true" with "false." This works because all statements are either true or false. No statement can be both true and false simultaneously.

Proof by contradiction (also known as an indirect proof) is an extremely powerful proof technique to prove a statement you can't easily prove directly.

The basic idea behind it is: First, you suppose the statement you are trying to prove is false, because that statement can either be true or false. Then, using the givens, we can come to a faulty conclusion that contradicts what we already know. For example, you could end up contradicting the fact that a median of a triangle intersects the midpoint of the opposite side, or something else. Therefore, the original statement can't be false, and it must be true.

Let's start with an intuitive, yet extremely easy example. Let's prove the following statement:

Not all computers are laptops.

It's a trivial example, but it's a good way to see how indirect proof works.

First, assume the statement is false. The resulting statement is:

All computers are laptops.

However, we know there are not only laptop computers, there are desktop as well as laptop computers. So this tells us that not all computers are laptops. But that contradicts our statement! Therefore, our original assumption has to be false since it led to a contradiction. Thus, the statement Not all computers are laptops. is true.

Well, this topic wasn't placed in the Geometry section for no reason, so let's do some geometry! This is a basic example.

Problem: In isosceles triangle $ABC$, $\overline{BC}$ is the base. A cevian from $\angle{A}$ to side $BC$ intersects $BC$ at $D$ such that $\overline{BD} \not \cong \overline{CD}$. Prove that $\overline{AD}$ does not bisect $\angle{A}$.

Proof: Using the concept of indirect proof, suppose that $\overline{AD}$ does bisect $\angle{A}$. This would mean that $\angle{BAD} \cong \angle{CAD}$. Since $\triangle{ABC}$ is isosceles with base $\overline{BC}$, $\overline{AB} \cong \overline{AC}$. Finally, by the Reflexive Property, $\overline{AD} \cong \overline{AD}$. By SAS, we have that $\triangle{ABD} \cong \triangle{ACD}$. This congruence means that $\overline{BD} \cong \overline{CD}$. But this is a contradiction, since from our giverns we have that $\overline{BD} \not \cong \overline{CD}$. Therefore, the statement that $\overline{AD}$ bisects $\angle{A}$ is false and therefore, $\overline{AD}$ does not bisect $\angle{A}$. $\Box$

Using the concept of proof by contradiction

Let's say that we want to prove two lines not parallel. (lines $s$ and $t$)

Great! We can use any of the two above facts, so we'll refer to both in the proof.

OK. Our statement that we are trying to prove is assumed to be false. The assumption is that our two lines, $s$ and $t$, are parallel.

Right! Because two angles cannot be congruent and not congruent at the same time, we have reached a contradiction.

We pointed out the contradiction, and now we state that we have proved the contrapositive (if ~original statement -> then ~given) of the original statement.

Naturally, if our contrapositive is correct, then our statement must be correct too. Thus, our two lines are not parallel and we are done. $\blacksquare{}$