Conceived by Johan van Benthem and Yde Venema, arrow logic started as an attempt to give a general account of the logic of transitions. The generality of the approach provided a wide application area ranging from philosophy to computer science. The book gives a comprehensive survey of logical research within and around arrow logic. Since the natural operations on transitions include composition, inverse and identity, their logic, arrow logic can be studied from (...) two different perspectives, and by two (complementary) methodologies: modal logic and the algebra of relations. Some of the results in this volume can be interpreted as price tags. They show what the prices of desirable properties, such as decidability, (finite) axiomatisability, Craig interpolation property, Beth definability etc. are in terms of semantic properties of the logic. The research program of arrow logic has considerably broadened in the last couple of years and recently also covers the enterprise to explore the border between decidable and undecidable versions of other applied logics. The content of this volume reflects this broadening. The editors included a number of papers which are in the spirit of this generalised research program. (shrink)

We consider arrow logics (i.e., propositional multi-modal logics having three -- a dyadic, a monadic, and a constant -- modal operators) augmented with various kinds of infinite counting modalities, such as 'much more', 'of good quantity', 'many times'. It is shown that the addition of these modal operators to weakly associative arrow logic results in finitely axiomatizable and decidable logics, which fail to have the finite base property.

In this paper, we study indiscernibility relations and complementarity relations in hyper arrow structures. A first-order characterization of indiscernibility and complementarity is obtained through a duality result between hyper arrow structures and certain structures of relational type characterized by first-order conditions. A modal analysis of indiscernibility and complementarity is performed through a modal logic which modalities correspond to indiscernibility relations and complementarity relations in hyper arrow structures.

We compare fork arrow logic, an extension of arrow logic, and its natural first-order counterpart (the correspondence language) and show that both have the same expressive power. Arrow logic is a modal logic for reasoning about arrow structures, its expressive power is limited to a bounded fragment of first-order logic. Fork arrow logic is obtained by adding to arrow logic the fork modality (related to parallelism and synchronization). (...) As a result, fork arrow logic attains the expressive power of its first-order correspondence language, so both can express the same input–output behavior of processes. (shrink)

We compare fork arrow logic, an extension of arrow logic, and its natural first-order counterpart (the correspondence language) and show that both have the same expressive power. Arrow logic is a modal logic for reasoning about arrow structures, its expressive power is limited to a bounded fragment of first-order logic. Fork arrow logic is obtained by adding to arrow logic the fork modality (related to parallelism and synchronization). (...) As a result, fork arrow logic attains the expressive power of its first-order correspondence language, so both can express the same input-output behavior of processes. (shrink)

In this paper we show that the class of fork squares has a complete orthodox axiomatization in fork arrow logic (FAL). This result may be seen as an orthodox counterpart of Venema's non-orthodox axiomatization for the class of squares in arrow logic. FAL is the modal logic of fork algebras (FAs) just as arrow logic is the modal logic of relation algebras (RAs). FAs extend RAs by a binary fork operator and are (...) axiomatized by adding three equations to RAs equational axiomatization. A proper FA is an algebra of relations where the fork is induced by an injective operation coding pair formation. In contrast to RAs, FAs are representable by proper ones and their equational theory has the expressive power of full first-order logic. A square semantics (the set of arrows is U×U for some set U) for arrow logic was defined by Y. Venema. Due to the negative results about the finite axiomatizability of representable RAs, Venema provided a non-orthodox finite axiomatization for arrow logic by adding a new rule governing the applications of a difference operator. We address here the question of extending the type of relational structures to define orthodox axiomatizations for the class of squares. Given the connections between this problem and the finitization problem addressed by I. Németi, we suspect that this cannot be done by using only logical operations. The modal version of the FA equations provides an orthodox axiomatization for FAL which is complete in view of the representability of FAs. Here we review this result and carry it further to prove that this orthodox axiomatization for FAL also axiomatizes the class of fork squares. (shrink)

This paper is devoted to the complete axiomatization of dynamic extensions of arrow logic based on a restriction of propositional dynamic logic with intersection. Our deductive systems contain an unorthodox inference rule: the inference rule of intersection. The proof of the completeness of our deductive systems uses the technique of the canonical model.

