# Homework Help: Infinite set

1. Apr 10, 2010

### amiv4

1. The problem statement, all variables and given/known data

Prove that Square = {x ∈ N|∃y : N. x = y^2} is an infinite set.

2. Relevant equations

Definition 0.1. A set A is infinite if there is an injection f : A → A that is not also a surjection.

3. The attempt at a solution

I get how to show that there is an injection, but i dont get how to show that it is also not a surjection

2. Apr 10, 2010

### Office_Shredder

Staff Emeritus
What injection are you looking at?

3. Apr 10, 2010

### amiv4

to prove the injection i thought u could do something like this

f(x) = f(y) for arbitrary x and y in N, then x^2 = y^2 and so x = y. and that proves an injection

4. Apr 10, 2010

### Staff: Mentor

What is the above supposed to be saying?

5. Apr 10, 2010

### amiv4

would it be that like 0 maps to 0, 1 to 1, 2 to 4, 3 to 9... so that shows injection but then like 5 doesnt map back to anything

6. Apr 10, 2010

### Office_Shredder

Staff Emeritus
Except you're supposed to have a map that goes from the set of squares to the set of squares. But the function that you're looking at will still work

7. Apr 10, 2010

### amiv4

so would it be like 4 mapped to 16 is an injection but if you go the other way 16 doesnt map back to 4 and that is why it isnt a surjection

8. Apr 10, 2010

### Staff: Mentor

What set is this? {x ∈ N|∃y : N. x = y^2}

Some characters are rendering as empty boxes.

9. Apr 10, 2010

### amiv4

it is bascially the set of square numbers