Logic and Foundations Commons^™

Many-Valued Coalgebraic Logic: From Boolean Algebras To Primal Varieties, Alexander Kurz, Wolfgang Poiger

Engineering Faculty Articles and Research

We study many-valued coalgebraic logics with primal algebras of truth-degrees. We describe a way to lift algebraic semantics of classical coalgebraic logics, given by an endofunctor on the variety of Boolean algebras, to this many-valued setting, and we show that many important properties of the original logic are inherited by its lifting. Then, we deal with the problem of obtaining a concrete axiomatic presentation of the variety of algebras for this lifted logic, given that we know one for the original one. We solve this problem for a class of presentations which behaves well with respect to a lattice structure …

Completeness Of Nominal Props, Samuel Balco, Alexander Kurz

Engineering Faculty Articles and Research

We introduce nominal string diagrams as string diagrams internal in the category of nominal sets. This leads us to define nominal PROPs and nominal monoidal theories. We show that the categories of ordinary PROPs and nominal PROPs are equivalent. This equivalence is then extended to symmetric monoidal theories and nominal monoidal theories, which allows us to transfer completeness results between ordinary and nominal calculi for string diagrams.

The Agnostic Structure Of Data Science Methods, Domenico Napoletani, Marco Panza, Daniele Struppa

MPP Published Research

