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

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 (...) of a natural logic and assume instead the meaning modulation of nonlogical terms. (shrink)

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 (...) on the index set complexity of computable equivalence structure with respect to bi-embeddability. (shrink)

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 (...) we show that every degree d.c.e above 0(α) for α a computable successor ordinal and 0(λ) for λ 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. (shrink)

In this paper we argue, against a somewhat standard view, that pragmatic phenomena occur in mathematical language. We provide concrete examples supporting this thesis.

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. (...) A special focus of our work is on the existence of infima and suprema of c-degrees. (shrink)

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

We study the algorithmic complexity of isomorphic embeddings between computable structures.

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 (...) mind changes that are needed to learn a given family K. We give a descriptive set-theoretic interpretation of such mind change complexity. We also study how bounding the Turing degree of learners affects the mind change complexity of a given family of algebraic structures. (shrink)

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 (...) a pair of structures which is learnable but no computable learner can learn it. (shrink)

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.

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

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

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 (...) learnable family of distributive lattices; no pair of Boolean algebras is learnable; no infinite family of linear orders is learnable. (shrink)