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?

  • $\begingroup$ Please show us your attempts and why they did not work. $\endgroup$ – Simon Oct 21 '18 at 12:21
  • $\begingroup$ 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”. $\endgroup$ – user606633 Oct 21 '18 at 12:27
  • 1
    $\begingroup$ 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. $\endgroup$ – Simon Oct 21 '18 at 12:39

OP: Posts should look a bit like this





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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.