Online research in philosophy

It is often alleged that, unlike typical axioms of mathematics, the Continuum Hypothesis (CH) is indeterminate. This position is normally defended on the ground that the CH is undecidable in a way that typical axioms are not. Call this kind of undecidability “absolute undecidability”. In this paper, I seek to understand what absolute undecidability could be such that one might hope to establish that (a) CH is absolutely undecidable, (b) typical axioms are not absolutely undecidable, and (c) (...) if a mathematical hypothesis is absolutely undecidable, then it is indeterminate. I shall argue that on no understanding of absolute undecidability could one hope to establish all of (a)–(c). However, I will identify one understanding of absolute undecidability on which one might hope to establish both (a) and (c) to the exclusion of (b). This suggests that a new style of mathematical antirealism deserves attention—one that does not depend on familiar epistemological or ontological concerns. The key idea behind this view is that typical mathematical hypotheses are indeterminate because they are relevantly similar to CH. (shrink)

This paper considers undecidability in the imitation game, the so-called Turing Test. In the Turing Test, a human, a machine, and an interrogator are the players of the game. In our model of the Turing Test, the machine and the interrogator are formalized as Turing machines, allowing us to derive several impossibility results concerning the capabilities of the interrogator. The key issue is that the validity of the Turing test is not attributed to the capability of human or machine, (...) but rather to the capability of the interrogator. In particular, it is shown that no Turing machine can be a perfect interrogator. We also discuss meta-imitation game and imitation game with analog interfaces where both the imitator and the interrogator are mimicked by continuous dynamical systems. (shrink)

We argue that it is fundamentally impossible to recover information about quantum superpositions when a quantum system has interacted with a sufficiently large number of degrees of freedom of the environment. This is due to the fact that gravity imposes fundamental limitations on how accurate measurements can be. This leads to the notion of undecidability: there is no way to tell, due to fundamental limitations, if a quantum system evolved unitarily or suffered wavefunction collapse. This in turn provides a (...) solution to the problem of outcomes in quantum measurement by providing a sharp criterion for defining when an event has taken place. We analyze in detail in examples two situations in which in principle one could recover information about quantum coherence: a) “revivals” of coherence in the interaction of a system with the measurement apparatus and the environment and b) the measurement of global observables of the system plus apparatus plus environment. We show in the examples that the fundamental limitations due to gravity and quantum mechanics in measurement prevent both revivals from occurring and the measurement of global observables. It can therefore be argued that the emerging picture provides a complete resolution to the measurement problem in quantum mechanics. (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)

This essay examines the relationship that obtains between Merleau-Ponty and Derrida through exploring an interesting point of dissension in their respective accounts of decision-making. Merleau-Ponty's early philosophy emphasizes the body-subject's tendency to seek an equilibrium with the world (by acquiring skills and establishing what he refers to as 'intentional arcs'), and towards deciding in an embodied and habitual manner that minimizes any confrontation with what might be termed a decision-making aporia. On the other hand, in his later writings, Derrida frequently (...) points towards a constitutive 'undecidability' involved in decision-making. He insists that a decision, if it is genuinely to be a decision, must involve a leap beyond all prior preparations, and this ensures that an aporia surrounds any attempt to decide. One must always decide without any equilibrium or stability, and yet these are precisely the things that Merleau-Ponty claims that our body moves us towards. Most of this essay will explore the significance of this disparity, and it will be argued that many of Merleau-Ponty's insights challenge the Derridean conception of the undecidability involved in decision-making. This becomes most obvious when comparing the decision-making processes of those expert in a particular field to those who are merely competent (for example chess), and this essay will attempt to establish that the aporia that Derrida discerns can actually be seen to constrict. (shrink)

A version of this paper was presented at the IEEE International Conference on Computational Intelligence, combined meeting of ICNN, FUZZ-IEEE, and ICEC, Orlando, June-July, 1994, and an earlier form of the result is to appear as "The Undecidability of the Spatialized Prisoner's Dilemma" in Theory and Decision . An interactive form of the paper, in which figures are called up as evolving arrays of cellular automata, is available on DOS disk as Research Report #94-04i . An expanded version appears (...) as chapter 6 of The Philosophical Computer. (shrink)

