Hard Provability Logics

Let $\mathcal{P}\mathcal{L}(\mathsf{T},{\mathsf{T}}^{\mathrm{\prime }})$ and $$\mathcal{P}\mathcal{L}${\Sigma_1}({\sf T},{\sf T}‘)$respectivelyindicatestheprovabilitylogicand$\Sigma_1$-provabilitylogicof${\sf T}$relativein${\sf T}’$. In this paper we characterize the following relative provability logics: ${\mathcal{P}\mathcal{L}}_{{\mathrm{\Sigma }}_1}(\mathsf{H}\mathsf{A},\mathbb{N})$, $$\mathcal{P}\mathcal{L}${\Sigma_1}({\sf HA},{\sf PA})$,$$\mathcal{P}\mathcal{L}${\Sigma_1}({\sf HA}^*,$\mathbb{N}$)$,$$\mathcal{P}\mathcal{L}${\Sigma_1}({\sf HA}^,{\sf PA})$,$$\mathcal{P}\mathcal{L}$({\sf PA},{\sf HA})$,$$\mathcal{P}\mathcal{L}$_{\Sigma_1}({\sf PA},{\sf HA})$,$$\mathcal{P}\mathcal{L}$({\sf PA}^,{\sf HA})$,$$\mathcal{P}\mathcal{L}${\Sigma_1}({\sf PA}^,{\sf HA})$,$$\mathcal{P}\mathcal{L}$({\sf PA}^,{\sf PA})$,$$\mathcal{P}\mathcal{L}${\Sigma_1}({\sf PA}^,{\sf PA})$,$$\mathcal{P}\mathcal{L}$({\sf PA}^,$\mathbb{N}$)$,$$\mathcal{P}\mathcal{L}${\Sigma_1}({\sf PA}^*,$\mathbb{N}$)$ (see Table \ref{Table-Theories}). It turns out that all of these provability logics are decidable. The notion of {\em reduction} for provability logics, first informally considered in \cite{reduction}. In this paper, we formalize a generalization of this notion (\Cref{Definition-Reduction-PL}) and provide several reductions of provability logics (See diagram \ref{Diagram-full}). The interesting fact is that ${\mathcal{P}\mathcal{L}}_{{\mathrm{\Sigma }}_1}(\mathsf{H}\mathsf{A},\mathbb{N})$ is the hardest provability logic: the arithmetical completenesses of all provability logics listed above, as well as well-known provability logics like $$\mathcal{P}\mathcal{L}$({\sf PA},{\sf PA})$,$$\mathcal{P}\mathcal{L}$({\sf PA},$\mathbb{N}$)$,$$\mathcal{P}\mathcal{L}${\Sigma_1}({\sf PA},{\sf PA})$,$$\mathcal{P}\mathcal{L}${\Sigma_1}({\sf PA},$\mathbb{N}$)$and$$\mathcal{P}\mathcal{L}${\Sigma_1}({\sf HA},{\sf HA})$ are all propositionally reducible to the arithmetical completeness of $$\mathcal{P}\mathcal{L}$_{\Sigma_1}({\sf HA},$\mathbb{N}$)$.