More examples of proof by contradiction

We have had good discussions on mathematical proofs, so I am planning to create a mathematical proof series that will discuss the basics such as direct proof, indirect proof, and proof by mathematical induction.  But before I do that, let me continue with more examples of proof by contradiction.

Proof by contradiction, as we have discussed, is a proof strategy where you assume the opposite of a statement, and then find a contradiction somewhere in your proof. Finding a contradiction means that your assumption is false and therefore the statement is true. Below are several more examples of this proof strategy.

Example 1:  \sqrt{2} irrational.

Example 2: \sqrt{6} is irrational. The proof of this is basically the same as example 1, so it is left as an exercise.

Example 3: Proof that there are infinitely many primes.

Example 4: Knights and Liars

Example 5: \sqrt{2} + \sqrt{3} is irrational. » Read more

Formal Proof of the Infinitude of Primes

In the Infinitude of Primes post, we have shown intuitively that there are infinitely many primes. In this post, we use our intuitive proof to create a more formal proof. The proof was supposedly constructed by Euclid and was shown in his book, The Elements.

Euclid (via Wikimedia)

We are going to use the proof strategy called proof by contradiction. Our proof is summarized as follows: » Read more

Prime Series 2: The Intuition Behind The Infinitude of Prime Numbers

Note: This is the third part of the Prime Number Series

  1. Part I: Introduction to Prime Numbers
  2. Part III: Formal Proof of the Infinitude of Prime Numbers

In Introduction to Prime Numbers, we conjectured that the number of prime numbers is decreasing as the counting numbers increase. In this post, we discuss intuitively that there is no greatest prime, or that there are infinitely many prime numbers.

Before proceeding with our discussion, it is noteworthy to remember that a number can either be prime or composite. We also know that composite numbers are product of primes.

Fragment of the original "Elements" by Euclid (via Wikimedia).

» Read more