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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How do I go about showing that the cardinality of the set of natural numbers and the cardinality of the cartesian product of integers is the same?:

$$|\Bbb N|=|\Bbb Z \times \Bbb Z|$$

Directly $|\Bbb N| = \aleph_0$ and I can separate the right side like this: $|\Bbb Z||\Bbb Z|$, and because the cardinality of the set of integers is $\aleph_0$, $\aleph_0$ times $\aleph$ is still $\aleph_0$ and thus they are equal. However, I need to show an example how a bijection can be used here? How do I construct a map to let me see a bijection is being used/provide that it is surjective/injective?

share|cite|improve this question
I know that, but how do I do it? – Shawn S. Rana Apr 24 '14 at 22:45
Do you know any bijections between $\mathbb Z$ and $\mathbb N$? How about between $\mathbb N$ and $\mathbb N\times\mathbb N$? – Andrés E. Caicedo Apr 24 '14 at 22:48
I know that they both have bijections but I do not how to prove it/find it – Shawn S. Rana Apr 24 '14 at 22:52
I can set up a table such as the top row resembles integers: 0,1,-1,2,-2,3,-3,4,-4... and the bottom row resembles natural numbers: 1,2,3,4,5,6,7,8... There is a bijection – Shawn S. Rana Apr 24 '14 at 22:58
Don't get distracted by that. Your task is to find one. Never mind that there are many, we just need one. A common example, that has a nice intuitive picture attached to it, is Cantor's pairing, see here. One that is easier to verify uses that each positive integer is the product of an odd number and a power of two, $n=2^a(2b+1)$. This gives you a bijection $n\mapsto(a,b)$ between the positive integers and $\mathbb N\times \mathbb N$. – Andrés E. Caicedo Apr 24 '14 at 23:37

Much like eating a steak, this problem is easier to swallow if you cut it into smaller pieces and chew on them. Specifically here you can do it in three steps:

  1. There is a bijection $f$ between $\Bbb{N\times N}$ and $\Bbb N$.
  2. There is a bijection $g$ between $\Bbb Z$ and $\Bbb N$.
  3. Now define, $h(m,k)=f(g(m),g(k))$, and show it is a bijection.

If indeed you succeeded in the first two steps, then the third is easy.

  • $h$ is injective, since if $h(m,k)=h(m',k')$, then $f(g(m),g(k))=f(g(m'),g(k'))$. But $f$ is injective, so $g(m)=g(m')$ and $g(k)=g(k')$. But $g$ is also injective. So $m=m'$ and $k=k'$ as wanted.
  • $h$ is surjective, since if $n$ is any natural number, then since $f$ is surjective, there are some $s,t\in\Bbb N$ such that $f(s,t)=n$. But also $g$ is surjective, so there are some $m,k\in\Bbb Z$ such that $g(m)=s$ and $g(k)=t$. Therefore $h(m,k)=n$ as wanted.
share|cite|improve this answer

Your Answer


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.