# Math Help - Countability of N x N (Naturals x Naturals)

1. ## Countability of N x N (Naturals x Naturals)

To Prove: N (set of Naturals numbers) * N (set of Natural numbers) is countable.

The way I need to go about writing this proof is to find a surjection from N --> NxN and then apply the fact that: a nonempty set A is countable if and only if there exists a surjection N --> A

Any help would be appreciated!

2. Originally Posted by jstarks44444
To Prove: N (set of Naturals numbers) * N (set of Natural numbers) is countable.

The way I need to go about writing this proof is to find a surjection from N --> NxN and then apply the fact that: a nonempty set A is countable if and only if there exists a surjection N --> A

Any help would be appreciated!
Oh god. Do you actually have to exhibit the surjection? You could note that the map $f:\mathbb{N}\times\mathbb{N}\to\mathbb{N}n,m)\mapsto 2^n3^m" alt="f:\mathbb{N}\times\mathbb{N}\to\mathbb{N}n,m)\mapsto 2^n3^m" /> is an injection and conclude that there must be a surjection the other way.

Or, I think $f(n,m)\mapsto 2^{m-1}(2n-1)$ is a bijection, I think.