Decidable and enumerable predicate logics of provability

Predicate modal formulas are considered as schemata of arithmetical formulas, where is interpreted as the standard formula of provability in a fixed sufficiently rich theory T in the language of arithmetic. QL _T(T) and QL _T are the sets of schemata of T-provable and true formulas, correspondingly. Solovay's well-known result — construction an arithmetical counterinterpretation by Kripke countermodel — is generalized on the predicate modal language; axiomatizations of the restrictions of QL _T(T) and QL _T by formulas, which contain no variables different from x, are given by means of decidable prepositional bimodal systems; under the assumption that T is ₁-complete, there is established the enumerability of the restrictions of QL _T(T) and QL _T by: 1) formulas in which the domains of different occurrences of don't intersect and 2) formulas of the form ⁿ A.     

On Meaningfulness and Truth

We show how to construct certain L _{M, T} -type interpreted languages, with each such language containing meaningfulness and truth predicates which apply to itself. These languages are comparable in expressive power to the L _T -type, truth-theoretic languages first considered by Kripke, yet each of our L _{M, T} -type languages possesses the additional advantage that, within it, the meaninglessness of any given meaningless expression can itself be meaningfully expressed. One therefore has, for example, the object level truth (and meaningfulness) of the claim that the strengthened Liar is meaningless.     

Valuation Semantics for First-Order Logics of Evidence and Truth

This paper introduces the logic QLET_F, a quantified extension of the logic of evidence and truth LET_F, together with a corresponding sound and complete first-order non-deterministic valuation semantics. LET_F is a paraconsistent and paracomplete sentential logic that extends the logic of first-degree entailment (FDE) with a classicality operator ∘ and a non-classicality operator ∙, dual to each other: while ∘A entails that A behaves classically, ∙A follows from A’s violating some classically valid inferences. The semantics of QLET_F combines structures that interpret negated predicates in terms of anti-extensions with first-order non-deterministic valuations, and completeness is obtained through a generalization of Henkin’s method. By providing sound and complete semantics for first-order extensions of FDE, K3, and LP, we show how these tools, which we call here the method of anti-extensions + valuations, can be naturally applied to a number of non-classical logics.

     

First-Order Frege Theory is Undecidable

The system whose only predicate is identity, whose only nonlogical vocabulary is the abstraction operator, and whose axioms are all first-order instances of Frege's Axiom V is shown to be undecidable.     

Probability: A new logico-semantical approach

This approach does not define a probability measure by syntactical structures. It reveals a link between modal logic and mathematical probability theory. This is shown (1) by adding an operator (and two further connectives and constants) to a system of lower predicate calculus and (2) regarding the models of that extended system. These models are models of the modal systemS ₅ (without the Barcan formula), where a usual probability measure is defined on their set of possible worlds. Mathematical probability models can be seen as models ofS ₅.     

The temporal architecture of central information processing: Evidence for a tentative time-quantum model

Summary A new, elaborated version of a time-quantum model (TQM) is outlined and illustrated by applying it to different experimental paradigms. As a basic prerequisite TQM adopts the coexistence of different discrete time units or (perceptual) intermittencies as constituent elements of the temporal architecture of mental processes. Unlike similar other approaches, TQM assumes the existence of an absolute lower bound for intermittencies, the time-quantum T, as an (approximately) universal constant and which has a duration of approximately 4.5 ms. Intermittencies of TQM must be multiples T _k=k·T ^* within the interval T ^*T _kL·T ^*M·T ^* with T ^*=q·T and integer q, k, L, and M. Here M denotes an upper bound for multipliers characteristic of individuals, the so-called coherence length; q and L may depend on task, individual and other factors. A second constraint is that admissible intermittencies must be integer fractions of L, the operative upper bound. In addition, M is assumed to determine the number of elementary information units to be stored in short-term memory.     

Frege's Begriffsschrift is Indeed First-Order Complete

It is widely taken that the first-order part of Frege's Begriffsschrift is complete. However, there does not seem to have been a formal verification of this received claim. The general concern is that Frege's system is one axiom short in the first-order predicate calculus comparing to, by now, standard first-order theory. Yet Frege has one extra inference rule in his system. Then the question is whether Frege's first-order calculus is still deductively sufficient as far as the first-order completeness is concerned. In this short note we confirm that the missing axiom is derivable from his stated axioms and inference rules, and hence the logic system in the Begriffsschrift is indeed first-order complete.     

The abstract variable-binding calculus

