Original title:
Kombinatorika matematických struktur
Translated title:
Kombinatorika matematických struktur
Authors:
Paták, Pavel ; Krajíček, Jan (advisor) ; Thapen, Neil (referee) Document type: Master’s theses
Year:
2010
Language:
eng Abstract:
[eng][cze] 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.Kombinatorika matematické struktury prvního řádu je třída všech formulí, které platí ve všech strukturách v ní definovatelných. Tento pojem poprvé zavedl Krajíček v [6]. V předložené práci se zabýváme charakterizací a srovnáním kombinatorik známých matematických struktur (reálná a komplexní čísla, husté lineární uspořádání, ...). Dále se věnujeme otázce výpočetní složitosti, tj. otázce, jak těžké je zjistit, zda daná formule leží v kombinatorice dané struktury. Dokážeme, že v případě modelů úplných teorií bez vlastnosti striktního uspořádání (SOP) či v případě pseudokonečných struktur je tento problém korekurzivně spočetně úplný a tudíž algoritmicky neřešitelný.
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/34475