Seminar

Place
Celetná 20, Room #116 (Department of Logic). Please write to radek.honzik at ff.cuni.cz if you wish to be on the mailing list.

Time
Monday, 16:40, according to the schedule below.

13.5.2024

Speaker: Wesley Fussner (Czech Academy of Sciences, Institute of Computer Science)

Title: Interpolation in basic fuzzy logics

Abstract:

Recent years have seen tremendous progress in developing a systematic understanding of interpolation properties in substructural logics, a diverse family of non-classical deductive systems descending from structural proof theory that include linear logic, relevant logics, superintuitionistic logics, and many others. Among other things, this wave of progress has seen the resolution of some long-standing open problems in the field. In this talk, we discuss one such old open problem and its solution. Namely, we provide a complete classification of the axiomatic extensions of Petr Hájek’s basic fuzzy logic with the (Craig, deductive) interpolation property. This solves a problem posed by Franco Montagna in 2006, asking whether there are uncountably many extensions of Hájek’s basic logic with interpolation. We will see from our classification that, in fact, there are only countably many. This is joint work with Simon Santschi.

29.4.2024

Speaker: David Roubinek (dep. of Logic, Bc student)

Title: Partition calculus in set theory

Abstract:

We will begin by introducing the arrow notation and stating both the finite and infinite versions of Ramsey’s theorem. We will then move to discussing possible generalizations for infinite cardinals above omega, with the main focus on omega_1,  omega_2 and aleph_omega. At the end we will mention some connections with other areas of set theory.

22.4.2024

Speaker: Igor Sedlar (Czech Academy of Sciences, Institute of Computer Science)

Title: A Logic of Probability Dynamics

Abstract:

We introduce a modal logic for reasoning about actions that affect the probability of events. Given a set of states S, we associate a finitely additive probability measure over an algebra E(S) of subsets of S (events) with each state in S. State transitions on S, interpreting actions, then represent changes in the probabilities of events in E(S). Effects of actions on probabilities of events can be formalized using a variant of the language of modal Łukasiewicz logic. Hence, we expand on the “static” framework of Hájek et al. [1,2] where only one probability measure is assumed and state transitions are not considered. We discuss several example scenarios and their fomalization. Our main technical result is that the validity problem of our logic is decidable. The proof builds on a reduction to local consequence in modal Łukasiewicz logic.

The talk is based on ongoing joint work with Chun-Yu Lin and Ondrej Majer.

References
[1] Petr Hájek, Lluı́s Godo, and Francesc Esteva. 1995. Fuzzy logic and probability. In UAI’95: Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence, Morgan Kaufmann, San Francisco, 237–244.
[2] Petr Hájek, Lluı́s Godo, and Francesc Esteva. 2000. Reasoning about probability using fuzzy logic. Neural Network World 10, 5 (2000), 811–824.

15.4.2024

Speaker: Vít Punčochář (FÚ AV ČR)

Title: Inquisitive Logic and Homotopy Type Theory (slides)

Abstract:

In my talk, I will present inquisitive logic and homotopy type theory as two different areas that have been developed completely separately. Inquisitive logic is a framework for a logical modelling of questions and homotopy type theory is a relatively new approach to the foundations of mathematics. I will sketch some preliminary ideas indicating that there might be an interesting connection between these two areas.

8.4.2024

Speaker: Jiri Rydl (dep. of Logic)

Title: Algebraic semantics for Multimodal logic (the topic of my master thesis, supervised by Igor Sedlar)

Abstract:

I will introduce and motivate a 2-sorted approach to algebraic semantics for multimodal logics, where the set of modalities has some algebraic structure. The central (starting) example is a so-called monoidal modal algebra (MA), a structure comprising a monoid A (of modalities) and an underlying boolean algebra X (of propositions). These two structures are related by a diamond-like operator, which induces a normal and additive function <a>: X \to X for every a \in A and behaves well w.r.t. monoidal multiplication and identity (so far, only unary modalities are treated, but it should not be problematic to extend the approach to arbitrary n-ary functions).In this sense, boolean algebras with operators (BAOs) can be seen as MAs by simply forgetting the monoidal structure on the set of modalities. I will define MAs, present some examples and formulate a representation theorem, in the line of Jonsson-Tarski representation theorem for BAOs.

The structure of monoids for modalities is by no means some privileged class, but rather a starting point in the formulation and study of the general 2-sorted approach. I will briefly mention the possibility of extending the language and structure of the algebra of modalities. Similarly, the underlying boolean algebras can be weakened to more general structures, but this is probably not yet on the horizon of research.

If time allows, I will mention a very different class of algebras, introduced originally with completely different motivations, which, however, may have some nice connections to MAs. These are monoids extended with an antidomain operation (antidomain monoids, AMs), whose intended interpretation is dynamic negation on binary relations. We do not yet have any precise connection between MAs and AMs, but I will give a few of Igor’s examples of AMs which suggest there may be some.

