You are here
Home ›normalizing reduction
Primary tabs
normalizing reduction
Definition 1.
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.
Examples.
-
Let be any set. Then no elements in are in normal form with respect to any reduction that is either reflexive. If is a symmetric relation, then is in normal form with respect to iff is not in the domain (or range) of .
-
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.
Mathematics Subject Classification
68Q42 Grammars and rewriting systems- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)
- Other useful stuff
Recent Activity
new question: Sorry to steal a few minutes of your time for this question, but i honestly don't know what else to do. by Whrazithar
new question: equality of the determinants of submatrices of an orthogonal matrix by ismayli
Jun 11
new correction: Typo by suitangi
Jun 2
new question: Creating another set with same cardinality. by hkkass
Jun 1
new image: ProblemOneRevised by unlord
new Education: Chapter II by rspuzio
May 31
new collection: The Calculus by Davis and Brenke by rspuzio
new question: Proofs by weixifan
new question: Summation Integration Question by trevor.nickle
May 27
new correction: typo+finite measure hypothesis by Filipe


