The integers with addition build a group $\langle \mathbb{Z},+,0\rangle$.

The functions $\operatorname{succ}:\mathbb{Z} \rightarrow \mathbb{Z}$, $\operatorname{pred}:\mathbb{Z} \rightarrow \mathbb{Z}$ with $\operatorname{succ}(x) = x +1$, $\operatorname{pred}(x) = x -1$ are the generators of the (free) group $\langle \{\operatorname{succ},\operatorname{pred}\}^+,\circ,\operatorname{id}\rangle$ with $\{\operatorname{succ},\operatorname{pred}\}^+$ the set of finite concatenations of $\operatorname{succ}$, $\operatorname{pred}$ and $\operatorname{succ}\circ \operatorname{pred} = \operatorname{pred}\circ \operatorname{succ} = \operatorname{id}$. This group is supposed to act on $\mathbb{Z}$.

There is a natural one-to-one mapping between $\langle \mathbb{Z},+,0\rangle$ and $\langle \{\operatorname{succ},\operatorname{pred}\}^+,\circ,\operatorname{id}\rangle$:

  • $+ \leftrightarrow \circ$
  • $0 \leftrightarrow \operatorname{id}$
  • $k > 0 \leftrightarrow \operatorname{succ}^k$
  • $k < 0 \leftrightarrow \operatorname{pred}^{-k}$

What's the official name of the group $\langle \{\operatorname{succ},\operatorname{pred}\}^+,\circ,\operatorname{id}\rangle$?

Compare with the monoid $\langle \mathbb{N},+,0\rangle$.

Consider the functions $\operatorname{succ}':\mathbb{N} \rightarrow \mathbb{N}$, $\operatorname{pred}':\mathbb{N} \rightarrow \mathbb{N}$ with $\operatorname{succ}'(x) = x +1$, $\operatorname{pred}'(0) = 0$ and $\operatorname{pred}'(x) = x -1$ if $x > 0$. The functions $\operatorname{succ}'$ and $\operatorname{pred}'$ are freely composable and $\operatorname{pred}'\circ \operatorname{succ}' = \operatorname{id}$.

But $\operatorname{succ}'\circ \operatorname{pred}' \neq \operatorname{id}$ because $\operatorname{succ}'\circ \operatorname{pred}'(0) = 1$. On the other side $\operatorname{succ}'\circ \operatorname{pred}'$ is somehow "almost" the identity because $\operatorname{succ}'\circ \operatorname{pred}'(n) = n$ for every other $n \neq 0$.

This means: $\operatorname{pred}'$ has a ("strong") right-inverse and $\operatorname{succ}'$ has a ("strong") left-inverse. In turn $\operatorname{pred}'$ has only a "weak" left-inverse and $\operatorname{succ}'$ has only a "weak" right-inverse.

Is this distinction between "strong" and "weak" inverses of any (and in any) use?

What's the name of the kind of algebraic structure $\langle \{\operatorname{succ}',\operatorname{pred}'\}^+,\circ,\operatorname{id}\rangle$ – which is supposed to act on $\mathbb{N}$ – is an example of?

  • 2
    $\begingroup$ I may be missing something but isn't that just $\mathbb Z$ with $1$ and $-1$ as generators? (In response to your first question.) The other thing is known to me as a standard example in ring theory or linear algebra of an operator admitting a left inverse but no right inverse. $\endgroup$ – Myself Dec 8 '14 at 12:19
  • $\begingroup$ I'm pretty sure its official name is simply $\mathbb{Z}$. $\endgroup$ – Najib Idrissi Dec 8 '14 at 12:32
  • $\begingroup$ Isn't it the group of the left(or right because is commutative) traslations of $+$ with the composition operation? I guess that we could see it as the ciclyc subgroup $\langle S \rangle$ of the group of bejections from $\Bbb Z$ to itself equipped with the composition. Where $S$ is the successor function. $\endgroup$ – MphLee Dec 8 '14 at 12:33
  • 1
    $\begingroup$ As an abstract group it surely is (isomorphic) to $\mathbb{Z}$. $\endgroup$ – Hans-Peter Stricker Dec 8 '14 at 13:21
  • $\begingroup$ Sure @HansStricker because $k \mapsto f_k$ where $f_k(x):=k+x$ is a bijection. And is an isomorphism betwen addition and composition (as you noted). $\endgroup$ – MphLee Dec 8 '14 at 17:39

If I understand the definition correctly, the structure $\langle \{\operatorname{succ}',\operatorname{pred}'\}^+,\circ,\operatorname{id}\rangle$ is an inverse monoid, i.e. an inverse semigroup with identity, since

  • $\operatorname{succ}' = \operatorname{succ}' \circ\operatorname{pred}'\circ \operatorname{succ}'$

  • $\operatorname{pred}' = \operatorname{pred}' \circ\operatorname{succ}'\circ \operatorname{pred}'$

| cite | improve this answer | |

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.