In this paper we argue that data science is a coherent and novel approach to empirical problems that, in its most general form, does not build understanding about phenomena. Within the new type of mathematization at work in data science, mathematical methods are not selected because of any relevance for a problem at hand; mathematical methods are applied to a specific problem only by `forcing’, i.e. on the basis of their ability to reorganize the data for further analysis and the intrinsic richness of their mathematical structure. In particular, we argue that deep learning neural networks are best understood within …

Analysis, Constructions And Diagrams In Classical Geometry, Marco Panza

MPP Published Research

Greek ancient and early modern geometry necessarily uses diagrams. Among other things, these enter geometrical analysis. The paper distinguishes two sorts of geometrical analysis and shows that in one of them, dubbed “intra-confgurational” analysis, some diagrams necessarily enter as outcomes of a purely material gesture, namely not as result of a codifed constructive procedure, but as result of a free-hand drawing.

Diagrams In Intra-Configurational Analysis, Marco Panza, Gianluca Longa

MPP Published Research

In this paper we would like to attempt to shed some light on the way in which diagrams enter into the practice of ancient Greek geometrical analysis. To this end, we will first distinguish two main forms of this practice, i.e., trans-configurational and intra-configurational. We will then argue that, while in the former diagrams enter in the proof essentially in the same way (mutatis mutandis) they enter in canonical synthetic demonstrations, in the latter, they take part in the analytic argument in a specific way, which has no correlation in other aspects of classical geometry. In intra-configurational analysis, diagrams represent …

Semi De Morgan Logic Properly Displayed, Giuseppe Greco, Fei Qin, M. Andrew Moshier, Alessandra Palmigiano

Mathematics, Physics, and Computer Science Faculty Articles and Research

In the present paper, we endow semi De Morgan logic and a family of its axiomatic extensions with proper multi-type display calculi which are sound, complete, conservative, and enjoy cut elimination and subformula property. Our proposal builds on an algebraic analysis of the variety of semi De Morgan algebras, and applies the guidelines of the multi-type methodology in the design of display calculi.

Extending Set Functors To Generalised Metric Spaces, Adriana Balan, Alexander Kurz, Jiří Velebil

Mathematics, Physics, and Computer Science Faculty Articles and Research

For a commutative quantale V, the category V-cat can be perceived as a category of generalised metric spaces and non-expanding maps. We show that any type constructor T (formalised as an endofunctor on sets) can be extended in a canonical way to a type constructor T_V on V-cat. The proof yields methods of explicitly calculating the extension in concrete examples, which cover well-known notions such as the Pompeiu-Hausdorff metric as well as new ones.

Conceptually, this allows us to to solve the same recursive domain equation X ≅ TX in different categories (such as sets and metric spaces) and …

Asymptotic Quasi-Completeness And Zfc, Mirna Džamonja, Marco Panza

MPP Published Research

The axioms ZFC of first order set theory are one of the best and most widely accepted, if not perfect, foundations used in mathematics. Just as the axioms of first order Peano Arithmetic, ZFC axioms form a recursively enumerable list of axioms, and are, then, subject to Gödel’s Incompleteness Theorems. Hence, if they are assumed to be consistent, they are necessarily incomplete. This can be witnessed by various concrete statements, including the celebrated Continuum Hypothesis CH. The independence results about the infinite cardinals are so abundant that it often appears that ZFC can basically prove very little about such cardinals. …

Was Frege A Logicist For Arithmetic?, Marco Panza

MPP Published Research

The paper argues that Frege’s primary foundational purpose concerning arithmetic was neither that of making natural numbers logical objects, nor that of making arithmetic a part of logic, but rather that of assigning to it an appropriate place in the architectonics of mathematics and knowledge, by immersing it in a theory of numbers of concepts and making truths about natural numbers, and/or knowledge of them transparent to reason without the medium of senses and intuition.

Enthymemathical Proofs And Canonical Proofs In Euclid’S Plane Geometry, Abel Lassalle, Marco Panza

MPP Published Research

Since the application of Postulate I.2 in Euclid’s Elements is not uniform, one could wonder in what way should it be applied in Euclid’s plane geometry. Besides legitimizing questions like this from the perspective of a philosophy of mathematical practice, we sketch a general perspective of conceptual analysis of mathematical texts, which involves an extended notion of mathematical theory as system of authorizations, and an audience-dependent notion of proof.

Fast Adjustable Npn Classification Using Generalized Symmetries, Xuegong Zhou, Lingli Wang, Peiyi Zhao, Alan Mishchenko

Mathematics, Physics, and Computer Science Faculty Articles and Research

NPN classification of Boolean functions is a powerful technique used in many logic synthesis and technology mapping tools in FPGA design flows. Computing the canonical form of a function is the most common approach of Boolean function classification. In this paper, a novel algorithm for computing NPN canonical form is proposed. By exploiting symmetries under different phase assignments and higher-order symmetries of Boolean functions, the search space of NPN canonical form computation is pruned and the runtime is dramatically reduced. The algorithm can be adjusted to be a slow exact algorithm or a fast heuristic algorithm with lower quality. For …

Review Of G. Israel, Meccanicismo. Trionfi E Miserie Della Visione Meccanica Del Mondo, Marco Panza

MPP Published Research

"This is Giorgio's Israel last book, which appeared only a few weeks after his untimely death, in September 2015. For many reasons, it can be considered as his intellectual legacy, since it comes back, in a new and organic way, to many of the research topics to which he devoted his life and his many publications, which include several papers in Historia Mathematica. One of these papers, co-authored with M. Menghini, appeared in vol. 25/4, 1998 and was devoted to Poincaré's and Enriques's opposite views on qualitative analysis, which is a theme also dealt with in this book (pp. 117–122)."

On Tarski's Axiomatic Foundations Of The Calculus Of Relations, Hajnal Andréka, Steven Givant, Peter Jipsen, István Németi

Mathematics, Physics, and Computer Science Faculty Articles and Research

It is shown that Tarski’s set of ten axioms for the calculus of relations is independent in the sense that no axiom can be derived from the remaining axioms. It is also shown that by modifying one of Tarski’s axioms slightly, and in fact by replacing the right-hand distributive law for relative multiplication with its left-hand version, we arrive at an equivalent set of axioms which is redundant in the sense that one of the axioms, namely the second involution law, is derivable from the other axioms. The set of remaining axioms is independent. Finally, it is shown that if …

Relation Algebras, Idempotent Semirings And Generalized Bunched Implication Algebras, Peter Jipsen

Mathematics, Physics, and Computer Science Faculty Articles and Research

This paper investigates connections between algebraic structures that are common in theoretical computer science and algebraic logic. Idempotent semirings are the basis of Kleene algebras, relation algebras, residuated lattices and bunched implication algebras. Extending a result of Chajda and Länger, we show that involutive residuated lattices are determined by a pair of dually isomorphic idempotent semirings on the same set, and this result also applies to relation algebras. Generalized bunched implication algebras (GBI-algebras for short) are residuated lattices expanded with a Heyting implication. We construct bounded cyclic involutive GBI-algebras from so-called weakening relations, and prove that the class of weakening …

On Benacerraf’S Dilemma, Again, Marco Panza

MPP Published Research

In spite of its enormous influence, Benacerraf’s dilemma admits no standard unanimously accepted formulation. This mainly depends on Benacerraf’s having originally presented it in a quite colloquial way, by avoiding any compact, somehow codified, but purportedly comprehensive formulation (Benacerraf 1973 cf. p. 29).

Quasivarieties And Varieties Of Ordered Algebras: Regularity And Exactness, Alexander Kurz

Engineering Faculty Articles and Research

We characterise quasivarieties and varieties of ordered algebras categorically in terms of regularity, exactness and the existence of a suitable generator. The notions of regularity and exactness need to be understood in the sense of category theory enriched over posets.

We also prove that finitary varieties of ordered algebras are cocompletions of their theories under sifted colimits (again, in the enriched sense).

Features Of Agent-Based Models, Reiko Heckel, Alexander Kurz, Edmund Chattoe-Brown

Engineering Faculty Articles and Research

The design of agent-based models (ABMs) is often ad-hoc when it comes to defining their scope. In order for the inclusion of features such as network structure, location, or dynamic change to be justified, their role in a model should be systematically analysed. We propose a mechanism to compare and assess the impact of such features. In particular we are using techniques from software engineering and semantics to support the development and assessment of ABMs, such as graph transformations as semantic representations for agent-based models, feature diagrams to identify ingredients under consideration, and extension relations between graph transformation systems to …

Foreword: Special Issue On Coalgebraic Logic, Alexander Kurz

Engineering Faculty Articles and Research

The second Dagstuhl seminar on coalgebraic logics took place from October 7-12, 2012, in the Leibniz Forschungszentrum Schloss Dagstuhl, following a successful earlier one in December 2009. From the 44 researchers who attended and the 30 talks presented, this collection highlights some of the progress that has been made in the field. We are grateful to Giuseppe Longo and his interest in a special issue in Mathematical Structures in Computer Science.

The Positivication Of Coalgebraic Logics, Fredrik Dahlqvist, Alexander Kurz

Engineering Faculty Articles and Research

We present positive coalgebraic logic in full generality, and show how to obtain a positive coalgebraic logic from a boolean one. On the model side this involves canonically computing a endofunctor T': Pos->Pos from an endofunctor T: Set->Set, in a procedure previously defined by the second author et alii called posetification. On the syntax side, it involves canonically computing a syntax-building functor L': DL->DL from a syntax-building functor L: BA->BA, in a dual procedure which we call positivication. These operations are interesting in their own right and we explicitly compute posetifications and positivications in the case …

Platonismes, Marco Panza

MPP Published Research

Selon la vulgata philosophique, le platonisme concernant un certain domaine de recherche est la thèse affirmant que ce domaine concerne des objets qui lui sont propres, dont l’existence est indépendante de l’activité cognitive humaine. Souvent, dans la même vulgata on parle aussi de platonisme pour se référer à une thèse un peu différente, d’après laquelle ce qu’on dit concernant ce domaine est vrai ou faux indépendamment de toute justification ou réfutation que l’on puisse apporter. Naturellement, si parmi les énoncées ayant trait à ce demain, il y en a qu’on peut prendre comme particulièrement surs du fait d’en avoir une …

Kolmogorov’S Axioms For Probabilities With Values In Hyperbolic Numbers, Daniel Alpay, M. E. Luna-Elizarrarás, Michael Shapiro

Mathematics, Physics, and Computer Science Faculty Articles and Research

We introduce the notion of a probabilistic measure which takes values in hyperbolic numbers and which satisfies the system of axioms generalizing directly Kolmogorov’s system of axioms. We show that this new measure verifies the usual properties of a probability; in particular, we treat the conditional hyperbolic probability and we prove the hyperbolic analogues of the multiplication theorem, of the law of total probability and of Bayes’ theorem. Our probability may take values which are zero–divisors and we discuss carefully this peculiarity.

Abstraction And Epistemic Economy, Marco Panza

MPP Published Research

Most of the arguments usually appealed to in order to support the view that some abstraction principles are analytic depend on ascribing to them some sort of existential parsimony or ontological neutrality, whereas the opposite arguments, aiming to deny this view, contend this ascription. As a result, other virtues that these principles might have are often overlooked. Among them, there is an epistemic virtue which I take these principles to have, when regarded in the appropriate settings, and which I suggest to call ‘epistemic economy’. My purpose is to isolate and clarify this notion by appealing to some examples concerning …

Multi-Type Display Calculus For Dynamic Epistemic Logic, Sabine Frittella, Giuseppe Greco, Alexander Kurz, Alessandra Palmigiano, Vlasta Sikimić

Engineering Faculty Articles and Research

In the present paper, we introduce a multi-type display calculus for dynamic epistemic logic, which we refer to as Dynamic Calculus. The displayapproach is suitable to modularly chart the space of dynamic epistemic logics on weaker-than-classical propositional base. The presence of types endows the language of the Dynamic Calculus with additional expressivity, allows for a smooth proof-theoretic treatment, and paves the way towards a general methodology for the design of proof systems for the generality of dynamic logics, and certainly beyond dynamic epistemic logic. We prove that the Dynamic Calculus adequately captures Baltag-Moss-Solecki’s dynamic epistemic logic, and enjoys Belnap-style cut …

Multi-Type Display Calculus For Propositional Dynamic Logic, Sabine Frittella, Giuseppe Greco, Alexander Kurz, Alessandra Palmigiano

Engineering Faculty Articles and Research

We introduce a multi-type display calculus for Propositional Dynamic Logic (PDL). This calculus is complete w.r.t. PDL, and enjoys Belnap-style cut-elimination and subformula property.

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 …

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.