The problem of negative truth is the problem of how, if everything in the world is positive, we can speak truly about the world using negative propositions. A prominent solution is to explain negation in terms of a primitive notion of metaphysical incompatibility. I argue that if this account is correct, then minimal logic is the correct logic. The negation of a proposition A is characterised as the minimal incompatible of A composed of it and the logical constant ¬. A (...) rule based account of the meanings of logical constants that appeals to the notion of incompatibility in the introduction rule for negation ensures the existence and uniqueness of the negation of every proposition. But it endows the negation operator with no more formal properties than those it has in minimal logic. (shrink)

We develop a novel solution to the negation version of the Frege-Geach problem by taking up recent insights from the bilateral programme in logic. Bilateralists derive the meaning of negation from a primitive *B-type* inconsistency involving the attitudes of assent and dissent. Some may demand an explanation of this inconsistency in simpler terms, but we argue that bilateralism’s assumptions are no less explanatory than those of *A-type* semantics that only require a single primitive attitude, but must stipulate inconsistency elsewhere. Based (...) on these insights, we develop a version of B-type expressivism called *inferential expressivism*. This is a novel semantic framework that characterises meanings by inferential roles that define which *attitudes* one can *infer* from the use of terms. We apply this framework to normative vocabulary, thereby solving the Frege-Geach problem generally and comprehensively. Our account moreover includes a semantics for epistemic modals, thereby also explaining normative terms under epistemic modals. (shrink)

We present an inferentialist account of the epistemic modal operator might. Our starting point is the bilateralist programme. A bilateralist explains the operator not in terms of the speech act of rejection ; we explain the operator might in terms of weak assertion, a speech act whose existence we argue for on the basis of linguistic evidence. We show that our account of might provides a solution to certain well-known puzzles about the semantics of modal vocabulary whilst retaining classical logic. (...) This demonstrates that an inferentialist approach to meaning can be successfully extended beyond the core logical constants. (shrink)

We study an alternative embedding of IPC into atomic system F whose translation of proofs is based, not on instantiation overflow, but instead on the admissibility of the elimination rules for disjunction and absurdity. As compared to the embedding based on instantiation overflow, the alternative embedding works equally well at the levels of provability and preservation of proof identity, but it produces shorter derivations and shorter simulations of reduction sequences. Lambda-terms are employed in the technical development so that the algorithmic (...) content is made explicit, both for the alternative and the original embeddings. The investigation of preservation of proof-reduction steps by the alternative embedding enables the analysis of generation of “administrative” redexes. These are the key, on the one hand, to understand the difference between the two embeddings; on the other hand, to understand whether the final word on the embedding of IPC into atomic system F has been said. (shrink)

An adequate semantics for generic sentences must stake out positions across a range of contested territory in philosophy and linguistics. For this reason the study of generic sentences is a venue for investigating different frameworks for understanding human rationality as manifested in linguistic phenomena such as quantification, classification of individuals under kinds, defeasible reasoning, and intensionality. Despite the wide variety of semantic theories developed for generic sentences, to date these theories have been almost universally model-theoretic and representational. This essay outlines (...) a range of proof-theoretic analyses for characterizing generics. Particular attention is given to an expressivist proof-theory that can be traced to 1) work on logical syntax that Carnap undertook prior to his turn toward truth-conditional model theory in the late 1930s, and 2) research on sequent calculi and natural deduction systems that originate in work from Gentzen and Prawitz.11 This essay offers a more precise exposition of some of the material discussed in the first two chapters of my dissertation (Stovall Citation2015a). These ideas developed in the context of a working group on non-monotonic logic run by Robert Brandom, and they were subsequently clarified through the work of Nissim Francez (particularly Francez Citation2015). I am indebted to many people for feedback and criticism on this essay, though I am sure none among them would agree with everything I say and do here. I would particularly like to thank Brandom, Francez, Ulf Hlobil, Daniel Kaplan, Jared Millson, Bernhard Nickel, Jaroslav Peregrin, Jeffry Pelletier, Thomas Ricketts, Mark Risjord, Shawn Standefer, and two reviewers for this journal. Work on this essay was supported by the joint Lead-Agency research grant between the Austrian Science Foundation (FWF) and the Czech Science Foundation (GAČR), Inferentialism and Collective Intentionality, GF17-33808L. It was substantially revised prior to its final submission. (shrink)

