Finite head convergence implies positive denotation
ProvedTreeEquivalenceHORS.Equivalence.head_convergence_has_positive_denotationcomputabilityrecursion-schemes
In every valid scheme, a closed ground term which head-converges has positive denotation at the specified finite environment.
Preamble
import Definitions.Def_TreeEquivalenceHORS_Equivalence_FiniteSemantics
Formal statement
namespace TreeEquivalenceHORS.Equivalence
theorem head_convergence_has_positive_denotation (G : HORS) (vg : G.Valid) (t : Tm) (ht : G.typeOf [] t = some .o)
(h : ∃ c us, G.HeadConv t c us) : G.den [] G.etaStar [] t = .bit true := by sorry
end TreeEquivalenceHORS.EquivalenceSource
Mingkun Xiao and Yixuan Sun, Tree Equivalence of Higher-Order Recursion Schemes Is Undecidable, §§3 and 5.6. https://arxiv.org/html/2610.39678v1