normalizing reduction

Definition 1.

Let X be a set and a reductionPlanetmathPlanetmathPlanetmath (binary relationMathworldPlanetmath) on X. An element xX is said to be in normal form with respect to if xy for all yX, i.e., if there is no yX such that xy. Equivalently, x is in normal form with respect to iff xdom(). To be irreducible is a common synonym for ‘to be in normal form’.

Denote by * the reflexive transitive closure of . An element yX is said to be a normal form of xX if y is in normal form and x*y.

A reduction on X is said to be normalizing if every element xX has a normal form.


  • Let X be any set. Then no elements in X are in normal form with respect to any reduction that is either reflexiveMathworldPlanetmathPlanetmath. If is a symmetric relationMathworldPlanetmath, then xX is in normal form with respect to iff x is not in the domain (or range) of .

  • Let X={a,b,c,d} and ={(a,a),(a,b),(a,c),(b,c),(a,d)}. Then c and d are both in normal form. In additionPlanetmathPlanetmath, 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 on X as follows: ab if there is an element cX such that a=bc. Then it is clear that every prime numberMathworldPlanetmath is in normal form. Furthermore, every element x in X has n normal forms, where n is the number of prime divisorsMathworldPlanetmathPlanetmath of x. Clearly, n1 for every xX. As a result, X is normalizing.

Title normalizing reduction
Canonical name NormalizingReduction
Date of creation 2013-03-22 17:57:35
Last modified on 2013-03-22 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