Seminar on Applied Mathematival Logic Archive

• 12.6.2019
  Sebastian Sequoiah-Grayson (Uni. Sydney): Modelling epistemic actions: From aggregations to combinations
  Abstract: Examples of epistemic actions are given most commonly as observations and announcements. In such frameworks, logical omniscience, or something close to inferential optimisation, is assumed often. In this talk I want to do several things. Firstly, I want to propose and defend a view of inferences themselves as epistemic actions of a psychological, information-handling sort. I shall introduce two varieties of such actions, aggregations and combinations. Secondly, I want to explain why it is that I think that nearly everything said about logical omniscience and epistemic closure is wrong. Then finally I shall introduce a new type of substructural epistemic logic that I think I think is a promising start to saying something important and non-trivial about the properties and nature of the inferential epistemic actions in question.


• 5.6.2019
  Joan Gispert (Uni. Barcelona): Structural completeness and quasivariety lattices in many-valued logics
  Abstract: Admissible rules of a logic are those rules under which the set of theorems are closed. A logic is said to be structurally complete when every admissible rule is a derivable rule. A logic is almost structurally complete when every rule is either derivable or passive (there is no substitution that turns all premisses into theorems). Gödel logic and Product logic are structurally complete and moreover every axiomatic extension is structurally complete; finite-valued Łukasiewicz logics turn to be almost structurally complete and the infinite valued Łukasiewicz logic is not structurally complete, nor almost structurally complete. In this talk we will algebraically investigate structural completeness, almost structural completeness for some cases of algebraizable many-valued logics, and we try, if possible, to describe the quasivariety lattice of its associated algebraic class.


• 29.5.2019
  Adam Přenosil (Vanderbilt Uni.): Algebras of fractions: bimonoids and bimodules
  Abstract: A classical result due essentially to Steinitz (1910) states that each cancellative commutative monoid can be embedded into an Abelian group. This was later improved by Ore (1931): each so-called right reversible cancellative monoid can be embedded into a group of right fractions, i.e. a group where each element has the form a · b−1 for some a; b in the original monoid. In this talk we show how to define and construct algebras of fractions for other classes of algebras, such as Heyting algebras. These algebras of fractions will be involutive residuated lattices into which a given residuated lattice has a suitable embedding. We sketch two approaches to this problem: one based on bimonoids (one-sorted structures with two compatible monoidal operations) and one based on bimodules (in this context, two-sorted structures consisting of a monoid acting on another monoid). The talk is based on joint work with Nick Galatos and Costas Tsinakis.


• 15.5.2019
  Radek Honzík (FF CUNI): A small ultrafilter number on uncountable regular cardinals
  Abstract: We will review the notion of compactness for infinitary logics, discuss the basic properties of compactness (limitations of Zorn’s lemma, construction of models using compactness). We will mention some original results related to the existence of a normal measure on uncountable kappa with small base and its compatibility with more compactness principles.


• 24.4.2019
  Tommaso Moraschini (ICS CAS): The poset of all logics
  Abstract: A notion of interpretability between arbitrary propositional logics is introduced, and shown to be a preorder on the class of all logics. Accordingly, we refer to its associated poset as to the "poset of all logics". In this talk we shall explore the structure of this poset. In particular, we observe that that it has infima of arbitrarily large sets, but even finite suprema may fail to exist. This should not come as a surprise, since the universe of the poset of all logics is indeed a proper class. The formalism of interpretability is subsequently exploited to introduce the notion of a Leibniz class of logics, and we refer to the complete lattice of Leibniz class as to the Leibniz hierarchy. This order-theoretic perspective allows us to address in mathematical terms the following foundational question: do the classes traditionally associated to the Leibniz hierarchy (e.g. that of protoalgebraic logics) capture "fundamental" concepts?


• 10.4.2019
  Zuzana Haniková (ICS CAS): Computing the validity degree in Łukasiewicz logic
  Abstract: This talk will consider provability/validity degrees in propositional Łukasiewicz logic in the context of other optimization problems. In order to define provability degrees of propositional formulas, rational constants are employed, so one in fact works in a conservative extension called Rational Pavelka logic (RPL). On the other hand, no constants are necessary to introduce the validity degree; for a formula F, its validity degree under a theory T is the infimum of values of F under assignments that make T true in the standard MV-algebra on [0,1]. Pavelka completeness states that in RPL the provability degree coincides with the validity degree. For T and F to be even considered as a computational problem, T needs to be finite, whereupon the provability/validity degree becomes rational; one can moreover show that the size of the denominator of this rational is polynomial in the sizes of T and F. I will discuss how the optimization problem relates to finite consequence in RPL taken as a decision problem (shown to be coNP-complete by Hájek), which can be viewed as an upper bound. Further, I will try to provide a lower bound using the taxonomy of optimization problems provided by [M. Krentel, The complexity of optimization problems].


