# Evan's theorem of embeddings into 2-generator semigroup.

I recently found this theorem when I am studying Semigroup presentations.

Theorem: If S is a semigroup generated by denummerably many elements, then S can be embedded into a semigroup generated by two elements.

As a hint for constructing the proof a theorem was given:

Theorem: Let $\alpha_{1},\alpha_{2}...:\mathbb N_{+}\to \mathbb N_{+}$ be any transformations. There exist two transformation $\beta_{1},\beta_{2}:\mathbb N_{+}\to \mathbb N_{+}$ such that each $\alpha_{i}$ is a composition of these two transformations.

By using a suitable isomorphisms Evan's theorem follows from the above result. But, to my suprise constructing the proof is given me headache. Please can someone assist?

-
Just to note that the theorem you mention is an old result of Sierpi\'nski from 1935: –  James Mitchell Nov 30 '13 at 10:19

I wanted to add this as a comment, but it turned out to be too long. The theorem you mention about countable sets of transformations is an old result of Sierpi\'nski from 1935:

W. Sierpi$\'n$ski, Sur les suites infinies de fonctions d\'efinies dans les ensembles quelconques, Fund. Math. 24 (1935), 209--212.

The article is available here and a short proof of Banach's can be found in Lemma 2.2 of this paper. You can read about similar results where the type of transformation is restricted to those which are continuous, injective, surjective and so on here.

-

The point is that every countable semigroup is isomorphic to a semigroup consisting of maps from a countable set to itself with composition. This can be seen by letting the semigroup act on itself by left multiplication. (We may assume that the semigroup is infinite by taking the product with some infinite semigroup.) Any countable set is as good as any other countable set, hence you can assume your semigroup consists of maps from the positive integers to the positive integers.
Now apply the theorem that you quote.

-
I think, for a general semigroup $S$, we need to let the semigroup act on $S^1$, where $S^1$=$S\cup \{1\}$ with the obvious multiplication. Otherwise, the resulting homomorphism may not be injective. For example let $S$ be a set of cardinality greater than $1$ with multiplication being a constant function. It's the zero semigroup on $S$. The action of $S$ on itself by left multiplication is not faithful. –  user23211 Mar 4 '12 at 12:28
Yes, I agree. We have to add 1 first. –  Stefan Geschke Jun 24 '12 at 13:20

I also suffered with the "straight forward reduction" statement of Subbiah. So I decided to make a short note on it. I want to post the full paper as an image, however, I found some difficulty and I could not post it.. I think, we can do the proof this way: Suppose S is a semigroup generated by a denumerable subset. first, a faithful representation from S to the full transformation semigroup on S^1 exists; second, it is clear that S^1 is also denumerable. thus, there exists a bijection from S^1 to the set of all natural numbers; third, we form a function from the full transformation semigroup on S^1 to the full transformation semigroup on the set of all natural numbers. this function makes use of the bijection above. now, this function becomes an isomorphism; fourth, we make a composition of the faithful representation above with the isomorphism. this makes the embedding from S to the full transformation semigroup on the set of all natural numbers. I think, we now have what we wanted. Please check...thanks - Joris

-