For an arbitrary finite algebra $\g A = (A, f, 0, 1)$ one defines a double sequence $a(i,j)$ by $a(i,0)\!=\!a(0,j)\! =\! 1$ and $a(i,j) \!= \!f( a(i, j-1) , a(i-1,j) )$.The problem if such recurrent double sequences are ultimately zero is undecidable, even if we restrict it to the class of commutative finite algebras.

We show that true first-order arithmetic is interpretable over the real-algebraic structure of models of intuitionistic analysis built upon a certain class of complete Heyting algebras. From this the undecidability of the structures follows. We also show that Scott's model is equivalent to true second-order arithmetic. In the appendix we argue that undecidability on the language of ordered rings follows from intuitionistically plausible properties of the real numbers.

By using algebraic properties of (commutative unital) indecomposable polynomial rings we achieve results concerning their first-order theory, namely: interpretability of arithmetic and a uniform proof of undecidability of their full theory, both in the language of rings without parameters. This vastly extends the scope of a method due to Raphael Robinson, which deals with a restricted class of polynomial integral domains.

The recent, short debate over the alethic undecidability of a Liar Sentence between Stephen Barker and Mark Jago is revisited. It is argued that Jago’s objections succeed in refuting Barker’s alethic undecidability solution to the Liar Paradox, but that, nevertheless, this approach may be revived as the alethic indeterminacy solution to the Liar Paradox. According to the alethic indeterminacy solution, there is genuine metaphysical indeterminacy as to whether a Liar Sentence bears an alethic property, whether truth or falsity. While (...) the alethic indeterminacy solution is presented here, and some revenge cases are considered and addressed, the primary aim of this paper is to revive and defend this underexplored and auspicious approach to solving the Liar Paradox. (shrink)

We first discuss some technical questions which arise in connection with the construction of undecidable propositions in analysis, in particular in connection with the notion of the normal form of a function representing a predicate. Then it is stressed that while a function f(x) may be computable in the sense of recursive function theory, it may nevertheless have undecidable properties in the realm of Fourier analysis. This has an implication for a conjecture of Penrose's which states that classical (...) physics is computable. (shrink)

Stephen Barker presents a novel approach to solving semantic paradoxes, including the Liar and its variants and Curry’s paradox. His approach is based around the concept of alethic undecidability. His approach, if successful, renders futile all attempts to assign semantic properties to the paradoxical sentences, whilst leaving classical logic fully intact. And, according to Barker, even the T-scheme remains valid, for validity is not undermined by undecidable instances. Barker’s approach is innovative and worthy of further consideration, particularly by those (...) of us who aim to find a solution without logical revisionism. As it stands, however, the approach is unsuccessful, as I shall demonstrate below. (shrink)

In the present paper the well-known Gödels – Churchs argument concerning the undecidability of logic (of the first order functional calculus) is exhibited in a way which seems to be philosophically interestingfi The natural numbers are not used. (Neither Chinese Theorem nor other specifically mathematical tricks are applied.) Only elementary logic and very simple set-theoretical constructions are put into the proof. Instead of the arithmetization I use the theory of concatenation (formalized by Alfred Tarski). This theory proves to be an (...) appropriate tool. The decidability is defined directly as the property of graphical discernibility of formulas. (shrink)

The product of two $\textbf {Alt}$ logics possesses the polynomial product finite model property and its membership problem is $\textbf {coNP}$-complete. Using a reduction from an undecidable domino-tiling problem, we prove that its admissibility problem is undecidable.

Literature has been philosophically understood as a practice in the last thirty years, which involves “modes of utterance” and stances, not intrinsic textual properties. Thus, the place for semantics in philosophical inquiry has clearly diminished. Literary aesthetic appreciation has shifted its focus from aesthetic realism, based on the study of textual features, to ways of reading. Peter Lamarque’s concept of narrative opacity is a clear example of this shift. According to the philosophy of literature, literature, like any other art form, (...) does not compel us to engage realistically with it. Against this trend, this paper argues for the distinction between two kinds of opacity, defending textual opacity as a necessary condition for literary opacity. In this sense, examples in literary criticism properly illustrate not a peripheral role of meaning in literary appreciation, but arbitrariness in interpretation, which involves semantic concerns. So the assumed interest in the specific ways in which literature embeds meaning in fictional narrative works. (shrink)

We obtain an effective embedding of the classical predicate logic into the logic of partial quasiary predicates. The embedding has the property that an image of a non-theorem of the classical logic is refutable in a model of the logic of partial quasiary predicates that has the same cardinality as the classical countermodel of the non-theorem. Therefore, we also obtain an embedding of the classical predicate logic of finite models into the logic of partial quasiary predicates over finite structures. (...) As a consequence, we prove that the logic of partial quasiary predicates is undecidable—more precisely, $\varSigma ^0_1$-complete—over arbitrary structures and not recursively enumerable—more precisely, $\varPi ^0_1$-complete—over finite structures. (shrink)

In this paper we study essential hereditary undecidability. Theories with this property are a convenient tool to prove undecidability of other theories. The paper develops the basic facts concerning essentially hereditary undecidability and provides salient examples, like a construction of essentially hereditarily undecidable theories due to Hanf and an example of a rather natural essentially hereditarily undecidable theory strictly below. We discuss the (non-)interaction of essential hereditary undecidability with recursive boolean isomorphism. We develop a reduction relation essential (...) tolerance, or, in the converse direction, lax interpretability that interacts in a good way with essential hereditary undecidability. We introduce the class of $$\Sigma ^0_1$$ Σ 1 0 -friendly theories and show that $$\Sigma ^0_1$$ Σ 1 0 -friendliness is sufficient but not necessary for essential hereditary undecidability. Finally, we adapt an argument due to Pakhomov, Murwanashyaka and Visser to show that there is no interpretability minimal essentially hereditarily undecidable theory. (shrink)

