Take the 2-minute tour ×
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.

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.

share|improve this question
1  
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 2

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

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.