In the spatialized Prisoner's Dilemma, players compete against their immediate neighbors and adopt a neighbor's strategy should it prove locally superior. Fields of strategies evolve in the manner of cellular automata (Nowak and May, 1993; Mar and St. Denis, 1993a,b; Grim 1995, 1996). Often a question arises as to what the eventual outcome of an initial spatial configuration of strategies will be: Will a single strategy prove triumphant in the sense of progressively conquering more and more territory without opposition, or (...) will an equilibrium of some small number of strategies emerge? Here it is shown, for finite configurations of Prisoner's Dilemma strategies embedded in a given infinite background, that such questions are formally undecidable: there is no algorithm or effective procedure which, given a specification of a finite configuration, will in all cases tell us whether that configuration will or will not result in progressive conquest by a single strategy when embedded in the given field. The proof introduces undecidability into decision theory in three steps: by (1) outlining a class of abstract machines with familiar undecidability results, by (2) modelling these machines within a particular family of cellular automata, carrying over undecidability results for these, and finally by (3) showing that spatial configurations of Prisoner's Dilemma strategies will take the form of such cellular automata. (shrink)

The undecidability of the first-order theory of diagonalizable algebras is shown here.

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.

We show that the D A -unification problem is undecidable. That is, given two binary function symbols $\bigoplus$ and $\bigotimes$ , variables and constants, it is undecidable if two terms built from these symbols can be unified provided the following D A -axioms hold: \begin{align*}(x \bigoplus y) \bigotimes z &= (x \bigotimes z) \bigoplus (y \bigotimes z),\\x \bigotimes (y \bigoplus z) &= (x \bigotimes y) \bigoplus (x \bigotimes z),\\x \bigoplus (y \bigoplus z) &= (x \bigoplus y) \bigoplus z.\end{align*} Two terms (...) are D A -unifiable (i.e. an equation is solvable in D A ) if there exist terms to be substituted for their variables such that the resulting terms are equal in the equational theory D A . This is the smallest currently known axiomatic subset of Hilbert's tenth problem for which an undecidability result has been obtained. (shrink)

This essay argues that, in the first Critique, the need for unity leads Kant to re-inscribe the subject in a situation of multiplicity and undecidability. The result, however, is not a relativization that negates the meaning of the subject’s existence, but rather a contextualization that makes meaning possible. This reading clarifies some of the connections between Kant and contemporary postmodernism, especially the work of Jacques Derrida.

In this paper I attempt to clarify a relatively little-studied aspect of Michael Dummett's argument for intuitionism: its use of the notion of ‘undecidable’ sentence. I give a new analysis of this concept in epistemic terms, with which I resolve some puzzles and questions about how it works in the anti-realist critique of classical logic.

We investigate a contractionless naive set theory, due to Grisin [11]. We prove that the theory is undecidable.

We investigate and classify the notion of final derivability of two basic inconsistency-adaptive logics. Specifically, the maximal complexity of the set of final consequences of decidable sets of premises formulated in the language of propositional logic is described. Our results show that taking the consequences of a decidable propositional theory is a complicated operation. The set of final consequences according to either the Reliability Calculus or the Minimal Abnormality Calculus of a decidable propositional premise set is in general undecidable, and (...) can be -complete. These classifications are exact. For first order theories even finite sets of premises can generate such consequence sets in either calculus. (shrink)

The present paper deals with the predicate version MTL of the logic MTL by Esteva and Godo. We introduce a Kripke semantics for it, along the lines of Ono''s Kripke semantics for the predicate version of FLew (cf. [O85]), and we prove a completeness theorem. Then we prove that every predicate logic between MTL and classical predicate logic is undecidable. Finally, we prove that MTL is complete with respect to the standard semantics, i.e., with respect to Kripke frames on the (...) real interval [0,1], or equivalently, with respect to MTL-algebras whose lattice reduct is [0,1] with the usual order. (shrink)