A natural problem from elementary arithmetic which is so strongly undecidable that it is not even Trial and Error decidable (in other words, not decidable in the limit) is presented. As a corollary, a natural, elementary arithmetical property which makes a difference between intuitionistic and classical theories is isolated.

The paper describes a decidable class of verification problems expressed in first order timed logic. To specify programs we useState Machines. It is known that Abstract State Machines and first order timed logic are two very powerful formalisms apt to represent verification problems for timed distributed systems. However, the general verification problem represented in this way is undecidable. Prior, some decidable classes of verification problems were described in semantical properties that are in their turn undecidable. The decidable class (...) of the present paper is described in syntactical terms. Though it admits no functions, only predicates, it is of practical interest and we give an example illustrating possible applications. (shrink)

All known structural extensions of the substructural logic $\textbf{FL}_{\textbf{e}}$, the Full Lambek calculus with exchange/commutativity (corresponding to subvarieties of commutative residuated lattices axiomatized by $\{\vee, \cdot, 1\}$ -equations), have decidable theoremhood; in particular all the ones defined by knotted axioms enjoy strong decidability properties (such as the finite embeddability property). We provide infinitely many such extensions that have undecidable theoremhood, by encoding machines with undecidable halting problem. An even bigger class of extensions is shown to have (...) class='Hi'>undecidable deducibility problem (the corresponding varieties of residuated lattices have undecidable word problem); actually with very few exceptions, such as the knotted axioms and the other prespinal axioms, we prove that undecidability is ubiquitous. Known undecidability results for non-commutative extensions use an encoding that fails in the presence of commutativity, so and-branching counter machines are employed. Even these machines provide encodings that fail to capture proper extensions of commutativity, therefore we introduce a new variant that works on an exponential scale. The correctness of the encoding is established by employing the theory of residuated frames. (shrink)

The discourse on the fundamental issues raised by synthetic biology, such as biosafety and biosecurity, intellectual property, environmental consequences and ethical and societal implications, is still open and controversial. This, coupled with the potential and risks the field holds, makes it one of the hottest topics in technology assessment today. How a new technology is perceived by the public influences the manner in which its products and applications will be received. Therefore, it is important to learn how people perceive (...) synthetic biology. This work gathers, integrates and discusses the results of three studies of public perceptions of synthetic biology: an analysis of existing research on how media portray synthetic biology across 13 European countries and in the USA, the Meeting of Young Minds, a public debate between prospective politicians and synthetic biologists in the Netherlands and the experiences of citizen panels and focus groups in Austria, the UK and the USA. The results show that the media are generally positive in their reports on synthetic biology, rather unbalanced in their view of potential benefits and risks, and also heavily influenced by the sources of the stories, namely scientists and stakeholders. Among the prospective Dutch politicians, there were positive expectations as well as very negative ones. Some of these positions are also shared by participants in public dialogue experiments, such as not only the demand for information, transparency and regulation but also a sense of resignation and ineluctability of scientific and technological progress. (shrink)

In this work, we aim at understanding incompleteness in an abstract way via metamathematical properties of formal theories. We systematically examine the relationships between the following twelve important metamathematical properties of arithmetical theories: Rosser, EI (effectively inseparable), RI (recursively inseparable), TP (Turing persistent), EHU (essentially hereditarily undecidable), EU (essentially undecidable), Creative, $\textbf{0}^{\prime }$ (theories with Turing degree $\textbf{0}^{\prime }$), REW (all RE sets are weakly representable), RFD (all recursive functions are definable), RSS (all recursive sets are strongly representable), (...) RSW (all recursive sets are weakly representable). Given any two properties $P$ and $Q$ in the above list, we examine whether $P$ implies $Q$. (shrink)

Derrida's key concepts or pseudo-concepts of différance, the trace, and the undecidable suggest analogies to some of the most significant results of formal, symbolic logic and metalogic. As early as 1970, Derrida himself pointed out an analogy between his use of ‘undecidable’ and Gödel's incompleteness theorems, which demonstrate the existence, in any sufficiently complex and consistent system, of propositions which cannot be proven or disproven (i.e., decided) within that system itself. More recently, Graham Priest has interpreted différance as (...) an instance of the general metalogical procedure of diagonalisation. In this essay, I consider the extent to which Derrida's key terms and the essential operations of deconstruction can be formalised. I argue that, if formalisation is indeed the technique of writing par excellence, then the formalisation of deconstructive concepts tends to show how the auto-deconstruction of total systems arises from the problematic possibility of writing itself. For instance, since diagonalisation permits the ‘arithmetisation of syntax’ whereby a formal system is able to formulate claims about its own logico-grammatical properties, we can understand its potential to inscribe the undecidable within the systematicity of language as simply one instance of the potential of writing, in figuring itself, to render inscrutable the trace of its own origin. (shrink)

We study the global properties of [Formula: see text], the Turing degrees of the n-r.e. sets. In Theorem 1.5, we show that the first order of [Formula: see text] is not decidable. In Theorem 1.6, we show that for any two n and m with n < m, [Formula: see text] is not a Σ1-substructure of [Formula: see text].

We initiate an investigation of structures on the set of real numbers having the property that path components of definable sets are definable. All o-minimal structures on $(\mathbb {R},<)$ have the property, as do all expansions of $(\mathbb {R},+,\cdot,\mathbb {N})$. Our main analytic-geometric result is that any such expansion of $(\mathbb {R},<,+)$ by Boolean combinations of open sets (of any arities) either is o-minimal or defines an isomorph of $(\mathbb N,+,\cdot )$. We also show that any given expansion (...) of $(\mathbb {R}, <, +,\mathbb {N})$ by subsets of $\mathbb {N}^n$ (n allowed to vary) has the property if and only if it defines all arithmetic sets. Variations arise by considering connected components or quasicomponents instead of path components. (shrink)

