0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – jpvee May 20 '14 at 7:22
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.