One set of functions larger than another set of functions?

Question

This summer I've been slowly working through Halmos's Naive Set Theory. I'm not that far, but I know what lies ahead, which is proving that one infinite set is larger than another (the reals larger than the naturals). My question is, is it possible to show that one set of functions is more abundant than another? For example, is it possible to prove the rational functions are more numerous than the polynomial functions? My mathematical knowledge is small, so please keep the answer intuitive.

Answer 1

Let me assume that you are talking about polynomial and rational functions over $\Bbb R$.

Then the answer is no. The reason is that each rational function can be described as the ratio of a pair of polynomials. Therefore there is a surjection from the set $\Bbb R[x]\times\Bbb R[x]$ onto the rational functions.

We can show that for infinite sets, $A\times A$ and $A$ have the same cardinality. In the general case this requires something called "the axiom of choice", and I will assume it here without incident.

So we have that on one hand $\Bbb R[x]$ can be mapped onto the rational functions; on the other hand it can certainly be mapped into the rational functions. So they have the same cardinality.