Logic and Foundations Commons^™

Tool Support For Reasoning In Display Calculi, Samuel Balco, Sabine Frittella, Giuseppe Greco, Alexander Kurz, Alessandra Palmigiano

Engineering Faculty Articles and Research

We present a tool for reasoning in and about propositional sequent calculi. One aim is to support reasoning in calculi that contain a hundred rules or more, so that even relatively small pen and paper derivations become tedious and error prone. As an example, we implement the display calculus D.EAK of dynamic epistemic logic. Second, we provide embeddings of the calculus in the theorem prover Isabelle for formalising proofs about D.EAK. As a case study we show that the solution of the muddy children puzzle is derivable for any number of muddy children. Third, there is a set of meta-tools, …

The Varieties Of Indispensability Arguments, Marco Panza, Andrea Sereni

MPP Published Research

The indispensability argument (IA) comes in many different versions that all reduce to a general valid schema. Providing a sound IA amounts to providing a full interpretation of the schema according to which all its premises are true. Hence, arguing whether IA is sound results in wondering whether the schema admits such an interpretation. We discuss in full details all the parameters on which the specification of the general schema may depend. In doing this, we consider how different versions of IA can be obtained, also through different specifications of the notion of indispensability. We then distinguish between schematic and …

Introduction To Functions And Generality Of Logic. Reflections On Frege's And Dedekind's Logicisms, Hourya Benis Sinaceur, Marco Panza, Gabriel Sandu

MPP Published Research

This book examines three connected aspects of Frege’s logicism: the differences between Dedekind’s and Frege’s interpretation of the term ‘logic’ and related terms and reflects on Frege’s notion of function, comparing its understanding and the role it played in Frege’s and Lagrange’s foundational programs. It concludes with an examination of the notion of arbitrary function, taking into account Frege’s, Ramsey’s and Russell’s view on the subject. Composed of three chapters, this book sheds light on important aspects of Dedekind’s and Frege’s logicisms. The first chapter explains how, although he shares Frege’s aim at substituting logical standards of rigor to intuitive …

Newton On Indivisibles, Antoni Malet, Marco Panza

MPP Published Research

Though Wallis’s Arithmetica infinitorum was one of Newton’s major sources of inspiration during the first years of his mathematical education, indivisibles were not a central feature of his mathematical production.

Wallis On Indivisibles, Antoni Malet, Marco Panza

MPP Published Research

The present chapter is devoted, first, to discuss in detail the structure and results of Wallis’s major and most influential mathematical work, the Arithmetica Infinitorum (Wallis 1656). Next we will revise Wallis’s views on indivisibles as articulated in his answer to Hobbes’s criticism in the early 1670s. Finally, we will turn to his discussion of the proper way to understand the angle of contingence in the first half of the 1680s. As we shall see, there are marked differences in the status that indivisibles seem to enjoy in Wallis’s thought along his mathematical career. These differences correlate with the changing …

The Logical System Of Frege’S Grundgesetze : A Rational Reconstruction, Méven Cadet, Marco Panza

MPP Published Research

This paper aims at clarifying the nature of Frege's system of logic, as presented in the first volume of the Grundgesetze . We undertake a rational reconstruction of this system, by distinguishing its propositional and predicate fragments. This allows us to emphasise the differences and similarities between this system and a modern system of classical second-order logic.

Pruebas Entimemáticas Y Pruebas Canónicas En La Geometría Plana De Euclides, Marco Panza, Abel Lassalle Casanave

MPP Published Research

Dado que la aplicación del Postulado I.2 no es uniforme en Elementos, ¿de qué manera debería ser aplicado en la geometría plana de Euclides? Además de legitimar la pregunta misma desde la perspectiva de una filosofía de la práctica matemática, nos proponemos esbozar una perspectiva general de análisis conceptual de textos matemáticos que involucra una noción ampliada de la teoría matemática como sistema de autorizaciones o potestades y una noción de prueba que depende del auditorio.

Since the application of Postulate I.2 in the Elements is not uniform, one could wonder in what way should it be applied in Euclid’s …

Positive Fragments Of Coalgebraic Logics, Adriana Balan, Alexander Kurz, Jirí Velebil

Engineering Faculty Articles and Research

