On Extending Closure Systems to Matroids

AbstractGeometric representations of data are of main interest in data analysis. Generalizing the idea of linear representations this paper is concerned with the representability of data by matroids which leads to the problem of extending closure systems to matroids. Finite matroid constructions are introduced in order to characterize the class of set systems which can be extended to the set of hyperplanes of a matroid. Since this constructive characterization of extendable set systems does not give simple conditions for extendability, the question arises of whether such simple conditions actually exist. By means of an infinite series of critical configurations and Łoś’s theorem from model theory it is proven that there is no finite set of first-order axioms characterizing the class of set systems that admit a matroid construction. These results are discussed and perspectives for further research are given