In this paper a new property of theories, called effective retractability is introduced and used to obtain a characterization for the degrees of subtheories of arithmetic and set theory. By theory we understand theory in standard formalization as defined by Tarski [10]. The word degree refers to the Kleene-Post notion of degree of recursive unsolvability [2]. By the degree of a theory we mean, of course, the degree associated with its decision problem via Gödel numbering.

This paper will first introduce first-order mereotopological axioms and axiomatized theories which can be found in some recent literature and it will also give a survey of decidability, undecidability as well as other relevant notions. Then the main result to be given in this paper will be the finite inseparability of any mereotopological theory up to atomic general mereotopology (AGEMT) or strong atomic general mereotopology (SAGEMT). Besides, a more comprehensive summary will also be given via making observations about other properties (...) stronger than undecidability. (shrink)

Pluralists maintain that there is more than one truth property in virtue of which bearers are true. Unfortunately, it is not yet clear how they diagnose the liar paradox or what resources they have available to treat it. This chapter considers one recent attempt by Cotnoir (2013b) to treat the Liar. It argues that pluralists should reject the version of pluralism that Cotnoir assumes, discourse pluralism, in favor of a more naturalized approach to truth predication in real languages, which (...) should be a desideratum on any successful pluralist conception. Appealing to determination pluralism instead, which focuses on truth properties, it then proposes an alternative treatment to the Liar that shows liar sentences to be undecidable. (shrink)

This paper presents a simple decidable logic of functional dependence LFD, based on an extension of classical propositional logic with dependence atoms plus dependence quantifiers treated as modalities, within the setting of generalized assignment semantics for first order logic. The expressive strength, complete proof calculus and meta-properties of LFD are explored. Various language extensions are presented as well, up to undecidable modal-style logics for independence and dynamic logics of changing dependence models. Finally, more concrete settings for dependence are discussed: (...) continuous dependence in topological models, linear dependence in vector spaces, and temporal dependence in dynamical systems and games. (shrink)

From the point of view of non-classical logics, Heyting's implication is the smallest implication for which the deduction theorem holds. This book studies properties of logical systems having some of the classical connectives and implication in the neighbourhood of Heyt ing's implication. I have not included anything on entailment, al though it belongs to this neighbourhood, mainly because of the appearance of the Anderson-Belnap book on entailment. In the later chapters of this book, I have included material that might be (...) of interest to the intuitionist mathematician. Originally, I intended to include more material in that spirit but I decided against it. There is no coherent body of material to include that builds naturally on the present book. There are some serious results on topological models, second order Beth and Kripke models, theories of types, etc., but it would require further research to be able to present a general theory, possibly using sheaves. That would have postponed pUblication for too long. I would like to dedicate this book to my colleagues, Professors G. Kreisel, M.O. Rabin and D. Scott. I have benefited greatly from Professor Kreisel's criticism and suggestions. Professor Rabin's fun damental results on decidability and undecidability provided the powerful tools used in obtaining the majority of the results reported in this book. Professor Scott's approach to non-classical logics and especially his analysis of the Scott consequence relation makes it possible to present Heyting's logic as a beautiful, integral part of non-classical logics. (shrink)

An excellent introduction to mathematical logic, this book provides readers with a sound knowledge of the most important approaches to the subject, stressing the use of logical methods in attacking nontrivial problems. It covers the logic of classes, of propositions, of propositional functions, and the general syntax of language, with a brief introduction that also illustrates applications to so-called undecidability and incompleteness theorems. Other topics include the simple proof of the completeness of the theory of combinations, Church's theorem on the (...) recursive unsolvability of the decision problem for the restricted function calculus, and the demonstrable properties of a formal system as a criterion for its acceptability. 1950 ed. (shrink)

Do undergraduate students perceive that it is more acceptable to ‹cheat’ using information technology (IT) than it is to cheat without the use of IT? Do business discipline-related majors cheat more than non-business discipline-related majors? Do undergraduate students perceive it to be more acceptable for them personally to cheat than for others to cheat? Questionnaires were administered to undergraduate students at five geographical academic locations in the spring, 2006 and fall 2006 and spring, 2007. A total of 708 usable questionnaires (...) were returned including 532 from students majoring in business-related disciplines and 139 from students majoring in non-business related disciplines (37 were undecided). It appears that in terms of intellectual property violations, undergraduate students in general find cheating using IT more acceptable than cheating without the use of IT. It also appears that undergraduate students perceive that it is relatively more acceptable for them to personally cheat when using IT than for others to cheat when using IT, although this is reversed when IT is not involved. No significant differences on these issues were found between undergraduate students having business discipline-related majors and those having non-business discipline-related majors. (shrink)

Guarded fragments of first-order logic were recently introduced by Andreka, van Benthem and Nemeti; they consist of relational first-order formulae whose quantifiers are appropriately relativized by atoms. These fragments are interesting because they extend in a natural way many propositional modal logics, because they have useful model-theoretic properties and especially because they are decidable classes that avoid the usual syntactic restrictions (on the arity of relation symbols, the quantifier pattern or the number of variables) of almost all other known decidable (...) fragments of first-order logic. Here, we investigate the computational complexity of these fragments. We prove that the satisfiability problems for the guarded fragment (GF) and the loosely guarded fragment (LGF) of first-order logic are complete for deterministic double exponential time. For the subfragments that have only a bounded number of variables or only relation symbols of bounded arity, satisfiability is EXPTIME-complete. We further establish a tree model property for both the guarded fragment and the loosely guarded fragment, and give a proof of the finite model property of the guarded fragment. It is also shown that some natural, modest extensions of the guarded fragments are undecidable. (shrink)

