Transcript Axioms and Theorems

Mathematical Proof
A domino and chessboard problem
A domino and chessboard problem
Imagine a chessboard has had two opposing corners
removed. A special prize for the first group to cover the
remaining squares with dominoes. They can’t overlap!
Impossible?
Trial and error seems to show it can’t be done.
How can we be sure without trying every
possible combination (of millions)?
Proving that the domino problem is
impossible.
Proving that the domino problem is
impossible.
A domino can only cover two adjoining
squares, so these two adjoining squares
MUST be of different colours as no two
adjoining squares are the same colour.
Covering a black and a white
square
Proving that the domino problem is
impossible.
Therefore the first 30 dominoes (wherever
they are put) must cover 30 white squares
and 30 black.
This MUST leave two black squares
uncovered. And since these can’t be
together, they cannot be covered by one
domino. Therefore it is impossible.
Proof
Note we have proved this without having
to try every combination, and our logic
shows that the proof has to be true for any
arrangement of dominoes.
Science can NEVER
be this certain
Remember syllogisms?
premises
• All human beings are mortal
• Socrates is a human being
• Therefore Socrates is mortal
conclusion
Mathematical proof
Mathematical proof is similar in structure to a
syllogism.
In maths we start with axioms (“premises”).
These are the starting points and basic
assumptions.
We then use deductive reasoning to reach a
conclusion, known in maths as a theorem.
For example, the axioms of
arithmetic
•
•
•
•
•
•
•
For any numbers m, n
m + n = n + m and mn = nm
For any numbers m, n and k
(m + n) + k = m + (n + k) and (mn)k = m(nk)
For any numbers m, n and k
m(n + k) = mn + mk
There is a number 0, which has the property that for any number n
n+0=n
There is a number 1 which has the property that for any number n
nx1=n
For every number n, there is a number k such that
n+k=0
For any numbers m, n and k
if k ≠ 0 and kn = km, then n = m
Mathematical proof
Mathematical proof aims to show using
axioms and logic that something is true in
all circumstances, even if all
circumstances cannot be tried. Once
proved mathematically, something is true
for all time.
Another example
The square root of 2 is an irrational
number (cannot be written as a fraction)
This is a proof by Euclid who used the
method of proof by contradiction.
Proof by contradiction
This starts by assuming by something is
true, and then showing that this cannot be
so.
Euclid’s proof that √2 is irrational
Euclid started by assuming that √2 is
rational
i.e.
√2 = p/q
Euclid’s proof that √2 is irrational
√2 = p/q
square both sides
2 = p2/q2
and rearrange
2q2 = p2
Euclid’s proof that √2 is irrational
2
2q
=
2
p
If you take any number and multiply it by 2
it must be even, this means that p2 is an
even number. If a square is an even
number, the original number (p) itself must
be even. Therefore p can be written as p=
2m where m is a whole number.
Euclid’s proof that √2 is irrational
2q2 = p2
If p= 2m where m is a whole number,
2q2 = (2m)2 = 4m2
Divide both sides by 2 and we get
q2 = 2m2
Euclid’s proof that √2 is irrational
q2 = 2m2
By the same argument as before, we know q2 is
even and so q must also be even so can be
written as q = 2n where n is a whole number.
Going back to the start
√2 = p/q = 2m/2n
Euclid’s proof that √2 is irrational
√2 = p/q = 2m/2n
This can be simplified to
√2 = m/n
And we are back where we started!
Euclid’s proof that √2 is irrational
√2 = m/n
This process can be repeated over and
over again infinitely and we never get
nearer to the simplest fraction. This means
that the simplest fraction does not exist,
i.e. our original assumption that √2 = p/q is
untrue!
This shows that √2 is indeed irrational.
Andrew Wiles
Euclid’s proof is a very simple one. When
Andrew Wiles proved that there are no
whole number solutions for the following
equation
y n + x n = zn
for n > 2
his proof was over 100 pages long and
only 6 other mathematicians in the world
could understand it!
http://www.youtube.com/watch?v=kBw_
i6tlQfU
Homework
Find the shortest
Mathematical proof
that you can find and
print it out. Bring it to
the next lesson so
you can stick it in
your ToK books.