proposition: Lemma M_backward_exists m p M: Mrel m p M -> exists l, M = T l.
proof: Proof. enough (forall a b x, M ++ [x] = (a, b) :: Step M -> M ++ [x] = tab (fun k => (a + k * n, b + k)) (S (length M))) as H. - intros H1 % H; apply app_injective_right in H1 as [H1 _]; eauto. - induction M as [|[l r]]; [cbn|]; intros; simplify; eauto. injection H as ? ? H1; subst. specialize (IHM _ _ _ H1) as ->. cbn [length]; rewrite !tab_S; cbn; simplify; do 2 f_equal. f_equal; lia. eapply tab_ext; intros; f_equal; lia. Qed.
imports: List Lia Undecidability.HOU(std.std axioms)