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.
I am also running a two-years research project (2018-2020) funded by the Austrian Science Fund (FWF), entitled Classifying relations via computable reducibility.

My research interests lie in computability theory and philosophy of mathematics.

Journal articles

  1. Classifying Equivalence relations in the Ershov hierarchy
    (with N. Bazhenov, M. Mustafa, A. Sorbi, M. Yamaleev), submitted
    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.
  2. Bi-embeddability spectra and bases of spectra
    (with E. Fokina and D. Rossegger)
    forthcoming in Mathematical Logic Quaterly
    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.
  3. Measuring the complexity of reductions between equivalence relations
    (with E. Fokina and D. Rossegger)
    forthcoming in Computability
    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.
  4. Degrees of bi-embeddable categoricity of equivalence structures
    (with N. Bazhenov, E. Fokina, and D. Rossegger)
    forthcoming in Archive for Mathematical Logic
    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.
  5. 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.
  6. 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.
  7. 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).
  8. 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.
  9. 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, discussion notes, and conference papers

  1. 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.
  2. At least one black sheep: Pragmatics and the language of mathematics
    (with M. Ruffino and G. Venturi)
    forthcoming in Journal of Pragmatics
    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.
  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.