Positive modal logic was introduced in an influential 1995 paper of Dunn as the positive fragment of standard modal logic. His completeness result consists of an axiomatization that derives all modal formulas that are valid on all Kripke frames and are built only from atomic propositions, conjunction, disjunction, box and diamond. In this paper, we provide a coalgebraic analysis of this theorem, which not only gives a conceptual proof based on duality theory, but also generalizes Dunn's result from Kripke frames to coalgebras for weak-pullback preserving functors. To facilitate this analysis we prove a number of category theoretic results on …

Presenting Distributive Laws, Marcello M. Bonsangue, Helle H. Hansen, Alexander Kurz, Jurriaan Rot

Engineering Faculty Articles and Research

Distributive laws of a monad T over a functor F are categorical tools for specifying algebra-coalgebra interaction. They proved to be important for solving systems of corecursive equations, for the specification of well-behaved structural operational semantics and, more recently, also for enhancements of the bisimulation proof method. If T is a free monad, then such distributive laws correspond to simple natural transformations. However, when T is not free it can be rather difficult to prove the defining axioms of a distributive law. In this paper we describe how to obtain a distributive law for a monad with an equational presentation …

Extensions Of Functors From Set To V-Cat, Adriana Balan, Alexander Kurz, Jirí Velebil

Engineering Faculty Articles and Research

We show that for a commutative quantale V every functor Set --> V-cat has an enriched left- Kan extension. As a consequence, coalgebras over Set are subsumed by coalgebras over V-cat. Moreover, one can build functors on V-cat by equipping Set-functors with a metric.

Approximation Of Nested Fixpoints, Alexander Kurz

Engineering Faculty Articles and Research

The question addressed in this paper is how to correctly approximate infinite data given by systems of simultaneous corecursive definitions. We devise a categorical framework for reasoning about regular datatypes, that is, datatypes closed under products, coproducts and fixpoints. We argue that the right methodology is on one hand coalgebraic (to deal with possible nontermination and infinite data) and on the other hand 2-categorical (to deal with parameters in a disciplined manner). We prove a coalgebraic version of Bekic lemma that allows us to reduce simultaneous fixpoints to a single fix point. Thus a possibly infinite object of interest is …

Coalgebraic Semantics Of Reflexive Economics (Dagstuhl Seminar 15042), Samson Abramsky, Alexander Kurz, Pierre Lescanne, Viktor Winschel

Engineering Faculty Articles and Research

This report documents the program and the outcomes of Dagstuhl Seminar 15042 “Coalgebraic Semantics of Reflexive Economics”.

On The Indispensable Premises Of The Indispensability Argument, Andrea Sereni, Marco Panza

MPP Published Research

We identify four different minimal versions of the indispensability argument, falling under four different varieties: an epistemic argument for semantic realism, an epistemic argument for platonism and a non-epistemic version of both. We argue that most current formulations of the argument can be reconstructed by building upon the suggested minimal versions. Part of our discussion relies on a clarification of the notion of (in)dispensability as relational in character. We then present some substantive consequences of our inquiry for the philosophical significance of the indispensability argument, the most relevant of which being that both naturalism and confirmational holism can be dispensed …

Euler, Reader Of Newton: Mechanics And Algebraic Analysis, Sébastien Maronne, Marco Panza

MPP Published Research

We follow two of the many paths leading from Newton’s to Euler’s scientific productions, and give an account of Euler’s role in the reception of some of Newton’s ideas, as regards two major topics: mechanics and algebraic analysis. Euler contributed to a re-appropriation of Newtonian science, though transforming it in many relevant aspects. We study this re-appropriation with respect to the mentioned topics and show that it is grounded on the development of Newton’s conceptions within a new conceptual frame also influenced by Descartes’s views sand Leibniz’s formalism.

A Proof-Theoretic Semantic Analysis Of Dynamic Epistemic Logic, Sabine Frittella, Giuseppe Greco, Alexander Kurz, Alessandra Palmigiano, Vlasta Sikimić

Engineering Faculty Articles and Research

The present paper provides an analysis of the existing proof systems for dynamic epistemic logic from the viewpoint of proof-theoretic semantics. Dynamic epistemic logic is one of the best known members of a family of logical systems which have been successfully applied to diverse scientific disciplines, but the proof theoretic treatment of which presents many difficulties. After an illustration of the proof-theoretic semantic principles most relevant to the treatment of logical connectives, we turn to illustrating the main features of display calculi, a proof-theoretic paradigm which has been successfully employed to give a proof-theoretic semantic account of modal and substructural …

