Another connection between logic and computational complexity is provided by first-order arithmetical theories which are similar in form to familiar systems such as Primitive Recursive Arithmetic and Peano arithmetic. Connections between formal arithmetic and computability theory have been known since the 1940s – e.g. the sets of natural numbers definable by \(\Delta^0_1\)-formulas and \(\Sigma^0_1\)-formulas in the standard model of arithmetic respectively correspond to the recursive and recursively enumerable sets, the provably total functions of \(\textrm{I}\Sigma^0_1\) correspond to the primitive recursive functions while those of \(\mathsf{PA}\) correspond to the \(\epsilon_0\)-recursive functions (cf., e.g.,   Schwichtenberg 2011). From the 1970s onwards, a number of similar results have been obtained which link the levels of the Polynomial Hierarchy to a class of first-order theories collectively known as bounded arithmetics.