A note on parameter free Π1‐induction and restricted exponentiation

We characterize the sets of all Π₂ and all $\mathcal {B}(\Sigma _{1})We characterize the sets of all Π₂ and all $\mathcal {B}(\Sigma _{1})$ (= Boolean combinations of Σ₁) theorems of IΠ^?₁ in terms of restricted exponentiation, and use these characterizations to prove that both sets are not deductively equivalent. We also discuss how these results generalize to n > 0. As an application, we prove that a conservation theorem of Beklemishev stating that IΠ^?_{n + 1} is conservative over IΣ^?_n with respect to $\mathcal {B}(\Sigma _{n+1})$ sentences cannot be extended to Π_{n + 2} sentences. © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim     

Fragments of Arithmetic and true sentences

By a theorem of R. Kaye, J. Paris and C. Dimitracopoulos, the class of the Π_n+1‐sentences true in the standard model is the only (up to deductive equivalence) consistent Π_n+1‐theory which extends the scheme of induction for parameter free Π_n+1‐formulas. Motivated by this result, we present a systematic study of extensions of bounded quantifier complexity of fragments of first‐order Peano Arithmetic. Here, we improve that result and show that this property describes a general phenomenon valid for parameter free schemes. As a consequence, we obtain results on the quantifier complexity, (non)finite axiomatizability and relative strength of schemes for Δ_n+1‐formulas. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Weak Arithmetics and Kripke Models

