The aim of this paper is to explore the peculiar case of infectious logics, a group of systems obtained generalizing the semantic behavior characteristic of the -fragment of the logics of nonsense, such as the ones due to Bochvar and Halldén, among others. Here, we extend these logics with classical negations, and we furthermore show that some of these extended systems can be properly regarded as logics of formal inconsistency and logics of formal undeterminedness.

This book concerns the foundations of epistemic modality and hyperintensionality and their applications to the philosophy of mathematics. David Elohim examines the nature of epistemic modality, when the modal operator is interpreted as concerning both apriority and conceivability, as well as states of knowledge and belief. The book demonstrates how epistemic modality and hyperintensionality relate to the computational theory of mind; metaphysical modality and hyperintensionality; the types of mathematical modality and hyperintensionality; to the epistemic status of large cardinal axioms, undecidable (...) propositions, and abstraction principles in the philosophy of mathematics; to the modal and hyperintensional profiles of the logic of rational intuition; and to the types of intention, when the latter is interpreted as a hyperintensional mental state. Chapter \textbf{2} argues for a novel type of expressivism based on the duality between the categories of coalgebras and algebras, and argues that the duality permits of the reconciliation between modal and hyperintensional cognitivism and modal and hyperintensional expressivism. Elohim develops a novel, topic-sensitive truthmaker semantics for dynamic epistemic logic, and develop a novel, dynamic two-dimensional semantics grounded in two-dimensional hyperintensional Turing machines. Chapter \textbf{3} provides an abstraction principle for epistemic (hyper-)intensions. Chapter \textbf{4} advances a topic-sensitive two-dimensional truthmaker semantics, and provides three novel interpretations of the framework along with the epistemic and metasemantic. Chapter \textbf{5} applies the fixed points of the modal $\mu$-calculus in order to account for the iteration of epistemic states in a single agent, by contrast to availing of modal axiom 4 (i.e. the KK principle). The fixed point operators in the modal $\mu$-calculus are rendered hyperintensional, which yields the first hyperintensional construal of the modal $\mu$-calculus in the literature and the first application of the calculus to the iteration of epistemic states in a single agent instead of the common knowledge of a group of agents. Chapter \textbf{6} advances a solution to the Julius Caesar problem based on Fine's `criterial' identity conditions which incorporate conditions on essentiality and grounding. Chapter \textbf{7} provides a ground-theoretic regimentation of the proposals in the metaphysics of consciousness and examines its bearing on the two-dimensional conceivability argument against physicalism. The topic-sensitive epistemic two-dimensional truthmaker semantics developed in chapters \textbf{2} and \textbf{4} are availed of in order for epistemic states to be a guide to metaphysical states in the hyperintensional setting. -/- Chapters \textbf{8-12} provide cases demonstrating how the two-dimensional hyperintensions of hyperintensional, i.e. topic-sensitive epistemic two-dimensional truthmaker, semantics, solve the access problem in the epistemology of mathematics. Chapter \textbf{8} examines the interaction between Elohim's hyperintensional semantics and the axioms of epistemic set theory, large cardinal axioms, the Epistemic Church-Turing Thesis, the modal axioms governing the modal profile of $\Omega$-logic, Orey sentences such as the Generalized Continuum Hypothesis, and absolute decidability. These results yield inter alia the first hyperintensional Epistemic Church-Turing Thesis and hyperintensional epistemic set theories in the literature. Chapter \textbf{9} examines the modal and hyperintensional commitments of abstractionism, in particular necessitism, and epistemic hyperintensionality, epistemic utility theory, and the epistemology of abstraction. Elohim countenances a hyperintensional semantics for novel epistemic abstractionist modalities. Elohim suggests, too, that higher observational type theory can be applied to first-order abstraction principles in order to make first-order abstraction principles recursively enumerable, i.e. Turing machine computable, and that the truth of the first-order abstraction principle for two-dimensional hyperintensions is grounded in its being possibly recursively enumerable and the machine being physically implementable. Chapter \textbf{10} examines the philosophical significance of hyperintensional $\Omega$-logic in set theory and discusses the hyperintensionality of metamathematics. Chapter \textbf{11} provides a modal logic for rational intuition and provides a hyperintensional semantics. Chapter \textbf{12} avails of modal coalgebras to interpret the defining properties of indefinite extensibility, and avails of hyperintensional epistemic two-dimensional semantics in order to account for the interaction between interpretational and objective modalities and the truthmakers thereof. This yields the first hyperintensional category theory in the literature. Elohim invents a new mathematical trick in which first-order structures are treated as categories, and Vopenka's principle can be satisfied because of the elementary embeddings between the categories and generate Vopenka cardinals in the category of Set in category theory. Chapter \textbf{13} examines modal responses to the alethic paradoxes. Elohim provides a counter-example to epistemic closure for logical deduction. Chapter \textbf{14} examines, finally, the modal and hyperintensional semantics for the different types of intention and the relation of the latter to evidential decision theory. (shrink)

