Probability,fuzziness and borderline cases

An integrated approach to truth-gaps and epistemic uncertainty is described, based on probability distributions defined over a set of three-valued truth models. This combines the explicit representation of borderline cases with both semantic and stochastic uncertainty, in order to define measures of subjective belief in vague propositions. Within this framework we investigate bridges between probability theory and fuzziness in a propositional logic setting. In particular, when the underlying truth model is from Kleene's three-valued logic then we provide a complete characterisation of compositional min–max fuzzy truth degrees. For classical and supervaluationist truth models we find partial bridges, with min and max combination rules only recoverable on a fragment of the language. Across all of these different types of truth valuations, min–max operators are resultant in those cases in which there is only uncertainty about the relative sharpness or vagueness of the interpretation of the language.     

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.     

A new technique for proving realisability and consistency theorems using finite paraconsistent models of cut‐free logic

A new technique for proving realisability results is presented, and is illustrated in detail for the simple case of arithmetic minus induction. CL is a Gentzen formulation of classical logic. CPQ is CL minus the Cut Rule. The basic proof theory and model theory of CPQ and CL is developed. For the semantics presented CPQ is a paraconsistent logic, i.e. there are non‐trivial CPQ models in which some sentences are both true and false. Two systems of arithmetic minus induction are introduced, CL‐A and CPQ‐A based on CL and CPQ, respectively. The realisability theorem for CPQ‐A is proved: It is shown constructively that to each theorem A of CPQ‐A there is a formula A *, a so‐called “realised disjunctive form of A ”, such that variables bound by essentially existential quantifiers in A * can be written as recursive functions of free variables and variables bound by essentially universal quantifiers. Realisability is then applied to prove the consistency of CL‐A, making use of certain finite non‐trivial inconsistent models of CPQ‐A. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

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 arithmetic complexity of certain constructive logics

A constructive arithmetical theory is an arbitrary set of closed arithmetical formulas that is closed with respect to derivability in an intuitionsitic arithmetic with the Markov principle and the formal Church thesis. For each arithmetical theory T there is a corresponding logic L(T) consisting of closed predicate formulas in which all arithmetic instances belong to T. For so-called internally enumerable constructive arithmetical theories with the property of existentiality, it is proved that the logic L(T) is II₁ ^T -@#@ complete. This implies, for example, that the logic of traditional constructivism is II₂ ⁰-complete.Translated from Matematicheskie Zametki, Vol. 52, No. 1, pp. 94–104, July, 1992.     

Countability of the set of closed overclasses of some minimal classes in the partly ordered set ℒ<Subscript>2</Subscript><Superscript>3</Superscript> of all closed classes of three-valued logic that can be mapped homomorphically onto two-valued logic

The following theorem is proved: the set of closed classes containing some minimal classes in the partly ordered set ?₂ ³ of closed classes in the three-valued logic that may be mapped homomorphically onto the two-valued logic is countable.     

On function classes in P 3 precomplete with respect to a strengthened closure operator

A classical theorem of Post [1] describes five precomplete classes in the set of Boolean functions. In [2], it was shown that there exist 18 precomplete classes of functions of three-valued logic. In [1, 2], the closure of sets of functions with respect to the substitution operator was studied. We consider two closure operators on functions of three-valued logic, which are obtained by supplementing the substitution operator by closures with respect to two identifications of function values, and prove the existence of three precomplete classes for one of these operators and five precomplete classes for the other.     

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.     

三值R_0命题逻辑系统中理论的随机发散度

在三值R_0命题逻辑系统中,给出了随机相似度和随机逻辑伪距离的基本性质.然后在随机逻辑度量空间中提出了理论的随机发散度,指出全体原子公式之集在随机逻辑度量空间中未必是全发散的,其是否全发散取决于给定的随机数序的分布.     

A note on kernels and Sperner’s Lemma

The kernel-solvability of perfect graphs was first proved by Boros and Gurvich, and later Aharoni and Holzman gave a shorter proof. Both proofs were based on Scarf’s Lemma. In this note we show that a very simple proof can be given using a polyhedral version of Sperner’s Lemma. In addition, we extend the Boros–Gurvich theorem to h-perfect graphs and to a more general setting.     

On time-dependent orthogonal polynomials on the unit circle

Two index formulas for operators defined by infinite band matrices are proved. These results may be interpreted as a generalization of a classical theorem of M. G. Krein on orthogonal polynomials. The proofs are based on dichotomy and nonstationary inertia theory.Dedicated to the memory of M. G. Krein, a mathematical giant, a great teacher and wonderful friend.Published in Ukrainskii Matematicheskii Zhurnal, Vol. 46, Nos. 1–2, pp. 18–36, January–February, 1994.     

An Intuitionistic Axiomatisation of Real Closed Fields

We give an intuitionistic axiomatisation of real closed fields which has the constructive reals as a model. The main result is that this axiomatisation together with just the decidability of the order relation gives the classical theory of real closed fields. To establish this we rely on the quantifier elimination theorem for real closed fields due to Tarski, and a conservation theorem of classical logic over intuitionistic logic for geometric theories.     

Certain Partial Conservativeness Properties of Intuitionistic Set Theory with the Principle of Double Complement of Sets