18.3.2024

Speaker: Max Lin (dep. of Logic)

Title: Finitely valued CPDL and related topics

Abstract:

Propositional dynamic logic, PDL, has been introduced as a logic of imperative computer programs, but it found many applications in formalizing reasoning about actions in general. Many-valued versions of PDL aim at formalizing reasoning about action in contexts where imprecise concepts are involved. Concurrent propositional dynamic logic (CPDL) either extends PDL with an operator representing parallel execution of two actions or redesigns PDL using π-calculus.  In this presentation, we outline a many-valued version of two CPDL. Our logic is based on propositional dynamic models where formulas and accessibility relations are both evaluated in finite Łukasiewicz chains. Our main technical result is a soundness and completeness theorem for the logic.

11.3.2024

Speaker: Šárka Stejskalová (dep. of Logic)

Title: Kurepa trees and forcing

Abstract:

We will discuss  omega_1-Kurepa trees, and start by giving some basic observations related to their existence and non-existence. In the second part we will discuss connections with forcing; we will focus on two (interrelated) aspects: (1) the indestructibility of the property that there are no Kurepa trees in certain models with respect to certain forcing notions, and (2) whether one can add an omega_1-Kurepa tree by a forcing of size omega_1.

26.2.2024

Speaker: Mgr. Štěpán Laichter (Logic)

Title: Leveraging Generative AI and LLMs in Logic Learning & Research (slides)

Abstract:

This talk aims to explore the potential of generative AI and Large Language Models (LLMs) within the field of logic. It will provide a foundational overview of generative AI technologies, highlighting both commercial and open-source tools beneficial for students and researchers in logic. The presentation will introduce strategies such as fine-tuning,  benchmarking, and context generation, alongside basic techniques for prompt engineering. We will also discuss the current limitations of generative AI and explore possibilities for future development. Attendees are encouraged to use this seminar as an opportunity to brainstorm applications of this technology in their own research areas and consider the ethical dimensions and practical challenges of integrating generative AI in logic research. (disclaimer: this abstract has been generated with a LLM).

4.12.2023

Speaker: Gerardo Zuloaga (Master student, dep. of Logic)

Title: Logical analysis of Fiction in the work of Jesús Maestro

Abstract:

Jesús G. Maestro is an important Spanish author, and his work mainly focuses on the analysis and criticism of literature. Published In 2017, Maestro’s book Critique of the Literary Reason proposes a rational and logical theory about literature. At the core of his theory is the notion of Fiction as it appears in literature. The goal of this talk is to analyse the arguments Maestro presents through this notion. In order to build this analysis, I will present the logical theory of argumentation proposed by Stephen Toulmin, and then I will explore all the reasons presented in Chapter 6 of the first volume of Maestro’s book for why fiction is important to literature. Following this I will conduct a formal analysis of Maestro’s notions, in which I will focus on the correctness of his arguments and proofs.

27.11.2023

Speaker: Corey Switzer (University of Vienna)

Title: Kaufmann Models: A Canonical Incompactness in the Theory of Arithmetic

Abstract:

A Kaufmann model is an $\omega_1$-like, recursively saturated, rather classless model of PA (or ZFC) (these concepts will be defined in the talk). Such models exhibit incompactness principles similar to an Aronszajn tree. For instance, if $M$ is Kaufmann, every countable elementary submodel carries a truth predicate while the model itself does not. Moreover their higher cardinal analogues are closely related to the tree property. A result of Schmerl shows that if there is a $\kappa$-Kaufmann model then the tree property fails on $\kappa$.

Kaufmann showed that there are Kaufmann models under the $\diamondsuit$ principle and Shelah eliminated this assumption via a forcing absouteness argument involving the strong logic $L_{\omega_1, \omega}(Q)$ where $Q$ is the quantifier “there exists uncountably many…”. A well known open problem of Hodges asks whether one can build a Kaufmann model “by hand”, without referring to forcing absoluteness or additional set thoeretic assumptions. In this talk we will discuss this problem as well as some recent attempts to answer it focusing on the role the strong logic $L_{\omega_1, \omega}(Q)$. In particular we will show that the axiomatizability of Kaufmann models in this logic is independent of ZFC.

20.11.2023

Speaker: Lukas Schembecker (University of Vienna)

Title: Preserving and constructing combinatorial families of reals with forcing (you can download slides here).

Abstract:
I will give a non-technical introduction on how to use forcing in the context of combinatorial set theory. Building on that, I will present recent work such as Sacks-indestructibility for various types of families and and how construct models with partitions of Baire space into compact sets of various sizes.

13.11.2023

Speaker: Moritz Kriegleder (University of Vienna)

Title: Minimal Models of Consciousness & the Free Energy Principle (you dan download slides here).

Abstract:

