Proof: For $n \in \mathbb{Z_+}$, the set of all functions $f: \{1,...,n\} \to \mathbb{Z_+}$ is countable

130 Views Asked by At

(citation: Munkres Topology 7.5 b)

Backgound (from Munkres Topology Chapter 7):

Theorem 7.1: $B$ is a nonempty countable set $\Leftarrow\Rightarrow$ there is an injective function $g: B \to \mathbb{Z_+}$

Theorem 7.6: a finite product of countable sets is countable

PROOF

Let $B_n = \{f | f: \{1,...n\} \to \mathbb{Z_+}\}$ and let $\mathbb{Z_+^n} = \{(z_1, z_2,...,z_n)|z_1, z_2,...,z_n\in \mathbb{Z_+}\}$.

Define the function $g_n: B_n \to \mathbb{Z_+^n}$ such that $g_n(f) = (f(1), f(2),...,f(n))$, where $f\in B_n$.

Let $z = z' \in \mathbb{Z_+^n}$, such that $z = g_n(f), z' = g_n(f')$ for $f,f'\in B_n$.

Then $z = (f(1),f(2),...,f(n)) = (f'(1),f'(2),...,f'(n)) = z'$, which holds iff $f(1)=f'(1), f(2)=f'(2),...,f(n)=f'(n)$.

This implies that $f = f'$, hence $g_n$ is an injection from $B_n$ into $\mathbb{Z_+^n}$.

$\mathbb{Z_+^n}$ is countable by Theorem 7.6, as $\mathbb{Z_+}$ is countable. Thus, by Theorem 7.1, $\exists$ an injective function $h: \mathbb{Z_+^n}\to \mathbb{Z_+}$. Then, $h \circ g_n: B_n\to \mathbb{Z_+}$ is injective.

Therefore, by Theorem 7.1, $B_n$ is countable.

I believe this is sufficient, but please let me know, if it may be corrected or improved.

1

There are 1 best solutions below

3
On BEST ANSWER

In the definition of $g_n$, you write $\color{red}{f(3)}$ instead of $f(n)$. The rest is correct.

Just a matter of taste: it is not necessary to say "where $f \in B_n$", since it is obvious; also it is not necessary to give two different names $(z=z')$ to the same thing, since it is a little misleading.