In this paper we show that the class of fork squares has a complete orthodox axiomatization in fork arrow logic (FAL). This result may be seen as an orthodox counterpart of Venema's non-orthodox axiomatization for the class of squares in arrow logic. FAL is the modal logic of fork algebras (FAs) just as arrow logic is the modal logic of relation algebras (RAs). FAs extend RAs by a binary fork operator and are (...) axiomatized by adding three equations to RAs equational axiomatization. A proper FA is an algebra of relations where the fork is induced by an injective operation coding pair formation. In contrast to RAs, FAs are representable by proper ones and their equational theory has the expressive power of full first-order logic. A square semantics (the set of arrows is ᵎ x ᵎ for some set ᵎ) for arrow logic was defined by Y. Venema. Due to the negative results about the finite axiomatizability of representable RAs, Venema provided a non-orthodox finite axiomatization for arrow logic by adding a new rule governing the applications of a difference operator. We address here the question of extending the type of relational structures to define orthodox axiomatizations for the class of squares. Given the connections between this problem and the finitization problem addressed by I. Németi, we suspect that this cannot be done by using only logical operations. The modal version of the FA equations provides an orthodox axiomatization for FAL which is complete in view of the representability of FAs. Here we review this result and carry it further to prove that this orthodox axiomatization for FAL also axiomatizes the class of fork squares. (shrink)

ABSTRACT The notion of n-dimensional arrow structure is introduced, which for n = 2 coincides with the notion of directed multi-graph. In part I of the paper several first-order and modal languages connected with arrow structures are studied and their expressive power is compared. Part II is devoted to the axiomatization of some arrow logics. At the end some further perspectives of ?arrow approach? are discussed.

Artificial agents, which are embedded in a virtual world, need to interpret a sequence of commands given to them adequately, considering the temporal structure for each command. In this paper, we start with the semantics of natural language and classify the temporal structures of various eventualities into such aspectual classes as action, process, and event. In order to formalize these temporal structures, we adopt Arrow Logic. This logic specifies the domain for the valuation of a sentence as (...) an arrow. We can connect, or give order to, arrows by defining inter-arrow operations, and can give different views for sentences. Thereafter we formalize the rules of aspectual shifts in situated inference, in the style of a logic programming language. Thus, we not only describe the static representation of temporal features, but also show the dynamic process to deduce how each eventuality is viewed. The rules are applied to the information flow through the sequence of commands; therefore, we consider how the temporal structure of a command affects the succeeding commands. (shrink)

The complexity of the satisfiability problems of various arrow logics and cylindric modal logics is determined. As is well known, relativising these logics makes them decidable. There are several parameters that can be set in such a relativisation. We focus on the following three: the number of variables involved, the similarity type and the kind of relativised models considered. The complexity analysis shows the importance and relevance of these parameters.

We present Arrow Update Logic, a theory of epistemic access elimination that can be used to reason about multi-agent belief change. While the belief-changing of Arrow Update Logic can be transformed into equivalent belief-changing from the popular Dynamic Epistemic Logic approach, we prove that arrow updates are sometimes exponentially more succinct than action models. Further, since many examples of belief change are naturally thought of from Arrow Update Logicrelativized” common knowledge familiar from the (...) Dynamic Epistemic Logic literature. (shrink)

Barteld Kooi and Bryan Renne (2011). Generalized Arrow Update Logic. In K.R. Apt (editor). Theoretical Aspects of Rationality and Knowledge, Proceedings of the Thirteenth Conference (TARK 2011), pp. 205-211.

This paper is a critique of Kenneth Arrow's thesis concerning the logical impossibility of a constitution. I argue that one of the premises of Arrow's proof, that of the transitivity of indifference, is untenable. Several concepts of preference are introduced and counter-instances are offered to the transitivity of indifference defined along the standard lines in terms of these concepts. Alternate analyses of indifference in terms of preference are considered, and it is shown that these do not serve (...) class='Hi'>Arrow's purposes either. Finally, it is argued that in the single special case in which indifference could plausibly be held to be transitive, Arrow's thesis is innocuous. (shrink)

