We investigate the substitution Frege () proof system and its relationship to extended Frege () in the context of modal and superintuitionistic propositional logics. We show that is p-equivalent to tree-like , and we develop a “normal form” for -proofs. We establish connections between for a logic L, and for certain bimodal expansions of L.We then turn attention to specific families of modal and si logics. We prove p-equivalence of and for all extensions of , all (...) tabular logics, all logics of finite depth and width, and typical examples of logics of finite width and infinite depth. In most cases, we actually show an equivalence with the usual system for classical logic with respect to a naturally defined translation.On the other hand, we establish exponential speed-up of over for all modal and si logics of infinite branching, extending recent lower bounds by P. Hrubeš. We develop a model-theoretical characterization of maximal logics of infinite branching to prove this result. (shrink)

The first complete English translation of a groundbreaking work. An ambitious account of the relation of mathematics to logic. Includes a foreword by Crispin Wright, translators' Introduction, and an appendix on Frege's logic by Roy T. Cook. The German philosopher and mathematician Gottlob Frege (1848-1925) was the father of analytic philosophy and to all intents and purposes the inventor of modern logic. Basic Laws of Arithmetic, originally published in German in two volumes (1893, 1903), is Freges magnum opus. (...) It was to be the pinnacle of Freges lifes work. It represents the final stage of his logicist project the idea that arithmetic and analysis are reducible to logic and contains his mature philosophy of mathematics and logic. The aim of Basic Laws of Arithmetic is to demonstrate the logical nature of mathematical theorems by providing gapless proofs in Frege's formal system using only basic laws of logic, logical inference, and explicit definitions. The work contains a philosophical foreword, an introduction to Frege's logic, a derivation of arithmetic from this logic, a critique of contemporary approaches to the real numbers, and the beginnings of a logicist treatment of real analysis. As is well-known, a letter received from Bertrand Russell shortly before the publication of the second volume made Frege realise that his basic law V, governing the identity of value-ranges, leads into inconsistency. Frege discusses a revision to basic law V written in response to Russells letter in an afterword to volume II. The continuing importance of Basic Laws of Arithmetic lies not only in its bearing on issues in the foundations of mathematics and logic but in its model of philosophical inquiry. Frege's ability to locate the essential questions, his integration of logical and philosophical analysis, and his rigorous approach to criticism and argument in general are vividly in evidence in this, his most ambitious work. Philip Ebert and Marcus Rossberg present the first full English translation of both volumes of Freges major work preserving the original formalism and pagination. The edition contains a foreword by Crispin Wright and an extensive appendix providing an introduction to Frege's formal system by Roy T. Cook. Readership: Scholars and advanced students in philosophy of logic, philosophy of mathematics, and early analytic philosophy. (shrink)

A Frege proof systemFis any standard system of prepositional calculus, e.g., a Hilbert style system based on finitely many axiom schemes and inference rules. An Extended Frege systemEFis obtained fromFas follows. AnEF-sequence is a sequence of formulas ψ1, …, ψκsuch that eachψiis either an axiom ofF, inferred from previous ψuand ψv by modus ponens or of the formq↔ φ, whereqis an atom occurring neither in φ nor in any of ψ1,…,ψi−1. Suchq↔ φ, is called an (...) extension axiom andqa new extension atom. AnEF-proof is anyEF-sequence whose last formula does not contain any extension atom. In [12], S. A. Cook and R. Reckhow proved that the pigeonhole principlePHPhas a simple polynomial sizeEF-proof and conjectured thatPHPdoes not admit polynomial sizeF-proof. In [5], S. R. Buss refuted this conjecture by furnishing polynomial sizeF-proof forPHP. Since then the important separation problem of polynomial sizeFand polynomial sizeEFhas not shown any progress.In [11], S. A. Cook introduced the systemPV, a free variable equational logic whose provable functional equalities are ‘polynomial time verifiable’ and showed that the metamathematics ofFandEFcan be developed inPVand the soundness ofEFproved inPV. In [3], S. R. Buss introduced the first order systemand showed thatis essentially a conservative extension ofPV. There he also introduced a second order system. (shrink)