Building on recent work, I present sequent systems for the non-classical logics LP, K3, and FDE with two main virtues. First, derivations closely resemble those in standard Gentzen-style systems. Second, the systems can be obtained by reformulating a classical system using nonstandard sequent structure and simply removing certain structural rules (relatives of exchange and contraction). I clarify two senses in which these logics count as “substructural.”.

The contribution of the body to cognition and control in natural and artificial agents is increasingly described as “off-loading computation from the brain to the body”, where the body is said to perform “morphological computation”. Our investigation of four characteristic cases of morphological computation in animals and robots shows that the ‘off-loading’ perspective is misleading. Actually, the contribution of body morphology to cognition and control is rarely computational, in any useful sense of the word. We thus distinguish (1) morphology that (...) facilitates control, (2) morphology that facilitates perception and the rare cases of (3) morphological computation proper, such as ‘reservoir computing.’ where the body is actually used for computation. This result contributes to the understanding of the relation between embodiment and computation: The question for robot design and cognitive science is not whether computation is offloaded to the body, but to what extent the body facilitates cognition and control – how it contributes to the overall ‘orchestration’ of intelligent behaviour. (shrink)

The study is focused on the relation between theology and mathematics in the situation of increasing secularization. My main concern in the second part of this paper is the early-twentieth-century foundational crisis of mathematics. The hypothesis that pure mathematics partially fulfilled the functions of theology at that time is tested on the views of the leading figures of the three main foundationalist programs: Russell, Hilbert and Brouwer.

What sort of logic do we get if we adopt a supervaluational semantics for vagueness? As it turns out, the answer depends crucially on how the standard notion of validity as truth preservation is recasted. There are several ways of doing that within a supervaluational framework, the main alternative being between “global” construals (e.g., an argument is valid iff it preserves truth-under-all-precisifications) and “local” construals (an argument is valid iff, under all precisifications, it preserves truth). The former alternative is by (...) far more popular, but I argue in favor of the latter, for (i) it does not suffer from a number of serious objections, and (ii) it makes it possible to restore global validity as a defined notion. (shrink)

The rather unrestrained use of second-order logic in the neo-logicist program is critically examined. It is argued in some detail that it brings with it genuine set-theoretical existence assumptions and that the mathematical power that Hume’s Principle seems to provide, in the derivation of Frege’s Theorem, comes largely from the ‘logic’ assumed rather than from Hume’s Principle. It is shown that Hume’s Principle is in reality not stronger than the very weak Robinson Arithmetic Q. Consequently, only a few rudimentary facts (...) of arithmetic are logically derivable from Hume’s Principle. And that hardly counts as a vindication of logicism. (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)

We present sequent calculi for normal modal logics where modal and propositional behaviours are separated, and we prove a cut elimination theorem for the basic system K, so as completeness theorems both for K itself and for its most popular enrichments. MSC: 03B45, 03F05.

