# Help with surjection and bijection exercise

Let $$O$$ be the set of positive odd integers:

A) Give an example of a function $$g: O \to O$$ that is surjective but not injective.

B) Prove that $$\;|Z| = |O|\;$$ by describing a witness for the bijection.

I’ve been attempting this exercise for a while now but have no clue on how to do it. Could anyone help me please?

• Please show us your attempts and why they did not work. – Simon Oct 21 '18 at 12:21
• I have tried multiple things in part A, but none of them worked. I guess it implies using the modulo operation, but I’m not sure in which way. As for part b, I haven’t tried anything as I’m not sure what they mean by “a witness”. – user606633 Oct 21 '18 at 12:27
• Don't be ashamed of your wrong attempts. Show us one of the functions you came up with for part A and we can discuss why it doesn't work. Success is built on millions of failures ! As for part B, by "a witness" they mean a particular bijection between Z and O. The idea is that the statement "|Z|=|O|" means that there exists such a bijection. Any particular such bijection is "a witness" to that statement being true. – Simon Oct 21 '18 at 12:39

## 1 Answer

OP: Posts should look a bit like this

details...

# Attempt

details...

Now, with problems such as these it is easier to try to do things a bit piecewise. That is, we only need to break injectivity once for it to be false. It helps to write the first few members out $$O=\{1,3,5,7,\dots\}$$Define the map $$\phi:O \to O$$ as follows:

$$\phi(1)=1 \text{ and } \phi(x)=x-2$$

Then $$\phi(1)=\phi(3)$$ and for any odd integer $$y>1$$ we have $$\phi(y+2)=y$$.

For the second part, consider the bijections from $$\mathbb{N} \to O$$ and from $$\mathbb{N} \to \mathbb{Z}$$ and you should be able to figure out how to write the bijection. Since you have two bijections you can they have well-defined inverses which you can compose to get the desired bijection.