Definition 1   Let $X$ be a set and $\rightarrow$ a reduction (binary relation) on $X$ An element is said to be in normal form with respect to $\rightarrow$ if for all , i.e., if there is no such that . Equivalently, $x$ is in normal form with respect to $\to$ iff $x\notin \operatorname{dom}(\to)$ To be irreducible is a common synonym for `to be in normal form'.

Denote by $\stackrel{*}{\rightarrow}$ the reflexive transitive closure of $\rightarrow$ An element is said to be a normal form of if $y$ is in normal form and .

A reduction $\to$ on $X$ is said to be normalizing if every element $x\in X$ has a normal form.

Examples.

• Let $X$ be any set. Then no elements in $X$ are in normal form with respect to any reduction that is either reflexive. If $\to$ is a symmetric relation, then $x\in X$ is in normal form with respect to $\to$ iff $x$ is not in the domain (or range) of $\to$
• Let $X=\lbrace a,b,c,d\rbrace$ and $\to = \lbrace (a,a),(a,b),(a,c),(b,c),(a,d)\rbrace$ Then $c$ and $d$ are both in normal form. In addition, they are both normal forms of $a$ while $d$ is a normal form only for $a$ However, $X$ is not normalizing because neither $c$ nor $d$ have normal forms.
• Let $X$ be the set of all positive integers greater than $1$ Define the reduction $\to$ on $X$ as follows: $a\to b$ if there is an element $c\in X$ such that $a=bc$ Then it is clear that every prime number is in normal form. Furthermore, every element $x$ in $X$ has $n$ normal forms, where $n$ is the number of prime divisors of $x$ Clearly, $n\ge 1$ for every $x\in X$ As a result, $X$ is normalizing.