On bounded arithmetic augmented by the ability to count certain sets of primes. (English) Zbl 1174.03026

The paper is concerned with the problem of proving the existence of infinitely many primes in variants of bounded arithmetic. J. B. Paris, A. J. Wilkie, and A. R. Woods [J. Symb. Log. 53, No. 4, 1235–1244 (1988; Zbl 0688.03042)] proved infinitude of primes in the theory \(\text{I}\Delta_0+\Omega_1\), but it does not seem to be provable in \(\text{I}\Delta_0\) alone. A. R. Woods [Some problems in logic and number theory, and their connections. Ph.D. thesis, Univ. Manchester (1981)] conjectured that the infinitude of primes is provable in the theory \(\text{I}\Delta_0(\pi)\) augmented by a recursive definition of the prime-counting function \(\pi\).
In the present paper, the authors prove the existence of infinitely many primes, and, in fact, Bertrand’s postulate (stating that there is a prime in the interval \((x,2x]\) for every \(x>0\)), in a similar but somewhat stronger theory, \(\text{I}\Delta_0(\xi)+\text{def}(\xi)\), where \(\text{def}(\xi)\) denotes a natural recursive definition of the function \(\xi(x,y,e)\) counting the number of primes \(p\leq x\) such that \(\lfloor y/p^e\rfloor\) is odd. Since the proof heavily relies on counting with logarithms, the paper includes a detailed development of a suitable rational approximation to the natural logarithm function, as well as several prime-counting functions, such as Chebyshev’s \(\theta\) and \(\psi\), in bounded arithmetic.


03F30 First-order arithmetic and fragments
03F20 Complexity of proofs
11A41 Primes


Zbl 0688.03042
Full Text: DOI


[1] Proving infinitude of prime numbers using binomial coefficients pp 1– (2008)
[2] Journal of the Indian Mathematical Society 11 pp 181– (1919)
[3] Introduction to number theory (1983)
[4] Provability of the pigeonhole principle and the existence of infinitely many primes 53 pp 1235– (1988) · Zbl 0688.03042
[5] DOI: 10.1007/BFb0075316
[6] Rozprawy Matematycine IV pp 1– (1953)
[7] DOI: 10.2307/2369154 · JFM 13.0132.03
[8] DOI: 10.1016/0168-0072(94)00029-3 · Zbl 0826.03027
[9] DOI: 10.1016/0168-0072(91)90096-5 · Zbl 0747.03025
[10] Logic Colloquium ’77 pp 237– (1978)
[11] Journal de mathématiques pares et appliquées, I série 17 pp 366– (1852)
[12] Messenger of Mathematics 21 pp 87– (1892)
[13] Local behaviour of the Chebyshev theorem in models of I{\(\Delta\)}0 57 pp 12– (1992)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.