As of May 4 2007 the scripts will autodetect your timezone settings. Nothing here has to be changed, but there are a few things

## Sunday, January 23, 2011

### Proof by contradiction ( M381-NT#2 )

M381 Unit 1 Foundations is about
- number patterns,
- proof by mathematical induction,
- divisibility and the division algorithm
- GCD and LCM ( greatest common divisor and least common multiple )
- the Euclidean algorithm
- solving linear Diophantine equations

Unit 1 also contains the proof of the method of mathematical induction. 'The proof of proof by induction'. This post is part 1 of a forthcoming series with an in-depth explanation of this proof. We begin with the concept of proof by contradiction.

If finding a direct proof fails we can try proving by contradiction. If we have to prove a proposition P we then assume ~P and show that this assumption implies a contradiction and thus ~P is false or P is true.

#### Example

Show that $\sqrt{2}$ is irrational ( can not be expressed as a fraction ).

We assume that $\sqrt{2}$ is rational ( not irrational ) and can thus write it as follows: $$\sqrt{2} = \frac{p}{q}$$ where $(p,q)=1$ ( have no common divisors, are relatively prime ).

Then:
$\sqrt{2} = \frac{p}{q}$
$2 = \frac{p^2}{q^2}$
$p^2 = 2q^2$
So $p^2$ is even. Since the square of an odd number is always odd and the square of an even number is always even, we know that $p$ must be even and can thus be factorized to $2r$.

Then:
$\sqrt{2} = \frac{2r}{q}$
$2 = \frac{4r^2}{q^2}$
$q^2 = 2r^2$
So q can be factorized further as well to $2s$.

Then:
$(p,q) = (2r,2s) = 2(r,s) > 1$.
This is clearly a contradiction and thus proves that $\sqrt{2}$ must be irrational.

## Welcome to The Bridge

Mathematics: is it the fabric of MEST?
This is my voyage
My continuous mission
To uncover hidden structures
To create new theorems and proofs
To boldly go where no man has gone before

(Raumpatrouille – Die phantastischen Abenteuer des Raumschiffes Orion, colloquially aka Raumpatrouille Orion was the first German science fiction television series. Its seven episodes were broadcast by ARD beginning September 17, 1966. The series has since acquired cult status in Germany. Broadcast six years before Star Trek first aired in West Germany (in 1972), it became a huge success.)