<p>It is a little bit sketchy, but here is my argument: Suppose that there are three terms <code>t</code>, <code>u</code>, <code>v</code> such that <code>t</code> reduces to <code>u</code>, <code>t</code> reduces to <code>v</code> and suppose that each term has a unique normal form. Since you are weakly normalizing as you said, there exists a normal form for <code>v</code> and <code>u</code>. But since the normal form is unique, then <code>v</code> and <code>u</code> are joinable. Hence, the system is confluent.</p>

CC BY-SA 4.0
2018-06-18T01:00:47.460Z
So the argument at the end of your answer is that if $v$ and $u$ were NOT joinable, then $t$ would have two distinct normal forms, contradicting the assumption that $t$ has a unique normal form? Am I understanding correctly?
User7819
CC BY-SA 4.0
2018-06-18T07:31:42.617Z
Yes, that is exactly my argument.
Saroupille
CC BY-SA 4.0
2018-06-16T21:07:20.613Z
2020-03-16T13:57:07.743Z
2020-03-16T13:57:07.743Z
Saroupille
<p>Consider a term rewriting system $\mathcal{R} = (\Sigma, R)$ over a signature $\Sigma$ with basic rewrite rules $R$. If $\mathcal{R}$ is weakly normalizing and confluent, then we know that each $\Sigma$-term has a unique normal form (with respect to $\mathcal{R}$). Is the converse also true? I.e. if each term has a unique normal form with respect to $\mathcal{R}$, then does it follow that $\mathcal{R}$ is weakly normalizing and confluent? Obviously if each term has a unique normal form, then the system is weakly normalizing, so it remains to ask whether it will be confluent. </p>

<p>In short, I am wondering whether the property of a term rewriting system to be weakly normalizing and confluent is strictly stronger than the property of each term having a unique normal form (with respect to the system).</p>

CC BY-SA 4.0
2018-06-18T07:09:29.950Z
This question is not reaearch level and would have been more suitable for [CS.SE](https://cs.stackexchange.com/). Anyway, beware that the standard definition of *unique normal form property* (commonly abbreviated UN) does **not** include existence, i.e., UN = "if two normal forms are related by rewriting (in any direction), then they are equal".  This is implied, but does *not* imply CR.  What you call "having a unique normal form" is UN+WN, which obviously implies CR.
Damiano Mazza
<term-rewriting-systems>
Does having unique normal forms imply weak normalization and confluence?
User7819
# Does having unique normal forms imply weak normalization and confluence?

(Asked by: username_0 on 2018-06-16)

Consider a term rewriting system $\mathcal{R} = (\Sigma, R)$ over a signature $\Sigma$ with basic rewrite rules $R$. If $\mathcal{R}$ is weakly normalizing and confluent, then we know that each $\Sigma$-term has a unique normal form (with respect to $\mathcal{R}$). Is the converse also true? I.e. if each term has a unique normal form with respect to $\mathcal{R}$, then does it follow that $\mathcal{R}$ is weakly normalizing and confluent? Obviously if each term has a unique normal form, then the system is weakly normalizing, so it remains to ask whether it will be confluent.

In short, I am wondering whether the property of a term rewriting system to be weakly normalizing and confluent is strictly stronger than the property of each term having a unique normal form (with respect to the system).

**Tags:** term-rewriting-systems
> **Comments:**
> **username_1**: This question is not reaearch level and would have been more suitable for [CS.SE](https://cs.stackexchange.com/). Anyway, beware that the standard definition of *unique normal form property* (commonly abbreviated UN) does **not** include existence, i.e., UN = "if two normal forms are related by rewriting (in any direction), then they are equal".  This is implied, but does *not* imply CR.  What you call "having a unique normal form" is UN+WN, which obviously implies CR.  

---

## 1 answers

### Answer by username_2 on 2018-06-16. Score: 4 | Accepted answer

It is a little bit sketchy, but here is my argument: Suppose that there are three terms `t`, `u`, `v` such that `t` reduces to `u`, `t` reduces to `v` and suppose that each term has a unique normal form. Since you are weakly normalizing as you said, there exists a normal form for `v` and `u`. But since the normal form is unique, then `v` and `u` are joinable. Hence, the system is confluent.

> **Comments:**
> **username_0**: So the argument at the end of your answer is that if $v$ and $u$ were NOT joinable, then $t$ would have two distinct normal forms, contradicting the assumption that $t$ has a unique normal form? Am I understanding correctly?  
> **username_2**: Yes, that is exactly my argument.  

---

