Inverses where $f(g(x))=x\neq g(f(x))$

Question

If $f: \mathbb{Z\to Z}$ and $G: \mathbb{Z\to Z}$, find $f$, and $g$ such that $f(g(x))=x\neq g(f(x))$.

I can find lots of $f$ and $g$ that aren't equal when composed with each other, but I have no idea how to proceed. A hint would be helpful.

Thanks in advance.

Answer 1

E.g. $\ g(n):=2n$, $f(2n):=n$ and you can do anything on the odds...

Note that we won't have $x\ne g(f(x))$ for all $x$ as, if $x=g(y)$ for some $y$, then $g(f(x))=g(f(g(y)))=g(\,y\,)=x$.

Answer 2

Hint: Applying $g$ to the equality gives $g(f(g(x)))=g(x)$ so if $y=g(x)$ then we must have $g(f(y))=y$. So the result could only fail for $y$ which are not $g(x)$ for any $x$. What is a simple way to construct a function which, say, misses out one such $y$?

Answer 3

Hint: If for all $x$ in the domain of $g$, $f(g(x))=x$, then $g$ is one-to-one, and $f$ is onto. Conversely, if $g\colon S\to T$ is one-to-one, then there is a function $f\colon T\to S$ with $f(g(x))=x$ for all $x\in S$. And also, if $f\colon T\to S$ is onto, then there is $g\colon S\to T$ with $f(g(x))=x$ for all $x\in S$. All of these statements are fairly easily proved except the last, which is equivalent to the Axiom of Choice. So, as @CutieKrait has said, you need a one-to-one function that’s not onto for the one of them, and its “semi-inverse” to be onto but not one-to-one.