False Proof – There are Finitely Many Primes

Problem: Show there are finitely many primes.

“Solution”: Suppose to the contrary there are infinitely many primes. Let P be the set of primes, and S the set of square-free natural numbers (numbers whose prime factorization has no repeated factors). To each square-free number n \in S there corresponds a subset of primes, specifically the primes which make up n‘s prime factorization. Similarly, any subset Q \subset P of primes corresponds to a number in S, since we can simply multiply all numbers in Q together to get a square-free number.

Thus we have shown a bijection between S and the power set of P, but the power set of an infinite set is uncountable. Hence, there are uncountably many square-free natural numbers, a contradiction. Hence there are only finitely many primes.

Explanation: The problem here lies in the bijection. Take any subset of primes which is infinitely large. Assuming there are infinitely primes to begin with, this is a valid step, since we may consider the subset of all primes, P \subset P. However, the product of all primes in an infinite subset of positive numbers is infinitely large, and hence cannot correspond to a square-free (finite) number. In other words, the set of finite subsets of an infinite set is countable.

This illuminates why the power set of an infinite set is interesting. Specifically, the only things which make it “big” are the infinite subsets. So these should be our primary concern.

Advertisements

3 thoughts on “False Proof – There are Finitely Many Primes

  1. “In other words, the set of finite subsets of an infinite set is countable.”

    I don’t agree with this, since the set of singleton subsets of the reals seems not countable to me (there’s an obvious one-to-one mapping between this set and the reals itself). I would agree with the statement “The set of finite subsets of a countable (even countably infinte) set is countable”.

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s