This is a survey article on algebraic logic. It gives a historical background leading up to a modern perspective. Central problems in algebraic logic (like the representation problem) are discussed in connection to other branches of logic, like modal logic, proof theory, model-theoretic forcing, finite combinatorics, and Gödel’s incompleteness results. We focus on cylindric algebras. Relation algebras and polyadic algebras are mostly covered only insofar as they relate to cylindric algebras, and even there we have not told the whole story. (...) We relate the algebraic notion of neat embeddings (a notion special to cylindric algebras) to the metalogical ones of provability, interpolation and omitting types in variants of first logic. Another novelty that occurs here is relating the algebraic notion of atom-canonicity for a class of boolean algebras with operators to the metalogical one of omitting types for the corresponding logic. A hitherto unpublished application of algebraic logic to omitting types of first order logic is given. Proofs are included when they serve to illustrate certain concepts. Several open problems are posed. We have tried as much as possible to avoid exploring territory already explored in the survey articles of Monk [93] and Németi [97] in the subject. (shrink)

This article concerns the metatheory of a class of modal logics whose language includes propositional constants of various kinds. The main novelties are the use of general frames with specific restrictions and the definition of the strict range of a formula. Many examples from the literature are treated within the framework provided and some traditional model-theoretic issues such as preservation results concerning the validity of formulas and definability results concerning frame properties are addressed.

A complete axiomatic system CTL$_{rp}$ is introduced for a temporal logic for finitely branching $\omega^+$-trees in a temporal language extended with so called reference pointers. Syntactic and semantic interpretations are constructed for the branching time computation tree logic CTL$^{*}$ into CTL$_{rp}$. In particular, that yields a complete axiomatization for the translations of all valid CTL$^{*}$-formulae. Thus, the temporal logic with reference pointers is brought forward as a simpler (with no path quantifiers), but in a way more expressive medium for reasoning (...) about branching time. (shrink)