The scientific study of consciousness has always been an interdisciplinary effort combining theories and tools from many fields. Minimal models provide a shared framework for the systematic study of phenomena identifying common assumptions. With a plethora of consciousness models available, a critical analysis of overlaps and tensions becomes necessary to map out different approaches. In my talk, I present the free energy principle as a model of consciousness and discuss how it uses ideas from physics and information theory to explain consciousness. The free energy principle suggests that organisms strive to minimize the surprise of beliefs about external states, which can be seen as a foundational principle of self-organisation and adaptive behavior. I defend a pragmatic philosophy when it comes to our use of mathematical tools to model consciousness and discuss how free energy models fit in with current paradigms in the cognitive sciences.

6.11.2023

Speaker: Timotej Šujan (Master student, FF UK)

Title: Structure of self-referential paradoxes

Abstract:

It is an open question whether all relevant self-referential paradoxes share a uniform structure. In this talk, we will discuss Graham Priest’s proposal for such a uniform structure (called the Inclosure Scheme) and show some of the problems associated with it, as well as the difficulties one encounters when trying to avoid these problems.

23.10.2023

Speaker: Filip Jankovec (PhD student, MFF UK)

Title: Infinitary rules for abelian logic

Abstract:

In abelian logic the reduced models are lattice ordered abelian groups. We will focus on three prominent linear models of abelian logic: integers, rationals and reals. These three structures are indistinguishable using finitary rules, however they can be separated using infinitary rules. In this talk we will focus on finding these rules and we will discuss the properties of the corresponding generalized quasivarities.

16.10.2023

Speaker: John Krueger (UNT) [CANCELLED due to travel problems]

Title: Suslin’s hypothesis and Aronszajn trees

You can download the slides John prepared for the talk here.

Abstract: In this talk we will discuss the history of the Suslin problem in set theory and related topics in the theory of trees. We begin with the origin of the Suslin problem in the context of the real number line, its effect on the development of the subject of trees by Kurepa and others, and its eventual solution with the invention of forcing. We then discuss the related topic of special Aronszajn trees, its connection with the emergence of forcing axioms such as Martin’s axiom, and characterizations of being special in terms of trees of one-to-one functions given by Baumgartner, and later by Honzik and Stejskalova.

9.10.2023

Speaker: Radek Honzik

Title: On the Rabin-Keisler theorem

Abstract: We review and discuss the Rabin-Keisler theorem which states that there exists a first-order theory T with language of size 2^omega which has a countable model and every other model has size at least 2^omega. This shows that the Loewenheim-Skolem theorem necessarily depends on the size of the language. The proof features a clever construction of an ultrafilter on omega which determines an ultrapower model. Different ultrafilters will be discussed in the context of this theorem; perhaps surprisingly, generalizations of the theorem to uncountable kappa > omega, with models of size kappa and kappa^omega, respectively, are related to large cardinals.

12.12.2022

Speaker: David Uhrik

Title: The Uncountable Hadwiger Conjecture

Abstract: I will talk about the uncountable version of the famous Hadwiger conjecture and its connection to the existence of non-special trees. Also new graph characterizations of Aronszajn, Kurepa and Suslin trees will be mentioned. A new generalized notion of connectedness for graphs will be introduced using which weakly compact cardinals can be characterized..

5.12.2022

Speaker: Adam Prenosil

Title: Stone and Priestley dualities in universal algebra

Abstract: The categorical duality between Boolean algebras and Stone spaces due to Marshall Stone (1936) and the duality between distributive lattices and Priestley spaces due to Hilary Priestley (1970) are among the basic tools that perhaps every algebraic logician has at least passing familiarity with. Less well known is the fact that they have universal algebraic generalizations. In this talk we explain why dualities for distributive lattices, MV-algebras etc. look the way they do, reviewing some classical results from the 1970’s and showcasing some new ones.

21.11.2022

Speaker: Daniil Kozhemiachenko

Title: Bi-Gödel modal logic and its paraconsistent expansion

Abstract: We present a modal logic expanding a Gödel logic with coimplication or Baaz‘ delta operator (bi-Gödel logic) and provide its semantics in terms of [0,1]-valued Kripke models which we dub $\KbiG$. We then provide a paraconsistent expansion of $\KbiG$ with a De Morgan (strong) negation $\neg$.We study model theoretical properties of $\KbiG$ and $\KGsquare$. In particular, we show that they are strictly more expressive than the classical modal logic $\mathbf{K}$. We establish that Glivenko theorem holds only in finitely branching frames. We also explore the classes of formulas that define the same classes of frames both in $\mathbf{K}$ (the classical modal logic) and $\KG^c$. We show that, among others, all Sahlqvist formulas and all formulas $\phi\rightarrow\chi$ where $\phi$ and $\chi$ are monotone, define the same classes of frames in $\mathbf{K}$ and $\KG^c$.

14.11.2022

Speaker: Max Lin

