A Counterexample to Lemma 64 of the Kahrs and Smith Proof for RTA-79
Moses Rahnama
Source abstract
<p>A complete targeted proof graph need not be universal, even when ⇓<sub><i>A</i></sub> is a consistency invariant. This gives a counterexample to Lemma&nbsp;64 of Kahrs and Smith, <i>Non-ω-Overlapping TRSs are UN</i> (FSCD&nbsp;2016). For the rule <i>d</i>(<i>x</i>)&nbsp;→&nbsp;<i>x</i>, the carrier {<i>c</i>,&nbsp;<i>d</i>(<i>c</i>),&nbsp;<i>d</i>(<i>d</i>(<i>c</i>))} admits such a graph with the sole parent edge <i>d</i>(<i>c</i>)&nbsp;↦&nbsp;<i>d</i>(<i>d</i>(<i>c</i>)). Its represented equivalence omits the root equation <i>d</i>(<i>c</i>)&nbsp;⇓<sub><i>A</i></sub>&nbsp;<i>c</i>. The proof checks the consistency-invariant premise and every graph condition, and identifies the failed induction step in the published argument. Changing a parent edge gives a universal graph on the same carrier. Problem&nbsp;79 of the RTA list of open problems is the conjecture that a term rewriting system has unique normal forms if its rules do not overlap under unification with infinite terms. The published solution of RTA-79 depends on Lemma&nbsp;64. Therefore, the published proof is false, and the RTA-79 problem remains open.</p>
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.