Provability of the pigeonhole principle and the existence of infinitely many primes
From MaRDI portal
Publication:4206725
DOI10.2307/2274618zbMath0688.03042OpenAlexW2170605748MaRDI QIDQ4206725
Alan R. Woods, A. J. Wilkie, Jeffrey Bruce Paris
Publication date: 1988
Published in: The Journal of Symbolic Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2307/2274618
Related Items (58)
On the Proof Complexity of Paris-Harrington and Off-Diagonal Ramsey Tautologies ⋮ Combinatorics with Definable Sets: Euler Characteristics and Grothendieck Rings ⋮ The prime number theorem and fragments of PA ⋮ Binary models generated by their tally part ⋮ Dual weak pigeonhole principle, Boolean complexity, and derandomization ⋮ The complexity of the pigeonhole principle ⋮ Expander Construction in VNC1 ⋮ On Grzegorczyk induction ⋮ Quadratic forms in models of \(I\Delta _{0}+\Omega _{1}\). I ⋮ Circuit principles and weak pigeonhole variants ⋮ \(\Delta_ 0\)-complexity of the relation \(y= \prod_{i\leq n} F(i)\) ⋮ Iterated multiplication in \(VTC^0\) ⋮ Approximate Euler characteristic, dimension, and weak pigeonhole principles ⋮ Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds ⋮ FRAGMENTS OF APPROXIMATE COUNTING ⋮ Lower bounds to the size of constant-depth propositional proofs ⋮ Local behaviour of the Chebyshev theorem in models of I⊿0 ⋮ Annual Meeting of the Association for Symbolic Logic, Los Angeles, 1989 ⋮ Toward the limits of the Tennenbaum phenomenon ⋮ Proof complexity in algebraic systems and bounded depth Frege systems with modular counting ⋮ \(\text{Count}(q)\) does not imply \(\text{Count}(p)\) ⋮ End extensions of models of linearly bounded arithmetic ⋮ Pell equations and exponentiation in fragments of arithmetic ⋮ Some consequences of cryptographical conjectures for \(S_2^1\) and EF ⋮ Collapsing modular counting in bounded arithmetic and constant depth propositional proofs ⋮ Expander construction in \(\mathrm{VNC}^1\) ⋮ The polynomial and linear hierarchies in models where the weak pigeonhole principle fails ⋮ Improved bounds on the weak pigeonhole principle and infinitely many primes from weaker axioms ⋮ ON THE EXISTENCE OF STRONG PROOF COMPLEXITY GENERATORS ⋮ Quadratic forms in models of \(I\Delta_0 + \Omega_1\). II: Local equivalence ⋮ Resolution proofs of generalized pigeonhole principles ⋮ Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic ⋮ Bounded arithmetic and the polynomial hierarchy ⋮ A new proof of the weak pigeonhole principle ⋮ Combinatorial principles in elementary number theory ⋮ Tautologies from Pseudo-Random Generators ⋮ Lower bounds for cutting planes proofs with small coefficients ⋮ Lower bounds for resolution and cutting plane proofs and monotone computations ⋮ Towards a unified complexity theory of total functions ⋮ Where pigeonhole principles meet Koenig lemmas ⋮ Abelian groups and quadratic residues in weak arithmetic ⋮ A form of feasible interpolation for constant depth Frege systems ⋮ Exponential lower bounds for the pigeonhole principle ⋮ Approximate counting in bounded arithmetic ⋮ Upper and lower Ramsey bounds in bounded arithmetic ⋮ Independence results for variants of sharply bounded induction ⋮ The Complexity of Propositional Proofs ⋮ On subrecursive complexity of integration ⋮ On bounded arithmetic augmented by the ability to count certain sets of primes ⋮ Approximate counting by hashing in bounded arithmetic ⋮ Non-standard finite fields over \(I\Delta_0+\Omega_1\) ⋮ Multifunction algebras and the provability of \(PH\downarrow\) ⋮ Solving Pell equations locally in models of IΔ0 ⋮ Structures interpretable in models of bounded arithmetic ⋮ A model-theoretic characterization of the weak pigeonhole principle ⋮ Witnessing functions in bounded arithmetic and search problems ⋮ Lower bounds for the weak pigeonhole principle and random formulas beyond resolution ⋮ Quasipolynomial size proofs of the propositional pigeonhole principle
This page was built for publication: Provability of the pigeonhole principle and the existence of infinitely many primes