The standard natural deduction rules for the identity predicate have seemed to some not to be harmonious. Stephen Read has suggested an alternative introduction rule that restores harmony but presupposes second-order logic. Here it will be shown that the standard rules are in fact harmonious. To this end, natural deduction will be enriched with a theory of definitional identity. This leads to a novel conception of canonical derivation, on the basis of which the identity elimination rule can be justified in (...) a proof-theoretical manner. (shrink)

We reconsider the pragmatic interpretation of intuitionistic logic [21] regarded as a logic of assertions and their justi cations and its relations with classical logic. We recall an extension of this approach to a logic dealing with assertions and obligations, related by a notion of causal implication [14, 45]. We focus on the extension to co-intuitionistic logic, seen as a logic of hypotheses [8, 9, 13] and on polarized bi-intuitionistic logic as a logic of assertions and conjectures: looking at the (...) S4 modal translation, we give a de nition of a system AHL of bi-intuitionistic logic that correctly represents the duality between intuitionistic and co-intuitionistic logic, correcting a mistake in previous work [7, 10]. A computational interpretation of cointuitionism as a distributed calculus of coroutines is then used to give an operational interpretation of subtraction.Work on linear co-intuitionism is then recalled, a linear calculus of co-intuitionistic coroutines is de ned and a probabilistic interpretation of linear co-intuitionism is given as in [9]. Also we remark that by extending the language of intuitionistic logic we can express the notion of expectation, an assertion that in all situations the truth of p is possible and that in a logic of expectations the law of double negation holds. Similarly, extending co-intuitionistic logic, we can express the notion of conjecture that p, de ned as a hypothesis that in some situation the truth of p is epistemically necessary. (shrink)

Intra-theoretical logical pluralism is a form of meaning-invariant pluralism about logic, articulated recently by Hjortland :355–373, 2013). This version of pluralism relies on it being possible to define several distinct notions of provability relative to the same logical calculus. The present paper picks up and explores this theme: How can a single logical calculus express several different consequence relations? The main hypothesis articulated here is that the divide between the internal and external consequence relations in Gentzen systems generates a form (...) of intra-theoretical logical pluralism. (shrink)

The article approaches cut elimination from a new angle. On the basis of an arbitrary inference relation among logically atomic formulae, an inference relation on a language possessing logical operators is defined by means of inductive clauses similar to the operator-introducing rules of a cut-free intuitionistic sequent calculus. The logical terminology of the richer language is not uniquely specified, but assumed to satisfy certain conditions of a general nature, allowing for, but not requiring, the existence of infinite conjunctions and disjunctions. (...) We investigate to what extent structural properties of the given atomic relation are preserved through the extension to the full language. While closure under the Cut rule narrowly construed is not in general thus preserved, two properties jointly amounting to closure under the ordinary structural rules, including Cut, are. -/- Attention is then narrowed down to the special case of a standard first-order language, where a similar result is obtained also for closure under substitution of terms for individual parameters. Taken together, the three preservation results imply the familiar cut-elimination theorem for pure first-order intuitionistic sequent calculus. -/- In the interest of conceptual economy, all deducibility relations are specified purely inductively, rather than in terms of the existence of formal proofs of any kind. (shrink)

This short paper has two loosely connected parts. In the first part, I discuss the difference between classical and intuitionist logic in relation to different the role of hypotheses play in each logic. Harmony is normally understood as a relation between two ways of manipulating formulas in systems of natural deduction: their introduction and elimination. I argue, however, that there is at least a third way of manipulating formulas, namely the discharge of assumption, and that the difference between classical and (...) intuitionist logic can be characterised as a difference of the conditions under which discharge is allowed. Harmony, as ordinarily understood, has nothing to say about discharge. This raises the question whether the notion of harmony can be suitably extended. This requires there to be a suitable fourth way of manipulating formulas that discharge can stand in harmony to. The question is whether there is such a notion: what might it be that stands to discharge of formulas as introduction stands to elimination? One that immediately comes to mind is the making of assumptions. I leave it as an open question for further research whether the notion of harmony can be fruitfully extended in the way suggested here. In the second part, I discuss bilateralism, which proposes a wholesale revision of what it is that is assumed and manipulated by rules of inference in deductions: rules apply to speech acts – assertions and denials – rather than propositions. I point out two problems for bilateralism. First, bilaterlists cannot, contrary to what they claim to be able to do, draw a distinction between the truth and assertibility of a proposition. Secondly, it is not clear what it means to assume an expression such as '+ A' that is supposed to stand for an assertion. Worse than that, it is plausible that making an assumption is a particular speech act, as argued by Dummett (Frege: Philosophy of Language, p.309ff). Bilaterlists accept that speech acts cannot be embedded in other speech acts. But then it is meaningless to assume + A or − A. (shrink)

