Tell me the concept of Prove by contradiction

Question

Accepted Answer

⚹ Prove by contradiction is a fundamental proof technique used in computer science and mathematics to establish the truth of a statement by demonstrating that assuming the statement is false leads to a contradiction. ⚹ ⚹ Here is a step-by-step explanation of the concept: ⚹ ∻Prove by Contradiction∻ ‖ ▪ ⋮ **Assume the negation**: Start by assuming that the statement you want to prove is false. If the statement is $P$, assume $ eg P$ (not $P$). ‖ ‖ ▪ ⋮ **Logical consequences**: Use logical reasoning and known facts to derive consequences from the assumption $ eg P$. ‖ ‖ ▪ ⋮ **Find a contradiction**: Show that these consequences lead to a contradiction, i.e., a statement that is known to be false or contradicts the original assumptions or known facts. ‖ ‖ ▪ ⋮ **Conclude the original statement**: Since assuming $ eg P$ leads to a contradiction, conclude that $P$ must be true. ‖ ⚹ Example: ⚹ ⚹ Suppose we want to prove that $\sqrt{2}$ is irrational. ⚹ 1. ⚹ Assume the negation: Assume $\sqrt{2}$ is rational. This means $\sqrt{2} = \frac{a}{b}$, where $a$ and $b$ are integers with no common factors (i.e., the fraction is in its simplest form). ⚹ 2. ⚹ Logical consequences: Squaring both sides, we get $2 = \frac{a^2}{b^2}$, which implies $a^2 = 2b^2$. Therefore, $a^2$ is even, which means $a$ must be even (since the square of an odd number is odd). ⚹ 3. ⚹ Find a contradiction: If $a$ is even, let $a = 2k$ for some integer $k$. Substituting back, we get $(2k)^2 = 2b^2$, which simplifies to $4k^2 = 2b^2$ or $2k^2 = b^2$. This implies $b^2$ is even, so $b$ must also be even. ⚹ 4. ⚹ Conclude the original statement: If both $a$ and $b$ are even, they have a common factor of 2, which contradicts our initial assumption that $\frac{a}{b}$ is in its simplest form. Therefore, our assumption that $\sqrt{2}$ is rational must be false, and hence $\sqrt{2}$ is irrational. ⚹ ⚹ This completes the proof by contradiction. ⚹

Sia