Nominaalsets

Nominaalsets, or nominal sets, are a mathematical framework used to model data that involve names and binding, such as variables in programming languages and formal logics. The standard setting begins with a countably infinite set A of atoms (names). The group G of interest is the group of all finite permutations of A, acting on A and on any set X equipped with a G-action: g ⋅ x.

An element x in a nominal set X is said to have finite support S ⊆ A if, whenever a permutation g fixes every atom in S, it also fixes x (g ⋅ x = x). Equivalently, S is the smallest such set, called the support of x. A nominal set is a set X together with a G-action such that every element has a finite support. Morphisms between nominal sets are equivariant maps f: X → Y that commute with the G-action.

Examples include the set A itself, with the natural permutation action, and finite products or function spaces built from nominal sets, which inherit a compatible action. A nominal set is called orbit-finite when it has only finitely many G-orbits.

Nominal sets provide a natural treatment of alpha-equivalence and freshness: two elements related by a name permutation that fixes all names in a term’s support represent the same syntactic object, and a name is fresh for an object if it does not belong to its support.

Applications include the formalization of syntax with binders, such as lambda-calculus, in a way that makes binding explicit and substitution capture-avoiding. Nominal techniques underpin nominal logic and nominal unification, and they support constructions like nominal automata for reasoning about infinite alphabets.