We show that the bounded arithmetic theory V0 does not prove that the polynomial time hierarchy collapses to the linear time hierarchy . The result follows from a lower bound for bounded depth circuits computing prefix parity, where the circuits are allowed some auxiliary input; we derive this from a theorem of Ajtai.

We show, under the assumption that factoring is hard, that a model of PV exists in which the polynomial hierarchy does not collapse to the linear hierarchy; that a model of S21 exists in which NP is not in the second level of the linear hierarchy; and that a model of S21 exists in which the polynomial hierarchy collapses to the linear hierarchy. Our methods are model-theoretic. We use the assumption about factoring to get a model in which the weak (...) pigeonhole principle fails in a certain way, and then work with this failure to obtain our results. As a corollary of one of the proofs, we also show that in S21 the failure of WPHP (for Σb1 definable relations) implies that the strict version of PH does not collapse to a finite level. (shrink)

Modifying the methods of Z. Adamowicz's paper Herbrand consistency and bounded arithmetic [3] we show that there exists a number n such that ⋃m Sm (the union of the bounded arithmetic theories Sm) does not prove the Herbrand consistency of the finitely axiomatizable theory $S_{3}^{n}$.

We prove that any proof of a [Formula: see text] sentence in the theory [Formula: see text] can be translated into a proof in [Formula: see text] at the cost of a polynomial increase in size. In fact, the proof in [Formula: see text] can be obtained by a polynomial-time algorithm. On the other hand, [Formula: see text] has nonelementary speedup over the weaker base theory [Formula: see text] for proofs of [Formula: see text] sentences. We also show that for (...) [Formula: see text], proofs of [Formula: see text] sentences in [Formula: see text] can be translated into proofs in [Formula: see text] at a polynomial cost in size. Moreover, the [Formula: see text]-conservativity of [Formula: see text] over [Formula: see text] can be proved in [Formula: see text], a fragment of bounded arithmetic corresponding to polynomial-time computation. For [Formula: see text], this answers a question of Clote, Hájek and Paris. (shrink)

We show that the arithmetical theory -INDx5, formalized in the language of Buss, i.e. with x/2 but without the MSP function x/2y, does not prove that every nontrivial divisor of a power of 2 is even. It follows that this theory proves neither NP=coNP nor.

We use finite model theory to prove:Let m ≥ 2. Then: If there exists k such that NP ⊆ σmTIME ∩ ΠmTIME, then for every r there exists kr such that PNP[nr] ⊆ σmTIME ∩ ΠmTIME; If there exists a superpolynomial time-constructible function f such that NTIME ⊆ Σpm ∪ Πpm, then additionally PNP[nr] ⊈ Σpm ∪ Πpm.This strengthens a result by Mocas [M96] that for any r, PNP[nr] ⊈ NEXP.In addition, we use FM-truth definitions to give a simple sufficient (...) condition for the σ11 arity hierarchy to be strict over finite models. (shrink)

We study the long-standing open problem of giving$\forall {\rm{\Sigma }}_1^b$separations for fragments of bounded arithmetic in the relativized setting. Rather than considering the usual fragments defined by the amount of induction they allow, we study Jeřábek’s theories for approximate counting and their subtheories. We show that the$\forall {\rm{\Sigma }}_1^b$Herbrandized ordering principle is unprovable in a fragment of bounded arithmetic that includes the injective weak pigeonhole principle for polynomial time functions, and also in a fragment that includes the surjective weak pigeonhole (...) principle for FPNPfunctions. We further give new propositional translations, in terms of random resolution refutations, for the consequences of$T_2^1$augmented with the surjective weak pigeonhole principle for polynomial time functions. (shrink)

