Natural deduction with general elimination rules

The structure of derivations in natural deduction is analyzed through isomorphism with a suitable sequent calculus, with twelve hidden convertibilities revealed in usual natural deduction. A general formulation of conjunction and implication elimination rules is given, analogous to disjunction elimination. Normalization through permutative conversions now applies in all cases. Derivations in normal form have all major premisses of elimination rules as assumptions. Conversion in any order terminates. Through the condition that in a cut-free derivation of the sequent Γ⇒C, no inactive weakening or contraction formulas remain in Γ, a correspondence with the formal derivability relation of natural deduction is obtained: All formulas of Γ become open assumptions in natural deduction, through an inductively defined translation. Weakenings are interpreted as vacuous discharges, and contractions as multiple discharges. In the other direction, non-normal derivations translate into derivations with cuts having the cut formula principal either in both premisses or in the right premiss only. Received: 1 December 1998 / Revised version: 30 June 2000 / Published online: 18 July 2001     

Explaining the Gentzen–Takeuti reduction steps: a second-order system

Using the concept of notations for infinitary derivations we give an explanation of Takeuti's reduction steps on finite derivations (used in his consistency proof for Π¹ ₁-CA) in terms of the more perspicious infinitary approach from [BS88]. Received: 27 April 1999 / Published online: 21 March 2001     

Note on generalizing theorems in algebraically closed fields

The generalization properties of algebraically closed fields of characteristic and of characteristic 0 are investigated in the sequent calculus with blocks of quantifiers. It is shown that admits finite term bases, and admits term bases with primality constraints. From these results the analogs of Kreisel's Conjecture for these theories follow: If for some , ( 1's) is provable in steps, then is provable. Received: February 1, 1996     

A Discontinuous Colombeau Differential Calculus

Starting from the Colombeau Generalized Functions, the sharp topologies and the notion of generalized points, we introduce a new kind of differential calculus (for functions between totally disconnected spaces). We also define here the notions of holomorphic generalized functions (in this new framework) and generalized manifold. Finally we give an answer to a question raised in [6].Research partially supported by CNPq (Proc 300652/95-0).     

The high temperature case for the random K-sat problem

We give a completely rigorous proof that the replica-symmetric solution holds at high enough temperature for the random K-sat problem. The most notable feature of this problem is that the order parameter of the system is a function and not a number. Received: 21 April 1998 / Revised version: 24 April 2000 / Published online: 21 December 2000     

Vector fields on smooth threefolds vanishing on complete intersections

A result of J. Wahl shows that the existence of a vector field vanishing on an ample divisor of a projective normal variety X implies that X is a cone over this divisor. If X is smooth, X will be isomorphic to the n-dimensional projective space. This paper is a first attempt to generalize Wahl's theorem to higher codimensions: Given a complex smooth projective threefold X and a vector field on X vanishing on an irreducible and reduced curve which is the scheme theoretic intersection of two ample divisors, X is isomorphic to the 3-dimensional projective space or the 3-dimensional quadric. Received: 24 April 2001     

The Karp complexity of unstable classes

A class K of structures is controlled if, for all cardinals λ, the relation of L _∞,λ-equivalence partitions K into a set of equivalence classes (as opposed to a proper class). We prove that the class of doubly transitive linear orders is controlled, while any pseudo-elementary class with the ω-independence property is not controlled. Received: 23 September 1998 / Revised version: 6 July 1999 / Published online: 21 December 2000     

Leibniz filters and the strong version of a protoalgebraic logic

A filter of a sentential logic ? is Leibniz when it is the smallest one among all the ?-filters on the same algebra having the same Leibniz congruence. This paper studies these filters and the sentential logic ?⁺ defined by the class of all ?-matrices whose filter is Leibniz, which is called the strong version of ?, in the context of protoalgebraic logics with theorems. Topics studied include an enhanced Correspondence Theorem, characterizations of the weak algebraizability of ?⁺ and of the explicit definability of Leibniz filters, and several theorems of transfer of metalogical properties from ? to ?⁺. For finitely equivalential logics stronger results are obtained. Besides the general theory, the paper examines the examples of modal logics, quantum logics and Łukasiewicz's finitely-valued logics. One finds that in some cases the existence of a weak and a strong version of a logic corresponds to well-known situations in the literature, such as the local and the global consequences for normal modal logics; while in others these constructions give an independent interest to the study of other lesser-known logics, such as the lattice-based many-valued logics. Received: 30 October 1998 /?Published online: 15 June 2001     

A non-uniform Berry–Esseen bound via Stein's method

This paper is part of our efforts to develop Stein's method beyond uniform bounds in normal approximation. Our main result is a proof for a non-uniform Berry–Esseen bound for independent and not necessarily identically distributed random variables without assuming the existence of third moments. It is proved by combining truncation with Stein's method and by taking the concentration inequality approach, improved and adapted for non-uniform bounds. To illustrate the technique, we give a proof for a uniform Berry–Esseen bound without assuming the existence of third moments. Received: 2 March 2000 / Revised version: 20 July 2000 / Published online: 26 April 2001     