Relation Lifting, With An Application To The Many-Valued Cover Modality, Marta Bílková, Alexander Kurz, Daniela Petrişan, Jirí Velebil

Engineering Faculty Articles and Research

We introduce basic notions and results about relation liftings on categories enriched in a commutative quantale. We derive two necessary and sufficient conditions for a 2-functor T to admit a functorial relation lifting: one is the existence of a distributive law of T over the “powerset monad” on categories, one is the preservation by T of “exactness” of certain squares. Both characterisations are generalisations of the “classical” results known for set functors: the first characterisation generalises the existence of a distributive law over the genuine powerset monad, the second generalises preservation of weak pullbacks.

The results presented in this paper …

Nominal Coalgebraic Data Types With Applications To Lambda Calculus, Alexander Kurz, Daniela Petrişan, Paula Severi, Fer-Jan De Vries

Engineering Faculty Articles and Research

We investigate final coalgebras in nominal sets. This allows us to define types of infinite data with binding for which all constructions automatically respect alpha equivalence. We give applications to the infinitary lambda calculus.

Nominal Computation Theory (Dagstuhl Seminar 13422), Mikołaj Bojanczyk, Bartek Klin, Alexander Kurz, Andrew M. Pitts

Engineering Faculty Articles and Research

This report documents the program and the outcomes of Dagstuhl Seminar 13422 “Nominal Computation Theory”. The underlying theme of the seminar was nominal sets (also known as sets with atoms or Fraenkel-Mostowski sets) and they role and applications in three distinct research areas: automata over infinite alphabets, program semantics using nominal sets and nominal calculi of concurrent processes.

Residuated Frames With Applications To Decidability, Nikolaos Galatos, Peter Jipsen

Mathematics, Physics, and Computer Science Faculty Articles and Research

Residuated frames provide relational semantics for substructural logics and are a natural generalization of Kripke frames in intuitionistic and modal logic, and of phase spaces in linear logic. We explore the connection between Gentzen systems and residuated frames and illustrate how frames provide a uniform treatment for semantic proofs of cut-elimination, the finite model property and the finite embeddability property, which imply the decidability of the equational/universal theories of the associated residuated lattice-ordered groupoids. In particular these techniques allow us to prove that the variety of involutive FL-algebras and several related varieties have the finite model property.

Epistemic Updates On Algebras, Alexander Kurz, Alessandra Palmigiano

Engineering Faculty Articles and Research

We develop the mathematical theory of epistemic updates with the tools of duality theory. We focus on the Logic of Epistemic Actions and Knowledge (EAK), introduced by Baltag-Moss-Solecki, without the common knowledge operator. We dually characterize the product update construction of EAK as a certain construction transforming the complex algebras associated with the given model into the complex algebra associated with the updated model. This dual characterization naturally generalizes to much wider classes of algebras, which include, but are not limited to, arbitrary BAOs and arbitrary modal expansions of Heyting algebras (HAOs). As an application of this dual characterization, we …

Dynamic Sequent Calculus For The Logic Of Epistemic Actions And Knowledge, Giuseppe Greco, Alexander Kurz, Alessandra Palmigiano

Engineering Faculty Articles and Research

"Dynamic Logics (DLs) form a large family of nonclassical logics, and perhaps the one enjoying the widest range of applications. Indeed, they are designed to formalize change caused by actions of diverse nature: updates on the memory state of a computer, displacements of moving robots in an environment, measurements in models of quantum physics, belief revisions, knowledge updates, etc. In each of these areas, DL-formulas express properties of the model encoding the present state of affairs, as well as the pre- and post-conditions of a given action. Actions are semantically represented as transformations of one model into another, encoding the …

Nominal Regular Expressions For Languages Over Infinite Alphabets, Alexander Kurz, Tomoyuki Suzuki, Emilio Tuosto

Engineering Faculty Articles and Research

We propose regular expressions to abstractly model and study properties of resource-aware computations. Inspired by nominal techniques – as those popular in process calculi – we extend classical regular expressions with names (to model computational resources) and suitable operators (for allocation, deallocation, scoping of, and freshness conditions on resources). We discuss classes of such nominal regular expressions, show how such expressions have natural interpretations in terms of languages over infinite alphabets, and give Kleene theorems to characterise their formal languages in terms of nominal automata.

