PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (198)
Orphanage
Unclass'd
Unproven (490)
Corrections (7)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very high Entry average rating: Very high
normalizing reduction (Definition)
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 $ \stackrel{*}{\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 \stackrel{*}{\rightarrow} 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=\lbrace a,b,c,d\rbrace$ and $ \to = \lbrace (a,a),(a,b),(a,c),(b,c),(a,d)\rbrace$. 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.



"normalizing reduction" is owned by CWoo.
(view preamble)

View style:

See Also: terminating reduction, diamond lemma

Also defines:  normal form, irreducible, normalizing
Log in to rate this entry.
(view current ratings)

Cross-references: prime divisors, number, prime number, clear, integers, positive, addition, range, domain, symmetric relation, Reflexive, reflexive transitive closure, iff, binary relation, reduction
There are 13 references to this entry.

This is version 7 of normalizing reduction, born on 2008-03-31, modified 2008-04-02.
Object id is 10460, canonical name is NormalizingReduction.
Accessed 734 times total.

Classification:
AMS MSC: 68Q42 (Computer science :: Theory of computing :: Grammars and rewriting systems)
Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)