Home Software Consultant

Beauty - Proof by Contradiction

2010-08-24T10:38:11+00:00

What is Proof By Contradiction -

To prove something by contradiction, we assume that what we want to prove is not true, and then show that the consequences of this are not possible. That is, the consequences contradict either what we have just assumed, or something we already know to be true (or, indeed, both) - we call this a contradiction.

Axioms

An Axiom is a proposition that is not proved or demonstrated but considered to be either self-evident, or subject to necessary decision. Therefore, its truth is taken for granted, and serves as a starting point for deducing and inferring other (theory dependent) truths.

  1. Additive Identity [ a + 0 = a ] 2. Multiplicative Identity [ a . 1 = 1 ] 3. [ 1 != 0 ] 4. Additive Inverse [ a + (-a) = 0 ] or, it could be written as a - a =0 5. Multiplicative Inverse [ a. 1/a = 1 ] 6. [ a .0 = 0 ] (this axiom has a proof) We all know that we cannot divide by 0. Can this truth(which we simply accept) be proved? We will start by assuming we can divide 1 by 0. From Axiom 5, the multiplicative inverse, for any n

n. 1/n = 1. So, when n = 0 , then 0 . 1/0 = 1

Lets choose 2 numbers, x and y, such that x != y. From axiom 6, we can say

x . 0 = 0 y . 0 = 0 x . 0 = y . 0

Lets, multiply each side by inverse of 0 i.e. 1/0.

(x.0) 1/0 = (y.0) 1/0 We can rewrite it, x(0 . 1/0) = y (0 . 1/0)

Now, 0. 1/0 is 1(multiplicative inverse), which means x = y , but this contradicts our assumption that x!=y.So, this means it was wrong to assume that 1/0 exists. There are some famous proofs using this method -

  1. There are infinite prime numbers ( Euclid proved this in Elements) 2. √2 is irrational*Sources:
  2. Proof by Contradiction2. The Art Of The Infinite ( our lost language of numbers)*