• 27.3.2019
  Igor Sedlár (ICS CAS): Two approaches to non-classical modal logic
  Abstract: Two prominent approaches to non-classical modal logic are the lattice-valued one, using Kripke frames and valuation functions mapping formula-state pairs to a lattice of truthvalues, and the relational one, extending frame semantics for non-classical logics--usually given by means of so-called Routley-Meyer frames--by additional accessibility relations corresponding to modal operators. In this talk, I outline some preliminary results on the relationship between these two approaches. Using elementary dualities between residuated lattices and Routley-Meyer frames, I show that the logic of all modal associative Routley-Meyer frames is the logic of all Kripke frames with valuations in complete distributive FL-algebras.


• 20.3.2019
  Joan Betrran-San Millán (FLU CAS): Frege's Begriffsschrift and second-order logic
  Abstract: Gottlob Frege developed in Begriffsschrift (1879) the concept-script, the fi rst formal system in the history of modern logic. The similarities between Frege's system and some contemporary formal systems have been taken for granted as evidence for a contemporary interpretation of the concept-script. In fact, the most common and traditional interpretation of Begriffsschrift's concept-script claims that it consists of a formal language of second-order logic and a deductive system for that language. In this talk, I offer a detailed analysis of Begriffsschrift's deductive system and justify that it must not be interpreted as a formal system of second-order logic. Specifically, I defend that a reformulation of the calculus of the concept-script in terms of a second-order calculus distorts its nature and, moreover, that some proofs of Begriffsschrift are not reproducible by means of this reformulation.


• 13.3.2019
  Pavel Hrubeš (MI CAS): Compression schemes and the Continuum Hypothesis
  Abstract: The Continuum Hypothesis is a conjecture about the cardinality of the set of real numbers. As such, it is a classical problem known to be undecidable from the usual ZFC axioms. We will show that some problems arising in the context of machine learning are equivalent to variants of CH - and hence undecidable over ZFC. We will focus on the problem of compressing finite strings of real numbers. (Based on joint work with S. Ben-David, S.Moran, A. Shpilka, A. Yehudayoff)


• 27.2.2019
  Ansten Klev (FLU CAS): Identity and definition in natural deduction
  Abstract: Recall that in natural deduction each primitive constant is equipped with introduction and elimination rules. Such rules can be given not only for the logical connectives and the quantifiers, but also for the identity predicate: its introduction rule is the reflexivity axiom, t = t, and its elimination rule is the indiscernibility of identicals. Although a normalization theorem can be proved for the resulting system, one might not be entirely satisfied with this treatment of identity, especially if one adheres to the idea - going back to Gentzen - that the meaning of a primitive constant is determined by its introduction rule(s). Firstly, it is not obvious that the introduction rule for the identity predicate is strong enough to justify its elimination rule. Secondly, it is not clear what to say about definitions taking the form of equations. Such definitions are usually regarded as axioms, hence they must be additional introduction rules for the identity predicate. Since definitions are particular to theories, it follows that the meaning of the identity predicate changes from one theory to the other. I will show that by enriching natural deduction with a theory of definitional identity we can answer both of these worries: we can justify the elimination rule on the basis of the introduction rule, and we can extend any theory with definitions while keeping the reflexivity axiom as the only introduction rule for the identity predicate.


• 20.2.2019
  Luca Reggio (ICS CAS): Uniform interpolation for IPC via an open mapping theorem for Esakia spaces
  Abstract: The uniform interpolation property of the intuitionistic propositional calculus (IPC) wasfirst proved by Pitts in 1992 by means of proof-theoretic methods. We prove an open mapping theorem for the topological spaces dual to finitely resented Heyting algebras. In turn, this yields a short, self-contained semantic proof of Pitts result. Our proof is based on the methods of Ghilardi & Zawadowski. However, it does not require sheaves nor games, only basic duality theory for Heyting algebras. This is joint work with Sam van Gool.


