This page is best viewed with Internet Explorer 6.0 and above

Some investigations into the foundations of mathematics, logic, and computability

 

“We have a habit in writing articles published in scientific journals to make the work as finished as possible, to cover up all the tracks, to not worry about the blind alleys or describe how you had the wrong idea first, and so on. So there isn’t any place to publish, in a dignified manner, what you actually did in order to get to do the work.”

 

Richard P. Feynman, in his Nobel Lecture, 1966

 

“If you ask a philosopher what the main problems are in the philosophy of mathematics, then the following two are likely to come up: what is the status of mathematical truth, and what is the nature of mathematical objects? That is, what gives mathematical statements their aura of infallibility, and what on earth are these statements about?”

 

W. T. Gowers in his talk, “Does mathematics need a philosophy?”, presented before the Cambridge University Society for the Philosophy of Mathematics and Mathematical Sciences, 2002

 

 

- o -

Mathematical Objects and Mathematical Truth

Reviewing classical interpretations of Cantor’s, Gödel’s, Tarski’s, and Turing’s reasoning

and

addressing some grey areas in the foundations of mathematics, logic and computability

 

 

   Bhupinder Singh Anand[1]

(The author is an independent scholar. E-mail: re@alixcomsi.com)

Preamble (July 2005) ►

These investigations (except #27) reflect an evolving view - starting from tentative, and mathematically unsustainable, arguments - of a significant limitation of standard interpretations of the formal reasoning, and conclusions, of classical, first order, theory.

Such interpretations - based primarily on the work of Cantor, Gödel, Tarski, and Turing - argue that the truth (satisfiability) of the propositions of a formal mathematical language, under an interpretation, is, both, non-algorithmic and essentially unverifiable constructively.

In these investigations, I argue (April 2002 onwards) that - if mathematics is to serve as a universal set of languages of, both, precise expression and unambiguous communication - such interpretations may need to be balanced by an alternative, constructive and intuitionistically unobjectionable, interpretation - of classical foundational concepts - in which non-algorithmic truth (satisfiability) is defined effectively.

More precisely, I suggest that some foundational concepts - implicitly accepted as intuitively unexceptionable in Platonic interpretations of Cantor’s, Gödel’s, Tarski’s and Turing’s reasoning - may be explicated effectively in non-Platonic interpretations that consider whether, and, if so, when, and how, we may, within classical logic and without inviting inconsistency:

(a) define a mathematical object formally ►;

(b) define mathematical truth (satisfiability) effectively ►;

(c) define effective methods of numerical computation non-algorithmically ►;

(d) differentiate between algorithmic assertions such as ‘For all x, R(x)’, and instantiational assertions such as ‘For any given x, R(x)’ ►;

(e) assert that two instantiationally equivalent relations, in a given interpretation of a formal language, have ‘the same meaning’ ►;

(f)  interpret universal quantification constructively ►;

(g)  link formal logic and computability ►;

(h) interpret Modus Ponens and the Generalisation Rule of Inference ►;

(i)  be unable to introduce a formula, which interprets as instantiationally true under every interpretation, as an axiom ►;

(j)  consider a formal language (axiomatic theory) as computable (constructive) ►.

(A copy of the current update can be downloaded from here as a 55kb PDF FILE ►)

(NOTE: The PDF FILES referred to in these pages may contain symbols that do not reproduce correctly in all viewers; they are best viewed with Adobe’s Acrobat Reader version 7.0 and above ►)

- o -

FORMAL ESSAYS

►Main essays   ►Subsidiary essays

(Except where indicated otherwise, these investigations have not been peer-reviewed. The author welcomes any comments and feedback - whether on the contents, presentation, or reading and printing problems. E-mail ►)

 < This indicates that the essay, or page, is currently under revision >

- o -

================================ 33 ================================

►PDF ►

►  Two presumptions in Goedel's interpretation of his own, formal, reasoning that are classically objectionable (March 2007)►

Standard expositions of Goedel's 1931 paper on undecidable arithmetical propositions are based on two presumptions in Goedel's 1931 interpretation of his own, formal, reasoning - one each in Theorem VI and in Theorem XI - which do not meet Goedel's, explicitly stated, requirement of classically constructive, and intuitionistically unobjectionable, reasoning. We see how these objections can be addressed, and note some consequences.

================================ 32 ================================

►PDF ►

►  An elementary proof that P ≠ NP (February 2007)►

We show that, if PA has no non-standard models, then P ≠ NP. We then give an elementary proof that PA has no non-standard models.

================================ 31 ================================

►PDF ►

►  Why we shouldn't fault Lucas and Penrose for continuing to believe in the Gödelian argument against computationalism (July 2006) ►

The only fault we can fairly lay at Lucas' and Penrose's doors, for continuing to believe in the essential soundness of the Gödelian argument, is their naive faith in, first, non-verifiable assertions in standard expositions of classical theory, and, second, in Goedel's unvalidated interpretation of his own formal reasoning. We show why their faith is misplaced in both instances.

================================ 30 ================================

►PDF ►

►  P ≠ NP under a constructive interpretation of Peano Arithmetic (March 2006) ►

We show that all provable arithmetical formulas are Turing-decidable under the standard interpretation of a standard, first-order, Peano Arithmetic, PA. An immediate consequence is that the set of Gödel-formulas of PA is empty, and that PA has no non-standard models. We show that this implies, further, that P ≠ NP.

================================ 29 ================================

►PDF ►

►  Why Brouwer was right in suggesting that Hilbert's Law of The Excluded Middle needed qualification (March 2006) ►

We reproduce Hilbert's axiomatic formalisation of Number Theory, and argue that his enunciation of the Law of the Excluded Middle is inconsistent with a Turing-verifiable model of the axioms under the standard interpretation.

================================ 28 ================================

►PDF ►

►  Naive Philosophical Foundations (December 2005) ►

This soliloquy outlines some naïve philosophical arguments underlying the thesis that mathematics ought to be viewed simply as a universal set of languages, some of precise expression, and some of unambiguous and effective communication.

================================ 27 ================================

►PDF ►

►  A Minimal Prime Generating Theorem that suggests the Prime Difference is O(π(p(n)^1/2) (December 2005) ►

Although this 1964 paper is not, strictly, a foundational paper, it developed as an off-shoot to the foundational query: Do we discover the natural numbers (Platonically), or do we construct them linguistically? The paper also assumes computational significance in the light of Agrawal, Kayal and Saxena's August 2002 paper, “PRIMES is in P”, since both the Trim and Compact Number Generating algorithms - each of which generates all the primes - are deterministic algorithms that suggest the Prime Difference, d_p(n), is O(π(p(n)^1/2).

================================ 26 ================================

►PDF ►

►  PA is instantiationally and arithmetically complete, but algorithmically incomplete: An alternative interpretation of Gödelian incompleteness under Church's Thesis that links formal logic and computability (July 2005) ►

We define instantiational and algorithmic completeness for a formal language, and arithmetical completeness for Peano Arithmetic. We show that, in the presence of Church's Thesis, an alternative interpretation of Gödelian incompleteness is that Peano Arithmetic is instantiationally complete, but algorithmically incomplete. We then postulate a Provability Thesis that links Peano Arithmetic and effective algorithmic computability - just as Church's Thesis links Recursive Arithmetic and effective instantiational computability - under which PA is arithmetically complete.

================================ 25 ================================

►PDF ►

►  The Göbbellian Syndrome (June 2005) ►

Can we really falsify truth by dictat? A critical note on J. R Lucas' 1996 remarks concerning non-standard models of first order Peano Arithmetic.

================================ 24 ================================

►PDF ►

►  The Mechanist's Challenge (June 2005) ►

Did we really hope to get away with The Gödelian Argument? A critical response to J. R Lucas’ 1996 articulation of his 1961 argument.

================================ 23 ================================

►PDF ►

►  An arguable inconsistency in ZF (February 2005) ►

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. However it is silent on the consistency of the latter.

We now show that PA+PRA is, in fact, inconsistent; hence ZF, too, is inconsistent.

================================ 22 ================================

►PDF ►

►  An arguable addition to the standard Deduction Theorems of first-order theories (September 2004) ►

We consider the immediate consequence of an arguable addition to the standard Deduction Theorems of first order theories.

(This is a formal presentation of the arguments of an earlier essay►)

================================ 21 ================================

►PDF ►

►  Is the Halting problem effectively solvable non-algorithmically, and is the Gödel sentence in NP, but not in P? (September 2004) ►

We consider the thesis that an arithmetical relation, which holds for any, given, assignment of natural numbersto 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 Gödel'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.

(This is a revised, and expanded, presentation of Theorem 1 of an earlier essay►)

================================ 20 ================================

►PDF ►

► Do Gödel’s incompleteness theorems set absolute limits on the ability of the brain to express and communicate mental concepts verifiably? (Jun 2004) ►

Classical interpretations of Gödel’s formal reasoning, and of his conclusions, implicitly imply that mathematical languages are essentially incomplete, in the sense that the truth of some arithmetical propositions of any formal mathematical language, under any interpretation, is, both, non-algorithmic, and essentially unverifiable. However, a language of general, scientific, discourse, which intends to mathematically express, and unambiguously communicate, intuitive concepts that correspond to scientific investigations, 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 - classically accepted as the foundation of all our mathematical languages - is verifiably complete in the above sense. We show how some paradoxical concepts of Quantum mechanics can, then, be expressed, and interpreted, naturally under a constructive definition of mathematical truth.

(This is an update of the essay published in the invited article section of the OA Web Journal NeuroQuantology 2004; 2: 60-100)

================================ 19 ================================

►PDF ►

►  How definitive is the standard interpretation of Goodstein’s argument? (Nov 2003) ►

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, firstly, that G(m) must, therefore, converge; and, secondly, that this conclusion - Goodstein’s Theorem - is unprovable in Peano Arithmetic, but true under its standard interpretation.

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 highlight why the standard interpretation of Goodstein's argument ought not to be accepted as definitive.

================================ 18 ================================

►PDF ►

►  The Einstein_Bohr debate: Can Laplace’s formula model a deterministic universe that is irreducibly probabilistic? (Jun 2003) ►

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(x₁,  ..., x_n) that holds if, and only if, T halts, then we can define Laplace’s formula recursively such that it can express the state of a deterministic quantum universe which is irreducibly probabilistic.

================================ 17 ================================

►PDF ►

►  How definitive is the standard interpretation of Gödel’s Incompleteness Theorem? (Jun 2003) ►

Standard interpretations of Gödel'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.

(We give a more formal presentation of this argument in a later essay►)

================================ 16 ================================

►PDF ►

►  Why we must heed Wittgenstein’s “notorious paragraph” (May 2003) ►

In this essay, we argue that, although Wittgenstein’s reservations on Gödel'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 Gödel's formal reasoning - even seventy years after the publication of his seminal 1931 paper - is of much greater significance, and relevance, to us today.

================================ 15 ================================

►PDF ►

►  Is the Halting probability a Dedekind real number? (May 2003) ►

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 essay 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.

================================ 14 ================================

►PDF ►

►  Can we express every transfinite concept constructively? (May 2003) ►

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 essay 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.