In set theory, a maximality principle is a principle that asserts some maximality property of the universe of sets or some part thereof. Set theorists have formulated a variety of maximality principles in order to settle statements left undecided by current standard set theory. In addition, philosophers of mathematics have explored maximality principles whilst attempting to prove categoricity theorems for set theory or providing criteria for selecting foundational theories. This article reviews recent work concerned with the formulation, investigation and (...) justification of maximality principles. (shrink)

This book concerns the foundations of epistemic modality and hyperintensionality and their applications to the philosophy of mathematics. I examine the nature of epistemic modality, when the modal operator is interpreted as concerning both apriority and conceivability, as well as states of knowledge and belief. The book demonstrates how epistemic modality and hyperintensionality relate to the computational theory of mind; metaphysical modality and hyperintensionality; the types of mathematical modality and hyperintensionality; to the epistemic status of large cardinal axioms, undecidable (...) propositions, and abstraction principles in the philosophy of mathematics; to the modal and hyperintensional profiles of the logic of rational intuition; and to the types of intention, when the latter is interpreted as a hyperintensional mental state. Chapter 2 argues for a novel type of expressivism based on the duality between the categories of coalgebras and algebras, and argues that the duality permits of the reconciliation between modal cognitivism and modal expressivism. I also develop a novel topic-sensitive truthmaker semantics for dynamic epistemic logic, and develop a novel dynamic epistemic two-dimensional hyperintensional semantics. Chapter 3 provides an abstraction principle for epistemic (hyper-)intensions. Chapter 4 advances a topic-sensitive two-dimensional truthmaker semantics, and provides three novel interpretations of the framework along with the epistemic and metasemantic. Chapter 5 applies the fixed points of the modal μ-calculus in order to account for the iteration of epistemic states in a single agent, by contrast to availing of modal axiom 4 (i.e. the KK principle). The fixed point operators in the modal μ-calculus are rendered hyperintensional, which yields the first hyperintensional construal of the modal μ-calculus in the literature and the first application of the calculus to the iteration of epistemic states in a single agent instead of the common knowledge of a group of agents. Chapter 6 advances a solution to the Julius Caesar problem based on Fine's `criterial' identity conditions which incorporate conditions on essentiality and grounding. Chapter 7 provides a ground-theoretic regimentation of the proposals in the metaphysics of consciousness and examines its bearing on the two-dimensional conceivability argument against physicalism. The topic-sensitive epistemic two-dimensional truthmaker semantics developed in chapters 2 and 4 are availed of in order for epistemic states to be a guide to metaphysical states in the hyperintensional setting. Chapters 8-12 provide cases demonstrating how the two-dimensional hyperintensions of hyperintensional, i.e. topic-sensitive epistemic two-dimensional truthmaker, semantics, solve the access problem in the epistemology of mathematics. Chapter 8 examines the interaction between my hyperintensional semantics and the axioms of epistemic set theory, large cardinal axioms, the Epistemic Church-Turing Thesis, the modal axioms governing the modal profile of Ω-logic, Orey sentences such as the Generalized Continuum Hypothesis, and absolute decidability. These results yield inter alia the first hyperintensional Epistemic Church-Turing Thesis and hyperintensional epistemic set theories in the literature. Chapter 9 examines the modal and hyperintensional commitments of abstractionism, in particular necessitism, and epistemic hyperintensionality, epistemic utility theory, and the epistemology of abstraction. I countenance a hyperintensional semantics for novel epistemic abstractionist modalities. I suggest, too, that observational type theory can be applied to first-order abstraction principles in order to make first-order abstraction principles recursively enumerable, i.e. Turing machine computable, and that the truth of the first-order abstraction principle for hyperintensions is grounded in its being possibly recursively enumerable and the machine being physically implementable. Chapter 10 examines the philosophical significance of hyperintensional Ω-logic in set theory and discusses the hyperintensionality of metamathematics. Chapter 11 provides a modal logic for rational intuition and provides a hyperintensional semantics. Chapter 12 avails of modal coalgebras to interpret the defining properties of indefinite extensibility, and avails of hyperintensional epistemic two-dimensional semantics in order to account for the interaction between the interpretational and objective modalities and truthmakers thereof. This yields the first hyperintensional category theory in the literature. I invent a new mathematical trick in which first order structures are treated as categories, and Vopenka's principle can be satisfied because of the elementary embeddings between the categories and generate Vopenka cardinals while bypassing the category of Set in category theory. Chapter 13 examines modal responses to the alethic paradoxes. Chapter 14 examines, finally, the modal and hyperintensional semantics for the different types of intention and the relation of the latter to evidential decision theory. (shrink)

We prove that everyn-modal logic betweenKnandS5nis undecidable, whenever n ≥ 3. We also show that each of these logics is non-finitely axiomatizable, lacks the product finite model property, and there is no algorithm deciding whether a finite frame validates the logic. These results answer several questions of Gabbay and Shehtman. The proofs combine the modal logic technique of Yankov–Fine frame formulas with algebraic logic results of Halmos, Johnson and Monk, and give a reduction of the representation problem of (...) finite relation algebras. (shrink)

We study the non-Fregean propositional logic with propositional quantifiers, denoted by $\mathsf{SCI}_{\mathsf{Q}}$. We prove that $\mathsf{SCI}_{\mathsf{Q}}$ does not have the finite model property and that it is undecidable. We also present examples of how to interpret in $\mathsf{SCI}_{\mathsf{Q}}$ various mathematical theories, such as the theory of groups, rings, and fields, and we characterize the spectra of $\mathsf{SCI}_{\mathsf{Q}}$-sentences. Finally, we present a translation of $\mathsf{SCI}_{\mathsf{Q}}$ into a classical two-sorted first-order logic, and we use the translation to prove some model-theoretic (...) properties of $\mathsf{SCI}_{\mathsf{Q}}$. (shrink)