Let S be a deductive system such that S-derivability (s) is arithmetic and sound with respect to structures of class K. From simple conditions on K and s, it follows constructively that the K-completeness of s implies MP(S), a form of Markov's Principle. If s is undecidable then MP(S) is independent of first-order Heyting arithmetic. Also, if s is undecidable and the S proof relation is decidable, then MP(S) is independent of second-order Heyting arithmetic, HAS. Lastly, when s is many-one (...) complete, MP(S) implies the usual Markov's Principle MP.An immediate corollary is that the Tarski, Beth and Kripke weak completeness theorems for the negative fragment of intuitionistic predicate logic are unobtainable in HAS. Second, each of these: weak completeness for classical predicate logic, weak completeness for the negative fragment of intuitionistic predicate logic and strong completeness for sentential logic implics MP. Beth and Kripke completeness for intuitionistic predicate or sentential logic also entail MP. (shrink)

We prove that the two-variable fragment of first-order intuitionistic logic is undecidable, even without constants and equality. We also show that the two-variable fragment of a quantified modal logic L with expanding first-order domains is undecidable whenever there is a Kripke frame for L with a point having infinitely many successors (such are, in particular, the first-order extensions of practically all standard modal logics like K, K4, GL, S4, S5, K4.1, S4.2, GL.3, etc.). For many quantified modal logics, including those (...) in the standard nomenclature above, even the monadic two-variable fragments turn out to be undecidable. (shrink)

It is shown, assuming the linear case of Schinzel's Hypothesis, that the first-order theory of the structure $\langle \omega; +, P\rangle$ , where P is the set of primes, is undecidable and, in fact, that multiplication of natural numbers is first-order definable in this structure. In the other direction, it is shown, from the same hypothesis, that the monadic second-order theory of $\langle\omega; S, P\rangle$ is decidable, where S is the successor function. The latter result is proved using a general (...) result of A. L. Semenov on decidability of monadic theories, and a proof of Semenov's result is presented. (shrink)

If a formal theory T is able to reason about its own syntax, then the diagonalizable algebra of T is defined as its Lindenbaum sentence algebra endowed with a unary operator □ which sends a sentence φ to the sentence □φ asserting the provability of φ in T. We prove that the first order theories of diagonalizable algebras of a wide class of theories are undecidable and establish some related results.

Using a result of Gurevich and Lewis on the word problem for finite semigroups, we give short proofs that the following theories are hereditarily undecidable: (1) finite graphs of vertex-degree at most 3; (2) finite nonvoid sets with two distinguished permutations; (3) finite-dimensional vector spaces over a finite field with two distinguished endomorphisms.

Recently, Lincoln, Scedrov and Shankar showed that the multiplicative fragment of second order intuitionistic linear logic is undecidable, using an encoding of second order intuitionistic logic. Their argument applies to the multiplicative-additive fragment, but it does not work in the classical case, because second order classical logic is decidable. Here we show that the multiplicative-additive fragment of second order classical linear logic is also undecidable, using an encoding of two-counter machines originally due to Kanovich. The faithfulness of this encoding is (...) proved by means of the phase semantics. (shrink)

Some have suggested that certain classical physical systems have undecidable long-term behavior, without specifying an appropriate notion of decidability over the reals. We introduce such a notion, decidability in (or d- ) for any measure , which is particularly appropriate for physics and in some ways more intuitive than Ko's (1991) recursive approximability (r.a.). For Lebesgue measure , d- implies r.a. Sets with positive -measure that are sufficiently "riddled" with holes are never d- but are often r.a. This explicates Sommerer (...) and Ott's (1996) claim of uncomputable behavior in a system with riddled basins of attraction. Furthermore, it clarifies speculations that the stability of the solar system (and similar systems) may be undecidable, for the invariant tori established by KAM theory form sets that are not d-. (shrink)

This paper concerns Alan Turing’s ideas about machines, mathematical methods of proof, and intelligence. By the late 1930s, Kurt Gödel and other logicians, including Turing himself, had shown that no finite set of rules could be used to generate all true mathematical statements. Yet according to Turing, there was no upper bound to the number of mathematical truths provable by intelligent human beings, for they could invent new rules and methods of proof. So, the output of a human mathematician, for (...) Turing, was not a computable sequence (i.e., one that could be generated by a Turing machine). Since computers only contained a finite number of instructions (or programs), one might argue, they could not reproduce human intelligence. Turing called this the “mathematical
objection” to his view that machines can think. Logico-mathematical reasons, stemming from his own work, helped to convince Turing that it should be possible to reproduce human intelligence, and eventually compete with it, by developing the appropriate kind of digital computer. He felt it
should be possible to program a computer so that it could learn or discover new rules, overcoming the limitations imposed by the incompleteness and undecidability results in the same way that human
mathematicians presumably do. (shrink)

In Episode 1, we introduced the very idea of a negation-incomplete formalized theory T . We noted that if we aim to construct a theory of basic arithmetic, we’ll ideally like the theory to be able to prove all the truths expressible in the language of basic arithmetic, and hence to be negation complete. But Gödel’s First Incompleteness Theorem says, very roughly, that a nice theory T containing enough arithmetic will always be negation incomplete. Now, the Theorem comes in two (...) flavours, depending on whether we cash out the idea of being ‘nice enough’ in terms of (i) the semantic idea of T ’s being a sound theory, or (ii) the idea of odel’s own T ’s being a consistent theory which proves enough arithmetic. And we noted that G¨. (shrink)

This paper deals with Derrida's analysis of Kant's Critique of Judgment in his essay 'Economimesis'. I argue that Derrida's analysis of Kant's aesthetics can be used to describe the aporia within Kantian politics between rebellion and progressive revolutionary acts. The focus of my argument falls on examining how the recent debate over Derrida's ethics can be usefully considered from the background of this treatment of Kant. In particular, the analysis Derrida gives of Kant's aesthetics commits him to a series of (...) conceptual constraints that can be detected in his recent commentaries on 'forgiveness' and 'hospitality'. I suggest that these recent commentaries on political topics also depart from his earlier practice of ethics in 'Economimesis' as a 'witnessing' of the particular. This departure can be clearly seen once the Kantian background to Derrida's recent writing is set out. (shrink)

