Show that $ \forall x (f g x = x) \not \models \forall x (g f x = x) $

Question

a question of my homework asks to show that $\forall x (f g x = x) \not \models \forall x (g f x = x)$ bv, I think, giving an example of an $\mathcal{L}$-structure $\mathcal{M}$ such that the statement holds. I am stuck on thinking of a universe discourse $M$ where the variables in the statement will range over. I have looked at using the naturals and reals but cannot come up with functions $f, g$ such that the statement holds. Somebody's help would be greatly appreciated.

Answer 1

The idea is to play with the domain and the range, so that $f$ is not injective. For example, in the naturals:

$f(x)=$ $ \begin{cases} 0 & x = 0 \\ x-1 & x > 0 \end{cases} $

$g(x)=x+1$

Then surely $\forall x fgx=x$, but $\forall x gfx\not=x$ (Check the case when $x=0$).

Answer 2

In order to do this, note that for any $x \neq y$ it is the case that $g(x) \neq g(y)$, for otherwise you would have $f(g(x))=f(g(y))$

In other words, $g$ will have to be injective, and have an inverse.

This, however, means that $f$ cannot be injective, for if it did, then given that you want $f(g(x))=x$, it would have to be true that $f$ and $g$ would be each others inverse, and hence you would also have $g(f(x))=x$, which is what you are trying to avoid.

And finally, notice that that means that we must be dealing with an infinite sized domain, for if it was finite, then $f$ would have to be injective after all.

So: that's what you need: an infinite size domain, a $g$ that is injective, and an $f$ that is not injective. Note how @shiranai's Answer has exactly those properties.