Undecidability

I give a detailed review of 'The Outer Limits of Reason' by Noson Yanofsky from a unified perspective of Wittgenstein and evolutionary psychology. I indicate that the difficulty with such issues as paradox in language and math, incompleteness, undecidability, computability, the brain and the universe as computers etc., all arise from the failure to look carefully at our use of language in the appropriate context and hence the failure to separate issues of scientific fact from issues of how language works. (...) I discuss Wittgenstein's views on incompleteness, paraconsistency and undecidability and the work of Wolpert on the limits to computation. To sum it up: The Universe According to Brooklyn---Good Science, Not So Good Philosophy. -/- Those wishing a comprehensive up to date framework for human behavior from the modern two systems view may consult my book ‘The Logical Structure of Philosophy, Psychology, Mind and Language in Ludwig Wittgenstein and John Searle’ 2nd ed (2019). Those interested in more of my writings may see ‘Talking Monkeys--Philosophy, Psychology, Science, Religion and Politics on a Doomed Planet--Articles and Reviews 2006-2019 3rd ed (2019) and Suicidal Utopian Delusions in the 21st Century 4th ed (2019) . (shrink)

Introduction to mathematical logic, part 2.Textbook for students in mathematical logic and foundations of mathematics. Platonism, Intuition, Formalism. Axiomatic set theory. Around the Continuum Problem. Axiom of Determinacy. Large Cardinal Axioms. Ackermann's Set Theory. First order arithmetic. Hilbert's 10th problem. Incompleteness theorems. Consequences. Connected results: double incompleteness theorem, unsolvability of reasoning, theorem on the size of proofs, diophantine incompleteness, Loeb's theorem, consistent universal statements are provable, Berry's paradox, incompleteness and Chaitin's theorem. Around Ramsey's theorem.

In this paper, I recreate a paradox from my earlier work (“Paradox with just self-reference”) albeit entirely within the language of arithmetic. (In lieu of self-referential expressions, Gödel numbering is used to generate the paradox.) This can suggest that Robinson arithmetic and its extensions are unsound; however, I claim instead that the metalanguage may be to blame, owing to arithmetization of syntax. If so, then the moral would be to restrict arithmetization in the metalanguage somehow, rather than distrust the arithmetical (...) theory in the object language. (shrink)

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 signature of the formal language of mereotopology contains two predicates $P$ and $C$, which stand for “being a part of” and “contact,” respectively. This paper will deal with the decidability issue of the mereotopological theories which can be formed by the axioms found in the literature. Three main results to be given are as follows: all axiomatized mereotopological theories are separable; all mereotopological theories up to $\mathbf{ACEMT}$, $\mathbf{SACEMT}$, or $\mathbf{SACEMT}^{\prime}$ are finitely inseparable; all axiomatized mereotopological theories except $\mathbf{SAX}$, $\mathbf{SAX}^{\prime}$, (...) or $\mathbf{S\overline{B}X}^{\prime}$, where $\mathbf{X}$ is strictly stronger than $\mathbf{CEMT}$, are undecidable. Then it can also be easily seen that all axiomatized mereotopological theories proved to be undecidable here are neither essentially undecidable nor strongly undecidable but are hereditarily undecidable. Result will be shown by constructing strongly undecidable mereotopological structures based on two-dimensional Euclidean space, and it will be pointed out that the same construction cannot be carried through if the language is not rich enough. (shrink)

The signature of the formal language of mereology contains only one binary predicate which stands for the relation “being a part of” and it has been strongly suggested that such a predicate must at least define a partial ordering. Mereological theories owe their origin to Leśniewski. However, some more recent authors, such as Simons as well as Casati and Varzi, have reformulated mereology in a way most logicians today are familiar with. It turns out that any theory which can be (...) formed by using the reformulated mereological axioms or axiom schemas is in a sense a subtheory of the elementary theory of Boolean algebras or of the theory of infinite atomic Boolean algebras. It is known that the theory of partial orderings is undecidable while the elementary theory of Boolean algebras and the theory of infinite atomic Boolean algebras are decidable. In this paper, I will look into the behaviors in terms of decidability of those mereological theories located in between. More precisely, I will give a comprehensive picture of the said issue by offering solutions to the open problems which I have raised in some of my papers published previously. (shrink)

