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.