D’Aquino et al. (J Symb Log 75(1):1–11, 2010) have recently shown that every real-closed field with an integer part satisfying the arithmetic theory IΣ4 is recursively saturated, and that this theorem fails if IΣ4 is replaced by IΔ0. We prove that the theorem holds if IΣ4 is replaced by weak subtheories of Buss’ bounded arithmetic: PV or $${\Sigma^b_1-IND^{|x|_k}}$$. It also holds for IΔ0 (and even its subtheory IE 2) under a rather mild assumption on cofinality. On the other hand, it (...) fails for the extension of IOpen by an axiom expressing the Bézout property, even under the same assumption on cofinality. (shrink)

We prove that: • if there is a model of I∆₀ + ¬ exp with cofinal Σ₁-definable elements and a Σ₁ truth definition for Σ₁ sentences, then I∆₀ + ¬ exp +¬BΣ₁ is consistent, • there is a model of I∆₀ Ω₁ + ¬ exp with cofinal Σ₁-definable elements, both a Σ₂ and a ∏₂ truth definition for Σ₁ sentences, and for each n > 2, a Σ n truth definition for Σ n sentences. The latter result is obtained by (...) constructing a model with a recursive truth-preserving translation of Σ₁ sentences into boolean combinations of $\exists \sum {\begin{array}{*{20}{c}} h \\ 0 \\ \end{array} } $ sentences. We also present an old but previously unpublished proof of the consistency of I∆₀ + ¬ exp + ¬BΣ₁ under the assumption that the size parameter in Lessan's ∆₀ universal formula is optimal. We then discuss a possible reason why proving the consistency of I∆₀ + ¬ exp + ¬BΣ₁ unconditionally has turned out to be so difficult. (shrink)

We show that for each n ≥ 1, if T2n does not prove the weak pigeonhole principle for Σbn functions, then the collection scheme B Σ1 is not finitely axiomatizable over T2n. The same result holds with Sn2 in place of T 2n.

We study the first-order consequences of Ramsey’s Theorem fork-colourings ofn-tuples, for fixed$n, k \ge 2$, over the relatively weak second-order arithmetic theory$\mathrm {RCA}^*_0$. Using the Chong–Mourad coding lemma, we show that in a model of$\mathrm {RCA}^*_0$that does not satisfy$\Sigma ^0_1$induction,$\mathrm {RT}^n_k$is equivalent to its relativization to any proper$\Sigma ^0_1$-definable cut, so its truth value remains unchanged in all extensions of the model with the same first-order universe.We give a complete axiomatization of the first-order consequences of$\mathrm {RCA}^*_0 + \mathrm {RT}^n_k$for$n \ge (...) 3$. We show that they form a non-finitely axiomatizable subtheory of$\mathrm {PA}$whose$\Pi _3$fragment coincides with$\mathrm {B} \Sigma _1 + \exp $and whose$\Pi _{\ell +3}$fragment for$\ell \ge 1$lies between$\mathrm {I} \Sigma _\ell \Rightarrow \mathrm {B} \Sigma _{\ell +1}$and$\mathrm {B} \Sigma _{\ell +1}$. We also give a complete axiomatization of the first-order consequences of$\mathrm {RCA}^*_0 + \mathrm {RT}^2_k + \neg \mathrm {I} \Sigma _1$. In general, we show that the first-order consequences of$\mathrm {RCA}^*_0 + \mathrm {RT}^2_k$form a subtheory of$\mathrm {I} \Sigma _2$whose$\Pi _3$fragment coincides with$\mathrm {B} \Sigma _1 + \exp $and whose$\Pi _4$fragment is strictly weaker than$\mathrm {B} \Sigma _2$but not contained in$\mathrm {I} \Sigma _1$.Additionally, we consider a principle$\Delta ^0_2$-$\mathrm {RT}^2_2$which is defined like$\mathrm {RT}^2_2$but with both the$2$-colourings and the solutions allowed to be$\Delta ^0_2$-sets rather than just sets. We show that the behaviour of$\Delta ^0_2$-$\mathrm {RT}^2_2$over$\mathrm {RCA}_0 + \mathrm {B}\Sigma ^0_2$is in many ways analogous to that of$\mathrm {RT}^2_2$over$\mathrm {RCA}^*_0$, and that$\mathrm {RCA}_0 + \mathrm {B} \Sigma ^0_2 + \Delta ^0_2$-$\mathrm {RT}^2_2$is$\Pi _4$- but not$\Pi _5$-conservative over$\mathrm {B} \Sigma _2$. However, the statement we use to witness failure of$\Pi _5$-conservativity is not provable in$\mathrm {RCA}_0 +\mathrm {RT}^2_2$. (shrink)

We define a new NP search problem, the “local improvement” principle, about labellings of an acyclic, bounded-degree graph. We show that, provably in , it characterizes the consequences of and that natural restrictions of it characterize the consequences of and of the bounded arithmetic hierarchy. We also show that over V0 it characterizes the consequences of V1 and hence that, in some sense, a miniaturized version of the principle gives a new characterization of the consequences of . Throughout our search (...) problems are “type-2” NP search problems, which take second-order objects as parameters. (shrink)

For any n, we construct a model of in which each formula is equivalent to an formula.

Author: Kołodziejczyk Sebastian Tomasz Title: ON THE MUTUAL RELATIONSHIP BETWEEN THE CONCEPT OF BEING AND THE PLURALITY OF METAPHYSICAL DISCOURSES (O związkach między wielością dyskursów metafizycznych a pojęciem bytu) Source: Filo-Sofija year: 2011, vol:.15, number: 2011/4, pages: 865-880 Keywords: METAPHYSICS, ARISTOTLE, BEING, CONCEPT OF BEING, CATEGORIES, UNIVERSALS, PARTICULARS, PARTICULARITY Discipline: PHILOSOPHY Language: POLISH Document type: ARTICLE Publication order reference (Primary author’s office address): E-mail: www:The aim of the paper is to argue that there is a mutual relationship between the (...) concept of being as it is conceived of in the classical Aristotelian metaphysics and the plurality of possible metaphysical discourses. That thesis is rooted in the inherent ambiguity of the concept of being and some consequences connected therewith. Three forms of metaphysical thinking are taken into account: the metaphysics of formal interpretation of the concept of being, metaphysics of existential determination of being, and metaphysics of the material content of every conceptual representation of being. (shrink)

The theory , axiomatized by the induction scheme for sharply bounded formulae in Buss’ original language of bounded arithmetic , has recently been unconditionally separated from full bounded arithmetic S2. The method used to prove the separation is reminiscent of those known from the study of open induction.We make the connection to open induction explicit, showing that models of can be built using a “nonstandard variant” of Wilkie’s well-known technique for building models of IOpen. This makes it possible to transfer (...) many results and methods from open to sharply bounded induction with relative ease.We provide two applications: the Shepherdson model of IOpen can be embedded into a model of , which immediately implies some independence results for ; extended by an axiom which roughly states that every number has a least 1 bit in its binary notation, while significantly stronger than plain , does not prove the infinity of primes. (shrink)

Journal of Mathematical Logic, Volume 22, Issue 03, December 2022. We study a new class of NP search problems, those which can be proved total using standard combinatorial reasoning based on approximate counting. Our model for this kind of reasoning is the bounded arithmetic theory [math] of [E. Jeřábek, Approximate counting by hashing in bounded arithmetic, J. Symb. Log. 74(3) (2009) 829–860]. In particular, the Ramsey and weak pigeonhole search problems lie in the new class. We give a purely computational (...) characterization of this class and show that, relative to an oracle, it does not contain the problem CPLS, a strengthening of PLS. As CPLS is provably total in the theory [math], this shows that [math] does not prove every [math] sentence which is provable in bounded arithmetic. This answers the question posed in [S. Buss, L. A. Kołodziejczyk and N. Thapen, Fragments of approximate counting, J. Symb. Log. 79(2) (2014) 496–525] and represents some progress in the program of separating the levels of the bounded arithmetic hierarchy by low-complexity sentences. Our main technical tool is an extension of the “fixing lemma” from [P. Pudlák and N. Thapen, Random resolution refutations, Comput. Complexity, 28(2) (2019) 185–239], a form of switching lemma, which we use to show that a random partial oracle from a certain distribution will, with high probability, determine an entire computation of a [math] oracle machine. The introduction to the paper is intended to make the statements and context of the results accessible to someone unfamiliar with NP search problems or with bounded arithmetic. (shrink)

