This paper is about two topics: 1. systems of explicit mathematics with universes and a non-constructive quantification operator $\mu$; 2. iterated fixed point theories with ordinals. We give a proof-theoretic treatment of both families of theories; in particular, ordinal theories are used to get upper bounds for explicit theories with finitely many universes.

We present a search engine for mathematical formulae. The MathWebSearch system harvests the web for content representations (currently MathML and OpenMath) of formulae and indexes them with substitution tree indexing, a technique originally developed for accessing intermediate results in automated theorem provers. For querying, we present a generic language extension approach that allows constructing queries by minimally annotating existing representations. First experiments show that this architecture results in a scalable application.

Organic chemists have been able to develop a robust, theoretical understanding of the phenomena they study; however, the primary theoretical devices employed in this field are not mathematical equations or laws, as is the case in most other physical sciences. Instead it is diagrams, and in particular structural formulas and potential energy diagrams, that carry the explanatory weight in the discipline. To understand how this is so, it is necessary to investigate both the nature of the diagrams employed in (...) organic chemistry and how these diagrams are used in the explanations of the discipline. I will begin this paper by characterizing some of the major ways that structural formulas used in organic chemistry. Next I will present a model of the explanations in organic chemistry and describe how both structural formulas and potential energy diagrams contribute to these explanations. This will be followed by several examples that support my abstract account of the role of diagrams in the explanations of organic chemistry. In particular, I will consider both the appeal to ‘hyperconjugation’ in the explanation of alkene stability and how the idea of ‘ring strain’ was developed to explain the relative stability of cyclic compounds. (shrink)

This introduction to mathematical logic starts with propositional calculus and first-order logic. Topics covered include syntax, semantics, soundness, completeness, independence, normal forms, vertical paths through negation normal formulas, compactness, Smullyan's Unifying Principle, natural deduction, cut-elimination, semantic tableaux, Skolemization, Herbrand's Theorem, unification, duality, interpolation, and definability. The last three chapters of the book provide an introduction to type theory (higher-order logic). It is shown how various mathematical concepts can be formalized in this very expressive formal language. This expressive notation (...) facilitates proofs of the classical incompleteness and undecidability theorems which are very elegant and easy to understand. The discussion of semantics makes clear the important distinction between standard and nonstandard models which is so important in understanding puzzling phenomena such as the incompleteness theorems and Skolem's Paradox about countable models of set theory. Some of the numerous exercises require giving formal proofs. A computer program called ETPS which is available from the web facilitates doing and checking such exercises. Audience: This volume will be of interest to mathematicians, computer scientists, and philosophers in universities, as well as to computer scientists in industry who wish to use higher-order logic for hardware and software specification and verification. (shrink)

W. V. Quine’s systematic development of mathematical logic has been widely praised for the new material presented and for the clarity of its exposition. This revised edition, in which the minor inconsistencies observed since its first publication have been eliminated, will be welcomed by all students and teachers in mathematics and philosophy who are seriously concerned with modern logic. Max Black, in Mind, has said of this book, “It will serve the purpose of inculcating, by precept and example, standards (...) of clarity and precision which are, even in formal logic, more often pursued than achieved.”. (shrink)

This paper provides evidence from the history of the natural sciences in philosophy (particularly mathematical physics, chemistry, and biology) that a “piloting” soul would have to make physical changes in human beings violating well-established physical laws. But, among other things, it has been discovered that there can be no such changes, and thus that there is no piloting soul. -/- 1. Introduction -- 2. Suitable Restrictions in Physical Theories -- 3. Evidence that Physical Formulas are not Violated -- 4. (...) How the Preservation of Physical Formulas Shows that There is No Afterlife - 4.1 How the Narrow Version Differs from Standard Closure - 4.2 Elucidation of the Tight Argument Against an Afterlife - 4.3 Summary and Final Thought. (shrink)

A translation of formulas in a language L1 to formulas in a language L2 is a mapping which preserves the parameters and commutes with the substitution prefix, the propositional connectives and the quantifiers. Every translation generates a corresponding transformation of theories in L1 to theories in L2. We formulate the equiconsistency problem for such transformations and propose a variant of its solution. First, for a transformation F we find the least theory A in L1 such that its inclusion in a (...) theory T guarantees equiconsistency of F and F, then we propose axiomatizations of A for some F's. (shrink)

