Institute of Discrete Mathematics and Geometry
Vienna University of Technology
Wiedner Hauptstrasse 8-10/104
1040 Vienna, Austria
Office: DA05A05 (green building)

Google Scholar

Luca San Mauro

I am a postdoctoral fellow at the Institute for Discrete Mathematics and Geometry of Vienna University of Technology, where I am running a two-years research project (2018-2020) funded by the Austrian Science Fund (FWF), entitled Classifying relations via computable reducibility. I also teach logic within the Master in Language and Mind of University of Siena.
Recently, I obtained the Italian habilitation to be Associate Professor of Logic and Philosophy of Science and the Italian habilitation to be Associate Professor of Mathematical Logic.

My research interests lie in computability theory and philosophy of mathematics. Here is my CV.

Journal articles

  1. Word problems and ceers
    (with V. Delle Rose and A. Sorbi)
    forthcoming in Mathematical Logic Quarterly
    Abstract: This note addresses the issue as to which ceers can be realized by word problems of computably enumerable (or, simply, c.e.) structures (such as c.e. semigroups, groups, and rings), where being realized means to fall in the same reducibility degree (under the notion of reducibility for equivalence relations usually called "computable reducibility"), or in the same isomorphism type (with the isomorphism induced by a computable function), or in the same strong isomorphism type (with the isomorphism induced by a computable permutation of the natural numbers). We observe for instance that every ceer is isomorphic to the word problem of some c.e. semigroup, but (answering a question of Gao and Gerdes) not every ceer is in the same reducibility degree of the word problem of some finitely presented semigroup, nor is in the same reducibility degree of some non-periodic semigroup. We also show that the ceer provided by provable equivalence of Peano Arithmetic is in the same strong isomorphim type as the word problem of some non-commutative and non-Boolean c.e. ring.
  2. Degrees of bi-embeddable categoricity
    (with N. Bazhenov, E. Fokina, and D. Rossegger)
    forthcoming in Computability
    Abstract: 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 \(\mathcal{A}\) as the family of Turing degrees that compute embeddings between any computable bi-embeddable copies of \(\mathcal{A}\); the degree of bi-embeddable categoricity of \(\mathcal{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 we show that every degree d.c.e. above \(\mathbf{0}^{(\alpha)}\) for \(\alpha\) a computable successor ordinal and \(\mathbf{0}^{(\lambda)}\) for \(\lambda\) a computable limit ordinal is a degree of bi-embeddable categoricity. We also give examples of families of degrees that are not bi-embeddable categoricity spectra.
  3. Learning family of algebraic structures from informant
    (with N. Bazhenov and E. Fokina)
    forthcoming in Information and Computation
    Abstract: 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 class \(\mathbf{InfEx_\cong}\), consisting of the structures whose isomorphism types can be learned in the limit. We show that a family of structures \(\mathbb{K}\) is \(\mathbf{InfEx_\cong}\)-learnable if and only if the structures from \(\mathbb{K}\) can be distinguished in terms of their \(\Sigma^{inf}_2\)-theories. We apply this characterization to familiar cases and we show the following: there is an infinite learnable family of distributive lattices; no pair of Boolean algebras is learnable; no infinite family of linear orders is learnable.
  4. Speech acts in mathematics
    (with M. Ruffino and G. Venturi)
    forthcoming in Synthese
    Abstract: We offer a novel picture of mathematical language from the perspective of speech act theory. There are distinct such acts within mathematics (not just assertions), 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 (which tends to see mathematics as a realm in which no pragmatic features of ordinary language are present) and in speech act theory (which tends to pay attention solely to communication in ordinary language but not to formal languages). As we will comment, the recognition of distinct illocutionary acts within logic and mathematics and the incorporation of illocutionary force indicators in the formal language for both goes back to Frege's conception of these topics. We are, therefore, going back to a Fregean perspective. This paper is part of a larger project of applying contemporary speech act theory to the scientific language of mathematics in order to uncover the varieties and regular combinations of illocutionary acts (silently) present in it. For reasons of space, we here concentrate only on assertive and declarative acts within mathematics, leaving the investigation of other kinds of acts for a future occasion.
  5. Minimal Equivalence Relations in Hyperarithmetical and Analytical Hierarchies
    (with N. Bazhenov, M. Mustafa, and M. Yamaleev)
    forthcoming in Lobachevskii Journal of Mathematics
    Abstract: A standard tool for classifying the complexity of equivalence relations on \(\omega\) is provided by computable reducibility. This reducibility gives rise to a rich degree structure. The paper studies equivalence relations, which induce minimal degrees with respect to computable reducibility. Let \(\Gamma\) be one of the following classes: \(\Sigma^0_{\alpha}\), \(\Pi^0_{\alpha}\), \(\Sigma^1_n\), or \(\Pi^1_n\), where \(\alpha \geq 2\) is a computable ordinal and \(n\) is a non-zero natural number. We prove that there are infinitely many pairwise incomparable minimal equivalence relations that are properly in \(\Gamma\).
  6. Classifying equivalence relations in the Ershov hierarchy
    (with N. Bazhenov, M. Mustafa, A. Sorbi, M. Yamaleev)
    forthcoming in Archive for Mathematical Logic
    Abstract: Computably enumerable equivalence relations (ceers) received a lot of attention in the literature. The standard tool to classify ceers is provided by the computable reducibility \(\leq_c\). This gives rise to a rich degree-structure. In this paper, we lift the study of \(c\)-degrees to the \(\Delta^0_2\) 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 \(\leq_c\) on the \(\Sigma^{-1}_{a}\smallsetminus \Pi^{-1}_a\) equivalence relations. A special focus of our work is on the (non)existence of infima and suprema of \(c\)-degrees.
  7. At least one black sheep: Pragmatics and the language of mathematics
    (with M. Ruffino and G. Venturi)
    Journal of Pragmatics, 160, 114-119, 2020
    Abstract: In this paper we argue, against a somewhat standard view, that pragmatic phenomena occur in mathematical language. We provide concrete examples supporting this thesis.
  8. Bi-embeddability spectra and bases of spectra
    (with E. Fokina and D. Rossegger)
    Mathematical Logic Quaterly, 65(2), 228-236, 2019
    Abstract: We study degree spectra of structures with respect to the bi-embeddability relation. The bi-embeddability spectrum of a structure is the family of Turing degrees of its bi-embeddable copies. To facilitate our study we introduce the notions of bi-embeddable triviality and basis of a spectrum. Using bi-embeddable triviality we show that several known families of degrees are bi-embeddability spectra of structures. We then characterize the bi-embeddability spectra of linear orderings and study bases of bi-embeddability spectra of strongly locally finite graphs.
  9. Measuring the complexity of reductions between equivalence relations
    (with E. Fokina and D. Rossegger)
    Computability, 8(3/4), 265-280, 2019
    Abstract: 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 spectrum of computably enumerable equivalence relations with no countable basis and a reducibility spectrum of computably enumerable equivalence relations which is downward dense, thus has no basis.
  10. Degrees of bi-embeddable categoricity of equivalence structures
    (with N. Bazhenov, E. Fokina, and D. Rossegger)
    Archive for Mathematical Logic, 58(5/6), 543-563, 2019
    Abstract: We study the algorithmic complexity of embeddings between bi-embeddable equivalence structures. We define the notions of computable bi-embeddable categoricity, (relative) \(\Delta^0_\alpha\) 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 \(\Delta^0_\alpha\) bi-embeddable categoricity and relative \(\Delta^0_\alpha\) bi-embeddable categoricity coincide for equivalence structures for \(\alpha=1,2,3\). We also prove that computable equivalence structures have degree of bi-embeddable categoricity \(\mathbf{0}\),\(\mathbf{0'}\), or \(\mathbf{0''}\). We furthermore obtain results on the index set complexity of computable equivalence structure with respect to bi-embeddability.
  11. Computable bi-embeddable categoricity
    (with N. Bazhenov, E. Fokina, and D. Rossegger)
    Algebra and Logic, 57(5), 392-396, 2018
    Abstract: We study the algorithmic complexity of isomorphic embeddings between computable structures.
  12. Trial and error mathematics: Completions of theories
    (with J. Amidei, U. Andrews, D. Pianigiani, and A. Sorbi)
    Journal of Logic and Computation, 29(1), 157-184, 2019
    Abstract: 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 of revision. In the present paper we consider a third class of systems, that of \(p\)-dialectical systems, that naturally combine features coming from the two other cases. We prove several results about \(p\)-dialectical systems and the sets that they represent. Then we focus on the completions of first-order theories. In doing so, we consider systems with connectives, i.e. systems that encode the rules of classical logic. We show that any consistent system with connectives represents the completion of a given theory. We prove that dialectical and \(q\)-dialectical systems coincide with respect to the completions that they can represent. Yet, \(p\)-dialectical systems are more powerful; we exhibit a \(p\)-dialectical system representing a completion of Peano Arithmetic that is neither dialectical nor \(q\)-dialectical.
  13. Trial and error mathematics II: Dialectical sets and quasidialectical sets, their degrees, and their distribution within the class of limit sets
    (with J. Amidei, D. Pianigiani and A. Sorbi)
    Review of Symbolic Logic, 9(4), 810-835, 2016
    Abstract: This paper is a continuation of Amidei, Pianigiani, San Mauro, Simi, and Sorbi (2016), where we have introduced the quasidialectical systems, which are abstract deductive systems designed to provide, in line with Lakatos' views, a formalization of trial and error mathematics more adherent to the real mathematical practice of revision than Magari's original dialectical systems. In this paper we prove that the two models of deductive systems (dialectical systems and quasidialectical systems) have in some sense the same information content, in that they represent two classes of sets (the dialectical sets and the quasidialectical sets, respectively), which have the same Turing degrees (namely, the computably enumerable Turing degrees), and the same enumeration degrees (namely, the \(\Pi^0_1\) enumeration degrees). Nonetheless, dialectical sets and quasidialectical sets do not coincide. Even restricting our attention to the so-called loopless quasidialectical sets, we show that the quasidialectical sets properly extend the dialectical sets. As both classes consist of \(\Delta^0_2\) sets, the extent to which the two classes differ is conveniently measured using the Ershov hierarchy: indeed, the dialectical sets are \(\omega\)-computably enumerable (close inspection also shows that there are dialectical sets which do not lie in any finite level; and in every finite level \(n \geq 2\) of the Ershov hierarchy there is a dialectical set which does not lie in the previous level); on the other hand, the quasidialectical sets spread out throughout all classes of the hierarchy (close inspection shows that for every ordinal notation a of a nonzero computable ordinal, there is a quasidialectical set lying in \(\Sigma^{-1}_{\alpha}\), but in none of the preceding levels).
  14. Trial and error mathematics I: Dialectical and quasidialectical systems
    (with J. Amidei, D. Pianigiani, G. Simi, and A. Sorbi)
    Review of Symbolic Logic, 9(2), 299-324, 2016
    Abstract: We define and study quasidialectical systems, which are an extension of Magari's dialectical systems, designed to make Magari's formalization of trial and error mathematics more adherent to the real mathematical practice of revision: our proposed extension follows, and in several regards makes more precise, varieties of empiricist positions à la Lakatos. We prove several properties of quasidialectical systems and of the sets that they represent, called quasidialectical sets. In particular, we prove that the quasidialectical sets are \(\Delta^0_2\) sets in the arithmetical hierarchy. We distinguish between "loopless" quasidialectal systems, and quasidialectical systems "with loops". The latter ones represent exactly those coinfinite c.e. sets, that are not simple. In a subsequent paper we will show that whereas the dialectical sets are \(\omega\)-c.e., the quasidialectical sets spread out throughout all classes of the Ershov hierarchy of the \(\Delta^0_2\) sets.
  15. Universal computably enumerable equivalence relations
    (with U. Andrews, S. Lempp, J.S. Miller, K.M. Ng, and A. Sorbi)
    Journal of Symbolic Logic, 79, 60-88, 2014
    Abstract: We study computably enumerable equivalence relations (ceers) under the reducibility \(R \leq S\) if there exists a computable function \(f\) such that, for every \(x, y\), \(x R y\) if and only if \(f (x) S f (y)\). We show that the degrees of ceers under the equivalence relation generated by ≤ form a bounded poset that is neither a lower semilattice, nor an upper semilattice, and its first order theory is undecidable. We then study the universal ceers. We show that 1) the uniformly effectively inseparable ceers are universal, but there are effectively inseparable ceers that are not universal; 2) a ceer \(R\) is universal if and only if \(R' ≤ R\), where \(R'\) denotes the halting jump operator introduced by Gao and Gerdes (answering an open question of Gao and Gerdes); and 3) both the index set of the universal ceers and the index set of the uniformly effectively inseparable ceers are \(\Sigma^0_3\)-complete (the former answering an open question of Gao and Gerdes).

Book chapters and conference papers

  1. Comparing the isomorphism types of equivalence structures and preorders
    (with N. Bazhenov and L. San Mauro), submitted
    Abstract: A general theme of computable structure theory is to investigate when structures have copies of a given complexity \(\Gamma\). We discuss such problem for the case of equivalence structures and preorders. We show that there is a \(\Pi^0_1\) equivalence structure with no \(\Sigma^0_1\) copy, and in fact that the isomorphism types realized by the \(\Pi^0_1\) equivalence structures coincide with those realized by the \(\Delta^0_2\) equivalence structures. We also construct a \(\Sigma^0_1\) preorder with no \(\Pi^0_1\) copy.
  2. Limit learning equivalence structures
    (with E. Fokina and T. Koetzing)
    Proceedings of Machine Learning Research, 98, 383-403, 2019
    Abstract: While most research in Gold-style learning focuses on learning formal languages, we consider the identification of computable structures, specifically equivalence structures. In our core model the learner gets more and more information about which pairs of elements of a structure are related and which are not. The aim of the learner is to find (an effective description of) the isomorphism type of the structure presented in the limit. In accordance with language learning we call this learning criterion \(\mathbf{InfEx}\)-learning (explanatory learning from informant). Our main contribution is a complete characterization of which families of equivalence structures are \(\mathbf{InfEx}\)-learnable. This characterization allows us to derive a bound of \(\mathbf{0''}\) on the computational complexity required to learn uniformly enumerable families of equivalence structures. We also investigate variants of \(\mathbf{InfEx}\)-learning, including learning from text (where the only information provided is which elements are related, and not which elements are not related) and finite learning (where the first actual conjecture of the learner has to be correct). Finally, we show how learning families of structures relates to learning classes of languages by mapping learning tasks for structures to equivalent learning tasks for languages.
  3. Church-Turing thesis, in practice
    in M. Piazza and G. Pulcini (eds), Truth, Existence and Explanation, Springer, 225-248, 2018
    Abstract: We aim at providing a philosophical analysis of the notion of "proof by Church's Thesis", which is – in a nutshell – the conceptual device that permits to rely on informal methods when working in Computability Theory. This notion allows, in most cases, to not specify the background model of computation in which a given algorithm – or a construction – is framed. In pursuing such analysis, we carefully reconstruct the development of this notion (from Post to Rogers, to the present days), and we focus on some classical constructions of the field, such as the construction of a simple set. Then, we make use of this focus in order to support the following encompassing claim (which opposes to a somehow commonly received view): the informal side of Computability, consisting of the large class of methods typically employed in the proofs of the field, is not fully reducible to its formal counterpart.
  4. Direzioni della logica in Italia: la teoria (classica) della ricorsività
    (with P. Cintioli and A. Sorbi)
    in H. Hosni, G. Lolli, C. Toffalori (eds.), Le direzioni della ricerca logica in Italia 2, Edizioni ETS, 195-234, 2018
  5. Degree spectra of structures with respect to the bi-embeddability relation
    (with E. Fokina and D. Rossegger)
    Proceedings of the 11th Panhellenic Logic Symposium, 32-38, 2017
  6. Computable bi-embeddable categoricity of equivalence structures
    (with N. Bazhenov, E. Fokina, and D. Rossegger)
    Proceedings of the 11th Panhellenic Logic Symposium, 126-132, 2017
  7. Reducibility and bi-reducibility spectra of equivalence relations
    (with E. Fokina and D. Rossegger)
    Proceedings of the 11th Panhellenic Logic Symposium, 83-89, 2017
  8. Naturalness in mathematics
    (with G. Venturi)
    in G. Lolli, M. Panza, G. Venturi (eds.), From Logic to Practice, Springer, 277-313, 2014
    Abstract: In mathematical literature, it is quite common to make reference to an informal notion of naturalness: axioms or definitions may be defined as “natural,” and part of a proof may deserve the same label (i.e., “in a natural way…”). Our aim is to provide a philosophical account of these occurrences. The paper is divided in two parts. In the first part, some statistical evidence is considered, in order to show that the use of the word “natural,” within the mathematical discourse, largely increased in the last decades. Then, we attempt to develop a philosophical framework in order to encompass such an evidence. In doing so, we outline a general method apt to deal with this kind of vague notions – such as naturalness – emerging in mathematical practice. In the second part, we mainly tackle the following question: is naturalness a static or a dynamic notion? Thanks to the study of a couple of case studies, taken from set theory and computability theory, we answer that the notion of naturalness – as it is used in mathematics – is a dynamic one, in which normativity plays a fundamental role.