Seminar

Research Seminar of the Department of Logic

05/14/2018

Is there a difference in gaps between convergence and divergence in ZFC and PA?

Peter Vojtáš, Department of Software Engineering, MFF UK


12/18/2017

(Homotopy) Type theory II.
Tomáš Lávička, Department of Logic, FF UK

Type theory is a possible alternative to set theory and first order predicate logic as a tool for mathematical foundations, which has recently been getting more and more attention especially due to the discovery of its close relation to algebraic topology. I will try to give an introductory  lecture to the basic concepts of type theory  and its formalism (not requiring any previous knowledge in the field) in such a way that we could get some idea on how one can do (not only constructive) mathematics with its framework. Along the way I will be suggesting where is the famous connection with algebraic topology coming from.  

Keywords: Types, identity types, dependent types, Univalence, constructive mathematics.

12/11/2017

(Homotopy) Type theory

Tomáš Lávička, Department of Logic, FF UK

Type theory is a possible alternative to set theory and first order predicate logic as a tool for mathematical foundations, which has recently been getting more and more attention especially due to the discovery of its close relation to algebraic topology. I will try to give an introductory  lecture to the basic concepts of type theory  and its formalism (not requiring any previous knowledge in the field) in such a way that we could get some idea on how one can do (not only constructive) mathematics with its framework. Along the way I will be suggesting where is the famous connection with algebraic topology coming from.  

Keywords: Types, identity types, dependent types, Univalence, constructive mathematics. 

11/27/2017

Definability of stationary subsets of $\omega_1$

Stefan Hoffelner, Department of Logic, FF UK


​​​​​​​

11/20/2017

Prediction principles in set theory: It's OK to guess

Miha Habić, Department of Logic, FF UK

Diagonalization arguments play a central role in logic and specifically set theory, reaching from Cantor's proof of the uncountability of the reals to complicated forcing arguments. Guessing principles provide a substitute in cases where there are too many objects to diagonalize against in a naive way. They work by providing small approximations to the objects and guaranteeing that the approximations are correct "often enough". In the talk I shall give a short introduction to some simple guessing principles, after which I shall examine joint guessing principles, which allow us to guess many objects at once.  

10/16/2017

The rearrangement number

William Brian, University of North Carolina at Charlotte, USA

Recall the classical result of Riemann that every conditionally convergent series can be rearranged to get a series which is divergent to infinity, oscillates or converges to an arbitrary real number. A natural question to ask is how many rearrangements are needed to witness the validity of this theorem. This leads to the definition of the rearrangement number which is a cardinal invariant of the continuum. We present recent results related to this number. The talk is based on the preprint by several authors including the speaker. 

12/19/2016

Nestandardní metody v konstrukci modelů slabých aritmetik
Jana Glivická

Představím novou metodu konstrukce modelů slabých aritmetik. Použijeme nestandardních metod ke konstrukci jisté elementární extenze standardního modelu aritmetiky, která je uzavřena na operaci *. Tento fakt nám umožní definovat na univerzu této extenze tzv. gradované verze aritmetických operací sčítání a násobení. Ukážeme, jak volbou různých gradací můžeme ovlivňovat platnost některých aritmetických tvrzení ve vzniklých strukturách. Speciálně předvedeme, jak lze touto metodou získat model Robinsonovy aritmetiky, v němž platí hypotéza prvočíselných dvojčat.

12/12/2016

Birkhoff's subdirect representation from a broader perspective

Tomáš Lávička