In this paper we define the notion of frame based formulas. We show that the well-known examples of formulas arising from a finite frame, such as the Jankov-de Jongh formulas, subframe formulas and cofinal subframe formulas, are all particular cases of the frame based formulas. We give a criterion for an intermediate logic to be axiomatizable by frame based formulas and use this criterion to obtain a simple proof that every locally tabular intermediate logic is axiomatizable by Jankov-de Jongh formulas. (...) We also show that not every intermediate logic is axiomatizable by frame based formulas. (shrink)

The production of mathematical formalism on state of the art computers is quite different than by pen and paper. In this paper, I examine the question of how different media influence mathematical writing. The examination is based on an investigation of professional mathematicians' use of various media for their writing. A model for describing mathematical writing through turn-takings is proposed. The model is applied to the ways mathematicians use computers for writing, and especially it is used to (...) understand how interaction with the computer system LaTeX is different in the case of formulas than in the case of diagrams. (shrink)

An oft-defended claim of a close relationship between Gentzen inference rules and the meaning of the connectives they introduce and eliminate has given rise to a whole domain called proof-theoretic semantics, see Schroeder- Heister (1991); Prawitz (2006). A branch of proof-theoretic semantics, mainly developed by Dosen (2019); Dosen and Petric (2011), isolates in a precise mathematical manner formulas (of a logic L) that have the same meaning. These isomorphic formulas are defined to be those that behave identically in inferences. (...) The aim of this paper is to investigate another type of recently discussed rules in the literature, namely grounding rules, and their link to the meaning of the connectives they provide the grounds for. In particular, by using grounding rules, we will refine the notion of isomorphic formulas through the notion of hyper-isomorphic formulas. We will argue that it is actually the notion of hyper-isomorphic formulas that identify those formulas that have the same meaning. (shrink)

In this paper we naturally define when a theory has bounded quantifier elimination, or is bounded model complete. We give several equivalent conditions for a theory to have each of these properties. These results provide simple proofs for some known results in the model theory of the bounded arithmetic theories like CPV and PV1. We use the mentioned results to obtain some independence results in the context of intuitionistic bounded arithmetic. We show that, if the intuitionistic theory of polynomial induction (...) on strict $\Pi_2^{b}$ formulas proves decidability of $\Sigma_1^b$ formulas, then P=NP. We also prove that, if the mentioned intuitionistic theory proves ${\rm LMIN}(\Sigma_{1}^{b})$ , then P=NP. (shrink)

Abstract.We use a model theoretic approach to investigate properties of local-global principles for positive primitive formulas in spaces of orderings, such as the existence of bounds and the axiomatizability of local-global principles. As a consequence we obtain various classes of special groups satisfying local-global principles for all positive primitive formulas, and we show that local-global principles are preserved by some natural constructions in special groups.

We consider the restriction of classical principles like Excluded Middle, Markov’s Principle, König’s Lemma to arithmetical formulas of degree 2. For any such principle, we find simple mathematical statements which are intuitionistically equivalent to it, provided we restrict universal quantifications over maps to computable maps.

We study game formulas the truth of which is determined by a semantical game of uncountable length. The main theme is the study of principles stating reflection of these formulas in various admissible sets. This investigation leads to two weak forms of strict-II11 reflection . We show that admissible sets such as H and Lω2 which fail to have strict-II11 reflection, may or may not, depending on set-theoretic hypotheses satisfy one or both of these weaker forms.

We extend natural deduction for first-order logic (FOL) by introducing diagrams as components of formal proofs. From the viewpoint of FOL, we regard a diagram as a deductively closed conjunction of certain FOL formulas. On the basis of this observation, we first investigate basic heterogeneous logic (HL) wherein heterogeneous inference rules are defined in the styles of conjunction introduction and elimination rules of FOL. By examining what is a detour in our heterogeneous proofs, we discuss that an elimination-introduction pair of (...) rules constitutes a redex in our HL, which is opposite the usual redex in FOL. In terms of the notion of a redex, we prove the normalization theorem for HL, and we give a characterization of the structure of heterogeneous proofs. Every normal proof in our HL consists of applications of introduction rules followed by applications of elimination rules, which is also opposite the usual form of normal proofs in FOL. Thereafter, we extend the basic HL by extending the heterogeneous rule in the style of general elimination rules to include a wider range of heterogeneous systems. (shrink)

