Switch to: References

Add citations

You must login to add citations.
  1. Iterated multiplication in $$ VTC ^0$$.Emil Jeřábek - 2022 - Archive for Mathematical Logic 61 (5):705-767.
    We show that $$ VTC ^0$$, the basic theory of bounded arithmetic corresponding to the complexity class $$\mathrm {TC}^0$$, proves the $$ IMUL $$ axiom expressing the totality of iterated multiplication satisfying its recursive definition, by formalizing a suitable version of the $$\mathrm {TC}^0$$ iterated multiplication algorithm by Hesse, Allender, and Barrington. As a consequence, $$ VTC ^0$$ can also prove the integer division axiom, and (by our previous results) the $$ RSUV $$ -translation of induction and minimization for sharply (...)
    Download  
     
    Export citation  
     
    Bookmark   3 citations  
  • Models of VTC0$\mathsf {VTC^0}$ as exponential integer parts.Emil Jeřábek - 2023 - Mathematical Logic Quarterly 69 (2):244-260.
    We prove that (additive) ordered group reducts of nonstandard models of the bounded arithmetical theory are recursively saturated in a rich language with predicates expressing the integers, rationals, and logarithmically bounded numbers. Combined with our previous results on the construction of the real exponential function on completions of models of, we show that every countable model of is an exponential integer part of a real‐closed exponential field.
    Download  
     
    Export citation  
     
    Bookmark  
  • Iterated multiplication in $$ VTC ^0$$ V T C 0.Emil Jeřábek - 2022 - Archive for Mathematical Logic 61 (5):705-767.
    We show that \, the basic theory of bounded arithmetic corresponding to the complexity class \, proves the \ axiom expressing the totality of iterated multiplication satisfying its recursive definition, by formalizing a suitable version of the \ iterated multiplication algorithm by Hesse, Allender, and Barrington. As a consequence, \ can also prove the integer division axiom, and the \-translation of induction and minimization for sharply bounded formulas. Similar consequences hold for the related theories \ and \. As a side (...)
    Download  
     
    Export citation  
     
    Bookmark   3 citations  
  • Elementary analytic functions in VT C 0.Emil Jeřábek - 2023 - Annals of Pure and Applied Logic 174 (6):103269.
    Download  
     
    Export citation  
     
    Bookmark   1 citation