Hyperarithmetical Complexity of Infinitary Action Logic with Multiplexing
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913357343227904 |
|---|---|
| author | Pshenitsyn, Tikhon |
| author_facet | Pshenitsyn, Tikhon |
| contents | In 2023, Kuznetsov and Speranski introduced infinitary action logic with multiplexing $!^m\nabla \mathrm{ACT}_ω$ and proved that the derivability problem for it lies between the $ω$ and $ω^ω$ levels of the hyperarithmetical hierarchy. We prove that this problem is $Δ^0_{ω^ω}$-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 $!^m\nabla \mathrm{ACT}_ω$ equals $ω^ω$. We also prove that the fragment of $!^m\nabla \mathrm{ACT}_ω$ where Kleene star is not allowed to be in the scope of the subexponential is $Δ^0_{ω^ω}$-complete. Finally, we present a family of logics, which are fragments of $!^m\nabla \mathrm{ACT}_ω$, such that the complexity of the $k$-th logic lies between $Δ^0_{ω^k}$ and $Δ^0_{ω^{k+1}}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_04091 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Hyperarithmetical Complexity of Infinitary Action Logic with Multiplexing Pshenitsyn, Tikhon Logic Logic in Computer Science In 2023, Kuznetsov and Speranski introduced infinitary action logic with multiplexing $!^m\nabla \mathrm{ACT}_ω$ and proved that the derivability problem for it lies between the $ω$ and $ω^ω$ levels of the hyperarithmetical hierarchy. We prove that this problem is $Δ^0_{ω^ω}$-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 $!^m\nabla \mathrm{ACT}_ω$ equals $ω^ω$. We also prove that the fragment of $!^m\nabla \mathrm{ACT}_ω$ where Kleene star is not allowed to be in the scope of the subexponential is $Δ^0_{ω^ω}$-complete. Finally, we present a family of logics, which are fragments of $!^m\nabla \mathrm{ACT}_ω$, such that the complexity of the $k$-th logic lies between $Δ^0_{ω^k}$ and $Δ^0_{ω^{k+1}}$. |
| title | Hyperarithmetical Complexity of Infinitary Action Logic with Multiplexing |
| topic | Logic Logic in Computer Science |
| url | https://arxiv.org/abs/2312.04091 |