Multivariate big-step induction conjecture for right cancellation of list concatenation

About 3 years old · traced to

Let T1T_{1} be the base theory for list concatenation. For a finite sequence of pairwise distinct list variables X⃗=(X1,…,Xm)\vec{X}=(X_{1},\dots,X_{m}) and a sequence of non-zero natural numbers p⃗=(p1,…,pm)\vec{p}=(p_{1},\dots,p_{m}), let IX⃗↷p⃗listφI^{\mathsf{list}}_{\vec{X}\curvearrowright\vec{p}}\varphi be the corresponding multivariate big-step list-induction axiom, and let Open(L1)-IND↗↷list\mathrm{Open}(\mathcal{L}_{1})\text{-}\mathrm{IND}^{\mathsf{list}}_{\nearrow_{\curvearrowright}} be the theory generated by these axioms for open formulas. For lists X,Y,ZX,Y,Z, write Y⌢XY\frown X for concatenation. Right-cancellation conjecture.

T1+Open(L1)-IND↗↷list⊬Y⌢X=Z⌢X→Y=Z.T_{1} + {\mathrm{Open}(\mathcal{L}_{1})}\text{-}\mathrm{IND}^{\mathsf{list}}_{\nearrow_{\curvearrowright}} \not\vdash Y \frown X = Z \frown X \rightarrow Y = Z.

The claim concerns whether multivariate heterogeneous big-step induction can prove right cancellation, a simple and practically relevant property of finite lists. The source presents the claim after defining the induction schema; its resolution is not supplied and remains open.

References

Primary source

Stefan Hetzl and Jannik Vierling, “Quantifier-free induction for lists”, arXiv:2305.08682 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.