Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.)

share|improve this question
    
the cardinality of the set of all subsets of a countable set is uncountable –  i. m. soloveichik Sep 2 '12 at 21:49
add comment

4 Answers

up vote 7 down vote accepted

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!

share|improve this answer
    
Living life on the edge is tough when one is as circular as I am...thanks so much sir! –  AsinglePANCAKE Sep 2 '12 at 21:55
add comment

It is true that the union of countably many countable sets is countable (if we assume the Axiom of Choice).

But the collection of functions from $\mathbb{N}$ to $\mathbb{N}$ is a set of subsets of $\mathbb{N}\times\mathbb{N}$. It is not clear what kind of union of countable sets you are thinking of.

One way to see that there are uncountably many functions from $\mathbb{N}$ to $\mathbb{N}$ is to note that there are already uncountably many functions from $\mathbb{N}$ to $\{0,1,2,\dots,9\}$. This is because the decimal expansion of a number between $0$ and $1$ gives rise to such a function. And you have seen a proof that there are uncountably many reals between $0$ and $1$.

One can also prove that there are uncountably many functions from $\mathbb{N}$ to $\mathbb{N}$ by a direct diagonalization.

share|improve this answer
1  
Actually the axiom of choice is moot here. We are taking unions over a collection of subsets of a countable set. This is besides the point that the union is not over a countable index set. –  Asaf Karagila Sep 2 '12 at 21:39
add comment

Let $\mathcal{A}$ denote the set of all functions from $\mathbb{N} \rightarrow \mathbb{N}$. The claim is that $\mathcal{A}$ is uncountable. To prove this suppose not, i.e. that $\mathcal{A}$ is countable. Let $(f_n)_{n \in \mathbb{N}}$ be a countable enumeration of all functions in $\mathcal{A}$. Define $f : \mathbb{N} \rightarrow \mathbb{N}$ as follows:

$h(n) = f_n(n) + 1$

Clearly $h$ is a function from $\mathbb{N} \rightarrow \mathbb{N}$. Hence $h \in \mathcal{A}$. But $h \neq f_n$ for any $n$ since $h(n) = f_n(n) + 1 \neq f_n(n)$. So $\mathcal{A}$ could not have been countable.


Indeed, each function $f : \mathbb{N} \rightarrow \mathbb{N}$ is countable. But why are you taking countable union of countable sets? What you want to know is the number of functions $f : \mathbb{N} \rightarrow \mathbb{N}$. When you say, "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," it appears that you are already assuming you have a countable number of functions. What is the countable union suppose to signify.

share|improve this answer
add comment

I'm sure, this is really a FAQ. The asnwer is the diagonal argument. If you have an enumeration of maps $\mathbb Z_+\to\mathbb Z_+$, that is for each $n \in \mathbb Z_+$ a map $f_n\colon\mathbb Z_+\to\mathbb Z_+$, then you can define the map $g\colon\mathbb Z_+\to\mathbb Z_+$ by $g(n) := f_n(n)+1$. Clearly, $g$ is not among the $f_n$ as it differs from $f_n$ for at least one input (namely $n$). Hence no countable list of such functions is complete.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.