Proof by Contradiction

စစ်ကိုမုန်း၍ တိုက်ခဲ့သည်




Introduction


Contradict = ဆန့်ကျင်သည်၊

Contradiction = ဆန့်ကျင်ခြင်း

Proof by Contradiction = ဆန့်ကျင်သက်သေပြခြင်း

Proof by Contradiction သည် A Level Mathematics တွင် မေးလေ့ရှိသော မေးခွန်းဖြစ်သည်။

အလွယ်ပြောရလျှင် မူလအဆိုပြုချက်ကို ဆန့်ကျင်ဘက် ယူဆပြီး၊ ယူဆချက်မှားကြောင်း သက်သေပြခြင်းဖြင့် မူလအဆို မှန်ကြောင်း ထောက်ခံခြင်းကို Proof by Contradiction ဟု ခေါ်ပါသည်။

တစ်ခုနှင့်တစ်ခု ပတ်သက်ခြင်းမရှိသော ဖြစ်ရပ်များ (mutually exclusive events) များတွင် မှန်သော အကြောင်းအခြင်း အရာများသည် မည်သည့်အခါမျှ မမှားသကဲ့သို့ မှားသော အကြောင်းအခြင်းအရာများသည် မည်သည့်အခါမျှ မမှန်ပေ။ အဆိုပါ အယူအဆကိုလက်ကိုင်ပြု၍ Proof by Contradiction ပုစ္ဆာများကို ဖြေရှင်းလေ့ရှိသည်။

Examples
  • စုံကိန်းများသည် 2 ၏ ဆတိုးကိန်းများ ဖြစ်သည်။

  • မကိန်းများသည် 2 ဖြင့် စား၍ မပြတ်ပါ။

  • Rational ကိန်းမှန်သမျှသည် အပိုင်းကိန်းပုံစံဖြင့် ဖော်ပြနိုင်သည်။

  • Irrational ကိန်းများသည် အပိုင်းကိန်းပုံစံဖြင့် မဖော်ပြနိုင်ပါ။
စသည်တို့သည် အမြဲမှန်သော မှန်ကန်ချက်များ ဖြစ်သည်။

မှန်သောအကြောင်းအရာကိုသာ မှန်ကြောင်းသက်သေပြနိုင်သည်။ တြိဂံသည် တြိဂံဖြစ်သောကြောင့်သာ တြိဂံဖြစ်ကြောင်း သက်သေပြနိုင်ခြင်း ဖြစ်သည်။ စတုဂံဖြစ်ကြောင်း သက်သေမပြနိုင်ပါ။ တြိဂံမြင်ပါလျှက် တြိဂံဖြစ်ကြောင်း သက်သေပြခိုင်း ခြင်းမှာ လက်တွေ့မဆန်ကြောင်း ဝေဖန်လေ့ရှိသည်။ လက်တွေ့ဆန်မှု မဆန်မှုကို စစ်ဆေးလိုခြင်းမဟုတ်ပဲ၊ ဘာသာရပ် နားလည်တတ်သိမှု၊ အယူအဆကို နားလည်မှု၊ ဝေါ်ဟာရသိရှိမှု၊ ဆင်ခြင်သုံးသပ်နိုင်မှု စသည့် သက်သေပြသူ၏ စွမ်းရည်ကို စစ်ဆေးခြင်းဖြစ်သည်။


Example (1)


Prove by contradiction that $\sqrt{2}$ is an irrational number.

$\sqrt{2}$ သည် irrational ကိန်းတစ်ခု ဖြစ်ကြောင်း သက်သေပြပါ။

Irrational number ဆိုသည်မှာ အဆုံးမရှိ ပြန်မထပ် ဒသမကိန်း တစ်နည်း အပိုင်းကိန်းဖြင့် ဖော်ပြနိုင်ခြင်းမရှိသော မရှိသော ကိန်းများဖြစ်သည်။ ယခုပုစ္ဆာကို သက်သေပြရန် အပိုင်းကိန်း၏ သတ်မှတ်ချက်ကို သိရှိရန်လိုပါသည်။

