Conjectured characterizations and reductions of intuitionistic provability logics of arithmetic

Let HA{\sf HA} and PA{\sf PA} denote Heyting and Peano arithmetic, respectively, let N\mathbb{N} be the standard natural numbers, and let PL(T,U)\mathcal{PL}(T,U) and PLΣ1(T,U)\mathcal{PL}_{\Sigma_1}(T,U) denote the provability logics of UU with respect to TT, using arbitrary and Σ1\Sigma_1 substitutions, respectively. Write iH{\sf iH} for the intuitionistic provability logic of HA{\sf HA}, iH{\sf iH}^{*} for the logic defined in the cited work, iHP{\sf iH\underline{P}} for iH{\sf iH} extended by P\underline{\sf P}, and iHSP{\sf iH\underline{SP}} for iH{\sf iH} extended by S\underline{\sf S} and P\underline{\sf P}. The notations iHσ{\sf iH_\sigma}, iHσP{\sf iH_\sigma\underline{P}}, iHσSP{\sf iH_\sigma\underline{SP}}, and iHσ ⁣{\sf iH_\sigma^{*\!*}} are the corresponding Σ1\Sigma_1-substitution logics.

Characterizations and reductions conjecture. The following characterizations and reductions hold:

iH=PL(HA,HA)PLΣ1(HA,HA)=iHσ.{\sf iH}=\mathcal{PL}({\sf HA},{\sf HA})\leq\mathcal{PL}_{\Sigma_1}({\sf HA},{\sf HA})={\sf iH_\sigma}. iH=PL(HA,HA)PL(HA,N)=iHSP.{\sf iH}=\mathcal{PL}({\sf HA},{\sf HA})\leq\mathcal{PL}({\sf HA},\mathbb{N})={\sf iH\underline{SP}}. iHP=PL(HA,PA)PLΣ1(HA,PA)=iHσP.{\sf iH\underline{P}}=\mathcal{PL}({\sf HA},{\sf PA})\leq\mathcal{PL}_{\Sigma_1}({\sf HA},{\sf PA})={\sf iH_\sigma\underline{P}}. iHSP=PL(HA,N)PLΣ1(HA,N)=iHσSP.{\sf iH\underline{SP}}=\mathcal{PL}({\sf HA},\mathbb{N})\leq\mathcal{PL}_{\Sigma_1}({\sf HA},\mathbb{N})={\sf iH_\sigma\underline{SP}}. iH=PL(HA,HA)PLΣ1(HA,HA)=iHσ ⁣.{\sf iH}^{*}=\mathcal{PL}({\sf HA}^{*},{\sf HA}^{*})\leq\mathcal{PL}_{\Sigma_1}({\sf HA}^{*},{\sf HA}^{*})={\sf iH}_\sigma^{*\!*}.

Moreover, all these reductions are computable, and consequently all the provability logics are decidable.

Sources & referencesView supporting material

Primary source

Mojtaba Mojtahedi, “Hard Provability Logics”, arXiv:1911.04284 (2019).

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.