Kombinatorika matematických struktur

The combinatorics of a first order mathematical structure is the class of all formulas valid in all in it definable structures. This notion was first introduced by Krajíček in [6]. In the present work we try to characterize and compare the combinatorics of several different prominent structures (reals, complex number, dense linear order, . . . ). We also study the question of algorithmical complexity, i.e. the question how hard it is to check whether a given formula lies in the combinatorics of a given structure. We prove that this question is corecursively enumeratively complete and therefore algorithmicaly undecidable in the case of models of complete theories without strict order property (SOP) and in the case of pseudofinite structures