This paper aims to unite two seemingly disparate themes in the philosophy of mathematics and language respectively, namely ante rem structuralism and inferentialism. My analysis begins with describing both frameworks in accordance with their genesis in the work of Hilbert. I then draw comparisons between these philosophical views in terms of their similar motivations and similar objections to the referential orthodoxy. I specifically home in on two points of comparison, namely the role of norms and the relation of ontological dependence (...) in both accounts. Lastly, I show that insights from this purported connection can address certain objections to both theories respectively. (shrink)

The main objective of this PhD Thesis is to present a method of obtaining strong normalization via natural ordinal, which is applicable to natural deduction systems and typed lambda calculus. The method includes (a) the definition of a numerical assignment that associates each derivation (or lambda term) to a natural number and (b) the proof that this assignment decreases with reductions of maximal formulas (or redex). Besides, because the numerical assignment used coincide with the length of a specific sequence of (...) reduction - the worst reduction sequence - it is the lowest upper bound on the length of reduction sequences. The main commitment of the introduced method is that it is constructive and elementary, produced only through analyzing structural and combinatorial properties of derivations and lambda terms, without appeal to any sophisticated mathematical tool. Together with the exposition of the method, it is presented a comparative study of some articles in the literature that also get strong normalization by means we can identify with the natural ordinal methods. Among them we highlight Howard[1968], which performs an ordinal analysis of Godel’s Dialectica interpretation for intuitionistic first order arithmetic. We reveal a fact about this article not noted by the author himself: a syntactic proof of strong normalization theorem for the system of typified lambda calculus λ⊃ is a consequence of its results. This would be the first strong normalization proof in the literature. (written in Portuguese). (shrink)

Philosophers are divided on whether the proof- or truth-theoretic approach to logic is more fruitful. The paper demonstrates the considerable explanatory power of a truth-based approach to logic by showing that and how it can provide (i) an explanatory characterization —both semantic and proof-theoretical—of logical inference, (ii) an explanatory criterion for logical constants and operators, (iii) an explanatory account of logic’s role (function) in knowledge, as well as explanations of (iv) the characteristic features of logic —formality, strong modal force, generality, (...) topic neutrality, basicness, and (quasi-)apriority, (v) the veridicality of logic and its applicability to science, (v) the normativity of logic, (vi) error, revision, and expansion in/of logic, and (vii) the relation between logic and mathematics. The high explanatory power of the truth-theoretic approach does not rule out an equal or even higher explanatory power of the proof-theoretic approach. But to the extent that the truth-theoretic approach is shown to be highly explanatory, it sets a standard for other approaches to logic, including the proof-theoretic approach. (shrink)

Gentzen’s approach to deductive systems, and Carnap’s and Popper’s treatment of probability in logic were two fruitful ideas that appeared in logic of the mid-twentieth century. By combining these two concepts, the notion of sentence probability, and the deduction relation formalized in the sequent calculus, we introduce the notion of ’probabilized sequent’ \ with the intended meaning that “the probability of truthfulness of \ belongs to the interval [a, b]”. This method makes it possible to define a system of derivations (...) based on ’axioms’ of the form \, obtained as a result of empirical research, and then infer conclusions of the form \. We discuss the consistency, define the models, and prove the soundness and completeness for the defined probabilized sequent calculus. (shrink)

We discuss relationships among the existence property, the disjunction property, and their weak variants in the setting of intermediate predicate logics. We deal with the weak and sentential existence properties, and the Z-normality, which is a weak variant of the disjunction property. These weak variants were presented in the author’s previous paper [16]. In the present paper, the Kripke sheaf semantics is used.

The purpose of this paper is to present a paraconsistent formal system and a corresponding intended interpretation according to which true contradictions are not tolerated. Contradictions are, instead, epistemically understood as conflicting evidence, where evidence for a proposition A is understood as reasons for believing that A is true. The paper defines a paraconsistent and paracomplete natural deduction system, called the Basic Logic of Evidence, and extends it to the Logic of Evidence and Truth. The latter is a logic of (...) formal inconsistency and undeterminedness that is able to express not only preservation of evidence but also preservation of truth. LETj is anti-dialetheist in the sense that, according to the intuitive interpretation proposed here, its consequence relation is trivial in the presence of any true contradiction. Adequate semantics and a decision method are presented for both BLE and LETj, as well as some technical results that fit the intended interpretation. (shrink)

