Indefinibilidade da representabilidade de matroides em linguagens monádicas de segunda ordem

Abstract

In this work we shall present important results on matroid theory and mathematical logic, more specifically in finite model theory and undefinability discovered by D. Mayhew, M. Newman, and G. Whittle. We shall prove that some monadic second-order languages cannot define linear and algebraic matroid representability, the latter being an extension of the former and a contribution of the development of this thesis. We shall also present a class of matroids studied by T. Zaslavsky called gain matroids and a matroid construction called proper amalgam.