Classical Logic and Proof by Contradiction

One method of proof is known as proof by contradiction, an instance of the argument technique called reductio ad absurdum. Based upon the "law of noncontradiction", this method is a two-part process: making an assumption, then deriving a logical contradiction from that assumption. This is known as a "nonconstructive method" because it does not build up to or construct an argument or object in the traditional sense.
Important Note: A specific type of proof by contradiction, proof by infinite descent, uses the least-integer principle (well-ordered property of `\mathbb N`). This involves demonstrating that for any positive integer solution to a problem, there exists a smaller positive integer solution that also works. Therefore, there are no solutions in the positive integers.

Laws of Classical Logic

1. Law of Identity: `P=P`
2. Law of Noncontradiction: `\neg(P\land \neg P)`
3. Law of the Excluded Middle: `P\lor\neg P`

Important Note: Intuitionist logic, on the other hand, deliberately excludes the law of the excluded middle and double-negation elimination.
Important Note: Proof by contradiction is not to be confused with proof by contraposition, which proves the contrapositive of the intended statement. Note that proof by contraposition does not require use of the law of the excluded middle.
Contraposition: `\neg Q \land(P\to Q)\to\neg P`

Example 1:

Prove that `\sqrt2` is irrational.
By definition, rational numbers can be written as `a/b` with `a,b\in\mathbb Z` and `\gcd(a,b)=1`.
Assume that `\sqrt2` is rational. Then, let `\sqrt2=a/b\implies a^2=2b^2`
As a result, `2\mid a^2\implies2\mid a\implies4\mid a^2`
Let `4k=a^2=2b^2\implies 2k=b^2\implies 2\mid b^2\implies 2\mid b`
`(2\mid a)\land(2\mid b)\implies\gcd(a,b)\ge2`
This is a contradiction. Therefore, the assumption was false, and `\sqrt2` is irrational.

Example 2:

Prove that the sum of any rational number and any irrational number is irrational.
Assume, for the sake of contradiction, that the `a+b=c` where `a` and `c` are rational and `b` is irrational.
By the closure of the field of rationals under subtraction, `c-a=b` is rational.
This is a contradiction. Therefore, the assumption was false, and the sum of any rational number and any irrational number is irrational.