In recent years combinations of tense and modality have moved intothe focus of logical research. From a philosophical point of view, logical systems combining tense and modality are of interest because these logics have a wide field of application in original philosophical issues, for example in the theory of causation, of action, etc. But until now only methods yielding completeness results for propositional languages have been developed. In view of philosophical applications, analogous results with respect to languages of predicate logic (...) are desirable, and in this paper I present two such results. The main developments in this area can be split into two directions, differing in the question whether the ordering of time is world-independent or not. Semantically, this difference appears in the discussion whether T x W-frames or Kamp-frames (resp. Ockham-frames) provide a suitable semantics for combinations of tense and modality. Here, two calculi are presented, the first adequate with respect to Kamp-semantics, the second to T x Wsemantics. (Both calculi contain an appropriate version of Gabbay's irreflexivity rule.) Furthermore, the proposed constructions of canonical frames simplify some of those which have hitherto been discussed. (shrink)

The paper deals with the problem of axiomatizing a system T1 of discrete tense logic, where one thinks of time as the set Z of all the integers together with the operations +1 ("immediate successor") and-1 ("immediate predecessor"). T1 is like the Segerberg-Sundholm system WI in working with so-called infinitary inference ruldes; on the other hand, it differs from W I with respect to (i) proof-theoretical setting, (ii) presence of past tense operators and a "now" operator, and, most importantly, with (...) respect to (iii) the presence in T1 of so-called systematic frame constants, which are meant to hold at exactly one point in a temporal structure and to enable us to express the irreflexivity of such structures. Those frame constants will be seen to play a paramount role in our axiomatization of T1. (shrink)

We introduce and study hierarchies of extensions of the propositional modal and temporal languages with pairs of new syntactic devices: point of reference-reference pointer which enable semantic references to be made within a formula. We propose three different but equivalent semantics for the extended languages, discuss and compare their expressiveness. The languages with reference pointers are shown to have great expressive power (especially when their frugal syntax is taken into account), perspicuous semantics, and simple deductive systems. For instance, Kamp's and (...) Stavi's temporal operators, as well as nominals (names, clock variables), are definable in them. Universal validity in these languages is proved undecidable. The basic modal and temporal logics with reference pointers are uniformly axiomatized and a strong completeness theorem is proved for them and extended to some classes of their extensions. (shrink)

Hyperboolean algebras are Boolean algebras with operators, constructed as algebras of complexes (or, power structures) of Boolean algebras. They provide an algebraic semantics for a modal logic (called here a {\em hyperboolean modal logic}) with a Kripke semantics accordingly based on frames in which the worlds are elements of Boolean algebras and the relations correspond to the Boolean operations. We introduce the hyperboolean modal logic, give a complete axiomatization of it, and show that it lacks the finite model property. The (...) method of axiomatization hinges upon the fact that a "difference" operator is definable in hyperboolean algebras, and makes use of additional non-Hilbert-style rules. Finally, we discuss a number of open questions and directions for further research. (shrink)

So far, T×W frames have been employed to provide a semantics for a language of tense logic that includes a modal operator that expresses historical necessity. The operator is defined in terms of quantification over possible courses of events that satisfy a certain constraint, namely, that of being alike up to a given point. However, a modal operator can as well be defined without placing that constraint. This paper outlines a T×W logic where an operator of the latter kind is (...) used to express the epistemic property of definiteness. Section 1 provides the theoretical background. Sections 2 and 3 set out the semantics. Sections 4 and 5 show, drawing on established results, that there is a sound and complete axiomatization of the logic outlined. (shrink)

In this paper, we introduce a general technology, calledtaming, for finding well-behaved versions of well-investigated logics. Further, we state completeness, decidability, definability and interpolation results for a multimodal logic, calledarrow logic, with additional operators such as thedifference operator, andgraded modalities. Finally, we give a completeness proof for a strong version of arrow logic.

We investigate an enrichment of the propositional modal language L with a "universal" modality ■ having semantics x ⊧ ■φ iff ∀y(y ⊧ φ), and a countable set of "names" - a special kind of propositional variables ranging over singleton sets of worlds. The obtained language ℒ $_{c}$ proves to have a great expressive power. It is equivalent with respect to modal definability to another enrichment ℒ(⍯) of ℒ, where ⍯ is an additional modality with the semantics x ⊧ ⍯φ (...) iff Vy(y ≠ x → y ⊧ φ). Model-theoretic characterizations of modal definability in these languages are obtained. Further we consider deductive systems in ℒ $_{c}$ . Strong completeness of the normal ℒ $_{c}$ logics is proved with respect to models in which all worlds are named. Every ℒ $_{c}$ -logic axiomatized by formulae containing only names (but not propositional variables) is proved to be strongly frame-complete. Problems concerning transfer of properties ([in]completeness, filtration, finite model property etc.) from ℒ to ℒ $_{c}$ are discussed. Finally, further perspectives for names in multimodal environment are briefly sketched. (shrink)

Fictional truth, or truth in fiction/pretense, has been the object of extended scrutiny among philosophers and logicians in recent decades. Comparatively little attention, however, has been paid to its inferential relationships with time and with certain deliberate and contingent human activities, namely, the creation of fictional works. The aim of the paper is to contribute to filling the gap. Toward this goal, a formal framework is outlined that is consistent with a variety of conceptions of fictional truth and based upon (...) a specific formal treatment of time and agency, that of so-called stit logics. Moreover, a complete axiomatic theory of fiction-making TFM is defined, where fiction-making is understood as the exercise of agency and choice in time over what is fictionally true. The language \ of TFM is an extension of the language of propositional logic, with the addition of temporal and modal operators. A distinctive feature of \ with respect to other modal languages is a variety of operators having to do with fictional truth, including a ‘fictionality’ operator \ . Some applications of TFM are outlined, and some interesting linguistic and inferential phenomena, which are not so easily dealt with in other frameworks, are accounted for. (shrink)

This paper presents a new modal logic for ceteris paribus preferences understood in the sense of "all other things being equal". This reading goes back to the seminal work of Von Wright in the early 1960's and has returned in computer science in the 1990' s and in more abstract "dependency logics" today. We show how it differs from ceteris paribus as "all other things being normal", which is used in contexts with preference defeaters. We provide a semantic analysis and (...) several completeness theorems. We show how our system links up with Von Wright's work, and how it applies to game-theoretic solution concepts, to agenda setting in investigation, and to preference change. We finally consider its relation with infinitary modal logics. (shrink)

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 BASIC MODAL LOGIC . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.

A certain type of inference rules in modal logics, generalizing Gabbay's Irreflexivity rule, is introduced and some general completeness results about modal logics axiomatized with such rules are proved.

We study the general problem of axiomatizing structures in the framework of modal logic and present a uniform method for complete axiomatization of the modal logics determined by a large family of classes of structures of any signature.

This paper presents a new modal logic for ceteris paribus preferences understood in the sense of “all other things being equal”. This reading goes back to the seminal work of Von Wright in the early 1960’s and has returned in computer science in the 1990’s and in more abstract “dependency logics” today. We show how it differs from ceteris paribus as “all other things being normal”, which is used in contexts with preference defeaters. We provide a semantic analysis and several (...) completeness theorems. We show how our system links up with Von Wright’s work, and how it applies to game-theoretic solution concepts, to agenda setting in investigation, and to preference change. We finally consider its relation with infinitary modal logics. (shrink)

While specifications and verifications of concurrent systems employ Linear Temporal Logic , it is increasingly likely that logical consequence in image will be used in the description of computations and parallel reasoning. Our paper considers logical consequence in the standard image with temporal operations image and image . The prime result is an algorithm recognizing consecutions admissible in image, so we prove that image is decidable w.r.t. admissible inference rules. As a consequence we obtain algorithms verifying the validity of consecutions (...) in image and solving the satisfiability problem. We start by a simple reduction of logical consecutions of image to equivalent ones in the reduced normal form . Then we apply a semantic technique based on image-Kripke structures with formula definable subsets. This yields necessary and sufficient conditions for a consecution to be not admissible in image. These conditions lead to an algorithm which recognizes consecutions admissible in image by verifying the validity of consecutions in special finite Kripke structures of size square polynomial in reduced normal forms of the consecutions. As a consequence, this also solves the satisfiability problem for image. (shrink)

The semantical structures called T x W frames were introduced in (Thomason, 1984) for the Ockhamist temporal-modal language, $[Unrepresented Character]_{o}$ , which consists of the usual propositional language augmented with the Priorean operators P and F and with a possibility operator ◇. However, these structures are also suitable for interpreting an extended language, $[Unrepresented Character]_{so}$ , containing a further possibility operator $\lozenge^{s}$ which expresses synchronism among possibly incompatible histories and which can thus be thought of as a cross-history 'simultaneity' operator. (...) In the present paper we provide an infinite set of axioms in $[Unrepresented Character]_{so}$ , which is shown to be strongly complete for T x W-validity. Von Kutschera (1997) contains a finite axiomatization of T x W-validity which however makes use of the Gabbay Irreflexivity Rule (Gabbay, 1981). In order to avoid using this rule, the proof presented here develops a new technique to deal with reflexive maximal consistent sets in Henkin-style constructions. (shrink)

The title reflects my conviction that, viewed semantically,modal logic is fundamentally dialogical; this conviction is based on the key role played by the notion of bisimulation in modal model theory. But this dialogical conception of modal logic does not seem to apply to modal proof theory, which is notoriously messy. Nonetheless, by making use of ideas which trace back to Arthur Prior (notably the use of nominals, special proposition symbols which ‘name’ worlds) I will show how to lift the dialogical (...) conception to modal proof theory. I argue that this shift to hybrid logic has consequences for both modal and dialogical logic, and I discuss these in detail. (shrink)

Temporal logic is one of the many areas in which a possible world semantics is adopted. Prior's Ockhamist and Peircean semantics for branching-time, though, depart from the genuine Kripke semantics in that they involve a quantification over histories, which is a second-order quantification over sets of possible worlds. In the paper, variants of the original Prior's semantics will be considered and it will be shown that all of them can be viewed as first-order counterparts of the original semantics.

The logic of 'elsewhere,' i.e., of a sentence operator interpretable as attaching to a formula to yield a formula true at a point in a Kripke model just in case the first formula is true at all other points in the model, has been applied in settings in which the points in question represent spatial positions, as well as in the case in which they represent moments of time. This logic is applied here to the alethic modal case, in which (...) the points are thought of as possible worlds, with the suggestion that its deployment clarifies aspects of a position explored by John Divers under the name 'modal agnosticism.' In particular, it makes available a logic whose Halldén incompleteness explicitly registers the agnostic element of the position - its neutrality as between modal realism and modal anti-realism. (shrink)

One of the important extensions of PDL is PDL with intersection of programs. We devote this paper to its complete axiomatization.

The aim of this paper is to give new kinds of modal logics suitable for reasoning about regions in discrete spaces. We call them dynamic logics of the region-based theory of discrete spaces. These modal logics are linguistic restrictions of propositional dynamic logic with the global diamond E. Their formulas are equivalent to Boolean combinations of modal formulas like E(A ∧ ⟨α⟩ B) where A and B are Boolean terms and α is a relational term. Examining what we can say (...) about dynamic models when we use formulas to describe them, we successively address the axiomatization/completeness issue and the decidability/complexity issue of our dynamic logics of the region-based theory of discrete spaces. (shrink)

Negative definability ([18]) is an alternative way of defining classes of Kripke frames via a modal language, one that enables us, for instance, to define the class of irreflexive frames. Besides a list of closure conditions for negatively definable classes, the paper contains two main theorems. First, a characterization is given of negatively definable classes of (rooted) finite transitive Kripke frames and of such classes defined using both traditional (positive) and negative definitions. Second, we characterize the negatively definable classes of (...) rooted general frames. (shrink)

This paper presents a short survey of recent developments in stit theories, with an emphasis on combinations of stit and deontic logic, and those of stit and epistemic logic.

Combining logics has become a rapidly expanding enterprise that is inspired mainly by concerns about modularity and the wish to join together tailor made logical tools into more powerful but still manageable ones. A natural question is whether it offers anything new over and above existing standard languages. By analysing a number of applications where combined logics arise, we argue that combined logics are a potentially valuable tool in applied logic, and that endorsements of standard languages often miss the point. (...) Using the history of quantified modal logic as our main example, we also show that the use of combined structures and logics is a recurring theme in the analysis of existing logical systems. (shrink)

We give a Hilbert style axiomatization for the set of formulas in the temporal language with Until and Since which are valid over the real number flow of time. The axiomatization, which is orthodox in the sense of only having the usual temporal rules of inference, is complete with respect to single formulas.

For branching-time temporal logic based on an Ockhamist semantics, we explore a temporal language extended with two additional syntactic tools. For reference to the set of all possible futures at a moment of time we use syntactically designated restricted variables called fan-names. For reference to all possible futures alternative to the actual one we use a modification of a difference modality, localized to the set of all possible futures at the actual moment of time.We construct an axiomatic system for this (...) extended branching-time logic and prove its soundness and completeness with respect to bundle tree semantics. Finally, we show how our axiomatic system can be extended with a variety of important additional operators, such as Since and Until, a global difference operator, operators for undivided and divided histories, reference pointers, etc. (shrink)

Natural language provides motivation for studying modal backwards-looking operators such as “now”, “then” and “actually” that evaluate their argument formula at some previously considered point instead of the current one. This paper investigates the expressive power over models of both propositional and first-order basic modal language enriched with such operators. Having defined an appropriate notion of bisimulation for first-order modal logic, I show that backwards-looking operators increase its expressive power quite mildly, contrary to beliefs widespread among philosophers of language and (...) formal semanticists. That in turn presents a strong argument for the use of operator-based systems in the semantics of natural language, instead of systems with explicit quantification over worlds and times that have become a de-facto standard for such applications. The popularity of such explicit-quantification systems is shown to be based on the misinterpretation of a claim by Cresswell, which led many philosophers and linguists to assume that introducing “now” and “then” is expressively equivalent to explicitly quantifying over worlds and times. (shrink)

Modal logics for reasoning about social networks is currently an active field of research. There is still a gap, however, between the state of the art in logical formalisations of concepts related to social networks and the much more mature field of social network analysis. In this paper we take a step to bridge that gap. One of the key foundations of social network analysis is balance theory, which is used to analyse signed social networks where agents can have positive (...) or negative relationships. Certain combinations of positive and negative relationships are considered to be unbalanced, or unstable—in particular the occurrence of cycles with an odd number of negative relationships. Especially relatively short cycles with an odd number of negative relationships are thought to put pressure on the agents to change one or more of the involved relationships from negative to positive or the other way around. Most existing logics for reasoning about social networks are defined for unsigned networks. In this paper we develop a modal logic for reasoning about structural properties of signed social networks, and give a sound and complete Hilbert-style axiomatic system. Furthermore, we completely axiomatise classes of signed social networks that are balanced to a certain degree n, in the sense that there are no cycles of length up to n with an odd number of negative relationships. Finally, we completely axiomatise the class of all fully balanced complete signed social networks, i.e., networks where everyone is connected with everyone else. Axiomatic completeness is non-trivial because neither the balance properties, nor the dichotomy between positive and negative relations, are modally definable. The paper thus provides a logical basis for reasoning about signed social networks in general and balanced networks in particular. (shrink)

In an earlier paper by the author, Åqvist , I presented an approach to the logic of historical necessity, or inevitability, in the sense of a “two-dimensional” combination of tense and modal logic for worlds, or histories, with the same time order, known as T × W logic. Distinctive features of that approach were, apart from its two-dimensionality, its being based on discrete and finite time, and its use of so-called systematic frame constants in order to enable us to indicate (...) longitudes and latitudes of any points in the co-ordinate systems under consideration. This led us to study and axiomatize an infinite hierarchy HTWxy of two-dimensional modal tense logics with the characteristic operators for historical necessity and possibility added to the original basic vocabulary. The main purpose of the present paper is then twofold: to extend the logics HTWxy to the interesting branch of philosophical logic constituted by deontic logic as combined with tense logic; and to deal with a curious puzzle known as the so-called epistemic obligation paradox – a well known stumbling-block in this area of research in philosophical logic. We argue for a solution to both these problems, which appeals to a new infinite hierarchy DHTWxym of extensions of the HTWxy in the sense of logics combining dyadic deontic modalities with temporal ones such as those for historical necessity and other two-dimensional modalities. (shrink)

Trees with indistinguishability relations provide a semantics for a temporal language “composed by” the Peircean tense operators and the Ockhamist modal operator. In this paper, a finite axiomatization with a non standard rule for this language interpreted over bundled trees with indistinguishability relations is given. This axiomatization is proved to be sound and strongly complete.

ABSTRACT This paper presents the axioinatization—without the rule of irreflexivity—of the modal logic of inequality as well as a method for proving its completeness. This method uses the technics of the frame of subordination.

The semantical structures called T×W frames were introduced in (Thomason, 1984) for the Ockhamist temporal-modal language, ℒO, which consists of the usual propositional language augmented with the Priorean operators P and F and with a possibility operator ⋄. However, these structures are also suitable for interpreting an extended language, ℒSO, containing a further possibility operator ⋄s which expresses synchronism among possibly incompatible histories and which can thus be thought of as a cross-history ‘simultaneity’ operator. In the present paper we provide (...) an infinite set of axioms in ℒSO, which is shown to be strongly complete forT ×W-validity. Von Kutschera (1997) contains a finite axiomatization of T×W-validity which however makes use of the Gabbay Irreflexivity Rule (Gabbay, 1981). In order to avoid using this rule, the proof presented here develops a new technique to deal with reflexive maximal consistent sets in Henkin-style constructions. (shrink)

The questions od determinism, causality, and freedom have been the main philosophical problems debated since the beginning of temporal logic. The issue of the logical value of sentences about the future was stated by Aristotle in the famous tomorrow sea-battle passage. The question has inspired Łukasiewicz’s idea of many-valued logics and was a motive of A. N. Prior’s considerations about the logic of tenses. In the scheme of temporal logic there are different solutions to the problem. In the paper we (...) consider indeterministic temporal logic based on the idea of temporal worlds and the relation of accessibility between them. (shrink)

T × W logic is a combination of tense and modal logic for worlds or histories with the same time order. It is the basis for logics of causation, agency and conditionals, and therefore an important tool for philosophical logic. Semantically it has been defined, among others, by R. H. Thomason. Using an operator expressing truth in all worlds, first discussed by C. M. Di Maio and A. Zanardo, an axiomatization is given and its completeness proved via D. Gabbay’s irreflexivity (...) lemma. Given this lemma the proof is more or less straight forward. At the end an alternative axiomatization is sketched in which Di Maio’s and Zanardo’s operator is replaced by a version of “actually”. (shrink)

ABSTRACT We characterize those binary ramified frames for which propositional modal logic is as expressive as the corresponding first-order logic.