Normative arrow update logic (NAUL) is a logic that combines normative temporal logic (NTL) and arrow update logic (AUL). In NAUL, norms are interpreted as arrow updates on labeled transition systems with a CTL-like logic. We show that the satisfiability problem of NAUL is decidable with a tableau method and it is in EXPSPACE.

In response to recent work on the aggregation of individual judgments on logically connected propositions into collective judgments, it is often asked whether judgment aggregation is a special case of Arrowian preference aggregation. We argue for the converse claim. After proving two impossibility theorems on judgment aggregation (using "systematicity" and "independence" conditions, respectively), we construct an embedding of preference aggregation into judgment aggregation and prove Arrow’s theorem (stated for strict preferences) as a corollary of our second result. Although we (...) thereby provide a new proof of Arrow’s theorem, our main aim is to identify the analogue of Arrow’s theorem in judgment aggregation, to clarify the relation between judgment and preference aggregation, and to illustrate the generality of the judgment aggregation model. JEL Classi…cation: D70, D71.. (shrink)

In his classic monograph, Social Choice and Individual Values, Arrow introduced the notion of a decisive coalition of voters as part of his mathematical framework for social choice theory. The subsequent literature on Arrow’s Impossibility Theorem has shown the importance for social choice theory of reasoning about coalitions of voters with different grades of decisiveness. The goal of this paper is a fine-grained analysis of reasoning about decisive coalitions, formalizing how the concept of a decisive coalition gives rise (...) to a social choice theoretic language and logic all of its own. We show that given Arrow’s axioms of the Independence of Irrelevant Alternatives and Universal Domain, rationality postulates for social preference correspond to strong axioms about decisive coalitions. We demonstrate this correspondence with results of a kind familiar in economics—representation theorems—as well as results of a kind coming from mathematical logic—completeness theorems. We present a complete logic for reasoning about decisive coalitions, along with formal proofs of Arrow’s and Wilson’s theorems. In addition, we prove the correctness of an algorithm for calculating, given any social rationality postulate of a certain form in the language of binary preference, the corresponding axiom in the language of decisive coalitions. These results suggest for social choice theory new perspectives and tools from logic. (shrink)

Riker (1982) famously argued that Arrow’s impossibility theorem undermined the logical foundations of “populism”, the view that in a democracy, laws and policies ought to express “the will of the people”. In response, his critics have questioned the use of Arrow’s theorem on the grounds that not all configurations of preferences are likely to occur in practice; the critics allege, in particular, that majority preference cycles, whose possibility the theorem exploits, rarely happen. In this essay, I argue that (...) the critics’ rejoinder to Riker misses the mark even if its factual claim about preferences is correct: Arrow’s theorem and related results threaten the populist’s principle of democratic legitimacy even if majority preference cycles never occur. In this particular context, the assumption of an unrestricted domain is justified irrespective of the preferences citizens are likely to have. (shrink)

Arrow’s axiomatic foundation of social choice theory can be understood as an application of Tarski’s methodology of the deductive sciences—which is closely related to the latter’s foundational contribution to model theory. In this note we show in a model-theoretic framework how Arrow’s use of von Neumann and Morgenstern’s concept of winning coalitions allows to exploit the algebraic structures involved in preference aggregation; this approach entails an alternative indirect ultrafilter proof for Arrow’s dictatorship result. This link also connects (...) Arrow’s seminal result to key developments and concepts in the history of model theory, notably ultraproducts and preservation results. (shrink)

All the attempts to find the justification of the privileged evolution of phenomena exclusively in the external world need to refer to the inescapable fact that we are living in such an asymmetric universe. This leads us to look for the origin of the “arrow of time” in the relationship between the subject and the world. The anthropic argument shows that the arrow of time is the condition of the possibility of emergence and maintenance of life in the (...) universe. Moreover, according to Bohr’s, Poincaré’s and Watanabe’s analysis, this agreement between the earlier-later direction of entropy increase and the past-future direction of life is the very condition of the possibility for meaningful action, representation and creation. Beyond this relationship of logical necessity between the meaning process and the arrow of time the question of their possible physical connection is explored. To answer affirmatively to this question, the meaning process is modelled as an evolving tree-like structure, called “Semantic Time”, where thermodynamic irreversibility can be shown. (shrink)

