12 found
Order:
  1.  5
    Categorical Characterizations of the Natural Numbers Require Primitive Recursion.Leszek Aleksander Kołodziejczyk & Keita Yokoyama - 2015 - Annals of Pure and Applied Logic 166 (2):219-231.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  2.  33
    The Strength of Sharply Bounded Induction Requires M S P.Sedki Boughattas & Leszek Aleksander Kołodziejczyk - 2010 - Annals of Pure and Applied Logic 161 (4):504-510.
    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.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  3.  8
    Fragments of Approximate Counting.Samuel R. Buss, Leszek Aleksander Kołodziejczyk & Neil Thapen - 2014 - Journal of Symbolic Logic 79 (2):496-525.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  4.  7
    The Provably Total NP Search Problems of Weak Second Order Bounded Arithmetic.Leszek Aleksander Kołodziejczyk, Phuong Nguyen & Neil Thapen - 2011 - Annals of Pure and Applied Logic 162 (6):419-446.
    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 (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  5.  4
    The Polynomial and Linear Hierarchies in Models Where the Weak Pigeonhole Principle Fails.Leszek Aleksander Kołodziejczyk & Neil Thapen - 2008 - Journal of Symbolic Logic 73 (2):578-592.
    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 (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  6. Truth Definitions in Finite Models.Leszek Aleksander Kołodziejczyk - 2004 - Journal of Symbolic Logic 69 (1):183-200.
    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 (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark  
  7.  10
    Real Closures of Models of Weak Arithmetic.Emil Jeřábek & Leszek Aleksander Kołodziejczyk - 2013 - Archive for Mathematical Logic 52 (1-2):143-157.
    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, (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  8.  21
    Truth Definitions Without Exponentiation and the Σ₁ Collection Scheme.Zofia Adamowicz, Leszek Aleksander Kołodziejczyk & Jeff Paris - 2012 - Journal of Symbolic Logic 77 (2):649-655.
    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 (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  9.  10
    On the Herbrand Notion of Consistency for Finitely Axiomatizable Fragments of Bounded Arithmetic Theories.Leszek Aleksander Kołodziejczyk - 2006 - Journal of Symbolic Logic 71 (2):624 - 638.
    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}$.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  10.  9
    Independence Results for Variants of Sharply Bounded Induction.Leszek Aleksander Kołodziejczyk - 2011 - Annals of Pure and Applied Logic 162 (12):981-990.
    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 (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  11.  13
    Partial Collapses of the Complexity Hierarchy in Models for Fragments of Bounded Arithmetic.Zofia Adamowicz & Leszek Aleksander Kołodziejczyk - 2007 - Annals of Pure and Applied Logic 145 (1):91-95.
    For any n, we construct a model of in which each formula is equivalent to an formula.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  12.  13
    A Note on the E1 Collection Scheme and Fragments of Bounded Arithmetic.Zofia Adamowicz & Leszek Aleksander Kołodziejczyk - 2010 - Mathematical Logic Quarterly 56 (2):126-130.
    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.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark