Let be an abstract rewriting system, i.e., a set equipped with a binary relation . Write for the reflexive-transitive closure of . We say that is confluent iff for every such that and , there exists such that and .
Note that only occurs in the definition of confluence, not the underlying . Confluence can therefore be reframed as a property of a preorder.
Say that an abstract rewriting system is strongly normalizing if every sequence
is eventually stable: there is some such that . An element is normal if implies .
Define to mean and . The condition of being strongly normalizing is that all downward chains
terminate after finitely many steps (no infinite descent), i.e., that is a well-founded relation.
In a confluent strongly normalizing abstract rewriting system , for every element there is a unique normal such that .
Of course, for every there is some normal for which . If that were not true for some , then by dependent choice, we can construct a sequence with and for which (since by hypothesis no in the chain is normal). But this violates “no infinite descent”.
Now suppose and for normal . By confluence, there is some such that and . By normality of , we have , establishing uniqueness.
With a little extra care, the word “confluent” in the proposition can be replaced by “locally confluent”, in the sense of locally confluent relation.
Take any abstract rewriting system . Given a certain element as the starting point, the set is the set of the elements reachable from by rewrites in . When is confluent, restricted to that set is a direction on that set.
Confluence can be seen as a local form of directedness. Again viewing as a preorder, directedness says any two elements must have an upper bound, while confluence says that any two elements have an upper bound if they also have a lower bound.
Last revised on November 6, 2026 at 20:40:22. See the history of this page for a list of all contributions to it.