Theabstract variable binding calculus (VB-calculus) provides a formal frame-work encompassing such diverse variable-binding phenomena as lambda abstraction, Riemann integration, existential and universal quantification (in both classical and nonclassical logic), and various notions of generalized quantification that have been studied in abstract model theory. All axioms of the VB-calculus are in the form of equations, but like the lambda calculus it is not a true equational theory since substitution of terms for variables is restricted. A similar problem with the standard formalism of the first-order predicate logic led to the development of the theory of cylindric and polyadic Boolean algebras. We take the same course here and introduce the variety of polyadic VB-algebras as a pure equational form of the VB-calculus. In one of the main results of the paper we show that every locally finite polyadic VB-algebra of infinite dimension is isomorphic to a functional polyadic VB-algebra that is obtained from a model of the VB-calculus by a natural coordinatization process. This theorem is a generalization of the functional representation theorem for polyadic Boolean algebras given by P. Halmos. As an application of this theorem we present a strong completeness theorem for the VB-calculus. More precisely, we prove that, for every VB-theory T that is obtained by adjoining new equations to the axioms of the VB-calculus, there exists a model D such that _T s=t iff _D s=t. This result specializes to a completeness theorem for a number of familiar systems that can be formalized as VB-calculi. For example, the lambda calculus, the classical first-order predicate calculus, the theory of the generalized quantifierexists uncountably many and a fragment of Riemann integration.The work of the first author was supported in part by National Science Foundation Grant #DMS 8805870.     

Virtual Modality

