Independence results for weak systems of intuitionistic arithmetic

This paper proves some independence results for weak fragments of Heyting arithmetic by using Kripke models. We present a necessary condition for linear Kripke models of arithmetical theories which are closed under the negative translation and use it to show that the union of the worlds in any linear Kripke model of HA satisfies PA. We construct a two‐node PA‐normal Kripke structure which does not force iΣ₂. We prove i?₁ ? i?₁, i?₁ ? i?₁, iΠ₂ ? iΣ₂ and iΣ₂ ? iΠ₂. We use Smorynski's operation Σ′ to show HA ? lΠ₁.     

Envelopes,indicators and conservativeness

A well known theorem proved (independently) by J. Paris and H. Friedman states that B Σ_{n +1} (the fragment of Arithmetic given by the collection scheme restricted to Σ_{n +1}‐formulas) is a Π_{n +2}‐conservative extension of I Σ_n (the fragment given by the induction scheme restricted to Σ_n ‐formulas). In this paper, as a continuation of our previous work on collection schemes for Δ_{n +1}(T )‐formulas (see [4]), we study a general version of this theorem and characterize theories T such that T + B Σ_{n +1} is a Π_{n +2}‐conservative extension of T . We prove that this conservativeness property is equivalent to a model‐theoretic property relating Π_n ‐envelopes and Π_n ‐indicators for T . The analysis of Σ_{n +1}‐collection we develop here is also applied to Σ_{n +1}‐induction using Parsons' conservativeness theorem instead of Friedman‐Paris' theorem. As a corollary, our work provides new model‐theoretic proofs of two theorems of R. Kaye, J. Paris and C. Dimitracopoulos (see [8]): B Σ_{n +1} and I Σ_{n +1} are Σ_{n +3}‐conservative extensions of their parameter free versions, B Σ^–_{n +1} and I Σ^–_{n +1}. (© 2006 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)     

On the structure of kripke models of heyting arithmetic

Since in Heyting Arithmetic (HA) all atomic formulas are decidable, a Kripke model for HA may be regarded classically as a collection of classical structures for the language of arithmetic, partially ordered by the submodel relation. The obvious question is then: are these classical structures models of Peano Arithmetic (PA)? And dually: if a collection of models of PA, partially ordered by the submodel relation, is regarded as a Kripke model, is it a model of HA? Some partial answers to these questions were obtained in [6], [3], [1] and [2]. Here we present some results in the same direction, announced in [7]. In particular, it is proved that the classical structures at the nodes of a Kripke model of HA must be models of IΔ₁ (PA^- with induction for provably Δ₁ formulas) and that the relation between these classical structures must be that of a Δ₁-elementary submodel. MSC: 03F30, 03F55.     

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     

Preservation theorems for Kripke models

There are several ways for defining the notion submodel for Kripke models of intuitionistic first‐order logic. In our approach a Kripke model A is a submodel of a Kripke model B if they have the same frame and for each two corresponding worlds A^α and B^α of them, A^α is a subset of B^α and forcing of atomic formulas with parameters in the smaller one, in A and B, are the same. In this case, B is called an extension of A. We characterize theories that are preserved under taking submodels and also those that are preserved under taking extensions as universal and existential theories, respectively. We also study the notion elementary submodel defined in the same style and give some results concerning this notion. In particular, we prove that the relation between each two corresponding worlds of finite Kripke models A ≤ B is elementary extension (in the classical sense) (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

The spanning subgraphs of eulerian graphs

It is shown that a connected graph G spans an eulerian graph if and only if G is not spanned by an odd complete bigraph K(2_m + 1, 2n + 1). A disconnected graph spans an eulerian graph if and only if it is not the union of the trivial graph with a complete graph of odd order. Exact formulas are obtained for the number of lines which must be added to such graphs in order to get eulerian graphs.     

Transfer theorems and asymptotic distributional results for m‐ary search trees

We derive asymptotics of moments and identify limiting distributions, under the random permutation model on m‐ary search trees, for functionals that satisfy recurrence relations of a simple additive form. Many important functionals including the space requirement, internal path length, and the so‐called shape functional fall under this framework. The approach is based on establishing transfer theorems that link the order of growth of the input into a particular (deterministic) recurrence to the order of growth of the output. The transfer theorems are used in conjunction with the method of moments to establish limit laws. It is shown that: (i) for small toll sequences (t_n) [roughly, t_n = O(n^1/2)] we have asymptotic normality if m ≤ 26 and typically periodic behavior if m ≥ 27; (ii) for moderate toll sequences [roughly, t_n = ω(n^1/2) but t_n = o(n)] we have convergence to nonnormal distributions if m ≤ m₀ (where m₀ ≥ 26) and typically periodic behavior if m ≥ m₀ + 1; and (iii) for large toll sequences [roughly, t_n = ω(n)] we have convergence to nonnormal distributions for all values of m. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

Sampling distribution of Gini's index of diversity

In the case of a multinomial distribution Π₁(1-Π₁)+Π₂(1-Π₂)+…+ Π_k(1-Π_k) is at times referred to as Gini's index of diversity. In this paper, we present the distributional properties of the statistic

, based on samples of size n for a homogeneous multinomial distribution. For 2≤n≤ 12 and 2≤k≤12, we give a short table of the pdf, cdf, and the moments of D. For large values of n, we mention some results for the asymptotic distribution of D for the general multinomial distribution.     

On Countable Products of Finite Hausdorff Spaces

We investigate in ZF (i.e., Zermelo‐Fraenke set theory without the axiom of choice) conditions that are necessary and sufficient for countable products ∏_m∈ℕX_m of (a) finite Hausdorff spaces X_m resp. (b) Hausdorff spaces X_m with at most n points to be compact resp. Baire. Typica results: (i) Countable products of finite Hausdorff spaces are compact (resp. Baire) if and only if countable products of non‐empty finite sets are non‐empty. (ii) Countable products of discrete spaces with at most n + 1 points are compact (resp. Baire) if and only if countable products of non‐empty sets with at most n points are non‐empty.     

Submodels of Kripke models

A Kripke model ? is a submodel of another Kripke model ℳ if ? is obtained by restricting the set of nodes of ℳ. In this paper we show that the class of formulas of Intuitionistic Predicate Logic that is preserved under taking submodels of Kripke models is precisely the class of semipositive formulas. This result is an analogue of the Łoś-Tarski theorem for the Classical Predicate Calculus. In Appendix A we prove that for theories with decidable identity we can take as the embeddings between domains in Kripke models of the theory, the identical embeddings. This is a well known fact, but we know of no correct proof in the literature. In Appendix B we answer, negatively, a question posed by Sam Buss: whether there is a classical theory T, such that ℋT is HA. Here ℋT is the theory of all Kripke models ℳ such that the structures assigned to the nodes of ℳ all satisfy T in the sense of classical model theory. Received: 4 February 1999 / Published online: 25 January 2001     

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)     

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.     