A Frege proof systemFis any standard system of prepositional calculus, e.g., a Hilbert style system based on finitely many axiom schemes and inference rules. An Extended Frege systemEFis obtained fromFas follows. AnEF-sequence is a sequence of formulas ψ1, …, ψκsuch that eachψiis either an axiom ofF, inferred from previous ψuand ψv by modus ponens or of the formq↔ φ, whereqis an atom occurring neither in φ nor in any of ψ1,…,ψi−1. Suchq↔ φ, is called an (...) extension axiom andqa new extension atom. AnEF-proof is anyEF-sequence whose last formula does not contain any extension atom. In [12], S. A. Cook and R. Reckhow proved that the pigeonhole principlePHPhas a simple polynomial sizeEF-proof and conjectured thatPHPdoes not admit polynomial sizeF-proof. In [5], S. R. Buss refuted this conjecture by furnishing polynomial sizeF-proof forPHP. Since then the important separation problem of polynomial sizeFand polynomial sizeEFhas not shown any progress.In [11], S. A. Cook introduced the systemPV, a free variable equational logic whose provable functional equalities are ‘polynomial time verifiable’ and showed that the metamathematics ofFandEFcan be developed inPVand the soundness ofEFproved inPV. In [3], S. R. Buss introduced the first order systemand showed thatis essentially a conservative extension ofPV. There he also introduced a second order system. (shrink)

Frege’s Grundgesetze der Arithmetik is formally inconsistent. This system is, except for minor differences, second-order logic together with an abstraction operator governed by Frege’s Axiom V. A few years ago, Richard Heck showed that the ramified predicative second-order fragment of the Grundgesetze is consistent. In this paper, we show that the above fragment augmented with the axiom of reducibility for concepts true of only finitely many individuals is still consistent, and that elementary Peano arithmetic (and more) is (...) interpretable in this extended system. (shrink)

We show that the untyped λ -calculus can be extended with Frege's interpretation of propositional notions, provided we restrict β -conversion to positive expressions. The system of illative λ -calculus so obtained admits a natural Scott-style semantics.

The purpose of this paper is to survey the correspondence between bounded arithmetic and propositional proof systems. In addition, it also contains some new results which have appeared as an extended abstract in the proceedings of the conference TAMC 2008 [11].Bounded arithmetic is closely related to propositional proof systems; this relation has found many fruitful applications. The aim of this paper is to explain and develop the general correspondence between propositional proof systems and arithmetic theories, as introduced by Krajíček (...) and Pudlák [46]. Instead of focusing on the relation between particular proof systems and theories, we favour a general axiomatic approach to this correspondence. In the course of the development we particularly highlight the role played by logical closure properties of propositional proof systems, thereby obtaining a characterization of extensions of EF in terms of a simple combination of these closure properties (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim). (shrink)

In [Boccuni 2010], a predicative fragment of Frege’s blv augmented with Boolos’ unrestricted plural quantification is shown to interpret pa2. The main disadvantage of that axiomatisation is that it does not recover Frege Arithmetic fa because of the restrictions imposed on the axioms. The aim of the present article is to show how [Boccuni 2010] can be consistently extended so as to interpret fa and consequently pa2 in a way that parallels Frege’s. In that way, the (...) presented system will be compared with the system pe in [Ferreira 2018] and some relevant differences between the two will be highlighted. (shrink)

In [Boccuni 2010], a predicative fragment of Frege’s blv augmented with Boolos’ unrestricted plural quantification is shown to interpret pa2. The main disadvantage of that axiomatisation is that it does not recover Frege Arithmetic fa because of the restrictions imposed on the axioms. The aim of the present article is to show how [Boccuni 2010] can be consistently extended so as to interpret fa and consequently pa2 in a way that parallels Frege’s. In that way, the (...) presented system will be compared with the system pe in [Ferreira 2018] and some relevant differences between the two will be highlighted. (shrink)

