It occurred to me this morning that my criticism of the journalism may rest on a platonist assumption. What if the journalist were some sort of intuitionist (Brouwer, et al.) who held that the existence of a number is identifiable with its being constructed or generated?
That's an interesting question. I'm not completely sure, but I suspect even intuitionists would agree that there is no largest prime number. The result does not rely on proof by contradiction or other dubious platonic methods. We have a constructive algorithm that, given any prime number n, will generate a larger yet prime. Consider m:= n! + 1. Either m is prime, or can be factorised into prime factors larger than n.
I assume that constructivists only require an algorithm we know to be in principle computational. (I hope the above is indeed computational in principle. Expanding a factorial surely is - that's just repeated multiplication. But how about checking for prime factorizations? I suppose it should be, as a computer could just do an exhaustive series of divisions by x [for all x: n < x < m] to check that m/x never yields a whole number?) The mere fact that we cannot yet actually compute it, e.g. due to hardware limitations, might not be a problem. Does anyone know for sure: do intuitionists (constructivists) require only that we demonstrate something to be constructable, or must it actually be constructed?
Posts
Yes, that was a bit sloppy of me! I'll update my post to make that clearer... thanks for the pointer.
ReplyDeleteIt is intuitionistically provable. It is even finitarily provable (see Hilbert's "On the infinite"). Of course, if you're an ultrafinitist, you'd believe it false.
ReplyDeleteObviously what Richard said is correct, so intuitionists needn't worry about this, but there is still a misleading aspect to the post. What matters is that the prime be constructable, but it isn't clear that what you've given is yet a construction. A proof that not both of a and b is not-F is not a construction of an F. So a proof that not all of the numbers up to n!+1 are composite is not yet a proof that one of them is prime.
ReplyDeleteAs it turns out in this case, it is a finite procedure to work out whether a particular number is prime, so once you've proven that not all the numbers in a finite set are composite, it is provable that one of them is prime. But you shouldn't be too content to rest with general conclusions like not all of the numbers through n!+1 are composite.
Hi Brian - nice to hear from you! I was hoping that the messy parenthetical section of my final paragraph might complete the construction (since it either determines m to be prime, or else finds its smallest factor, which would itself be prime), but I wasn't very clear. I'm not even entirely sure it works, since (as I'm sure is clear) I know very little about all this stuff!
ReplyDelete