Constructive Analysis and Nonstandard Analysis are often characterized as completely antipodal approaches to analysis. We discuss the possibility of capturing the central notion of Constructive Analysis (i.e. algorithm, finite procedure or explicit construction) by a simple concept inside Nonstandard Analysis. To this end, we introduce Omega-invariance and argue that it partially satisfies our goal. Our results provide a dual approach to Erik Palmgren's development of Nonstandard Analysis inside constructive mathematics.

Physical superpositions exist both in classical and in quantum physics. However, what is exactly meant by ‘superposition’ in each case is extremely different. In this paper we discuss some of the multiple interpretations which exist in the literature regarding superpositions in quantum mechanics. We argue that all these interpretations have something in common: they all attempt to avoid ‘contradiction’. We argue in this paper, in favor of the importance of developing a new interpretation of superpositions which takes into account contradiction, (...) as a key element of the formal structure of the theory, “right from the start”. In order to show the feasibility of our interpretational project we present an outline of a paraconsistent approach to quantum superpositions which attempts to account for the contradictory properties present in general within quantum superpositions. This approach must not be understood as a closed formal and conceptual scheme but rather as a first step towards a different type of understanding regarding quantum superpositions. (shrink)

O propósito deste trabalho é fornecer uma resposta a duas questões fundamentais: 1) pode uma lógica não alética ser uma lógica meinongiana? E consequentemente 2) pode uma lógica não alética ser uma lógica adequada a uma teoria meinongiana dos objetos? Usando os resultados de da Costa (1989) e da Costa & Marconi (1986) e além disso de da Costa (1986 e 1993), proponho uma lógica minimal não alética de primeira ordem com identidade e o símblo " de Hilbert (da Costa (...) et al. 1992) que podem colocar em um espírito meinongiano os aspectos mais relevantes da lógica meinongiana subajcente à teoria dos objetos de Meinong. Esta é apenas uma primeira abordagem minha, para dar conta de reflexões complexas, mas também interessante como o pensamento de Meinong. Além disso, dando uma resposta positiva a 1) e 2) indico um modo plausível que pode evitar ambas as difíceis abordagens e a tentativa de recusar a teoria dos objetos de modo a não comprometer a lógica padrão e algumas de suas leis. Minha abordagem mostra que a teoria de Meinong pode ser uma ontologia válida, porque há uma lógica adequada e não banal subjacente a ela. DOI:10.5007/1808-1711.2010v14n1p99. (shrink)

On the basis of a wide range of historical examples various features of axioms are discussed in relation to their use in mathematical practice. A very general framework for this discussion is provided, and it is argued that axioms can play many roles in mathematics and that viewing them as self-evident truths does not do justice to the ways in which mathematicians employ axioms. Possible origins of axioms and criteria for choosing axioms are also examined. The distinctions introduced aim at (...) clarifying discussions in philosophy of mathematics and contributing towards a more refined view of mathematical practice. (shrink)

We survey the theory of Mucnik and Medvedev degrees of subsets of $^{\omega}{\omega}$with particular attention to the degrees of $\Pi_{1}^{0}$ subsets of $^{\omega}2$. Sections 1-6 present the major definitions and results in a uniform notation. Sections 7-6 present proofs, some more complete than others, of the major results of the subject together with much of the required background material.

Exhumation and study of the 1945 paradox of confirmation brings out the defect of its formulation. In the context of quantifier conditional-probability logic it is shown that a repair can be accomplished if the truth-functional conditional used in the statement of the paradox is replaced with a connective that is appropriate to the probabilistic context. Description of the quantifier probability logic involved in the resolution of the paradox is presented in stages. Careful distinction is maintained between a formal logic language (...) and its semantics, as the same language may be outfitted with different semantics. An acquaintance with sections 1? 5 of Hailperin (2006) covering the sentential aspects of probability logic is assumed as background information for quantifier probability logic. (shrink)