The Zermelo–Fraenkel set theory with the underlying intuitionistic logic (for brevity, we refer to it as the intuitionistic Zermelo–Fraenkel set theory) in a two-sorted language (where the sort 0 is assigned to numbers and the sort 1, to sets) with the collection scheme used as the replacement scheme of axioms (the ZFI2C theory) is considered. Some partial conservativeness properties of the intuitionistic Zermelo–Fraenkel set theory with the principle of double complement of sets (DCS) with respect to a certain class of arithmetic formulas (the class all so-called AEN formulas) are proved. Namely, let T be one of the theories ZFI2C and ZFI2C + DCS. Then (1) the theory T+ECT is conservative over T with respect to the class of AEN formulas; (2) the theory T+ECT+M is conservative over T+M{su?} with respect to the class of AEN formulas. Here ECT stands for the extended Church’s thesis, Mis the strong Markov principle, and M{su?} is the weak Markov principle. The following partial conservativeness properties are also proved: (3) T+ECT+M is conservative over T with respect to the class of negative arithmetic formulas; (4) the classical theory ZF2 is conservative over ZFI2C with respect to the class of negative arithmetic formulas.     

Resplendent models and $${\Sigma_1^1}$$ -definability with an oracle

In this article we find some sufficient and some necessary -conditions with oracles for a model to be resplendent or chronically resplendent. The main tool of our proofs is internal arguments, that is analogues of classical theorems and model-theoretic constructions conducted inside a model of first-order Peano Arithmetic: arithmetised back-and-forth constructions and versions of the arithmetised completeness theorem, namely constructions of recursively saturated and resplendent models from the point of view of a model of arithmetic. These internal arguments are used in conjunction with Pabion’s theorem that ensures that certain oracles are coded in a sufficiently saturated model of arithmetic. Examples of applications are provided for the theories of dense linear orders and of discrete linear orders. These results are then generalised to other ω-categorical theories and theories with a unique countable recursively saturated model.      

Extracting Herbrand disjunctions by functional interpretation

Carrying out a suggestion by Kreisel, we adapt Gödel’s functional interpretation to ordinary first-order predicate logic(PL) and thus devise an algorithm to extract Herbrand terms from PL-proofs. The extraction is carried out in an extension of PL to higher types. The algorithm consists of two main steps: first we extract a functional realizer, next we compute the β-normal-form of the realizer from which the Herbrand terms can be read off. Even though the extraction is carried out in the extended language, the terms are ordinary PL-terms. In contrast to approaches to Herbrand’s theorem based on cut elimination orɛ-elimination this extraction technique is, except for the normalization step, of low polynomial complexity, fully modular and furthermore allows an analysis of the structure of the Herbrand terms, in the spirit of Kreisel ([13]), already prior to the normalization step. It is expected that the implementation of functional interpretation in Schwichtenberg’s MINLOG system can be adapted to yield an efficient Herbrand-term extraction tool.BRICS, Basic Research in Computer Science, funded by the Danish National Research FoundationUlrich Kohlenbach’s research was partially supported by the Danish National Research Council, Grant no. 21-02-0474.     

An epistemic model of an agent who does not reflect on reasoning processes

This paper introduces an epistemic model of a boundedly rational agent under the two assumptions that (i) the agent’s reasoning process is in accordance with the model but (ii) the agent does not reflect on these reasoning processes. For such a concept of bounded rationality a semantic interpretation by the possible world semantics of the Kripke (1963) type is no longer available because the definition of knowledge in these possible world semantics implies that the agent knows all valid statements of the model. The key to my alternative semantic approach is the extension of the method of truth tables, first introduced for the propositional logic by Wittgenstein (1922), to an epistemic logic so that I can determine the truth value of epistemic statements for all relevant truth conditions. In my syntactic approach I define an epistemic logic–consisting of the classical calculus of propositional logic plus two knowledge axioms–that does not include the inference rule of necessitation, which claims that an agent knows all theorems of the logic. As my main formal result I derive a determination theorem linking my semantic with my syntactic approach. The difference between my approach and existing knowledge models is illustrated in a game-theoretic application concerning the epistemic justification of iterative solution concepts.     

Effectively inseparable Boolean algebras in lattices of sentences

We show the non-arithmeticity of 1st order theories of lattices of Σ _n sentences modulo provable equivalence in a formal theory, of diagonalizable algebras of a wider class of arithmetic theories than has been previously known, and of the lattice of degrees of interpretability over PA. The first two results are applications of Nies’ theorem on the non-arithmeticity of the 1st order theory of the lattice of r.e. ideals on any effectively dense r.e. Boolean algebra. The theorem on degrees of interpretability relies on an adaptation of techniques leading to Nies’ theorem.     

A canonical partition theorem for equivalence relations on Zt

A canonical version of the multidimensional version of van der Waerden's theorem on arithmetic progressions is proved.     

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.     

Probabilistic number theory in additive arithmetic semigroups II

We prove two quantitative mean-value theorems of completely multiplicative functions on additive arithmetic semigroups. On the basis of the two theorems, a central limit theorem of additive functions on additive arithmetic semigroups is proved with a best possible error estimate. This generalizes the vital results of Halász and Elliott in classical probabilistic number theory to function fields. Received October 26, 1998; in final form April 5, 2000 / Published online October 11, 2000