Title: Logic for Rational Interaction with Uncertain Information

Abstract: In past decades, many logics have been proposed to model game-playing scenarios, mainly logic for rational or strategic interactions. These logics, however, do not involve uncertain information, which is pervasive in many game-playing frameworks. Therefore, in this talk, we explore three main logical formalisms for possibilistic reasoning in game-theoretic situations-game logic, coalition logic, and alternating-time temporal logic. We will introduce the classical version, mention some important meta-theorems, and discuss the fuzzy version of these logics. This talk is based on joint work with Dr. Liau for a grant from NSF in Taiwan.

7.11.2022

Speaker: Stepan Laichter

Title: Modelling dialogue

Abstract: In the talk, I will provide an overview of my research on dialogue, mainly focusing on modelling conversational turns with GPT-3.  I will start by providing an overview of the field of dialogue modelling, its methods, historical development, and its relationship to the field of logic at large. Subsequently, I will talk about two research projects that I was part of in the Dialogue Modelling group at the University of Amsterdam last semester.  The first concerns dialogue adaptation to different age groups and the second, my master’s thesis, concerns the modelling of conversational turns with the GPT-3 large language model.

31.10.2022

Speaker: Salvatore Scamperti

Title: Describing Wadge Hierarchy on zero-dimensional Polish spaces

The Wadge Hierarchy of the Baire space is the partial order induced by the reduction through continuous functions on the power set of the Baire space. We will introduce some properties of the Wadge Hierarchy of the Baire space and give some examples. Then we will compare the Wadge Hierarchy of the Baire space and of the Cantor space, to achieve the description of the Wadge Hierarchy of a zero-dimensional Polish space.

24.10.2022

Speaker: Martin Blahynka

Title: Consistency of naive set theory when interpretating quantifiers exclusively

The idea of interpreting quantifiers exclusively dates back to Wittgenstein. Jaakko Hintikka then applied the idea to naive set theory to avoid paradoxes. Given exclusive interpretation, we have (from unrestricted comprehension) e.g. a set R that contains exactly those other sets that are not members of themselves, but this R may or may not contain itself (thus no Russel’s paradox). However, it turns out that having parameters in the comprehension schema tends to lead to inconsistency. The main focus of the talk will be the sketch of my proof that one such theory (with parameters in the comprehension) considered by Hintikka is inconsistent.

10.10.2022

Speaker: Sarka Stejskalova

Title: Automorphisms of trees

In the talk we will focus on omega_1-trees. We will discuss the number of nontrivial automorphisms which can exist on a given omega_1-tree. We will compare these results with results regarding omega-trees. We will also discuss whether we can add an automorphism to omega_1-tree with a nice forcing. It will be an introductory talk accessible to students with basic knowledge of set theory.

 

29.11.2021

We meet in person in room 119 (Celetna, Department of Logic)

Speaker: Vit Fojtik

Title: Expressivity of shallow neural networks

Most current applications of artificial intelligence owe their success to deep neural networks. However, our understanding of neural networks lags far behind the applications. In this talk, we will have a look at some results about their expressivity – their theoretical capabilities and limitations as functional approximators, disregarding the process of training. We will limit our attention to the simpler case of one-hidden-layer networks.
No previous knowledge required.

.

22.11.2021

We meet in person in room 119 (Celetna, Department of Logic)

Speaker: Christopher Lambie-Hanson (Institute of Mathematics, AVČR)

Title: Uncountably Chromatic Graphs

In this talk, we will give an introduction to the study of graphs with uncountable chromatic number, which are of central interest in a variety of fields of mathematical logic. We will discuss questions about compactness for chromatic numbers of graphs as well as questions about what graphs need or need not appear as subgraphs of uncountably chromatic graphs. We will begin by introducing a few classical results from the mid-twentieth century and end with a couple of very recent results coming from both set theory and model theory.

8.11.2021

We meet in person in room 119 (Celetna, Department of Logic)

Speaker: Sarka Stejskalova (Department of Logic)

Title: The negation of the weak Kurepa hypothesis

In the talk we will focus on the negation of the weak Kurepa hypothesis which says that there are no trees of size and height omega_1 with more than omega_1 distinct cofinal branches. We will discuss the effect of the negation of the weak Kurepa hypothesis on the continuum function and also mention some natural generalizations. This is a part of an on-going program which studies compactness principles at omega_1 and omega_2 (and other small cardinals). It will be an introductory talk accessible to students with basic knowledge of set theory.

25.10.2021

We meet in person in room 119 (Celetna, Department of Logic)

Speaker: Vitezslav Svejdar (Department of Logic)

Title: Interpolation in classical and intuitionistic logic

