Answers are grounded in this paper and cite their sources.
In 2023, Kuznetsov and Speranski introduced infinitary action logic with multiplexing !ᵐ∇ ACTω and proved that the derivability problem for it lies between the ω level and the ω ω level of the hyperarithmetical hierarchy. We prove that this problem is ⁰_ω ω-complete under Turing reductions. Namely, we show that it is recursively isomorphic to the satisfaction predicate for computable infinitary formulas of rank less than ω ω in the language of arithmetic. As a consequence we prove that the closure ordinal for !ᵐ∇ ACTω equals ω ω. We also prove that the fragment of !ᵐ∇ ACTω where Kleene star is not allowed to be in the scope of the subexponential is ⁰_ω ω-complete. Finally, we present a family of logics, which are fragments of !ᵐ∇ ACTω, such that the complexity of the k-th logic lies between ⁰_ω ᵏ and ⁰_ω ᵏ⁺¹.
No takes yet. Share an insight, caveat, or question.
Tikhon Pshenitsyn (2024) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: