Search

We consider the thesis that an arithmetical relation, which holds for any, given, assignment of natural numbers to its free variables, is Turing-decidable if, and only if, it is the standard representation of a PA-provable formula. We show that, classically, such a thesis is, both, unverifiable and irrefutable, and, that it implies the Turing Thesis is false; that Goedel's arithmetical predicate R(x), treated as a Boolean function, is in the complexity class NP, but not in P; and that the Halting problem is effectively solvable, albeit not algorithmically., Comment: 12 pages; an HTML version is available at http://alixcomsi.com/Is_the_Halting_problem.htm

Classical theory proves that every primitive recursive function is strongly representable in PA; that formal Peano Arithmetic, PA, and formal primitive recursive arithmetic, PRA, can both be interpreted in Zermelo-Fraenkel Set Theory, ZF; and that if ZF is consistent, then PA+PRA is consistent. We show that PA+PRA is inconsistent; it follows that ZF, too, is inconsistent., Comment: rev1; typos corrected in formulas; 5 pages; an HTML version is available at http://alixcomsi.com/An_arguable_inconsistency_in_ZF.htm

We consider the immediate consequence of an arguable addition to the standard Deduction Theorems of first order theories., Comment: 9 pages; an HTML version is available at http://alixcomsi.com/An_arguable_addition.htm

Classical interpretations of Goedel's formal reasoning imply that the truth of some arithmetical propositions of any formal mathematical language, under any interpretation, is essentially unverifiable. However, a language of general, scientific, discourse cannot allow its mathematical propositions to be interpreted ambiguously. Such a language must, therefore, define mathematical truth verifiably. We consider a constructive interpretation of classical, Tarskian, truth, and of Goedel's reasoning, under which any formal system of Peano Arithmetic is verifiably complete. We show how some paradoxical concepts of Quantum mechanics can be expressed, and interpreted, naturally under a constructive definition of mathematical truth., Comment: 73 pages; this is an updated version of the NQ essay; an HTML version is available at http://alixcomsi.com/Do_Goedel_incompleteness_theorems.htm

Goodstein's argument is essentially that the hereditary representation m_{[b]} of any given natural number m in the natural number base b can be mirrored in Cantor Arithmetic, and used to well-define a finite decreasing sequence of transfinite ordinals, each of which is not smaller than the ordinal corresponding to the corresponding member of Goodstein's sequence of natural numbers G(m). The standard interpretation of this argument is first that G(m) must therefore converge; and second that this conclusion---Goodstein's Theorem---is unprovable in Peano Arithmetic but true under the standard interpretation of the Arithmetic. We argue however that even assuming Goodstein's Theorem is indeed unprovable in PA, its truth must nevertheless be an intuitionistically unobjectionable consequence of some constructive interpretation of Goodstein's reasoning. We consider such an interpretation, and construct a Goodstein functional sequence to highlight why the standard interpretation of Goodstein's argument ought not to be accepted as a definitive property of the natural numbers., Comment: v5; minor editing; 17 pages; new Lemma 6; graph of terminating Goodstein sequences included; major revision of notation on 20/04/2011; an updated version is available at http://alixcomsi.com/Index01.pdf

If we assume the Thesis that any classical Turing machine T, which halts on every n-ary sequence of natural numbers as input in a determinate time t(n), determines a PA-provable formula, whose standard interpretation is an n-ary arithmetical relation f(x1, ..., xn) that holds if, and only if, T halts, then we can define Laplace's formula recursively such that it can model the state of a deterministic quantum universe that is irreducibly probabilistic., Comment: 27 pages; an HTML version is available at http://alixcomsi.com/Can_Laplace's_formula.htm

Standard interpretations of Goedel's "undecidable" proposition, [(Ax)R(x)], argue that, although [~(Ax)R(x)] is PA-provable if [(Ax)R(x)] is PA-provable, we may not conclude from this that [~(Ax)R(x)] is PA-provable. We show that such interpretations are inconsistent with a standard Deduction Theorem of first order theories., Comment: 12 pages; an HTML version is available at http://alixcomsi.com/How_definitive_is_the_standard.htm

In a recent historical overview, Cristian S. Calude, Elena Calude, and Solomon Marcus identify eight stages in the development of the concept of a mathematical proof in support of an ambitious conjecture: we can express classical mathematical concepts adequately only in a mathematical language in which both truth and provability are essentially unverifiable. In this paper we show, firstly, that the concepts underlying their thesis can, however, be interpreted constructively; and, secondly, that an implicit thesis in the authors' arguments implies that the probability of a given Turing machine halting on a given input cannot be expressed as a Dedekind real number., Comment: 32 pages; an HTML version is available at http://alixcomsi.com/index01.htm

We argue that, although Wittgenstein's reservations on Goedel's interpretation of his own formal reasoning are, indeed, of historical importance, the uneasiness that academicians and philosophers continue to sense, and express, over standard interpretations of Goedel's formal reasoning - even seventy years after the publication of his seminal 1931 paper - is of much greater significance, and relevance, to us today., Comment: 40 pages; an HTML version is available at http://alixcomsi.com/index01.htm

In a forthcoming book, professional computer scientist and physicist Paul Budnik presents an exposition of classical mathematical theory as the backdrop to an elegant thesis: we can interpret any model of a formal system of Peano Arithmetic in an appropriate, digital, computational language. In this paper we attempt - without addressing the question of whether or not Budnik succeeds in establishing his thesis convincingly - to identify dogmas of standard interpretations of classical mathematical theory that appear to be implicit in Budnik's exposition, and to correspond to them dogmas of a constructive interpretation of classical theory., Comment: 40 pages; an HTML version is available at http://alixcomsi.com/Can_we_express_every_transfinite.htm

We present some arguments for the thesis that a set-theoretic inspired faith, in the ability of intuitive truth to faithfully reflect relationships between elements of a Platonic universe, may be as misplaced as an assumption that such truth cannot be expressed in a constructive, and effectively verifiable, manner., Comment: v2; revised para 2.2(ix); introduced standardised ACI compliant notation for citations; 24 pages; an HTML version is available at http://alixcomsi.com/The_formal_roots_of_Platonism.htm

If we define classical foundational concepts constructively, and introduce non-algorithmic effective methods into classical mathematics, then we can bridge the chasm between truth and provability, and define computational methods that are not Turing-computable., Comment: v2; introduced standardised ACI compliant notation for citations; 13 pages; an HTML version is available at http://alixcomsi.com/Can_Turing_machines.htm

Whatever other beliefs there may remain for considering Cantor's diagonal argument as mathematically legitimate, there are three that, prima facie, lend it an illusory legitimacy; they need to be explicitly discounted appropriately. The first, Cantor's diagonal argument defines a non-countable Dedekind real number; the second, Goedel uses the argument to define a formally undecidable, but interpretively true, proposition; and the third, Turing uses the argument to define an uncomputable Dedekind real number., Comment: v2; introduced standardised ACI compliant notation for citations; 15 pages; an HTML version is available at http://alixcomsi.com/Three_beliefs.htm

We formally define a "mathematical object" and "set". We then argue that expressions such as "(Ax)F(x)", and "(Ex)F(x)", in an interpretation M of a formal theory P, may be taken to mean "F(x) is true for all x in M", and "F(x) is true for some x in M", respectively, if, and only if, the predicate letter "F" is a mathematical object in P. In the absence of a proof, the expressions "(Ax)F(x)", and "(Ex)F(x)", can only be taken to mean that "F(x) is true for any given x in M", and "It is not true that F(x) is false for any given x in M", respectively, indicating that the predicate "F(x)" is well-defined, and effectively decidable individually, for any given value of x, but that there may be no uniform effective method (algorithm) for such decidability. We show how some paradoxical concepts of Quantum Mechanics can then be expressed in a constructive interpretation of standard Peano's Arithmetic., Comment: v2; revised para 5(xviii); introduced standardised ACI compliant notation for citations; 15 pages; an HTML version is available at http://alixcomsi.com/Is_there_a_loophole.htm

We consider a philosophical question that is implicit in Selmer Bringsjord's paper, "The narrational case against Church's Thesis": If, as Mendelson argues, the classically accepted definitions of foundational concepts such as "partial recursive function", "function", "(Tarskian) truth", "set" etc. are vague and imprecise - hence possibly non-constructive and intuitionistically objectionable - then replacing one non-constructive concept by another may be psychologically unappealing, but it should be meta-mathematically valid and acceptable., Comment: v2; introduced standardised ACI compliant notation for citations; 11 pages; an HTML version is available at http://alixcomsi.com/CTG_06_Consequences_Bringsjord.htm

If we assume the Thesis that any classical Turing machine T, which halts on every n-ary sequence of natural numbers as input, determines a PA-provable formula, whose standard interpretation is an n-ary arithmetical relation f(x1, >..., xn) that holds if, and only if, T halts, then standard PA can model the state of a deterministic universe that is consistent with a probabilistic Quantum Theory. Another significant consequence of this Thesis is that every partial recursive function can be effectively defined as total., Comment: 12 pages. Revision 1. Appendix 1 added. An HTML version is available at http://alixcomsi.com/index01.htm

In 1995, David Chalmers opined as implausible that there may be parts of our arithmetical competence that no sound formal system could ever duplicate. We prove that the recursive number-theoretic relation x=Sb(y 19|Z(y)) - which is algorithmically verifiable since Goedel's recursive function Sb(y 19|Z(y)) is Turing-computable - cannot be "duplicated" in any consistent formal system of Arithmetic., Comment: v2; introduced standardised ACI compliant notation for citations; 9 pages; this paper reproduces Meta-theorem 1 and related Meta-lemmas from my earlier paper http://arXiv.org/abs/math.GM/0210078 ; an HTML version is available at http://alixcomsi.com/index01.htm

We give a precise definition of a formal mathematical object as any symbol for an individual constant, predicate letter, or a function letter that can be introduced through definition into a formal mathematical language without inviting inconsistency. We then show: there is an elementary, recursive, number-theoretic relation that is not a formal mathematical object, since it is not the standard interpretation of any of its representations in Goedel's formal system P; the range of a recursive number-theoretic function does not always define a (recursively enumerable set) formal mathematical object consistently in any Axiomatic Set Theory that models P; there is no P-formula, Con(P), whose standard interpretation is unambiguously equivalent to Goedel's number-theoretic definition of "P is consistent"; every recursive number-theoretic function is not strongly representable in P; Tarski's definitions of "satisfiability" and "truth" can be made constructive, and intuitionistically unobjectionable, by reformulating Church's Thesis constructively; the classical definition of Turing machines can be extended to include self-terminating, converging, and oscillating routines; a constructive Church's Thesis implies, firstly, that every partial recursive number-theoretic function can be constructively extended as a unique total function, and, secondly, that we can define effectively computable functions that are not classically Turing-computable; Turing's and Cantor's diagonal arguments do not necessarily define Cauchy sequences., Comment: v6; introduced ACI compliant notation for citations; replaced Corollary 1.2; corrected Corollary 14.3; other minor corrections and additions; 76 pages; an HTML version is available at http://alixcomsi.com/CTG_06_Consequences.htm

In an earlier paper, "Omega-inconsistency in Goedel's formal system: a constructive proof of the Entscheidungsproblem" (math/0206302), I argued that a constructive interpretation of Goedel's reasoning establishes any formal system of Arithmetic as omega-inconsistent. It follows from this that Goedel's Theorem VI holds vacuously. In this paper I show that Goedel's Theorem XI essentially states that, if we assume there is a P-formula [Con(P)] whose standard interpretation is equivalent to the assertion "P is consistent", then [Con(P)] is not P-provable. I argue that there is no such formula., Comment: v2. Introduced ACI compliant notation for citations. 9 pages. An HTML version is available at http://alixcomsi.com/index01.htm

If we apply an extension of the Deduction meta-Theorem to Goedel's meta-reasoning of "undecidability", we can conclude that Goedel's formal system of Arithmetic is not omega-consistent. If we then take the standard interpretation "(Ax)(F(x)" of the PA-formula [(Ax)F(x)] to mean "There is a general, x-independent, routine to establish that F(x) holds for all x", instead of "F(x) holds for all x", it follows that a constructively interpreted omega-inconsistent system proves Hilbert's Entscheidungsproblem negatively., Comment: v3. Introduced ACI compliant notation for citations. 10 pages. An HTML version is available at http://alixcomsi.com/index01.htm

I review the classical conclusions drawn from Goedel's meta-reasoning establishing an undecidable proposition GUS in standard PA. I argue that, for any given set of numerical values of its free variables, every recursive arithmetical relation can be expressed in PA by different, but formally equivalent, propositions. This asymmetry yields alternative Representation and Self-reference meta-Lemmas. I argue that Goedel's meta-reasoning can thus be expressed avoiding any appeal to the truth of propositions in the standard interpretation IA of PA. This now establishes GUS as decidable, and PA as omega-inconsistent. I argue further that Rosser's extension of Goedel's meta-reasoning involves an invalid deduction., Comment: v3: Introduced ACI compliant notation for citations. 30 pages. An HTML version is available on the web at http://alixcomsi.com/index01.htm

Goedel's explicit thesis was that his undecidable formula GUS is a well-formed, well-defined formal sentence in any formalisation of Intuitive Arithmetic IA in which the axioms and rules of inference are recursively definable. His implicit thesis was that GUS is not formally inconsistent in any such system. I argue in a constructive, intuitionistically unobjectionable, and recursively definable formalisation PP of IA that GUS is a well-formed formula but an ill-defined formal sentence reflecting the "Liar" paradox in PP. Further, introducing "formal truth" and "provability" values to selected propositions of IA through PP leads to the collapse of Lucas' Goedelian argument., Comment: v2: 40 pages. An HTML version of this paper is on the web at http://alixcomsi.com/index01.htm . Preface added, footnotes added, major revisions made

In this paper, we argue that formal systems of first order Arithmetic that admit Goedelian undecidable propositions validly are abnormally non-constructive. We argue that, in such systems, the strong representation of primitive recursive predicates admits abnormally non-constructive, Platonistic, elements into the formal system that are not reflected in the predicates which they are intended to formalise. We argue that the source of such abnormal Platonistic elements in these systems is the non-constructive Generalisation rule of inference of first order logic. We argue that, in most simply consistent systems that faithfully formalise intuitive Arithmetic, we cannot infer from Goedel's reasoning the Platonistic existence of abnormally non-constructive propositions that are formally undecidable, but true under every interpretation. We define a constructive formal system of Peano's Arithmetic, omega2-PA, whose axioms are identical to the axioms of standard Peano's Arithmetic PA, but lead to significantly different logical consequences. We thus argue that the formal undecidability of true Arithmetical propositions is a characteristic not of relations that are Platonistically inherent in any Arithmetic of the natural numbers, but of the particular formalisation chosen to represent them., Comment: 63 pages. Also available at http://alixcomsi.com/index01.htm; added abstract; substituted recursive definition for omega-constructivity in Chapter 3.11