It has been known for a few years that no more than Pi-1-1 comprehension is needed for the proof of "Frege's Theorem". One can at least imagine a view that would regard Pi-1-1 comprehension axioms as logical truths but deny that status to any that are more complex—a view that would, in particular, deny that full second-order logic deserves the name. Such a view would serve the purposes of neo-logicists. It is, in fact, no part of my view that, (...) say, Delta-3-1 comprehension axioms are not logical truths. What I am going to suggest, however, is that there is a special case to be made on behalf of Pi-1-1 comprehension. Making the case involves investigating extensions of first-order logic that do not rely upon the presence of second-order quantifiers. A formal system for so-called "ancestral logic" is developed, and it is then extended to yield what I call "Arché logic". (shrink)

In this article, I first analyze and assess the epistemological and semantic status of canonical value-range equations in the formal language of Frege’s Grundgesetze der Arithmetik. I subsequently scrutinize the relation between (a) his informal, metalinguistic stipulation in Grundgesetze I, Section 3, and (b) its formal counterpart, which is Basic Law V. One point I argue for is that the stipulation in Section 3 was designed not only to fix the references of value-range names, but that it was probably (...) also intended to play a regulative role with an eye to Basic Law V. I further intend to shed new light on the status of Frege’s identification of the truth-values with their unit classes in Grundgesetze I, Section 10 and determine its place and importance in his overall logicist project. In a subsequent section, I first discuss the hypothetical extendability of the logical system of Grundgesetze. In what follows, I analyze the incompleteness of that system—were it not inconsistent and hence trivially complete—by focusing on the role of the definite description operator and the axiom governing it (= Basic Law VI) as well as on the role of the application operator. The latter is defined by means of the former. I further comment on the redundancy of an axiom that could be designed to supplement Basic Law VI by incorporating the second clause of Frege’s two-part elucidation of the description operator. I argue that although it seems likely that Basic Law VI could have been shown to be dispensable in Grundgesetze, Frege would probably have been reluctant to dispense with it, despite his commitment to axiomatic parsimony. In my view, the reason is that he considers it essential that every primitive function-name of his formal language be governed and grounded by a basic law that is tailored to the nature and the role of the primitive name occurring at a key point in the law. Toward the end of the article, I propose solutions to two problems with Frege’s use of “=” in the concept-script sentences that result from his definitions involving the replacement of the double stroke of definition with the judgment-stroke. I conclude the article with a summary of the main results that I have achieved. (shrink)

It is shown that the feasibly constructive arithmetic theory IPV does not prove LMIN, unless the polynomial hierarchy CPV-provably collapses. It is proved that PV plus LMIN intuitionistically proves PIND. It is observed that PV + PIND does not intuitionistically prove NPB, a scheme which states that the extended Frege systems are not polynomially bounded.

My aim is to understand the practice of mathematics in a way that sheds light on the fact that it is at once a priori and capable of extending our knowledge. The account that is sketched draws first on the idea, derived from Kant, that a calculation or demonstration can yield new knowledge in virtue of the fact that the system of signs it employs involves primitive parts that combine into wholes that are themselves parts of larger wholes. Because (...) wholes such as numerals and Euclidean figures both have parts and are parts of larger wholes, their parts can be recombined into new wholes in ways that enable extensions of our knowledge. I show that sentences of Frege 's Begriffsschrift can also be read as involving three such levels of articulation; because they have these three levels, we can understand in essentially the same way how a proof from concepts alone can extend our knowledge. (shrink)

We set out the implication fragment of Frege’s Grundgesetze, clarifying the implication rules and showing that this system extends Absolute Implication, or the implication fragment of Intuitionist logic. We set out a sequent calculus which naturally captures Frege’s implication proofs, and draw particular attention to the Cut-like features of his Hypothetical Syllogism rule.

