Kripke semantics for provability logic GLP

A well-known polymodal provability logic due to Japaridze is complete w.r.t. the arithmetical semantics where modalities correspond to reflection principles of restricted logical complexity in arithmetic. This system plays an important role in some recent applications of provability algebras in proof theory. However, an obstacle in the study of is that it is incomplete w.r.t. any class of Kripke frames. In this paper we provide a complete Kripke semantics for . First, we isolate a certain subsystem of that is sound and complete w.r.t. a nice class of finite frames. Second, appropriate models for are defined as the limits of chains of finite expansions of models for . The techniques involves unions of n-elementary chains and inverse limits of Kripke models. All the results are obtained by purely modal-logical methods formalizable in elementary arithmetic.     

Cut elimination and strong separation for substructural logics: An algebraic approach

We develop a general algebraic and proof-theoretic study of substructural logics that may lack associativity, along with other structural rules. Our study extends existing work on (associative) substructural logics over the full Lambek Calculus (see, for example, Ono (2003) [34], Galatos and Ono (2006) [18], Galatos et al. (2007) [17]). We present a Gentzen-style sequent system that lacks the structural rules of contraction, weakening, exchange and associativity, and can be considered a non-associative formulation of . Moreover, we introduce an equivalent Hilbert-style system and show that the logic associated with and is algebraizable, with the variety of residuated lattice-ordered groupoids with unit serving as its equivalent algebraic semantics.Overcoming technical complications arising from the lack of associativity, we introduce a generalized version of a logical matrix and apply the method of quasicompletions to obtain an algebra and a quasiembedding from the matrix to the algebra. By applying the general result to specific cases, we obtain important logical and algebraic properties, including the cut elimination of and various extensions, the strong separation of , and the finite generation of the variety of residuated lattice-ordered groupoids with unit.     

Completeness for flat modal fixpoint logics

This paper exhibits a general and uniform method to prove axiomatic completeness for certain modal fixpoint logics. Given a set Γ of modal formulas of the form γ(x,p₁,…,p_n), where x occurs only positively in γ, we obtain the flat modal fixpoint language L_?(Γ) by adding to the language of polymodal logic a connective ?_γ for each γ∈Γ. The term ?_γ(φ₁,…,φ_n) is meant to be interpreted as the least fixed point of the functional interpretation of the term γ(x,φ₁,…,φ_n). We consider the following problem: given Γ, construct an axiom system which is sound and complete with respect to the concrete interpretation of the language L_?(Γ) on Kripke structures. We prove two results that solve this problem.First, let be the logic obtained from the basic polymodal by adding a Kozen-Park style fixpoint axiom and a least fixpoint rule, for each fixpoint connective ?_γ. Provided that each indexing formula γ satisfies a certain syntactic criterion, we prove this axiom system to be complete.Second, addressing the general case, we prove the soundness and completeness of an extension of . This extension is obtained via an effective procedure that, given an indexing formula γ as input, returns a finite set of axioms and derivation rules for ?_γ, of size bounded by the length of γ. Thus the axiom system is finite whenever Γ is finite.     

An analogue of Hilbert's 10th problem for fields of meromorphic functions over non-Archimedean valued fields

Let K be a complete and algebraically closed valued field of characteristic 0. We prove that the set of rational integers is positive existentially definable in the field of meromorphic functions on K in the language of rings augmented by a constant symbol for the independent variable z and by a symbol for the unary relation “the function x takes the value 0 at 0”. Consequently, we prove that the positive existential theory of in the language is undecidable. In order to obtain these results, we obtain a complete characterization of all analytic projective maps (over K) from an elliptic curve minus a point to , for any elliptic curve defined over the field of constants.     

Admissible rules in the implication-negation fragment of intuitionistic logic

Uniform infinite bases are defined for the single-conclusion and multiple-conclusion admissible rules of the implication-negation fragments of intuitionistic logic and its consistent axiomatic extensions (intermediate logics). A Kripke semantics characterization is given for the (hereditarily) structurally complete implication-negation fragments of intermediate logics, and it is shown that the admissible rules of this fragment of form a PSPACE-complete set and have no finite basis.     

A minimal classical sequent calculus free of structural rules

Gentzen’s classical sequent calculus has explicit structural rules for contraction and weakening. They can be absorbed (in a right-sided formulation) by replacing the axiom P,¬P by Γ,P,¬P for any context Γ, and replacing the original disjunction rule with Γ,A,B implies Γ,A∨B.This paper presents a classical sequent calculus which is also free of contraction and weakening, but more symmetrically: both contraction and weakening are absorbed into conjunction, leaving the axiom rule intact. It uses a blended conjunction rule, combining the standard context-sharing and context-splitting rules: Γ,Δ,A and Γ,Σ,B implies Γ,Δ,Σ,A∧B. We refer to this system as minimal sequent calculus.We prove a minimality theorem for the propositional fragment : any propositional sequent calculus S (within a standard class of right-sided calculi) is complete if and only ifS contains (that is, each rule of is derivable in S). Thus one can view as a minimal complete core of Gentzen’s .     

Classical predicative logic-enriched type theories

A logic-enriched type theory (LTT) is a type theory extended with a primitive mechanism for forming and proving propositions. We construct two LTTs, named and , which we claim correspond closely to the classical predicative systems of second order arithmetic and . We justify this claim by translating each second order system into the corresponding LTT, and proving that these translations are conservative. This is part of an ongoing research project to investigate how LTTs may be used to formalise different approaches to the foundations of mathematics.The two LTTs we construct are subsystems of the logic-enriched type theory , which is intended to formalise the classical predicative foundation presented by Herman Weyl in his monograph Das Kontinuum. The system has also been claimed to correspond to Weyl’s foundation. By casting and as LTTs, we are able to compare them with . It is a consequence of the work in this paper that is strictly stronger than .The conservativity proof makes use of a novel technique for proving one LTT conservative over another, involving defining an interpretation of the stronger system out of the expressions of the weaker. This technique should be applicable in a wide variety of different cases outside the present work.     