We solve a major open problem concerning algorithmic properties of products of ‘transitive’ modal logics by showing that products and commutators of such standard logics as K4, S4, S4.1, K4.3, GL, or Grz are undecidable and do not have the finite model property. More generally, we prove that no Kripke complete extension of the commutator [K4,K4] with product frames of arbitrary finite or infinite depth (with respect to both accessibility relations) can be decidable. In particular, if.

We show that—unlike products of ‘transitive’ modal logics which are usually undecidable—their ‘expanding domain’ relativisations can be decidable, though not in primitive recursive time. In particular, we prove the decidability and the finite expanding product model property of bimodal logics interpreted in two-dimensional structures where one component—call it the ‘flow of time’—is • a finite linear order or a finite transitive tree and the other is composed of structures like • transitive trees/partial orders/quasi-orders/linear orders or only finite such (...) structures expanding over time. The decidability proof is based on Kruskal’s tree theorem, and the proof of non-primitive recursiveness is by reduction of the reachability problem for lossy channel systems. The result is used to show that the dynamic topological logic interpreted in topological spaces with continuous functions is decidable if the number of function iterations is assumed to be finite. (shrink)

Mereological theories are theories based on a binary predicate ‘being a part of’. It is believed that such a predicate must at least define a partial ordering. A mereological theory can be obtained by adding on top of the basic axioms of partial orderings some of the other axioms posited based on pertinent philosophical insights. Though mereological theories have aroused quite a few philosophers’ interest recently, not much has been said about their meta-logical properties. In this paper, I will look (...) into whether those theories are decidable or not. Besides, since theories of Boolean algebras are in some sense upper bounds of mereological theories which can be found in the literature, I shall also make some observations about the possibility of getting mereological theories beyond Boolean algebras. (shrink)

The purpose of this paper is to clarify the relationship between various conditions implying essential undecidability: our main result is that there exists a theory T in which all partially recursive functions are representable, yet T does not interpret Robinson’s theory R. To this end, we borrow tools from model theory — specifically, we investigate model-theoretic properties of the model completion of the empty theory in a language with function symbols. We obtain a certain characterization of ∃∀ theories interpretable in (...) existential theories in the process. (shrink)

RésuméSelon K. Gödel, les restrictions méthodologiques des constructivistes sont aberrantes, et le point de vue réaliste est beaucoup plus fécond: il est hi‐même parvenu à ses résultats logiques fondarnentaux en donnant une place à la notion de vérite, qui n'est pas de type combinatoire. Le premier théorème d'incomplétude est hi‐même un argument décisif en faveur du réalisme, si l'on accepte le principe d'«accessibilité» en vertu duquel nous pouvons décider de toutes les propriétés de nos constructions intellectuelles. Par ailleurs, il existe (...) un large spectre d'arguments permettant de statuer sur un énoncé indécidable dans un système formel. La thèse mécaniste, selon laquelle l'intelligence humaine peut être pensée sans distorsion significative sur le modèle d'une machine de Turing, est donc inacceptable.SummaryAccording to K. Gödel, the methodological restrictions of the constructivists are aberrant, and the realist point of view is much more fruitful. He reached these fundamental logical results himself by making place for a non‐cornbinatorial notion of truth. The first incompletness theorem is itself a decisive argument in favor of realism, provided that the principle of «accessibility» is accepted, by virtue of which we are capable of determining all the properties of our intellectual constructions. Moreover, there are numerous arguments that permit the evaluation of an undecidable statement in a formal system. The mechanistic thesis, according to which the functioning of the human mind, without significant distorsion, can be compared to a Turing machine, is now unacceptable.ZusammenfassungNach Gödel sind die methodologischen Einschränkungen der Konstruktivisten irrig, und er hält den realistischen Standpuukt für viel fruchtbarer. Er selbst erreichte seine grundlegenden logischen Ergebnisse dadurch, dass er Platz machte für einen nichtkombinatorischen Begriff der Wahrheit. Das erste Unvollständigkeitstheorem ist selbst ein entscheidendes Argument zugunsten des Realismus, sofern das «Zugänglichkeitsprinzip» akzeptiert wird, wonach wir fähig sind, alle Eigenschaften unserer intellektuellen Konstruktionen zu bestinmen. Zudem gibt es zahlreiche Argumente, die die Beurteilung einer unentscheidbaren Aussage in einem formalen System erlauben. Die mechanistische These, nach welcher das Funktionieren des menschlichen Geistes ohne wesentliche Verzerrung mit einer Turingmaschine verglichen werden kann, ist heute nicht mehr annehmbar. (shrink)

This book concerns the foundations of epistemic modality. I examine the nature of epistemic modality, when the modal operator is interpreted as concerning both apriority and conceivability, as well as states of knowledge and belief. The book demonstrates how epistemic modality relates to the computational theory of mind; metaphysical modality; the types of mathematical modality; to the epistemic status of large cardinal axioms, undecidable propositions, and abstraction principles in the philosophy of mathematics; to the modal profile of rational intuition; (...) and to the types of intention, when the latter is interpreted as a modal mental state. Chapter 2 argues for a novel type of expressivism based on the duality between the categories of coalgebras and algebras, and argues that the duality permits of the reconciliation between modal cognitivism and modal expressivism. Chapter 3 provides an abstraction principle for epistemic intensions. Chapter 4 advances a two-dimensional truthmaker semantics, and provides three novel interpretations of the framework along with the epistemic and metasemantic. Chapter 5 applies the fixed points of the modal $\mu$-calculus in order to account for the iteration of epistemic states, by contrast to availing of modal axiom 4. Chapter 6 advances a solution to the Julius Caesar problem based on Fine's "criterial" identity conditions which incorporate conditions on essentiality and grounding. Chapter 7 provides a ground-theoretic regimentation of the proposals in the metaphysics of consciousness and examines its bearing on the two-dimensional conceivability argument against physicalism. The epistemic two-dimensional truthmaker semantics developed in chapter 4 is availed of in order for epistemic states to be a guide to metaphysical states in the hyperintensional setting. Chapter 8 examines the modal commitments of abstractionism, in particular necessitism, and epistemic modality and the epistemology of abstraction. Chapter 9 examines the modal profile of $\Omega$-logic in set theory. Chapter 10 examines the interaction between epistemic two-dimensional semantics and absolute decidability. Chapter 11 avails of modal coalgebraic automata to interpret the defining properties of indefinite extensibility, and avails of epistemic two-dimensional semantics in order to account for the interaction of the interpretational and objective modalities thereof. The hyperintensional, epistemic two-dimensional truthmaker semantics developed in chapter 4 is applied in chapters 8, 10, and 11. Chapter 12 provides a modal logic for rational intuition. Chapter 13 examines modal responses to the alethic paradoxes. Chapter 14 examines, finally, the modal semantics for the different types of intention and the relation of the latter to evidential decision theory. (shrink)