အပိုင်းကိန်းဆိုသည်မှာ ကိန်းပြည့်နှစ်ခု၏ အချိုးဖြစ်သည်။ ပိုင်းခြေနှင့် ပိုင်းဝေနှစ်ခုလုံးသည် ကိန်းပြည့်များသာ ဖြစ်ရမည်။ ပိုင်းဝေနှင့်ပိုင်းခြေသည် အငယ်ဆုံး ကျဉ်းပိုင်းပုံစံ ဖြစ်ရမည်။ ဆိုလိုသည်မှာ $\displaystyle\frac{p}{q}$ ဟုရေးလျှင် $p$ နှင့် $q$ သည် $1$ မှ လွဲ၍ မည်သည့်ကိန်းနှင့်မှ စား၍ မပြတ်တော့သော ကိန်းပြည့်များ ဖြစ်ရမည်။ တစ်နည်းဆိုသော် $p$ နှင့် $q$၏ အကြီးဆုံး ဘုံဆခွဲကိန်းမှာ $1$ သာ ဖြစ်ရမည်။ အကြီးဆုံး ဘုံဆခွဲကိန်းမှာ $1$ သာရှိသော ကိန်းနှစ်လုံးကို relatively prime numbers (သို့မဟုတ်) coprime numbers ဟုခေါ်သည်။ အပိုင်းကိန်းတစ်ခု တွင် ပိုင်းဝေနှင့်ပိုင်းခြေသည် coprime numbers များ ဖြစ်ရမည်။

$\sqrt{2}$ သည် irrational ကိန်းတစ်ခု ဖြစ်ကြောင်း သက်သေပြပါ ဟုမေးထားသည် ဖြစ်ရာ ပေးထားအဆိုကို ဆန့်ကျင် ယူဆပါမည်။

ဆန့်ကျင် ယူဆချက်မှာ $\sqrt{2}$ သည် rational ကိန်းတစ်ခု ဖြစ်သည်။

ထို့ကြောင့် $\sqrt{2}$ ကို $\displaystyle\frac{p}{q}$ ဟူ၍ ဖော်ပြနိုင်သည်။ $p$ နှင့် $q$ တွင် $1$ မှလွဲ၍ တူညီသော ဘုံဆခွဲကိန်း မရှိပါ။

ထို့ကြောင့် $p^2=2q^2$ ဖြစ်ပါမည်။

$p^2$ နှင့် $q^2$ နှစ်ထပ်ကိန်းများ (perfect square) များ တွေ့ရပါသည်။

နှစ်ထပ်ကိန်းများ ၏ ဂုဏ်သတ္တိမှာ မကိန်း ၏ နှစ်ထပ်ကိန်းသည် မကိန်း သာ ဖြစ်ပြီး စုံကိန်း၏ နှစ်ထပ်ကိန်းသည် စုံကိန်းသာ ဖြစ်သည်။

စုံကိန်းတစ်ခုသည် 2 ဖြင့်စား၍ ပြတ်သောကြောင့် မည်သည့်ကိန်း $k$ အတွက် မဆို $2k$ သည်စုံကိန်း ဖြစ်ပြီး စုံကိန်း မှ $1$ လျော့လျှင် (သို့) စုံကိန်းကို $1$ တိုးလျှင် မကိန်းဖြစ်သည်။

ထို့ကြောင့် မည်သည့်ကိန်း $k$ အတွက် မဆို $2k\pm 1$ သည် မကိန်းဖြစ်သည်။

$2q^2$ သည် စုံကိန်း ဖြစ်သောကြောင့် $p^2$ သည် စုံကိန်းဖြစ်ပြီး $2q^2$ သည် စုံကိန်းဖြစ်ရန် $q^2$ သည် မကိန်းသာ ဖြစ်ရမည်။

ထို့ကြောင့် $q$ သည် မကိန်း ဖြစ်သည်။

ထို့ကြောင့် $p$ သည် စုံကိန်း ဖြစ်သည်။ ထို့ကြောင့် $p =2k$ ဟု ယူဆနိုင်သည်။