From Velocities To Fluxions, Marco Panza

MPP Published Research

"Though the De Methodis results, for its essential structure and content, from a re-elaboration of a previous unfinished treatise composed in the Fall of 1666—now known, after Whiteside, as The October 1666 tract on fluxions ([22], I, pp. 400-448)—, the introduction of the term ‘fluxion’ goes together with an important conceptual change concerned with Newton’s understanding of his own achievements. I shall argue that this change marks a crucial step in the origins of analysis, conceived as an autonomous mathematical theory."

Strongly Complete Logics For Coalgebras, Alexander Kurz, Jiří Rosický

Engineering Faculty Articles and Research

Coalgebras for a functor model different types of transition systems in a uniform way. This paper focuses on a uniform account of finitary logics for set-based coalgebras. In particular, a general construction of a logic from an arbitrary set-functor is given and proven to be strongly complete under additional assumptions. We proceed in three parts.

Part I argues that sifted colimit preserving functors are those functors that preserve universal algebraic structure. Our main theorem here states that a functor preserves sifted colimits if and only if it has a finitary presentation by operations and equations. Moreover, the presentation of the …

Completeness For The Coalgebraic Cover Modality, Clemens Kupke, Alexander Kurz, Yde Venema

Engineering Faculty Articles and Research

We study the finitary version of the coalgebraic logic introduced by L. Moss. The syntax of this logic, which is introduced uniformly with respect to a coalgebraic type functor, required to preserve weak pullbacks, extends that of classical propositional logic with a so-called coalgebraic cover modality depending on the type functor. Its semantics is defined in terms of a categorically defined relation lifting operation.

As the main contributions of our paper we introduce a derivation system, and prove that it provides a sound and complete axiomatization for the collection of coalgebraically valid inequalities. Our soundness and completeness proof is algebraic, …

Coalgebraic Logics (Dagstuhl Seminar 12411), Ernst-Erich Doberkat, Alexander Kurz

Engineering Faculty Articles and Research

This report documents the program and the outcomes of Dagstuhl Seminar 12411 “Coalgebraic Logics”. The seminar deals with recent developments in the area of coalgebraic logic, a branch of logics which combines modal logics with coalgebraic semantics. Modal logic finds its uses when reasoning about behavioural and temporal properties of computation and communication, coalgebras have evolved into a general theory of systems. Consequently, it is natural to combine both areas for a mathematical description of system specification. Coalgebraic logics are closely related to the broader categories semantics/formal methods and verification/logic.

Lagrange's Theory Of Analytical Functions And His Ideal Of Purity Of Method, Giovanni Ferraro, Marco Panza

MPP Published Research

We reconstruct essential features of Lagrange’s theory of analytical functions by exhibiting its structure and basic assumptions, as well as its main shortcomings. We explain Lagrange’s notions of function and algebraic quantity, and we concentrate on power-series expansions, on the algorithm for derivative functions, and the remainder theorem—especially on the role this theorem has in solving geometric and mechanical problems. We thus aim to provide a better understanding of Enlightenment mathematics and to show that the foundations of mathematics did not, for Lagrange, concern the solidity of its ultimate bases, but rather purity of method—the generality and internal organization of …

Relation Liftings On Preorders And Posets, Marta Bílková, Alexander Kurz, Daniela Petrişan, Jiří Velebil

Engineering Faculty Articles and Research

The category Rel(Set) of sets and relations can be described as a category of spans and as the Kleisli category for the powerset monad. A set-functor can be lifted to a functor on Rel(Set) iff it preserves weak pullbacks. We show that these results extend to the enriched setting, if we replace sets by posets or preorders. Preservation of weak pullbacks becomes preservation of exact lax squares. As an application we present Moss’s coalgebraic over posets.

Towards Nominal Formal Languages, Alexander Kurz, Tomoyuki Suzuki, Emilio Tuosto

Engineering Faculty Articles and Research

We introduce formal languages over infinite alphabets where words may contain binders.We define the notions of nominal language, nominal monoid, and nominal regular expressions. Moreover, we extend history-dependent automata (HD-automata) by adding stack, and study the recognisability of nominal languages.

Generic Trace Logics, Christian Kissig, Alexander Kurz

Engineering Faculty Articles and Research

We combine previous work on coalgebraic logic with the coalgebraic traces semantics of Hasuo, Jacobs, and Sokolova.