Proof by Contradiction

• The method is rooted in the Law of Excluded Middle, which states that for any proposition $P$, either $P$ is true or its negation $\neg P$ is true.

• It also utilizes the Law of Non-Contradiction, which asserts that a statement and its negation cannot both be true simultaneously in the same context.

• In formal logic, this is represented as $((\neg P \implies Q) \land \neg Q) \implies P$, meaning if the negation of $P$ implies a false statement $Q$, then $P$ must be true.

• This approach is particularly useful when a direct proof is difficult because the properties of the 'negation' are easier to manipulate than the properties of the original statement.

Step-by-Step Methodology

• Step 1: State the Assumption: Clearly write down the negation of the statement. For example, to prove $x$ is irrational, start with 'Assume $x$ is rational.'
• Step 2: Use Definitions: Convert the assumption into a mathematical form. If assuming a number is rational, write it as $\frac{a}{b}$ where $a, b$ are integers with no common factors.
• Step 3: Perform Algebraic Manipulation: Work through logical steps using established theorems and algebraic rules to explore the consequences of the assumption.
• Step 4: Identify the Conflict: Look for a result that contradicts a known fact or the initial conditions of your assumption (e.g., finding that $a$ and $b$ actually share a common factor).
• Step 5: Conclude: Explicitly state that the contradiction proves the initial assumption false and the original statement true.

• Contradiction vs. Counter-example: A counter-example is used to prove a general statement is false, whereas proof by contradiction is used to prove a statement is true.

• Negation Clarity: In direct proof, you build the result; in contradiction, you must be extremely precise in how you negate the original claim to avoid logical errors.

• Incorrect Negation: A common error is failing to negate the statement correctly. For example, the negation of 'All $x$ have property $P$' is 'There exists at least one $x$ that does not have property $P$', not 'No $x$ has property $P$'.

• Circular Reasoning: Ensure that you do not use the statement you are trying to prove as a justification within the proof itself.

• Stopping Too Early: Students often find a strange result and assume it is a contradiction. You must clearly link the result to a specific violation of your initial assumption or a known mathematical law.