Symmetric inverse semigroup

In abstract algebra, the set ${\mathcal {I}}_{X}$ of all partial one-one transformations on a set X forms an inverse semigroup, called the symmetric inverse semigroup (or monoid) on X. In general ${\mathcal {I}}_{X}$ is not commutative. More details about its origin are available in the discussion on the origins of the inverse semigroup.

Finite symmetric inverse semigroups

When X is a finite set {1, ..., n}, the inverse semigroup of one-one partial transformations is denoted by C_n and its elements are called charts or partial symmetries. The notion of chart generalizes the notion of permutation. A (famous) example of charts are the hypomorphic mapping sets from the reconstruction conjecture in graph theory.

The cycle notation of classical, group-based permutations generalizes to symmetric inverse semigroups by the addition of a notion called a path, which (unlike a cycle) ends when it reaches the "undefined" element; the notation thus extended is called path notation.

Reconstruction conjecture

References

• S. Lipscomb, "Symmetric Inverse Semigroups", AMS Mathematical Surveys and Monographs (1997), ISBN 0-8218-0627-0.