Combinatorial principles in elementary number theory

Annals of Pure and Applied Logic 55 (1):35-50 (1991)
  Copy   BIBTEX

Abstract

We prove that the theory IΔ0, extended by a weak version of the Δ0-Pigeonhole Principle, proves that every integer is the sum of four squares (Lagrange's theorem). Since the required weak version is derivable from the theory IΔ0 + ∀x (xlog(x) exists), our results give a positive answer to a question of Macintyre (1986). In the rest of the paper we consider the number-theoretical consequences of a new combinatorial principle, the ‘Δ0-Equipartition Principle’ (Δ0EQ). In particular we give a new proof, which can be formalized in IΔ0 + Δ0EQ, of the fact that every prime of the form 4n + 1 is the sum of two squares

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 76,346

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Analytics

Added to PP
2013-11-23

Downloads
13 (#768,068)

6 months
1 (#450,993)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Two (or three) notions of finitism.Mihai Ganea - 2010 - Review of Symbolic Logic 3 (1):119-144.
End extensions of models of linearly bounded arithmetic.Domenico Zambella - 1997 - Annals of Pure and Applied Logic 88 (2-3):263-277.
The prime number theorem and fragments ofP A.C. Cornaros & C. Dimitracopoulos - 1994 - Archive for Mathematical Logic 33 (4):265-281.
Quadratic forms in models of IΔ0+ Ω1. I.Paola D’Aquino & Angus Macintyre - 2007 - Annals of Pure and Applied Logic 148 (1):31-48.
Quadratic forms in models of I Δ 0 + Ω 1. I.Paola D’Aquino & Angus Macintyre - 2007 - Annals of Pure and Applied Logic 148 (1-3):31-48.

View all 14 citations / Add more citations

References found in this work

Existence and feasibility in arithmetic.Rohit Parikh - 1971 - Journal of Symbolic Logic 36 (3):494-508.
On the scheme of induction for bounded arithmetic formulas.A. J. Wilkie & J. B. Paris - 1987 - Annals of Pure and Applied Logic 35 (C):261-302.
Some Classes of Recursive Functions.Andrzej Grzegorczyk - 1955 - Journal of Symbolic Logic 20 (1):71-72.
Primes and their residue rings in models of open induction.Angus Macintyre & David Marker - 1989 - Annals of Pure and Applied Logic 43 (1):57-77.

View all 6 references / Add more references