Let $iT$ be the intuitionistic first order theory with non-logical axioms of classical first order theory $T$.

Theorem1. If $\mathsf{T^i_2}\vdash \mathsf{T_2}$, then $\mathsf{T^i_2}$ proves that the polynomial time hierarchy collapses to $\Sigma^p_{i+3}$.

proof. See Relating the Bounded Arithmetic and Polynomial-Time Hierarchies.

Corollary. There exists $i\in \mathbb{N}$ such that $\mathsf{T^i_2\vdash T_2}$ iff there exists $j\in \mathbb{N}$ such that $i\mathsf{T^j_2}\vdash i\mathsf{T_2}$.

proof. Straightforward by Theorem 1.

Q1. Is the following statement true?

There exists $i\in \mathbb{N}$ such that $I\mathsf{E_i}\vdash I\Delta_0$ iff there exists $j\in \mathbb{N}$ such that $iI\mathsf{E_j}\vdash iI\Delta_0$.




Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.