Monoids with only one-sided inverses

abstract-algebra

I'm solving an exercise in Artin that asks for a proof that that an element $a$ can have either a left or right inverse, but not be invertible. The problem comes before he has defined the notion of a group, so it seems that I only need a well-defined law of composition and an identity element, so I'm trying to confine myself to the simple case of a monoid.

For one case, I took his example in exercise 1.3 of the shift map $s(n) = n + 1$ where $n \in \mathbb{N}$. This map can be shown to have a left inverse, but no right inverse. It is not clear, however, what this $s$ is an element of. Sets of functions from $\mathbb{N} \to \mathbb{N}$? Without being able to describe the monoid, it doesn't seem obvious to me that I can call $s$ an "element."

I tried a similar mapping $t(n) = n – 1$ to try to find one with a right inverse, but no left inverse. It took me a while to realize that the map isn't even defined when $n = 0$, so I have to restrict the domain to exclude $1$, but that seems to have the effect of preventing me from proving the absence of a left inverse.

Some thoughts on this would be greatly appreciated.

SLIGHT EDIT:

How is this example for the shift map?

We define the monoid to be the set of functions from $\mathbb{N} \to \mathbb{N}$. The law of composition is composition of functions. If we compose two functions that map from $\mathbb{N}$ to $\mathbb{N}$, the result is another function that maps from $\mathbb{N}$ to $\mathbb{N}$, so the composition is closed. The identity element is the identity map $i: \mathbb{N} \to \mathbb{N}, n \mapsto n$. The shift map is one example of a map that has a left inverse, but no right inverse.

Best Answer

I don't remember how Artin defines $\Bbb{N}$, but I'm going to define $\Bbb{N}$ to be the set of non-negative integers. Some people prefer to define $\Bbb{N}$ to be the set of positive integers.

Let $M$ be the set of functions $\Bbb{N}\to\Bbb{N}$. $M$ is a monoid with the operation of function composition. Let $I:\Bbb{N}\to\Bbb{N}$ denote the identity of $M$. Hence $I:\Bbb{N}\to\Bbb{N}$ is the function that sends $n\mapsto n$ for each $n\in\Bbb{N}$.

Let $f:\Bbb{N}\to\Bbb{N}$ be the function that sends $n\mapsto n+1$ for each $n\in\Bbb{N}$, and let $g:\Bbb{N}\to\Bbb{N}$ be the function that sends $0\mapsto0$ and $n\mapsto n-1$ for all $n\ge1$. Then $g\circ f=I$, so $f$ has a left-inverse and $g$ has a right inverse. We can also show that (1) $f$ has no right inverse, and (2) $g$ has no left inverse. Since each of these is a good exercise, I've hidden the proofs below.

Claim 1: $f$ has no right inverse.

Suppose $h:\Bbb{N}\to\Bbb{N}$ such that $f\circ h=I$. It follows that $$0=I(0)=f(h(0))=h(0)+1,$$ which implies that $h(0)=-1$, a contradiction.

Claim 2: $g$ has no left inverse.

Suppose $k:\Bbb{N}\to\Bbb{N}$ such that $k\circ g=I$. It follows that $$0=I(0)=k(g(0))=k(0)=k(g(1))=I(1)=1.$$ So $0=1$, a classic contradiction.

Here's an exercise that I hope will be helpful: let $f\in M$, the monoid of functions $\Bbb{N}\to\Bbb{N}$. Show that (A) $f$ has a left-inverse iff $f$ is injective, and (B) $f$ has a right-inverse iff $f$ is surjective. If you have any questions about this exercise, or any other questions, please let me know by posting a comment!

Related Question