# How do I construct a proof showing what the cardinality of the set is:{ p/q such that p,q are elements of Natural Numbers}?

I know that the cardinality of the set of 1/k such that k is an element of Natural numbers is just Aleph-Null because I can prove that there is a bijective function from N-> 1/k for each k. But how do I do this specific problem? Some natural numbers when paired together will just get me the same natural number, ie, 3/1 can be written as 90/30, and p and q are different, but I will get 1 when p/q.

-
As an alternative to the already mentioned Bernstein-Schroder Theorem, you can construct a bijection between $\mathbb{N}$ and $\mathbb{Q}$ directly. I have described the construction here. –  jpvee May 20 at 7:22

## 2 Answers

I think I got it... If p and q are both in the Natural Numbers, then that means p/q will bring a rational number. So then I just need to find a bijection between the set of natural numbers and the set of rationals.

-

Shawn, there are many ways to think about this problem. The slickest proof I know uses the Bernstein-Schroder Theorem, which says that any two sets $A$ and $B$ having injective maps $f: A\to B$ and $g:B\to A$ are of the same cardinality. Here's a two-step proof showing that $|\mathbb N|=|\mathbb Q|$. Use the Bernstein-Schroder for both steps.

1. First, show that $|\mathbb N|=|\mathbb N\times\mathbb N|$. It should be easy, if you give it some thought, to find an injective map from $\mathbb N$ to $\mathbb N\times\mathbb N$. Finding an injective map from $\mathbb N\times\mathbb N$ to $\mathbb N$ is the hardest part of the problem, and this is where I'll use a slick trick. Consider the map $f(m,n)=2^m\cdot 3^n$. Why does it work?

2. Next, show that $|\mathbb Q|=|\mathbb N\times\mathbb N|$. I leave this step to you.

-