|
|
Dělitelnost v okruzích
Ketner, Michal ; Švejdar, Vítězslav (vedoucí práce) ; Honzík, Radek (oponent)
Práce si klade za cíl definovat teorii dělitelnosti pro obecné obory integrity a nastí- nit hierarchii oborů dělitelnosti s vlastnostmi, které očekáváme, že budou platit obdobně jako při dělení na celých číslech. Pomocí ideálů zobecňujeme Čínskou zbytkovou větu a na ní demonstrujeme, že se může vyplatit oslabit obecnost teorie, protože máme poté efektivnější nástroje, jak hledat řešení. Práce je zpracovaná pro všechny zájemce o mate- matiku, kteří chtějí nahlednout do teorie dělitelnosti, proto teorii budujeme od počátku a srovnáváme ji s dělením na celých číslech. 1
|
|
|
Monadic NP sets
Putzer, Martin ; Krajíček, Jan (vedoucí práce) ; Honzík, Radek (oponent)
Jako zobecněná spektra se označují třídy konečně axiomatisovatelné v existenční druhořádové logice s relací platnosti omezenou na konečné struktury. Jest známým faktem, že korrespondují dle Faginovy věty s prvky složitostní třídy NP. Prob- lém uzavřenosti NP na komplementaci se tedy redukuje na problém uzavřenosti zobecněných spekter na komplementaci. Důkaz P ̸= NP, za předpokladu, že ono tvrzení skutečně platí, by tak mohl spočívat v nalezení konkretního zobecněného spektra (a tedy třídy v NP), jehož doplněk, jsa arci v coNP, by nebyl prvkem NP. Hledání takového důkazu ovšem též nepřineslo úspěch. Částečné rozřešení tohoto problému (an sám je toliko speciálním příkladem obecnějšího tak zvaného prob- lému Asserova) přinesla Fagin-Hájkova věta, tvrdící, že jistá podtřída NP, třída tak zvaných monadických NP množin vskutku netvoří třídu uzavřenou na kom- plementaci. Reprodukce Faginova původního důkazu této věty, spolu s uvedením veškerého potřebného apparátu, je cílem této práce. 1
|
|
|
Schönhageho-Strassenův algoritmus a jeho matematické pozadí
Jelínková, Valentina ; Švejdar, Vítězslav (vedoucí práce) ; Honzík, Radek (oponent)
Název práce: Schönhageho-Strassenův algoritmus a jeho matematické pozadí Autor: Valentina Jelínková Katedra: Katedra Logiky Vedoucí: Doc. RNDr. Vítězslav Švejdar, CSc Abstrakt: Práce se zabývá Schönhageho-Strassenovým algoritmem, pro násobení velkých čísel se složitostí O(n log n log log n). Obsahuje nezbytné teoretické základy pro popis a pochopení algoritmu a jeho složitosti. Významný pro- stor je věnován Diskrétní Fourierově transformaci v komplexní a modulární aritmetice, se dvěmi různými interpretacemi algoritmu FFT. Klíčová slova: okruh, polynom, modulární aritmetika, Fourierova transfor- mace 1
|
|
|
Konstruktivní univerzum L
Ketner, Michal ; Honzík, Radek (vedoucí práce) ; Přenosil, Adam (oponent)
Tato práce zkoumá univerzum konstruktivních množin L, jak ho definoval Godel. Práce srovnává dva způsoby konstrukce L: jeden přes formalizaci relace splňovaní a druhý pomocí konečně mnoha tzv.rudimentárních funkcí, které L generují. Práce dále povede k ověření implikace Con(ZF)→Con(ZFC + CH). Práce má podat ucelený pohled na konstrukci L a ověření relativní konzistence CH. Powered by TCPDF (www.tcpdf.org)
|
|
|
The continuum function on singular cardinals
Stejskalová, Šárka ; Honzík, Radek (vedoucí práce) ; Verner, Jonathan (oponent)
Bakalářská práce se zabývá chováním funkce kontinua na singulárních kardinálech v teorii ZFC. Práce je rozdělena na dvě části. První část se soustředí na Silverovu větu a rozebírá dva různé důkazy této věty, původní Silverův a čistě kombinatorický důkaz dle Baumgartnera a Přikrého. Druhá část je věnována hypotéze singulárních kardinálů, která ovlivňuje chování funkce kontinua. V práci je ukázáno, za předpokladu velkých kardinálů, že hypotéza singulárních kardinálů je nedokazatelná nad teorií ZFC. Pomocí Eastonova a Přikrého forcingu je nalezen model ZFC, ve kterém hypotéza singulárních kardinálů neplatí.
|
|
|
Tree property at more cardinals
Stejskalová, Šárka ; Honzík, Radek (vedoucí práce) ; Zdomskyy, Lyubomyr (oponent)
V této práci se zabýváme Aronszajnovými a specialními Aronszajnovými stromy, je- jich existencí a neexistencí. Zavádíme dnes nejběžněji užívanou definici speciálního Aronszajnova stromu a několik zobecnění této definice a zkoumáme vztahy mezi nimi. Dále se věnujeme stromové a slabé stromové vlastnosti, což je tvrzení, že na daném regulárním kardinálu κ neexistuje žadný Aronszajnův strom, respek- tive žadný speciální Aronszajnův strom. Definujeme a srovnáváme dva forcingy, Mitchellův a Gregorieffův, a následně je použiváme k získání modelu, ve kterém máme (slabou) stromovou vlastnost na daném kardinálu. Nakonec ukážeme jak použít Mitchellův forcing ke konstrukci modelu, ve kterém máme (slabou) stro- movou vlastnost na více kardinálech. 1
|
|
|
The continuum function on regular cardinals in the presence of large cardinals
Blicha, Martin ; Honzík, Radek (vedoucí práce) ; Verner, Jonathan (oponent)
V této práci zkoumáme, jak na sebe vzájemně působí velké kardinály a funkce kontinua. Z Eastonova výsledku víme, že funkce kontinua na regulárních kardinálech má v ZFC velkou volnost. Avšak velké kardinály kladou na chování funkce kontinua další omezující podmínky. Vzájemné ovlivňování velkých kardinálů a funkce kontinua se liší pro jednotlivé typy velkých kardinálů. Abychom poukázali na tyto rozdíly, soustředíme se na slabě kompaktní a měřitelný kardinál. Pro srovná- ní také přezkoumáme nepopsatelné kardinály, na kterých ukážeme, že není snadné přesně určit důvod těchto rozdílů. 1
|
|
|
The tree property and the continuum function
Stejskalová, Šárka ; Honzík, Radek (vedoucí práce) ; Cummings, James (oponent) ; Brooke-Taylor, Andrew (oponent)
Funkce kontinua je funkce, která libovolnému nekonečnému kardinálu κ přiřadí hodnotu 2κ. Řekneme, že regulární nespočetný kardinál κ má stromovou vlastnost, jestliže každý κ-strom má kofinální větev, ekvivalentně, že neexistuje žádný κ-Aronszajnův strom. Obdobně definujeme, že regulární nespočetný kardinál κ má slabou stromovou vlastnost, jestliže neexistuje žádný speciální κ-Aronszajnův strom. Stromová vlastnost a slabá stromová vlastnost mají následující netriviální efekt na funkci kontinua: (*) Jestliže (slabá) stromová vlastnost platí na κ++, pak 2κ ≥ κ++. V této práci se věnujeme několika výsledkům, které naznačují, že (*) je jediná restrikce, kterou na funkci kontinua kladou stromová vlastnost a slabá stromová vlastnost kromě obvyklých restrikcí dokazatelných v ZFC (monotonie a tvrzení, že kofinalita 2κ musí být větší než κ; označme tyto restrikce (**)). Nejprve ukážeme, že stromová vlastnost na ℵ2n pro každé 1 ≤ n < ω a slabá stromová vlastnost na ℵn pro 2 ≤ n < ω neovlivňují funkci kontinua pod ℵω víc, než je dáno podmínkami (*) a (**), tedy že každé chování funkce kontinua pod ℵω, které splňuje podmínky (*) a (**), je realizovatelné v nějaké generické extenzi. Pro důkaz stromové...
|
|
|
The tree property and the continuum function
Stejskalová, Šárka ; Honzík, Radek (vedoucí práce) ; Cummings, James (oponent) ; Brooke-Taylor, Andrew (oponent)
Funkce kontinua je funkce, která libovolnému nekonečnému kardinálu κ přiřadí hodnotu 2κ. Řekneme, že regulární nespočetný kardinál κ má stromovou vlastnost, jestliže každý κ-strom má kofinální větev, ekvivalentně, že neexistuje žádný κ-Aronszajnův strom. Obdobně definujeme, že regulární nespočetný kardinál κ má slabou stromovou vlastnost, jestliže neexistuje žádný speciální κ-Aronszajnův strom. Stromová vlastnost a slabá stromová vlastnost mají následující netriviální efekt na funkci kontinua: (*) Jestliže (slabá) stromová vlastnost platí na κ++, pak 2κ ≥ κ++. V této práci se věnujeme několika výsledkům, které naznačují, že (*) je jediná restrikce, kterou na funkci kontinua kladou stromová vlastnost a slabá stromová vlastnost kromě obvyklých restrikcí dokazatelných v ZFC (monotonie a tvrzení, že kofinalita 2κ musí být větší než κ; označme tyto restrikce (**)). Nejprve ukážeme, že stromová vlastnost na ℵ2n pro každé 1 ≤ n < ω a slabá stromová vlastnost na ℵn pro 2 ≤ n < ω neovlivňují funkci kontinua pod ℵω víc, než je dáno podmínkami (*) a (**), tedy že každé chování funkce kontinua pod ℵω, které splňuje podmínky (*) a (**), je realizovatelné v nějaké generické extenzi. Pro důkaz stromové...
|
|
|
Reflection principles and large cardinals
Mrva, Mikuláš ; Honzík, Radek (vedoucí práce) ; Verner, Jonathan (oponent)
Práce zkoumá vztah tzv. principů reflexe a velkých kardinálů. Lévy ukázal, že v ZFC platí tzv. věta o reflexi a dokonce, že věta o reflexi je ekviva- lentní schématu nahrazení a axiomu nekonečna nad teorií ZFC bez axiomu nekonečna a schématu nahrazení. Tedy lze na větu o reflexi pohlížet jako na svého druhu axiom nekonečna. Práce zkoumá do jaké míry a jakým způsobem lze větu o reflexi zobecnit a jaký to má vliv na existenci tzv. velkých kardinálů. Práce definuje nedosažitelné, Mahlovy a nepopsatelné kardinály a ukáže, jak je lze zavést pomocí reflexe. Přirozenou limitou kardinálů získaných reflexí jsou kardinály nekonzistentní s L. Práce nabídne intuitivní zdůvodněn, proč tomu tak je. 1
|
host ::
RSS.