This volume seeks to further the use of formal methods in clarifying one of the central problems of philosophy: that of our free human agency and its place in our indeterministic world. It celebrates the important contributions made in this area by Nuel Belnap, American logician and philosopher. Philosophically, indeterminism and free action can seem far apart, but in Belnap’s work, they are intimately linked. This book explores their philosophical interconnectedness through a selection of original research papers that build forth (...) on Belnap’s logical and philosophical work. Some contributions take the form of critical discussions of Belnap's published work, some develop points made in his publications in new directions, and others provide additional insights on the topics of indeterminism and free action. In Nuel Belnap’s work on indeterminism and free action, three formal frameworks figure prominently: the simple branching histories framework known as "branching time;" its relativistic spatio-temporal extension, branching space-times; and the “seeing to it that” logic of agency. As those frameworks provide the formal background for the contributed papers, the volume introduction gives an overview of the current state of their development. It also introduces case-intensional first order logic, a general intensional logic offering resources for a first-order extension of the mentioned frameworks and a recent research focus of Belnap’s. The volume also contains an extended biographical interview with Nuel Belnap. (shrink)

This book offers a comprehensive treatment of the classical decision problem of mathematical logic and of the role of the classical decision problem in modern computer science. The text presents a revealing analysis of the natural order of decidable and undecidable cases and includes a number of simple proofs and exercises.

In this paper we present BTC, which is a complete logic for branchingtime whose modal operator quantifies over histories and whose temporal operators involve a restricted quantification over histories in a given possible choice. This is a technical novelty, since the operators of the usual logics for branching-time such as CTL express an unrestricted quantification over histories and moments. The value of the apparatus we introduce is connected to those logics of agency that are interpreted on branching-time, as for instance (...) Stit Logics. (shrink)

John MacFarlane explores how we might make sense of the idea that truth is relative. He provides new, satisfying accounts of parts of our thought and talk that have resisted traditional methods of analysis, including what we mean when we talk about what is tasty, what we know, what will happen, what might be the case, and what we ought to do.

The semantics of tense has received a great deal of attention in the contemporary linguistics, philosophy and logic literatures. This is probably due partly to a renewed appreciation for the fact that issues involving tense touch on certain issues of philosophical importance (viz., determinism, causality, and the nature of events, of time and of change). It may also be due partly to neglect. Tense was noticeably omitted from the theories of meaning advanced in previous generations. In the writings of both (...) Russell and Frege there is the suggestion that tense would be absent altogether from an ideal or scientifically adequate language. (Tense was not the only blemish of natural language to be removed, of course, but tense is a more serious omission than, say, pronouns because it is present in every sentence of the language.) Finally, in recent years there has been a greater recognition of the important role that all of the so-called “indexical” expressions must play in an explanation of mental states and human behavior. Tense is no exception. Knowing that our friend died is cause for mourning, knowing that he dies is just another confirmation of a familiar syllogism. (shrink)

"This book develops a rigorous theory of indeterminism as a local and modal concept. Its crucial insight is that our world contains events or processes with alternative, really possible outcomes. The theory aims at clarifying what this assumption involves, and it does it in two ways. First, it provides a mathematically rigorous framework for local and modal indeterminism. Second, we support that theory by spelling out the philosophically relevant consequences of this formulation and by showing its fruitful applications in metaphysics. (...) To this end, we offer a formal analysis of modal correlations and of causation, which is applicable in indeterministic and non-local contexts as well. We also propose a rigorous theory of objective single-case probabilities, intended to represent degrees of possibility. In a third step, we link our theory to current physics, investigating how local and modal indeterminism relates to issues in the foundations of physics, in particular, quantum non-locality and spatio-temporal relativity. The book also ventures into the philosophy of time, showing how the theory's resources can be used to explicate the dynamic concept of the past, present, and future based on local indeterminism"--. (shrink)

Temporal Logic: From Ancient Ideas to Artificial Intelligence deals with the history of temporal logic as well as the crucial systematic questions within the field. The book studies the rich contributions from ancient and medieval philosophy up to the downfall of temporal logic in the Renaissance. The modern rediscovery of the subject, which is especially due to the work of A. N. Prior, is described, leading into a thorough discussion of the use of temporal logic in computer science and the (...) understanding of natural language. Temporal Logic: From Ancient Ideas to Artificial Intelligence thus interweaves linguistic, philosophical and computational aspects into an informative and inspiring whole. (shrink)

