An involution is an endomorphism whose square is the identity morphism. Such an endomorphism must be an automorphism; indeed, it is its own inverse.
Where this makes sense, an anti-involution is an antihomomorphism instead of a homomorphism (so an antiendomorphism and necessarily an antiautomorphism).
Two involutions commute if and only if their composition is also an involution, as displayed by the following algebra:
Fixed point free involutions
In combinatorics, an important class of involutions are the fixed point free ones: an arbitrary involution on a finite set of cardinality may be specified by the choice of elements which are fixed together with a fixed point free involution on the remaining . The number of fixed point free involutions on a set of labelled elements is counted by the double factorial , while arbitrary involutions on a set of labelled elements are counted by OEIS sequence A000085, which also counts the number of Young tableaux with cells.
Monad of involutions
An involution on a set is the same thing as an action of on .
More generally, let be a monoidal category with distributive finite coproducts. The object is equipped with an involution
defined as the copairing of the right and left injections. Moreover, 2 can be given the structure of a monoid in , with unit and multiplication
defined by and (here we make use of the isomorphism to define by copairing). The mapping
thus extends to a monad on , sending any object to the free object equipped with an involution over . Explicitly, the unit and the multiplication of the monad are defined by tensoring the unit and the multiplication of the monoid with the identity on , while the involution on is likewise defined by tensoring the involution on 2 with the identity on .
We then have that involutions in are precisely the algebras of the monad . In the forward direction, given an involution , we define a monad algebra structure on by (again using the isomorphism ). Conversely, given a monad algebra , we can define an endomorphism by . The monad algebra laws imply that
and since is defined such that , we derive that is an involution.
- Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, CUP, 2009. (author pdf)