On the basis of Martin-Löf’s meaning explanations for his type theory a detailed justification is offered of the rule of identity elimination. Brief discussions are thereafter offered of how the univalence axiom fares with respect to these meaning explanations and of some recent work on identity in type theory by Ladyman and Presnell.

Dummett’s justification procedures are revisited. They are used as background for the discussion of some conceptual and technical issues in proof-theoretic semantics, especially the role played by assumptions in proof-theoretic definitions of validity.

We are justified in employing the rule of inference Modus Ponens (or one much like it) as basic in our reasoning. By contrast, we are not justified in employing a rule of inference that permits inferring to some difficult mathematical theorem from the relevant axioms in a single step. Such an inferential step is intuitively “too large” to count as justified. What accounts for this difference? In this paper, I canvass several possible explanations. I argue that the most promising approach (...) is to appeal to features like usefulness or indispensability to important or required cognitive projects. On the resulting view, whether an inferential step counts as large or small depends on the importance of the relevant rule of inference in our thought. (shrink)

This article offers an overview of inferential role semantics. We aim to provide a map of the terrain as well as challenging some of the inferentialist’s standard commitments. We begin by introducing inferentialism and placing it into the wider context of contemporary philosophy of language. §2 focuses on what is standardly considered both the most important test case for and the most natural application of inferential role semantics: the case of the logical constants. We discuss some of the (alleged) benefits (...) of logical inferentialism, chiefly with regards to the epistemology of logic, and consider a number of objections. §3 introduces and critically examines the most influential and most fully developed form of global inferentialism: Robert Brandom’s inferentialism about linguistic and conceptual content in general. Finally, in §4 we consider a number of general objections to IRS and consider possible responses on the inferentialist’s behalf. (shrink)

This paper responds to recent work in the philosophy of Homotopy Type Theory by James Ladyman and Stuart Presnell. They consider one of the rules for identity, path induction, and justify it along ‘pre-mathematical’ lines. I give an alternate justification based on the philosophical framework of inferentialism. Accordingly, I construct a notion of harmony that allows the inferentialist to say when a connective or concept is meaning-bearing and this conception unifies most of the prominent conceptions of harmony through category theory. (...) This categorical harmony is stated in terms of adjoints and says that any concept definable by iterated adjoints from general categorical operations is harmonious. Moreover, it has been shown that identity in a categorical setting is determined by an adjoint in the relevant way. Furthermore, path induction as a rule comes from this definition. Thus we arrive at an account of how path induction, as a rule of inference governing identity, can be justified on mathematically motivated grounds. (shrink)

In this paper we give a brief treatment of a theory of proofs for a system of Full Intuitionistic Linear Logic. This system is distinct from Classical Linear Logic, but unlike the standard Intuitionistic Linear Logic of Girard and Lafont includes the multiplicative disjunction par. This connective does have an entirely natural interpretation in a variety of categorical models of Intuitionistic Linear Logic. The main proof-theoretic problem arises from the observation of Schellinx that cut elimination fails outright for an intuitive (...) formulation of Full Intuitionistic Linear Logic; the nub of the problem is the interaction between par and linear implication. We present here a term assignment system which gives an interpretation of proofs as some kind of non-deterministic function. In this way we find a system which does enjoy cut elimination. The system is a direct result of an analysis of the categorical semantics, though we make an effort to present the system as if it were purely a proof-theoretic construction. (shrink)

This paper gives new confluence proofs for several lambda calculi with permutation-like reduction, including lambda calculi corresponding to intuitionistic and classical natural deduction with disjunction and permutative conversions, and a lambda calculus with explicit substitutions. For lambda calculi with permutative conversion, naïve parallel reduction technique does not work, and traditional notion of residuals is required as Ando pointed out. This paper shows that the difficulties can be avoided by extending the technique proposed by Dehornoy and van Oostrom, called the Z (...) theorem: existence of a mapping on terms with the Z property concludes the confluence. Since it is still hard to directly define a mapping with the Z property for the lambda calculi with permutative conversions, this paper extends the Z theorem to compositional functions, called compositional Z, and shows that we can adopt it to the calculi. (shrink)

A first-order language with a defined identity predicate is proposed whose apparatus for atomic predication is sensitive to grammatical categories of natural language. Subatomic natural deduction systems are defined for this naturalistic first-order language. These systems contain subatomic systems which govern the inferential relations which obtain between naturalistic atomic sentences and between their possibly composite components. As a main result it is shown that normal derivations in the defined systems enjoy the subexpression property which subsumes the subformula property with respect (...) to atomic and identity formulae as a special case. The systems admit a proof-theoretic semantics which does not only apply to logically compound but also to atomic and identity formulae—as well as to their components. The potential of the defined systems for a meticulous first-order analysis of natural inferences whose validity crucially depends on expressions of some of the aforementioned categories is demonstrated. (shrink)

The paper is a defense of a strict form of anti-realism, competing the "in principle" form defended by Michael Dummett. It proposes to ground anti-realism on the basis of two principles ("immanence" and "implicitness") and to develop the consequences of these principles in the light of sub-structural logics.

Hilbert’s choice operators τ and ε, when added to intuitionistic logic, strengthen it. In the presence of certain extensionality axioms they produce classical logic, while in the presence of weaker decidability conditions for terms they produce various superintuitionistic intermediate logics. In this thesis, I argue that there are important philosophical lessons to be learned from these results. To make the case, I begin with a historical discussion situating the development of Hilbert’s operators in relation to his evolving program in the (...) foundations of mathematics and in relation to philosophical motivations leading to the development of intuitionistic logic. This sets the stage for a brief description of the relevant part of Dummett’s program to recast debates in metaphysics, and in particular disputes about realism and anti-realism, as closely intertwined with issues in philosophical logic, with the acceptance of classical logic for a domain reflecting a commitment to realism for that domain. Then I review extant results about what is provable and what is not when one adds epsilon to intuitionistic logic, largely due to Bell and DeVidi, and I give several new proofs of intermediate logics from intuitionistic logic+ε without identity. With all this in hand, I turn to a discussion of the philosophical significance of choice operators. Among the conclusions I defend are that these results provide a finer-grained basis for Dummett’s contention that commitment to classically valid but intuitionistically invalid principles reflect metaphysical commitments by showing those principles to be derivable from certain existence assumptions; that Dummett’s framework is improved by these results as they show that questions of realism and anti-realism are not an “all or nothing” matter, but that there are plausibly metaphysical stances between the poles of anti-realism and realism, because different sorts of ontological assumptions yield intermediate rather than classical logic; and that these intermediate positions between classical and intuitionistic logic link up in interesting ways with our intuitions about issues of objectivity and reality, and do so usefully by linking to questions around intriguing everyday concepts such as “is smart,” which I suggest involve a number of distinct dimensions which might themselves be objective, but because of their multivalent structure are themselves intermediate between being objective and not. Finally, I discuss the implications of these results for ongoing debates about the status of arbitrary and ideal objects in the foundations of logic, showing among other things that much of the discussion is flawed because it does not recognize the degree to which the claims being made depend on the presumption that one is working with a very strong logic. (shrink)

Methods available for the axiomatization of arbitrary finite-valued logics can be applied to obtain sound and complete intelim rules for all truth-functional connectives of classical logic including the Sheffer stroke and Peirce’s arrow. The restriction to a single conclusion in standard systems of natural deduction requires the introduction of additional rules to make the resulting systems complete; these rules are nevertheless still simple and correspond straightforwardly to the classical absurdity rule. Omitting these rules results in systems for intuitionistic versions of (...) the connectives in question. (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)

The focus of this paper are Dummett's meaning-theoretical arguments against classical logic based on consideration about the meaning of negation. Using Dummettian principles, I shall outline three such arguments, of increasing strength, and show that they are unsuccessful by giving responses to each argument on behalf of the classical logician. What is crucial is that in responding to these arguments a classicist need not challenge any of the basic assumptions of Dummett's outlook on the theory of meaning. In particular, I (...) shall grant Dummett his general bias towards verificationism, encapsulated in the slogan 'meaning is use'. The second general assumption I see no need to question is Dummett's particular breed of molecularism. Some of Dummett's assumptions will have to be given up, if classical logic is to be vindicated in his meaning-theoretical framework. A major result of this paper will be that the meaning of negation cannot be defined by rules of inference in the Dummettian framework. (shrink)