The languages of finitary and infinitary logic over the alphabet of bounded lattices have proven to be of considerable use in the study of compacta. Significant among the sentences of these languages are the ones that are base free, those whose truth is unchanged when we move among the lattice bases of a compactum. In this paper we define syntactically the expansive sentences, and show each of them to be base free. We also show that many well-known properties of compacta (...) may be expressed using expansive sentences; and that any property so expressible is closed under inverse limits and co-existential images. As a byproduct, we conclude that co-existential images of pseudo-arcs are pseudo-arcs. This is of interest because the corresponding statement for confluent maps is still open, and co-existential maps are often—but not always—confluent. (shrink)

This paper investigates the status of the fragments of Peano Arithmetic obtained by restricting induction, collection and least number axiom schemes to formulas which are $${\Delta_1}$$ provably in an arithmetic theory T. In particular, we determine the provably total computable functions of this kind of theories. As an application, we obtain a reduction of the problem whether $${I\Delta_0 + \neg \mathit{exp}}$$ implies $${B\Sigma_1}$$ to a purely recursion-theoretic question.

For a theory T, we study relationships among IΔ n +1 (T), LΔ n+1 (T) and B * Δ n+1 (T). These theories are obtained restricting the schemes of induction, minimization and (a version of) collection to Δ n+1 (T) formulas. We obtain conditions on T (T is an extension of B * Δ n+1 (T) or Δ n+1 (T) is closed (in T) under bounded quantification) under which IΔ n+1 (T) and LΔ n+1 (T) are equivalent. These conditions depend (...) on Th Πn +2 (T), the Π n+2 –consequences of T. The first condition is connected with descriptions of Th Πn +2 (T) as IΣ n plus a class of nondecreasing total Π n –functions, and the second one is related with the equivalence between Δ n+1 (T)–formulas and bounded formulas (of a language extending the language of Arithmetic). This last property is closely tied to a general version of a well known theorem of R. Parikh. Using what we call Π n –envelopes we give uniform descriptions of the previous classes of nondecreasing total Π n –functions. Π n –envelopes are a generalization of envelopes (see [10]) and are closely related to indicators (see [12]). Finally, we study the hierarchy of theories IΔ n+1 (IΣ m ), m≥n, and prove a hierarchy theorem. (shrink)

The Komori–Kashima problem, that asks whether the implicational intermediate logics axiomatizable by formulas minimal in classical logic are only intuitionistic logic and classical logic, has stood for over a decade. In this paper, we give a counter-example to this problem. Additionally, we also give some open problems derived from this result.

Akama et al. [1] introduced a hierarchical classification of first-order formulas for a hierarchical prenex normal form theorem in semi-classical arithmetic. In this paper, we give a justification for the hierarchical classification in a general context of first-order theories. To this end, we first formalize the standard transformation procedure for prenex normalization. Then we show that the classes $$\textrm{E}_k$$ and $$\textrm{U}_k$$ introduced in [1] are exactly the classes induced by $$\Sigma _k$$ and $$\Pi _k$$ respectively via the transformation procedure in (...) any first-order theory. (shrink)

We study the theories I∇n, L∇n and overspill principles for ∇n formulas. We show that IEn ⇒ L∇n ⇒ I∇n, but we do not know if I∇n L∇n. We introduce a new scheme, the growth scheme Crγ, and we prove that L∇n ⇒ Cr∇n⇒ I∇n. Also, we analyse the utility of bounded collection axioms for the study of the above theories.

A new approach to defining complexity of propositional formulas and proofs is suggested. Instead of measuring the size of these syntactical structures in the propositional language, the article suggests to define the complexity by the size of external descriptions of such constructions. The main result is a lower bound on proof complexity with respect to this new definition of complexity.