In large anonymous games, payoffs are determined by strategy distributions rather than strategy profiles. If half the players choose a strategy a, all of them get a certain payoff, whereas if only one-third of the players choose that strategy, the players choosing may get a different payoff. Strategizing in such a game by a player involves reasoning about not who does what but what fraction of the population makes the same choice as that player.We present a simple modal logic to (...) reason about such strategization in large games. Since actual numbers are irrelevant, a player need not even know how many others are in the game, thus leading to the consideration of games with unboundedly many players. The logic we consider is the propositional modal fragment of a first order modal logic. We show that it has a bounded agent property, giving us a decision procedure for satisfiability. We also present a complete axiomatization of the valid formulas. The logic admits a natural model checking algorithm and bisimulation characterization. The logic with quantification over players is more appropriate, but is undecidable. (shrink)

Completeness is shown for several versions of Girard's linear logic with respect to Petri nets as the class of models. One logic considered is the -free fragment of intuitionistic linear logic without the exponential !. For this fragment Petri nets form a sound and complete model. The strongest logic considered is intuitionistic linear logic, with ,&, and the exponential ! , and forms of quantification. This logic is shown sound and complete with respect to atomic nets , though only once (...) we add extra axioms specific to the Petri-net model. The logic is remarkably expressive, enabling descriptions of the kinds of properties one might wish to show of nets; in particular, negative properties, asserting the impossibility of an assertion, can also be expressed. Unfortunately, with respect to this logic, whether an assertion is true of a finite net becomes undecidable. (shrink)