Věta o interpolaci tvrdí, že když je formule \varphi\to\psi logicky platná, pak existuje formule \mu taková, že \varphi\to\mu i \mu\to\psi jsou logicky platné, a přitom \mu obsahuje pouze takové mimologické symboly, které se vyskytují současně ve \varphi i v \psi. Za “symboly” se v predikátové logice považují predikátové symboly a volné proměnné, ale z dostupné literatury není tak jasné, jestli se k nim mají počítat i funkční symboly. Naznačíme důkazově teoretický důkaz využívající zobecněné pravidlo generalizace. Budeme uvažovat, jak jej lze modifikovat pro intuicionistickou logiku.

17.5.2021

Talks by master and bachelor students.

Speaker: Martin Blahynka (Master student, Logic)
 

Title: Non-well-founded Conway games

Abstract: I will introduce the topic of combinatorial games. The classical example of such games is a game played between two players who alternate in making a move and the player who has no move to make loses; while possible moves are always determined by the current position, from which each player may have different options. This is how cominatorial games were first introduced by John Horton Conway in the ’70s.

I will show a possible way to extend the theory of such games to non-well-founded games – i.e. games in which an infinite play is possible.

I will also introduce another type of a combinatorial game and show how the two can be reduced to each other so that the existence of winning strategies is preserved.

Speaker: Stepan Laichter (Master student, Logic)
 
Title: Computation as social agency

Abstract: In my presentation, I will summarise van Benthem’s view of computation as an “interactive agency in social networks”. In this view, van Bethem proposes a view of computation based on the shift from the traditional perspective of what is computed to a view prioritising by whom and how something is computedI will provide a basic evaluation of this approach as a full theory of computation and contrast the view to a traditional Turing-style account of computation.
 
Speaker: Jan Rydl (Bachelor student, Logic)
 

Title: Some remarks on intuitionistic multisuccedent calculi

Abstract: I will motivate the concept of a multisuccedent calculus for intuitionistic logic and make a few historical remarks. Then I will introduce a sample calculus, discuss some of its notable features, and offer a few variants which occur in the literature.

3.5.2021

Epistemic Reasoning with Byzantine-Faulty Agents

Speaker: Krisztina Fruzsa (TU Wien)

I will present some of our results regarding the applications of epistemic logic to the study of byzantine fault-tolerant distributed systems. For the purpose of the knowledge-based analysis of such systems, by extending Fagin et al.’s classic runs-and-systems framework [R. Fagin et al., 1995], we have developed a very general framework which allows one to express any type of faulty behavior of the agents, from fully byzantine to fully benign. One of our central results is the, so-called, Brain-in-a-Vat Lemma (formalizing the brain-in-a-vat scenario) which exposes the substantial limitations of what can be known by the agents in byzantine fault-tolerant distributed systems. We will discuss this lemma together with its consequences. In particular, we will see how it affects the preconditions of actions of the agents in such systems, given that the Knowledge of Preconditions principle [Y.Moses, 2015] holds.

26.4.2021

Generalizing Propositional Dynamic Logic.

Speaker: Igor Sedlar (ICS CAS)

Propositional Dynamic Logic, PDL, is a well-known modal logic designed to formalize reasoning about action, especially about the correctness properties of actions expressing that a given post-condition is guaranteed to hold if the action is executed successfully in a state satisfying a given pre-condition. Being an extension of classical propositional logic, PDL is not adequate in many settings, for example if some sort of meaning connection between pre-conditions and post-conditions of an action is required, or if actions and the desired post-conditions are specified using graded notions. In this talk I will outline my recent work on generalizations of PDL using a propositional base different from classical propositional logic, most notably relevant logics and many-valued logics. Some of the results were obtained jointly with V. Punčochář and A. Tedder.

19.4.2021

Probabilities over Belnap Dunn logic

Speaker: Ondrej Majer (Inst. of Philosophy, Inst. of Computer Science CAS), Time: Monday April 19, 16:30 Prague time over Zoom (contact Radek Honzik for details).

Belnap and Dunn introduced a four valued propositional logic which was designed to deal with incomplete or contradictory information. It extends the classical approach in that the propositions cannot simply be either true or false, but also both true and false or neither. The latter two values are to account for the possibility of the available information being incomplete or providing contradictory evidence.

We present a probabilistic extension of Belnap Dunn logic that permits agents to have probabilistic beliefs based on incomplete and/or inconsistent information. We provide a sound and complete axiomatization for the framework defined and also methods for updating probabilistic beliefs and for aggregating inconsistent/incomplete information coming from distinct sources.

15.3.2021

What is Y-cc forcing?

Speaker: David Chodounsky (Institute of mathematics AVCR), Time: Monday March 15, 16:30 Prague time over Zoom (contact Radek Honzik for details).

The notion of Y-cc, introduced by Zapletal and the speaker, is an notion  intermediate between ccc and sigma-centered forcing. Although the formulation of the definition is somewhat cumbersome and takes heavy use of countable elementary submodels, the notion behaves in a very natural way and has surprisingly nice properties. I will explain the definition
of Y-cc, mention the main properties, and showcase proofs of some basic facts.

