A note on the monotone functional interpretation

We prove a result relating the author's monotone functional interpretation to the bounded functional interpretation due to Ferreira and Oliva. More precisely we show that (over model of majorizable functionals) largely a solution for the bounded interpretation also is a solution for the monotone functional interpretation although the latter uses the existence of an underlying precise witness. This makes it possible to focus on the extraction of bounds (as in the bounded interpretation) while using the conceptual benefit of having precise realizers at the same time without having to construct them.     

Two General Results on Intuitionistic Bounded Theories

We study, within the framework of intuitionistic logic, two well-known general results of (classical logic) bounded arithmetic. Firstly, Parikh's theorem on the existence of bounding terms for the provably total functions. Secondly, the result which states that adding the scheme of bounded collection to (suitable) bounded theories does not yield new II₂ consequences.     

Equivalence of bar induction and bar recursion for continuous functions with continuous moduli

We compare Brouwer's bar theorem and Spector's bar recursion for the lowest type in the context of constructive reverse mathematics. To this end, we reformulate bar recursion as a logical principle stating the existence of a bar recursor for every function which serves as the stopping condition of bar recursion. We then show that the decidable bar induction is equivalent to the existence of a bar recursor for every continuous function from ${\mathbb{N}}^{\mathbb{N}}$ to $\mathbb{N}$ with a continuous modulus. We also introduce fan recursion, the bar recursion for binary trees, and show that the decidable fan theorem is equivalent to the existence of a fan recursor for every continuous function from ${\{0,1\}}^{\mathbb{N}}$ to $\mathbb{N}$ with a continuous modulus. The equivalence for bar induction holds over the extensional version of intuitionistic arithmetic in all finite types augmented with the characteristic principles of Gödel's Dialectica interpretation. On the other hand, we show the equivalence for fan theorem without using such extra principles.     

Extracting Algorithms from Intuitionistic Proofs

This paper presents a new method - which does not rely on the cut-elimination theorem - for characterizing the provably total functions of certain intuitionistic subsystems of arithmetic. The new method hinges on a realizability argument within an infinitary language. We illustrate the method for the intuitionistic counterpart of Buss's theory S, and we briefly sketch it for the other levels of bounded arithmetic and for the theory IΣ₁.     

Reasoning about proof and knowledge

In previous work [15], we presented a hierarchy of classical modal systems, along with algebraic semantics, for the reasoning about intuitionistic truth, belief and knowledge. Deviating from Gödel's interpretation of IPC in S4, our modal systems contain IPC in the way established in [13]. The modal operator can be viewed as a predicate for intuitionistic truth, i.e. proof. Epistemic principles are partially adopted from Intuitionistic Epistemic Logic IEL [4]. In the present paper, we show that the S5-style systems of our hierarchy correspond to an extended Brouwer–Heyting–Kolmogorov interpretation and are complete w.r.t. a relational semantics based on intuitionistic general frames. In this sense, our S5-style logics are adequate and complete systems for the reasoning about proof combined with belief or knowledge. The proposed relational semantics is a uniform framework in which also IEL can be modeled. Verification-based intuitionistic knowledge formalized in IEL turns out to be a special case of the kind of knowledge described by our S5-style systems.     

Uniform K-theory,and Poincaré duality for uniform K-homology

We revisit ?pakula's uniform K-homology, construct the external product for it and use this to deduce homotopy invariance of uniform K-homology.We define uniform K-theory and on manifolds of bounded geometry we give an interpretation of it via vector bundles of bounded geometry. We further construct a cap product with uniform K-homology and prove Poincaré duality between uniform K-theory and uniform K-homology on spin^c manifolds of bounded geometry.     

Possible world semantics for first-order logic of proofs

In the tech report Artemov and Yavorskaya (Sidon) (2011) [4] an elegant formulation of the first-order logic of proofs was given, FOLP. This logic plays a fundamental role in providing an arithmetic semantics for first-order intuitionistic logic, as was shown. In particular, the tech report proved an arithmetic completeness theorem, and a realization theorem for FOLP. In this paper we provide a possible-world semantics for FOLP, based on the propositional semantics of Fitting (2005) [5]. We also give an Mkrtychev semantics. Motivation and intuition for FOLP can be found in Artemov and Yavorskaya (Sidon) (2011) [4], and are not fully discussed here.     

Categories with families and first-order logic with dependent sorts

First-order logic with dependent sorts, such as Makkai's first-order logic with dependent sorts (FOLDS), or Aczel's and Belo's dependently typed (intuitionistic) first-order logic (DFOL), may be regarded as logic enriched dependent type theories. Categories with families (cwfs) is an established semantical structure for dependent type theories, such as Martin-Löf type theory. We introduce in this article a notion of hyperdoctrine over a cwf, and show how FOLDS and DFOL fit in this semantical framework. A soundness and completeness theorem is proved for DFOL. The semantics is functorial in the sense of Lawvere, and uses a dependent version of the Lindenbaum-Tarski algebra for a DFOL theory. Agreement with standard first-order semantics is established. Applications of DFOL to constructive mathematics and categorical foundations are given. A key feature is a local propositions-as-types principle.     