This thesis is on the history and philosophy of logic and semantics. Logic can be described as the ‘science of reasoning’, as it deals primarily with correct patterns of reasoning. However, logic as a discipline has undergone dramatic changes in the last two centuries: while for ancient and medieval philosophers it belonged essentially to the realm of language studies, it has currently become a sub-branch of mathematics. This thesis attempts to establish a dialogue between the modern and the medieval traditions (...) in logic, by means of ‘translations’ of the medieval logical theories into the modern framework of symbolic logic, i.e. formalizations. One of its conclusions is that, when properly understood within their own framework, the interest of medieval logical theories for modern investigations go beyond mere historical interest, but that a thorough conceptual analysis of such theories must be undertaken in order to avoid conceptual misprojections. While such translations of medieval into modern logic have been attempted before, the approach presented here is innovative in that attention is paid to the similarities as well as to the dissimilarities between the two traditions, and to what can be learned from the medieval masters for modern investigations in logic and semantics. (shrink)

It is argued, by use of specific examples, that mathematical understanding is something which cannot be modelled in terms of entirely computational procedures. Our conception of a natural number (a non-negative integer: 0, 1, 2, 3,…) is something which goes beyond any formulation in terms of computational rules. Our ability to perceive the properties of natural numbers depends upon our awareness, and represents just one of the many ways in which awareness provides an essential ingredient to our ability to understand. (...) There is no bar to the quality of understanding being the result of natural selection, but only so long as the physical laws contain a non-computational ingredient. (shrink)

In this paper, we present valuation semantics for the Propositional Intuitionistic Calculus (also called Heyting Calculus) and three important subcalculi: the Implicative, the Positive and the Minimal Calculus (also known as Kolmogoroff or Johansson Calculus). Algorithms based in our definitions yields decision methods for these calculi.

After a discussion of the different treatments in the literature of vacuous descriptions, the notion of descriptor is slightly generalized to function descriptor Ⅎ $\overset \rightarrow \to{y}$, so as to form partial functions φ = Ⅎ $y.A$ which satisfy $\forall \overset \rightarrow \to{x}z\leftrightarrow y=z))$. We use logic with existence predicate, as introduced by D. S. Scott, to handle partial functions, and prove that adding function descriptors to a theory based on such a logic is conservative. For theories with quantification over (...) functions, the situation is different: there the addition of Ⅎ yields new theorems in the Ⅎ-free fragment, but an axiomatisation is easily given. The proofs are syntactical. (shrink)

The syllogistic figures and moods can be taken to be argument schemata as can the rules of the Stoic propositional logic. Sentence schemata have been used in axiomatizations of logic only since the landmark 1927 von Neumann paper [31]. Modern philosophers know the role of schemata in explications of the semantic conception of truth through Tarski’s 1933 Convention T [42]. Mathematical logicians recognize the role of schemata in first-order number theory where Peano’s second-order Induction Axiom is approximated by Herbrand’s Induction-Axiom (...) Schema [23]. Similarly, in first-order set theory, Zermelo’s second-order Separation Axiom is approximated by Fraenkel’s first-order Separation Schema [17]. In some of several closely related senses, a schema is a complex system having multiple components one of which is a template-text or scheme-template, a syntactic string composed of one or more “blanks” and also possibly significant words and/or symbols. In accordance with a side condition the template-text of a schema is used as a “template” to specify a multitude, often infinite, of linguistic expressions such as phrases, sentences, or argument-texts, called instances of the schema. The side condition is a second component. The collection of instances may but need not be regarded as a third component. The instances are almost always considered to come from a previously identified language (whether formal or natural), which is often considered to be another component. This article reviews the often-conflicting uses of the expressions ‘schema’ and ‘scheme’ in the literature of logic. It discusses the different definitions presupposed by those uses. And it examines the ontological and epistemic presuppositions circumvented or mooted by the use of schemata, as well as the ontological and epistemic presuppositions engendered by their use. In short, this paper is an introduction to the history and philosophy of schemata. (shrink)