I use the Corcoran–Smiley interpretation of Aristotle's syllogistic as my starting point for an examination of the syllogistic from the vantage point of modern proof theory. I aim to show that fresh logical insights are afforded by a proof-theoretically more systematic account of all four figures. First I regiment the syllogisms in the Gentzen–Prawitz system of natural deduction, using the universal and existential quantifiers of standard first-order logic, and the usual formalizations of Aristotle's sentence-forms. I explain how the syllogistic is (...) a fragment of my system of Core Logic. Then I introduce my main innovation: the use of binary quantifiers, governed by introduction and elimination rules. The syllogisms in all four figures are re-proved in the binary system, and are thereby revealed as all on a par with each other. I conclude with some comments and results about grammatical generativity, ecthesis, perfect validity, skeletal validity and Aristotle's chain principle. (shrink)

I present a new syntactical method for proving the Interpolation Theorem for the implicational fragment of intuitionistic logic and its substructural subsystems. This method, like Prawitz’s, works on natural deductions rather than sequent derivations, and, unlike existing methods, always finds a ‘strongest’ interpolant under a certain restricted but reasonable notion of what counts as an ‘interpolant’.

In this paper, I provide a thorough discussion and reconstruction of Bernard Bolzano’s theory of grounding and a detailed investigation into the parallels between his concept of grounding and current notions of normal proofs. Grounding (Abfolge) is an objective ground-consequence relation among true propositions that is explanatory in nature. The grounding relation plays a crucial role in Bolzano’s proof-theory, and it is essential for his views on the ideal buildup of scientific theories. Occasionally, similarities have been pointed out between Bolzano’s (...) ideas on grounding and cut-free proofs in Gentzen’s sequent calculus. My thesis is, however, that they bear an even stronger resemblance to the normal natural deduction proofs employed in proof-theoretic semantics in the tradition of Dummett and Prawitz. (shrink)

This paper discusses proof-theoretic semantics, the project of specifying the meanings of the logical constants in terms of rules of inference governing them. I concentrate on Michael Dummett’s and Dag Prawitz’ philosophical motivations and give precise characterisations of the crucial notions of harmony and stability, placed in the context of proving normalisation results in systems of natural deduction. I point out a problem for defining the meaning of negation in this framework and prospects for an account of the meanings of (...) modal operators in terms of rules of inference. (shrink)

If correct, Christopher Peacocke’s [20] “manifestationism without verificationism,” would explode the dichotomy between realism and inferentialism in the contemporary philosophy of language. I first explicate Peacocke’s theory, defending it from a criticism of Neil Tennant’s. This involves devising a recursive definition for grasp of logical contents along the lines Peacocke suggests. Unfortunately though, the generalized account reveals the Achilles’ heel of the whole theory. By inventing a new logical operator with the introduction rule for the existential quantifier and the elimination (...) rule for the universal quantifier, I am able to show that Peacocke’s theory only avoids verificationism to the extent that it does not satisfy manifestationism. (shrink)

We present a categorical/denotational semantics for the Lambek Syntactic Calculus , indeed for a λlD-typed version Curry-Howard isomorphic to it. The main novelty of our approach is an abstract noncommutative construction with right and left adjoints, called sequential product. It is defined through a hierarchical structure of categories reflecting the implicit permission to sequence expressions and the inductive construction of compound expressions. We claim that Lambek's noncommutative product corresponds to a noncommutative bi-endofunctor into a category, which encloses all categories of (...) such hierarchical structure. A soundness theorem for LSC is shown with respect to this semantical framework. (shrink)

In the domain of ontology design as well as in Knowledge Representation, modeling universals is a challenging problem.Most approaches that have addressed this problem rely on Description Logics (DLs) but many difficulties remain, due to under-constrained representation which reduces the inferences that can be drawn and further causes problems in expressiveness. In mathematical logic and program checking, type theories have proved to be appealing but, so far they have not been applied in the formalization of ontologies. To bridge this gap, (...) we present in this paper a theory for representing ontologies in a dependently typed framework which relies on strong formal foundations including both a constructive logic and a functional type system. The language of this theory defines in a precise way what ontological primitives such as classes, relations, properties, etc., and thereof roles, are. The first part of the paper details how these primitives are defined and used within the theory. In a second part, we focus on the formalization of the role primitive. A review of significant role properties leads to the specification of a role profile and most of the remaining work details through numerous examples, how the proposed theory is able to fully satisfy this profile. It is demonstrated that dependent types can model several non-trivial aspects of roles including a formal solution for generalization hierarchies, identity criteria for roles and other contributions. A discussion is given on how the theory is able to cope with many of the constraints inherent in a good role representation. (shrink)

A proof employing no semantic terms is offered in support of the claim that there can be truths without truthmakers. The logical resources used in the proof are weak but do include the structural rule Contraction.