• 6.2.2019
  Marco Abbadini (Universita degli Studi di Milano): The dual of compact ordered spaces is a variety
  Abstract: Last year (2018), Hofmann, Neves and Nora proved that the dual of the category of partially ordered compact spaces and monotone continuous maps is an infinitary quasi-variety. One of the open questions was: is it also a variety? We show that the answer is: yes, it is an infinitary variety.


• 12. 12. 2018
  Berta Grimau (UTIA CAS): The Instability of Plural Scepticism towards Superplural Logic
  Abstract: Plural Logic is an extension of First-Order Logic which has, as well as singular terms and quantifiers, their plural counterparts. Analogously, Superplural Logic is an extension of Plural Logic which has, as well as plural terms and quantifiers, superplural ones. The basic idea is that superplurals stand to plurals like plurals stand to singulars (they are pluralized plurals). Allegedly, Superplural Logic enjoys the expressive power of a simple type theory while committing us to nothing more than the austere ontology of First-Order Logic. Were this true, Superplural Logic would be a useful tool, with various applications in the philosophy of mathematics, metaphysics and formal semantics. However, while the notions of plural reference and quantification enjoy widespread acceptance today, their superplural counterparts have been received with a lot of scepticism. In this talk, I will argue for the legitimacy of a face value interpretation of Superplural Logic by showing that some ordinary languages display clear cases of superplural reference and that they do so in an indispensable manner. Since the arguments I will put forward are of the same sort friends of Plural Logic have employed to defend their position, I will conclude that the (commonly held) view that Plural Logic is legitimately interpreted at face value but not so its superplural extensions is likely to suffer from internal tensions.


• 5. 12. 2018
  Guillermo Badia (Kepler University, Linz): Maximality of first-order logics based on finite MTL-chains
  


• 28. 11. 2018
  Andrew Tedder (ICS CAS): Residuals and conjugates in positive substructural logic
  Abstract: While the relations between an operation and its residuals play an essential role in substructural logic, a closely related relation between operations is that of conjugation - so closely related that with Boolean negation, the conjugates and residuals of an operation are interde_nable. In this talk extensions of the Lambek Calculus including conjugates of fusion (without negation) are investigated. Some interesting properties of the conjugates are discussed, a proof system is presented, its adequacy questioned, and some applications are considered.


• 21. 11. 2018
  Carles Noguera (UTIA CAS): General neighborhood and Kripke semantics for modal many-valued logics
  Abstract: Frame semantics, given by Kripke or neighborhood frames, do not give completeness theorems for all modal logics extending, respectively, K and E. Such shortcoming can be overcome by means of general frames, i.e. frames equipped with a collection of admissible sets of worlds (which is the range of possible valuations over such frame). We export this approach from the classical paradigm to modal many-valued logics by defining general A-frames over a given residuated lattice A (i.e., the usual frames with a collection of admissible A-valued sets). We describe in details the relation between general Kripke and neighborhood A-frames and prove that, if the logic of A is finitary, all extensions of the corresponding logic E of A are complete w.r.t. general neighborhood frames. Our work provides a new approach to the current research trend of generalizing relational semantics for non-classical modal logics to circumvent axiomatization problems.


• 14. 11. 2018
  Luca Reggio (ICS CAS): Duality, definability and continuous functions
  Abstract: Weierstrass approximation theorem states that any continuous real-valued function defined on a closed real interval can be approximated by polynomials. In 1937 Marshall Stone proved a vast generalisation of this result: nowadays known as the Stone-Weierstrass theorem, this is a fundamental result of functional analysis with far-reaching consequences. We show how, through duality theory, the Stone-Weierstrass theorem can be seen as an instance of the Beth definability property of a certain logic.


• 19. 10. 2018
  Special session -- Amanda Vidal (ICS CAS): Generalizing Geiger's result to two valued versions
  Abstract: We will go through an introduction to the algebraic approach to CSP and VCSP. We will then explore a notion of order-homomophism over valued structures that gives place to certain polymorphisms, and we show that these polymorphisms, considered over a small transformation of the original structure, characterize up to preservation the set of pp-definable formulas in the structure. When the polymorphisms preserve both strong or weak conjunction, they will characterize the corresponding definable formulas in locally finite structures. This can be seen as a natural generalization of Geigers characterization result for usual CSP to valued cases. Moreover, we will study how these kind of polymorphisms can be modified to preserve positive formulas with strong conjunction only (in the sense of the usual VCSP studied in the literature).