Games with 1-backtracking

We associate with any game G another game, which is a variant of it, and which we call . Winning strategies for have a lower recursive degree than winning strategies for G: if a player has a winning strategy of recursive degree 1 over G, then it has a recursive winning strategy over , and vice versa. Through we can express in algorithmic form, as a recursive winning strategy, many (but not all) common proofs of non-constructive Mathematics, namely exactly the theorems of the sub-classical logic Limit Computable Mathematics (Hayashi (2006) [6], Hayashi and Nakata (2001) [7]).     

Sequences of semicontinuous functions accompanying continuous functions

A space X is said to have property (USC) (resp. (LSC)) if whenever is a sequence of upper (resp. lower) semicontinuous functions from X into the closed unit interval [0,1] converging pointwise to the constant function 0 with the value 0, there is a sequence of continuous functions from X into [0,1] such that fn?gn (n∈ω) and converges pointwise to 0. In this paper, we study spaces having these properties and related ones. In particular, we show that (a) for a subset X of the real line, X has property (USC) if and only if it is a σ-set; (b) if X is a space of non-measurable cardinal and has property (LSC), then it is discrete. Our research comes of Scheepers' conjecture on properties S₁(Γ,Γ) and wQN.     

Generalized arithmetic operators and their relationship to t-norms in interval-valued fuzzy set theory

In this paper we study extensions of the arithmetic operators +, -, ·, ÷ to the lattice of closed subintervals of the unit interval. Starting from a minimal set of axioms that these operators must fulfill, we investigate which properties they satisfy. We also investigate some classes of t-norms on which can be generated using these operators; these classes provide natural extensions of the Łukasiewicz, product, Frank, Schweizer–Sklar and Yager t-norms to .     

Holomorphy of spectral multipliers of the Ornstein-Uhlenbeck operator

Let γ be the Gauss measure on and the Ornstein-Uhlenbeck operator. For every p in [1,∞)?{2}, set , and consider the sector . The main results of this paper are the following. If p is in (1,∞)?{2}, and , i.e., if M is an Lp(γ)uniform spectral multiplier of in our terminology, and M is continuous on , then M extends to a bounded holomorphic function on the sector . Furthermore, if p=1 a spectral multiplier M, continuous on , satisfies the condition if and only if M extends to a bounded holomorphic function on the right half-plane, and its boundary value M(i·) on the imaginary axis is the Euclidean Fourier transform of a finite Borel measure on the real line. We prove similar results for uniform spectral multipliers of second order elliptic differential operators in divergence form on belonging to a wide class, which contains . From these results we deduce that operators in this class do not admit an H^∞ functional calculus in sectors smaller than .     

q-Analog of the Möbius function and the cyclotomic identity associated to a profinite group

Let G be a profinite group and q an indeterminate. In this paper, we introduce and study a q-analog of the Möbius function and the cyclotomic identity arising from the lattice of open subgroups of G. When q is any integer, we show that they have close connections with the functors , , and introduced in [Y.-T. Oh, q-Deformation of Witt-Burnside rings, Math. Z. 257 (2007) 151-191]. In particular, we interpret the multiplicative property of the inverse of the table of marks and the Möbius function of G as a composition property of certain functors. Classification of , , and up to strict natural isomorphism as q varies over the set of integers and its application will be dealt with, too.     

Nonstandard arithmetic and recursive comprehension

First order reasoning about hyperintegers can prove things about sets of integers. In the author’s paper Nonstandard Arithmetic and Reverse Mathematics, Bulletin of Symbolic Logic 12 (2006) 100-125, it was shown that each of the “big five” theories in reverse mathematics, including the base theory , has a natural nonstandard counterpart. But the counterpart of has a defect: it does not imply the Standard Part Principle that a set exists if and only if it is coded by a hyperinteger. In this paper we find another nonstandard counterpart, , that does imply the Standard Part Principle.     

Congruences involving Bernoulli polynomials

Let {B_n(x)} be the Bernoulli polynomials. In the paper we establish some congruences for , where p is an odd prime and x is a rational p-integer. Such congruences are concerned with the properties of p-regular functions, the congruences for and the sum , where h(d) is the class number of the quadratic field of discriminant d and p-regular functions are those functions f such that are rational p-integers and for n=1,2,3,… . We also establish many congruences for Euler numbers.     

The double negation of the intermediate value theorem

In the context of intuitionistic analysis, we consider the set F consisting of all continuous functions ? from [0,1] to R such that ?(0)=0 and ?(1)=1, and the set I₀ consisting of ?’s in F where there exists x∈[0,1] such that . It is well-known that there are weak counterexamples to the intermediate value theorem, and with Brouwer’s continuity principle we have I₀≠F. However, there exists no satisfying answer to . We try to answer to this question by reducing it to a schema (which we call ) about intuitionistic decidability that asserts “there exists an intuitionistically enumerable set that is not intuitionistically decidable”. We also introduce the notion of strong Specker double sequence, and prove that the existence of such a double sequence is equivalent to the existence of a function ?∈F_mon where .     

Canonical extensions for congruential logics with the deduction theorem

We introduce a new and general notion of canonical extension for algebras in the algebraic counterpart of any finitary and congruential logic S. This definition is logic-based rather than purely order-theoretic and is in general different from the definition of canonical extensions for monotone poset expansions, but the two definitions agree whenever the algebras in are based on lattices. As a case study on logics purely based on implication, we prove that the varieties of Hilbert and Tarski algebras are canonical in this new sense.