11 votes
Accepted

What is the consistency strength of this theory?

$\let\itp\vartriangleright\def\mr{\mathrm}\DeclareMathOperator\dom{dom}\let\bez\smallsetminus\let\sset\subseteq$The weakened theory is much weaker than bounded arithmetic. Let me denote the theory as $...
Emil Jeřábek's user avatar
9 votes
Accepted

Are the irrotational and solenoidal parts of a smooth vector field linearly independent?

$\newcommand\R{\mathbb R}\newcommand\na{\nabla}\newcommand\om{\boldsymbol{\omega}}\newcommand\si{\sigma}\newcommand\Ga{\Gamma}\newcommand\F{\mathbf F}\newcommand\x{\mathbf x}\newcommand\0{\mathbf 0}$...
Iosif Pinelis's user avatar
7 votes
Accepted

Intutionistic Robinson Arithmetic

Both are false. Consider the following Kripke model $M\vDash Q^e$ (in fact, it satisfies the intuitionistic version of $\mathrm{PA}^-$): it consists of two worlds $u,v$ such that $u$ sees $v$; the ...
Emil Jeřábek's user avatar
7 votes
Accepted

Bounded Arithmetic vs Complexity Theory

If $T_1$ and $T_2$ are theories corresponding to complexity classes $C_1$ and $C_2$ (resp.), then separation of $C_1$ from $C_2$ from $C_2$ implies separation of $T_1$ from $T_2$, but not necessarily ...
Emil Jeřábek's user avatar
5 votes

Bounded Arithmetic vs Complexity Theory

The arithmetic theories you're talking about typically have the property that the provably total functions are precisely the functions in some familiar complexity class. So suppose that the provably ...
Timothy Chow's user avatar
  • 77.9k
5 votes
Accepted

Weak Bounded Arithmetics

$\def\dotminus{\mathbin{\dot{-}}}$Actually, there are a number of papers on variants of $S^0_2$, $T^0_2$, and other theories axiomatized by $\Sigma^b_0$ (sharply bounded) schemata, in particular: [1] ...
Emil Jeřábek's user avatar
4 votes
Accepted

Logical complexity of hard functions conjectures

As given, $\phi_1$ and $\phi_2$ are $\Sigma_2$. They cannot be shown equivalent to $\Pi_2$ statements by any proof that relativizes. This follows by the same argument as in Examples of $G_\delta$ ...
Emil Jeřábek's user avatar
4 votes
Accepted

On subtheories of $\mathsf{T_2+EXP}$

All these theories coincide: if exponentiation is total, a bounded formula is equivalent on any bounded domain to a sharply bounded formula (with an exponentially large parameter), hence bounded ...
Emil Jeřábek's user avatar
3 votes
Accepted

Bounded Arithmetic and Counting

Q1: Yes. The paper you linked to in the question actually proves the theorem for every pair of natural numbers $p,q$ such that $p$ has a prime factor that does not divide $q$ (in other words, $p$ does ...
Emil Jeřábek's user avatar
1 vote

Provability in $S^1_2$

(Note: I'm not actually familiar with $S^1_2$ and the related formalism, but I'm going by your description of the theory, and I have been already thinking about related questions in an informal way.) ...
Itai Bar-Natan's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible