Indirect Proof: Contraposition, Contradiction আর Counterexample

গত পর্বে direct proof দেখেছি: p ধরে নিয়ে q-তে পৌঁছানো। কিন্তু সবসময় p থেকে q পর্যন্ত সোজা রাস্তা পাওয়া যায় না। তখন ঘুরপথ ধরতে হয়, যাকে বলে indirect proof। এই পর্বে তিনটা কৌশল দেখব: contraposition, contradiction আর counterexample। শেষে দেখব একটা ভুল proof, যেটা "প্রমাণ" করে 1 = 2। (Section 1.7)

Proof by contraposition#

পর্ব ২-এ দেখেছি, p → q আর তার contrapositive ¬q → ¬p সবসময় সমান। তাই p → q সরাসরি প্রমাণ করা কঠিন হলে, তার বদলে ¬q → ¬p direct proof দিয়ে প্রমাণ করলেই চলে: ¬q ধরে নিই, দেখাই ¬p।

উদাহরণ ১#

Theorem: n integer আর 3n + 2 বিজোড় হলে, n বিজোড়।

সরাসরি করতে গেলে "3n + 2 = 2k + 1" থেকে n সম্পর্কে কিছু বের করা ঝামেলার। Contrapositive অনেক সহজ: "n জোড় হলে, 3n + 2 জোড়।"

Proof: ধরি n জোড় (মানে conclusion মিথ্যা)। তাহলে কোনো integer k-এর জন্য n = 2k।

3n + 2 = 3(2k) + 2
       = 6k + 2
       = 2(3k + 1)
       = 2j            যেখানে j = 3k + 1

তাই 3n + 2 জোড় (মানে hypothesis মিথ্যা)। আমরা ¬q → ¬p দেখিয়েছি, তাই p → q সত্য। ∎

উদাহরণ ২#

Theorem: n integer হলে, n² বিজোড় হলে n বিজোড়।

Proof (contraposition): ধরি n জোড়, মানে n = 2k। তাহলে n² = 4k² = 2(2k²), তাই n² জোড়। জোড় n থেকে জোড় n² পেলাম, তাই contrapositive অনুযায়ী n² বিজোড় হলে n বিজোড়। ∎

Proof by contradiction#

কোনো statement p প্রমাণ করতে: ধরে নিই p মিথ্যা, তারপর যুক্তি দিয়ে একটা অসম্ভব জিনিসে পৌঁছাই, যেমন একই সাথে r আর ¬r। সঠিক যুক্তিতে অসম্ভব কিছু আসতে পারে না, তাই ধরে নেওয়াটাই ভুল ছিল। মানে p সত্য।

Logic-এর ভাষায়: আমরা দেখাই ¬p → F সত্য। এর contrapositive T → p, আর সেটা সত্য হতে পারে শুধু p সত্য হলে।

p → q প্রমাণের বেলায় এর মানে: p আর ¬q দুটো একসাথে ধরে নিয়ে বিরোধ খোঁজা।

শার্লক হোমসের পদ্ধতিও এটাই: অসম্ভবগুলো বাদ দিলে যা বাকি থাকে, সেটাই সত্য।

উদাহরণ: √2 irrational#

Theorem: √2 irrational, মানে দুটো integer-এর ভাগফল আকারে লেখা যায় না।

Proof: উল্টোটা ধরি: √2 rational। তাহলে এমন integer a আর b আছে (b ≠ 0) যে √2 = a/b, আর ভগ্নাংশটা লঘিষ্ঠ আকারে, মানে a আর b-এর কোনো common factor নেই। (যেকোনো ভগ্নাংশকে কেটে এভাবে ছোট করা যায়।)

দুই পাশে square করি:

2   = a² / b²
2b² = a²

তাই a² জোড়। a বিজোড় হলে a² বিজোড় হতো (গত পর্বের প্রথম উদাহরণ), তাই contrapositive অনুযায়ী a² জোড় মানে a-ও জোড়। তাহলে কোনো integer c-এর জন্য a = 2c:

2b² = (2c)² = 4c²
b²  = 2c²

তাই b²-ও জোড়, আর একই যুক্তিতে b-ও জোড়।

