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

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

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)

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)

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)

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)

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.

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

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

Epistemicism associates vagueness with ignorance produced by semantic plasticity: the shiftiness of intensions in our language resulting from small changes in usage. The recent literature (Caie 2012; Magidor 2018; Yli-Vakkuri 2016) points to a missing piece in the epistemicist theory of vagueness, namely a clear account of the semantics of the definiteness operator Δ. The fundamentals of the epistemicist theory are well understood. However, the technical work of defining the definiteness operator has proven difficult. There are several desiderata that we (...) would like Δ to satisfy. For instance, we would like the epistemicist notion of ‘definiteness’ to interact well with modal operators and validate intuitive principles like ‘necessarily, if φ is definitely true, then φ is true’. Providing an account that would meet all such desiderata has eluded the epistemicists so far. In this paper, I present a novel version of a multidimensional model inspired by the work of Robert Stalnaker and David Kaplan. Using this model, I provide an account of epistemicist definiteness that meets our desiderata. (shrink)

The epistemicist theory aims to explain ignorance due to vagueness by semantic plasticity: the shiftiness of intensions across close possible worlds resulting from shiftiness in usage. This explanation is challenged by the Omniscient Speaker Puzzle (Sennet in Philos Stud 161(2):273–285, 2012). Suppose that an omniscient speaker, Barney, who knows all the facts about usage and how these facts determine the intensions of expressions, cooks up a scheme to stabilise the intension of a normally semantically plastic term like ‘rich’. It seems (...) that ‘rich’ would display all the phenomena associated with vagueness without being semantically plastic, thus making the epistemicist explanation of ignorance due to vagueness insufficient. In this paper, I present a few choice points for epistemicism that arise as a result of the puzzle. (shrink)

a This is an outline of a coherence theory of law. Its basic ideas are: reasonable support and weighing of reasons. All the rest is commentary.a (TM) These words at the beginning of the preface of this book perfectly indicate what On Law and Reason is about. It is a theory about the nature of the law which emphasises the role of reason in the law and which refuses to limit the role of reason to the application of deductive logic. (...) In 1989, when the first edition of On Law and Reason appeared, this book was ground breaking for several reasons. It provided a rationalistic theory of the law in the language of analytic philosophy and based on a thorough understanding of the results, including technical ones, of analytic philosophy. That was not an obvious combination at the time of the booka (TM)s first appearance and still is not. The result is an analytical rigor that is usually associated with positivist theories of the law, combined with a philosophical position that is not natural law in a strict sense, but which shares with it the emphasis on the role of reason in determining what the law is. If only for this rare combination, On Law and Reason still deserves careful study. On Law and Reason also foreshadowed and influenced a development in the field of Legal Logic that would take place in the nineties of the 20th century, namely the development of non-monotonic (a defeasiblea (TM)) logics for the analysis of legal reasoning. In the new Introduction to this second edition, this aspect is explored in some more detail. (shrink)

Leszek Kołakowski explores 23 questions asked by great philosophers, introducing us to the great ideas and philosophers of Western thought.

Niniejsza wypowiedź jest próbą ukazania wyższości intelektualnej jednostki wybitnej nad jednostkami przeciętnymi. Transgresja jest tutaj formą przejścia, przemiany artysty, negującego zastany porządek świata, pragnącego podłożyć podwaliny pod nową rzeczywistość widzianą oczami szalonego geniusza - Friedricha Nietzschego, do którego często się odwołuję. Jego pojęcie \"Nadczłowieka\" jest tożsame z pojęciem genialnego twórcy, jednostki wybitnej, niezrozumiałej przez pospólstwo, która swoimi horyzontami twórczymi wybiega daleko poza własną epokę\".

It is proved that the following conditions are equivalent: (a) there exists a complete, atomless, σ-centered Boolean algebra, which does not contain any regular, atomless, countable subalgebra, (b) there exists a nowhere dense ultrafilter on ω. Therefore, the existence of such algebras is undecidable in ZFC. In "forcing language" condition (a) says that there exists a non-trivial σ-centered forcing not adding Cohen reals.

"[An] important essay by a philosopher who more convincingly than any other I can think of demonstrates the continuing significance of his vocation in the life of our culture."--Karsten Harries, The New York Times Book Review With The Presence of Myth , Kolakowski demonstrates that no matter how hard man strives for purely rational thought, there has always been-and always will be-a reservoir of mythical images that lend "being" and "consciousness" a specifically human meaning. "Kolakowski undertakes a philosophy of culture (...) which extends to all realms of human intercourse--intellectual, artistic, scientific, and emotional. . . . [His] book has real significance for today, and may well become a classic in the philosophy of culture."-- Anglican Theological Review. (shrink)

