|
|
The Divisibility Relation in Rings
Ketner, Michal ; Švejdar, Vítězslav (advisor) ; Honzík, Radek (referee)
This thesis aims to define a theory of divisibility for general integral domains. A hiear- chy of divisibility domains with properties to those of division on the integers is outlined. Chinese residue theorem is generalized by means of ideals in order to demonstrate wea- kening of generalization, that provides more effective tools. The thesis is prepared for all those interested in mathematics who want to get an insight into the theory of divisibility, so we build the theory from the beginning and compare it with division on integers. 1
|
|
|
Monadic NP sets
Putzer, Martin ; Krajíček, Jan (advisor) ; Honzík, Radek (referee)
Generalised spectra, id est classes finitely axiomatisable in existential second-order logic restricted to finite structures, are known by Fagin's theorem to coincide with members of the complexity class NP. Thereby, the problem of NP being closed under complementation reduces to the problem whether every class of finite struc- tures complementary to a generalised spectrum is, too, a generalised spectrum. Provided P ̸= NP, a proof thereof could then possibly be based on finding a par- ticular generalised spectrum (thereby an NP class) whose complement, while in coNP would not be in NP. Pursuits of such a proof, too, however, have been to no avail. A partial resolution of this problem (itself a special case to so called Asser's problem) is Fagin-Hájek theorem, claiming that a subclass of NP, the class of so called monadic NP sets is not closed under complementation. Reproduc- ing Fagin's original proof of the theorem is the aim of this thesis, along with introducing the reader to all preliminary apparatus needed for the proof. 1
|
|
|
Schönhage-Strassen algorithm and the mathematics behind it
Jelínková, Valentina ; Švejdar, Vítězslav (advisor) ; Honzík, Radek (referee)
Thesis name: Schönhage-Strassen algorithm and the mathematics behind it Author: Valentina Jelínková Department: Katedra Logiky Supervisor: Doc. RNDr. Vítězslav Švejdar, CSc Abstrakt: This thesis deals with the Schönhage-Strassen algorithm for mul- tiplying large integers with complexity O(n log n log log n). It contains the necessary theoretical foundations for describing and understanding the algo- rithm and its complexity. A significant attention is devoted to the Discrete Fourier Transform in complex and modular arithmetic, with two different interpretations of the FFT algorithm. Keywords: rings, polynomials, modul arithmetic, Fourier transform 1
|
|
|
The constructive universe L
Ketner, Michal ; Honzík, Radek (advisor) ; Přenosil, Adam (referee)
The theme explores the universe of constructive set L as it was defined by Godel. The work compares two methods of construction L set: one through the formalization of satisfaction relationand the other one with several (finitely many) called rudimentary functions that generate L. The work continues with verification of the implications Con(ZF)→Con(ZFC + CH). The goal is to give a comprehensive view of the construction L and verification of 's relative consistency CH. Powered by TCPDF (www.tcpdf.org)
|
|
|
The continuum function on singular cardinals
Stejskalová, Šárka ; Honzík, Radek (advisor) ; Verner, Jonathan (referee)
Bachelor thesis studies the behaviour of the continuum function on singular cardinals in theory ZFC. The work is divided into two parts. The focus of the first part is on the Silver's Theorem and it analyzes two different proofs of this Theorem, Silver's original proof and the second, purely combinatorial, proof by Baumgartner and Prikry. The second part is devoted to the Singular Cardinal Hypothesis, which influences the behaviour of the continuum function. In the thesis it is shown that, in the presence of large cardinals, Singular Cardinal Hypothesis is not provable in ZFC. Using Easton and Prikry forcing a model is found where the Singular Cardinal Hypothesis does not hold.
|
|
|
Tree property at more cardinals
Stejskalová, Šárka ; Honzík, Radek (advisor) ; Zdomskyy, Lyubomyr (referee)
In this thesis we study the Aronszajn and special Aronszajn trees, their existence and nonexistence. We introduce the most common definition of special Aronszajn tree and some of its generalizations and we examine the relations between them. Next we study the notions of the tree property and the weak tree property at a given regular cardinal κ. The tree property means that there are no Aronszajn trees at κ and the weak tree property means that there are no special Aronszajn trees at κ. We define and compare two forcings, the Mitchell forcing and the Grigorieff forcing, and we use them to obtain a model in which the (weak) tree property holds at a given cardinal. At the end, we show how to use the Mitchell forcing to construct a model in which the (weak) tree property holds at more than one cardinal. 1
|
|
|
The continuum function on regular cardinals in the presence of large cardinals
Blicha, Martin ; Honzík, Radek (advisor) ; Verner, Jonathan (referee)
This thesis examines the interactions between the continuum function and large cardinals. It is know, by a result of Easton, that the continuum function on regular cardinals has great freedom in ZFC. However, large cardinals lay additional constraints to possible behaviour of the continuum function. We focus on weakly compact and measurable cardinal to point out the differences in interactions with the continuum function between various types of large cardinals. We also study the case of indescribable cardinals for the comparison, and the results lead us to conclude that it is not easy to pinpoint the reason for these differences. 1
|
|
|
The tree property and the continuum function
Stejskalová, Šárka ; Honzík, Radek (advisor) ; Cummings, James (referee) ; Brooke-Taylor, Andrew (referee)
The continuum function is a function which maps every infinite cardinal κ to 2κ. We say that a regular uncountable cardinal κ has the tree property if every κ-tree has a cofinal branch, or equivalently if there are no κ-Aronszajn trees. We say that a regular uncountable cardinal κ has the weak tree property if there are no special κ-Aronszajn trees. It is known that the tree property, and the weak tree property, have the following non-trivial effect on the continuum function: (∗) If the (weak) tree property holds at κ++, then 2κ ≥ κ++. In this thesis we show several results which suggest that (∗) is the only restriction which the tree property and the weak tree property put on the continuum function in addition to the usual restrictions provable in ZFC (monotonicity and the fact that the cofinality of 2κ must be greater than κ; let us denote these conditions by (∗∗)). First we show that the tree property at ℵ2n for every 1 ≤ n < ω, and the weak tree property at ℵn for 2 ≤ n < ω, does not restrict the continuum function below ℵω more than is required by (∗), i.e. every behaviour of the continuum function below ℵω which satisfies the conditions (∗) and (∗∗) is realisable in some generic extension. We use infinitely many weakly compact cardinals (for the tree property) and infinitely many Mahlo...
|
|
|
The tree property and the continuum function
Stejskalová, Šárka ; Honzík, Radek (advisor) ; Cummings, James (referee) ; Brooke-Taylor, Andrew (referee)
The continuum function is a function which maps every infinite cardinal κ to 2κ. We say that a regular uncountable cardinal κ has the tree property if every κ-tree has a cofinal branch, or equivalently if there are no κ-Aronszajn trees. We say that a regular uncountable cardinal κ has the weak tree property if there are no special κ-Aronszajn trees. It is known that the tree property, and the weak tree property, have the following non-trivial effect on the continuum function: (∗) If the (weak) tree property holds at κ++, then 2κ ≥ κ++. In this thesis we show several results which suggest that (∗) is the only restriction which the tree property and the weak tree property put on the continuum function in addition to the usual restrictions provable in ZFC (monotonicity and the fact that the cofinality of 2κ must be greater than κ; let us denote these conditions by (∗∗)). First we show that the tree property at ℵ2n for every 1 ≤ n < ω, and the weak tree property at ℵn for 2 ≤ n < ω, does not restrict the continuum function below ℵω more than is required by (∗), i.e. every behaviour of the continuum function below ℵω which satisfies the conditions (∗) and (∗∗) is realisable in some generic extension. We use infinitely many weakly compact cardinals (for the tree property) and infinitely many Mahlo...
|
|
|
Reflection principles and large cardinals
Mrva, Mikuláš ; Honzík, Radek (advisor) ; Verner, Jonathan (referee)
This thesis aims to examine relations between so called "Reflection Princi- ples" and Large cardinals. Lévy has shown that Reflection Theorem is a sound theorem of ZFC and it is equivalent to Replacement Scheme and the Axiom of Infinity. From this point of view, Reflection theorem can be seen a specific version of an Axiom of Infinity. This paper aims to examine the Reflection Principle and its generalisations with respect to existence of Large Cardinals. This thesis will establish Inaccessible, Mahlo and Indescribable cardinals and their definition via reflection. A natural limit of Large Cardi- nals obtained via reflection are cardinals inconsistent with L. The thesis will offer an intuitive explanation of why this is the case. 1
|
guest ::
RSS feed.