Reverse mathematics of matroids

DOI10.1007/978-3-319-50062-1_12MaRDI QIDQ2970956zbMATH OpenOpenAlexFDO

Authors Jeffry L. Hirst, Carl Mummert

Publication date 4 April 2017

Published in Computability and Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1604.04912

zbMATH Keywords

connected componentgraphinductionmatroidreverse mathematics

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Second- and higher-order arithmetic and fragments (03F35) Combinatorial aspects of matroids and geometric lattices (05B35)

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 $Sigm{a}_2^0$ formulas.

Recommendations

• scientific article; zbMATH DE number 4112602
• scientific article; zbMATH DE number 3878912
• Subspaces of computable vector spaces
• Computable reductions and reverse mathematics
• scientific article; zbMATH DE number 3924748

Cites work

• Abstract dependence, recursion theory, and the lattice of recursively enumerable filters
• Addendum to ``Countable algebra and set existence axioms
• Closed choice and a uniform low basis theorem
• Connected components of graphs and reverse mathematics
• Countable algebra and set existence axioms
• Effective Choice and Boundedness Principles in Computable Analysis
• scientific article; zbMATH DE number 3833946 (Why is no real title available?)
• Independence in computable algebra
• On the Abstract Properties of Linear Dependence
• On the existence of a connected component of a graph
• On uniform relationships between combinatorial problems
• Recursion theory on fields and abstract dependence
• Recursively enumerable vector spaces
• Weihrauch degrees, omniscience principles and weak computability

Cited in

(6)

• Comparing representations for function spaces in computable analysis
• scientific article; zbMATH DE number 3878912 (Why is no real title available?)
• scientific article; zbMATH DE number 1187507 (Why is no real title available?)
• scientific article; zbMATH DE number 1822248 (Why is no real title available?)
• Weihrauch Complexity in Computable Analysis
• Foundations of online structure theory. II: The operator approach

This page was built for publication: Reverse mathematics of matroids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2970956)