Philosophers of language have drawn on metamathematical results in varied ways. Extensionalist philosophers have been particularly impressed with two, not unrelated, facts: the existence, due to Frege/Tarski, of a certain sort of semantics, and the seeming absence of intensional contexts from mathematical discourse. The philosophical import of these facts is at best murky. Extensionalists will emphasize the success and clarity of the model theoretic semantics; others will emphasize the relative poverty of the mathematical idiom; still others will question the aptness (...) of the standard extensional semantics for mathematics. In this paper I investigate some implications of the Gödel Second Incompleteness Theorem for these positions. I argue that the realm of mathematics, proof theory in particular, has been a breeding ground for intensionality and that satisfactory intensional semantic theories are implicit in certain rigorous technical accounts. (shrink)

The recursion theorem in abstract partially ordered algebras, such as operative spaces and others, is the most fundamental result of algebraic recursion theory. The primary aim of the present paper is to prove this theorem for iterative operative spaces in full generality. As an intermediate result, a new and rather large class of models of the combinatory logic is obtained.

We consider the informal concept of "computability" or "effective calculability" and two of the formalisms commonly used to define it, "(Turing) computability" and "(general) recursiveness". We consider their origin, exact technical definition, concepts, history, general English meanings, how they became fixed in their present roles, how they were first and are now used, their impact on nonspecialists, how their use will affect the future content of the subject of computability theory, and its connection to other related areas. After a careful (...) historical and conceptual analysis of computability and recursion we make several recommendations in section §7 about preserving the intensional differences between the concepts of "computability" and "recursion." Specifically we recommend that: the term "recursive" should no longer carry the additional meaning of "computable" or "decidable;" functions defined using Turing machines, register machines, or their variants should be called "computable" rather than "recursive;" we should distinguish the intensional difference between Church's Thesis and Turing's Thesis, and use the latter particularly in dealing with mechanistic questions; the name of the subject should be "Computability Theory" or simply Computability rather than "Recursive Function Theory.". (shrink)

Alonzo Church's mathematical work on computability and undecidability is well-known indeed, and we seem to have an excellent understanding of the context in which it arose. The approach Church took to the underlying conceptual issues, by contrast, is less well understood. Why, for example, was "Church's Thesis" put forward publicly only in April 1935, when it had been formulated already in February/March 1934? Why did Church choose to formulate it then in terms of Gödel's general recursiveness, not his own λ (...) -definability as he had done in 1934? A number of letters were exchanged between Church and Paul Bernays during the period from December 1934 to August 1937; they throw light on critical developments in Princeton during that period and reveal novel aspects of Church's distinctive contribution to the analysis of the informal notion of effective calculability. In particular, they allow me to give informed, though still tentative answers to the questions I raised; the character of my answers is reflected by an alternative title for this paper, Why Church needed Gödel's recursiveness for his Thesis. In Section 5, I contrast Church's analysis with that of Alan Turing and explore, in the very last section, an analogy with Dedekind's investigation of continuity. (shrink)

Russell had two theories of definite descriptions: one for singular descriptions, another for plural descriptions. We chart its development, in which ‘On Denoting’ plays a part but not the part one might expect, before explaining why it eventually fails. We go on to consider many-valued functions, since they too bring in plural terms—terms such as ‘4’ or the descriptive ‘the inhabitants of London’ which, like plain plural descriptions, stand for more than one thing. Logicians need to take plural reference seriously (...) if only because mathematicians take many-valued functions seriously. We assess the objection (by Russell, Frege and others) that many-valued functions are illegitimate because the corresponding terms are ambiguous. We also assess the various methods proposed for getting rid of them. Finding the objection ill-founded and the methods ineffective, we introduce a logical framework that admits plural reference, and use it to answer some earlier questions and to raise some more. (shrink)

