18 found
Order:
  1.  36
    Universal computably enumerable equivalence relations.Uri Andrews, Steffen Lempp, Joseph S. Miller, Keng Meng Ng, Luca San Mauro & Andrea Sorbi - 2014 - Journal of Symbolic Logic 79 (1):60-88.
  2.  63
    Speech acts in mathematics.Marco Ruffino, Luca San Mauro & Giorgio Venturi - 2020 - Synthese 198 (10):10063-10087.
    We offer a novel picture of mathematical language from the perspective of speech act theory. There are distinct speech acts within mathematics, and, as we intend to show, distinct illocutionary force indicators as well. Even mathematics in its most formalized version cannot do without some such indicators. This goes against a certain orthodoxy both in contemporary philosophy of mathematics and in speech act theory. As we will comment, the recognition of distinct illocutionary acts within logic and mathematics and the incorporation (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  3. On logicality and natural logic.Salvatore Pistoia-Reda & Luca San Mauro - 2021 - Natural Language Semantics 29 (3):501-506.
    In this paper we focus on the logicality of language, i.e. the idea that the language system contains a deductive device to exclude analytic constructions. Puzzling evidence for the logicality of language comes from acceptable contradictions and tautologies. The standard response in the literature involves assuming that the language system only accesses analyticities that are due to skeletons as opposed to standard logical forms. In this paper we submit evidence in support of alternative accounts of logicality, which reject the stipulation (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  4.  49
    Thin Objects Are Not Transparent.Matteo Plebani, Luca San Mauro & Giorgio Venturi - 2023 - Theoria 89 (3):314-325.
    In this short paper, we analyse whether assuming that mathematical objects are “thin” in Linnebo's sense simplifies the epistemology of mathematics. Towards this end, we introduce the notion of transparency and show that not all thin objects are transparent. We end by arguing that, far from being a weakness of thin objects, the lack of transparency of some thin objects is a fruitful characteristic mark of abstract mathematics.
    No categories
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  5.  37
    Degrees of bi-embeddable categoricity of equivalence structures.Nikolay Bazhenov, Ekaterina Fokina, Dino Rossegger & Luca San Mauro - 2019 - Archive for Mathematical Logic 58 (5-6):543-563.
    We study the algorithmic complexity of embeddings between bi-embeddable equivalence structures. We define the notions of computable bi-embeddable categoricity, \ bi-embeddable categoricity, and degrees of bi-embeddable categoricity. These notions mirror the classical notions used to study the complexity of isomorphisms between structures. We show that the notions of \ bi-embeddable categoricity and relative \ bi-embeddable categoricity coincide for equivalence structures for \. We also prove that computable equivalence structures have degree of bi-embeddable categoricity \, or \. We furthermore obtain results (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  6.  28
    On the Structure of Computable Reducibility on Equivalence Relations of Natural Numbers.Uri Andrews, Daniel F. Belin & Luca San Mauro - 2023 - Journal of Symbolic Logic 88 (3):1038-1063.
    We examine the degree structure $\operatorname {\mathrm {\mathbf {ER}}}$ of equivalence relations on $\omega $ under computable reducibility. We examine when pairs of degrees have a least upper bound. In particular, we show that sufficiently incomparable pairs of degrees do not have a least upper bound but that some incomparable degrees do, and we characterize the degrees which have a least upper bound with every finite equivalence relation. We show that the natural classes of finite, light, and dark degrees are (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  7.  23
    Classifying equivalence relations in the Ershov hierarchy.Nikolay Bazhenov, Manat Mustafa, Luca San Mauro, Andrea Sorbi & Mars Yamaleev - 2020 - Archive for Mathematical Logic 59 (7-8):835-864.
    Computably enumerable equivalence relations received a lot of attention in the literature. The standard tool to classify ceers is provided by the computable reducibility \. This gives rise to a rich degree structure. In this paper, we lift the study of c-degrees to the \ case. In doing so, we rely on the Ershov hierarchy. For any notation a for a non-zero computable ordinal, we prove several algebraic properties of the degree structure induced by \ on the \ equivalence relations. (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  8.  10
    Degrees of bi-embeddable categoricity.Luca San Mauro, Nikolay Bazhenov, Ekaterina Fokina & Dino Rossegger - 2021 - Computability 1 (10):1-16.
    We investigate the complexity of embeddings between bi-embeddable structures. In analogy with categoricity spectra, we define the bi-embeddable categoricity spectrum of a structure A as the family of Turing degrees that compute embeddings between any computable bi-embeddable copies of A; the degree of bi-embeddable categoricity of A is the least degree in this spectrum (if it exists). We extend many known results about categoricity spectra to the case of bi-embeddability. In particular, we exhibit structures without degree of bi-embeddable categoricity, and (...)
    Direct download  
     
    Export citation  
     
    Bookmark   1 citation  
  9.  15
    At least one black sheep: Pragmatics and the language of mathematics.Luca San Mauro, Marco Ruffino & Giorgio Venturi - 2020 - Journal of Pragmatics 1 (160):114-119.
    In this paper we argue, against a somewhat standard view, that pragmatic phenomena occur in mathematical language. We provide concrete examples supporting this thesis.
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark   1 citation  
  10. Trial and error mathematics: Dialectical systems and completions of theories.Luca San Mauro, Jacopo Amidei, Uri Andrews, Duccio Pianigiani & Andrea Sorbi - 2019 - Journal of Logic and Computation 1 (29):157-184.
    This paper is part of a project that is based on the notion of a dialectical system, introduced by Magari as a way of capturing trial and error mathematics. In Amidei et al. (2016, Rev. Symb. Logic, 9, 1–26) and Amidei et al. (2016, Rev. Symb. Logic, 9, 299–324), we investigated the expressive and computational power of dialectical systems, and we compared them to a new class of systems, that of quasi-dialectical systems, that enrich Magari’s systems with a natural mechanism (...)
    Direct download  
     
    Export citation  
     
    Bookmark  
  11. Computable bi-embeddable categoricity.Luca San Mauro, Nikolay Bazhenov, Ekaterina Fokina & Dino Rossegger - 2018 - Algebra and Logic 5 (57):392-396.
    We study the algorithmic complexity of isomorphic embeddings between computable structures.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  12.  25
    Trial and error mathematics II: Dialectical sets and quasidialectical sets, their degrees, and their distribution within the class of limit sets.Jacopo Amidei, Duccio Pianigiani, Luca San Mauro & Andrea Sorbi - 2016 - Review of Symbolic Logic 9 (4):810-835.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  13.  62
    Trial and error mathematics I: Dialectical and quasidialectical systems.Jacopo Amidei, Duccio Pianigiani, Luca San Mauro, Giulia Simi & Andrea Sorbi - 2016 - Review of Symbolic Logic 9 (2):299-324.
  14.  12
    Investigating the Computable Friedman–Stanley Jump.Uri Andrews & Luca San Mauro - 2024 - Journal of Symbolic Logic 89 (2):918-944.
    The Friedman–Stanley jump, extensively studied by descriptive set theorists, is a fundamental tool for gauging the complexity of Borel isomorphism relations. This paper focuses on a natural computable analog of this jump operator for equivalence relations on $\omega $, written ${\dotplus }$, recently introduced by Clemens, Coskey, and Krakoff. We offer a thorough analysis of the computable Friedman–Stanley jump and its connections with the hierarchy of countable equivalence relations under the computable reducibility $\leq _c$. In particular, we show that this (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  15.  24
    Calculating the mind-change complexity of learning algebraic structures.Luca San Mauro, Nikolay Bazhenov & Vittorio Cipriani - 2022 - In Ulrich Berger, Johanna N. Y. Franklin, Florin Manea & Arno Pauly (eds.), Revolutions and Revelations in Computability. pp. 1-12.
    This paper studies algorithmic learning theory applied to algebraic structures. In previous papers, we have defined our framework, where a learner, given a family of structures, receives larger and larger pieces of an arbitrary copy of a structure in the family and, at each stage, is required to output a conjecture about the isomorphism type of such a structure. The learning is successful if there is a learner that eventually stabilizes to a correct conjecture. Here, we analyze the number of (...)
    Direct download  
     
    Export citation  
     
    Bookmark  
  16.  9
    Learning families of algebraic structures from informant.Luca San Mauro, Nikolay Bazhenov & Ekaterina Fokina - 2020 - Information And Computation 1 (275):104590.
    We combine computable structure theory and algorithmic learning theory to study learning of families of algebraic structures. Our main result is a model-theoretic characterization of the learning type InfEx_\iso, consisting of the structures whose isomorphism types can be learned in the limit. We show that a family of structures is InfEx_\iso-learnable if and only if the structures can be distinguished in terms of their \Sigma^2_inf-theories. We apply this characterization to familiar cases and we show the following: there is an infinite (...)
    Direct download  
     
    Export citation  
     
    Bookmark  
  17.  5
    Measuring the complexity of reductions between equivalence relations.Luca San Mauro, Ekaterina Fokina & Dino Rossegger - 2019 - Computability 3 (8):265-280.
    Computable reducibility is a well-established notion that allows to compare the complexity of various equivalence relations over the natural numbers. We generalize computable reducibility by introducing degree spectra of reducibility and bi-reducibility. These spectra provide a natural way of measuring the complexity of reductions between equivalence relations. We prove that any upward closed collection of Turing degrees with a countable basis can be realised as a reducibility spectrum or as a bi-reducibility spectrum. We show also that there is a reducibility (...)
    Direct download  
     
    Export citation  
     
    Bookmark  
  18.  11
    On the Turing complexity of learning finite families of algebraic structures.Luca San Mauro & Nikolay Bazhenov - 2021 - Journal of Logic and Computation 7 (31):1891-1900.
    In previous work, we have combined computable structure theory and algorithmic learning theory to study which families of algebraic structures are learnable in the limit (up to isomorphism). In this paper, we measure the computational power that is needed to learn finite families of structures. In particular, we prove that, if a family of structures is both finite and learnable, then any oracle which computes the Halting set is able to achieve such a learning. On the other hand, we construct (...)
    Direct download  
     
    Export citation  
     
    Bookmark