In the first section of this paper we show that i Π₁ ≡ W⌝⌝lΠ₁ and that a Kripke model which decides bounded formulas forces iΠ₁ if and only if the union of the worlds in any (complete) path in it satisflies IΠ₁. In particular, the union of the worlds in any path of a Kripke model of HA models IΠ₁. In the second section of the paper, we show that for equivalence of forcing and satisfaction of Π_m‐formulas in a linear Kripke model deciding Δ₀‐formulas it is necessary and sufficient that the model be Σ_m‐elementary. This implies that if a linear Kripke model forces PEM_prenex, then it forces PEM. We also show that, for each n ≥ 1, iΦ_n does not prove ℋ︁(IΠ_n's are Burr's fragments of HA.     

A note on the Σ1 collection scheme and fragments of bounded arithmetic

We show that for each n ≥ 1, if T₂ⁿ does not prove the weak pigeonhole principle for Σ^b_n functions, then the collection scheme B Σ₁ is not finitely axiomatizable over T₂ⁿ. The same result holds with Sⁿ₂ in place of T 2ⁿ (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On the Π11‐separation principle

We study the proof‐theoretic strength of the Π₁¹‐separation axiom scheme, and we show that Π₁¹‐separation lies strictly in between the Δ₁¹‐comprehension and Σ₁¹‐choice axiom schemes over RCA₀. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Some More Conservation Results on the Baire Category Theorem

In this paper, we generalize a result of Brown and Simpson [1] to prove that RCA₀+Π⁰_∞‐BCT is conservative over RCA₀ with respect to the set of formulae in the form ∃!Xφ(X), where φ is arithmetical. We also consider the conservation of Π⁰_0∞‐BCT over Σ^b₁‐NIA+∇^b₁‐CA.     

Herbrandizing search problems in Bounded Arithmetic

We study search problems and reducibilities between them with known or potential relevance to bounded arithmetic theories. Our primary objective is to understand the sets of low complexity consequences (esp. Σ^b₁ or Σ^b₂) of theories Sⁱ₂ and Tⁱ₂ for a small i, ideally in a rather strong sense of characterization; or, at least, in the standard sense of axiomatization. We also strive for maximum combinatorial simplicity of the characterizations and axiomatizations, eventually sufficient to prove conjectured separation results. To this end two techniques based on the Herbrand's theorem are developed. They characterize/axiomatize Σ^b₁‐consequences of Σ^b₂‐definable search problems, while the method based on the more involved concept of characterization is easier and gives more transparent results. This method yields new proofs of Buss' witnessing theorem and of the relation between PLS and Σ^b₁(T¹₂), and also an axiomatization of Σ^b₁(T²₂). (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Determinacy of Wadge classes and subsystems of second order arithmetic

In this paper we study the logical strength of the determinacy of infinite binary games in terms of second order arithmetic. We define new determinacy schemata inspired by the Wadge classes of Polish spaces and show the following equivalences over the system RCA₀*, which consists of the axioms of discrete ordered semi‐rings with exponentiation, Δ₁⁰ comprehension and Π₀⁰ induction, and which is known as a weaker system than the popularbase theory RCA₀: 1. Bisep(Δ₁⁰, Σ₁⁰)‐Det* ? WKL₀, (1) 2. Bisep(Δ₁⁰, Σ₂⁰)‐Det* ? ATR₀ + Σ₁¹ induction, (2) 3. Bisep(Σ₁⁰, Σ₂⁰)‐Det* ? Sep(Σ₁⁰, Σ₂⁰)‐Det* ? Π₁¹‐CA₀, (3) 4. Bisep(Δ₂⁰, Σ₂⁰)‐Det* ? Π₁¹‐TR₀, (4) where Det* stands for the determinacy of infinite games in the Cantor space (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Simulating non‐prenex cuts in quantified propositional calculus

We show that the quantified propositional proof systems G_i are polynomially equivalent to their restricted versions that require all cut formulas to be prenex Σ^q_i (or prenex Π^q_i). Previously this was known only for the treelike systems G*_i. © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim     

The Arithmetical Hierarchy of Real Numbers

A real number x is computable iff it is the limit of an effectively converging computable sequence of rational numbers, and x is left (right) computable iff it is the supremum (infimum) of a computable sequence of rational numbers. By applying the operations “sup” and “inf” alternately n times to computable (multiple) sequences of rational numbers we introduce a non‐collapsing hierarchy {Σ_n, Π_n, Δ_n : n ∈ ℕ} of real numbers. We characterize the classes Σ₂, Π₂ and Δ₂ in various ways and give several interesting examples.     

An unexpected separation result in Linearly Bounded Arithmetic

The theories Sⁱ₁(α) and Tⁱ₁(α) are the analogues of Buss' relativized bounded arithmetic theories in the language where every term is bounded by a polynomial, and thus all definable functions grow linearly in length. For every i, a Σ^b_i+1(α)‐formula TOPⁱ(a), which expresses a form of the total ordering principle, is exhibited that is provable in Sⁱ⁺¹₁ (α), but unprovable in Tⁱ₁(α). This is in contrast with the classical situation, where Sⁱ⁺¹₂ is conservative over Tⁱ₂ w. r. t. Σ^b_i+1‐sentences. The independence results are proved by translations into propositional logic, and using lower bounds for corresponding propositional proof systems. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Products of operator ideals and extensions of Schatten classes

We study relations between Schatten classes and product operator ideals, where one of the factors is the Banach ideal Π_E,2 of (E, 2)‐summing operators, and where E is a Banach sequence space with ?₂ ? E. We show that for a large class of 2‐convex symmetric Banach sequence spaces the product ideal Π_E,2 ○ ??^a_q,s is an extension of the Schatten class ??_F with a suitable Lorentz space F. As an application, we obtain that if 2 ≤ p, q < ∞, 1/r = 1/p + 1/q and E is a 2‐convex symmetric space with fundamental function λ_E(n) ≈? n^1/p, then Π_E,2 ○ Π_q is an extension of the Schatten class ??r,q (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On the index sets of Σ-subsets of the real numbers

We compute the levels of complexity in analytical and arithmetical hierarchies for the sets of the Σ-formulas defining in the hereditarily finite superstructure over the ordered field of the reals the classes of open, closed, clopen, nowhere dense, dense subsets of ? ⁿ , first category subsets in ? ⁿ as well as the sets of pairs of Σ-formulas corresponding to the relations of set equality and inclusion which are defined by them. It is also shown that the complexity of the set of the Σ-formulas defining connected sets is at least Π ₁ ¹ .     

Sequences in the range of a vector measure and Banach spaces satisfying Π1(X,l 1) = Π2(X,l 1)

If X is a Banach space such that Π₁(X,l ₁) = Π₂ (X, l ₁), we prove the following results: 1) A bounded sequence (x _n ) lies inside the range of some X-valued measure if and only if the operator (α _n ) ? l ₁ → Σ _n α _n x _n ? X is 1-summing, and 2) If A is a bounded subset of X lying in the range of some X ^??-valued measure, then A is necessarily contained in the range of some X-valued measure.     

Note on the heights of random recursive trees and random m-ary search trees

A process of growing a random recursive tree T_n is studied. The sequence {T_n} is shown to be a sequence of “snapshots” of a Crump–Mode branching process. This connection and a theorem by Kingman are used to show quickly that the height of T_n is asymptotic, with probability one, to c log n. In particular, c = e = 2.718 … for the uniform recursive tree, and c = (2γ)^?1, where γe^1+γ = 1, for the ordered recursive tree. An analogous reduction provides a short proof of Devroye's limit law for the height of a random m-ary search tree. We show finally a close connection between another Devroye's result, on the height of a random union-find tree, and our theorem on the height of the uniform recursive tree. © 1994 John Wiley & Sons, Inc.     

Almost sure central limit theorems for random functions

Let {Xn,-∞< n <∞} be a sequence of independent identically distributed random variables with EX1 = 0, EX12 = 1 and let Sn =∑k=1∞Xk, and Tn = Tn(X1,…,Xn) be a random function such that Tn = ASn Rn, where supn E|Rn| <∞and Rn = o(n~(1/2)) a.s., or Rn = O(n1/2-2γ) a.s., 0 <γ< 1/8. In this paper, we prove the almost sure central limit theorem (ASCLT) and the function-typed almost sure central limit theorem (FASCLT) for the random function Tn. As a consequence, it can be shown that ASCLT and FASCLT also hold for U-statistics, Von-Mises statistics, linear processes, moving average processes, error variance estimates in linear models, power sums, product-limit estimators of a continuous distribution, product-limit estimators of a quantile function, etc.     

The structure of compact disjointness preserving operators on continuous functions

Let T be a compact disjointness preserving linear operator from C₀(X) into C₀(Y), where X and Y are locally compact Hausdorff spaces. We show that T can be represented as a norm convergent countable sum of disjoint rank one operators. More precisely, T = Σ_n δ ?h_n for a (possibly finite) sequence {x_n }_n of distinct points in X and a norm null sequence {h_n }_n of mutually disjoint functions in C₀(Y). Moreover, we develop a graph theoretic method to describe the spectrum of such an operator (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Nearly Model Complete Theories

A theory T of a language L is 1-model complete (nearly model complete) iff for every formula ρ of L there is a formula ? (χ) of L which is a ??-formula (a Boolean combination of universal formulas) such that T ? ?x [??θ]. The main results of the paper give characterizations of nearly model complete theories and of 1-model complete theories. As a consequence we obtain that a theory T is nearly model complete iff whenever ?? is a model of T and ???₁??, then T ∪ Δ¹_?? is a complete L(A)-theory, where Δ¹_?? is the 1-diagram of ??. We also point out that our main results extend to (n + l)-model complete and nearly ra-model complete theories for all n > 0.     

Topological realizations of families of ergodic automorphisms, multitowers and orbit equivalence

We study minimal topological realizations of families of ergodic measure preserving automorphisms (e.m.p.a.'s). Our main result is the following theorem. Theorem: Let {T_p:p∈I} be an arbitrary finite or countable collection of e.m.p.a.'s on nonatomic Lebesgue probability spaces (Y _p v _p ). Let S be a Cantor minimal system such that the cardinality of the set ε _S of all ergodic S-invariant Borel probability measures is at least the cardinality of I. Then for any collection {μ _p :pεI} of distinct measures from ε _S there is a Cantor minimal system S′ in the topological orbit equivalence class of S such that, as a measure preserving system, (S ¹,μ _p ) is isomorphic to T_p for every p∈I. Moreover, S′ can be chosen strongly orbit equivalent to S if and only if all finite topological factors of S are measure-theoretic factors of T_p for all p∈I. This result shows, in particular, that there are no restrictions at all for the topological realizations of countable families of e.m.p.a.'s in Cantor minimal systems. Namely, for any finite or countable collection {T ₁,T₂,…} of e.m.p.a.'s of nonatomic Lebesgue probability spaces, there is a Cantor minimal systemS, whose collection {μ1,μ2…} of ergodic Borel probability measures is in one-to-one correspondence with {T ₁,T₂,…}, and such that (S,μ _i ) is isomorphic toT _i for alli. Furthermore, since realizations are taking place within orbit equivalence classes of a given Cantor minimal system, our results generalize the strong orbit realization theorem and the orbit realization theorem of [18]. Those theorems are now special cases of our result where the collections {T _p}, {T _p }{μ _p } consist of just one element each. Research of I.K. was supported by NSF grant DMS 0140068.