Weak theories of linear algebra

Archive for Mathematical Logic 44 (2):195-208 (2005)
  Copy   BIBTEX

Abstract

We investigate the theories of linear algebra, which were originally defined to study the question of whether commutativity of matrix inverses has polysize Frege proofs. We give sentences separating quantified versions of these theories, and define a fragment in which we can interpret a weak theory V 1 of bounded arithmetic and carry out polynomial time reasoning about matrices - for example, we can formalize the Gaussian elimination algorithm. We show that, even if we restrict our language, proves the commutativity of inverses

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,227

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

Weakly one-based geometric theories.Alexander Berenstein & Evgueni Vassiliev - 2012 - Journal of Symbolic Logic 77 (2):392-422.
On VC-minimal theories and variants.Vincent Guingona & Michael C. Laskowski - 2013 - Archive for Mathematical Logic 52 (7-8):743-758.
Linear transformations in unitary geometric algebra.Garret Sobczyk - 1993 - Foundations of Physics 23 (10):1375-1385.
n‐linear weakly Heyting algebras.Sergio A. Celani - 2006 - Mathematical Logic Quarterly 52 (4):404-416.
Modularity of proof-nets.Roberto Maieli & Quintijn Puite - 2005 - Archive for Mathematical Logic 44 (2):167-193.
Dynamic ordinal analysis.Arnold Beckmann - 2003 - Archive for Mathematical Logic 42 (4):303-334.
Minimal truth and interpretability.Martin Fischer - 2009 - Review of Symbolic Logic 2 (4):799-815.

Analytics

Added to PP
2013-11-23

Downloads
39 (#410,656)

6 months
9 (#315,924)

Historical graph of downloads
How can I increase my downloads?