By a well-known result of Cook and Reckhow [S.A. Cook, R.A. Reckhow, The relative efficiency of propositional proof systems, Journal of Symbolic Logic 44 36–50; R.A. Reckhow, On the lengths of proofs in the propositional calculus, Ph.D. Thesis, Department of Computer Science, University of Toronto, 1976], all Frege systems for the classical propositional calculus are polynomially equivalent. Mints and Kojevnikov [G. Mints, A. Kojevnikov, Intuitionistic Frege systems are polynomially equivalent, Zapiski Nauchnyh Seminarov POMI 316 129–146] have recently shown (...) p-equivalence of Frege systems for the intuitionistic propositional calculus in the standard language, building on a description of admissible rules of IPC by Iemhoff [R. Iemhoff, On the admissible rules of intuitionistic propositional logic, Journal of Symbolic Logic 66 281–294]. We prove a similar result for an infinite family of normal modal logics, including K4, GL, S4, and. (shrink)

This chapter contains sections titled: Dynamical Systems Theory and Coupling Haugeland's Theory of Systems and the Coupling of Components Clark's Theories of Systems and Coupling Conclusion.

We define a mathematical formalism based on the concept of an ‘‘open dynamical system” and show how it can be used to model embodied cognition. This formalism extends classical dynamical systems theory by distinguishing a ‘‘total system’’ (which models an agent in an environment) and an ‘‘agent system’’ (which models an agent by itself), and it includes tools for analyzing the collections of overlapping paths that occur in an embedded agent's state space. To illustrate the way this (...) formalism can be applied, several neural network models are embedded in a simple model environment. Such phenomena as masking, perceptual ambiguity, and priming are then observed. We also use this formalism to reinterpret examples from the embodiment literature, arguing that it provides for a more thorough analysis of the relevant phenomena. (shrink)

Philosophers and cognitive scientists alike have recently been interested in whether cognition extends beyond the boundaries of skin and skull and into the environment. However, the extended cognition hypothesis has suffered many objections over the past few decades. In this paper, I explore the option of control extending beyond the human boundary. My aim is to convince the reader of three things: (i) that control can be implemented in artifacts, (ii) that humans and artifacts can form extended control (...) systems, and (iii) that perhaps extended control ought to be preferred over extended cognition. Using the objections to extended cognition as constraints on my own extended theorizing and the example of autofocus systems in cameras, I decompose and localize the components of an autofocus system that realize the central properties of control from a plausible theory of control in the literature. I then provide criteria according to which control can be extended in a system. Finally, I consider how this theory of extended control ought to be preferred to theories of extended cognition. (shrink)

In this paper we discuss extensions of Feferman's theory T 0 for explicit mathematics by the so-called limit and Mahlo axioms and present a novel approach to constructing natural recursion-theoretic models for systems of explicit mathematics which is based on nonmonotone inductive definitions.

The concept of an extended cognitive system is central to contemporary studies of cognition. In the paper I analyze the place of the epistemic subject within the extended cognitive system. Is it extended as well? In answering this question I focus on the differences between the first and the second wave of arguments for the extended mind thesis. I argue that the position of Cognitive Integration represented by Richard Menary is much more intuitive and (...) fruitful in analyses of cognition and knowledge than the early argument formulated by Andy Clark and David Chalmers. Cognitive Integration is compatible with virtue epistemology of John Greco’s agent reliabilism. The epistemic subject is constituted by its cognitive character composed of an integrated set of cognitive abilities and processes. Some of these processes are extended, they are a manipulation of external informational structures and, as such, they constitute epistemic practices. Epistemic practices are normative; to conduct them correctly the epistemic subject needs to obey epistemic norms embedded in the cultural context. The epistemic subject is not extended because of the casual coupling with external informational artifacts which extend his mind from inside the head and into the world. Rather, cognitive practices constitute the subject’s mind, they transform his cognitive abilities, and this is what makes the mind and epistemic subject “extended”. (shrink)

