After pages and pages of posts in a thread called "How to prove God exists.", and no such proof forthcomming, beyond threats, insults, repetitions of definitions and empty questions, claims and completely unrelated google-searches, I think it is time to show a "How to prove..."
I know that mathematical proofs follow a slightly more rigid standard, and use a more formal language and approach. Still, I think it is interesting to see that such a proof manages to do its job without any needs to insult anyone, that every claim can in itself be traced back to a "true" statement, and that it doesn't have to constantly repeat its definitions to achive anything.
For this example, I would like to present one of my favorites: Prime factorization. It is a very basic and useful concept of elementary numbers theory, and the proof is complex enough to be entertaining.
So, without further ado... into the fray.
-------------------------------------------------------------------------
Assertion: Every natural number greater than 1 can be represented by exactly one unique product of prime numbers. (*)
Some definitions, for those who really don't know the matter, or those who like to nitpick.
A "natural number" is one of those numbers by which we count: {1,2,3,4....}. There is an infinite amount of natural numbers.
A "prime number" is a natural number which can only divided without rest by 1 and itself. {1}, though it technically falls under this definition, is not regarded as a prime number. The first prime numbers thus are {2,3,5,7,11,13,17,19,23....}. There is an infinite amount of prime numbers. (Something that we will not prove today.)
"Divided without rest", for those who do not know, means to be completly divided into equal natural numbers. For simplicity the "without rest" is usually left off. So it can be said that "2 divides 6" or " 4 is not a divider of 9".
So, back to our assertion.
This proof will consist of two parts. First, we will prove that there is at least on product of prime numbers to represent each natural number.
Each natural number
n > 2 falls under one of two cases:
1) It is a prime number.
It can not be divided by anything else, the prime factorization thus consist of only one factor: the number n itself.
2) It is not a prime number.
It can be divided by a set of other numbers, called the "dividers".
In this set, there is a smallest number. (In every set of natural numbers, there is a minimum number. This is another true assertion that we will not prove today. I hate to call it 'obvious', but it is very basic.)
This smallest divider of a natural number n is a prime number.
(And yet another assertion, which we should prove. It's easy to do. Small sidetrack incomming
Let's call this smallest divider
d, and assume that it is NOT a prime number.
Thus there exist at least two other numbers
a and
b, where
a *
b =
d, where
a <
d and
b <
d. (To carry on, we only need to consider one of these two. It works eqally well for
a and
b. Also of course we disregard the 1 and d itself as trivial.)
So we know that
a is a divider of
d. A factor in a product is always a divider of that product.
For that reason, we also know that
a is a divider of our original number
n.
So
a is smaller than
d and is a divider of
n. But we started with the assumption that
d is the smallest divider of
n.
That is a contradiction, and thus the assumption that a not prime number
d can be the smallest divider of a natural number
n must be false.
The opposite must be correct... so we have indeed proven that the smallest divider of any natural number is a prime number.
(This method is called "inverse proof" or "proof by contradiction". We will use it again later.)
So back to our prime factorization:
We have established that every natural number
n can be divided by a smallest divider
d, which is a prime number.
So
n =
d *
m.
This new number
m, the remaining factor in
n, is now either a prime number, or it is not. (What else could it be?)
Thus we can go back to step one, and do the same thing to this new number.
Because all natural numbers are finite, they can all be written as a finite product of natural numbers. Thus at some point we will reach an end of this repeating factorization, when the last factor is a prime number.
Thus every natural number can be written as a product of prime numbers.
q.e.d. step 1. (Quod erat demonstrandum - which has been to demonstrate)
Step 2: we have shown that there is one way to represent any natural number as a product of prime numbers. Now we have to show that there is only
one such product,
(*) disregarding the sequence of factors. In a product, the sequence of different factors does not matter. This is called "commutativity".
We will do that with an inverse proof again. So we start off with assuming that there is a set of natural numbers, for which there are at least two different sets of prime factors.
As said above, in every set of natural numbers, there is a smallest number.
So we will call this smallest number again
n. It has at least two sets of prime factors, thus it can be written in this way.
n =
p1 *
p2 *
p3 *
... *
pk = q1 *
q2 *
q3 * ... *
ql
Each of the
p prime factors must be different from each of the
q prime factors. There cannot be two identical factors in these two products.
Why? If we assume that there were identical factors, we could remove this identical factor from both products, to get a new number which could be written by two different products... and this new number would be smaller than our original. But we said the original number was the smallest that could be written this way. This contradiction tells us that the assumption is false: there cannot be any identical factors in these two products.
Now that we know that, we can pick some numbers to work with. Let's say we order the
p's and
q's according to size, and thus
p1 and
q1 are the smallest of their respective sets. We already know that they are not identical, so one is smaller than the other.
Let's say - without limitation of generality - that
p1 < q1
We can do that without problems. These are only placeholder names. If in reality,
q1 would be smaller, we would simply change the names - call
q p and vice versa and work from there.
Now let's do a little mathemagic: We define three new numbers.
a =
n / p1
That means it is now the product of the prime numbers
p2...pk.
This representation must be unique, because
a must be smaller than
n (because we divided it by something), and we said that
n is the smallest natural number with more that one prime factor representations.
b = n
/ q1
Same as above, only that it is now the product of the prime numbers
q2...ql.
c = n -
p1 *
b
Why not? Just another number with we can have fun with. And fun we will have. We will do a few transformations with this equation. First, we will replace
n with the two lines from above.
c = p1 * a - p1 * b
c = q1 * b - p1 * b
We can put the factor
p1 outside of the brackets in the first line, and the factor
b in the second line, getting us to.
c = p1 * (a-b)
c = (q1 - p1) *b
And, of course both being equal, we can simplify this equation to
p1 * (a-b) = (q1 - p1) *b
So, what do we have gained? Doesn't look like much, does it?
But wait! We can see that
p1 is a single factor in this equation. That means it
divides it.
p1 | (q1 - p1) *b ( "|" just means "divides")
Now if a number divides a product, that means it divides at least one of the factors in this product. (This is another basic theorem, called the "Lemma of Euklid". We will not prove it today.)
Thus
p1 divides either
(q1 - p1) or it divides
b. But we already know it does not divide
b.
b is the product of all the
q's... and we have already learned that there cannot be any factor
p in the
q's.
So
p1 divides
(q1 - p1). And a final assertion that is indeed true but that we will not prove today: if a number divides some other two numbers, it also divides a sum of these other numbers.
If a | b and a | c then a | (b + c).
We will use that to simplify the last expression. Knowing that of course
p1 divides itself, we get to understand that
p1 | (q1 - p1) + p1.
Solving the brackets the
p1 cancel out, leaving us with
p1 | q1
p1 is a divider of
q1.
But that again is a contradiction. Both
p1 and
q1 are different prime numbers. There is no way one can divide the other.
That means that the whole assumptions on which this math-rant was based in false.
n is not the smallest number for which there are more than one prime factorizations. And if there isn't a smallest number, that means that there is NO number of such a kind.
q.e.d. part 2.
So, for all those who managed to walk through this... this is how you prove things. You make assumptions, follow them through to either show them correct or false. You base them on other proven assertions, down to some fundamental "truths" in your system.
(Disclaimer: the second step of the proof is of at least medium complexity. I had to translate all the math terms into English, I had to write it down without correct mathematical connotations, and I only proof-read it once. So if there are any mistakes in this post, just let me know.)