Document Type
Book Chapter
Publication Date
2017
Abstract
Matroids generalize the familiar notion of linear dependence from linear algebra. Following a brief discussion of founding work in computability and matroids, we use the techniques of reverse mathematics to determine the logical strength of some basis theorems for matroids and enumerated matroids. Next, using Weihrauch reducibility, we relate the basis results to combinatorial choice principles and statements about vector spaces. Finally, we formalize some of the Weihrauch reductions to extract related reverse mathematics results. In particular, we show that the existence of bases for vector spaces of bounded dimension is equivalent to the induction scheme for \Sigma^0_2 formulas.
Recommended Citation
Jeffry L. Hirst and Carl Mummert. Reverse mathematics of matroids, In Computability and Complexity: Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday, Day, Fellows, Greenberg, Khoussainov, Melnikov, and Rosamond (Eds.), 2017, pp. 143–159. Preprint: http://arxiv.org/abs/1604.04912
Comments
This is the author’s manuscript of a chapter published in Computability and Complexity: Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday. The version of record is available at https://www.springer.com/gp/book/9783319500614.
Copyright © 2017 Springer International Publishing AG. All rights reserved.