# Do endomaps of sets have interesting properties?

I've been thinking about maps between sets. Injections, surjections and the rest. Often when thinking about some kind of map, it is interesting to say "what about the maps from a set to itself?" Call these maps endomaps. Permutations of elements of the set are a special case of endomaps: they are bijective endomaps. Permutations have lots of interesting properties: they form groups and so on.

But what about general endomaps that are not necessarily bijective? Do they have any interesting properties that people study? They don't necessarily have inverses, which rules them out as forming groups, but composition of endomaps is associative, so they aren't totally devoid of interesting properties.

It is also the case that for every endomap, there exists some subset of its domain (not necessarily unique) such that it is bijective on that subset. So these maps are permutations if restricted to a particular subset. Is this enough to make endomaps interesting in their own right, or are they only studied as a part of the study of maps between sets in general?

[It might be obvious that this question was motivated by thinking about category theory, but there's nothing particularly categorical about the question as such...]

• The first few remarks you made say that the endomaps form a monoid, en.wikipedia.org/wiki/Monoid. (This is true in any category.) – Akhil Mathew Aug 27 '10 at 13:35
• One often useful property is that an endomap of a finite set is injective iff it is surjective. – Charles Staats Aug 27 '10 at 13:49
• what is the difference between an endomap and an endomorphism? – Tom Stephens Aug 27 '10 at 16:00
• @Tom Stephens: they are spelled differently ;) – Seamus Aug 27 '10 at 17:02

One of the important properties of endomaps of an infinite set $X$ is that the expressive power of the logic that allows you to quantify over all endomaps of $X$ is the same as the expressive power of the full second order logic on $X.$ Roughly, this means that any relation on $X$ (a subset of $X^n$) can be modelled by means of endomaps. For instance, any equivalence relation $E$ on $X$ is modelled as follows: for every such equivalnce relation $E$ there is an endomap $f : X \to X$ such that $$E(x_1,x_2) \iff f(x_1)=f(x_2) \qquad (x_1,x_2 \in X).$$ So endomaps of $X$ can tell you everything about $X,$ if you "ask" them properly.

For other classes of structures, endomorphisms also carry lots and lots of information. For instance, the semigroup $\mathrm{End}(V)$ of all endomorphisms of a given vector space $V$ carries most essential information about $V,$ etc.

The generalization of cycle decomposition to endomaps is quite interesting; rather than just cycles, endomaps break up into cycles in which each vertex is the root of a tree. Counting endomaps (of which there are $n^n$) is therefore relevant to counting trees, and this is the basis of a beautiful proof due to Joyal (which I believe can be found in Bergeron, Labelle, and Leroux's Combinatorial Species and Tree-like Structures) of Cayley's formula.

A set equipped with an endomap is just about the simplest kind of dynamical system. The category of sets equipped with endomaps is sometimes called the category of (discrete) dynamical systems and can be a useful example in category theory, e.g. it pops up in Lawvere and Schanuel's Conceptual Mathematics.

Given a set $X$, the collection of all maps $s\colon X\to X$ forms a semigroup under the operation of composition, called the "full transformation semigroup" of $X$, often denoted $\mathcal{T}_X$. Full transformation semigroups play the same role in semigroup theory as symmetric groups do in group theory (the symmetric group is the group you get by considering the bijections from a set to itself, under composition). For example, the analogue of Cayley's Theorem ("every group is a subgroup of a symmetric group") holds for semigroups ("every semigroup is a subsemigroup of a full transformation semigroup").

You claim that "for every endomap, there exists some subset of its domain such that it is bijective on that subset". That is only true if you restrict yourself to finite sets or you allow restriction to the empty set: consider the map $f\colon\mathbb{N}\to\mathbb{N}$ given by $f(n)=n+1$. If $X$ is a nonempty subset of $\mathbb{N}$, then the minimum of $X$ is not in $f(X)$, so $f$ is not bijective on $X$.

• Good point, I was restricting myself to finite groups. – Seamus Aug 27 '10 at 17:01