ထို့ကြောင့် $(2k)^2=2q^2$ ဖြစ်မည်။

ထို့ကြောင့် $(q^2=2k^2$ ဖြစ်မည်။ ရလဒ်အရ $q^2$ သည် စုံကိန်းဖြစ်သည်။

ထို့ကြောင့် $q$ သည် စုံကိန်း ဖြစ်သည်။

အကြောင်းအခြင်းအရာ ညီညွတ်ခြင်း မရှိသောကြောင့် $\sqrt{2}$ သည် rational ကိန်းတစ်ခုဖြစ်သည် ဆိုသော ယူဆချက်မှန်ပါ။

ထို့ကြောင့် မူလအဆို $\sqrt{2}$ သည် irrational ကိန်းတစ်ခု ဖြစ်သည်ဆိုသည့် အဆိုမှာ မှန်သည်ဟု သက်သေပြနိုင်သည်။


Solution

Assume that $\sqrt{2}$ is a rational number.

Then$\sqrt{2}=\displaystyle \frac{p}{q}$ where $p$ and $q$ have no common factor.

$\therefore\ \ p^2=2q^2$.

$\therefore\ \ p^2$ is even that implies $p$ is even and hence $q^2$ and $q$ must be odd.

Since $p$ is even, assume that $p=2k$ where $k$ is an integer.

$\therefore\ \ (2k)^2=2q^2$ and $q^2 = 2k^2$ that implies $q$ is an even number and this is contradiction.

Hence, we can say that $\sqrt{2}$ is an irrational number.

Example (2)


Prove by contradiction that for any integer $n>1$, $n$ and $n+1$ do not have a prime factor in common.

$1$ ထက်ကြီး သောမည့်သည့်ကိန်းပြည့် $n$ အတွက်မဆို $n$ နှင့် $n+1$ တွင် တူညီသော သုဒ္ဓဆခွဲကိန်း မရှိကြောင်း ဆန့်ကျင်သက်သေပြနည်း ဖြင့် သက်သေပြပါ။

$n$ နှင့် $n+1$ သည် ရှေ့နောက်ကပ်လျှက် ကိန်းပြည့်နှစ်ခု ဖြစ်သောကြောင့် ဆခွဲကိန်း မရှိနိုင်ပါ။ မရှိကြောင်း ဆန့်ကျင် သက်သေပြရမည် ဖြစ်သည်။

ထို့ကြောင့် $1$ ထက်ကြီး သောမည့်သည့်ကိန်းပြည့် $n$ အတွက်မဆို $n$ နှင့် $n+1$ တွင် တူညီသော သုဒ္ဓဆခွဲကိန်း ရှိသည်ဟု ယူဆမည်။

အဆိုပါ သုဒ္ဓဆခွဲကိန်းသည် $p$ ဖြစ်ပါစေ။

ထို့ကြောင့် $n=pk$, $k$ သည် ကိန်းပြည့်တစ်ခု ဖြစ်သည်။

နှင့် $n+1 = pk$, $k$ သည် ကိန်းပြည့်တစ်ခု ဖြစ်သည်။

ထို့ကြောင့် $(n+1)-n = p(h-k)$ ဖြစ်မည်။

ဆက်လက်ဖြေရှင်းသော် $p (h-k) = 1$ ဖြစ်မည်။

အထက်ပါညီမျှခြင်းတွင် $p$ နှင့် $h-k$ တို့သည် မတူညီသော ဆခွဲကိန်းများ ဖြစ်ကြသည်။

သို့ရာတွင် $1$ ၏ ဆခွဲကိန်းမှာ $1$ သာ ဖြစ်သောကြောင့် $p$ နှင့် $h-k$ တို့သည် မတူညီသော ဆခွဲကိန်းများ ဖြစ်ကြသည် ဆိုသော ရလဒ်မမှန်တော့ပါ။ ထို့ကြောင့် ဆန့်ကျင်ယူဆချက်မှားပြီး မူလအဆို မှန်ကြောင်း သက်သေပြနိုင်သည်။


Solution

Suppose that for any integer $n>1$, $n$ and $n+1$ have a prime factor $p$.

Then we have $n=pk$ and $n+1=ph$ where $k$ and $h$ are distinct integers.

Hence $(n+1)-n = p(h-k)$ that implies $p(h-k)=1$.

Here $p$ and $h-k$ are distinct integers but 1 only has itself as a factor so this is a contradiction.

Thus, for any integer $n>1$, $n$ and $n+1$ do not have a prime factor in common.

Example (3)


Prove by contradiction that the curves $ y=x^4+7x^2+5$ and $ y=x^2$ do not intersect each other.

$ y=x^4+7x^2+5$ နှင့် $ y=x^2$ တစ်ခုနှင့် တစ်ခု မဖြတ်ကြောင်း သက်သေပြပါ။

သိရှိထားမည့် အချက်မှာ Curve နှစ်ခု တစ်ခုနှင့်တစ်ခု ဖြတ်လျှင် ညီမျှခြင်းနှစ်ခုကို တပြိုင်နက် ပြေလည်စေနိုင်သော $x$ တန်ဖိုး ရှိသည်။ ဆန့်ကျင် အဆိုပြုချက် $ y=x^4+7x^2+5$ နှင့် $ y=x^2$ တစ်ခုနှင့်တစ်ခု ဖြတ်သည်ဟုယူဆ၍ ဖြတ်မှတ်ရှာမည်။ ဖြတ်မှတ်မရှိသောအခါ ယူဆချက်မှားယွင်းကြောင်း မူလအဆို မှန်ကြောင်း သက်သေပြနိုင်ပါသည်။


Solution

$ C_1 :\quad y=x^4+7x^2+5$

$ C_2 :\quad y=x^4+7x^2+5$

Assume that $ C_1$ and $ C_2$ intersect each other.

At the point of intersection,

$ x^4+7x^2+5 = x^2$

$ x^4+6x^2+5 = 0$

$ \therefore \quad (x^2+5)(x^2+1)=0$

$ \therefore \quad x^2= -5 \ \text{or}\ x^2=-1$

There is no real solution for $x$ and our assumption is not true.

Hence the curves $ y=x^4+7x^2+5$ and $ y=x^2$ do not intersect each other.

Example (4)


Use proof by contradiction to show that there exist no integers a and b for which $25a + 15b = 1$.

ဆန့်ကျင် သက်သေပြနည်းကို သုံး၍ $25a + 15b = 1$ ကို‌ ပြေလည်စေသော ကိန်းပြည့်တန်ဖိုး $a$ နှင့် $b$ မရှိကြောင်း သက်သေပြပါ။

သိရှိထားရမည့် အချက်မှာ ကိန်းပြည့်များ၏ ပေါင်းလဒ်၊ နုတ်လဒ်နှင့် မြှောက်လဒ်တို့မှာ ကိန်းပြည့်များသာ ဖြစ်သည်။


Solution

Let us assume that there exist integers $a$ and $b$ for which $25a + 15b = 1$.

Since $25a + 15b = 1$, dividing both sides with 5, $5a + 3b =\displaystyle \frac{1}{5}$.

Since $a$ and $b$ are integers, both $5a$ and $3b$ are integers and their sum $5a + 3b$ must be integers.

But $\displaystyle \frac{1}{5}$ is not integer and so this is contradiction.

So, our assumption is false and the original statement is true.

Therefore, there do not exist integers $a$ and $b$ for which $25a + 15b = 1$.

Exercises


  1. Prove by contradiction that $\sqrt{3}$ is irrational.

  2. Prove by contradiction that the sum of a rational number and an irrational number is irrational.

  3. Prove by contradiction that there are infinitely many prime numbers.

  4. Prove, by contradiction that $\displaystyle\frac{a+b}{2} \geq \sqrt{a b} \quad \forall\ a, b \in \mathbb{N}$.

  5. Prove by contradiction that if $m^{2}=10$ then $m$ is not a rational number.