2
$\begingroup$

Let $J_n=\{1,\dots,n\}$. How do I show that the set of all functions $J_n\to \mathbb N$ is countable? Any function is given by specifying the images of $1,\dots,n$. There are $|\mathbb N|$ options for the image of each $i=1, \dots, n$. So intuitively, the set of such functions is the union of $n$ copies of $\mathbb N$, hence countable. But how to formalize it?

$\endgroup$
  • $\begingroup$ It might help to consider a simple case first: what if $n=2$? Do you see a way to "code" a (ordered) pair of natural numbers as a single natural number? $\endgroup$ – Noah Schweber Aug 26 '18 at 19:06
1
$\begingroup$

It's not the union, it's the Cartesian product.

$\endgroup$
  • $\begingroup$ How can one see this? I only can see that a particular function is (by definition) a subset of $J_n\times\mathbb N$. $\endgroup$ – user531587 Aug 26 '18 at 19:10
  • $\begingroup$ @user531587 Yes, and that's a Cartesian product (really, you should think of it as $\mathbb{N}\times...\times\mathbb{N}$ ($n$ times)). $\endgroup$ – Noah Schweber Aug 26 '18 at 19:13
  • $\begingroup$ @NoahSchweber But the Cartesian product $J_n\times \mathbb N$ is just the definition of a single function. I need to account for all functions somehow, but I don't know how to do that. (And I'm not sure where did you get $\mathbb N^n$ from.) $\endgroup$ – user531587 Aug 26 '18 at 19:17
  • 2
    $\begingroup$ @user531587 Each function $f:J_n\to \mathbb N$ assigns to element of $\{1,\ldots,n\}$ a natural number. So such a function could be given by $f(1)=42,$ $f(2)=120, \ldots, f(n) = 99,$ or something like this. We can correspond this to the ordered pair $(42,120,\ldots,99) \in \mathbb N^n,$ the $n$-fold cartesian product of $\mathbb N.$ $\endgroup$ – spaceisdarkgreen Aug 26 '18 at 19:19
  • $\begingroup$ @spaceisdarkgreen Oh, I see, so there is a bijection between the set of functions I described and the set $\mathbb N^n$. And since finite Cartesian products of countable sets are countable, the result follows. $\endgroup$ – user531587 Aug 26 '18 at 19:21
1
$\begingroup$

Let $\mathcal{J_k} = \{f : J_k \to \mathbb{N} \}$ be the set of functions from $J_k$ to $\mathbb{N}$. Now, the mapping

$$ \begin{align} & \mathcal{J_k} \ \longrightarrow \ \mathbb{N}^k \\ & \quad f \mapsto (f(1), \dots, f(k) ) \end{align} $$

is bijective, so it suffices to show that $\mathbb{N}^k$ is countable. Take distinct primes $p_1, \dots, p_k$ and consider the function

$$ \Gamma: \mathbb{N^k} \to \mathbb{N} \\ (n_1, \dots, n_k) \mapsto p_1^{n_1}\cdots p_k^{n_k} $$

By the fundamental theorem of arithmetic, $\Gamma$ is injective, and so $|\mathbb{N}^k| \leq |\mathbb{N}| = \aleph_0$ as desired.

If you want to have an explicit injection, you can compose both mappings, i.e. you can take the function $f \mapsto p_1^{f(1)}\cdots p_k^{f(k)}$.

$\endgroup$
0
$\begingroup$

Each function is given by a $n$-tuple $(f_1, \dotsc, f_n) \in \mathbb{N}^n$ of natural numbers, where $f_i = f(i)$.

You can use the Cantor pairing function, $$ \pi(x, y) := y + \sum_{i=0}^{x+y} i = y+\frac{1}{2} (x + y) (x + y + 1) $$ which is a bijection between $\mathbb{N}$ and $\mathbb{N}^2$, iteratively to encode an $n$-tuple to a natural number.

E.g.

  • $\langle f_1, f_2 \rangle = \pi(f_1, f_2)$
  • $\langle f_1, f_2, f_3 \rangle = \langle f_1, \langle f_2, f_3 \rangle \rangle$
  • $\langle f_1, f_2, f_3, f_4 \rangle = \langle f_1, \langle f_2, f_3, f_4 \rangle \rangle = \langle f_1, \langle f_2, \langle f_3, f_4 \rangle \rangle\rangle$

and so on. This is called a Cantor tuple function.

$\endgroup$

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