The Number of Primes is Finite
The number of primes is finite. Proof: We know that the number of subsets of a set is incommensurably greater than the number of members: {a.b.c} has eight subsets; the integers have uncountably many subsets (maybe of the power of the continuum, maybe not, depending on your axiomatic taste). Consider the set of all finite subsets of the set of primes. The primes, being a subset of the integers, can be only countably infinite. If the number of primes is infinite, the number of finite subsets of primes is uncountably infinite. But to each finite subset of primes there corresponds uniquely an integer, namely the product of the members of the subset. The set of finite subsets of primes is in one-to-one correspondence with a subset of the integers, namely the “square-free” integers, those having no prime factor to a power higher than one. Thus the set of square-free integers and a fortiori the set of all integers is uncountably infinite. But we know that the set of all integers is not uncountably infinite. Thus our hypothesis is false: the number of primes is not infinite. Q.E.D.
See you in Stockholm?
ReplyDeleteJames, Wabulon is offering us a test: he knows the number of primes is infinite, and we are supposed to show where his "proof" went wrong.
ReplyDeleteI figured that. I think I can find it, but it's early in the morning now and I haven't had a beer yet. Hang on.
ReplyDeleteThis:
ReplyDeleteIf the number of primes is infinite, the number of finite subsets of primes is uncountably infinite.
is not true because this:
But to each finite subset of primes there corresponds uniquely an integer, namely the product of the members of the subset.
is true. It is a requirement of uncountability that such a function not exist.
This is interesting, because the set of all finite subsets (SOAFS) of integers is uncountably infinite, so we have one countably infinite set (the integers) whose SOAFS is uncountably infinite, and another countably infinite set (the primes) whose SOAFS is not. Is this unreasonable? Obviously not (because it's true) but I'll also take a stab at why this is so.
The set of primes is smaller than the set of integers. Therefore, it's reasonable to presume that the SOAFS of primes is also the smaller of the two. The unique relationship, embedded in the definition of primeness, that allows a mapping of the SOAFS into the integers, allows it to cross the mathematical line from uncountably to countably infinite.
Or, I may be full of crap.
If the number of primes is infinite, the number of finite subsets of primes is uncountably infinite.
ReplyDeleteis indeed the first false sentence.
We know that the number of subsets of a set is incommensurably greater than the number of members
is true, but that implies nothing about the number of finite subsets of a set.
In fact, contra Andy Stedman, the number of finite subsets of the set of integers is countably infinite.
An injection from them into the integers can be given similarly to the original post, giving a bijection to the square-free integers. Call the prime numbers p_0, p_1, p_2,... Take a bijection from the integers to the natural numbers: f(n)=2n if n>=0, f(n)=-2n-1 if n<0. From a given finite subset of the integers, a_0, a_1,... a_n, map to the product p_{f(a_0)} * p_{f(a_1)} * ... p_{f(a_n)}.
Or, a different injection for computer nerds: a finite subset of integers can be writen as a finite sequence of the symbols 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, - (minus), and "," (comma); as a comma-separated list in decimal notation. Just treat each sequence of symbols as an ASCII string to get a unique integer in some obvious way (since none of those are the null character).
Jared, are you saying Wikipedia led me astray?
ReplyDeletehttp://en.wikipedia.org/wiki/Uncountable
The diagonalization proof technique can also be used to show that several other sets are uncountable, such as the set of all infinite sequences of natural numbers (and even the set of all infinite sequences consisting only of zeros and ones) and the set of all subsets of the set of natural numbers.
Jared got it right. I intentionally blurred the distinction between the set of all subsets and the set of all finite subsets. If the base set is countably infinite, one is uncountably infinite, the other not.
ReplyDeleteGot it.
ReplyDeleteIs this right? I don't see why.
ReplyDeleteIf the number of primes is infinite, the number of finite subsets of primes is uncountably infinite.
BTW I posted that without reading everything above (obviously).
ReplyDeleteIf the number of primes is finite, multiply all of those primes together. Then add 1. What are the divisors of that number?
ReplyDeleteGood job following the thread here, TomG! I'd advise reading the comments before you post, not after.
ReplyDeleteTomG: there are no numbers that big. Mathematicians have yet to discover any numbers with more than approximately 10^17 digits. This highest number also happens to be prime.
ReplyDeleteWrong, Andy. My favourite is the world record number.
ReplyDeleteAlso Wab, no axiom makes P(N) otheh than continuum that I know of.
@Andy Stedman: If the number of integers is finite, then the proof that the number of primes is finite becomes a lot easier. 8-)
ReplyDeleteScineram -
ReplyDeleteTurns out that the continuum issue--an unsolved problem for decades--is undecidable. I.e., youse can have it either way you want, by a suitable axiom.
@Gene Callahan: Who are you?
ReplyDeleteUm, Gene Callahan?
ReplyDelete"Turns out that the continuum issue--an unsolved problem for decades--is undecidable. I.e., youse can have it either way you want, by a suitable axiom."
ReplyDeleteP(N) is continuum. Period.
OK, OK, Scineram. You're maybe bigger than I am and possibly could beat me up. Best to be safe. You're absolutely right.
ReplyDeleteYou want me to give an egzact bijection?
ReplyDeleteOk, I won't bother. I was referring to
ReplyDeletethe integers have uncountably many subsets (maybe of the power of the continuum, maybe not, depending on your axiomatic taste).
You shall read this.