Algorithmic information theory, or the theory of Kolmogorov complexity, has become an extraordinarily popular theory, and this is no doubt due, in some part, to the fame of Chaitin’s incompleteness results arising from this field. Actually, there are two rather different results by Chaitin: the earlier one concerns the finite limit of the provability of complexity (see Chaitin, 1974a, 1974b, 1975a); and the later is related to random reals and the halting probability (see Chaitin, 1986, 1987a, 1987b, 1988, 1989.

We present some recent technical results of us on the incompleteness of classical analysis and then discuss our work on the Arnol'd decision problems for the stability of fixed points of dynamical systems.

This paper uses the recent ‘network film’ of Mateo Garrone Gomorrah in order to let Alain Badiou’s theory of subjectivization-in-decision percolate through the immanent networks of contemporary ‘risk societies’ and the narrative structures through which they find expression in cinema. Adumbrating a tension between choices and decisions I seek to create ‘edges’ between two worlds that in the most part of Badiou’s work have been decisively and platonically separated: the world of being and the one of our embodied social experience. (...) Cinema lends its dynamical and ‘tensed’ mediation in order for this new and open topology to be explored. (shrink)

This paper explores how providing the inferential basis to argue for a range of equally plausible interpretations features as a way of managing issues of accountability in talk about armed confrontation. We examine conversation produced in open-ended interviews with diplomatic representatives of the United States and Great Britain in discussion about those countries'' involvement in the Persian Gulf conflict of 1990–91. By providing the inferential basis upon which to argue for a range of equally plausible interpretative scenarios, speakers attend to (...) the potential for any one account to be privileged over another. Further, in speculating upon the relationship between interpretative particulars and the inferential outcome to be drawn for some specific version of events in question, speakers work to establish the parameters of an admissible narrative trajectory with which to account for those events. In so doing, they manage the implications that excluded versions would otherwise make relevant. (shrink)

In dynamic epistemic logic and other fields, it is natural to consider relativization as an operator taking sentences to sentences. When using the ideas and methods of dynamic logic, one would like to iterate operators. This leads to iterated relativization. We are also concerned with the transitive closure operation, due to its connection to common knowledge. We show that for three fragments of the logic of iterated relativization and transitive closure, the satisfiability problems are fi1 11–complete. Two of these fragments (...) do not include transitive closure. We also show that the question of whether a sentence in these fragments has a finite (tree) model is fi0 01–complete. These results go via reduction to problems concerning domino systems. (shrink)

We present some recent technical results of us on the incompleteness of classical analysis and then discuss our work on the Arnol'd decision problems for the stability of fixed points of dynamical systems.

There is no uniquely standard concept of an effectively decidable set of real numbers or real n-tuples. Here we consider three notions: decidability up to measure zero [M.W. Parker, Undecidability in Rn: Riddled basins, the KAM tori, and the stability of the solar system, Phil. Sci. 70(2) (2003) 359–382], which we abbreviate d.m.z.; recursive approximability [or r.a.; K.-I. Ko, Complexity Theory of Real Functions, Birkhäuser, Boston, 1991]; and decidability ignoring boundaries [d.i.b.; W.C. Myrvold, The decision problem for entanglement, in: (...) R.S. Cohen et al. (Eds.), Potentiality, Entanglement, and Passion-at-a-Distance: Quantum Mechanical Studies fo Abner Shimony, Vol. 2, Kluwer Academic Publishers, Great Britain, 1997, pp. 177–190]. Unlike some others in the literature, these notions apply not only to certain nice sets, but to general sets in Rn and other appropriate spaces. We consider some motivations for these concepts and the logical relations between them. It has been argued that d.m.z. is especially appropriate for physical applications, and on Rn with the standard measure, it is strictly stronger than r.a. [M.W. Parker, Undecidability in Rn: Riddled basins, the KAM tori, and the stability of the solar system, Phil. Sci. 70(2) (2003) 359–382]. Here we show that this is the only implication that holds among our three decidabilities in that setting. Under arbitrary measures, even this implication fails. Yet for intervals of non-zero length, and more generally, convex sets of non-zero measure, the three concepts are equivalent. (shrink)

The goal of this thesis is to undo those assumptions about understanding and the doxastic and social relationships that are concomitant with those assumptions, while offering a different way of construing understanding that is conducive to allowing Christian religious educators to move forward in their work, especially as that work concerns intergenerational strife. This rewriting of our notions of understanding and relationship will be in a direction wherein thedistinctions between faith, knowledge, self-understanding, enculturation, and ethical choice are blurred. Accordingly, this (...) thesis finds the concern with many of those interdisciplinary approaches to the study of philosophy, theology, and education that have been influenced by both Korean Christian religious education and its radical, deconstructive re-positionings. The thesis also attempts to reflexively deploy such approaches throughout. (shrink)

"A valuable collection both for original source material as well as historical formulations of current problems."-- The Review of Metaphysics "Much more than a mere collection of papers . . . a valuable addition to the literature."-- Mathematics of Computation An anthology of fundamental papers on undecidability and unsolvability by major figures in the field, this classic reference opens with Godel's landmark 1931 paper demonstrating that systems of logic cannot admit proofs of all true assertions of arithmetic. Subsequent papers (...) by Godel, Church, Turing, and Post single out the class of recursive functions as computable by finite algorithms. Additional papers by Church, Turing, and Post cover unsolvable problems from the theory of abstract computing machines, mathematical logic, and algebra, and material by Kleene and Post includes initiation of the classification theory of unsolvable problems. Suitable for graduate and undergraduate courses. 1965 ed. (shrink)

Although Church and Turing presented their path-breaking undecidability results immediately after their explication of effective decidability in 1936, it has been generally felt that these results do not have any direct bearing on ordinary mathematics but only contribute to logic, metamathematics and the theory of computability. Therefore it was such a celebrated achievement when Yuri Matiyasevich in 1970 demonstrated that the problem of the solvability of Diophantine equations is undecidable. His work was building essentially on the earlier work by (...) Julia Robinson, Martin Davis and Hilary Putnam (1961), who had showed that the problem of solvability of exponential Diophantine equations is undecidable. One should note, however, that although it was only Matiyasevich’s result which finally solved Hilbert’s tenth problem, already the earlier result had provided a perfectly natural problem of ordinary number theory which is undecidable. (shrink)

This book is well known for its proof that many mathematical systems - including lattice theory and closure algebras - are undecidable. It consists of three treatises from one of the greatest logicians of all time: "A General Method in Proofs of Undecidability," "Undecidability and Essential Undecidability in Mathematics," and "Undecidability of the Elementary Theory of Groups.".

We prove the hereditary undecidability of the L t theories of: (1) torsion-free Hausdorff topological abelian groups; (2) locally pure Hausdorff topological abelian groups.

In this paper we give short proofs to the undecidability of the τ-theory for free groups and other relevant theories.

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)

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

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)

