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
  • 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, 2014 at 7:22

2 Answers 2

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .