normalizing reduction

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 $\lx@stackrel{{\scriptstyle*}}{{\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\lx@stackrel{{\scriptstyle*}}{{\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=\{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\geq 1$ for every $x\in X$. As a result, $X$ is normalizing.

Title normalizing reduction NormalizingReduction 2013-03-22 17:57:35 2013-03-22 17:57:35 CWoo (3771) CWoo (3771) 10 CWoo (3771) Definition msc 68Q42 TerminatingReduction DiamondLemma normal form irreducible normalizing