Model-theoretic 1-types overa given first-order theory T may be construed as natural metalogical miniatures of G. W. Leibniz' ``complete individual notions', ``substances' or ``substantial forms'. This analogy prompts this essay's modal semantics for an essentiallyundecidable first-order theory T, in which one quantifies over such ``substances' in a boolean universe V(C), where C is the completion of the Lindenbaum-algebra of T.More precisely, one can define recursively a set-theoretic translate of formulae _N of formulae of a normal modal theory T_m based on T, such that the counterpart `<sub>i</sub>' of a the modal variable `x_i' of L(T_m) in this translation-scheme ranges over elements of V(C) that are 1-types of T with value 1 (sometimes called `definite' C-valued 1-types of T).The article's basic completeness-result (2.13) then establishes that varphi; is a theorem of T<sub>m</sub> iff [[ <sub>N</sub> () is aconsequenceof <sub>N</sub> (T<sub>m</sub>) for each extension N of T which is a subtheory of the canonical generic theory (ultrafilter) u]] = 1 – or equivalently, that T<sub>m</sub> is consistent iff[[there is anextension N of T such that N is a subtheory of the canonical generic theory u, and <sub>N</sub>() for all in T<sub>m</sub>]] > 0.The proof of thiscompleteness-result also shows that an N which provides a countermodel for a modally unprovable – or equivalently, a closed set in the Stone space St(T) in the sense of V(C) – is intertranslatable with an `accessibility'-relation of a closely related Kripke-semantics whose `worlds' are generic extensions of an initial universe V via C.This interrelation providesa fairly precise rationale for the semantics' recourse to C-valued structures, and exhibits a sense in which the boolean-valued context is sharp.     

On the Existence of Continua of Logics Between Some Intermediate Predicate Logics

A method for constructing continua of logics squeezed between some intermediate predicate logics, developed by Suzuki [8], is modified and applied to intervals of the form [L, L+ ¬¬S], where Lis a predicate logic, Sis a closed predicate formula. This solves one of the problems from Suzuki's paper.     

A Logic for Multiple-source Approximation Systems with Distributed Knowledge Base

The theory of rough sets starts with the notion of an approximation space, which is a pair (U,R), U being the domain of discourse, and R an equivalence relation on U. R is taken to represent the knowledge base of an agent, and the induced partition reflects a granularity of U that is the result of a lack of complete information about the objects in U. The focus then is on approximations of concepts on the domain, in the context of the granularity. The present article studies the theory in the situation where information is obtained from different sources. The notion of approximation space is extended to define a multiple-source approximation system with distributed knowledge base, which is a tuple (U,R_P)_{Pßf N}(U,R_P)_{P\ss_f N}, where N is a set of sources and P ranges over all finite subsets of N. Each R _P is an equivalence relation on U satisfying some additional conditions, representing the knowledge base of the group P of sources. Thus each finite group of sources and hence individual source perceives the same domain differently (depending on what information the group/individual source has about the domain), and the same concept may then have approximations that differ with the groups. In order to express the notions and properties related with rough set theory in this multiple-source situation, a quantified modal logic LMSAS ^D is proposed. In LMSAS ^D , quantification ranges over modalities, making it different from modal predicate logic and modal logic with propositional quantifiers. Some fragments of LMSAS ^D are discussed and it is shown that the modal system KTB is embedded in LMSAS ^D . The epistemic logic S5^D_nS5^D_n is also embedded in LMSAS ^D , and cannot replace the latter to serve our purpose. The relationship of LMSAS ^D with first and second-order logics is presented. Issues of expressibility, axiomatization and decidability are addressed.     

The architecture of modern mathematics: Essays in history and philosophy

It is a little understood fact that the system of formal logic presented in Wittgenstein’s Tractatusprovides the basis for an alternative general semantics for a predicate calculus that is consistent and coherent, essentially independent of the metaphysics of logical atomism, and philosophically illuminating in its own right. The purpose of this paper is threefold: to describe the general characteristics of a Tractarian-style semantics, to defend the Tractatus system against the charge of expressive incompleteness as levelled by Robert Fogelin, and to give a semantics for a formal language that is the Tractarian equivalent of a first-order predicate calculus. Of note in regard to the latter is the fact that a Tractatusstyle truth-definition makes no appeal to the technical trick of defining truth in terms of the satisfaction of predicates by infinite sequences of objects, yet is materially equivalent to the usual Tarski-style truth-definitions     

Temporal Reference in Linear Tense Logic

The paper introduces a first-order theory in the language of predicate tense logic which contains a single simple axiom. It is shewn that this theory enables times to be referred to and sentences involving ‘now’ and ‘then’ to be formalised. The paper then compares this way of increasing the expressive capacity of predicate tense logic with other mechanisms, and indicates how to generalise the results to other modal and tense systems.     

The <Emphasis Type="Italic">γ</Emphasis>-admissibility of Relevant Modal Logics II — The Method using Metavaluations

The γ-admissibility is one of the most important problems in the realm of relevant logics. To prove the γ-admissibility, either the method of normal models or the method using metavaluations may be employed. The γ-admissibility of a wide class of relevant modal logics has been discussed in Part I based on a former method, but the γ-admissibility based on metavaluations has not hitherto been fully considered. Sahlqvist axioms are well known as a means of expressing generalized forms of formulas with modal operators. This paper shows that γ is admissible for relevant modal logics with restricted Sahlqvist axioms in terms of the method using metavaluations.     

Incompleteness and the Barcan formula

A (normal) system of prepositional modal logic is said to be complete iff it is characterized by a class of (Kripke) frames. When we move to modal predicate logic the question of completeness can again be raised. It is not hard to prove that if a predicate modal logic is complete then it is characterized by the class of all frames for the propositional logic on which it is based. Nor is it hard to prove that if a propositional modal logic is incomplete then so is the predicate logic based on it. But the interesting question is whether a complete propositional modal logic can have an incomplete extension. In 1967 Kripke announced the incompleteness of a predicate extension of S4. The purpose of the present article is to present several such systems. In the first group it is the systemswith the Barcan Formula which are incomplete, while those without are complete. In the second group it is thosewithout the Barcan formula which are incomplete, while those with the Barcan Formula are complete. But all these are based on propositional systems which are characterized by frames satisfying in each case a single first-order sentence.     

Algorithmic problems concerning first-order definability of modal formulas on the class of all finite frames

The main result is that is no effective algorithmic answer to the question:how to recognize whether arbitrary modal formula has a first-order equivalent on the class of finite frames. Besides, two known problems are solved: it is proved algorithmic undecidability of finite frame consequence between modal formulas; the difference between global and local variants of first-order definability of modal formulas on the class of transitive frames is shown.Presented byHiroakira Ono     

Remarks on Gregory's “Actually” Operator

In this note we show that the classical modal technology of Sahlqvist formulas gives quick proofs of the completeness theorems in [8] (D. Gregory, Completeness and decidability results for some propositional modal logics containing actually operators, Journal of Philosophical Logic 30(1): 57–78, 2001) and vastly generalizes them. Moreover, as a corollary, interpolation theorems for the logics considered in [8] are obtained. We then compare Gregory's modal language enriched with an actually operator with the work of Arthur Prior now known under the name of hybrid logic. This analysis relates the actually axioms to standard hybrid axioms, yields the decidability results in [8], and provides a number of complexity results. Finally, we use a bisimulation argument to show that the hybrid language is strictly more expressive than Gregory's language.     

On Intermediate Predicate Logics of some Finite Kripke Frames,I. Levelwise Uniform Trees

An intermediate predicate logic L is called finite iff it is characterized by a finite partially ordered set M, i.e., iff L is the logic of the class of all predicate Kripke frames based on M. In this paper we study axiomatizability of logics of this kind. Namely, we consider logics characterized by finite trees M of a certain type (levelwise uniform trees) and establish the finite axiomatizability criterion for this case.