1.3.2021

Some notes on centered forcings and separability

Speaker: Radek Honzik (Department of Logic, FFUK) Title: Some notes on centered forcings and separability. Time: Monday 1.3.2021; 16:30 Prague time. Please write to Radek Honzik to get the Zoom link.

We will discuss some folklore results which may not be so widely known. They are related to a specific property of partial orders (forcings): We say that (P,<) is sigma-centered if it is a union of countably many centered sets (or filters).  We say that a topological space X is separable if it contains a countable dense subset. We will deal with the following topics: (1) What is the analogy between the notions of sigma-centeredness and separability (of topological spaces)? (2)
For which cardinals is the Cohen forcing on omega sigma-centered? 

11.1.2021

Talks by master and bachelor students

Speakers: Stepan Laichter, Jiri Rydl, Jan Stefanisin. Time: Monday January 11, 16:30, Prague time. Place: Zoom (contact Radek Honzik for details).

Stepan Laichter (Master program in Logic, Prague), Title: An Introduction to Social Software

Abstract: I will introduce the notion of social software in logic, as formulated by Rohit Parikh, and discuss the relation of social software to other fields in mathematics and the sciences. I will illustrate how some of the applications of social software can draw upon propositional dynamic logic. I will close with a discussion on the need for such a term and outline some open questions within the field.

Jiri Rydl (Bachelor program in Logic, Prague), Title: Gentzen’s Untersuchungen

Abstract: I will discuss Gentzen’s Untersuchungen (1935), the first paper to propose a variant of sequent calculus. For Gentzen the central purpose for the development of such system was that it allowed for a nice treatment of the Hauptsatz, the cut elimination theorem in case of sequent calculi. I will go through the central steps in the proof of this theorem and follow with a brief discussion of some points which allow for a different approach, such as Gentzen’s local definition of the cutrank, the elimination of topmost cuts, or his introduction of multicut.

Jan Stefanisin (Bachelor program in Logic, Prague), Title: Interpretace axiomatickych teorii a jejich vyuziti.

12/07/2020

Partition relations

Speaker: David Uhrik (MFFUK),
Time: Monday December 7, 16:30, Prague time.
Place: Zoom (contact Radek Honzik for details).

The study of partition relations arguably started with the famous Ramsey theorems, since then it has become a very live part of set theory with far-reaching applications and connections to numerous parts of mathematics, e.g. topology, theory of ordered sets, infinite graph theory, large cardinals and many others. I will give an overview of results, old and new, in this area.

11/30/2020

Purity of formal mathematical proofs

Speaker: Robin Martinot (Universiteit Utrecht),
Time: Monday November 30, 16:30, Prague time.
Place: Zoom (contact Radek Honzik for details).

A phenomenon that has gained attention in the philosophy of proof theory is the property of purity of proof. Intuitively, a pure proof of a mathematical theorem only draws upon notions that belong to the content of the theorem. An impure proof, by contrast, contains notions that are topically unrelated to the theorem. This classification of proofs is connected to other properties of proofs such as simplicity, efficiency and equivalence, and therefore also to Hilbert’s 24th problem. A reliable formal measure of purity would provide insight into what constitutes the gap between two proofs of the same theorem. I will discuss several strategies from the literature for devising such a measure, the most com- mon of which makes use of cut elimination. Most current strategies still have considerable weaknesses, including limited applicability to stronger mathematical theories. I will touch upon some strategies that I am currently exploring to help overcome these vulnerabilities.

11/23/2020

The Limits of Causal Graphs: Density

Speaker: Dean McHugh (University of Amsterdam),
Time: Monday November 23, 16:30, Prague time.
Place: Zoom (contact Radek Honzik for details).

Causal reasoning is often modelled using causal graphs, such as Bayesian networks and structural causal models (e.g. Pearl 2000, Causality). Given the success of graphical models of causation, one may ask whether they can represent every instance of causal reasoning, or whether a more expressive framework is required. In this talk we show that graphical causal models are limited in their expressive power: some intuitive causal structures are impossible to represent using graphical causal models. Specifically, graphical causal models cannot represent dense causal chains; that is, chains of events where between any two events C and E on the chain there is a third event D on the chain such that C causally influences D and D causally influences E. Dense causal chains appear, arguably, in both our intuitive representation of the world and models in physics that assume spacetime is dense. Since any framework representing causal reasoning should be compatible with these models, a more expressive framework is required—one that can represent dense causal chains.

11/16/2020

P-ultrafilters in Silver extensions

David Chodounsky (Institute of Mathematics, AVCR) will talk about P-ultrafilters in Silver extensions.
Time: 16.11.2020, 16:30 Prague time. Write to Radek Honzik to get the Zoom link.

