Fundamenta Informaticae - Volume 164, issue 4

Authors: Szymanik, Jakub

Article Type: Introduction

DOI: 10.3233/FI-2019-1769

Citation: Fundamenta Informaticae, vol. 164, no. 4, pp. i-iii, 2019

Authors: Czarnecki, Marek | Zdanowski, Konrad

Article Type: Research Article

Abstract: The property of being true in almost all finite, initial segments of the standard model of arithmetic is ∑ 2 0 –complete. Thus, it admits a kind of a truth definition. We define such an arithmetical predicate. Then, we define its modal logic SL and prove a completeness theorem with respect to finite models semantics. The proof that SL is the modal logic of the approximate truth definition for finite arithmetical models is based on an extension of SL by a fixed-point construction.

Keywords: finite models, truth definition, modal logic

DOI: 10.3233/FI-2019-1770

Citation: Fundamenta Informaticae, vol. 164, no. 4, pp. 299-325, 2019

Authors: Grudzińska, Justyna | Zawadowski, Marek

Article Type: Research Article

Abstract: Classical scope-assignment strategies for multi-quantifier sentences involve quantifier phrase (QP)-movement (e.g., [11], [12]). More recent continuation-based approaches provide a compelling alternative, for they interpret QPs in situ — without resorting to Logical Forms or any structures beyond the overt syntax. The continuation-based strategies can be divided into two groups: those that locate the source of scope-ambiguity in the rules of semantic composition (e.g., [1]) and those that attribute it to the lexical entries for the quantifier words (e.g., [2], [8]). In this paper, we focus on the former operation-based approaches and the nature of the semantic operations involved. More specifically, …we discuss three such possible operation-based strategies for multi-quantifier sentences, together with their relative merits and costs. Show more

Keywords: continuation, quantification, scope ambiguity

DOI: 10.3233/FI-2019-1771

Citation: Fundamenta Informaticae, vol. 164, no. 4, pp. 327-344, 2019

Authors: Kalociński, Dariusz

Article Type: Research Article

Abstract: Modulus of a computable approximation is a function which returns the number of a stage at which the approximation has already converged for its argument. The least modulus points at the earliest such stage for each of its arguments. We recall and show some properties of least moduli, including their close connection to c.e. degrees, and minimal witnessing functions for FM -representable sets. We observe, for instance, that the non-density theorem for the d.c.e. degrees gives an example of an incomplete degree that has no least moduli below 0 _ ′ . Using the properties of …least moduli themselves, we construct a degree containing no least moduli for itself and having least moduli of incomparable degrees. In particular, the technique used demonstrates an approach of constructing a non-c.e. degree, which is somewhat different from that proposed by Cooper. Show more

Keywords: modulus, witnessing function, c.e. degrees, d.c.e. degrees, non-c.e. degrees, incomparable degrees

DOI: 10.3233/FI-2019-1772

Citation: Fundamenta Informaticae, vol. 164, no. 4, pp. 345-358, 2019

Authors: Zawadowski, Marek

Article Type: Research Article

Abstract: We give an abstract characterization of the category of co-semi-analytic functors and describe an action of semi-analytic functors on co-semi-analytic functors.

DOI: 10.3233/FI-2019-1773

Citation: Fundamenta Informaticae, vol. 164, no. 4, pp. 359-373, 2019

Authors: Zdanowski, Konrad

Article Type: Research Article

Abstract: We prove that there are single Henkin quantifiers such that first order logic augmented by one of these quantifiers is undecidable in the empty vocabulary. We estimate the size of such quantifiers proving undecidability of L 0 ( H 12 ) and L 0 ( E 10 ) .

Keywords: Henkin quantifiers, undecidability, word problem

DOI: 10.3233/FI-2019-1774

Citation: Fundamenta Informaticae, vol. 164, no. 4, pp. 375-386, 2019