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.
|Autori:||BERARDUCCI A; INTRIGILA B|
|Titolo:||Combinatorial principles in elementary number theory|
|Anno del prodotto:||1991|
|Digital Object Identifier (DOI):||10.1016/0168-0072(91)90096-5|
|Appare nelle tipologie:||1.1 Articolo in rivista|