Gentzen's systems of natural deduction and sequent calculus were byproducts in his program of proving the consistency of arithmetic and analysis. It is suggested that the central component in his results on logical calculi was the use of a tree form for derivations. It allows the composition of derivations and the permutation of the order of application of rules, with a full control over the structure of derivations as a result. Recently found documents shed new light on the discovery of (...) these calculi. In particular, Gentzen set up five different forms of natural calculi and gave a detailed proof of normalization for intuitionistic natural deduction. An early handwritten manuscript of his thesis shows that a direct translation from natural deduction to the axiomatic logic of Hilbert and Ackermann was, in addition to the influence of Paul Hertz, the second component in the discovery of sequent calculus. A system intermediate between the sequent calculus LI and axiomatic logic, denoted LIG in unpublished sources, is implicit in Gentzen's published thesis of 1934—35. The calculus has half rules, half “groundsequents,” and does not allow full cut elimination. Nevertheless, a translation from LI to LIG in the published thesis gives a subformula property for a complete class of derivations in LIG. After the thesis, Gentzen continued to work on variants of sequent calculi for ten more years, in the hope to find a consistency proof for arithmetic within an intuitionistic calculus. (shrink)

Inferentialism is the conviction that to be meaningful in the distinctively human way, or to have a 'conceptual content', is to be governed by a certain kind of inferential rules. The term was coined by Robert Brandom as a label for his theory of language; however, it is also naturally applicable (and is growing increasingly common) within the philosophy of logic.

This paper analyzes and evaluates Bolzano's remarks on the apagogic method of proof with reference to his juvenile booklet "Contributions to a better founded presentation of mathematics" of 1810 and to his ?Theory of science? (1837). I shall try to defend the following contentions: (1) Bolzanos vain attempt to transform all indirect proofs into direct proofs becomes comprehensible as soon as one recognizes the following facts: (1.1) his attitude towards indirect proofs with an affirmative conclusion differs from his stance to (...) indirect proofs with a negative conclusion; (1.2) by Bolzano's lights arguments via consequentia mirabilis only seem to be indirect. (2) Bolzano does not deny that indirect proofs can be perfect certifications (Gewissmachungen) of their conclusion; what he denies is rather that they can provide grounds for their conclusions. (2.1) They cannot do the latter, since they start from false premises and (2.2) since they make an unnecessary detour. (3) The far-reaching agreement between his early and late assessment of apagogical proofs (in the Beyträge of 1810 and the Wissenschaftslehre of 1837) is partly due to the fact that he develops his own position always against the background of Wolff's and Lambert's views. (shrink)

The axiomatic presentation of modal systems and the standard formulations of natural deduction and sequent calculus for modal logic are reviewed, together with the difficulties that emerge with these approaches. Generalizations of standard proof systems are then presented. These include, among others, display calculi, hypersequents, and labelled systems, with the latter surveyed from a closer perspective.

Second-order abstract categorial grammars (de Groote in Association for computational linguistics, 39th annual meeting and 10th conference of the European chapter, proceedings of the conference, pp. 148–155, 2001) and hyperedge replacement grammars (Bauderon and Courcelle in Math Syst Theory 20:83–127, 1987; Habel and Kreowski in STACS 87: 4th Annual symposium on theoretical aspects of computer science. Lecture notes in computer science, vol 247, Springer, Berlin, pp 207–219, 1987) are two natural ways of generalizing “context-free” grammar formalisms for string and tree (...) languages. It is known that the string generating power of both formalisms is equivalent to (non-erasing) multiple context-free grammars (Seki et al. in Theor Comput Sci 88:191–229, 1991) or linear context-free rewriting systems (Weir in Characterizing mildly context-sensitive grammar formalisms, University of Pennsylvania, 1988). In this paper, we give a simple, direct proof of the fact that second-order ACGs are simulated by hyperedge replacement grammars, which implies that the string and tree generating power of the former is included in that of the latter. The normal form for tree-generating hyperedge replacement grammars given by Engelfriet and Maneth (Graph transformation. Lecture notes in computer science, vol 1764. Springer, Berlin, pp 15–29, 2000) can then be used to show that the tree generating power of second-order ACGs is exactly the same as that of hyperedge replacement grammars. (shrink)