This monograph is designed to provide an introduction to the principal areas of tense logic. Many of the developments in this ever-growing field have been intentionally excluded to fulfill this aim. Length also dictated a choice between the alternative notations of A. N. Prior and Nicholas Rescher - two pioneers of the subject. I choose Prior's because of the syntactical parallels with the language it symbolizes and its close ties with other branches of logi cal theory, especially modal logic. The (...) first chapter presents a wider view of the material than later chapters. Several lines of development are consequently not followed through the remainder of the book, most notably metric systems. Although it is import ant to recognize that the unadorned Prior-symbolism can be enriched in vari ous ways it is an advanced subject as to how to actually carry off these enrichments. Readers desiring more information are referred to the appropri ate literature. Specialists will notice that only the first of several quantifi cational versions of tense logic is proven complete in the final chapter. Again constraints of space are partly to blame. The proof for the 'star' systems is wildly complex and at the time of this writing is not yet ready for publi cation. (shrink)

In the tree-like representation of Time, two histories are undivided at a moment t whenever they share a common moment in the future of t. In the present paper, it will first be proved that Ockhamist and Peircean branching-time logics are unable to express some important sentences in which the notion of undividedness is involved. Then, a new semantics for branching-time logic will be presented. The new semantics is based on trees endowed with an indistinguishability function, a generalization of the (...) notion of undividedness. It will be shown that Ockhamist and Peircean semantics can be viewed as limit cases of the semantics developed in this paper. (shrink)

In several semantics for branching-time logic, the evaluation rules involve a quantification over the set of all histories in a given tree-like structure T. These semantics are often generalized by replacing these quantifications by quantifications over a bundle in T, that is, over a set of histories fulfilling suitable closure properties. According to this generalization, the basic semantical structures are pairs 〈T, B〉 in which B is a bundle in T.The problem of the definability of the class of complete bundled (...) trees, in a given class G, concerns the existence of a set Γ of formulas such that, for every bundled tree 〈T, B〉 in G, Γ is true in 〈T, B〉 if and only if B is the set of all histories in T. In Ockhamist branching-time logic, sets Γ corresponding to particular classes G have been found. It will be proved that Γ does not exist if G is the class of all bundled trees. (shrink)

This paper deals with structures ${\langle{\bf T}, I\rangle}$ in which T is a tree and I is a function assigning each moment a partition of the set of histories passing through it. The function I is called indistinguishability and generalizes the notion of undividedness. Belnap’s choices are particular indistinguishability functions. Structures ${\langle{\bf T}, I\rangle}$ provide a semantics for a language ${\mathcal{L}}$ with tense and modal operators. The first part of the paper investigates the set-theoretical properties of the set of indistinguishability (...) classes, which has a tree structure. The significant relations between this tree and T are established within a general theory of trees. The aim of second part is testing the expressive power of the language ${\mathcal{L}}$ . The natural environment for this kind of investigations is Belnap’s seeing to it that (stit). It will be proved that the hybrid extension of ${\mathcal{L}}$ (with a simultaneity operator) is suitable for expressing stit concepts in a purely temporal language. (shrink)

