# How do I go about showing the cardinality of two sets are the same?

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?

-
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 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 Caicedo Apr 24 '14 at 23:37

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.
• $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.