On the finiteness theorem of Siegel and Mahler concerning diophantine equations

In this paper we present a new proof, involving so-called nonstandard arguments, of Siegel's classical theorem on diophantine equations: Any irreducible algebraic equation f(x,y) = 0 of genus g > 0 admits only finitely many integral solutions. We also include Mahler's generalization of this theorem, namely the following: Instead of solutions in integers, we are considering solutions in rationals, but with the provision that their denominators should be divisible only by such primes which belong to a given finite set. Then again, the above equation admits only finitely many such solutions. From general nonstandard theory, we need the definition and the existence of enlargements of an algebraic number field. The idea of proof is to compare the natural arithmetic in such an enlargement, with the functional arithmetic in the function field defined by the above equation.     

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     

Provably recursive functions of constructive and relatively constructive theories

In this paper we prove conservation theorems for theories of classical first-order arithmetic over their intuitionistic version. We also prove generalized conservation results for intuitionistic theories when certain weak forms of the principle of excluded middle are added to them. Members of two families of subsystems of Heyting arithmetic and Buss-Harnik’s theories of intuitionistic bounded arithmetic are the intuitionistic theories we consider. For the first group, we use a method described by Leivant based on the negative translation combined with a variant of Friedman’s translation. For the second group, we use Avigad’s forcing method.     

Preservation theorems for bounded formulas

In this paper we naturally define when a theory has bounded quantifier elimination, or is bounded model complete. We give several equivalent conditions for a theory to have each of these properties. These results provide simple proofs for some known results in the model theory of the bounded arithmetic theories like CPV and PV₁. We use the mentioned results to obtain some independence results in the context of intuitionistic bounded arithmetic. We show that, if the intuitionistic theory of polynomial induction on strict formulas proves decidability of formulas, then P=NP. We also prove that, if the mentioned intuitionistic theory proves , then P=NP.     

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.     

The strength of extensionality II — Weak weak set theories without infinity

By obtaining several new results on Cook-style two-sorted bounded arithmetic, this paper measures the strengths of the axiom of extensionality and of other weak fundamental set-theoretic axioms in the absence of the axiom of infinity, following the author’s previous work [K. Sato, The strength of extensionality I — weak weak set theories with infinity, Annals of Pure and Applied Logic 157 (2009) 234-268] which measures them in the presence. These investigations provide a uniform framework in which three different kinds of reverse mathematics-Friedman-Simpson’s “orthodox” reverse mathematics, Cook’s bounded reverse mathematics and large cardinal theory-can be reformulated within one language so that we can compare them more directly.     

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.     

Comparing material and structural set theories

We study elementary theories of well-pointed toposes and pretoposes, regarded as category-theoretic or “structural” set theories in the spirit of Lawvere's “Elementary Theory of the Category of Sets”. We consider weak intuitionistic and predicative theories of pretoposes, and we also propose category-theoretic versions of stronger axioms such as unbounded separation, replacement, and collection. Finally, we compare all of these theories formally to traditional membership-based or “material” set theories, using a version of the classical construction based on internal well-founded relations.     

A focused approach to combining logics

We present a compact sequent calculus LKU for classical logic organized around the concept of polarization. Focused sequent calculi for classical, intuitionistic, and multiplicative-additive linear logics are derived as fragments of the host system by varying the sensitivity of specialized structural rules to polarity information. We identify a general set of criteria under which cut-elimination holds in such fragments. From cut-elimination we derive a unified proof of the completeness of focusing. Furthermore, each sublogic can interact with other fragments through cut. We examine certain circumstances, for example, in which a classical lemma can be used in an intuitionistic proof while preserving intuitionistic provability. We also examine the possibility of defining classical-linear hybrid logics.     

Transfer principles in nonstandard intuitionistic arithmetic

 Using a slight generalization, due to Palmgren, of sheaf semantics, we present a term-model construction that assigns a model to any first-order intuitionistic theory. A modification of this construction then assigns a nonstandard model to any theory of arithmetic, enabling us to reproduce conservation results of Moerdijk and Palmgren for nonstandard Heyting arithmetic. Internalizing the construction allows us to strengthen these results with additional transfer rules; we then show that even trivial transfer axioms or minor strengthenings of these rules destroy conservativity over HA. The analysis also shows that nonstandard HA has neither the disjunction property nor the explicit definability property. Finally, careful attention to the complexity of our definitions allows us to show that a certain weak fragment of intuitionistic nonstandard arithmetic is conservative over primitive recursive arithmetic. Received: 7 January 2000 / Revised version: 26 March 2001 / Published online: 12 July 2002     

An Effective Conservation Result for Nonstandard Arithmetic

We prove that a nonstandard extension of arithmetic is effectively conservative over Peano arithmetic by using an internal version of a definable ultrapower. By the same method we show that a certain extension of the nonstandard theory with a saturation principle has the same proof‐theoretic strength as second order arithmetic, where comprehension is restricted to arithmetical formulas.