Hardy and Unruh constructed a family of non-maximally entangled states of pairs of particles giving rise to correlations that cannot be accounted for with a local hidden-variable theory. Rather than pointing to violations of some Bell inequality, however, they pointed to apparent clashes with the basic rules of logic. Specifically, they constructed these states and the associated measurement settings in such a way that the outcomes satisfy some conditionals but not an additional one entailed by them. Quantum mechanics avoids (...) the broken ‘if …then …’ arrows in such Hardy–Unruh chains, as we call them, because it cannot simultaneously assign truth values to all conditionals involved. Measurements to determine the truth value of some preclude measurements to determine the truth value of others. Hardy–Unruh chains thus nicely illustrate quantum contextuality: which variables do and do not obtain definite values depends on what measurements we decide to perform. Using a framework inspired by Bub and Pitowsky and developed in our book Understanding Quantum Raffles (co-authored with Michael E. Cuffaro), we construct and analyze Hardy–Unruh chains in terms of fictitious bananas mimicking the behavior of spin-1/2 particles. (shrink)

Applying Weglorz' mode s of set theory without the axiom of choice, we investigate Arrow-type social we fare functions for infinite societies with restricted coalition algebras. We show that there is a reasonable, nondictatorial social welfare function satisfying “finite discrimination”, if and only if in Weglorz' mode there is a free ultrafilter on a set representing the individuals.

Metalogic is an open-ended cognitive, formal methodology pertaining to semantics and information processing. The language that mathematizes metalogic is known as metalanguage and deals with metafunctions purely by extension on patterns. A metalogical process involves an effective enrichment in knowledge as logical statements, and, since human cognition is an inherently logic–based representation of knowledge, a metalogical process will always be aimed at developing the scope of cognition by exploring possible cognitive implications reflected on successive levels of abstraction. Indeed, it (...) is basically impracticable to maintain logic–and–metalogic without paying heed to cognitive theorizing. For it is cognitively irrelevant whether possible conclusions are deduced from some premises before the premises are determined to be true or whether the premises themselves are determined to be true first and, then, the conclusions are deduced from them. In this paper we consider the term metalogic as inherently embodied under the framework referred to as cognitive science and mathematics. We propose a metalogical interpretation of Arrow’s impossibility theorem and, to that end, choice theory is understood as a mental course of action dealing with logic and metalogic issues, in which a possible mathematical approach to model a mental course of action is adopted as a systematic operating method. Nevertheless, if we look closely at the core of Arrow’s impossibility theorem in terms of metalogic, a second fundamental contribution to this framework is represented by the Nash equilibrium. As a result of the foregoing, therefore, we prove the metalogical equivalence between Arrow’s impossibility theorem and the existence of the Nash equilibrium. More specifically, Arrow’s requirements correspond to the Nash equilibrium for finite mixed strategies with no symmetry conditions. To demonstrate this proof, we first verify that Arrow’s set and Nash’s set are isomorphic to each other, both sets being under stated conditions of non–symmetry. Then, the proof is completed by virtue of category theory. Indeed, the two sets are categories that correspond biuniquely to one another and, thus, it is possible to define a covariant functor that preserves their mutual structures. According to this, we show the proof–dedicated metalanguage as a precursor to a special equivalence theorem. (shrink)

