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

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
Keywords Mathematics   Mathematics, general   Algebra   Mathematical Logic and Foundations
Categories (categorize this paper)
Reprint years 2005
DOI 10.1007/s00153-004-0249-8
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 64,159
Through your library

References found in this work BETA

Notes on Polynomially Bounded Arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
The Proof Complexity of Linear Algebra.Michael Soltys & Stephen Cook - 2004 - Annals of Pure and Applied Logic 130 (1-3):277-323.

Add more references

Citations of this work BETA

Proving Properties of Matrices Over {\ Mathbb {Z} _ {2}}.Michael Soltys - 2012 - Archive for Mathematical Logic 51 (5-6):535-551.

Add more citations

Similar books and articles

Weakly One-Based Geometric Theories.Alexander Berenstein & Evgueni Vassiliev - 2012 - Journal of Symbolic Logic 77 (2):392-422.
Proving Properties of Matrices Over {\ Mathbb {Z} _ {2}}.Michael Soltys - 2012 - Archive for Mathematical Logic 51 (5-6):535-551.
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 index
2013-11-23

Total views
30 ( #366,542 of 2,454,826 )

Recent downloads (6 months)
1 ( #449,241 of 2,454,826 )

How can I increase my downloads?

Downloads

My notes