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	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