With each projective geometry we can associate a Lyndon algebra. Such an algebra always satisfies Tarski's axioms for relation algebras and Lyndon algebras thus form an interesting connection between the fields of projective geometry and algebraic logic. In this paper we prove that if G is a class of projective geometries which contains an infinite projective geometry of dimension at least three, then the class L(G) of Lyndon algebras associated with projective geometries in G has an undecidable equational theory. In (...) our proof we develop and use a connection between projective geometries and diagonal-free cylindric algebras. (shrink)

Let $ be the restriction of usual order relation to integers which are primes or squares of primes, and let ⊥ denote the coprimeness predicate. The elementary theory of $\langle\mathbb{N};\bot, , is undecidable. Now denote by $ the restriction of order to primary numbers. All arithmetical relations restricted to primary numbers are definable in the structure $\langle\mathbb{N};\bot, . Furthermore, the structures $\langle\mathbb{N};\mid, and $\langle\mathbb{N};=,+,x\rangle$ are interdefinable.

We give an overview of decidability results for modal logics having a binary modality. We put an emphasis on the demonstration of proof-techniques, and hope that this will also help in finding the borderlines between decidable and undecidable fragments of usual first-order logic.

In this paper we show that relativized versions of relation set algebras and cylindric set algebras have undecidable equational theories if we include coordinatewise versions of the counting operations into the similarity type. We apply these results to the guarded fragment of first-order logic.

We prove that the first order theory of the fixed point algebra corresponding to an r.e. consistent theory containing arithmetic is hereditarily undecidable.

We show that the partial order of Σ0 3-sets under inclusion is elementarily definable with parameters in the semilattice of r.e. wtt-degrees. Using a result of E. Herrmann, we can deduce that this semilattice has an undecidable theory, thereby solving an open problem of P. Odifreddi.

Let k and l be two multiplicatively independent integers, and let $L \subseteq \mathbb{N}^n$ be a l-recognizable set which is not definable in $\langle\mathbb{N}; +\rangle$ . We prove that the elementary theory of $\langle\mathbb{N}; +, V_k, L\rangle$ , where V k (x) denotes the greatest power of k dividing x, is undecidable. This result leads to a new proof of the Cobham-Semënov theorem.

We construct a decidable first-order theory T such that the theory of its finite models is undecidable. Moreover, T will be equationally axiomatizable and of finite type.

