The eskolemization of universal quantifiers

This paper is a sequel to the papers Baaz and Iemhoff (2006, 2009) [4] and [6] in which an alternative skolemization method called eskolemization was introduced that, when restricted to strong existential quantifiers, is sound and complete for constructive theories. In this paper we extend the method to universal quantifiers and show that for theories satisfying the witness property it is sound and complete for all formulas. We obtain a Herbrand theorem from this, and apply the method to the intuitionistic theory of equality and the intuitionistic theory of monadic predicates.     

Independence results in formal topology

We analyze a family of games by using formal topology as a tool. In order to win any game in the family one has to find a sequence of moves leading to one of the final states for that game. Thus, two results are relevant to the topic: to find terminating strategies and/or to show that every strategy is terminating. We will show that the language of formal topology can be useful to represent in a topological framework both of the problems, and in particular that the property of termination of all the strategies for a game is equivalent to the discreteness of a suitable formal space. Finally, we will provide some examples of games which are terminating according to any strategy, that is, such that the associated formal spaces are discrete, but the first order formulas expressing such a discreteness cannot be proved in Peano Arithmetic.     

Completeness and interpolation of almost‐everywhere quantification over finitely additive measures

We give an axiomatization of first‐order logic enriched with the almost‐everywhere quantifier over finitely additive measures. Using an adapted version of the consistency property adequate for dealing with this generalized quantifier, we show that such a logic is both strongly complete and enjoys Craig interpolation, relying on a (countable) model existence theorem. We also discuss possible extensions of these results to the almost‐everywhere quantifier over countably additive measures.     

Modularity results for interpolation,amalgamation and superamalgamation

Wolter in [38] proved that the Craig interpolation property transfers to fusion of normal modal logics. It is well-known [21] that for such logics Craig interpolation corresponds to an algebraic property called superamalgamability. In this paper, we develop model-theoretic techniques at the level of first-order theories in order to obtain general combination results transferring quantifier-free interpolation to unions of theories over non-disjoint signatures. Such results, once applied to equational theories sharing a common Boolean reduct, can be used to prove that superamalgamability is modular also in the non-normal case. We also state that, in this non-normal context, superamalgamability corresponds to a strong form of interpolation that we call “comprehensive interpolation property” (which consequently transfers to fusions).     

The anti-Specker property, a Heine–Borel property, and uniform continuity

Working within Bishop’s constructive framework, we examine the connection between a weak version of the Heine–Borel property, a property antithetical to that in Specker’s theorem in recursive analysis, and the uniform continuity theorem for integer-valued functions. The paper is a contribution to the ongoing programme of constructive reverse mathematics.     

Glivenko theorems revisited

Glivenko-type theorems for substructural logics (over FL) are comprehensively studied in the paper [N. Galatos, H. Ono, Glivenko theorems for substructural logics over FL, Journal of Symbolic Logic 71 (2006) 1353-1384]. Arguments used there are fully algebraic, and based on the fact that all substructural logics are algebraizable (see [N. Galatos, H. Ono, Algebraization, parametrized local deduction theorem and interpolation for substructural logics over FL, Studia Logica 83 (2006) 279-308] and also [N. Galatos, P. Jipsen, T. Kowalski, H. Ono, Residuated Lattices: An Algebraic Glimpse at Substructural Logics, in: Studies in Logic and the Foundations of Mathematics, vol. 151, Elsevier, 2007] for the details).As a complementary work to the algebraic approach developed in [N. Galatos, H. Ono, Glivenko theorems for substructural logics over FL, Journal of Symbolic Logic 71 (2006) 1353-1384], we present here a concise, proof-theoretic approach to Glivenko theorems for substructural logics. This will show different features of these two approaches.     

On the interpolation property of some intuitionistic modal logics

LetL be one of the intuitionistic modal logics considered in [7] (or one of its extensions) and letM _L be the algebraic semantics ofL. In this paper we will extend toL the equivalence, proved in the classical case (see [6]), among he weak Craig interpolation theorem, the Robinson theorem and the amalgamation property of varietyM _L. We will also prove the equivalence between the Craig interpolation theorem and the super-amalgamation property of varietyM _L. Then we obtain the Craig interpolation theorem and Robinson theorem for two intuitionistic modal logics, one ofS ₄-type and the other one ofS ₅-type, showing the super-amalgamation property of the corresponding algebraic semantics.     

Uniform interpolation and the existence of sequent calculi

This paper presents a uniform and modular method to prove uniform interpolation for several intermediate and intuitionistic modal logics. The proof-theoretic method uses sequent calculi that are extensions of the terminating sequent calculus $\mathsf{G4ip}$ for intuitionistic propositional logic. It is shown that whenever the rules in a calculus satisfy certain structural properties, the corresponding logic has uniform interpolation. It follows that the intuitionistic versions of $\mathsf{K}$ and $\mathsf{KD}$ (without the diamond operator) have uniform interpolation. It also follows that no intermediate or intuitionistic modal logic without uniform interpolation has a sequent calculus satisfying those structural properties, thereby establishing that except for the seven intermediate logics that have uniform interpolation, no intermediate logic has such a sequent calculus.     

On constructivity and the Rosser property: a closer look at some Gödelean proofs

The proofs of Kleene, Chaitin and Boolos for Gödel's First Incompleteness Theorem are studied from the perspectives of constructivity and the Rosser property. A proof of the incompleteness theorem has the Rosser property when the independence of the true but unprovable sentence can be shown by assuming only the (simple) consistency of the theory. It is known that Gödel's own proof for his incompleteness theorem does not have the Rosser property, and we show that neither do Kleene's or Boolos' proofs. However, we show that a variant of Chaitin's proof can have the Rosser property. The proofs of Gödel, Rosser and Kleene are constructive in the sense that they explicitly construct, by algorithmic ways, the independent sentence(s) from the theory. We show that the proofs of Chaitin and Boolos are not constructive, and they prove only the mere existence of the independent sentences.     

