Logic and Foundations Commons^™

Conditionals And Modalities In Constructive Quantum Logics, Juan P. Aguilera, Guillaume Massas

Mathematics, Physics, and Computer Science Faculty Articles and Research

We investigate logics that generalize both intuitionistic logic and quantum logic. In earlier work, we introduced Ex-logic, an extension of Holliday's fundamental logic that coincides with the intersection of orthologic and the implication-free fragment of intuitionistic logic. In this paper, we add an implication connective to Ex-logic and axiomatize iEx-logic, the intersection of full intuitionistic logic and orthomodular logic with the implication connective interpreted as the Sasaki hook. As a consequence, we obtain a characterization of the lattice of logics extending iEx-logic as the product of the lattice of intermediate logics and the lattice of orthomodular logics. We also explore …

Logic Enriched Over A Quantale, Alexander Kurz

Engineering Faculty Articles and Research

Many-valued logics have a long history in mathematical logic as well as in applications to the semantics of programming languages and to engineering more generally. Typically these logics are rich with features motivated by the particular applications they stem from. In his 1973 article "Metric Spaces, Generalized Logic, and Closed Categories", Lawvere argued that any quantale Ω gives rise to a generalized Ω-valued logic that has as its models the categories enriched over the quantale. This suggests developing a uniform framework for many-valued logics parameterized in a quantale. In this talk we will review some previous and ongoing work in …

Dedekind-Macneille And Related Completions: Subfitness, Regularity, And Booleanness, G. Bezhanishvili, F. Dashiell Jr., M. A. Moshier, Joanne Walters-Wayland

Mathematics, Physics, and Computer Science Faculty Articles and Research

Completions play an important rôle for studying structure by supplying elements that in some sense “ought to be.” Among these, the Dedekind-MacNeille completion is of particular importance. In 1968 Janowitz provided necessary and sufficient conditions for it to be subfit or Boolean. Another natural separation axiom connected to these is regularity. We explore similar characterizations of when closely related completions are subfit, regular, or Boolean. We are mainly interested in the Bruns-Lakser, ideal, and canonical completions, which (unlike the Dedekind-MacNeille completion) satisfy stronger forms of distributivity. The first two are widely used in pointfree topology, while the latter is of …

Smooth And Proper Maps With Respect To A Fibration, Mathieu Anel, Jonathan Weinberger

Engineering Faculty Articles and Research

This paper explain how the geometric notions of local contractibility and properness are related to the Σ-types and Π-types constructors of dependent type theory. We shall see how every Grothendieck fibration comes canonically with such a pair of notions—called smooth and proper maps—and how this recovers the previous examples and many more. This paper uses category theory to reveal a common structure between geometry and logic, with the hope that the parallel will be beneficial to both fields. The style is mostly expository, and the main results are proved in external references.

Canonical Extensions Of Quantale Enriched Categories, Alexander Kurz

MPP Research Seminar

No abstract provided.

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 …

Platonism, De Re, And (Philosophy Of) Mathematical Practice, Marco Panza

MPP Published Research

The chapter advances a reformulation of the classical problem of the nature of mathematical objects (if any), here called “Plato’s problem,” in line with the program of a philosophy of mathematical practice. It then provides a sketch of a platonist solution, following the same perspective. This solution disregards as nonsensical the question of the existence of abstract, and specifically mathematical, objects, by rather focusing on the modalities of our access to them: objects (in general, both concrete and abstract) are regarded as individual contents that we have (or can have) a de re epistemic access to. The question of the …

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 …

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 …

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.

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

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 …

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 …

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.

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

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 …

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.