About equations Let  be the signature with a constant $0$, a unary symbol $s$, and a binary symbol $+$. Our favorite example of $\sigma$-algebra is the natural numbers with the usual interpretations of the symbols. Let $\gamma$ be the set of two identities:
\begin{align}0 + y &= y \\
s(x) + y &= s(x + y)\end{align}
These are called the recursion equations for $+$. Prove that $\gamma \not\models x + y = y + x$. That is, the
commutative law of $+$ does not follow from the recursion equations for $+$.
I'm really stuck with this question.
 A: If you want to prove that $\gamma$ doesn't entail something, you need to build a model of $\gamma$ in which that thing is false. So in this case, we want to build a set $A$ with two operations $\oplus$ and $\mathfrak{s}$ and a special element $\Omega$ (written differently to emphasize that they're weird) such that


*

*$\Omega\oplus y=y$ for all $y$, and

*$\mathfrak{s}(x)\oplus y=\mathfrak{s}(x\oplus y)$ for all $x$ and $y$; but

*$x\oplus y$ is not necessarily the same as $y\oplus x$.
A useful counterexample here is the right projection function: $a\pi_rb=b$. It's not commutative in any structure with more than one element, since $a\pi_rb=b$ but $b\pi_ra=a$ (There's also left projection, of course.) Also, right projection trivially satisfies the first axiom of $\gamma$, regardless of what $\Omega$ is.
So this gives us a first guess as to what our model should be:


*

*Our underlying set should be something simple, say $\{0, 1\}$ (could be more complicated, but why do that if we don't have to?).

*Our $\oplus$ is just right projection.

*Our $\Omega$ is $0$ (doesn't matter which one we pick).
But we don't know what $\mathfrak{s}$ should be at the moment.
So let's think about it. We'll want $\mathfrak{s}(x)\oplus y=\mathfrak{s}(x\oplus y)$. But we've already decided what $\oplus$ is - it's just right projection! So we can simplify both sides of this equation. Do you see how to do this simplification? Do you see what this suggests $\mathfrak{s}$ should be defined as?
Once you fill in that gap, you'll get a structure which makes $\gamma$ true but in which $\oplus$ isn't commutative.