CZF does not have the existence property

Constructive theories usually have interesting metamathematical properties where explicit witnesses can be extracted from proofs of existential sentences. For relational theories, probably the most natural of these is the existence property, EP, sometimes referred to as the set existence property  . This states that whenever (∃x)?(x)$(\exists x)?(x)$ is provable, there is a formula χ(x)$\chi (x)$ such that (∃!x)?(x)∧χ(x)$(\exists !x)?(x)\wedge \chi (x)$ is provable. It has been known since the 80s that EP holds for some intuitionistic set theories and yet fails for IZF. Despite this, it has remained open until now whether EP holds for the most well known constructive set theory, CZF. In this paper we show that EP fails for CZF.     

Order-enriched categorical models of the classical sequent calculus

It is well-known that weakening and contraction cause naïve categorical models of the classical sequent calculus to collapse to Boolean lattices. Starting from a convenient formulation of the well-known categorical semantics of linear classical sequent proofs, we give models of weakening and contraction that do not collapse. Cut-reduction is interpreted by a partial order between morphisms. Our models make no commitment to any translation of classical logic into intuitionistic logic and distinguish non-deterministic choices of cut-elimination. We show soundness and completeness via initial models built from proof nets, and describe models built from sets and relations.     

Craig interpolation for semilinear substructural logics

The Craig interpolation property is investigated for substructural logics whose algebraic semantics are varieties of semilinear (subdirect products of linearly ordered) pointed commutative residuated lattices. It is shown that Craig interpolation fails for certain classes of these logics with weakening if the corresponding algebras are not idempotent. A complete characterization is then given of axiomatic extensions of the “R‐mingle with unit” logic (corresponding to varieties of Sugihara monoids) that have the Craig interpolation property. This latter characterization is obtained using a model‐theoretic quantifier elimination strategy to determine the varieties of Sugihara monoids admitting the amalgamation property.     

Fonctions généralisées et analyse non standard

We study some connections between Non-Standard Analysis and algebraical theories of generalized functions. More precisely, we point out the fact that the construction of these algebras can be interpreted in terms of Non Standard asymptotic properties. For example, we show that the construction of the J. F. Colombeau'Algebra is equivalent (in a certain sense) to a monadic property. Conversely, we show that a certain galactic property (being exponentially small with respect to a parameter) leads to a new algebra.

     

The Σ1-provability logic of HA

In this paper we introduce a modal theory ${\mathsf{iH}}_{\sigma }$ which is sound and complete for arithmetical ${\mathrm{\Sigma }}_1$-interpretations in $\mathsf{HA}$, in other words, we will show that ${\mathsf{iH}}_{\sigma }$ is the ${\mathrm{\Sigma }}_1$-provability logic of $\mathsf{HA}$. Moreover we will show that ${\mathsf{iH}}_{\sigma }$ is decidable. As a by-product of these results, we show that $\mathsf{HA}+\square \perp$ has de Jongh property.     

Constructibility in higher order arithmetics

Summary We define and investigate constructibility in higher order arithmetics. In particular we get an interpretation ofn-order arithmetic inn-order arithmetic without the scheme of choice such that and the property to be a well-ordering are absolute in it and such that this interpretation is minimal among such interpretations.     

Elimination of Skolem functions for monotone formulas in analysis

In this paper a new method, elimination of Skolem functions for monotone formulas, is developed which makes it possible to determine precisely the arithmetical strength of instances of various non-constructive function existence principles. This is achieved by reducing the use of such instances in a given proof to instances of certain arithmetical principles. Our framework are systems -qf , where (GA is a hierarchy of (weak) subsystems of arithmetic in all finite types (introduced in [14]), AC-qf is the schema of quantifier-free choice in all types and is a set of certain analytical principles which e.g. includes the binary K?nig's lemma. We apply this method to show that the arithmetical closures of single instances of -comprehension and -choice contribute to the growth of extractable bounds from proofs relative to only by a primitive recursive functional in the sense of Kleene. In subsequent papers these results are widely generalized and the method is used to determine the arithmetical content of single sequences of instances of the Bolzano-Weierstra? principle for bounded sequences in , the Ascoli-lemma and others. February 14, 1996     

Archimedeanness and the MacNeille completion of pseudoeffect algebras and po-groups

Pseudoeffect (PE-) algebras are partial algebras differing from effect algebras in that they need not satisfy the commutativity assumption. PE-algebras typically arise from intervals of po-groups; this applies in particular to all those which satisfy a certain Riesz property.In this paper, we discuss the property of archimedeanness for PE-algebras on the one hand and for po-groups on the other hand. We prove that under the assumption of suphomogeneity, archimedeanness holds for a PE-algebra with the Riesz property if and only if it holds for its representing group. The algebra is in that case commutative. This result is established by using the technique of MacNeille completion. We give the exact condition for this completion to exist, and we clearly exhibit the role played by archimedeanness and by sup-homogeneity.     

Prefixed tableaus and nested sequents

Nested sequent systems for modal logics are a relatively recent development, within the general area known as deep reasoning. The idea of deep reasoning is to create systems within which one operates at lower levels in formulas than just those involving the main connective or operator. Prefixed tableaus go back to 1972, and are modal tableau systems with extra machinery to represent accessibility in a purely syntactic way. We show that modal nested sequents and prefixed modal tableaus are notational variants of each other, roughly in the same way that Gentzen sequent calculi and tableaus are notational variants. This immediately gives rise to new modal nested sequent systems which may be of independent interest. We discuss some of these, including those for some justification logics that include standard modal operators.