This paper introduces an extension A of Kleene's axiomatization of Brouwer's intuitionistic analysis, in which the classical arithmetical and analytical hierarchies are faithfully represented as hierarchies of the domains of continuity. A domain of continuity is a relation R(α) on Baire space with the property that every constructive partial functional defined on {α : R(α)} is continuous there. The domains of continuity for A coincide with the stable relations (those equivalent in A to their double negations), while every relation R(α) (...) is equivalent in A to ∃αA(α, β) for some stable A(α, β) (which belongs to the classical analytical hierarchy). The logic of A is intuitionistic. The axioms of A include countable comprehension, bar induction, Troelstra's generalized continuous choice, primitive recursive Markov's Principle and a classical axiom of dependent choices proposed by Krauss. Constructive dependent choices, and constructive and classical countable choice, are theorems, A is maximal with respect to classical Kleene function realizability, which establishes its consistency. The usual disjunction and (recursive) existence properties ensure that A preserves the constructive sense of "or" and "there exists.". (shrink)

We present a survey of proof theory in the USSR beginning with the paper by Kolmogorov [1925] and ending (mostly) in 1969; the last two sections deal with work done by A. A. Markov and N. A. Shanin in the early seventies, providing a kind of effective interpretation of negative arithmetic formulas. The material is arranged in chronological order and subdivided according to topics of investigation. The exposition is more detailed when the work is little known in the West or (...) the original presentation can be improved using notions or results which appeared later. This includes such topics as Novikov's cut-elimination method (regular formulas) and Maslov's inverse method for the predicate logic. (shrink)

As an undergraduate I was taught to multiply two numbers with the help of log tables, using the formulaHaving graduated to teach calculus to Engineers, I learned that log tables were to be replaced by slide rules. It was then that Imade the fateful decision that there was no need for me to learn how to use this tedious device, as I could always rely on the students to perform the necessary computations. In the course of time, slide rules were (...) replaced by pocket calculators and personal computers, but I stuck to my original decision.My computer phobia did not prevent me from taking an interest in the theoretical question: what is a computation? This question goes back to Hilbert's 10th problem, which asks for an algorithm, or computational procedure, to decide whether any given polynomial equation is solvable in integers. It quickly leads to the related question: which numerical functionsf: ℕn→ ℕ are computable?While Hilbert's 10th problem was only resolved in 1970, this related question had some earlier answers, of which I shall single out the following three:f is recursive,f is computable on an abstract machine,f is definable in the untyped λ-calculus.These tentative answers were shown to be equivalent by Church [1936] and Turing [1936–7].I shall discuss here some of the more recent developments of these notions of computability and their relevance to linguistics and logic. I hope to be forgiven for dwelling on some of the work I have been involved with personally, with greater emphasis than is justified by its historical significance. (shrink)

We show how to extract effective bounds Φ for $\bigwedge u^1 \bigwedge v \leq_\gamma tu \bigvee w^\eta G_0$ -sentences which depend on u only (i.e. $\bigwedge u \bigwedge v \leq_\gamma tu \bigvee w \leq_\eta \Phi uG_0$ ) from arithmetical proofs which use analytical assumptions of the form \begin{equation*}\tag{*}\bigwedge x^\delta\bigvee y \leq_\rho sx \bigwedge z^\tau F_0\end{equation*} (γ, δ, ρ, and τ are arbitrary finite types, η ≤ 2, G0 and F0 are quantifier-free, and s and t are closed terms). If τ (...) ≤ 2, (*) can be weakened to $\bigwedge x^\delta, z^\tau\bigvee y \leq_\rho sx \bigwedge \tilde{z} \leq_\tau z F_0$ . This is used to establish new conservation results about weak König's lemma. Applications to proofs in classical analysis, especially uniqueness proofs in approximation theory, will be given in subsequent papers. (shrink)