Nick Dyer-Witheford and Greig de Peuter. Games of Empire: Global Capitalism and Video Games . Minneapolis: University of Minnesota Press. 2009. 320pp. pbk. $19.95 ISBN-13: 978-0816666119. In Games of Empire , Nick Dyer-Witheford and Greig de Peuter expand an earlier study of “the video game industry as an aspect of an emerging postindustrial, post-Fordist capitalism” (xxix) to argue that videogames are “exemplary media of Empire” (xxix). Their notion of “Empire” is based on Michael Hardt and Antonio Negri’s Empire (2000), which (...) characterizes the contemporary world order as a decentralized system of global economic, political, and economic power that transcends national boundaries. In the view of the authors, Hardt and Negri’s account sets itself apart from other analyses of international politics by offering a “comprehensive account of conditions of work, forms of subjectivity, and types of struggle in contemporary capital” (xx). Dyer-Witheford and de Peuter thus divide Games of Empire into three sections to reflect each of these aspects of Empire ’s argument, seeing their work as the first account to explore “virtual games within a system of global ownership, privatized property, coercive class relations, military operations, and radical struggle” (xxix). Books in the University of Minnesota Press’s Electronic Mediations series “explore the humanistic and social implications” of new technologies that spark “significant changes in society and culture, politics and economics, thinking and being.” That’s an abstract goal, and one that Games of Empire surely meets. Yet at times it can be difficult to understand exactly which specific intervention this book seeks to make. It is unclear whether the authors of Games of Empire see their work as an indictment of game scholars’ lack of attention to political economy, or whether it’s a work of political theory hoping to show that other disciplines should be paying more attention to the production and play of videogames. Because Dyer-Witheford and de Peuter don’t directly criticize previous political critiques of gaming—such as Edward Castronova’s exploration of the “porous membrane” allowing two-way traffic between virtual economies and those of the real world, or Alexander Galloway’s unraveling of control protocols in algorithmic design, or Ian Bogost’s idea of political procedural rhetoric—they sometimes leave the reader wondering how to situate the book in the broader discourse on games and politics, either separately or together. Thus, Games of Empire might best be seen as an introduction to the writings of Hardt and Negri for game players and designers, rather than as a text for communicating the basic concepts of game studies and design. It is neither a truly new theory of games or digital media, nor is it a new theory of Empire—and that’s not a criticism. It is instead an introduction to Empire through popular culture, as Zizek does for Lacan in Looking Awry . If one were teaching an introductory course on contemporary political theory, this book would offer obvious inroads into Negri and Hardt’s thinking for a number of reasons. Despite its radical ideological bent, the book isn’t off-putting to readers who don’t necessarily share the authors’ politics. It synthesizes complex ideas from difficult thinkers like Marx, Foucault, and Guattari while integrating modifications and critiques of Empire theory itself. And although the book is dense, sometimes feeling longer than it actually is (just over 200 pages), Games of Empire maintains a breezy readability by tightly coupling core concepts of Empire theory to well-known games and widely-publicized conflicts within the videogame industry. The first section of the book focuses on immaterial labor, the accumulation of “cognitive capital,” and the global process of manufacturing videogame consoles. It is significant for the authors that videogames began as hacker experiments within research institutes of the military industrial complex, programmed on stolen time, before becoming a commodity (7). This is the first in a string of examples showing how creative dissidence and conflict fuel the continuing evolution of Empire’s control. Dyer-Witheford and de Peuter explain that the videogame industry now constitutes an international production apparatus dominating both creative work in developed nations and manual labor in developing ones. Because game industries in the United States, Western Europe, and Japan are predominately non-unionized, they serve as an exemplary system for analyzing how global capital exploits contemporary intellectual work—including an excellent analysis of the “EA Spouse” scandal of 2004. On the side of the consumer, the authors argue that rabid “console races” that drive the industry forward from a technological perspective serve to structure gamer identity and combat piracy; later in the book, these machines offer a window into the worlds of Congolese coltan mining and electronic waste (222-224). In the second section, Dyer-Witheford and de Peuter move on to deep case studies of individual games to show how the most popular game genres embed imperial assumptions about conflict, exchange, and urban life. First they argue that military training games such as Full Spectrum Warrior —co-developed by university researchers, industry developers, and military contractors—contribute to the “banalization” of war, a subjective state wherein perpetual preparedness for war is accepted as a part of everyday life (100). Chapter five covers Michel Foucalt’s notion of “biopower,” the extension of capital accumulation to life itself. The authors argue that virtual worlds such as World of Warcraft , which take market capitalism as a given and force players into essentialist roles and racial antagonisms, are organized to maximize control and profit (often on the backs of virtual currency “farmers” in China and southeast Asia). Finally, they criticize the naïve assumption that humor and cynicism in the popular sandbox game franchise Grand Theft Auto offer any remedy to its racialized, violent content. Instead, such games indulge and normalize the fantasy of getting rich at any cost by keeping the realities of contemporary urban life and corporate greed at a safe distance (181). Part three of Games of Empire focuses on “games of multitude,” a preliminary attempt to escape from Empire’s order through alternate modes of videogame development and play. Multitude is defined dialectically, as “the engine and the enemy” of Empire (187). This is the most important, yet also most contradictory section of the text. It lays bare the process by which Empire and its media feed our creative and intellectual development to overabundance. At a certain point, the force of the multitude reaches such a level that it threatens the stability of Empire; however, instead of following Hardt and Negri’s utopian assumptions about the radical potential of the multitude, the authors here follow Paolo Virno’s warning that Empire is “very good at adopting apparently iconoclastic practices and utopian ideas as management techniques and revenue sources” (188). At every turn, advances in player configurative power provide new sources of revenue and advertising angles for the game industry. A disappointing shortcoming of these latter pages is the lack of truly new examples for radical resistance within game development. Instead, it turns out that the radical left seems satisfied with the same mild successes that the left-of-center also has celebrated: artist’s mods, virtual world activism, and critical counterplay within strategy- and wargames. Having been frequently cited by many authors before Dyer-Witheford and de Peuter, this idea of subversion or resistance through play feels tired and unpersuasive. It is unclear if the authors believe it is possible to embrace game design itself as a way of pursuing what they call “exodus” from Empire, or if an all-too-fashionable subversion is the only workable strategy. While the book does explore how the earliest independent game studios were eventually subverted and incorporated into the game industry proper, it doesn’t affirm or critique more recent non-commercial, DIY game development projects such as Klik-of-the-Month Club and Ludum Dare. Dyer-Witheford and de Peuter’s analysis of so-called “tactical games,” including the editorial works of La Molleindustria, leads to an even more ambivalent take on the contemporary design ecology. At the conclusion of his essay on “Countergaming,” Galloway asserts that avant-garde videogame artists “should create new grammars of action […] should create alternative algorithms” (Galloway 125). Yet Dyer-Witheford and de Peuter characterize works such as McDonald’s Video Game and Oiligarchy as didactic, suggesting that the role of radical political games might be “limited to that of agitprop” (199). They are concerned that games like those of Molleindustria rigidly structure the activities of their players in order to prove a point. Yet, despite their repeated assertion that the equation of greater interactivity with democratic digital liberation is flawed, the authors see potential in policy simulators that “allow players to edit or tweak” (202) their parameters in response to what Bogost has called simulation fever , the simultaneous drive toward and fear of simulation (Bogost 108). The possibility of practicing radical design is bucked, and early attempts at critical game development like those of Molleindustria’s seem to be relegated to the status of exceptions that prove the rule for player-centered exodus. Overall, there is one glaring question Games of Empire leaves unanswered: how exactly are videogames the “exemplary media” of Empire, and what are the implications of videogames being exemplary in this way? Presumably Dyer-Witheford and de Peuter want to avoid essentialist claims, so they’re not keen on following Wark’s desire to mark “the game’s difference from [legacy media] as something that speaks to changes in the overall structure of social and technical relations” (Wark 225). It is also unclear how the production apparatuses, labor standards, and subjectivizing processes involved in the creation and use of other any other kind of digital media would fail to justify their equally exemplary status. Even the book’s concluding paragraph holds that virtual games “are one molecular component of this undecidable collective mutation” (Dyer-Witheford and de Peuter 229) of intellect, labor, and daily life. In the end, the authors seem to back away from their focus on games as exemplary to bring their work in line with broader theories of the gradual digitization of the everyday, in line with Galloway and Manovich. Despite these flaws, there is an undeniable elegance to Games of Empire ’s contrasting of gaming’s overwhelmingly imperial content with its multitudinous form . And its ambivalence about the potential of independent or political game development might be seen by scholars of Empire as a strength rather than a weakness, an acceptance that every new expression of multitude offers another opportunity for the expansion of Empire. The book also functions as a strong, all-encompassing call to greater responsibility on the part of mainstream game developers to be more conscious of the ideologies they embed in their work, of the way their intellectual property is used and manipulated by those who employ them, and of the material impact their industry has on the world at large. For players it offers a toolbox of concepts for radical examinations of their own play activities, asking them to be more cognizant of the consequences of their consumption of digital media and the ways in which their virtual lives interface with the real. REFERENCES Bogost, Ian. Unit Operations: An Approach to Videogame Criticism . Cambridge, Mass.: MIT Press, 2006. Castranova, Edward. Synthetic Worlds: The Business and Culture of Online Games . Chicago, Illinois: University of Chicago Press, 2006. Dyer-Witheford, Nick and de Peuter, Greig. Games of Empire: Global Capitalism and Video Games . Minneapolis, Minnesota: University of Minnesota Press, 2009. Galloway, Alexander. Gaming: Essays on Algorithmic Culture . Minneapolis, Minnesota: University of Minnesota Press, 2006). Wark, McKenzie. Gamer Theory . Cambridge, Mass.: Harvard University Press, 2007. (shrink)

