|
|
Některé otázky definovatelnosti
Lechner, Jiří ; Stanovský, David (vedoucí práce) ; Kepka, Tomáš (oponent)
Zaměříme se na prvořádovou definovatelnost v kvaziuspořádané třídě konečných orientovaných grafů uspořádané vnořitelností. Nejprve dokážeme definovatelnost každého grafu až do velikosti tři. Protože budeme muset k jazyku kvaziuspořádání přidat některé grafy jako konstanty, budeme se snažit najít nejmenší potřebnou množinu co možná nejmenších konstant. Postupně vybudujeme aparát, jehož prostřednictvím budeme schopni vyjádřit v jazyce vnořitelnosti vnitřní strukturu každého grafu. Nakonec vyšetříme některé aspekty definovatelnosti ve svazu univerzálních tříd orientovaných grafů. Ukážeme, že množina konečně generovaných a množina konečně axiomatizovatelných univerzálních tříd jsou definovatelné podmnožiny svazu.
|
|
|
Kombinatorika matematických struktur
Paták, Pavel
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 vlastností 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ý.
|
|
|
Některé otázky definovatelnosti
Lechner, Jiří ; Stanovský, David (vedoucí práce) ; Kepka, Tomáš (oponent)
Zaměříme se na prvořádovou definovatelnost v kvaziuspořádané třídě konečných orientovaných grafů uspořádané vnořitelností. Nejprve dokážeme definovatelnost každého grafu až do velikosti tři. Protože budeme muset k jazyku kvaziuspořádání přidat některé grafy jako konstanty, budeme se snažit najít nejmenší potřebnou množinu co možná nejmenších konstant. Postupně vybudujeme aparát, jehož prostřednictvím budeme schopni vyjádřit v jazyce vnořitelnosti vnitřní strukturu každého grafu. Nakonec vyšetříme některé aspekty definovatelnosti ve svazu univerzálních tříd orientovaných grafů. Ukážeme, že množina konečně generovaných a množina konečně axiomatizovatelných univerzálních tříd jsou definovatelné podmnožiny svazu.
|
|
|
Kombinatorika matematických struktur
Paták, Pavel
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 vlastností 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ý.
|
host ::
RSS.