Problem: Show there are finitely many primes.
“Solution”: Suppose to the contrary there are infinitely many primes. Let be the set of primes, and
the set of square-free natural numbers (numbers whose prime factorization has no repeated factors). To each square-free number
there corresponds a subset of primes, specifically the primes which make up
‘s prime factorization. Similarly, any subset
of primes corresponds to a number in
, since we can simply multiply all numbers in
together to get a square-free number.
Thus we have shown a bijection between and the power set of
, 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, . 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.
Nice!
LikeLike
“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”.
LikeLike
Should read: the set of finite subsets of a countably infinite set is countable.
LikeLike