Thread: 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 $\displaystyle 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 $\displaystyle f(n,m)\mapsto 2^{m-1}(2n-1)$ is a bijection, I think.