Building on the original formulation of the autopoietic theory (AT), extended enactivism argues that living beings are autopoietic systems that extend beyond the spatial boundaries of the organism. In this article, we argue that extended enactivism, despite having some basis in AT’s original formulation, mistakes AT’s definition of living beings as autopoietic entities. We offer, as a reply to this interpretation, a more embodied reformulation of autopoiesis, which we think is necessary to counterbalance the (excessively) disembodied spirit of (...) AT’s original formulation. The article aims to clarify and correct what we take to be a misinterpretation of AT as a research program. AT, contrary to what some enactivists seem to believe, did not (and does not) intend to motivate an extended conception of living beings. AT’s primary purpose, we argue, was (and is) to provide a universal individuation criterion for living beings, these understood as discrete bodies that are embedded in, but not constituted by, the environment that surrounds them. However, by giving a more explicitly embodied definition of living beings, AT can rectify and accommodate, so we argue, the enactive extended interpretation of autopoiesis, showing that although living beings do not extend beyond their boundaries as autopoietic unities, they do form part, in normal conditions, of broader autopoietic systems that include the environment. (shrink)

We present a general method for inserting proofs in Frege systems for classical logic that produces systems that can internalize their own proofs.

This paper presents writing as an extended cognitive system comprised of brain, body, and the material form that is writing. Part I introduces the theoretical framework used for the analysis, Material Engagement Theory (MET), and the initial insights into writing systems gained by applying MET to Mesopotamian artifacts for numbers and writing. Part II discusses how writing as a material form has changed over time and why this material change reflects, accumulates, and distributes change in the behaviors and (...) brains of generations of writers. Part III explains why forms of writing used today are a visible form of language in being comprised of contrastive graphic features. Part IV argues against the idea that writing should be excluded from being considered as an extended cognitive system. On the contrary, considering writing from this perspective can provide new insights into the ways we use material forms—not just in writing but more broadly—to change our behaviors and brains, and their roles in intensifying and perpetuating those changes. (shrink)

Cognitive Science, Volume 45, Issue 11, November 2021.

forthcoming in R. Menary (ed.), The Extended Mind.

A notion of feasible function of finite type based on the typed lambda calculus is introduced which generalizes the familiar type 1 polynomial-time functions. An intuitionistic theory IPVω is presented for reasoning about these functions. Interpretations for IPVω are developed both in the style of Kreisel's modified realizability and Gödel's Dialectica interpretation. Applications include alternative proofs for Buss's results concerning the classical first-order system S12 and its intuitionistic counterpart IS12 as well as proofs of some of Buss's conjectures concerning (...) IS12, and a proof that IS12 cannot prove that extended Frege systems are not polynomially bounded. (shrink)

We prove that the problem of determining the minimum propositional proof length is NP- hard to approximate within a factor of 2 log 1 - o(1) n . These results are very robust in that they hold for almost all natural proof systems, including: Frege systems, extended Frege systems, resolution, Horn resolution, the polynomial calculus, the sequent calculus, the cut-free sequent calculus, as well as the polynomial calculus. Our hardness of approximation results usually apply to proof length (...) measured either by number of symbols or by number of inferences, for tree-like or dag-like proofs. We introduce the Monotone Minimum (Circuit) Satisfying Assignment problem and reduce it to the problems of approximation of the length of proofs. (shrink)

We survey the best known lower bounds on symbols and lines in Frege and extended Frege proofs. We prove that in minimum length sequent calculus proofs, no formula is generated twice or used twice on any single branch of the proof. We prove that the number of distinct subformulas in a minimum length Frege proof is linearly bounded by the number of lines. Depthd Frege proofs ofm lines can be transformed into depthd proofs ofO(m d+1) (...) symbols. We show that renaming Frege proof systems are p-equivalent to extended Frege systems. Some open problems in propositional proof length and in logical flow graphs are discussed. (shrink)