It is well known that varieties (resp.. quasi-varieties) are generated by its (relatively) subdirectly irreducible members (Birkhoff's representation). As we will see this representation theorem will not hold in general in the setting of generalized quasi-varieties (classes of algebras described by quasi-equations with countably many premises). I will present some characterization results of Birhoff's representability, which I then use to prove that the proper generalized quasi-variety generated by the [0,1] Lukasiewicz chain is representable in the above sense - the core idea of the proof uses a modification of the well-known topological proof of compactness for classical logic into higher cardinalities.

12/05/2016

Gentzen's cut elimination strategy and Tait's cut elimination strategy in propositional sequent calculus
Anna Horská

Nowadays, we usually eliminate cuts by decreasing the cut-rank of the derivation (Tait's strategy). That is, a cut with the greatest complexity is chosen such that there are only smaller cuts above it and this one is then decomposed into smaller cuts. Gentzen applies another strategy in his article of 1935. He eliminates the highest cuts, i.e., cuts that there are no other cuts above them. Hence, this procedure does not pay attention to the complexity of the chosen cut. The main property of cut elimination that we are interested in is the growth of the height of the derivation during the elimination, especially we want to know the height of the cut-free derivation. I want to show that both strategies mentioned above give us the same cut-free derivation in propositional logic. Not only is the height of the cut-free derivations the same, but they also have the same structure. I will define a procedure for eliminating a single cut (according to Buss) which makes global changes to the derivation. Then, I use Church-Rosser property to obtain that cut-free derivations are the same, when the only difference during the elimination is the way we choose the next cut to eliminate.

11/28/2016

Interpolants in the context of software verification
Martin Blicha

In the first part we present the role of interpolants in some verification algorithms to demonstrate the usefulness of the concept and the motivation for our work. In the second part we examine interpolation systems for propositional logic (the algorithms for computation of interpolants from a refutation proof), namely symmetric system (Pudlák, Krajíček), McMillan's system, and their generalization, framework of Labeled Interpolation Systems (D'Silva et al.). We conclude with incorporating partial variable assignment into the computation of interpolant, done in the framework of Labeled Partial Assignment Interpolation Systems (Jančík et al.).

10/31/2016

Nestovaný sekventový kalkulus pro intuicionistickou logiku
Eva Kolovratníková

Nejprve představíme nestovaný kalkulus pro intuicionistickou logiku a vysvětlíme, jak funguje nestování. Pak přidáme pravidla pro kvantifikátory a získáme kalkulus pro intuicionistickou predikátovou logiku s konstantním univerzem. Následně přidáme omezení, abychom získali kalkulus pro standardní intuicionistickou predikátovou logiku. Na závěr si předvedeme prefixová tabla pro obě varianty intuicionistické logiky a ukážeme, jak transformovat tabla do nestovaných sequentů. (English version of abstract) Firstly, we introduce nested sequent calculus for intuitionistic logics and show how the nesting works. Secondly, we show that standard quantification rules lead to calculus for intuitionistic predicate logic with constant domains. Then we add some restrictions to obtain calculus for standard Intuitionistic predicate logic. Finally, we introduce prefixed tableaux for both variants of Intuitionistic logic and show how we can transform tableaux to nested sequents.

10/10/2016

Vopěnkův princip a Vopěnkovy kardinály
Radek Honzík
Vopěnkův princip formuloval Petr Vopěnka a zní takto: Je-li A vlastní třída struktur v daném (množinovém) jazyce, pak existují dvě struktury M a N v A, že M je elementárně vnořitelná do N. Petr Vopěnka navrhl tento princip spíše s představou, že se brzy ukáže jako sporný, nicméně se tak nestalo. Ukážeme, že konzistentní síla tohoto tvrzení je velmi velká; v hierarchii velkých kardinálů se tento princip nachází mezi nejsilnějšími kardinály (např. implikuje konzistenci superkompatních kardinálů). Pozn. Podle obecenstva bude přednáška buď v češtině nebo angličtině.

04/25/2016

Fermat's last theorem and Catalan's conjecture in arithmetics with weak exponentiation
Petr Glivický

Wiles's proof of Fermat's Last Theorem (FLT) has stimulated a lively discussion on how much is actually needed for the proof. Despite the fact that the original proof uses set-theoretical assumptions unprovable in Zermelo-Fraenkel set theory with axiom of choice (ZFC) - namely, the existence of Grothendieck universes - it is widely believed that "certainly much less than ZFC is used in principle, probably nothing beyond Peano arithmetic, and perhaps much less than that." (McLarty) In this talk, I will present a joint work with V. Kala. We studied (un)provabiliy of FLT and Catalan's conjecture in arithmetical theories with weak exponentiation, i.e. in theories in the language  $L=(0,1,+,\cdot,exp,<)$ where the $(0,1,+,\cdot,<)$-fragment is usually very strong (often even the complete theory $\mbox{Th}(\mathbb N)$ of natural numbers in that language) but the exponentiation satisfies only basic arithmetical properties and not much of induction. In such theories, Diophantine problems such as FLT or Catalan's conjecture, are formalized using the exponentiation exp instead of the exponentiation definable in the $(0,1,+,\cdot,<)$-fragment. I will present a natural basic set of axioms Exp for exponentiation (consisting mostly of elementary identities) and show that the theory $T=\mbox{Th}(\mathbb N)+Exp$ is strong enough to prove Catalan's conjecture, while FLT is still unprovable in $T$. This gives an interesting separation of strengths of the two famous Diophantine problems. Nevertheless, I show that by adding just one more axiom for exponentiation (the, so called, "coprimality" of exp) the theory becomes strong enough to prove FLT, i.e. FLT is provable in T+"coprimality". (Of course, in the proof of this, we use the Wiles's result too.)