|
|
Intuitionistic logic as a useful tool
Vachková, Eva ; Švejdar, Vítězslav (advisor) ; Bílková, Marta (referee)
This work deals with intuitionistic logic and completness of Gentzen calculus with respect to its semantics. The completness proof uses saturated sequents. The language considered is at most countable. Furthermore, our work investigates one of the generalizations of intuitionistic logic, namely intuitionistic logic with constant domain, or Grzegorczyk's logic. We deal with Markov's principle and use it to prove that Gentzen calculus adapted to this logic is not cut-free complete with respect to Grzegorczyk's logic. Part of the work deals with Heyting algebras-one of the possible semantics of intuitionistic propositional logic. We show that the Rieger-Nishimura lattice is a Heyting algebra, too. For Heyting algebras, filters and prime filters are defined and used to obtain Kripke's frames. It is shown that the same formulas hold in these frames and in Heyting algebras.
|
|
|
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.
|
|
| |
|
|
Logic of provability from the philosophical point of view
Filippi, Jan ; Švejdar, Vítězslav (referee) ; Jirků, Petr (advisor)
The mathematical part of this thesis studies the phenomenon of self-reference in arithmetics. A higher programming language is used to present ideas and proofs, enabling us to reach the known results of Gödel, Rosser and Löb in a natural way. At the end of this part, we formulate another problem of a similar type and propose some ways to solve it. The philosophical part draws analogies between statements originating in the logic of provability and their application in humanities. We study the clash between determinism and existence of free will, and apply the theory of recursive functions to this issue.
|
|
|
Interpolation in modal logics
Bílková, Marta ; Pudlák, Pavel (advisor) ; Švejdar, Vítězslav (referee) ; Iemhoff, Rosalie (referee)
Since Craig's landmark result on interpolation for classical predicate logic, proved as the main technical lemma in [14], interpolation is considered one of the centra! concepts in pure logic. Various interpolation properties find their applications in computer science and have many deep purely logical consequences. We focus on two propositional versions of Craig interpolation property: Craig Interpolation Property: for every provable implication (A -+ B) there is an interpolant I containing only only common variables of A and B such that both implications (A -+ I) and (I-+ B) are provable. Craig interpolation, although it seems rather technical, is a deep logical property. It is dosely related to expressive power of a logic - as such it entails Beth's definability property, or forces functional completeness. It is also related to Robinson's joint consistency of two theories that agree on the common language. Craig interpolation has an important algebraic counterpart - it entails amalgamation or superamalgamation property of appropriate algebraic structures. In case of modal provability logics, Craig interpolation entails fixed point theorem. There are other interpolation properties, defined w.r.t. a consequence relation rather then w.r.t. a provable implication. In presence of deduction theorem the two...
|
|
|
Explicit fixed-points in provability logic
Chvalovský, Karel ; Bílková, Marta (referee) ; Švejdar, Vítězslav (advisor)
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.
|
|
|
Bisimulation
Arazim, Pavel ; Švejdar, Vítězslav (referee) ; Bílková, Marta (advisor)
This work is about bisimulation in modal logic as well as in intuicionistic logic without contraction. Bisimulation is a relation between models, which is weaker than isomorphism, yet still guarantees equivalence in the in the selected logic. It is typically used to demonstrate that some properties of models cannot be distinguished. For instance the cardinality cannot be distinguished, which is shown by disjunct union. Bisimulation also helps to clarify the relation between modal and classical logic. Apart from bisimulation, the related notion of bounded morphism is studied because it enables to elevate the unde- nability and undistinguishability to the discourse of frames. The part about modal logic is basically a compilation of well known facts, yet their interaction is made more clear and some proofs, which are usually disregarded as obvious, are presented in an explicit manner. Talking about the second part, mere reasonable de nition of the semantics is an honest work. Yet even here the bisimulation and bounded isomorphism are introduced and some examples are shown in order to illustrate their utility.
|
|
|
Some semantic methods in intuitionistic logic
Bergmannová, Pavla ; Švejdar, Vítězslav (advisor)
V práci se podíváme do světa intuicionistické logiky. Zjistíme že v intuicionistické logice nelze definovat logické spojky pomocí jiných logických spojek. Podíváme se, jak je to v intuicionistické logice s jednoatomovými formulemi, ukážeme, že je můžeme vyčerpávajícím způsobem zorganizovat. Také se budeme věnovat kripkovským modelům a uvidíme, že v některých případech lze vydatně zredukovat nosnou množinu kripkovského modelu. Předložíme nástroje, pomocí kterých poznáme, které prvky jsou v modelu jaksi "navíc" a tudíž je můžeme z modelu "vyškrtnout". Na závěr se soustředíme na jednoatomové modely a na to, jak to vypadá s jejich složitostí, když je maximálně redukujeme. V práci je využito toho, že lze písmem rozlišit dvě implikace ---+ a ~- První z nich je používána jako implikace v rámci diskutovaných formulí, druhá jako prvek metajazyka, kterým si povídáme o této problematice. Při důkazech tvrzení o intuicionistické logice se řídíme pravidly klasické logiky. Písmena A, B, C, ... a z, cp, lf/, . . . představují formule, písmena p, q představují atomy.
|
|
|
The undecidability of the field of rationals
Jurenka, David ; Krajíček, Jan (referee) ; Švejdar, Vítězslav (advisor)
Otázka rozhodnutelnosti, tj. otázka, zda existuje algoritmus, který by byl schopen rozhodnout o platnosti každé prvořádové predikátové formule, se dostala na výsluní pozornosti matematiků ve dvacátých letech minulého století. Spolu s ní byla zkoumána i rozhodnutelnost druhořádových formulí a obecně jakéhokoli matematického tvrzení. Souhrnně byly tyto otázky označovány jako Hilbertův Entscheidungsproblem a ještě roku 1930 Hilbert věřil v jejich kladné řešení. Roku 1936 však Alonzo Church ukázal, že samotná predikátová logika prvního řádu je nerozhodnutelná, a téhož roku pak Alan Turing představil dnes již klasický nerozhodnutelný problém, problém zastavení. Oba při tom ve svých pracech využili myšlenek, které formuloval Kurt Godel ve svém důkazu neúplnosti aritmetiky. V otázce rozhodnutelnosti základních aritmetických struktur přinesl první významný výsledek Mojzesz Presburger, který roku 1929 dokázal rozhodnutelnost přirozených čísel s operací sčítání a konstantami O a 1. Nicméně hned následujícího roku vyplynulo z Godelových výsledků, že tatáž struktura včetně operace násobení již rozhodnutelná být nemůže. Tím byla zároveň vyřešena i otázka rozhodnutelnosti čísel celých, neboť pojem přirozeného čísla je v této struktuře definovatelný (viz kapitolu 4.2), a tak je možno v celých číslech reformulovat každou...
|
|
|
The undecidability of the field of rationals
Jurenka, David ; Švejdar, Vítězslav (advisor) ; Krajíček, Jan (referee)
Otázka rozhodnutelnosti, tj. otázka, zda existuje algoritmus, který by byl schopen rozhodnout o platnosti každé prvořádové predikátové formule, se dostala na výsluní pozornosti matematiků ve dvacátých letech minulého století. Spolu s ní byla zkoumána i rozhodnutelnost druhořádových formulí a obecně jakéhokoli matematického tvrzení. Souhrnně byly tyto otázky označovány jako Hilbertův Entscheidungsproblem a ještě roku 1930 Hilbert věřil v jejich kladné řešení. Roku 1936 však Alonzo Church ukázal, že samotná predikátová logika prvního řádu je nerozhodnutelná, a téhož roku pak Alan Turing představil dnes již klasický nerozhodnutelný problém, problém zastavení. Oba při tom ve svých pracech využili myšlenek, které formuloval Kurt Godel ve svém důkazu neúplnosti aritmetiky. V otázce rozhodnutelnosti základních aritmetických struktur přinesl první významný výsledek Mojzesz Presburger, který roku 1929 dokázal rozhodnutelnost přirozených čísel s operací sčítání a konstantami O a 1. Nicméně hned následujícího roku vyplynulo z Godelových výsledků, že tatáž struktura včetně operace násobení již rozhodnutelná být nemůže. Tím byla zároveň vyřešena i otázka rozhodnutelnosti čísel celých, neboť pojem přirozeného čísla je v této struktuře definovatelný (viz kapitolu 4.2), a tak je možno v celých číslech reformulovat každou...
|
guest ::