তাহলে a আর b দুটোই জোড়, মানে 2 দুটোরই factor। কিন্তু আমরা ধরে নিয়েছিলাম a আর b-এর কোনো common factor নেই। বিরোধ। তাই শুরুর ধারণাটা ভুল: √2 irrational। ∎

If and only if প্রমাণ#

p ↔ q আকারের theorem প্রমাণ করতে দুই দিকই দেখাতে হয়: p → q এবং q → p। (পর্ব ২: biconditional মানে দুই দিকের implication।)

Theorem: n integer হলে, n বিজোড় if and only if n² বিজোড়।

Proof: দুই দিক আমরা আগেই প্রমাণ করেছি:

• n বিজোড় হলে n² বিজোড়: গত পর্বের direct proof
• n² বিজোড় হলে n বিজোড়: এই পর্বের উদাহরণ ২ (contraposition)

তাই n বিজোড় ↔ n² বিজোড়। ∎

Counterexample: একটাই যথেষ্ট#

∀x P(x) মিথ্যা প্রমাণ করতে হাজারটা উদাহরণ লাগে না। এমন একটা x খুঁজে পেলেই হয়, যার জন্য P(x) মিথ্যা। একে বলে counterexample। (Section 1.4-এর De Morgan: ¬∀x P(x) ≡ ∃x ¬P(x)।)

দাবি: "প্রতিটা positive integer দুটো integer-এর square-এর যোগফল।"

1 = 0² + 1² আর 2 = 1² + 1² দেখে মনে হতে পারে কথাটা সত্য। কিন্তু 3 দেখি: 3-এর চেয়ে ছোট বা সমান square শুধু 0 আর 1, কারণ 2² = 4 তো 3-এর চেয়ে বড়। এদের দুটো নিয়ে যোগ করলে পাওয়া যায় 0 + 0 = 0, 0 + 1 = 1, বা 1 + 1 = 2, কখনো 3 না। তাই 3 একটা counterexample, দাবিটা মিথ্যা।

Code-এর ভাষায়: একটা failing test case-ই বলে দেয় function-এ bug আছে।

Proof-এ ভুল: "1 = 2"#

নিচের "proof" টা দেখুন। প্রতিটা ধাপ ঠিক মনে হয়, কিন্তু শেষে আসে 2 = 1:

1. a = b                      Premise
2. a² = a·b                   (1)-এর দুই পাশে a দিয়ে গুণ
3. a² - b² = a·b - b²         (2)-এর দুই পাশ থেকে b² বিয়োগ
4. (a - b)(a + b) = b(a - b)  (3)-এ algebra
5. a + b = b                  দুই পাশকে (a - b) দিয়ে ভাগ
6. 2b = b                     (5)-এ a-এর জায়গায় b, কারণ a = b
7. 2 = 1                      (6)-এর দুই পাশকে b দিয়ে ভাগ

ভুলটা কোথায়? নিজে খুঁজে তারপর উত্তর দেখুন।

Practice#

প্রশ্ন ১. Contraposition দিয়ে প্রমাণ করুন: n integer আর n² জোড় হলে, n জোড়।

প্রশ্ন ২. Counterexample দিয়ে ভুল প্রমাণ করুন: "প্রতিটা prime number বিজোড়।"

প্রশ্ন ৩. Contradiction দিয়ে প্রমাণ করুন: সবচেয়ে বড় কোনো integer নেই।

শেষ কথা#

• Contraposition: p → q এর বদলে ¬q → ¬p প্রমাণ করুন, কারণ দুটো সমান।
• Contradiction: যা প্রমাণ করতে চান তার উল্টো ধরে নিন, তারপর একটা অসম্ভব জিনিসে পৌঁছান।
• If and only if: দুই দিকের implication আলাদা আলাদা প্রমাণ করুন।
• Counterexample: ∀x P(x) ভুল প্রমাণ করতে একটা উদাহরণই যথেষ্ট।
• Proof-এর প্রতিটা ধাপ যাচাই করুন, বিশেষ করে শূন্য দিয়ে ভাগ।

বইয়ের পরের section-এ (1.8) আছে আরও কৌশল: case ধরে ধরে প্রমাণ (proof by cases), existence proof, আর কোন সমস্যায় কোন পদ্ধতি ধরবেন।