This paper explores the implications of extended and distributed cognition theory for our notions of personal identity. On an extended and distributed approach to cognition, external information is under certain conditions constitutive of memory. On a narrative approach to personal identity, autobiographical memory is constitutive of our diachronic self. In this paper, I bring these two approaches together and argue that external information can be constitutive of one’s autobiographical memory and thus also of one’s diachronic self. To develop (...) this claim, I draw on recent empirical work in human-computer interaction, looking at lifelogging technologies in both healthcare and everyday contexts. I argue that personal identity can neither be reduced to psychological structures instantiated by the brain nor by biological structures instantiated by the organism, but should be seen as an environmentally-distributed and relational construct. In other words, the complex web of cognitive relations we develop and maintain with other people and technological artifacts partly determines our self. This view has conceptual, methodological, and normative implications: we should broaden our concepts of the self as to include social and artifactual structures, focus on external memory systems in the (empirical) study of personal identity, and not interfere with people’s distributed minds and selves. (shrink)

Extended and distributed cognition theories argue that human cognitive systems sometimes include non-biological objects. On these views, the physical supervenience base of cognitive systems is thus not the biological brain or even the embodied organism, but an organism-plus-artifacts. In this paper, we provide a novel account of the implications of these views for learning, education, and assessment. We start by conceptualising how we learn to assemble extended cognitive systems by internalising cultural norms and practices. Having a better grip (...) on how extended cognitive systems are assembled, we focus on the question: If our cognition extends, how should we educate and assess such extended cognitive systems? We suggest various ways to minimize possible negative effects of extending one’s cognition and to efficiently find and organise (online) information by adopting a virtue epistemology approach. Educational and assessment implications are foregrounded, particularly in the case of Danish students’ use of the Internet during exams. (shrink)

We consider tautologies formed form a pseudo-random number generator, defined in Krajicek [11] and in Alekhnovich et al. [2]. We explain a strategy of proving their hardness for Extended Frege systems via a conjecture about bounded arithmetic formulated in Krajicek [11]. Further we give a purely finitary statement, in the form of a hardness condition imposed on a function, equivalent to the conjecture. This is accompanied by a brief explanation, aimed at non-specialists, of the relation between prepositional proof (...) complexity and bounded arithmetic. (shrink)

The complementary properties and functions of cognitive artifacts and other external resources are integrated into the human cognitive system to varying degrees. The goal of this paper is to develop some of the tools to conceptualize this complementary integration between agents and artifacts. It does so by proposing a multidimensional framework, including the dimensions of information flow, reliability, durability, trust, procedural transparency, informational transparency, individualization, and transformation. The proposed dimensions are all matters of degree and jointly they constitute a (...) multidimensional space in which situated cognitive systems can be located and have certain dimensional configurations. These dimensions provide a new perspective on the conditions for cognitive extension. They are, however, not meant to provide a set of necessary and sufficient conditions, but to provide a toolbox for investigating the degree and nature of the integration of agent and artifact into “new systemic wholes”. The higher a situated system scores on the proposed dimensions, the more functional integration occurs, and the more tightly coupled the system is. (shrink)

In this paper we introduce a system AID of bounded arithmetic. The main feature of AID is to allow a form of inductive definitions, which was extracted from Buss’ propositional consistency proof of Frege systems F in Buss 3–29). We show that AID proves the soundness of F , and conversely any Σ 0 b -theorem in AID yields boolean sentences of which F has polysize proofs. Further we define Σ 1 b -faithful interpretations between AID+Σ 0 b (...) -CA and a quantified theory QALV of an equational system ALV in Clote 57–106). Hence ALV also proves the soundness of F. (shrink)

Let g be a map defined as the Nisan–Wigderson generator but based on an NP ∩ coNP -function f. Any string b outside the range of g determines a propositional tautology τb expressing this fact. Razborov [27] has conjectured that if f is hard on average for P/poly then these tautologies have no polynomial size proofs in the Extended Frege system EF. We consider a more general Statement that the tautologies have no polynomial size proofs in any (...) propositional proof system. This is equivalent to the statement that the complement of the range of g contains no infinite NP set. We prove that Statement is consistent with Cook' s theory PV and, in fact, with the true universal theory T PV in the language of PV. If PV in this consistency statement could be extended to "a bit" stronger theory then Razborov's conjecture would follow, and if TPV could be added too then Statement would follow. We discuss this problem in some detail, pointing out a certain form of reflection principle for propositional logic, and we introduce a related feasible disjunction property of proof systems. (shrink)

The complementary properties and functions of cognitive artifacts and other external resources are integrated into the human cognitive system to varying degrees. The goal of this paper is to develop some of the tools to conceptualize this complementary integration between agents and artifacts. It does so by proposing a multidimensional framework, including the dimensions of information flow, reliability, durability, trust, procedural transparency, informational transparency, individualization, and transformation. The proposed dimensions are all matters of degree and jointly they constitute a (...) multidimensional space in which situated cognitive systems can be located and have certain dimensional configurations. These dimensions provide a new perspective on the conditions for cognitive extension. They are, however, not meant to provide a set of necessary and sufficient conditions, but to provide a toolbox for investigating the degree and nature of the integration of agent and artifact into “new systemic wholes”. The higher a situated system scores on the proposed dimensions, the more functional integration occurs, and the more tightly coupled the system is. (shrink)

We present a simple propositional proof system which consists of a single axiom schema and a single rule, and use this system to construct a sequence of combinatorial tautologies that, when added to any Frege system, p-simulates extended-Frege systems.

The canonical pair of a proof system P is the pair of disjoint NP sets where one set is the set of all satisfiable CNF formulas and the other is the set of CNF formulas that have P-proofs bounded by some polynomial. We give a combinatorial characterization of the canonical pairs of depth d Frege systems. Our characterization is based on certain games, introduced in this article, that are parametrized by a number k, also called the depth. We (...) show that the canonical pair of a depth d Frege system is polynomially equivalent to the pair (Ad+2,Bd+2) where Ad+2 (respectively, Bd+1) are depth d+1 games in which Player I (Player II) has a positional winning strategy. Although this characterization is stated in terms of games, we will show that these combinatorial structures can be viewed as generalizations of monotone Boolean circuits. In particular, depth 1 games are essentially monotone Boolean circuits. Thus we get a generalization of the monotone feasible interpolation for Resolution, which is a property that enables one to reduce the task of proving lower bounds on the size of refutations to lower bounds on the size of monotone Boolean circuits. However, we do not have a method yet for proving lower bounds on the size of depth d games for d>1. (shrink)

In proof theory one distinguishes sequent proofs with cut and cut-free sequent proofs, while for proof complexity one distinguishes Frege systems and extended Frege systems. In this paper we show how deep inference can provide a uniform treatment for both classifications, such that we can define cut-free systems with extension, which is neither possible with Frege systems, nor with the sequent calculus. We show that the propositional pigeonhole principle admits polynomial-size proofs in a cut-free system (...) with extension. We also define cut-free systems with substitution and show that the cut-free system with extension p-simulates the cut-free system with substitution. (shrink)

Let L be a first-order language and Φ and ψ two $\Sigma _{1}^{1}$ L-sentences that cannot be satisfied simultaneously in any finite L-structure. Then obviously the following principle Chain L,Φ,ψ (n,m) holds: For any chain of finite L-structures C 1 ,...,C m with the universe [n] one of the following conditions must fail: 1. $C_{1}\vDash \Phi $ , 2. C i ≅ C i+1 , for i = 1,...,m — 1, 3. $C_{m}\vDash \Psi $ . For each fixed L and (...) parameters n,m the principle Chain L,Φ,ψ (n,m) can be encoded into a propositional DNF formula of size polynomial in n,m. For any language L containing only constants and unary predicates we show that there is a constant c L such that the following holds: If a constant depth Frege system in DeMorgan language proves Chain L,Φ,ψ (n, c L · n) by a size s proof then the class of finite L-structures with universe [n] satisfying Φ can be separated from the class of those L-structures on [n] satisfying ψ by a depth 3 formula of size $2^{{\rm log}(s)^{O(1)}}$ and with bottom fan-in ${\rm log}(s)^{O(1)}$. (shrink)