P-ultrafilters are an important and widely used class of ultrafilters on natural numbers. Their existence is however not provable in ZFC. The first model without P-ultrafilters was constructed by Shelah in 1977.  For a long time the method of Shelah was essentially the only known way to get models without P-ultrafilters and many related questions remained
opened. Many of these questions were settled in our joint paper with O.  Guzman, we proved that there are in fact no P-ultrafilters in the Silver model (and it realtives). I will give a quick overview of this result.

11/09/2020

Incomparable consistency degrees and large-cardinal axioms

Speaker: Radek Honzik (Department of Logic, FFUK)
Title: Incomparable consistency degrees and large-cardinal axioms.
Time: Monday 9.11.2020; 16:30 Prague time. Please write to Radek Honzik to get the Zoom link.

We will review the folklore fact that if T is a theory allowing the usual Goedel-like analysis (such as PA or ZFC), then there are infinitely many incomparable consistency degrees, i.e. there are infinitely many statements A, B such that T + Con(T +A) does not imply Con(T+B), or conversely.

On the other hand, it is known that virtually all “interesting” independent statements over ZFC have comparable consistency degrees. This is because they are reducible to large-cardinal axioms which are linearly ordered in the consistency ordering. We use this fact to argue that large-cardinal axioms (and statements equivalent to them in the consistency ordering) are natural mathematical propositions which are not affected by self-referential constructions.

10/26/2020

Decision theory and Bayesian agents

Daniel Herrmann, University of California Irvine, will talk about decision theory and Bayesian agents. The talk will take place over Zoom on Monday 16:30, October 26, Prague time (GMT+2), using the stable Zoom link. If you don’t know the Zoom link, write to Radek Honzik.

Decision theory attempts to provide an account of rational decision making. To this end decision theorists often reason about idealized Bayesian agents. Sharpening and generalizing some remarks by Brian Skyrms and Richard Jeffrey, I argue that for Bayesian agents with a sufficiently rich algebra there can be no decision problems. This is a problem for decision theory, as most of the debate concerns these kinds of agents. I propose a solution to this problem, but one which comes with a cost: in order for an agent to view herself as in a legitimate decision problem she cannot be ideally Bayesian. I argue that my solution both fits well with certain approaches to decision theory, especially deliberational dynamics, and helps clarify the goals of decision theory.

10/19/2020

Elementary embeddings in set theory

Radek Honzik, department of Logic, will talk about Elementary embeddings in set theory. Monday October 19, 16:30, over Zoom.

Abstract: We will review some applications of elementary embeddings between transitive models of set theory. In particular, we will discuss the method of lifting an embedding to a generic extension which is often used to show that some desirable large-cardinal properties are preserved under forcing.
Time: Monday October 19, 16:30 (Prague time, GMT+2) The talk will take place over Zoom (write to Radek Honzik to get the link).

03/16/2020

On enhanced generalization (Cancelled!)

Vitezslav Svejdar (Department of Logic) will talk about enhanced generalization (Monday 16.3).

The generalization rule in logical calculi makes it possible to
“unsubstitute” a variable $y$ from a formula $\varphi_x(y)$ and conclude
that $\forall x \varphi$ (or that $\exists x \varphi$ if the step
is happening in a premise), provided that there are no unwanted free
occurrences of the unsubstituted variable. We consider an enhanced
generalization rule that makes it possible to simultaneously
unsubstitute not only several variables, but also several terms
(provided that they are pairwise different and there are no unwanted
occurrences of their outermost symbols). While we cannot claim that this
enhanced generalization models a step in a reasoning, and it is not
sound in logic with equality, we show that it is sound in logic without
equality and that it has a useful application, namely the interpolation
theorem (for logic without equality but with function symbols).

02/24/2020

Believing the Axioms I

Tereza Stejskalová (logika, FFUK) bude mluvit axiomech ZFC a jejich historii a motivaci. Přednáška je založena na článku P. Maddy Believing the Axioms I (JSL 1988).

02/17/2020

Believing the Axioms II

Radek Honzik will discuss P. Maddy’s paper Believing the Axioms II (JSL 1988).

Believing the Axioms II is a continuation of the first paper by Maddy and deals with the Axiom of Determinacy (AD). The paper attempts to argue that AD (or its variants) may be a good candidate for a new strong axiom of set theory. The seminar will review the basic points of the paper (prior knowledge of the paper is not necessary).

12/16/2019

Casual inferences in statistics

Lars S. Laichter (Department of logic) will introduce basic concepts of casual inferences in statistics. CHANGE OF DATE:  16.12.,  16:30.

