Název: Některé otázky definovatelnosti
Překlad názvu: Some questions of definability
Autoři: Lechner, Jiří ; Stanovský, David (vedoucí práce) ; Kepka, Tomáš (oponent)
Typ dokumentu: Diplomové práce
Rok: 2012
Jazyk: cze
Abstrakt: [cze] [eng]
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. We focus on first-order definability in the quasiordered class of finite digraphs ordered by embeddability. At first we will prove definability of each digraph up to size three. We will need to add to the quasiorder structure some digraphs as constants, so we try to find the needed set of constants as small as possible with small digraph as well. Gradually we make instruments that we can use to express the inner structure of each digraphs in the language of embeddability. At the end we investigate definability in the closely related lattice of universal classes of digraphs. We show that the set of finitely generated and also the set of finitely axiomatizable universal classes are definable subsets of the lattice.
Klíčová slova: definovatelnost; konečné orientované grafy; definability; finite digraphs

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/49622

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-498450


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Diplomové práce