Semantic justifications of the classical rules of logical inference typically make use of a notion of bivalent truth, understood as a property guaranteed to attach to a sentence or its negation regardless of the prospects for speakers to determine it as so doing. For want of a convincing alternative account of classical logic, some philosophers suspicious of such recognition-transcending bivalence have seen no choice but to declare classical deduction unwarranted and settle for a weaker system; intuitionistic logic in particular, buttressed (...) by assertion-conditional semantics, is often considered to enjoy a degree of meaning-theoretical respectability unattainable by classical logic.The decision to forgo the classical inference rules is not always made lightly. Thus, Dummett: " In the resolution of the conflict between [the view that generally accepted classical modes of inference ought to be theoretically accommodated, and the demand that any such accommodation be achieved without recourse to bivalence] lies, as I see it, one of the most fundamental and intractable problems in the theory of meaning; indeed, in all philosophy. "The present article ventures to suggest that the conflict need not be irresoluble. Helping ourselves only to such conceptual resources as are standardly invoked by proponents of intuitionistic logic, we shall formulate a rudimentary meaning theory for a selection of logical constants, define a relation of valid inferability, and prove that the latter includes all of classical first-order logic. The result is essentially that reported in Sandqvist as Theorem 2.20.2. TheoryWe will be considering a standard-syntax first-order language with ⊃, ⊥ and ∀ as its only primitive logical constants. We assume countable supplies of individual constants, individual functors , and predicates , as well as a denumerably infinite set of individual variables. By a basic 1 formula we will mean one that …[Full Text of this Article]. (shrink)

According to the species of neo-logicism advanced by Hale and Wright, mathematical knowledge is essentially logical knowledge. Their view is found to be best understood as a set of related though independent theses: (1) neo-fregeanism-a general conception of the relation between language and reality; (2) the method of abstraction-a particular method for introducing concepts into language; (3) the scope of logic-second-order logic is logic. The criticisms of Boolos, Dummett, Field and Quine (amongst others) of these theses are explicated and assessed. (...) The issues discussed include reductionism, rejectionism, the Julius Caesar problem, the Bad Company objections, and the charge that second-order logic is set theory in disguise. (shrink)

Evidence is given that implication (and its special case, negation) carry the logical strength of a system of formal logic. This is done by proving normalization and cut elimination for a system based on combinatory logic or λ-calculus with logical constants for and, or, all, and exists, but with none for either implication or negation. The proof is strictly finitary, showing that this system is very weak. The results can be extended to a "classical" version of the system. They can (...) also be extended to a system with a restricted set of rules for implication: the result is a system of intuitionistic higher-order BCK logic with unrestricted comprehension and without restriction on the rules for disjunction elimination and existential elimination. The result does not extend to the classical version of the BCK logic. (shrink)

We prove the following surprising property of Heyting's intuitionistic propositional calculus, IpC. Consider the collection of formulas, φ, built up from propositional variables (p,q,r,...) and falsity $(\perp)$ using conjunction $(\wedge)$ , disjunction (∨) and implication (→). Write $\vdash\phi$ to indicate that such a formula is intuitionistically valid. We show that for each variable p and formula φ there exists a formula Apφ (effectively computable from φ), containing only variables not equal to p which occur in φ, and such that for (...) all formulas ψ not involving $p, \vdash \psi \rightarrow A_p\phi$ if and only if $\vdash \psi \rightarrow \phi$ . Consequently quantification over propositional variables can be modelled in IpC, and there is an interpretation of the second order propositional calculus, IpC2, in IpC which restricts to the identity on first order propositions. An immediate corollary is the strengthening of the usual interpolation theorem for IpC to the statement that there are least and greatest interpolant formulas for any given pair of formulas. The result also has a number of interesting consequences for the algebraic counterpart of IpC, the theory of Heyting algebras. In particular we show that a model of IpC2 can be constructed whose algebra of truth-values is equal to any given Heyting algebra. (shrink)

A new formalism for predicate logic is introduced, with a non-standard method of binding variables, which allows a compositional formalization of certain anaphoric constructions, including donkey sentences and cross-sentential anaphora. A proof system in natural deduction format is provided, and the formalism is compared with other accounts of this type of anaphora, in particular Dynamic Predicate Logic.

A sequent calculus is given in which the management of weakening and contraction is organized as in natural deduction. The latter has no explicit weakening or contraction, but vacuous and multiple discharges in rules that discharge assumptions. A comparison to natural deduction is given through translation of derivations between the two systems. It is proved that if a cut formula is never principal in a derivation leading to the right premiss of cut, it is a subformula of the conclusion. Therefore (...) it is sufficient to eliminate those cuts that correspond to detour and permutation conversions in natural deduction. (shrink)