If K is a class of semiassociative relation algebras and K contains the relation algebra of all binary relations on a denumerable set, then the word problem for the free algebra over K on one generator is unsolvable. This result implies that the set of sentences which are provable in the formalism Lwx is an undecidable theory. A stronger algebraic result shows that the set of logically valid sentences in Lwx forms a hereditarily undecidable theory in Lwx. These results generalize (...) similar theorems, due to Tarski, concerning relation algebras and the formalism Lx. (shrink)

In this paper I discuss William J. Clifford's principle, "It is wrong always, everywhere, and for anyone, to believe anything upon insufficient evidence" and an objection to it based on William James's contention that "Our passional nature not only lawfully may, but must, decide an option between propositions, whenever it is a genuine option that cannot by its nature be decided on intellectual grounds." I argue that on one central way of understanding the key terms, there are no genuine options (...) that cannot be decided on intellectual grounds. I also argue that there is another way to understand the terms so that there are cases of the sort James describes, but then, as an objection to Clifford, the argument is needlessly complex, invoking concepts such as genuine options and intellectual undecidability, that play no crucial role. (shrink)

This introduction to mathematical logic starts with propositional calculus and first-order logic. Topics covered include syntax, semantics, soundness, completeness, independence, normal forms, vertical paths through negation normal formulas, compactness, Smullyan's Unifying Principle, natural deduction, cut-elimination, semantic tableaux, Skolemization, Herbrand's Theorem, unification, duality, interpolation, and definability. The last three chapters of the book provide an introduction to type theory (higher-order logic). It is shown how various mathematical concepts can be formalized in this very expressive formal language. This expressive notation facilitates proofs (...) of the classical incompleteness and undecidability theorems which are very elegant and easy to understand. The discussion of semantics makes clear the important distinction between standard and nonstandard models which is so important in understanding puzzling phenomena such as the incompleteness theorems and Skolem's Paradox about countable models of set theory. Some of the numerous exercises require giving formal proofs. A computer program called ETPS which is available from the web facilitates doing and checking such exercises. Audience: This volume will be of interest to mathematicians, computer scientists, and philosophers in universities, as well as to computer scientists in industry who wish to use higher-order logic for hardware and software specification and verification. (shrink)

This is a free book, 165 pages. It is for anyone who has had a solid introductory logic course and wants more. Topics covered include soundness and completeness for first-order logic, Tarski's theorem on the undefinability of truth, Gödel's incompleteness theorems, the undecidability of first-order logic, a smattering of second-order logic, and modal logic (both propositional and quantificational). I wrote it for use in my own course, because I thought I could present the most important results and concepts more (...) clearly than the available textbooks. (shrink)

Kurt Godel, the greatest logician of our time, startled the world of mathematics in 1931 with his Theorem of Undecidability, which showed that some statements in mathematics are inherently "undecidable." His work on the completeness of logic, the incompleteness of number theory, and the consistency of the axiom of choice and the continuum theory brought him further worldwide fame. In this introductory volume, Raymond Smullyan, himself a well-known logician, guides the reader through the fascinating world of Godel's incompleteness theorems. (...) The level of presentation is suitable for anyone with a basic acquaintance with mathematical logic. As a clear, concise introduction to a difficult but essential subject, the book will appeal to mathematicians, philosophers, and computer scientists. (shrink)

How to introduce 'politics' as a specific concept within a deconstructive style of thinking? In order to answer this question, this contribution compares Derrida with Laclau. According to the former the starting-point of a deconstructive style of thinking is différance. It links together the economic detour of homecoming and the relation to otherness. Laclau's analysis of politics as hegemonization within a situation of undecidability presupposes this notion of différance and can therefore be useful in introducing politics within a deconstructive (...) style of thinking. But there still is a major difference between Derrida and Laclau's decisionism: if différance as the relation without relation of economy and otherness cannot avoid decisions based on power in order to stabilize the social, these decisions are always marked by passivity and therefore deconstructible in the name of 'justice' that exceeds politics even if it takes place nowhere but within politics. Key Words: decisionism • . Derrida • . hegemony • . Laclau • . law. (shrink)