In this paper I present a range of substructural logics for a conditional connective ↦. This connective was original introduced semantically via restriction on the ternary accessibility relation R for a relevant conditional. I give sound and complete proof systems for a number of variations of this semantic definition. The completeness result in this paper proceeds by step-by-step improvements of models, rather than by the one-step canonical model method. This gradual technique allows for the additional control, lacking in the canonical (...) model method, that is required. (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.

Amartya Sen has recently urged that political philosophers pay attention to social choice theory in their deliberations about justice. However, despite its merits, social choice theory is not standardly part of undergraduate political philosophy. One difficulty is that it involves symbolic logic and difficult concepts. We can reduce this challenge by making the material no harder than it needs to be. I consider the standard proof of Arrow’s Theorem, a seminal result. Kenneth Arrow does not explicate the (...) role of the irrelevance of independent alternatives. Sen and Wulf Gaertner have offered clarifications, but I shall elucidate the full role. (shrink)

In this paper, I investigate the relationship between preference and judgment aggregation, using the notion of ranking judgment introduced in List and Pettit. Ranking judgments were introduced in order to state the logical connections between the impossibility theorem of aggregating sets of judgments and Arrow’s theorem. I present a proof of the theorem concerning ranking judgments as a corollary of Arrow’s theorem, extending the translation between preferences and judgments defined in List and Pettit to the conditions on the (...) aggregation procedure. (shrink)

Since the nineteenth century, the problem of the arrow of time has been traditionally analyzed in terms of entropy by relating the direction past-to-future to the gradient of the entropy function of the universe. In this paper, we reject this traditional perspective and argue for a global and non-entropic approach to the problem, according to which the arrow of time can be defined in terms of the geometrical properties of spacetime. In particular, we show how the global non-entropic (...) arrow can be transferred to the local level, where it takes the form of a non-spacelike local energy flow that provides the criterion for breaking the symmetry resulting from time-reversal invariant local laws. (shrink)

It is shown how the temporal-modal system of events TM (axiomatized in Appendix) allows for the avoidance of the logical determinism without the rejection of the principle of bivalence. The point is that the temporal and the modal parts of TM are so inter-related that modalities are in-the-real-world-inherent modalities independently of whether they concern actual or only possible events. Though formulated in a tenseless language, whose interpretation does not require the assumption of tense facts at the basic level of reality, (...) TM implies an objective, observer-independent difference between tenses based only on the way in which modalities are distributed along the time continuum. The conclusion is that the arrow of time is an intra-model characteristic of any model of TM that describes the non-deterministic real world up to a certain point of its history, while the flow of time is an inter-model characteristic of the continuous transition between these models. (shrink)

We explore the better known paradoxes of Zeno including modern variants based on infinite processes, from the point of view of standard, classical analysis, from which there is still much to learn (especially concerning the paradox of division), and then from the viewpoints of non-standard and non-classical analysis (the logic of the latter being intuitionist).The standard, classical or Cantorian notion of the continuum, modeled on the real number line, is well known, as is the definition of motion as the (...) time derivative of distance (we are not concerned with position and motion in more than one dimension, since Zeno wasn't). The real number line consists of its points, the distance between distinct points being positive and finite. The standard, classical derivative relies on the classical notion of limit, which does not use infinitesimals. (shrink)

Zeno’s arrow does not move “in the now” (Phys. VI 8, 239b2) or, equivalently, “in the place it is” (DK 29 B 4). Zeno concludes from this that the arrow does not move at all. In Aristotle (ibid. 9, 239b5–9, 31–33), Zeno’s argument takes the form of an invalid inference from instants to periods of time. Insofar as it fails to bring out an inconsistency in Aristotle’s account of motion, the paradox is thus eliminated. That instantaneous motion is (...) a contradiction in terms belongs to the common ground Aristotle shares with Zeno. That’s why information concerning Zeno’s relevant argument must be sought elsewhere (see section 3). Aristotle’s discussion of the Arrow pertains to the conclusions drawn from the denial of instantaneous motion. But the argument he refutes is of his own making, or so I will argue (section 2). In particular, Aristotle fails to address the presentist commitment adumbrated in his account, which would leave nothing beyond the denial of instantaneous motion for Zeno to prove. Presentism is no option in Phys. VI where a tenseless account of time and motion is offered. I will argue that Aristotle’s account of the tenses in De interpretatione is prone to Zeno’s argument if the present is conceived as an instant – which it arguably is not (section 4). (shrink)

This paper examines the problem of founding irreversibility on reversible equations of motion from the point of view of the Brussels school's recent developments in the foundations of quantum statistical mechanics. A detailed critique of both their 'subdynamics' and 'transformation' theory is given. It is argued that the subdynamics approach involves a generalized form of 'coarse-graining' description, whereas, transformation theory cannot lead to truly irreversible processes pointing to a preferred direction of time. It is concluded that the Brussels school's conception (...) of microscopic temporal irreversibility, as such, is tacitly assumed at the macroscopic level. Finally a logical argument is provided which shows, independently of the mathematical formalism of the theory concerned, that statistical reasoning alone is not sufficient to explain the arrow of time. (shrink)

In this paper we will consider the existing notions of bilateralism in the context of proof-theoretic semantics and propose, based on our understanding of bilateralism, an extension to logical multilateralism. This approach differs from what has been proposed under this name before in that we do not consider multiple speech acts as the core of such a theory but rather multiple consequence relations. We will argue that for this aim the most beneficial proof-theoretical realization is to use sequent calculi with (...) multiple sequent arrows satisfying some specific conditions, which we will lay out in this paper. We will unfold our ideas with the help of a case study in logical tetralateralism and present an extension of Almukdad and Nelson’s propositional constructive four-valued logic by unary operations of meaningfulness and nonsensicality. We will argue that in sequent calculi with multiple sequent arrows it is possible to maintain certain features that are desirable if we assume an understanding of the meaning of connectives in the spirit of proof-theoretic semantics. The use of multiple sequent arrows will be justified by the presence of congruentiality-breaking unary connectives. (shrink)

In the children's book ``The Phantom Tollbooth'' by Norton Juster one can find the following passage:``Yes, please,'' said Milo. ``Can you show me the biggest number there is?''.

Reductive accounts of the direction of time are often paired with Humean accounts of laws, while non-reductive accounts of time are often paired with anti-Humean accounts of laws. The traditional pairing of views has recently come under question. This paper aims to clarify what sorts of anti-Humean views motivate anti-reductionism about the direction of time. It is argued that those who think (i) that the laws are metaphysically fundamental, and (ii) that the laws contain time-asymmetric contents, should treat the (...) class='Hi'>arrow of time as metaphysically fundamental. (shrink)

This volume contains the proceedings of JELIA '92, les Journ es Europ ennes sur la Logique en Intelligence Artificielle, or the Third European Workshop on Logics in Artificial Intelligence. The volume contains 2 invited addresses and 21 selected papers covering such topics as: - Logical foundations of logic programming and knowledge-based systems, - Automated theorem proving, - Partial and dynamic logics, - Systems of nonmonotonic reasoning, - Temporal and epistemic logics, - Belief revision. One invited paper, by D. Vakarelov, (...) is on arrow logics, i.e., modal logics for representing graph information. The other, by L.M. Pereira,J.J. Alferes, and J.N. Apar cio, is on default theory for well founded semantics with explicit negation. (shrink)

Methods available for the axiomatization of arbitrary finite-valued logics can be applied to obtain sound and complete intelim rules for all truth-functional connectives of classical logic including the Sheffer stroke and Peirce’s arrow. The restriction to a single conclusion in standard systems of natural deduction requires the introduction of additional rules to make the resulting systems complete; these rules are nevertheless still simple and correspond straightforwardly to the classical absurdity rule. Omitting these rules results in systems for intuitionistic (...) versions of the connectives in question. (shrink)

Written for any motivated reader with a high-school knowledge of mathematics, and the discipline to follow logical arguments, this book presents the proofs for revolutionary impossibility theorems in an accessible way, with less jargon and notation, and more background, intuition, examples, explanations, and exercises.

Ramsey famously pronounced that discounting “future enjoyments” would be ethically indefensible. Suppes enunciated an equity criterion implying that all individuals’ welfare should be treated equally. By contrast, Arrow accepted, perhaps rather reluctantly, the logical force of Koopmans’ argument that no satisfactory preference ordering on a sufficiently unrestricted domain of infinite utility streams satisfies equal treatment. In this paper, we first derive an equitable utilitarian objective based on a version of the Vickrey–Harsanyi original position, extended to allow a variable and (...) uncertain population with no finite bound. Following the work of Chichilnisky and others on sustainability, slightly weakening the conditions of Koopmans and co-authors allows intergenerational equity to be satisfied. In fact, assuming that the expected total number of individuals who ever live is finite, and that each individual’s utility is bounded both above and below, there is a coherent equitable objective based on expected total utility. Moreover, it implies the “extinction discounting rule” advocated by, inter alia, the Stern Review on climate change. (shrink)