The logical consequence relation of propositional tense logic

This work concerns the model theory of propositional tense logic with the Kripke relational semantics. It is shown (i) that there is a formula y whose logical consequences form a complete II set, and (ii) that for 0 ≦ m < ω+ ω there are formulas γ_m such that all models of γ_m are isomorphic and have cardinality x_m, where x₀ = χ₀, x_m+1 = 2^xm, and x_ω = lim{x_m < | m ω}. Familiarity with the relational semantics for modal and tense logic ([1] or [3], for example) will be presumed. A knowledge of recursion theory would be helpful, although some background material will be provided.     

Low sets without subsets of higher many‐one degree

Given a reducibility ?_r, we say that an infinite set A is r‐introimmune if A is not r‐reducible to any of its subsets B with |A\B| = ∞. We consider the many‐one reducibility ?_m and we prove the existence of a low₁ m‐introimmune set in Π⁰₁ and the existence of a low₁ bi‐m‐introimmune set.     

Some descriptive set theory and core models

We analyse the trees given by sharps for Π¹₂ sets via inner core models to give a canonical decomposition of such sets when a core model is Σ¹₃ absolute. This is by way of analogy with Solovay's analysis of Π¹₁ sets into ω₁ Borel sets — Borel in codes for wellorders. We find that Π¹₂ sets are also unions of ω₁ Borel sets — but in codes for mice and wellorders. We give an application of this technique in showing that if a core model, K, is Σ¹₃ absolute thenTheorem. Every real is in K iff every Π¹₃ set of reals contains a Π¹₃ singleton.     

A graph theoretic upper bound on the permanent of a nonnegative integer matrix. II. The extremal case

Matrices A for which the upper bound per(A)?1+min{Π(c_i?1), Π(r_i?1)} holds with equality are characterized. Cases where the bound is achieved correspond to multigraphs with the property that there exists a unique path from any vertex to any disjoint cycle union. This occurs precisely when some multigraph associated with A has the mastercycle property: all cycles thread all branchpoints in the same circular order. Such multigraphs may also be characterized as a circular concatenation of certain acyclic multigraphs, each having a unique source and sink. This analysis yields two normal forms for the extremal matrices, one based on a nested block decomposition, and another based on an overlapping block decomposition. The extremal cases are invariant under contractions, yielding another characterization.     

Homology of Centralizers

Given a group Π, we study the group homology of centralizers Π _g , g ? Π, and of their central quotients Π _g /〈 g〉. This study is motivated by the structure of the Hochschild and the cyclic homology of group algebras, and is based on Quillen's approach to the cyclic homology of algebras via algebra extensions. A method of computing the de Rham complex of a group algebra by means of a Gruenberg resolution is also developed.     

Lollipop graphs are extremal for commute times

Consider a simple random walk on a connected graph G=(V, E). Let C(u, v) be the expected time taken for the walk starting at vertex u to reach vertex v and then go back to u again, i.e., the commute time for u and v, and let C(G)=max_{u, v∈V}C(u, v). Further, let 𝒢(n, m) be the family of connected graphs on n vertices with m edges, , and let 𝒢(n)=∪_m𝒢(n, m) be the family of all connected n‐vertex graphs. It is proved that if G∈(n, m) is such that C(G)=max_{H∈𝒢(n, m)}C(H) then G is either a lollipop graph or a so‐called double‐handled lollipop graph. It is further shown, using this result, that if C(G)=max_H∈𝒢(n)C(H) then G is the full lollipop graph or a full double‐handled lollipop graph with [(2n−1)/3] vertices in the clique unless n≤9 in which case G is the n‐path. ©2000 John Wiley & Sons, Inc. Random Struct. Alg., 16, 131–142, 2000