The paper discusses the notion of finite model truth definitions (or FM-truth definitions), introduced by M. Mostowski as a finite model analogue of Tarski's classical notion of truth definition. We compare FM-truth definitions with Vardi's concept of the combined complexity of logics, noting an important difference: the difficulty of defining FM-truth for a logic ᵍ does not depend on the syntax of L, as long as it is decidable. It follows that for a natural ᵍ there exist FM-truth definitions whose (...) evaluation is much easier than the combined complexiy of ᵍ would suggest. We apply the general theory to give a complexity-theoretical characterization of the logics for which the $\Sigma_{m}^{d}$ classes (prenex classes of higher order logics) define FM-truth. For any $d \geq 2.m \geq 1$ we construct a family $\{[\Sigma_{m}^{d}]^{\leg\kappa}\}\kappa\in\omega$ of syntactically defined fragments of $\Sigma_{m}^{d}$ which satisfy this characterization. We also use the $[\Sigma_{m}^{d}]\leg\kappa$ classes to give a refinement of known results on the complexity classes captured by $\Sigma_{m}^{d}$ . We close with a few simple corollaries, one of which gives a sufficient condition for the existence, given a vocabulary $\sigma$ , of a fixed number $\kappa$ such that model checking for all first order sentences over $\sigma$ can be done in deterministic time $n^{\kappa}$. (shrink)

Throughout the centuries, the doctrine of divine simplicity laid at the heart of Christian theology. In Thomas Aquinas’ mature thought, simplicity occupies a privileged place among other attributes of God. A simple simple being is a being that does not consist of any parts or constituents. God’s being simple means that he does not exhibit any of the seven types of composition. The arguments that serve as the justification for this thesis can be divided into four groups which I labeled: (...) the argument from the lack of potentiality, the argument from the priority of parts to the whole, the argument from the anterior maker and the argument from perfection. All of them begin with identifying God with the first cause of all things and add other premises that are specific to them. The first argument — that the first cause does not have potentiality and every composite being does have it. The second — that everything that is composite depends on it’s parts while the first cause is not dependent upon anything. The third — that every composite being needs a cause or explanation and the first cause has neither. The fourth — that the first cause is a perfectly good being and such a being cannot be composite. The analyses that were conducted show that the first two reasonings seem to be unsound. The third of the arguments provides a fine justification for the thesis in question. The fourth may serve as an additional, but weaker justification for it. (shrink)

The article attempts to prove whether some elements of New Deal make it a revolutionary phenomenon. When thinking of New Deal as a model of revolution it can be said that the revolutionary change was the liberation of the bureaucratic class. It was the government that was liberated from the power of citizens. Therefore, it can also be said that the change was made without no change in the political system. The United States of America remained a democratic country but (...) the power was transferred from the citizens to the bureaucratic apparatus. This, apart from the violent character of the changes, could have caused Garrett to define Neal Deal as a revolution that happened behind the back of the biggest opponents of revolution. (shrink)

Presented paper is my reply to Prof. Andrzej Biłat’s review of the book Przewodnik po metafizyce (A Companion to Metaphysics) edited by myself and published by WAM Press. It contains answers to both general and particular remarks and comments risen by Prof. Biłat.