Quite a few results concerning the decidability of mereological theories have been given in my previous paper. But many mereological theories are still left unaccounted for. In this paper I will refine a general method for proving the undecidability of a theory and then by making use of it, I will show that most mereological theories that are strictly weaker than CEM are finitely inseparable and hence undecidable. The same results might be carried over to some extensions of those weak (...) theories by adding the fusion axiom schema. Most of the proofs to be presented in this paper take finite lattices as the base models when applying the refined method. However, I shall also point out the limitation of this kind of reduction and make some observations and conjectures concerning the decidability of stronger mereological theories. (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 formalist philosophy of mathematics (in its purest, most extreme version) is widely regarded as a “discredited position”. This pure and extreme version of formalism is called by some authors “game formalism”, because it is alleged to represent mathematics as a meaningless game with strings of symbols. Nevertheless, I would like to draw attention to some arguments in favour of game formalism as an appropriate philosophy of real mathematics. For the most part, these arguments have not yet been used or (...) were neglected in past discussions. (shrink)

I have read many recent discussions of the limits of computation and the universe as computer, hoping to find some comments on the amazing work of polymath physicist and decision theorist David Wolpert but have not found a single citation and so I present this very brief summary. Wolpert proved some stunning impossibility or incompleteness theorems (1992 to 2008-see arxiv.org) on the limits to inference (computation) that are so general they are independent of the device doing the computation, and even (...) independent of the laws of physics, so they apply across computers, physics, and human behavior. They make use of Cantor's diagonalization, the liar paradox and worldlines to provide what may be the ultimate theorem in Turing Machine Theory, and seemingly provide insights into impossibility, incompleteness, the limits of computation,and the universe as computer, in all possible universes and all beings or mechanisms, generating, among other things,a non- quantum mechanical uncertainty principle and a proof of monotheism. There are obvious connections to the classic work of Chaitin, Solomonoff, Komolgarov and Wittgenstein and to the notion that no program (and thus no device) can generate a sequence (or device) with greater complexity than it possesses. One might say this body of work implies atheism since there cannot be any entity more complex than the physical universe and from the Wittgensteinian viewpoint, ‘more complex’ is meaningless (has no conditions of satisfaction, i.e., truth-maker or test). Even a ‘God’ (i.e., a ‘device’ with limitless time/space and energy) cannot determine whether a given ‘number’ is ‘random’ nor can find a certain way to show that a given ‘formula’, ‘theorem’ or ‘sentence’ or ‘device’ (all these being complex language games) is part of a particular ‘system’. -/- Those wishing a comprehensive up to date framework for human behavior from the modern two systems view may consult my article The Logical Structure of Philosophy, Psychology, Mind and Language as Revealed in Wittgenstein and Searle 59p(2016). For all my articles on Wittgenstein and Searle see my e-book ‘The Logical Structure of Philosophy, Psychology, Mind and Language in Wittgenstein and Searle 367p (2016). Those interested in all my writings in their most recent versions may consult my e-book Philosophy, Human Nature and the Collapse of Civilization - Articles and Reviews 2006-2016’ 662p (2016). -/- All of my papers and books have now been published in revised versions both in ebooks and in printed books. -/- Talking Monkeys: Philosophy, Psychology, Science, Religion and Politics on a Doomed Planet - Articles and Reviews 2006-2017 (2017) https://www.amazon.com/dp/B071HVC7YP. -/- The Logical Structure of Philosophy, Psychology, Mind and Language in Ludwig Wittgenstein and John Searle--Articles and Reviews 2006-2016 (2017) https://www.amazon.com/dp/B071P1RP1B. -/- Suicidal Utopian Delusions in the 21st century: Philosophy, Human Nature and the Collapse of Civilization - Articles and Reviews 2006-2017 (2017) https://www.amazon.com/dp/B0711R5LGX . (shrink)

We consider a seemingly popular justification (we call it the Re-flexivity Defense) for the third derivability condition of the Hilbert-Bernays-Löb generalization of Godel's Second Incompleteness Theorem (G2). We argue that (i) in certain settings (rouglily, those where the representing theory of an arithmetization is allowed to be a proper subtheory of the represented theory), use of the Reflexivity Defense to justify the tliird condition induces a fourth condition, and that (ii) the justification of this fourth condition faces serious obstacles. We (...) conclude that, in the types of settings mentioned, the Reflexivity Defense does not justify the usual ‘reading’ of G2—namely, that the consistency of the represented theory is not provable in the representing theory. (shrink)

In this paper the modal operator "x is provable in Peano Arithmetic" is incorporated into first-order theories. A provability extension of a theory is defined. Presburger Arithmetic of addition, Skolem Arithmetic of multiplication, and some first order theories of partial consistency statements are shown to remain decidable after natural provability extensions. It is also shown that natural provability extensions of a decidable theory may be undecidable.

A proof is presented that a form of incompleteness in Quantum Mechanics follows directly from the use of unbounded operators. It is then shown that the problems that arise for such operators are not connected to the non- commutativity of many pairs of operators in Quantum Mechanics and hence are an additional source of incompleteness to that which allegedly flows from the..

Full proofs of the Gödel incompleteness theorems are highly intricate affairs. Much of the intricacy lies in the details of setting up and checking the properties of a coding system representing the syntax of an object language (typically, that of arithmetic) within that same language. These details are seldom illuminating and tend to obscure the core of the argument. For this reason a number of efforts have been made to present the essentials of the proofs of Gödel’s theorems without getting (...) mired in syntactic or computational details. One of the most important of these efforts was made by Löb [8] in connection with his analysis of sentences asserting their own provability. Löb formulated three conditions (now known as the Hilbert-Bernays-Löb derivability conditions), on the provability predicate in a formal system which are jointly sufficient to yield the Gödel’s second incompleteness theorem for it. A key role in Löb’s analysis is played by (a special case of) what later became known as the diagonalization or fixed point property of formal systems, a property which had already, in essence, been exploited by Gödel in his original proofs of the incompleteness theorems. The fixed point property plays a central role in Lawvere’s [7] category-theoretic account of incompleteness phenomena (see also [10]). Incompleteness theorems have also been subjected to intensive investigation within the framework of modal logic (see, e.g.[4], [5]). In this formulation the modal operator takes up the role previously played by the provability predicate, and the derivability conditions on the latter are translated into algebraic conditions (the so-called GL, i.e., Gödel–Löb, conditions) on the former. My purpose here is to present a framework for incompleteness phenomena, fully compatible with intuitionistic or constructive principles, in which the idea of a coding system is retained, only in a 2 simple, but very general form, a form wholly free of syntactical notions. As codes we shall take the elements of an arbitrary given nonempty set, possibly, but not necessarily, the set of natural numbers.. (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)

An interpretation of Wittgenstein’s much criticized remarks on Gödel’s First Incompleteness Theorem is provided in the light of paraconsistent arithmetic: in taking Gödel’s proof as a paradoxical derivation, Wittgenstein was drawing the consequences of his deliberate rejection of the standard distinction between theory and metatheory. The reasoning behind the proof of the truth of the Gödel sentence is then performed within the formal system itself, which turns out to be inconsistent. It is shown that the features of paraconsistent arithmetics match (...) with some intuitions underlying Wittgenstein’s philosophy of mathematics, such as its strict finitism and the insistence on the decidability of any mathematical question. (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)