2
$\begingroup$

Find a left-inverse for the function $f:\Bbb Z \to \Bbb Z$ given by $f(n)=2n+1$.

Verify that your answer is correct. Does f have a right-inverse? Explain.


Hi all, I need to asses whether this function is left and/or right invertible, and then prove it using proper proof language. I'm trying to follow the way my professor taught me, but I'm not really sure I understand what I'm doing.

This is what I have:

Theorem. $f$ is left-invertible.

Proof.

$f$ is left-invertible if there is some function $g:\Bbb Z \to \Bbb Z$ such that $g \circ f = id_{\Bbb Z}$. Consider $g(n)=\frac{n-1}{2}$. Then, $g \circ f(n) =\frac{2n+1-1}{2}=n=id_{\Bbb Z}$. Therefore, $f$ is left-invertible.

Does that make any sense so far? Honestly, it doesn't make any sense to me. The other problem is that using a similar strategy, I find that $f$ is also right-invertible. However, I know that not to be true, because $f(1)=3$ and $f(2)=5$, and thus there is no $n\in\Bbb Z$ such that $f(n)=4$ (aka, the function only spits out odd numbers if we restrict the domain to integer inputs). Therefore, it is not survective. If anyone can help me understand, perhaps from the beginning, how to properly do this problem and write it out, that would be amazing.

Cheers

$\endgroup$
  • 1
    $\begingroup$ Your construction of a left inverse is somewhat flawed, in that the function you write down is not a function from $\mathbb Z \to \mathbb Z$. It only takes integer values if $n$ is odd, which is good enough since the image of $f$ consists of odd integers. $\endgroup$ – lulu May 10 '18 at 23:51
  • 1
    $\begingroup$ It's easy to get confused, no worries there. The problem with your $h$, of course, is that it isn't integer valued when $n$ is even. $\endgroup$ – lulu May 10 '18 at 23:52
  • 1
    $\begingroup$ You already have! Suppose $h$ existed. Then $f(h(4))=4$, by definition of right inverse. But $f(n)$ is odd for all $n$, a contradiction! $\endgroup$ – lulu May 10 '18 at 23:57
  • 1
    $\begingroup$ Worth noting: your function $f$ makes sense on all of $\mathbb Q$ and in that context your function $h$ is a perfectly good inverse. $\endgroup$ – lulu May 10 '18 at 23:58
  • 1
    $\begingroup$ I'm not happy with the logic, quite. Saying $f(1)=3, f(3)=5$ doesn't prove that $f(n)=4$ is impossible. I'd get that result by arguing that for all $n$, $f(n)$ is odd. $\endgroup$ – lulu May 11 '18 at 0:04
3
$\begingroup$

Your formula for $g(n)$ doesn't ensure $g(n)\in\mathbf Z$. To make it work, you should take $$g(n)=\biggl\lfloor\frac{n-1}2\biggr\rfloor.$$

If $f$ had a right inverse, it would be surjective, which isn't the case.

Note that a function with a left inverse is injective, which is indeed the case.

$\endgroup$
  • $\begingroup$ Hi, I am not familiar with that notation (the bracket-looking things surrounding the expression). What does that mean? $\endgroup$ – akot717 May 10 '18 at 23:52
  • $\begingroup$ By the way, I could have proved this by proving that it was injective and not surjective (since I know how to do that). But I'm required to prove this using the composition concepts specifically. $\endgroup$ – akot717 May 10 '18 at 23:54
  • 1
    $\begingroup$ @akot717 The brackets indicate the floor function - it means to round the input down to the next integer. (e.g. $\lfloor 2+\frac{1}2\rfloor = 2$ and $\lfloor \frac{-1}2\rfloor= -1$ and $\lfloor 5\rfloor = 5$) $\endgroup$ – Milo Brandt May 10 '18 at 23:58
  • $\begingroup$ I see. But why do I need to write $g(n)$ as a floor function if I have already indicated that my function has domain $\Bbb Z$? $\endgroup$ – akot717 May 11 '18 at 0:03
  • 1
    $\begingroup$ That's because $\frac{n-1}2$ is not an integer if $n$ is even $\endgroup$ – Bernard May 11 '18 at 0:07

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.