The hybrid logic and the independence friendly modal logic IFML are compared for their expressive powers. We introduce a logic IFML c having a non-standard syntax and a compositional semantics; in terms of this logic a syntactic fragment of IFML is singled out, denoted IFML c . (In the Appendix it is shown that the game-theoretic semantics of IFML c coincides with the compositional semantics of IFML c .) The hybrid logic is proven to be strictly more expressive than IFML (...) c . By contrast, and the full IFML are shown to be incomparable for their expressive powers. Building on earlier research (Tulenheimo and Sevenster 2006), a PSPACE -decidable fragment of the undecidable logic is disclosed. This fragment is not translatable into the hybrid logic and has not been studied previously in connection with hybrid logics. In the Appendix IFML c is shown to lack the property of ‘quasi-positionality’ but proven to enjoy the weaker property of ‘ bounded quasi-positionality’. The latter fact provides from the IFML internal perspective an account of what makes the compositional semantics of IFML c possible. (shrink)

We argue that Gödel's completeness theorem is equivalent to completability of consistent theories, and Gödel's incompleteness theorem is equivalent to the fact that this completion is not constructive, in the sense that there are some consistent and recursively enumerable theories which cannot be extended to any complete and consistent and recursively enumerable theory. Though any consistent and decidable theory can be extended to a complete and consistent and decidable theory. Thus deduction and consistency are not decidable in logic, and an (...) analogue of Rice's Theorem holds for recursively enumerable theories: all the non-trivial properties of them are undecidable. (shrink)

Alexius Meinong's Gegenstandstheorie is subject to a formal semantic paradox. The theory of defective objects originally developed by Meinong in response to Ernst Mally's paradox about self-referential thought is rejected as a general solution to paradox in the object theory. The intentionality thesis is also refuted by the counter-example of the unapprehended mountain. It is argued that despite these difficulties, an object theory is required in order to make intuitively correct sense of ontological commitment. ;A version of Meinong's theory is (...) formalized. The logic has non-standard truth value semantics and an objectual interpretation of quantifiers for a domain of existent and non-existent objects. Theories of intentional, referential, and extensional identity are offered, together with two theories of definite description, lambda abstraction, eight systems of alethic modal logic, and formal metatheory. The logic avoids the incompleteness and undecidability limitations of Godel and Church, and all logical, semantic, and set theoretical paradoxes, without type theory or Tarskian hierarchy of metalanguages. It is naively complete and mechanically decidable. ;Wittgenstein's private language argument is refuted as an obstacle to defining private mental objects in the logic. The argument is shown to be valid, but unsound. The object theory logic may therefore provide a mixed or impure private language, and its domain may contain private mental objects as well as ordinary public and non-existent objects. This means that it constitutes an object theory logic of intention, and can be used to represent the logical structure of intentional and specifically phenomenological philosophical theories that require the intelligible designation of private mental objects. ;Appendices include Henkin-type consistency, completeness, and compactness proofs ; criticism of Kazimierz Twardowski's arguments for the distinction between content and object in phenomenological psychology; translation of and commentary on Mally's essay, "Uber die Unabhangigkeit der Gegenstande vom Denken"; a discussion of the distinction between nuclear and extra-nuclear properties, and the eliminability of the modal moment; and a philosophical application of the logic to a solution of the paradox of analysis. (shrink)

In [14], we studied the computational behaviour of various first-order and modal languages interpreted in metric or weaker distance spaces. [13] gave an axiomatisation of an expressive and decidable metric logic. The main result of this paper is in showing that the technique of representing metric spaces by means of Kripke frames can be extended to cover the modal (hybrid) language that is expressively complete over metric spaces for the (undecidable) two-variable fragment of first-order logic with binary pred-icates interpreting (...) the metric. The frame conditions needed correspond rather directly with a Boolean modal logic that is, again, of the same expressivity as the two-variable fragment. We use this representation to derive an axiomatisation of the modal hybrid variant of the two-variable fragment, discuss the compactness property in distance logics, and derive some results on (the failure of) interpolation in distance logics of various expressive power. (shrink)

Around 1950, B.A. Trakhtenbrot proved an important undecidability result (known, by a pure accident, as \Trakhtenbrot's theorem"): there is no algorithm to decide, given a rst-order sentence, whether the sentence is satis able in some nite model. The result is in fact true even if we restrict ourselves to languages that has only one binary relation Tra63]. It is hardly conceivable that at that time Prof. Trakhtenbrot expected his result to in uence the development of the theory of relational databases (...) query languages, but it did. This perhaps is not surprising in view of the following two facts: 1) The theory of relational databases is strongly rooted in logic and can easily be abstracted to make it a branch of mathematical logic. 2) The main interest in the theory of relational databases is in nite relations. In the rst section we explain those two points in more detail. Then, in section 2 of the present paper, we discuss the question: \What constitutes a reasonable query to a database?" The discussion naturally leads to a certain class of queries, known as the \domain independent" queries, as an ideal query language. At this point Trakhtenbrot's theorem appears as a major obstacle, since it easily implies that this ideal class is undecidable. Real query languages cannot be allowed to have this property. Section 3 outlines then several possible ways to circumvent this di culty. The following section explains the.. (shrink)