|
|
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
|
|
|
The notion of interpretation between axiomatic theories
Štefanišin, Jan ; Švejdar, Vítězslav (advisor) ; Haniková, Zuzana (referee)
Thesis: The Notion of Interpretation between Axiomatic Theories Author: Jan Štefanišin Abstract: In this thesis we are researching the concept of intepretability between axiomatic theories and its basic properties and its uses. We define one-dimensional interpretation and show its behaviour on simple school theories. We also prove some important theorems about interpretations. In next two chapters we show interpretations on more complex theories. We use interpretations for transporting property of essential undecidability to theories in which theory R is interpretable. Then we show that theory of bounded arithmetic I∆0 is localy interpretable in Robinson arithmetic Q, which is also an example of cut-interpretation and is related to Edward Nelson's finitist program which we will comment on. Finally we return to school theories and use them to show how to prove that one theory is not interpretable in another. Keywords: interpretation, axiomatic theory, interpretability, definable sets, Ro- binson arithmetic
|
|
|
The notion of interpretation between axiomatic theories
Štefanišin, Jan ; Švejdar, Vítězslav (advisor) ; Haniková, Zuzana (referee)
In this thesis we are researching the concept of intepretability between axiomatic theories and its basic properties, its use and variants. We define one- dimensional interpretation and show its behaviour on simple school theories. Then we define multi-dimensional interpetation and piecewise interpretation and use them to make structure of degree of interpretability, in particular Double Degrees structure. We use one-dimensional interpretations for transporting property of essential undecidability to theories in which theory R is interpretable. Finally we show that theory of bounded arithmetic I∆0 is loccaly interpretable in Robinson arithmetic Q, which is also an example of cut-interpretation and is related to Edward Nelson's finitist program which we will comment on. Keywords: interpretation, axiomatic theory, interpretability, definable sets, Ro- binson arithmetic
|
|
|
Elementary axiomatic theories over intuitionistic logic
Heřmanová, Barbora ; Švejdar, Vítězslav (advisor) ; Ferenz, Nicholas (referee)
This thesis studies basic properties of intuitionistic logic and several elementary theories over it. We choose three theories to explore: the theory of equality, the theory of linear order, and the theory of apartness. We do not work with the last theory in classical logic and we will study it in connection with the other two theories, especially in relation to conservativity. This thesis draws mainly from the results of Dirk van Dalen, Richard Statman, and Craig Smorynski. Keywords: intuitionistic logic, elementary theories, apartness, conservativity
|
|
|
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 Divisibility Relation in Rings
Ketner, Michal ; Švejdar, Vítězslav (advisor) ; Arazim, Pavel (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
|
|
| |
|
|
Intuitionistic logic and axiomatic theories
Brablec, Vladimír ; Švejdar, Vítězslav (advisor) ; Jeřábek, Emil (referee)
This thesis explores some properties of elementary intuitionistic theories. We focus on the following theories: the theory of equality, linear order, dense linear order, the theory of a successor function, Robinson arithmetic and the theory of rational numbers with addition; moreover, we usually deal with two dierent formulations of the theories. As for the properties, our main interest is in the following four: coincidence with the classical version of a theory, saturation, De Jongh's theorem and decidability. The thesis draws especially from the results of C. Smorynski and D. de Jongh and tries to develop them. Some results known for Heyting arithmetic are proved for other theories. We also try to answer the question of what is the eect of replacing an axiom by a dierent (classically equivalent) axiom, or which properties a \good" intuitionistic theory should have.
|
|
|
Explicit fixed-points in provability logic
Chvalovský, Karel ; Švejdar, Vítězslav (advisor) ; Bílková, Marta (referee)
The aim of this diploma thesis is to discuss the explicit calculations of xed-points in provability logic GL. The xed-point theorem reads: For every modal formula A(p) such that each occurrence of p is under the scope of ¤, there is a formula D containing only sentence letters contained in A(p), not containing the sentence letter p, such that GL proves D ' A(D). Moreover, D is unique up to the provable equivalence. Firstly, we establish some special cases of the theorem and then we will look more closely at the full theorem. We show one semantic and two syntactic full xed-point constructions and prove their correctness. We also discuss some complexity aspects connected with the constructions and present basic upper bounds on length and modal depth of the constructed xed-points.
|
|
|
Machine-Free Characterization of Polynomially Computable Functions
Profeld, Michal ; Švejdar, Vítězslav (advisor) ; Verner, Jonathan (referee)
This work is focused into constructing mathematical structure. This structure is closed under it's operations. Structure was developed to contain all functions of certain growth rate. To be More specific functi- ons with polynomial growth rate. We can say that our structure con- tains all functions that have growth rate slower or equal to polynomial growth rate and no other function. Development of our structure was influenced mostly by work of Samuel R. Buss [1] 1
|
guest ::
