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.

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)

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)

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)

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)

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)

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)

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)

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 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}$.

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)

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)

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.

Miłosz’s volume Światło dzienne 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)

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)

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.

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 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)

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

The feasible interpolation theorem for semantic derivations from [J. Krajíček, Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic, J. Symbolic Logic 62 457–486] allows to derive from some short semantic derivations of the disjointness of two [Formula: see text] sets [Formula: see text] and [Formula: see text] a small communication protocol computing the Karchmer–Wigderson multi-function [Formula: see text] associated with the sets, and such a protocol further yields a small circuit separating [Formula: see text] from (...) [Formula: see text]. When [Formula: see text] is closed upwards, the protocol computes the monotone Karchmer–Wigderson multi-function [Formula: see text] and the resulting circuit is monotone. Krajíček [Interpolation by a game, Math. Logic Quart. 44 450–458] extended the feasible interpolation theorem to a larger class of semantic derivations using the notion of a real communication complexity. In this paper, we generalize the method to a still larger class of semantic derivations by allowing randomized protocols. We also introduce an extension of the monotone circuit model, monotone circuits with a local oracle, that does correspond to communication protocols for [Formula: see text] making errors. The new randomized feasible interpolation thus shows that a short semantic derivation of the disjointness of [Formula: see text], [Formula: see text] closed upwards, yields a small randomized protocol for [Formula: see text] and hence a small monotone CLO separating the two sets. This research is motivated by the open problem to establish a lower bound for proof system [Formula: see text] operating with clauses formed by linear Boolean functions over [Formula: see text]. The new randomized feasible interpolation applies to this proof system and also to cutting planes CP, to small width resolution over CP of Krajíček [Discretely ordered modules as a first-order extension of the cutting planes proof system, J. Symbolic Logic 63 1582–1596] ) and to random resolution RR of Buss, Kolodziejczyk and Thapen [Fragments of approximate counting, J. Symbolic Logic 79 496–525]. The method does not yield yet lengths-of-proofs lower bounds; for this it is necessary to establish lower bounds for randomized protocols or for monotone CLOs. (shrink)

Ethical attitudes and behaviour are complex. This complexity extends to the influencers operating at different levels both outside and within the organisation, and in different combinations for different individuals. There is hence a growing need to understand the proximal and distal influencers of ethical attitudes, and how these operate in concert at the individual, organisational, and societal levels. Few studies have attempted to combine these main research streams and systematically examine their combined impact. The minority of studies that have taken (...) a combined approach have often done so using conventional statistical and analytical techniques which imply linearity between variables—a situation that rarely exists in business settings and is likely to lead to simplistic or even erroneous conclusions. Applying a fuzzy-set qualitative comparative analysis approach, this paper reports on the mutual and simultaneous influence of individual demographic factors, as well as proximal and distal factors stemming from within and outside the work environment to understand individuals’ ethical views within the workplace. The multiple configurations that emerged reveal the complex nature of influencers of ethical attitudes, and reinforce the view that “one size does not fit all”. We discuss these implications together with managerial recommendations and future research directions. (shrink)

The paper builds on the postulate of “myths we live by,” which shape our imaginative life (and hence our social expectations), but which are also open to reflective study and reinvention. It applies this principle, in particular, to the concepts of love and vulnerability. We are accustomed to think of the condition of vulnerability in an objectifying and distancing way, as something that affects the bearers of specific (disadvantaged) social identities. Against this picture, which can serve as a pretext for (...) paternalist and controlling attitudes to the groups in question – notably to women – Anderson urges us to reimagine our vulnerability as a condition not merely of exposure to violence but of openness to mutual affection, love, and friendship. Hegel’s celebrated image of the owl of Minerva, which takes wing only with the coming of dusk, suggests an association of (philosophical) wisdom with negativity – with the experience of death or loss. Anderson, by contrast, proposes an alternative and more hopeful image of the dawn of enlightenment, in the guise of new ethical dispositions shaped by an emancipatory (and so, no longer an oppressive or sexist) conception of our capacity for love. Her main interlocutors or influences in this piece are Judith Butler (who contributes the idea of a “relational ontology”), Michèle Le Doeuff, and Mary Midgley. (shrink)