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.

This is more of a "How to write" question than a "help me solve" one, sorry if these are unaccepted/closed, let me know and I won't open anymore like this.

I need to prove that $A:=\{x\in \mathbb{N}|$ exists $n\in\mathbb{N}$ such that $x=n^2 \}$ is countable. This obviously requires me to prove that exists a bijective function from N to it. Which sounds very simple, but I don't really know how to write it.

Edit: Well, this is what I had written before asking:
Proof. We'll notice that this set is equal to $\left\{ n^{2}|n\in\mathbb{N}\right\}$ , since for each n we can find $n^{2}$ and say it's equal to $x$ .

In order to prove that a set is countable we need to find a bijective function from $\mathbb{N}$ to it. We'll look at:

$$f:\mathbb{N}\to \mathbb{N}^{2},f\left(n\right)=n^{2}$$

Since multiplication is well defined we can say this function is injective. Now how do I explain surjective?

share|improve this question
    
How about sending n to x? –  Espen Nielsen Nov 4 '12 at 13:03

2 Answers 2

up vote 3 down vote accepted

Note that in fact your set is

$$A:=\{n^2\;\;;\;\;n\in\Bbb N\}$$

so what about

$$f:\Bbb N\to A\;\;,\;\;f(n):=n^2\,\,?$$

Please pay attention to the fact that if instead $\,\Bbb N\,$ we'd have $\,\Bbb Z\,$ , the above function would not be $\,1-1\,$ ...

share|improve this answer
    
how do I explain this function is infact bijective? –  Nescio Nov 4 '12 at 13:17
    
Did you get the hint why it is injective? Well, there you go! As for surjective: it follows in a straightforward way from the re-writing your set A as I did in my answer! If you're still having doubts, tell me where exactly, after you've done some self work. –  DonAntonio Nov 4 '12 at 13:21
    
If you'll look at the edit you'll see that's exactly where I was when asking in the first place. Well, it's my fault for trying to post questions while on a bus. I got my answer I think , ty... –  Nescio Nov 4 '12 at 13:28

Given $$A = \{ x \in \mathbb N \,|\, \exists n \in \mathbb N,\,\, x = n^2 \}$$ then the function $n \mapsto n^2$ is a bijection between $\mathbb N$ and $A$.

  • Injective: natural numbers are positive.
  • Surjective: given $x \in A$, there exists by definition of A some $n$ such that $n^2 = x$.
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.