The missing axiom conjecture for matroid representability in MSOL
The missing axiom conjecture for matroid representability in MSOL
Let a finite matroid be a finite set equipped with a rank function
Let MSOL denote monadic second-order logic for matroids, whose structures use finite ground sets, subsets, cardinalities, and rank functions. Missing axiom conjecture. There is no finite set of sentences, , in MSOL such that is a representable matroid if and only if it satisfies the rank axioms and every sentence in . This formalizes the claim that representability cannot be finitely axiomatized in MSOL. The paper proves finite axiomatizability for representability over fixed finite fields conditional on Rota's conjecture, while proving non-finite-axiomatizability over any fixed infinite field within the relevant framework; the general representability conjecture remains open.
Sources & referencesView supporting material
Primary source
Dillon Mayhew, Mike Newman and Geoff Whittle, “Is the missing axiom of matroid theory lost forever?”, arXiv:1204.3365 (2016).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.