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 N\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=PP=P
  2. Law of Noncontradiction: ¬(P¬P)\neg(P\land \neg P)
  3. Law of the Excluded Middle: P¬PP\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: ¬Q(PQ)¬P\neg Q \land(P\to Q)\to\neg P

Example 1:

Prove that 2\sqrt2 is irrational.
By definition, rational numbers can be written as a/ba/b with a,bZa,b\in\mathbb Z and gcd(a,b)=1\gcd(a,b)=1.
Assume that 2\sqrt2 is rational. Then, let 2=a/b    a2=2b2\sqrt2=a/b\implies a^2=2b^2
As a result, 2a2    2a    4a22\mid a^2\implies2\mid a\implies4\mid a^2
Let 4k=a2=2b2    2k=b2    2b2    2b4k=a^2=2b^2\implies 2k=b^2\implies 2\mid b^2\implies 2\mid b
(2a)(2b)    gcd(a,b)2(2\mid a)\land(2\mid b)\implies\gcd(a,b)\ge2
This is a contradiction. Therefore, the assumption was false, and 2\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=ca+b=c where aa and cc are rational and bb is irrational.
By the closure of the field of rationals under subtraction, ca=bc-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.