# normalizing reduction

###### Definition 1.

Let $X$ be a set and $\rightarrow$ a reduction   (binary relation  ) on $X$. An element $x\in X$ is said to be in normal form with respect to $\rightarrow$ if $x\nrightarrow y$ for all $y\in X$, i.e., if there is no $y\in X$ such that $x\rightarrow y$. 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 $\lx@stackrel{{\scriptstyle*}}{{\rightarrow}}$ the reflexive transitive closure of $\rightarrow$. An element $y\in X$ is said to be a normal form of $x\in X$ if $y$ is in normal form and $x\lx@stackrel{{\scriptstyle*}}{{\rightarrow}}y$.

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

Examples.

Title normalizing reduction NormalizingReduction 2013-03-22 17:57:35 2013-03-22 17:57:35 CWoo (3771) CWoo (3771) 10 CWoo (3771) Definition msc 68Q42 TerminatingReduction DiamondLemma normal form irreducible normalizing