How do we prove true but unprovable propositions? Gödel produced a statement whose undecidability derives from its ad hoc construction. Concrete or mathematical incompleteness results are interesting unprovable statements of formal arithmetic. We point out where exactly the unprovability lies in the ordinary ‘mathematical’ proofs of two interesting formally unprovable propositions, the Kruskal-Friedman theorem on trees and Girard's normalization theorem in type theory. Their validity is based on robust cognitive performances, which ground mathematics in our relation to space and (...) time, such as symmetries and order, or on the generality of Herbrand's notion of ‘prototype proof’. (shrink)

What can computers do in principle? What are their inherent theoretical limitations? These are questions to which computer scientists must address themselves. The theoretical framework which enables such questions to be answered has been developed over the last fifty years from the idea of a computable function: intuitively a function whose values can be calculated in an effective or automatic way. This book is an introduction to computability theory (or recursion theory as it is traditionally known to mathematicians). Dr Cutland (...) begins with a mathematical characterisation of computable functions using a simple idealised computer (a register machine); after some comparison with other characterisations, he develops the mathematical theory, including a full discussion of non-computability and undecidability, and the theory of recursive and recursively enumerable sets. The later chapters provide an introduction to more advanced topics such as Gildel's incompleteness theorem, degrees of unsolvability, the Recursion theorems and the theory of complexity of computation. Computability is thus a branch of mathematics which is of relevance also to computer scientists and philosophers. Mathematics students with no prior knowledge of the subject and computer science students who wish to supplement their practical expertise with some theoretical background will find this book of use and interest. (shrink)

Deductive inference is usually regarded as being “tautological” or “analytical”: the information conveyed by the conclusion is contained in the information conveyed by the premises. This idea, however, clashes with the undecidability of first-order logic and with the (likely) intractability of Boolean logic. In this article, we address the problem both from the semantic and the proof-theoretical point of view. We propose a hierarchy of propositional logics that are all tractable (i.e. decidable in polynomial time), although by means of (...) growing computational resources, and converge towards classical propositional logic. The underlying claim is that this hierarchy can be used to represent increasing levels of “depth” or “informativeness” of Boolean reasoning. Special attention is paid to the most basic logic in this hierarchy, the pure “intelim logic”, which satisfies all the requirements of a natural deduction system (allowing both introduction and elimination rules for each logical operator) while admitting of a feasible (quadratic) decision procedure. We argue that this logic is “analytic” in a particularly strict sense, in that it rules out any use of “virtual information”, which is chiefly responsible for the combinatorial explosion of standard classical systems. As a result, analyticity and tractability are reconciled and growing degrees of computational complexity are associated with the depth at which the use of virtual information is allowed. (shrink)

We first state a few previously obtained results that lead to general undecidability and incompleteness theorems in axiomatized theories that range from the theory of finite sets to classical elementary analysis. Out of those results we prove several incompleteness theorems for axiomatic versions of the theory of noncooperative games with Nash equilibria; in particular, we show the existence of finite games whose equilibria cannot be proven to be computable.

This paper is about different types of silence, and about differing processes of philosophical investigation and sagely illumination. It is argued that the sagely Dao of wu wei leads to silence in the sense of no spoken words, and the philosophical way of proof leads to silence in the sense of no spoken words. So both proof and wu wei both lead to silence in the sense of no spoken words. Accordingly there is a type of silence that results from (...) the explosive process of philosophical argumentation and reduction to no spoken words because of undecidability, and there is also a type of silence that results from the implosive process of sagely silence and reversion to silent illumination with no spoken words. However, the silence of explosion and the silence of implosion differ as regards processes of reduction and reversion respectively. Therefore, proof and wu wei both lead to silence in the sense of no spoken words, but the type of silence resulting from the explosive process of philosophical argumentation and reduction to no spoken words because of undecidability and the type of silence resulting from the implosive process of sagely silence and reversion to silent illumination because of the incommunicability of Dao differ. (shrink)