Abelian groups and quadratic residues in weak arithmetic

0343145 - MÚ 2011 RIV DE eng J - Journal Article
Jeřábek, Emil
Abelian groups and quadratic residues in weak arithmetic.
Mathematical Logic Quarterly. Roč. 56, č. 3 (2010), s. 262-278. ISSN 0942-5616. E-ISSN 1521-3870
R&D Projects: GA AV ČR IAA1019401; GA MŠMT(CZ) 1M0545
Institutional research plan: CEZ:AV0Z10190503
Keywords : bounded arithmetic * abelian group * Fermat's little theorem * quadratic reciprocity
Subject RIV: BA - General Mathematics
Impact factor: 0.361, year: 2010
http://onlinelibrary.wiley.com/doi/10.1002/malq.200910009/abstract;jsessionid=9F636FFACB84C025FD90C7E6880350DD.f03t03

We investigate the provability of some properties of abelian groups and quadratic residues in variants of bounded arithmetic. Specifically, we show that the structure theorem for finite abelian groups is provable in S22 + iWPHP( b1), and use it to derive Fermat’s little theorem and Euler’s criterion for the Legendre symbol in S22 + iWPHP(PV )extended by the pigeonhole principle PHP(PV ). We prove the quadratic reciprocity theorem (including the supplementary laws) in the arithmetic theories T02 +Count2(PV ) and I 0 + Count2( 0) with modulo-2 counting principles.
Permanent Link: http://hdl.handle.net/11104/0185687