ABSTRACTIn this paper, we present a generalisation of proof simulation procedures for Frege systems by Bonet and Buss to some logics for which the deduction theorem does not hold. In particular, we study the case of finite-valued Łukasiewicz logics. To this end, we provide proof systems and which augment Avron's Frege system HŁuk with nested and general versions of the disjunction elimination rule, respectively. For these systems, we provide upper bounds on speed-ups w.r.t. both the number of (...) steps in proofs and the length of proofs. We also consider Tamminga's natural deduction and Avron's hypersequent calculus GŁuk for 3-valued Łukasiewicz logic and generalise our results considering the disjunction elimination rule to all finite-valued Łukasiewicz logics. (shrink)

Given the metaphysical and explanatory stalemate between Embedded and Extended cognition, different authors proposed moral arguments to overcome such a deadlock in favor of EXT. Farina and Lavazza attribute to EXT and EMB a substantive moral content, arguing in favor of the former by virtue of its progressiveness and inclusiveness. In this treatment, I criticize four of their moral arguments. In Sect. 2, I focus on the argument from legitimate interventions and on the argument from extended agency. Section (...) 3 concerns the argument from better protection and the argument from better treatment. Sections 4 and 5 are dedicated to counterarguments against each respectively. By distinguishing between EXT and the extended view, I argue that it is sufficient to use this second version for directly addressing and evaluating moral problems on normative grounds, independently of the causal or constitutive cognitive influence of the external resource on the agents’ minds. Moreover, I argue that the arguments and assumptions used by EXT theorists do not foster values of progressiveness and inclusiveness. To conclude, in Sect. 6, I show that the analysis of each argument converges on the conclusion that EXT does not have substantive moral content and implications per se, since they always depend on further assumptions. (shrink)

The increasing popularity of artificial cognitive enhancements raises the issue of their impact on the agent’s personal autonomy, and issues pertaining to how the latter is to be secured. The extended mind thesis implies that mental states responsible for autonomous action can be partly constituted by the workings of cognitive artifacts themselves, and the question then arises of whether this commits one to embracing an extended agent thesis. My answer is negative. After briefly presenting the main accounts on (...) the conditions for autonomous agency, and analyzing how the latter can be protected from threats posed by the use of cognitive artifacts, I argue that autonomous agency is essentially tied to conscious experience and intentionality, which in turn can only be attributed to the human part of any extended cognitive system. I present both theoretical (conceptual) and practical arguments against recognizing the entire extended system, composed of one human and an artifact, as an autonomous agent. (shrink)

Robert Rupert argues against the view that human cognitive processes comprise elements beyond the boundary of the organism, developing a systems-based conception in place of this extended view. He also argues for a conciliatory understanding of the relation between the computational approach to cognition and the embedded and embodied views.

According to Frege, neither demonstratives nor indexicals are singular terms; only a demonstrative together with ‘circumstances accompanying its utterance’ has sense and singular reference. While this view seems defensible for demonstratives, where demonstrations serve as non-verbal signs, indexicals, especially pure indexicals like ‘I’, ‘here’, and ‘now’, seem not to be in need of completion by circumstances of utterance. In this paper I argue on the basis of independent reasons that indexicals are in fact in need of completion; I identify (...) the completers as uses of circumstances of utterance by the speaker; and I show how these uses together with the utterance of indexical sentences express thoughts. The starting point of the paper is a criticism of Kripke’s and Künne’s alternative treatment of indexicals in Frege’s framework. (shrink)