normalizing reduction
Definition 1.
Let $X$ be a set and $\to $ a reduction^{} (binary relation^{}) on $X$. An element $x\in X$ is said to be in normal form with respect to $\to $ if $x\nrightarrow y$ for all $y\in X$, i.e., if there is no $y\in X$ such that $x\to y$. Equivalently, $x$ is in normal form with respect to $\to $ iff $x\notin \mathrm{dom}(\to )$. To be irreducible is a common synonym for ‘to be in normal form’.
Denote by $\stackrel{*}{\to}$ the reflexive transitive closure of $\to $. An element $y\in X$ is said to be a normal form of $x\in X$ if $y$ is in normal form and $x\stackrel{*}{\to}y$.
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=\{a,b,c,d\}$ and $\to =\{(a,a),(a,b),(a,c),(b,c),(a,d)\}$. 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.
Title  normalizing reduction 

Canonical name  NormalizingReduction 
Date of creation  20130322 17:57:35 
Last modified on  20130322 17:57:35 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  10 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 68Q42 
Related topic  TerminatingReduction 
Related topic  DiamondLemma 
Defines  normal form 
Defines  irreducible 
Defines  normalizing 