Let be a set and a reduction (binary relation) on . An element is said to be in normal form with respect to if for all , i.e., if there is no such that . Equivalently, is in normal form with respect to iff . To be irreducible is a common synonym for ‘to be in normal form’.
Denote by the reflexive transitive closure of . An element is said to be a normal form of if is in normal form and .
A reduction on is said to be normalizing if every element has a normal form.
Let and . Then and are both in normal form. In addition, they are both normal forms of , while is a normal form only for . However, is not normalizing because neither nor have normal forms.
Let be the set of all positive integers greater than . Define the reduction on as follows: if there is an element such that . Then it is clear that every prime number is in normal form. Furthermore, every element in has normal forms, where is the number of prime divisors of . Clearly, for every . As a result, is normalizing.
|Date of creation||2013-03-22 17:57:35|
|Last modified on||2013-03-22 17:57:35|
|Last modified by||CWoo (3771)|