Set Theory – Cardinality of the Set of All Functions from Blank to Blank

Question

I'm trying to determine if a bunch of examples constitute countable or uncountable sets. One of which is the set of all functions from the positive integers to the positive integers. Word on the street is that it's uncountable, but I can't really convince myself. My (probably wrong) logic is as follows. Each function is a subset of $A = \mathbb Z^+ \times \mathbb Z^+$. $A$ is countable, so each function is countable since each is a subset of $A$. The set in question is the union of all said functions, each of which is countable. Hence since a union of countable sets is countable, the set of all functions from $\mathbb Z^+$ to $\mathbb Z^+$ is countable. I'm bracing myself for when you guys to point out the fail! (And hopefully rewire my faulty logic.)

Answer 1

Yes, every function from $\mathbb Z^+$ to itself is indeed a countable set. However there are uncountably many of those.

Your mistake is that the set of functions (denoted by $\left(\mathbb Z^+\right)^{\mathbb Z^+}$) is not the union of all the functions. However you are correct that this union will be countable again.

Now, see that all the functions whose range is included in $\{1,2\}$ are also functions from the positive numbers to the positive numbers. It is a common exercise to show that this set corresponds to the power set of $\mathbb Z^+$. Cantor's theorem tells us that this power set is uncountable.

Also note that you are assuming the consequence. You assume that the set of functions is countable, so taking a union over this set will be a countable union, and therefore the set is countable. This is quite a circularity!