In my presentation, I will provide a brief introduction and a discussion of the methods of causal inference in statistics. Methods of causal inference have been argued to be an important addition to traditional statistical methods. In particular, I will introduce the notion of the Structural Causal Model (SCM), as proposed by Judeau Pearl, to illustrate some of the major advancements in the general theory of causation. These advancements include methods for inferring a model’s properties based on (1) effects of interventions, (2) probabilities of counterfactuals, and (3) direct and indirect effects. Finally, I will discuss some of the possible applications of this theory, as well as its wider implications for scientific inquiry. Overall, I aim for this presentation to provide an accessible introduction to the methods of causal inference and highlight the advantages of the methods of causal inference over traditional statistical methods.

12/02/2019

Who’s who in large cardinals, II

Radek Honzik (Department of logic) will continue talking about large cardinals. Monday 2.12., 16:30. We will discuss “larger” large cardinals, such as measurable and supercompact cardinals, and their effect on the set-theoretical universe and applications in mathematics and set theory.

11/25/2019

THE IMPOSSIBILITY OF SQUARING THE CIRCLE Gregory, Huygens and the limits of Cartesian geometry

Davide Crippa (Institute of Philosophy, AVČR) will talk about the impossibility of squaring the circle. Monday 25. November, 16:30, Department of Logic.

With the emergence of the algebraic movement in XVIth and XVIIth century geometry, the ideal that all mathematical problems should and could be solved by the most adequate means was fostered by outstanding mathematicians (Viète, Descartes). Yet it was a matter of dispute whether certain well-known problems, like the quadrature of the circle, could be solved by geometrically acceptable methods. My talk will explore this issue, considering a controversy occurred in 1668 between the Scottish mathematician James Gregory and the Dutch mathematician Christiaan Huygens, about the possibility of solving the quadrature of central conics (which included the circle) by algebraic means. Whereas the former held it was impossible, the latter believed that the circle could be squared algebraically. This controversy is significant because it hinged upon methodological or foundational questions: which were the bounds of Cartesian geometry? Are the five algebraic operations sufficient in order to express and solve all problems concerning the objects of Euclid’s geometry?

11/18/2019

Who’s who in large cardinals, I

Radek Honzik (Department of logic) will talk about motivations, history and applications behind large cardinals. 16:30, Monday 18.11.2019.

11/11/2019

Aspekty eliminovatelnosti řezu v různých logikách

Vítězslav Švejdar (Department of Logic, FFUK) bude mluvit o různých neklasických logikách a jejich vztahu k eleminovatelnosti řezu. 11. listopadu, 16:30.

11/04/2019

Finitní verze Gödelových vět o neúplnosti

Martina Maxa bude mluvit o finitních verzích Gödelových vět o neúplnosti a Löbově větě. Monday November 4, 16:30.

Budeme se zabývat finitními protějšky známých vět dotýkajících se základů matematiky, jako jsou Gödelovy věty o neúplnosti či Löbova věta. Jejich finitní verze jsou již silnější než známé otevřené problémy ve výpočetní složitosti jako např. domněnka P se nerovná NP. Kromě finitní verze druhé Gödelovy věty, představíme i finitní verzy první Gödelovy věty a ukážeme vztah mezi těmito domněnkami. Také uvedeme tvrzení, jež by se dalo nazvat finitní verzí Löbovy věty. Cílem je ukázat, že otevřené problémy ve výpočetní složitosti mají blízký vztah k problémům týkajících se logiky a tímto i základů matematiky.

 

10/21/2019

Most common proposals for solving the CH problem

Radek Honzik will survey old and recent attempts and proposals for solving the Continuum Hypothesis problem. Monday  October 21, 16:30.  Students interested in credits from the seminar should attend and discuss their participation in the seminar.

Students interested in credits from the seminar should attend and discuss their participation in the seminar.

04/29/2019

Složitost Booleovských formulí

Seminář katedry: Vít Fojtík, Department of Logic, FF UK, 17:00, 29.4.2019.

Booleovské formule jsou typ Booleovských obvodů modelující výpočty, při kterých si nelze pamatovat mezivýsledky. Přestože lze ukázat, že existují funkce s exponenciální formulovou složitostí (a dokonce jich je většina), jedním z nevyřešených problémů výpočetní složitosti je najít ,,větší než polynomiální” dolní odhad pro nějakou konkrétní funkci. Snahy o sestrojení odhadu se ubírají dvěma převažujícími směry; první ja založený na abstraktním pojmu míry složitosti, zatímco druhý používá náhodně zvolené podfunkce dané funkce.

03/04/2019

Indestructibility of Kurepa Hypothesis

Šárka Stejskalová, Department of Logic, FF UK

We will review an argument of Jensen and Schlechta form 1990 who showed that Kurepa Hypothesis can be indestructible under all ccc forcing notions. Possible generalizations will be discussed.

02/25/2019

Abstract notion of liftability for supercompact cardinals

Radek Honzík, Department of Logic, FF UK

We will discuss generalizations of the property of kappa-directed closure which appears in the classical theorem of Levy on indestructible supercompact cardinals. Seminar takes place in C119 at 17:00.

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.)

Úvod > Research > Seminar