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.

Given a set D = $\{(a,b)∣a,b ∈ \mathbb{N}\}$ where L is the set of all points in the first quadrant whose coordinates are natural numbers.

Which has more elements, D or $\mathbb{N}$?

I know it has something to do with finding a surjection or injection, which can help decide which has more elements, but it's also possibly a bijection? Not sure which has more or if they have the same cardinality/size.

share|improve this question
1  
What is $L$? It seems you mean $D$ –  Thomas Andrews Dec 1 '13 at 15:24
    
Depends on what you mean by "formula." –  Thomas Andrews Dec 1 '13 at 15:26
    
a formula that you can solve. For example, not related to this problem, a formula such as f(x)=2x where the domain is N and the codomain is 2N. something like that where there's an operation applied to the function –  gticecream8 Dec 1 '13 at 17:56

2 Answers 2

up vote 1 down vote accepted

Using the cantor Scherer theorem: if we can find an injection $f$ from $\mathbb N$ to $D$ and a surjection $g$ from $\mathbb N$ to $D$ then we are done.

for the surjection let $f((a,b))= a$.

For the injection let $g((a,b))=a+b+a$.

see this video to see why the injection is indeed an injection.

Infinity is bigger than you think

and see they are the same thing.

share|improve this answer

How about $$s(n)=(i+1,j+1)\text{ if }n=2^i3^ju\text{ with }\gcd(6,u)=1$$ or $$s(n)=\left(\left\lfloor \frac{n-\lfloor\sqrt n\rfloor^2}2\right\rfloor,\lfloor\sqrt n\rfloor-\left\lfloor \frac{n-\lfloor\sqrt n\rfloor^2}2\right\rfloor\right) $$ (Adjustments according to your local deifnition of $\mathbb N$ may be necessary).

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.