In Ockhamist branching-time logic [Prior 67], formulas are meant to be evaluated on a specified branch, or history, passing through the moment at hand. The linguistic counterpart of the manifoldness of future is a possibility operator which is read as `at some branch, or history (passing through the moment at hand)'. Both the bundled-trees semantics [Burgess 79] and the $\langle moment, history\rangle$ semantics [Thomason 84] for the possibility operator involve a quantification over sets of moments. The Ockhamist frames are (3-modal) (...) Kripke structures in which this second-order quantification is represented by a first-order quantification. The aim of the present paper is to investigate the notions of modal definability, validity, and axiomatizability concerning 3-modal frames which can be viewed as generalizations of Ockhamist frames. (shrink)

It is known that even seemingly small fragments of the first-order temporal logic over the natural numbers are not recursively enumerable. In this paper we show that the monodic fragment is an exception by constructing its finite Hilbert-style axiomatization. We also show that the monodic fragment with equality is not recursively axiomatizable.

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)

One of time's most puzzling aspects concerns its ontological status: on the one hand, it is a subjective and relative notion, based on our conscious experience of successive events; yet, on the other hand, our civilization and technology are based on the understanding that something like objective, absolute Time exists. Some philosophers have taken this paradox so far as to conclude that time is unreal; others, accepting the existence of absolute time, have engaged in heated debates regarding its structure, be (...) it linear or circular, bounded or unbounded, dense or discrete. (shrink)

In the 4th century BC, the Greek philosopher Diodoros Chronos gave a temporal definition of necessity. Because it connects modality and temporality, this definition is of interest to philosophers working within branching time or branching space-time models. This definition of necessity can be formalized and treated within a logical framework. We give a survey of the several known modal and temporal logics of abstract space-time structures based on the real numbers and the integers, considering three different accessibility relations between spatio-temporal (...) points. (shrink)

In this paper we develop a novel propositional semantics based on the framework of branching time. The basic idea is to replace the moment-history pairs employed as parameters of truth in the standard Ockhamist semantics by pairs consisting of a moment and a consistent, downward closed set of so-called transitions. Whereas histories represent complete possible courses of events, sets of transitions can represent incomplete parts thereof as well. Each transition captures one of the alternative immediate future possibilities open at a (...) branching point. The transition semantics exploits the structural resources a branching time structure has to offer and provides a fine-grained picture of the interrelation of modality and time. In addition to temporal and modal operators, a so-called stability operator becomes interpretable as a universal quantifier over the possible future extensions of a given transition set. The stability operator allows us to specify how and how far time has to unfold for the truth value of a sentence at a moment to become settled and enables a perspicuous treatment of future contingents. We show that the semantics developed along those lines generalizes and extends extant approaches: both Peirceanism and Ockhamism can be viewed as limiting cases of the transition approach that build on restricted resources only, and on both accounts, stability collapses into truth. (shrink)

The transition semantics presented in Rumberg (J Log Lang Inf 25(1):77–108, 2016a) constitutes a fine-grained framework for modeling the interrelation of modality and time in branching time structures. In that framework, sentences of the transition language L_t are evaluated on transition structures at pairs consisting of a moment and a set of transitions. In this paper, we provide a class of first-order definable Kripke structures that preserves L_t-validity w.r.t. transition structures. As a consequence, for a certain fragment of L_t, validity (...) w.r.t. transition structures turns out to be axiomatizable. The result is then extended to the entire language L_t by means of a quite natural ‘Henkin move’, i.e. by relaxing the notion of validity to bundled structures. (shrink)

Neither question (1) nor question (2) posed on page 446 have been adequately answered in this paper. Regarding (1) we have merely given functor maps onto the object languages of physical theories and regarding (2) we have merely described the algebraic structure of observables. A more satisfactory treatment will most likely involve (1) a generalization to algebraic categories, universal algebra and model theory in such a way as to capture the full inference structure of (perhaps van Fraassen's modal) quantum logic, (...) and (2) the introduction of the category of differentiable manifolds in order to capture the full symplectic structure of (perhaps Chernoff-Marsden's) Hamiltonian dynamics. (See van Fraassen [4] and Chernoff-Marsden [5] in Other References.)Finally, the intriguing suggestion of Finkelstein that “category theory is to metaphysics what group theory is to physics” deserves serious consideration. Indeed, although the theme has not been touched on explicitly in this paper it was central in motivating the project initially. However, it is more properly to be developed in a context external to a symposium on quantum logic. (shrink)

It is shown that the decision problem for the temporal logic with until and since connectives over real-numbers time is PSPACE-complete. This is the most practically useful dense time temporal logic.

We present an axiomatisation for the first-order temporal logic with connectives Until and Since over the class of all linear flows of time. Completeness of the axiom system is proved.We also add a few axioms to find a sound and complete axiomatisation for the first order temporal logic of Until and Since over rational numbers time.

This paper deals with the historical and philosophical background of the introduction of the notion of branching time in philosophical logic as it is revealed in the hitherto unpublished mail-correspondence between Saul Kripke and A.N. Prior in the late 1950s. The paper reveals that the idea was first suggested by Saul Kripke in a letter to A.N. Prior, dated September 3, 1958, and it is shown how the elaboration of the idea in the course of the correspondence was intimately intervowen (...) with considerations of how to represent indeterminism and of the adequacy of tensed logic in light of special relativity. The correspondence underpins the point that Prior's later development of branching time may be understood as a crucial part of his attempt at the formulating a conceptual framework integrating basic human notions of time and free choice. (shrink)

The logical theory of branching space-times, which provides a relativistic framework for studying objective indeterminism, remains mostly disconnected from discussions of space-time theories in philosophy of physics. Earman has criticized the branching approach and suggested “pruning some branches from branching space-time.” This article identifies the different—order-theoretic versus topological—perspective of both discussions as a reason for certain misunderstandings and tries to remove them. Most important, we give a novel, topological criterion of modal consistency that usefully generalizes an earlier criterion, and we (...) introduce a differential-geometrical version of branching space-times as a non-Hausdorff (generalized) manifold. (shrink)

ABSTRACT The question of axiomatizability of first-order temporal logics is studied w.r.t. different semantics and several restrictions on the language. The validity problem for logics admitting flexible interpretations of the predicate symbols or allowing at least binary predicate symbols is shown to be ?1 1-complete. In contrast, it is decidable for temporal logics with rigid monadic predicate symbols but without function symbols and identity.

This is a thorough treatment of first-order modal logic. The book covers such issues as quantification, equality (including a treatment of Frege's morning star/evening star puzzle), the notion of existence, non-rigid constants and function symbols, predicate abstraction, the distinction between nonexistence and nondesignation, and definite descriptions, borrowing from both Fregean and Russellian paradigms.

Much previous work in artificial intelligence has neglected representing time in all its complexity. In particular, it has neglected continuous change and the indeterminacy of the future. To rectify this, I have developed a first‐order temporal logic, in which it is possible to name and prove things about facts, events, plans, and world histories. In particular, the logic provides analyses of causality, continuous change in quantities, the persistence of facts (the frame problem), and the relationship between tasks and actions. It (...) may be possible to implement a temporal‐inference machine based on this logic, which keeps track of several “maps” of a time line, one per possible history. (shrink)

This paper investigates modular combinations of temporal logic systems. Four combination methods are described and studied with respect to the transfer of logical properties from the component one-dimensional temporal logics to the resulting combined two-dimensional temporal logic. Three basic logical properties are analyzed, namely soundness, completeness, and decidability. Each combination method comprises three submethods that combine the languages, the inference systems, and the semantics of two one-dimensional temporal logic systems, generating families of two-dimensional temporal languages with varying expressivity and varying (...) degrees of transfer of logical properties. The temporalization method and the independent combination method are shown to transfer all three basic logical properties. The method of full join of logic systems generates a considerably more expressive language but fails to transfer completeness and decidability in several cases. So a weaker method of restricted join is proposed and shown to transfer all three basic logical properties. (shrink)

If it is not now determined whether there will be a sea battle tomorrow, can an assertion that there will be one be true? The problem has persisted because there are compelling arguments on both sides. If there are objectively possible futures which would make the prediction true and others which would make it false, symmetry considerations seem to forbid counting it either true or false. Yet if we think about how we would assess the prediction tomorrow, when a sea (...) battle is raging (or not), it seems we must assign the utterance a definite truth-value. I argue that both arguments must be given their due, and that this requires relativizing utterance-truth to a context of assessment. I show how this relativization can be handled in a rigorous formal semantics, and I argue that we can make coherent sense of assertion without assuming that utterances have their truth-values absolutely. (shrink)

I present a variant of with time, called, interpreted in standard Kripke semantics. On the syntactic level, is nothing but the extension of atemporal individual by: the future tense and past tense operators, and the operator of group agency for the grand coalition. A sound and complete axiomatisation for is given. Moreover, it is shown that supports reasoning about interesting normative concepts such as the concepts of achievement obligation and commitment.

As a remedy for the bad computational behaviour of first-order temporal logic (FOTL), it has recently been proposed to restrict the application of temporal operators to formulas with at most one free variable thereby obtaining so-called monodic fragments of FOTL. In this paper, we are concerned with constructing tableau algorithms for monodic fragments based on decidable fragments of first-order logic like the two-variable fragment or the guarded fragment. We present a general framework that shows how existing decision procedures for first-order (...) fragments can be used for constructing a tableau algorithm for the corresponding monodic fragment of FOTL. Some example instantiations of the framework are presented. (shrink)

In this paper, we introduce a new fragment of the first-order temporal language, called the monodic fragment, in which all formulas beginning with a temporal operator have at most one free variable. We show that the satisfiability problem for monodic formulas in various linear time structures can be reduced to the satisfiability problem for a certain fragment of classical first-order logic. This reduction is then used to single out a number of decidable fragments of first-order temporal logics and of two-sorted (...) first-order logics in which one sort is intended for temporal reasoning. Besides standard first-order time structures, we consider also those that have only finite first-order domains, and extend the results mentioned above to temporal logics of finite domains. We prove decidability in three different ways: using decidability of monadic second-order logic over the intended flows of time, by an explicit analysis of structures with natural numbers time, and by a composition method that builds a model from pieces in finitely many steps. (shrink)

The theory of trees with additional unary predicates and quantification over nodes and branches embraces a rich branching time logic. This theory was reduced in the companion paper to the first-order theory of binary, bounded, well-founded trees with additional unary predicates. Here we prove the decidability of the latter theory.