On the definability of verbal subgroups

We show that if G is a group of finite Morley rank, then the verbal subgroup <w(G)> is of finite width, where w is a concise word. As a byproduct, we show that if G is any abelian-by-finite group, then G ⁿ =<x ⁿ (G)> is definable. Received: 15 March 1996 / Published online: 18 July 2001     

Near coherence and filter games

We investigate a two-player game involving pairs of filters on ω. Our results generalize a result of Shelah ([7] Chapter VI) dealing with applications of game theory in the study of ultrafilters. Received: 28 September 1998 / Published online: 25 January 2001     

An elementary proof of strong normalization for intersection types

We provide a new and elementary proof of strong normalization for the lambda calculus of intersection types. It uses no strong method, like for instance Tait-Girard reducibility predicates, but just simple induction on type complexity and derivation length and thus it is obviously formalizable within first order arithmetic. To obtain this result, we introduce a new system for intersection types whose rules are directly inspired by the reduction relation. Finally, we show that not only the set of strongly normalizing terms of pure lambda calculus can be characterized in this system, but also that a straightforward modification of its rules allows to characterize the set of weakly normalizing terms. Received: 15 June 1998 / Revised version: 15 November 1999 / Published online: 15 June 2001     

Density results in the Δ20 e-degrees

We show that the Δ⁰ ₂ enumeration degrees are dense. We also show that for every nonzero n-c. e. e-degree a, with n≥ 3, one can always find a nonzero 3-c. e. e-degree b such that b < a on the other hand there is a nonzero ωc. e. e-degree which bounds no nonzero n-c. e. e-degree. Received: 13 June 2000 / Published online: 3 October 2001     

Groupwise dense families

We show that the Filter Dichotomy Principle implies that there are exactly four classes of ideals in the set of increasing functions from the natural numbers. We thus answer two open questions on consequences of ? < ?. We show that ? < ? implies that ? = ?, and that Filter Dichotomy together with ? < ? implies ? < ?. The technical means is the investigation of groupwise dense sets, ideals, filters and ultrafilters. With related techniques we prove the new inequality ?≤ cf(?). Received: 9 October 1998 / Revised version: 18 August 1999 / Published online: 21 December 2000     

On the filter of computably enumerable supersets of an r-maximal set

We study the filter ℒ^*(A) of computably enumerable supersets (modulo finite sets) of an r-maximal set A and show that, for some such set A, the property of being cofinite in ℒ^*(A) is still Σ⁰ ₃-complete. This implies that for this A, there is no uniformly computably enumerable “tower” of sets exhausting exactly the coinfinite sets in ℒ^*(A). Received: 6 November 1999 / Revised version: 10 March 2000 /?Published online: 18 May 2001     

The G-homotopy type of proper locally linear G-manifolds. II

In this paper we study proper locally linear actions of Lie groups on topological manifolds and prove that such G-spaces have the G-homotopy type of a G-CW complex. Results on G-invariant metrics and equivariant embeddings into Banach G-spaces are also obtained. Received: 19 June 2000     

Generalization of a problem of Lehmer

Given a prime number p, Lehmer raised the problem of investigating the number of integers for which a and are of opposite parity, where is such that . We replace the pair by a point lying on a more general irreducible curve defined mod p and instead of the parity conditions on the coordinates more general congruence conditions are considered. An asymptotic result is then obtained for the number of such points. Received: 12 July 2000 / Revised version: 7 November 2000     

Sur la torsion de la distribution ordinaire universelle attachée à un corps de nombres

We study the torsion subgroup of the universal ordinary distribution related to a general number field. We describe a way to control this subgroup. We apply this method to the special case of an imaginary quadratic field, and we give examples of such fields where these torsion subgroups are non-trivial. Received: 4 January 2001 / Revised version: 17 May 2001     

Deux théorèmes de non-annulation de valeurs spéciales de fonctions L

In answer to questions recently raised by Merel [Mer], we prove two non-vanishing theorems for the central value of automorphic L-functions: let p be prime and let χ be a primitive character modulo p. Then for all p large enough 1. If χ is not quadratic and even, there exists a primitive weight 2 form f of level p with . 2. If χ is quadratic and even, then there exists a primitive weight 2 form f of level p with . Received: 12 March 2000 / Revised version: 26 September 2000     

The shrinking principle and the axiom of choice

The axiom of choice is equivalent to the shrinking principle: every indexed cover of a set has a refinement with the same index set which is a partition. A simple and direct proof of this equivalence is given within an elementary fragment of constructive Zermelo–Fraenkel set theory. Variants of the shrinking principle are discussed, and it is related to a similar but different principle formulated by Vaught.