Based on the relevant logic R, the system R# was proposed as a relevant Peano arithmetic. R# has many nice properties: the most conspicuous theorems of classical Peano arithmetic PA are readily provable therein; it is readily and effectively shown to be nontrivial; it incorporates both intuitionist and classical proof methods. But it is shown here that R# is properly weaker than PA, in the sense that there is a strictly positive theorem QRF of PA which is unprovable in R#. (...) The reason is interesting: if PA is slightly weakened to a subtheory P+, it admits the complex ring C as a model; thus QRF is chosen to be a theorem of PA but false in C. Inasmuch as all strictly positive theorems of R# are already theorems of P+, this nonconservativity result shows that QRF is also a nontheorem of R#. As a consequence, Ackermann's rule γ is inadmissible in R#. Accordingly, an extension of R# which retains its good features is desired. The system R##, got by adding an omega-rule, is such an extension. Central question: is there an effectively axiomatizable system intermediate between R# and R##, which does formalize arithmetic on relevant principles, but also admits γ in a natural way? (shrink)

For each positive n , two alternative axiomatizations of the theory of strings over n alphabetic characters are presented. One class of axiomatizations derives from Tarski's system of the Wahrheitsbegriff and uses the n characters and concatenation as primitives. The other class involves using n character-prefixing operators as primitives and derives from Hermes' Semiotik. All underlying logics are second order. It is shown that, for each n, the two theories are definitionally equivalent [or synonymous in the sense of deBouvere]. It (...) is further shown that each member of one class is synonymous with each member of the other class; thus that all of the theories are definitionally equivalent with each other and with Peano arithmetic. Categoricity of Peano arithmetic then implies categoricity of each of the above theories. (shrink)

We introduce new proof systems for propositional logic, simple deduction Frege systems, general deduction Frege systems, and nested deduction Frege systems, which augment Frege systems with variants of the deduction rule. We give upper bounds on the lengths of proofs in Frege proof systems compared to lengths in these new systems. As applications we give near-linear simulations of the propositional Gentzen sequent calculus and the natural deduction calculus by Frege proofs. The length of a proof is the number of lines (...) in the proof. A general deduction Frege proof system provides at most quadratic speedup over Frege proof systems. A nested deduction Frege proof system provides at most a nearly linear speedup over Frege system where by "nearly linear" is meant the ratio of proof lengths is O) where α is the inverse Ackermann function. A nested deduction Frege system can linearly simulate the propositional sequent calculus, the tree-like general deduction Frege calculus, and the natural deduction calculus. Hence a Frege proof system can simulate all those proof systems with proof lengths bounded by O). Also we show that a Frege proof of n lines can be transformed into a tree-like Frege proof of O lines and of height O. As a corollary of this fact we can prove that natural deduction and sequent calculus tree-like systems simulate Frege systems with proof lengths bounded by O. (shrink)

In this article, I develop three conceptual innovations within the area of formal metatheory, and present a computer program, called Reconstructor, that implements those developments. The first development consists in a methodology for testing formal reconstructions of scientific theories, which involves checking both whether translations of paradigmatically successful applications into models satisfy the formalisation of the laws, and also whether unsuccessful applications do not. I show how Reconstructor can help carry this out, since it allows the end-user to specify a (...) formal language, input axioms and models formulated in that language, and then ask if the models satisfy the axioms. The second innovation is the introduction of incomplete models (for which the denotation of some terms is missing) into scientific metatheory, in order to represent cases of missing information. I specify the paracomplete semantics built into Reconstructor to deal with sentences where denotation failures occur. The third development consists in a new way of explicating the structuralist notion of a determination method, by equating them with algorithms. This allows determination methods to be loaded into Reconstructor and then executed within a model to find out the value of a previously non-denoting term (i.e. it allows the formal reconstruction to make predictions). This, in turn, can help test the reconstruction in a different way. Finally, I conclude with some suggestions about additional uses the program may have. (shrink)