The crisis of metaphysics has many roots. One of them is recognized to be a kind of semantic failure. It lies in the fact that the meaning and reference of metaphysical propositions as well as metaphysical terms seems to be problematic. This diagnosis was first established by I. Kant and then repeated by some of the XXth century philosophers. In this paper I will show what role is played by what I called the Requirement of Reference (RR) in the analysis (...) of the metaphysical discourse. I will argue that the RR draws the limitations for the conceptual and propositional schemata of metaphysics and, at the same time, prevents metaphysics from making de re assertions and utterances. I shall also examine in this light some of Ludwig Wittgenstein's theses from Tractatus and Philosophical Investigations in order to argue that two sorts of metaphysical considerations are possible despite of the above-mentioned criticism. One of them is the analysis of what might be shown but cannot be expressed in language. The other is the deep analysis of the conceptual schemata that constitute the foundations of human thought. (shrink)

The classical arguments against metaphysics provided by Immanuel Kant, neopositivists and recently by analytical philosophers focus on the problem of meaning. In my paper I would like to shed a little bit of light on different dimensions of this problem in the metaphysical discourse and make a proposition how to overcome the difficulties that arise from this kind of discourse.

The classical arguments against metaphysics provided by Immanuel Kant, neopositivists and recently by analytical philosophers focus on the problem of meaning. In my paper I would like to shed a little bit of light on different dimensions of this problem in the metaphysical discourse and make a proposition how to overcome the difficulties that arise from this kind of discourse.

This paper is devoted to one of the most intriguing theory that was invented by medieval theologians and philosophers in order to explain the nature of God. I am not personally keen on the theological dimension of this idea, I would rather like to focus on its promising philosophical usefulness and its explanatory power. For the very long time I was hesitating what aspect of this theory to choose as the most interesting and most illuminating. I eventually made a decision (...) that there is still a very important and unsolved problem with 'pure experience' that has nothing to do with any concepts and theories; that is totally direct and devoid of any mediating factors. It seems to be very interesting to shed a little bit of light on it and combine it with what is at first sight such an old-fashioned theory as the theory of transcendental. My paper is divided into three sections. In the first of them will consider some difficulties connected with the problem of pure experience. In the second part the theory of transcendentals is outlined. The third section contains the application of the theory of transcendental to the problem of pure experience. (shrink)

This paper is devoted to one of the most intriguing theory that was invented by medieval theologians and philosophers in order to explain the nature of God. I am not personally keen on the theological dimension of this idea, I would rather like to focus on its promising philosophical usefulness and its explanatory power. For the very long time I was hesitating what aspect of this theory to choose as the most interesting and most illuminating. I eventually made a decision (...) that there is still a very important and unsolved problem with 'pure experience' that has nothing to do with any concepts and theories; that is totally direct and devoid of any mediating factors. It seems to be very interesting to shed a little bit of light on it and combine it with what is at first sight such an old-fashioned theory as the theory of transcendental. My paper is divided into three sections. In the first of them will consider some difficulties connected with the problem of pure experience. In the second part the theory of transcendentals is outlined. The third section contains the application of the theory of transcendental to the problem of pure experience. (shrink)

Miłosz’s volume Światło dzienne (Daylight, 1953) is conventionally read by critics as political poetry deeply engaged with history. The article offers a corrective to this traditional reading by interpreting the volume as interplay of European and American influences. As a European poet, Miłosz had experienced the violent demise of ideals at the foundation of the Old World. Światło dzienne is, therefore, at one level, an elegiac volume in which both persons and ideas are mourned. On the other hand, to the (...) extent that America continues for Miłosz the noble ideas abandoned in Europe, he cannot accept what he regards as their misguided or perverse incarnations. This explains the emotional climate of the whole volume, with its dominant mood of disappointment, anger and refusal of reconciliation. Światło dzienne is American in its outlook in taking seriously America’s status as a superpower and its influence on the future direction of global history. It is anti-American, however, in identifying America’s perceived failures to live up to the post-war challenge for human civilization in general and the consequent dangers. The article intends to assess Miłosz’s debt to English-language poetry in this volume in light of his personal notes from his reading and translation work at the time. (shrink)

In this book, an international team of scholars from leading American, British and Continental European universities presents original ideas about religious epistemology, the philosophy of God's action in the world, including the problem of evil and Divine Providence, and the philosophical challenge of religious diversity.