I have always enjoyed maths and used to try to solve elementary maths problems as a school kid. I can remember with joy finally solving a simple-to-state problem after hours of thinking about it. Often the solution popped out of my head almost involuntarily after I had spent a lot of time thinking about it* and then almost abandoning the effort. I recalled some history here in an early post that aroused no interest at all.
My son William out of the blue this evening asked me 'are there fewer prime numbers than natural numbers?'. Firstly, I told him that Euclid had proved that the number of primes was infinite in 300BC (a modern proof is here). Then I told him that 'counting' elements in infinite sets was analogous to but an extension of counting elements in finite sets. I then tried to tell him the little I remembered about Cantor's theorem of countable sets which intrigued me as a kid.
I told him if you can put a set into 1 to 1 correspondence with the natural numbers - a bijection - then a set is countable. In this sense there are as many even numbers as natural numbers and, as a consequence of one of Cantor's main theorems, as many rational numbers as natural numbers. There are as many primes as there are natural numbers since the nth prime number can be put into 1:1 correspondence with the number n for n=1,2,3,...... Thus the set of primes is countable.
This I hope answered his question although, to be honest, that a 10 year old asked it was far more interesting than the answer I had to scratch around to recall.
* I think I spent more time trying to think things through then than I do today. My knowledge is greater today but my brain often switches to autopilot mode and I apply knowledge rather than think.
Thursday, April 17, 2008
Subscribe to:
Post Comments (Atom)
Posts
7 comments:
An interesting thing is that there are more real numbers (number on the number line) than natural numbers or rational numbers. In other words there is no one-to-one correspondence between natural numbers and real numbers.
The proof is a proof by contradiction using Cantor's famous diagonal argument. It is sufficient to prove that there are more real numbers between 0 and 1 than natural numbers (because the real numbers between 0 and 1 are a subset of the real numbers). Suppose there was a one-to-one correspondence, then we could enumerate the real numbers between 0 and 1, i.e. write them down as an (infinite) list.
Suppose we have such an enumeration, and consider a number whose first digit is different to the first digit of the first number in the enumeration, whose second digit is different to the second digit of the second number in the enumeration, whose nth digit is different to the nth digit of the nth number of the enumeration, and so on.
Such a number cannot be in the enumeration, because if it was there would be a natural number k for which the kth digit of the kth number in the enumeration is the same as the kth digit of the number we chose.
This contradicts the assumption that we have an enumeration of the real numbers between 0 and 1. Therefore there are more real numbers than natural numbers.
Harry, surely there must be an anti-Rudd angle to all of this.
I believe that Euclid's proof went like this - suppose that there is a largest prime, say p. Consider p(p-1)(p-2)...2 + 1 (or p! + 1). Then this is a prime since none of the numbers 2, ..., p are divisors (and any other potential divisor would have to be composite and therefore divisible by one of these), thus we have a contradiction since p is supposed to be the largest.
I would think that this is still the most common proof which is given in modern maths courses (certainly it's the one I teach).
Stu, p!+1 need not be prime. It can have a factor larger than p.
Harry, if we have assumed that p is the largest prime, then any number greater than p is composite and must have a divisor, d, which is less than or equal to p. Thus if this number divides p!+1, then d does as well, but we can see than none of the numbers up to p can divide p!+1.
My only quibble is your claim that p!+1 is prime. It isn't necessarily.
2X3X5X11X13+1 = 30,031 = 59X509 (both of these are prime). I learnt this from the wikipedia entry on prime numbers.
The logic of Euclid's theorem is right however. If p!+1 is prime then you have an extra prime. If p!+1 isn't prime then it must have a divisor other that 2,3,....p. There is still another prime.
I agree with what you say Harry, it's just that the claim that p!+1 is prime relies on the assumption that p is the largest prime, which of course leads to a contradiction.
Since there is no largest prime, then in general it is certainly not true that p!+1 must be prime, as your example illustrates.
Post a Comment