Procrastination as putting off until tomorrow what one had intended to do today is well-known tendency in everyday life. In an attempt to understand the character of procrastination in different life-domains, a large body of research has been accumulated over the last decades. This article was aimed to evaluate a specific decisional procrastination of school-to-work transition that is treated as maturity postponement. Two studies are reported examining SWT procrastination defined as career indecision among Polish students graduating universities. In Study 1, (...) attitudinal and identity statuses were analyzed as correlates of career procrastination. A path analysis conducted for the model, which was aimed to explain the influence of career self-efficacy and occupational commitment on career indecision, revealed its very good fitness. Those two independent variables explain 10% of career indecision variance. Stepwise multiple regression analyses conducted to ascertain relationship of five identity statuses to procrastination measure showed that Commitment Making and Ruminative Exploration are strongest predictor variables. In study 2, the stepwise multiple regression analyses conducted to ascertain the independent relationship of each of Big Five personality factor revealed that Neuroticism and Extraversion accounts of the most of explained variance of school-to-work transition procrastination. (shrink)

Źródeł koncepcji genocentrycznej należy dopatrywać się w dynamicznym rozwoju XIX- i XX-wiecznej genetyki – zwłaszcza współczesnej syntezy ewolucyjnej oraz genetyki molekularnej. Za ideą tą stoi teza, iż w naukach biologicznych wyjaśnienia odwołujące się do czynników genetycznych są uprzywilejowane; przy tym istotnym założeniem idei genocentrycznej w ramach genetyki molekularnej jest to, że geny oraz kod genetyczny pełnią szczególną rolę w determinowaniu rozwoju organizmu. Chociaż stanowisko genocentryczne jest jednym z fundamentów współczesnej teorii ewolucji, to przez długi czas nie podejmowano na tym gruncie (...) problematyki biologii rozwoju. W związku z tym w ostatnich latach można dostrzec zwrot w stronę nurtu alternatywnego, wykazującego istotność uwzględnienia czynników poza-genetycznych w wyjaśnianiu zjawisk i procesów biologiczno-rozwojowych. Najistotniejsze w tym kontekście są argumenty i idee stojące za odrzuceniem specjalnej roli genów, zwłaszcza na gruncie ewolucyjnej biologii rozwoju; kontekst evo-devo wydaje się interesujący ze względu na ambicję integracji biologii rozwojowej i biologii ewolucyjnej. (shrink)

Artykuł jest dygresyjnym przeglądem kilku internetowych witryn muzeów, wybranych i uporządkowanych tematycznie według klucza naukowych zainteresowań autora, zwłaszcza w kontekście sposobu udostępniania online zgromadzonych zbiorów. Instytucje muzealne proponują rozmaite metody i zakresy prezentacji: od najprostszego zamieszczenia fotografii kilkudziesięciu najbardziej spektakularnych zabytków (tzw. _highlights of the collection_) po profesjonalne bazy danych obejmujące całość zasobów wraz z obiektami magazynowymi, wspomagane zaawansowanymi narzędziami przeszukiwania i w pełni naukową deskrypcją. Bez wątpienia w obliczu tego faktu poszczególne muzea różnie definiują profil adresatów swoich kolekcji prezentowanych (...) online. (shrink)

Wychodząc od metaforycznego (figuralnego) ujęcia problemu zła, w oparciu o wybrane przemyślenia Leszka Kołakowskiego, rozważania składające się na artykuł zmierzają do namysłu nad „złem w polityce” w sensie niedomagań i nadużyć wolności: pokus władzy autokratycznej i totalitarnej. Dotyczą antropologicznego i politycznego przekraczania granic wolności kosztem (aż do zniesienia) wolności innych. Evil Politics or Trouble with the Devil. Reflections on the Political Demonology of Leszek Kołakowski Proceeding from a metaphorical (figurative) account of the problem of evil, and based on (...) class='Hi'>Leszek Kołakowski’s selected thoughts, this paper’s considerations aim to deliberate on “evil in politics” in the spirit of the shortcomings and excesses of freedom: namely, the lure of autocratic and totalitarian power. At issue is how the bounds of freedom are anthropologically and politically transgressed at the expense (to the point of abolishing) the freedom of others. (shrink)

The aim of this paper is to show the main thesis concerning the theory of cognition of the eminent neo-Kantian Heinrich Rickert, as presented in his work “Der Gegenstand der Erkenntnis”. On the one hand, Rickert finds out that thinking is fated to “clash with nothingness”, thus creating a temptation to reject all rigours and to yield to complete discretion. On the other hand, he attributes axiological status to nothingness which subjects thinking to a particular kind of “ought”. In his (...) view, the cognizing subject is faced with an axiological choice: either discretion or truth and argues that it is worth opting for truth. His argumentation could be an interesting point of reference for contemporary culture gradually moving away from the type of thinking rooted in objectively existing principles. (shrink)