You are currently browsing the tag archive for the ‘ambiguity’ tag.

(Notations, non-standard concepts, and definitions used commonly in these investigations are detailed in this post.)

In this post I address two critical issues, as raised in private correspondence with researchers, which may illuminate some objections to Gödel’s reasoning and conclusions that have been raised elsewhere by Wittgenstein, Floyd, Putnam et al.:

(i) By Rosser’s reasoning, doesn’t simple consistency suffice for defining an undecidable arithmetical proposition?

(ii) Doesn’t Gödel’s undecidable formula assert its own unprovability?

NOTE: The following correspondence refers copiously to this paper that was presented in June 2015 at the workshop on Hilbert’s Epsilon and Tau in Logic, Informatics and Linguistics, University of Montpellier, France.

Subsequently, most of the cited results were detailed formally in the following paper due to appear in the December 2016 issue of ‘Cognitive Systems Research‘:

A: Doesn’t simple consistency suffice for defining Rosser’s undecidable arithmetical proposition?

You claim that the PA system is $\omega$-inconsistent, and that Gödel’s first theorem holds vacuously. But by Rosser’s result, simple consistency suffices.

Well, it does seem surprising that Rosser’s claim—that his ‘undecidable’ proposition only assumes simple consistency—has not been addressed more extensively in the literature. Number-theoretic expositions of Rosser’s proof have generally remained either implicit or sketchy (see, for instance, this post).

Note that Rosser’s proposition and reasoning involve interpretation of an existential quantifier, whilst Gödel’s proposition and reasoning only involve interpretation of a universal quantifier.

The reason why Rosser’s claim is untenable is that—in order to interpret the existential quantifier as per Hilbert’s $\epsilon$-calculus—Rosser’s argument needs to assume his Rule C (see Elliott Mendelson, Introduction to Mathematical Logic, 1964 ed., p.73), which implicitly implies that Gödel’s arithmetic P—in which Rosser’s argumentation is grounded—is $\omega$-consistent .

See, for instance, this analysis of (a) Wang’s outline of Rosser’s argument on p.5, (b) Beth’s outline of Rosser’s argument on p.6, and (c) Mendelson’s exposition of Rosser’s argument in Section 4.2 on p.8.

Moreover, the assumption is foundationally fragile, because Rule C invalidly assumes that we can introduce an ‘unspecified’ formula denoting an ‘unspecified’ numeral into PA even if the formula has not been demonstrated to be algorithmically definable in terms of the alphabet of PA.

See Theorem 8.5 and following remarks in Section 8, pp.7-8 of this paper that was presented in June 2015 at the workshop on Hilbert’s Epsilon and Tau in Logic, Informatics and Linguistics, University of Montpellier, France.

B: As I see it, rule C is only a shortcut.

As I see it, rule C is only a shortcut; it is totally eliminable. Moreover, it is part of predicate logic, not of the Peano’s arithmetic.

Assuming that Rule C is a short cut which can always be eliminated is illusory, and is tantamount to invalidly (see Corollary 8.6, p.17 of the Epsilon 2015 paper) claiming that Hilbert’s $\epsilon$ calculus is a conservative extension of the first-order predicate calculus.

Reason: Application of Rule C invalidly (see Theorem 8.5 and following remarks in Section 8, pp.7-8 of the Epsilon 2015 paper) involves introduction of a new individual constant, say $[d]$, in a first-order theory $K$ (see Mendelson 1964, p.74, I(iv)); ‘invalidly’ since Rule C does not qualify that $[d]$ must be algorithmically computable from the alphabet of $K$—which is necessary if $K$ is first-order.

Notation: We use square brackets to indicate that the expression within the brackets denotes a well-formed formula of a formal system, say $K$, that is to be viewed syntactically merely as a first-order string of $K$—i.e, one which is finitarily constructed from the alphabet of the language of $K$—without any reference to its meaning under any interpretation of $K$.

Essentially, Rule C mirrors in $K$ the intuitionistically objectionable postulation that the formula $[(\exists x)F(x)]$ of $K$ can always be interpreted as:

$F'(a)$ holds for some element $a$

in the domain of the interpretation of $K$ under which the formula $[F(x)]$ interprets as the relation $F'(x)$.

The Epsilon 2015 paper shows that this is not a valid interpretation of the formula $[(\exists x)F(x)]$ under any finitary, evidence-based, interpretation of $K$.

That, incidentally, is a consequence of the proof that PA is not $\omega$-consistent; which itself is a consequence of (Theorem 7.1, p.15, of the Epsilon 2015 paper):

Provability Theorem for PA: A PA formula $[F(x)]$ is provable if, and only if, $[F(x)]$ interprets as an arithmetical relation $F'(x)$ that is algorithmically computable as always true (see Definition 3, p.7, of the Epsilon 2015 paper) over the structure $\mathbb{N}$ of the natural numbers.

Compare with what Gödel has essentially shown in his famous 1931 paper on formally undecidable arithmetical propositions, which is that (Lemma 8.1, p.16, of the Epsilon 2015 paper):

Gödel: There is a PA formula $[R(x, p)]$—which Gödel refers to by its Gödel number $r$—which is not provable in PA, even though $[R(x, p)]$ interprets as an arithmetical relation that is algorithmically verifiable as always true (see Definition 4, p.7, of the Epsilon 2015 paper) over the structure $\mathbb{N}$ of the natural numbers.

C: If you by-pass the intuitionist objections, would all logicist and post-formalist theories hold?

If I have understood correctly, you claim that the PA system is $\omega$-inconsistent from an intuitionistic point of view? If you by-pass the intuitionist objections, would all logicist and post-formalist theories hold?

There is nothing to bypass—the first-order Peano Arithmetic PA is a formal axiomatic system which is $\omega$-inconsistent as much for an intuitionist, as it is for a realist, a finitist, a formalist, a logicist or a nominalist.

Philosophers may differ about beliefs that are essentially unverifiable; but the $\omega$-incompleteness of PA is a verifiable logical meta-theorem that none of them would dispute.

D: Isn’t Gödel’s undecidable formula $[(\forall x)R(x, p)]$—which Gödel refers to by its Gödel number $17Gen\ r$—self-referential?

Isn’t Gödel’s undecidable formula $[(\forall x)R(x, p)]$—which Gödel refers to by its Gödel number $17Gen\ r$—self-referential and covertly paradoxical?

According to Wittgenstein it interprets in any model as a sentence that is devoid of sense, or even meaning. I think a good reason for this is that the formula is simply syntactically wrongly formed: the provability of provability is not defined and can not be consistently defined.

What you propose may be correct, but for automation systems of deduction wouldn’t $\omega$-inconsistency be much more problematic than undecidability?

How would you feel if a syntax rule is proposed, that formulas containing numerals are instantiations of open formulas that may not be part of the canonical language? Too daring, may be?

Let me briefly respond to the interesting points that you have raised.

1. The $\omega$-inconsistency of PA is a meta-theorem; it is a Corollary of the Provability Theorem of PA (Theorem 7.1, p.15, of the Epsilon 2015 paper).

2. Gödel’s PA-formula $[(\forall x)R(x, p)]$ is not an undecidable formula of PA. It is merely unprovable in PA.

3. Moreover, Gödel’s PA-formula $[\neg(\forall x)R(x, p)]$ is provable in PA, which is why the PA formula $[(\forall x)R(x, p)]$ is not an undecidable formula of PA.

4. Gödel’s PA-formula $[(\forall x)R(x, p)]$ is not self-referential.

5. Wittgenstein correctly believed—albeit purely on the basis of philosophical considerations unrelated to whether or not Gödel’s formal reasoning was correct—that Gödel was wrong in stating that the PA formula $[(\forall x)R(x, p)]$ asserts its own unprovability in PA.

Reason: We have for Gödel’s primitive recursive relation $Q(x, y)$ that:

$Q(x, p)$ is true if, and only if, the PA formula $[R(x, p)]$ is provable in PA.

However, in order to conclude that the PA formula $[(\forall x)R(x, p)]$ asserts its own unprovability in PA, Gödel’s argument must further imply—which it does not—that:

$(\forall x)Q(x, p)$ is true (and so, by Gödel’s definition of $Q(x, y)$, the PA formula $[(\forall x)R(x, p)]$ is not provable in PA) if, and only if, the PA formula $[(\forall x)R(x, p)]$ is provable in PA.

In other words, for the PA formula $[(\forall x)R(x, p)]$ to assert its own unprovability in PA, Gödel must show—which his own argument shows is impossible, since the PA formula $[(\forall x)R(x, p)]$ is not provable in PA—that:

The primitive recursive relation $Q(x, p)$ is algorithmically computable as always true if, and only if, the arithmetical relation $R'(x, p)$ is algorithmically computable as always true (where $R'(x, p)$ is the arithmetical interpretation of the PA formula $[R(x, p)]$ over the structure $\mathbb{N}$ of the natural numbers).

6. Hence, Gödel’s PA-formula $[(\forall x)R(x, p)]$ is not covertly paradoxical.

7. IF Wittgenstein believed that the PA formula $[(\forall x)R(x, p)]$ is empty of meaning and has no valid interpretation, then he was wrong, and—as Gödel justifiably believed—he could not have properly grasped Gödel’s formal reasoning that:

(i) ‘$17Gen\ r$ is not $\kappa$-provable’ is a valid meta-theorem if PA is consistent, which means that:

‘If PA is consistent and we assume that the PA formula $[(\forall x)R(x, p)]$ is provable in PA, then the PA formula $[\neg(\forall x)R(x, p)]$ must also be provable in PA; from which we may conclude that the PA formula $[(\forall x)R(x, p)]$ is not provable in PA’

(ii) ‘$Neg(17Gen\ r)$ is not $\kappa$-provable’ is a valid meta-theorem ONLY if PA is $\omega$-consistent, which means that:

‘If PA is $\omega$-consistent and we assume that the PA formula $[\neg(\forall x)R(x, p)]$ is provable in PA, then the PA formula $[(\forall x)R(x, p)]$ must also be provable in PA; from which we may conclude that the PA formula $[\neg(\forall x)R(x, p)]$ is not provable in PA’.

8. In fact the PA formula $[(\forall x)R(x, p)]$ has the following TWO meaningful interpretations (the first of which is a true arithmetical meta-statement—since the PA formula $[R(n)]$ is provable in PA for any PA-numeral $[n]$—but the second is not—since the PA formula $[(\forall x)R(x, p)]$ is not provable in PA):

(i) For any given natural number $n$, there is an algorithm which will verify that each of the arithmetical meta-statements ‘$R'(1, p)$ is true’, ‘$R'(2, p)$ is true’, …, ‘$R'(n, p)$ is true’ holds under the standard, algorithmically verifiable, interpretation $\mathbb{M}$ of PA (see \S 5, p.11 of the Epsilon 2015 paper);

(ii) There is an algorithm which will verify that, for any given natural number $n$, the arithmetical statement ‘$R'(n, p)$ is true’ holds under the finitary, algorithmically computable, interpretation $\mathbb{B}$ of PA (see \S 6, p.13 of the Epsilon 2015 paper).

9. IF Wittgenstein believed that the PA formula $[(\forall x)R(x, p)]$ is not a well-defined PA formula, then he was wrong.

Gödel’s definition of the PA formula $[(\forall x)R(x, p)]$ yields a well-formed formula in PA, and cannot be treated as ‘syntactically wrongly formed’.

10. The Provability Theorem for PA shows that both ‘proving something in PA’ and ‘proving that something is provable in PA’ are finitarily well-defined meta-mathematical concepts.

11. The Provability Theorem for PA implies that PA is complete with respect to the concepts of satisfaction, truth and provability definable in automated deduction systems, which can only define algorithmically computable truth.

12. The Provability Theorem for PA implies that PA is categorical, so you can introduce your proposed syntax rule ONLY if it leads to a conservative extension of PA.

13. Whether ‘daring’ or not, why would you want to introduce such a rule?

E: Consider these two statements of yours …

Consider these two statements of yours:

“(iv): $p$ is the Gödel-number of the formula $[(\forall x)][R(x, y)]$ of PA” and

“D(4): Gödel’s PA-formula $[(\forall x)R(x, p)]$ is not self-referential.”

If ‘$p$‘ is the Gödel-number of the open formula in para (iv), and the second argument of the closed formula $R$ in para D(4) is ‘$p$‘, then the second formula is obtained by instantiating the variable ‘$y$‘ in the first with its own Gödel-number.

So how would you call, in one word, the relation between the entire formula (in D(4)) and its second argument?

Para D(4) is an attempt to clarify precisely this point.

1. Apropos the first statement ‘(iv)’ cited by you:

From a pedantic perspective, the “relation between the entire formula (in D(4)) and its second argument” cannot be termed self-referential because the “second argument”, i.e., $p$, is the Gödel-number of the PA formula $[(\forall x)R(x, y)]$, and not that of “the entire formula (in 4)”, i.e., of the formula $[(\forall x)R(x, p)]$ itself (whose Gödel number is $17Gen\ r$).

Putting it crudely, $17Gen\ r$ is neither self-referential—nor circularly defined—because it is not defined in terms of $17Gen\ r$, but in terms of $p$.

2. Apropos the second statement ‘D(4)’ cited by you:

I would interpret:

Gödel’s PA-formula $[(\forall x)R(x, p)]$ is self-referential

to mean, in this particular context, that—as Gödel wrongly claimed:

$[(\forall x)R(x, p)]$ asserts its own unprovability in PA.

Now, if we were to accept the claim that $[(\forall x)R(x, p)]$ is self-referential in the above sense, then (as various critics of Gödel’s reasoning have pointed out) we would have to conclude further that Gödel’s argument leads to the contradiction:

$(\forall x)Q(x, p)$ is true—and so, by Gödel’s definition of $Q(x, y)$—the PA formula $[(\forall x)R(x, p)]$ is not provable in PA—if, and only if, the PA formula $[(\forall x)R(x, p)]$ is provable in PA.

However, in view of the Provability Theorem of PA (Theorem 7.1, p.15, of the Epsilon 2015 paper), this contradiction would only follow if Gödel’s argument were to establish (which it does not) that:

The primitive recursive relation $Q(x, p)$ is algorithmically computable as always true if, and only if, the arithmetical interpretation $R'(x, p)$ of the PA formula $[R(x, p)]$ is algorithmically computable as always true over the structure $\mathbb{N}$ of the natural numbers.

The reason Gödel cannot claim to have established the above is that his argument only proves the much weaker meta-statement:

The arithmetical interpretation $R'(x, p)$ of the PA formula $[R(x, p)]$ is algorithmically verifiable as always true over the structure $\mathbb{N}$ of the natural numbers.

Ergo—contrary to Gödel’s claim— Gödel’s PA-formula $[(\forall x)R(x, p)]$ is not self-referential (and so, even though Gödel’s claimed interpretation of what his own reasoning proves is wrong, there is no paradox in Gödel’s reasoning per se)!

F: Is the PA system $\omega$-inconsistent without remedy?

Is the PA system $\omega$-inconsistent without remedy? Is it possible to introduce a new axiom or new rule which by-passes the problematic unprovable statements of the Gödel-Rosser Theorems?

1. Please note that the first-order Peano Arithmetic PA is:

(i) consistent (Theorem 7.3, p.15, of the Epsilon 2015 paper); which means that for any PA-formula $[A]$, we cannot have that both $[A]$ and $[\neg A]$ are Theorems of PA;

(ii) complete (Theorem 7.1, p.15, of the Epsilon 2015 paper); which means that we cannot add an axiom to PA which is not a Theorem of PA without inviting inconsistency;

(iii) categorical (Theorem 7.2, p.15, of the Epsilon 2015 paper); which means that if $\mathbb{M}$ is an interpretation of PA over a structure $\mathbb{S}$, and $\mathbb{B}$ is an interpretation of PA over a structure $\mathbb{T}$, then $\mathbb{S}$ and $\mathbb{T}$ are identical and denote the structure $\mathbb{N}$ of the natural numbers defined by Dedekind’s axioms; and so PA has no model which contains an element that is not a natural number (see Footnote 54, p.16, of the Epsilon 2015 paper).

2. What this means with respect to Gödel’s reasoning is that:

(i) PA has no undecidable propositions, which is why it is not $\omega$-consistent (Corollary 8.4, p.16, of the Epsilon 2015 paper);

(ii) The Gödel formula $[(\forall x)R(x, p)]$ is not provable in PA; but it is algorithmically verifiable as true (Corollary 8.3, p.16, of the Epsilon 2015 paper) under the algorithmically verifiable standard interpretation $\mathbb{M}$ of PA (see Section 5, p.11, of the Epsilon 2015 paper) over the structure $\mathbb{N}$ of the natural numbers;

(iii) The Gödel formula $[(\forall x)R(x, p)]$ is not provable in PA; and it is algorithmically computable as false (Corollary 8.3, p.16, of the Epsilon 2015 paper) under the algorithmically computable finitary interpretation $\mathbb{B}$ of PA (see Section 6, p.13, of the Epsilon 2015 paper) over the structure $\mathbb{N}$ of the natural numbers;

(iv) The Gödel formula $[\neg(\forall x)R(x, p)]$ is provable in PA; and it is therefore also algorithmically verifiable as true under the algorithmically verifiable standard interpretation $\mathbb{M}$ of PA over the structure $\mathbb{N}$ of the natural numbers—which means that the logic by which the standard interpretation of PA assigns values of ‘satisfaction’ and ‘truth’ to the formulas of PA (under Tarski’s definitions) may be paraconsistent (see http://plato.stanford.edu/entries/logic-paraconsistent) since PA is consistent;

(v) The Gödel formula $[\neg(\forall x)R(x, p)]$ is provable in PA; and it is therefore algorithmically computable as true (Corollary 8.2, p.16, of the Epsilon 2015 paper) under the algorithmically computable finitary interpretation $\mathbb{B}$ of PA over the structure $\mathbb{N}$ of the natural numbers.

3. It also means that:

(a) The “Gödel-Rosser Theorem” is not a Theorem of PA;

(b) The “unprovable Gödel sentence” is not a “problematic statement”;

(c) The “PA system” does not require a “remedy” just because it is “$\omega$-inconsistent”;

(d) No “new axiom or new rule” can “by-pass the unprovable sentence”.

4. Which raises the question:

Why do you see the “unprovable Gödel sentence” as a “problematic statement” that requires a “remedy” which must “by-pass the unprovable sentence”?

Author’s working archives & abstracts of investigations

(Notations, non-standard concepts, and definitions used commonly in these investigations are detailed in this post.)

Ferguson’s and Priest’s thesis

In a brief, but provocative, review of what they term as “the enduring evolution of logic” over the ages, the authors of Oxford University Press’ recently released ‘A Dictionary of Logic‘, philosophers Thomas Macaulay Ferguson and Graham Priest, take to task what they view as a Kant-influenced manner in which logic is taught as a first course in most places in the world:

“… as usually ahistorical and somewhat dogmatic. This is what logic is; just learn the rules. It is as if Frege had brought down the tablets from Mount Sinai: the result is God-given, fixed, and unquestionable.”

Ferguson and Priest conclude their review by remarking that:

“Logic provides a theory, or set of theories, about what follows from what, and why. And like any theoretical inquiry, it has evolved, and will continue to do so. It will surely produce theories of greater depth, scope, subtlety, refinement—and maybe even truth.”

However, it is not obvious whether that is prescient optimism, or a tongue-in-cheek exit line!

A nineteenth century parody of the struggle to define ‘truth’ objectively

For, if anything, the developments in logic since around 1931 has—seemingly in gross violation of the hallowed principle of Ockham’s razor, and its crude, but highly effective, modern avatar KISS—indeed produced a plethora of theories of great depth, scope, subtlety, and refinement.

These, however, seem to have more in common with the, cynical, twentieth century emphasis on subjective, unverifiable, ‘truth’, rather than with the concept of an objective, evidence-based, ‘truth’ that centuries of philosophers and mathematicians strenuously struggled to differentiate and express.

A struggle reflected so eloquently in this nineteenth century quote:

“When I use a word,” Humpty Dumpty said, in rather a scornful tone, “it means just what I choose it to mean—neither more nor less.”

“The question is,” said Alice, “whether you can make words mean so many different things.”

“The question is,” said Humpty Dumpty, “which is to be master—that’s all.”

… Lewis Carroll (Charles L. Dodgson), ‘Through the Looking-Glass’, chapter 6, p. 205 (1934 ed.). First published in 1872.

Making sense of mathematical propositions about infinite processes

It was, indeed, an epic struggle which culminated in the nineteenth century standards of rigour successfully imposed—in no small measure by the works of Augustin-Louis Cauchy and Karl Weierstrasse—on verifiable interpretations of mathematical propositions about infinite processes involving real numbers.

A struggle, moreover, which should have culminated equally successfully in similar twentieth century standards—on verifiable interpretations of mathematical propositions containing references to infinite computations involving integers—sought to be imposed in 1936 by Alan Turing upon philosophical and mathematical discourse.

For it follows from Turing’s 1936 reasoning that where quantification is not, or cannot be, explicitly defined in formal logical terms—eg. the classical expression of the Liar paradox as ‘This sentence is a lie’—a paradox cannot per se be considered as posing serious linguistic or philosophical concerns (see, for instance, the series of four posts beginning here).

Of course—as reflected implicitly in Kurt Gödel’s seminal 1931 paper on undecidable arithmetical propositions—it would be a matter of serious concern if the word ‘This’ in the English language sentence, ‘This sentence is a lie’, could be validly viewed as implicitly implying that:

(i) there is a constructive infinite enumeration of English language sentences;

(ii) to each of which a truth-value can be constructively assigned by the rules of a two-valued logic; and,

(iii) in which ‘This’ refers uniquely to a particular sentence in the enumeration.

Gödel’s influence on Turing’s reasoning

However, Turing’s constructive perspective had the misfortune of being subverted by a knee-jerk, anti-establishment, culture that was—and apparently remains to this day—overwhelmed by Gödel’s powerful Platonic—and essentially unverifiable—mathematical and philosophical 1931 interpretation of his own construction of an arithmetical proposition that is formally unprovable, but undeniably true under any definition of ‘truth’ in any interpretation of arithmetic over the natural numbers.

Otherwise, I believe that Turing could easily have provided the necessary constructive interpretations of arithmetical truth—sought by David Hilbert for establishing the consistency of number theory finitarily—which is addressed by the following paper due to appear in the December 2016 issue of ‘Cognitive Systems Research‘:

What is logic: using Ockham’s razor

Moreover, the paper endorses the implicit orthodoxy of an Ockham’s razor influenced perspective—which Ferguson and Priest seemingly find wanting—that logic is simply a deterministic set of rules that must constructively assign the truth values of ‘truth/falsity’ to the sentences of a language.

It is a view that I expressed earlier as the key to a possible resolution of the EPR paradox in the following paper that I presented on 26’th June at the workshop on Emergent Computational Logics at UNILOG’2015, Istanbul, Turkey:

where I introduced the definition:

A finite set $\lambda$ of rules is a Logic of a formal mathematical language $\mathcal{L}$ if, and only if, $\lambda$ constructively assigns unique truth-values:

(a) Of provability/unprovability to the formulas of $\mathcal{L}$; and

(b) Of truth/falsity to the sentences of the Theory $T(\mathcal{U})$ which is defined semantically by the $\lambda$-interpretation of $\mathcal{L}$ over a structure $\mathcal{U}$.

I showed there that such a definitional rule-based approach to ‘logic’ and ‘truth’ allows us to:

$\bullet$ Equate the provable formulas of the first order Peano Arithmetic PA with the PA formulas that can be evidenced as true’ under an algorithmically computable interpretation of PA over the structure $\mathbb{N}$ of the natural numbers;

$\bullet$ Adequately represent some of the philosophically troubling abstractions of the physical sciences mathematically;

$\bullet$ Interpret such representations unambiguously; and

$\bullet$ Conclude further:

$\bullet$ First that the concept of infinity is an emergent feature of any mechanical intelligence whose true arithmetical propositions are provable in the first-order Peano Arithmetic; and

$\bullet$ Second that discovery and formulation of the laws of quantum physics lies within the algorithmically computable logic and reasoning of a mechanical intelligence whose logic is circumscribed by the first-order Peano Arithmetic.

Author’s working archives & abstracts of investigations

(Notations, non-standard concepts, and definitions used commonly in these investigations are detailed in this post.)

A Economist: The return of the machinery question

In a Special Report on Artificial Intelligence in its issue of 25th June 2016, ‘The return of the machinery question‘, the Economist suggests that both cosmologist Stephen Hawking and enterpreneur Elon Musk share to some degree the:

“… fear that AI poses an existential threat to humanity, because superintelligent computers might not share mankind’s goals and could turn on their creators”.

B Our irrational propensity to fear that which we are drawn to embrace

Surprising, since I suspect both would readily agree that, if anything should scare us, it is our irrational propensity to fear that which we are drawn to embrace!

And therein should lie not only our comfort, but perhaps also our salvation.

For Artificial Intelligence is constrained by rationality; Human Intelligence is not.

An Artificial Intelligence must, whether individually or collectively, create and/or destroy only rationally. Humankind can and does, both individually and collectively, create and destroy irrationally.

C Justifying irrationality

For instance, as the legatees of logicians Kurt Goedel and Alfred Tarski have amply demonstrated, a Human Intelligence can easily be led to believe that some statements of even the simplest of mathematical languages—Arithmetic—must be both ‘formally undecidable’ and ‘true’, even in the absence of any objective yardstick for determining what is ‘true’!

D Differentiating between Human reasoning and Mechanistic reasoning

An Artificial Intelligence, however, can only treat as true that which can be proven—by its rules—to be true by an objective assignment of ‘truth’ and ‘provability’ values to the propositions of the language that formally expresses its mechanical operations—Arithmetic.

The implications of the difference are not obvious; but that the difference could be significant is the thesis of this paper which is due to appear in the December 2016 issue of Cognitive Systems Research:

E Respect for evidence-based ‘truth’ could be Darwinian

More importantly, the paper demonstrates that both Human Intelligence—whose evolution is accepted as Darwinian—and Artificial Intelligence—whose evolution it is ‘feared’ may be Darwinian—share a common (Darwinian?) respect for an accountable concept of ‘truth’.

A respect that should make both Intelligences fitter to survive by recognising what philosopher Christopher Mole describes in this invitational blogpost as the:

“… importance of the rapport between an organism and its environment”

—an environment that can obviously accommodate the birth, and nurture the evolution, of both intelligences.

So, it may not be too far-fetched to conjecture that the evolution of both intelligences must also, then, share a Darwinian respect for the kind of human values—towards protecting intelligent life forms—that, no matter in how limited or flawed a guise, is visibly emerging as an inherent characteristic of a human evolution which, no matter what the cost could, albeit optimistically, be viewed as struggling to incrementally strengthen, and simultaneously integrate, individualism (fundamental particles) into nationalism (atoms) into multi-nationalism (molecules) and, possibly, into universalism (elements).

F The larger question: Should we fear an extra-terrestrial Intelligence?

From a broader perspective yet, our apprehensions about the evolution of a rampant Artificial Intelligence created by a Frankensteinian Human Intelligence should, perhaps, more rightly be addressed—as some have urged—within the larger uncertainty posed by SETI:

Is there a rational danger to humankind in actively seeking an extra-terrestrial intelligence?

I would argue that any answer would depend on how we articulate the question and that, in order to engage in a constructive and productive debate, we need to question—and reduce to a minimum—some of our most cherished mathematical and scientific beliefs and fears which cannot be communicated objectively.

Author’s working archives & abstracts of investigations

(Notations, non-standard concepts, and definitions used commonly in these investigations are detailed in this post.)

We investigate whether the probabilistic distribution of prime numbers can be treated as a heuristic model of quantum behaviour, since it too can be treated as a quantum phenomena, with a well-defined binomial probability function that is algorithmically computable, where the conjectured values of $\pi(n)$ differ from actual values with a binomial standard deviation, and where we define a phenomena as a quantum phenomena if, and only if, it obeys laws that can only be represented mathematically by functions that are algorithmically verifiable, but not algorithmically computable.

1. Thesis: The concept of ‘mathematical truth’ must be accountable

The thesis of this investigation is that a major philosophical challenge—which has so far inhibited a deeper understanding of the quantum behaviour reflected in the mathematical representation of some laws of nature (see, for instance, this paper by Eamonn Healey)—lies in holding to account the uncritical acceptance of propositions of a mathematical language as true under an interpretation—either axiomatically or on the basis of subjective self-evidence—without any specified methodology of accountability for objectively evidencing such acceptance.

2. The concept of ‘set-theoretical truth’ is not accountable

Since current folk lore is that all scientific truths can be expressed adequately, and communicated unambiguously, in the first order Set Theory ZF, and since the Axiom of Infinity of ZF cannot—even in principle—be objectively evidenced as true under any putative interpretation of ZF (as we argue in this post), an undesirable consequence of such an uncritical acceptance is that the distinction between the truths of mathematical propositions under interpretation which can be objectively evidenced, and those which cannot, is not evident.

3. The significance of such accountability for mathematics

The significance of such a distinction for mathematics is highlighted in this paper due to appear in the December 2016 issue of Cognitive Systems Research, where we address this challenge by considering the two finitarily accountable concepts of algorithmic verifiability and algorithmic computability (first introduced in this paper at the Symposium on Computational Philosophy at the AISB/IACAP World Congress 2012-Alan Turing 2012, Birmingham, UK).

(i) Algorithmic verifiability

A number-theoretical relation $F(x)$ is algorithmically verifiable if, and only if, for any given natural number $n$, there is an algorithm $AL_{(F,\ n)}$ which can provide objective evidence for deciding the truth/falsity of each proposition in the finite sequence $\{F(1), F(2), \ldots, F(n)\}$.

(ii) Algorithmic computability

A number theoretical relation $F(x)$ is algorithmically computable if, and only if, there is an algorithm $AL_{F}$ that can provide objective evidence for deciding the truth/falsity of each proposition in the denumerable sequence $\{F(1), F(2), \ldots\}$.

(iii) Algorithmic verifiability vis à vis algorithmic computability

We note that algorithmic computability implies the existence of an algorithm that can decide the truth/falsity of each proposition in a well-defined denumerable sequence of propositions, whereas algorithmic verifiability does not imply the existence of an algorithm that can decide the truth/falsity of each proposition in a well-defined denumerable sequence of propositions.

From the point of view of a finitary mathematical philosophy—which is the constraint within which an applied science ought to ideally operate—the significant difference between the two concepts could be expressed by saying that we may treat the decimal representation of a real number as corresponding to a physically measurable limit—and not only to a mathematically definable limit—if and only if such representation is definable by an algorithmically computable function (Thesis 1 on p.9 of this paper that was presented on 26th June at the workshop on Emergent Computational Logics at UNILOG’2015, 5th World Congress and School on Universal Logic, Istanbul, Turkey).

We note that although every algorithmically computable relation is algorithmically verifiable, the converse is not true.

We show in the CSR paper how such accountability helps define finitary truth assignments that differentiate human reasoning from mechanistic reasoning in arithmetic by identifying two, hitherto unsuspected, Tarskian interpretations of the first order Peano Arithmetic PA, under both of which the PA axioms interpret as finitarily true over the domain $N$ of the natural numbers, and the PA rules of inference preserve such truth finitarily over $N$.

4. The ambit of human reasoning vis à vis the ambit of mechanistic reasoning

One corresponds to the classical, non-finitary, putative standard interpretation of PA over $N$, and can be treated as circumscribing the ambit of human reasoning about ‘true’ arithmetical propositions.

The other corresponds to a finitary interpretation of PA over $N$ that circumscibes the ambit of mechanistic reasoning about ‘true’ arithmetical propositions, and establishes the long-sought for consistency of PA (see this post); which establishes PA as a mathematical language of unambiguous communication for the mathematical representation of physical phenomena.

5. The significance of such accountability for the mathematical representation of physical phenomena

The significance of such a distinction for the mathematical representation of physical phenomena is highlighted in this paper that was presented on 26th June at the workshop on Emergent Computational Logics at UNILOG’2015, 5th World Congress and School on Universal Logic, Istanbul, Turkey, where we showed how some of the seemingly paradoxical elements of quantum mechanics may resolve if we define:

Quantum phenomena: A phenomena is a quantum phenomena if, and only if, it obeys laws that can only be represented mathematically by functions that are algorithmically verifiable but not algorithmically computable.

6. The mathematical representation of quantum phenomena that is determinate but not predictable

By considering the properties of Gödel’s $\beta$ function (see $\S$4.1 on p.8 of this preprint)—which allows us to strongly represent any non-terminating sequence of natural numbers by an arithmetical function—it would follow that, since any projection of the future values of a quantum-phenomena-associated, algorithmically verifiable, function is consistent with an infinity of algorithmically computable functions, all of whose past values are identical to the algorithmically verifiable past values of the function, the phenomena itself would be essentially unpredicatable if it cannot be represented by an algorithmically computable function.

However, since the algorithmic verifiability of any quantum phenomena shows that it is mathematically determinate, it follows that the physical phenomena itself must observe determinate laws.

7. Such representation does not need to admit multiverses

Hence (contrary to any interpretation that admits unverifiable multiverses) only one algorithmically computable extension of the function is consistent with the law determining the behaviour of the phenomena, and each possible extension must therefore be associated with a probability that the next observation of the phenomena is described by that particular extension.

8. Is the probability of the future behaviour of quantum phenomena definable by an algorithmically computable function?

The question arises: Although we cannot represent quantum phenomena explicitly by an algorithmically computable function, does the phenomena lend itself to an algorithmically computable probability of its future behaviour in the above sense?

9. Can primes yield a heuristic model of quantum behaviour?

We now show that the distribution of prime numbers denoted by the arithmetical prime counting function $\pi(n)$ is a quantum phenomena in the above sense, with a well-defined probability function that is algorithmically computable.

10. Two prime probabilities

We consider the two probabilities:

(i) The probability $P(a)$ of selecting a number that has the property of being prime from a given set $S$ of numbers;

Example 1: I have a bag containing $100$ numbers in which there are twice as many composites as primes. What is the probability that the first number you blindly pick from it is a prime. This is the basis for setting odds in games such as roulette.

(ii) The probability $P(b)$ of determining a proper factor of a given number $n$.

Example 2: I give you a $5$-digit combination lock along with a $10$-digit number $n$. The lock only opens if you set the combination to a proper factor of $n$ which is greater than $1$. What is the probability that the first combination you try will open the lock. This is the basis for RSA encryption, which provides the cryptosystem used by many banks for securing their communications.

11. The probability of a randomly chosen number from the set of natural numbers is not definable

Clearly the probability $P(a)$ of selecting a number that has the property of being prime from a given set $S$ of numbers is definable if the precise proportion of primes to non-primes in $S$ is definable.

However if $S$ is the set $N$ of all integers, and we cannot define a precise ratio of primes to composites in $N$, but only an order of magnitude such as $O(\frac{1}{log_{_{e}}n})$, then equally obviously $P(a) = P(n\ is\ a\ prime)$ cannot be defined in $N$ (see Chapter 2, p.9, Theorem 2.1, here).

12. The prime divisors of a natural number are independent

Now, the following paper proves $P(b) = \frac{1}{\pi(\sqrt{n})}$, since it shows that whether or not a prime $p$ divides a given integer $n$ is independent of whether or not a prime $q \neq p$ divides $n$:

Why Integer Factorising cannot be polynomial time

We thus have that $\pi(n) \approx n.\prod_{_{i = 1}}^{^{\pi(\sqrt{n})}}(1-\frac{1}{p_{_{i}}})$, with a binomial standard deviation.

Hence, even though we cannot define the probability $P(n\ is\ a\ prime)$ of selecting a number from the set $N$ of all natural numbers that has the property of being prime, $\prod_{_{i = 1}}^{^{\pi(\sqrt{n})}}(1-\frac{1}{p_{_{i}}})$ can be treated as the putative non-heuristic probability that a given $n$ is a prime.

13. The distribution of primes is a quantum phenomena

The distribution of primes is thus determinate but unpredictable, since it is representable by the algorithmically verifiable but not algorithmically computable arithmetical number-theoretic function $Pr(n) = p_{_{n}}$, where $p_{_{n}}$ is the $n$‘th prime.

The Prime Number Generating Theorem and the Trim and Compact algorithms detailed in this 1964 investigation illustrate why the arithmetical number-theoretic function $Pr(n)$ is algorithmically verifiable but not algorithmically computable (see also this Wikipedia proof that no non-constant polynomial function $Pr(n)$ with integer coefficients exists that evaluates to a prime number for all integers $n$.).

Moreover, although the distribution of primes is a quantum phenomena with probabilty $\prod_{_{i = 1}}^{^{\pi(\sqrt{n})}}(1-\frac{1}{p_{_{i}}})$, it is easily seen (see Figs. 7-11 on pp.23-26 of this preprint) that the generation of the primes is algorithmically computable.

14. Why the universe may be algorithmically computable

By analogy, this suggests that although the measurable values of some individual properties of particles in the universe over time may represent a quantum phenomena, the universe itself may be algorithmically computable if the laws governing the generation of all the particles in the universe over time are algorithmically computable.

Author’s working archives & abstracts of investigations

(Notations, non-standard concepts, and definitions used commonly in these investigations are detailed in this post.)

The Unexplained Intellect: Complexity, Time, and the Metaphysics of Embodied Thought

Christopher Mole is an associate professor of philosophy at the University of British Columbia, Vancouver. He is the author of Attention is Cognitive Unison: An Essay in Philosophical Psychology (OUP, 2011), and The Unexplained Intellect: Complexity, Time, and the Metaphysics of Embodied Thought (Routledge, 2016).

In his preface to The Unexplained Intellect, Mole emphasises that his book is an attempt to provide arguments for (amongst others) the three theses that:

(i) “Intelligence might become explicable if we treat intelligence thought as if it were some sort of computation”;

(ii) “The importance of the rapport between an organism and its environment must $\ldots$ be understood from a broadly computational perspective”;

(iii) “$\ldots$ our difficulties in accounting for our psychological orientation with respect to time are indications of the need to shift our philosophical focus away from mental states—which are altogether too static—and towards a theory of the mind in which it is dynamic mental entities that are taken to be metaphysically foundational”.

The Brains blog

Mole explains at length his main claims in The Unexplained Intellect—and the cause that those claims serve—in a lucid and penetrating, VI-part, series of invited posts in The Brains blog (a leading forum for work in the philosophy and science of mind that was founded in 2005 by Gualtiero Piccinini, and has been administered by John Schwenkler since late 2011).

In these posts, Mole seeks to make the following points.

I: The Unexplained Intellect: The mind is not a hoard of sentences

We do not currently have a satisfactory account of how minds could be had by material creatures. If such an account is to be given then every mental phenomenon will need to find a place within it. Many will be accounted for by relating them to other things that are mental, but there must come a point at which we break out of the mental domain, and account for some things that are mental by reference to some that are not. It is unclear where this break out point will be. In that sense it is unclear which mental entities are, metaphysically speaking, the most fundamental.

At some point in the twentieth century, philosophers fell into the habit of writing as if the most fundamental things in the mental domain are mental states (where these are thought of as states having objective features of the world as their truth-evaluable contents). This led to a picture in which the mind was regarded as something like a hoard of sentences. The philosophers and cognitive scientists who have operated with this picture have taken their job to be telling us what sort of content these mental sentences have, how that content is structured, how the sentences come to have it, how they get put into and taken out of storage, how they interact with one another, how they influence behaviour, and so on.

This emphasis on states has caused us to underestimate the importance of non-static mental entities, such as inferences, actions, and encounters with the world. If we take these dynamic entities to be among the most fundamental of the items in the mental domain, then — I argue — we can avoid a number of philosophical problems. Most importantly, we can avoid a picture in which intelligent thought would be beyond the capacities of any physically implementable system.

II: The Unexplained Intellect: Computation and the explanation of intelligence

A lot of philosophers think that consciousness is what makes the mind/body problem interesting, perhaps because they think that consciousness is the only part of that problem that remains wholly philosophical. Other aspects of the mind are taken to be explicable by scientific means, even if explanatorily adequate theories of them remain to be specified.

$\ldots$ I’ll remind the reader of computability theory’s power, with a view to indicating how it is that the discoveries of theoretical computer scientists place constraints on our understanding of what intelligence is, and of how it is possible.

III: The Unexplained Intellect: The importance of computability

If we found that we had been conceiving of intelligence in such a way that intelligence could not be modelled by a Turing Machine, our response should not be to conclude that some alternative must be found to a ‘Classically Computational Theory of the Mind’. To think only that would be to underestimate the scope of the theory of computability. We should instead conclude that, on the conception in question, intelligence would (be) absolutely inexplicable. This need to avoid making intelligence inexplicable places constraints on our conception of what intelligence is.

IV: The Unexplained Intellect: Consequences of imperfection

The lesson to be drawn is that, if we think of intelligence as involving the maintenance of satisfiable beliefs, and if we think of our beliefs as corresponding to a set of representational states, then our intelligence would depend on a run of good luck the chances of which are unknown.

My suggestion is that we can reach a more explanatorily satisfactory conception of intelligence if we adopt a dynamic picture of the mind’s metaphysical foundations.

V: The Unexplained Intellect: The importance of rapport

I suggest that something roughly similar is true of us. We are not guaranteed to have satisfiable beliefs, and sometimes we are rather bad at avoiding unsatisfiability, but such intelligence as we have is to be explained by reference to the rapport between our minds and the world.

Rather than starting from a set of belief states, and then supposing that there is some internal process operating on these states that enables us to update our beliefs rationally, we should start out by accounting for the dynamic processes through which the world is epistemically encountered. Much as the three-colourable map generator reliably produces three-colourable maps because it is essential to his map-making procedure that borders appear only where they will allow for three colorability, so it is essential to what it is for a state to be a belief that beliefs will appear only if there is some rapport between the believer and the world. And this rapport — rather than any internal processing considered in isolation from it — can explain the tendency for our beliefs to respect the demands of intelligence.

VI: The Unexplained Intellect: The mind’s dynamic foundations

$\ldots$ memory is essentially a form of epistemic retentiveness: One’s present knowledge counts as an instance of memory when and only when it was attained on the basis of an epistemic encounter that lies in one’s past. One can epistemically encounter a proposition as the conclusion of an argument, and so can encounter it before the occurrence of any event to which it pertains, but one cannot encounter an event in that way. In the resulting explanation of memory’s temporal asymmetry, it is the dynamic events of epistemic encountering to which we must make reference. These encounters, and not the knowledge states to which they lead, do the lion’s share of the explanatory work.

A: Simplifying Mole’s perspective

It may help simplify Mole’s thought-provoking perspective if we make an arbitrary distinction between:

(i) The mind of an applied scientist, whose primary concern is our sensory observations of a ‘common’ external world;

(ii) The mind of a philosopher, whose primary concern is abstracting a coherent perspective of the external world from our sensory observations; and

(iii) The mind of a mathematician, whose primary concern is adequately expressing such abstractions in a formal language of unambiguous communication.

My understanding of Mole’s thesis, then, is that:

(a) although a mathematician’s mind may be capable of defining the ‘truth’ value of some logical and mathematical propositions without reference to the external world,

(b) the ‘truth’ value of any logical or mathematical proposition that purports to represent any aspect of the real world must be capable of being evidenced objectively to the mind of an applied scientist; and that,

(c) of the latter ‘truths’, what should interest the mind of a philosopher is whether there are some that are ‘knowable’ completely independently of the passage of time, and some that are ‘knowable’ only partially, or incrementally, with the passage of time.

B. Support for Mole’s thesis

It also seems to me that Mole’s thesis implicitly subsumes, or at the very least echoes, the belief expressed by Chetan R. Murthy (‘An Evaluation Semantics for Classical Proofs‘, Proceedings of Sixth IEEE Symposium on Logic in Computer Science, pp. 96-109, 1991; also Cornell TR 91-1213):

“It is by now folklore … that one can view the values of a simple functional language as specifying evidence for propositions in a constructive logic …”

If so, the thesis seems significantly supported by the following paper that is due to appear in the December 2016 issue of ‘Cognitive Systems Research’:

The CSR paper implicitly suggests that there are, indeed, (only?) two ways of assigning ‘true’ or ‘false’ values to any mathematical description of real-world events.

C. Algorithmic computability

First, a number theoretical relation $F(x)$ is algorithmically computable if, and only if, there is an algorithm $AL_{F}$ that can provide objective evidence (cf. ibid Murthy 91) for deciding the truth/falsity of each proposition in the denumerable sequence $\{F(1), F(2), \ldots\}$.

(We note that the concept of algorithmic computability’ is essentially an expression of the more rigorously defined concept of realizability’ on p.503 of Stephen Cole Kleene’s ‘Introduction to Metamathematics‘, North Holland Publishing Company, Amsterdam.)

D. Algorithmic verifiability

Second, a number-theoretical relation $F(x)$ is algorithmically verifiable if, and only if, for any given natural number $n$, there is an algorithm $AL_{(F,\ n)}$ which can provide objective evidence for deciding the truth/falsity of each proposition in the finite sequence $\{F(1), F(2), \ldots, F(n)\}$.

We note that algorithmic computability implies the existence of an algorithm that can finitarily decide the truth/falsity of each proposition in a well-defined denumerable sequence of propositions, whereas algorithmic verifiability does not imply the existence of an algorithm that can finitarily decide the truth/falsity of each proposition in a well-defined denumerable sequence of propositions.

The following theorem (Theorem 2.1, p.37 of the CSR paper) shows that although every algorithmically computable relation is algorithmically verifiable, the converse is not true:

Theorem: There are number theoretic functions that are algorithmically verifiable but not algorithmically computable.

E. The significance of algorithmic ‘truth’ assignments for Mole’s theses

The significance of such algorithmic ‘truth’ assignments for Mole’s theses is that:

Algorithmic computability—reflecting the ambit of classical Newtonian mechanics—characterises natural phenomena that are determinate and predictable.

Such phenomena are describable by mathematical propositions that can be termed as ‘knowable completely’, since at any point of time they are algorithmically computable as ‘true’ or ‘false’.

Hence both their past and future behaviour is completely computable, and their ‘truth’ values are therefore ‘knowable’ independent of the passage of time.

Algorithmic verifiability—reflecting the ambit of Quantum mechanics—characterises natural phenomena that are determinate but unpredictable.

Such phenomena are describable by mathematical propositions that can only be termed as ‘knowable incompletely’, since at any point of time they are only algorithmically verifiable, but not algorithmically computable, as ‘true’ or ‘false’

Hence, although their past behaviour is completely computable, their future behaviour is not completely predictable, and their ‘truth’ values are not independent of the passage of time.

F. Where Mole’s implicit faith in the adequacy of set theoretical representations of natural phenomena may be misplaced

It also seems to me that, although Mole’s analysis justifiably holds that the:

$\ldots$ importance of the rapport between an organism and its environment”

has been underacknowledged, or even overlooked, by existing theories of the mind and intelligence, it does not seem to mistrust, and therefore ascribe such underacknowledgement to any lacuna in, the mathematical and epistemic foundations of the formal language in which almost all descriptions of real-world events are currently sought to be expressed, which is the language of the set theory ZF.

G. Any claim to a physically manifestable ‘truth’ must be objectively accountable

Now, so far as applied science is concerned, history teaches us that the ‘truth’ of any mathematical proposition that purports to represent any aspect of the external world must be capable of being evidenced objectively; and that such ‘truths’ must not be only of a subjective and/or revelationary nature which may require truth-certification by evolutionarily selected prophets.

(Not necessarily religious—see, for instance, Melvyn B. Nathanson’s remarks, “Desperately Seeking Mathematical Truth“, in the Opinion piece in the August 2008 Notices of the American Mathematical Society, Vol. 55, Issue 7.)

The broader significance of seeking objective accountability is that it admits the following (admittedly iconoclastic) distinction between the two fundamental mathematical languages:

1. The first-order Peano Arithmetic PA as the language of science; and

2. The first-order Set Theory ZF as the language of science fiction.

It is a distinction that is faintly reflected in Stephen G. Simpson’s more conservative perspective in his paper ‘Partial Realizations of Hilbert’s Program‘ (#6.4, p.15):

“Finitistic reasoning (my read: ‘First-order Peano Arithmetic PA’) is unique because of its clear real-world meaning and its indispensability for all scientific thought. Nonfinitistic reasoning (my read: ‘First-order Set Theory ZF’) can be accused of referring not to anything in reality but only to arbitrary mental constructions. Hence nonfinitistic mathematics can be accused of being not science but merely a mental game played for the amusement of mathematicians.”

The distinction is supported by the formal argument (detailed in the above-cited CSR paper) that:

(i) PA has two, hitherto unsuspected, evidence-based interpretations, the first of which can be treated as circumscribing the ambit of human reasoning about ‘true’ arithmetical propositions; and the second can be treated as circumscribing the ambit of mechanistic reasoning about ‘true’ arithmetical propositions.

What this means is that the language of arithmetic—formally expressed as PA—can provide all the foundational needs for all practical applications of mathematics in the physical sciences. This was was the point that I sought to make—in a limited way, with respect to quantum phenomena—in the following paper presented at Unilog 2015, Istanbul last year:

(Presented on 26’th June at the workshop on ‘Emergent Computational Logics’ at UNILOG’2015, 5th World Congress and School on Universal Logic, 20th June 2015 – 30th June 2015, Istanbul, Turkey.)

(ii) Since ZF axiomatically postulates the existence of an infinite set that cannot be evidenced (and which cannot be introduced as a constant into PA, or as an element into the domain of any interpretation of PA, without inviting inconsistency—see Theorem 1 in $\S$4 of this post), it can have no evidence-based interpretation that could be treated as circumscribing the ambit of either human reasoning about ‘true’ set-theoretical propositions, or that of mechanistic reasoning about ‘true’ set-theoretical propositions.

The language of set theory—formally expressed as ZF—thus provides the foundation for abstract structures that—although of possible interest to philosophers of science—are only mentally conceivable by mathematicians subjectively, and have no verifiable physical counterparts, or immediately practical applications of mathematics, that can materially impact on the study of physical phenomena.

The significance of this distinction can be expressed more vividly in Russell’s phraseology as:

(iii) In the first-order Peano Arithmetic PA we always know what we are talking about, even though we may not always know whether it is true or not;

(iv) In the first-order Set Theory we never know what we are talking about, so the question of whether or not it is true is only of fictional interest.

H. The importance of Mole’s ‘rapport’

Accordingly, I see it as axiomatic that the relationship between an evidence-based mathematical language and the physical phenomena that it purports to describe, must be in what Mole terms as ‘rapport’, if we view mathematics as a set of linguistic tools that have evolved:

(a) to adequately abstract and precisely express through human reasoning our observations of physical phenomena in the world in which we live and work; and

(b) unambiguously communicate such abstractions and their expression to others through objectively evidenced reasoning in order to function to the maximum of our co-operative potential in acieving a better understanding of physical phenomena.

This is the perspective that I sought to make in the following paper presented at Epsilon 2015, Montpellier, last June, where I argue against the introduction of ‘unspecifiable’ elements (such as completed infinities) into either a formal language or any of its evidence-based interpretations (in support of the argument that since a completed infinity cannot be evidence-based, it must therefore be dispensible in any purported description of reality):

(Presented on 10th June at the Epsilon 2015 workshop on ‘Hilbert’s Epsilon and Tau in Logic, Informatics and Linguistics’, 10th June 2015 – 12th June 2015, University of Montpellier, France.)

I. Why mathematical reasoning must reflect an ‘agnostic’ perspective

Moreover, from a non-mathematician’s perspective, a Propertarian like Curt Doolittle would seem justified in his critique (comment of June 2, 2016 in this Quanta review) of the seemingly ‘mystical’ and ‘irrelevant’ direction in which conventional interpretations of Hilbert’s ‘theistic’ and Brouwer’s ‘atheistic’ reasoning appear to have pointed mainstream mathematics for, as I argue informally in an earlier post, the ‘truths’ of any mathematical reasoning must reflect an ‘agnostic’ perspective.

Author’s working archives & abstracts of investigations

(Notations, non-standard concepts, and definitions used commonly in these investigations are detailed in this post.)

In a recent paper A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory, authors Adam Yedidia and Scott Aaronson argue upfront in their Introduction that:

Like any axiomatic system capable of encoding arithmetic, ZFC is constrained by Gödel’s two incompleteness theorems. The first incompleteness theorem states that if ZFC is consistent (it never proves both a statement and its opposite), then ZFC cannot also be complete (able to prove every true statement). The second incompleteness theorem states that if ZFC is consistent, then ZFC cannot prove its own consistency. Because we have built modern mathematics on top of ZFC, we can reasonably be said to have assumed ZFC’s consistency.

The question arises:

How reasonable is it to build modern mathematics on top of a Set Theory such as ZF?

Some immediate points to ponder upon (see also reservations expressed by Stephen G. Simpson in Logic and Mathematics and in Partial Realizations of Hilbert’s Program):

1. “Like any axiomatic system capable of encoding arithmetic, …”

The implicit assumption here that every ZF formula which is provable about the finite ZF ordinals must necessarily interpret as a true proposition about the natural numbers is fragile since, without such an assumption, we can only conclude from Goodstein’s argument (see Theorem 1.1 here) that a Goodstein sequence defined over the finite ZF ordinals must terminate even if the corresponding Goodstein sequence over the natural numbers does not terminate!

2. “ZFC is constrained by Gödel’s two incompleteness theorems. The first incompleteness theorem states that if ZFC is consistent (it never proves both a statement and its opposite), then ZFC cannot also be complete (able to prove every true statement). The second incompleteness theorem states that if ZFC is consistent, then ZFC cannot prove its own consistency.”

The implicit assumption here is that ZF is $\omega$-consistent, which implies that ZF is consistent and must therefore have an interpretation over some mathematically definable structure in which ZF theorems interpret as ‘true’.

The question arises: Must such ‘truth’ be capable of being evidenced objectively, or is it only of a subjective, revelationary, nature (which may require truth-certification by evolutionarily selected prophets—see Nathanson’s remarks as cited in this post)?

The significance of seeking objective accountbility is that in a paper, “The Truth Assignments That Differentiate Human Reasoning From Mechanistic Reasoning: The Evidence-Based Argument for Lucas’ Gödelian Thesis“, which is due to appear in the December 2016 issue of Cognitive Systems Research, we show (see also this post) that the first-order Peano Arithmetic PA:

(i) is finitarily consistent; but

(ii) is not $\omega$-consistent; and

(iii) has no ‘undecidable’ arithmetical proposition (whence both of Gödel’s Incompleteness Theorems hold vacuously so far as the arithmetic of the natural numbers is concerned).

3. “Because we have built modern mathematics on top of ZFC, we can reasonably be said to have assumed ZFC’s consistency.”

Now, one justification for such an assumption (without which it may be difficult to justify building modern mathematics on top of ZF) could be the belief that acquisition of set-theoretical knowledge by students of mathematics has some essential educational dimension.

If so, one should take into account not only the motivations of such a student for the learning of mathematics, but also those of a mathematician for teaching it.

This, in turn, means that both the content of the mathematics which is to be learnt (or taught), as well as the putative utility of such learning (or teaching) for a student (or teacher), merit consideration.

Considering content, I would iconoclastically submit that the least one may then need to accomodate is the following distinction between the two fundamental mathematical languages:

1. The first-order Peano Arithmetic PA, which is the language of science; and

2. The first-order Set Theory ZF, which is the language of science fiction.

A distinction that is reflected in Stephen G. Simpson’s more conservative perspective in Partial Realizations of Hilbert’s Program ($\S$6.4, p.15):

Finitistic reasoning (read ‘First-order Peano Arithmetic PA’) is unique because of its clear real-world meaning and its indispensability for all scientific thought. Nonfinitistic reasoning (read ‘First-order Set Thyeory ZF’) can be accused of referring not to anything in reality but only to arbitrary mental constructions. Hence nonfinitistic mathematics can be accused of being not science but merely a mental game played for the amusement of mathematicians.

Reason:

(i) PA has two, hitherto unsuspected, evidence-based interpretations (see this post), the first of which can be treated as circumscribing the ambit of human reasoning about true’ arithmetical propositions; and the second can be treated as circumscribing the ambit of mechanistic reasoning about true’ arithmetical propositions.

It is this language of arithmetic—formally expressed as PA—that provides the foundation for all practical applications of mathematics where the latter could be argued as having an essential educational dimension.

(ii) Since ZF axiomatically postulates the existence of an infinite set that cannot be evidenced (and which cannot be introduced as a constant into PA, or as an element into the domain of any interpretation of PA, without inviting inconsistency—see paragraph 4.2 of this post), it can have no evidence-based interpretation that could be treated as circumscribing the ambit of either human reasoning about true’ set-theoretical propositions, or that of mechanistic reasoning about true’ set-theoretical propositions.

The language of set theory—formally expressed as ZF—thus provides the foundation for abstract structures that are only mentally conceivable by mathematicians (subjectively?), and have no physical counterparts, or immediately practical applications of mathematics, which could meaningfully be argued as having an essential educational dimension.

The significance of this distinction can be expressed more vividly in Russell’s phraseology as:

(iii) In the first-order Peano Arithmetic PA we always know what we are talking about, even though we may not always know whether it is true or not;

(iv) In the first-order Set Theory we never know what we are talking about, so the question of whether or not it is true is only of fictional interest.

The distinction is lost when—as seems to be the case currently—we treat the acquisition of mathematical knowledge as necessarily including the body of essentially set-theoretic theorems—to the detriment, I would argue, of the larger body of aspiring students of mathematics whose flagging interest in acquiring such a wider knowledge in universities around the world reflects the fact that, for most students, their interests seem to lie primarily in how a study of mathematics can enable them to:

(a) adequately abstract and precisely express through human reasoning their experiences of the world in which they live and work; and

(b) unambiguously communicate such abstractions and their expression to others through objectively evidenced reasoning in order to function to the maximum of their latent potential in acieving their personal real-world goals.

In other words, it is not obvious how how any study of mathematics that has the limited goals (a) and (b) can have any essentially educational dimension that justifies the assumption that ZF is consistent.

Author’s working archives & abstracts of investigations

Preamble

I find a frustrating equivocity[*] in standard literature between the intent behind the definitions of the classes $P$ and $NP$ as explained informally in terms of ‘verifiability’ and ‘decidability’, and the formal definitions of these two classes.

I call it the $PvNP$ Separation Problem.

My understanding of the intent commonly expressed in standard literature is that:

Verifiability: A number-theoretical formula $F(x)$ is verifiable under an interpretation (and should by intent be defined in $NP$) if, and only if, for any given natural number $n$, there is a deterministic algorithm $AL_{(F,\ n)}$ which can provide objective evidence for deciding the value of each formula in the finite sequence $\{F(1), F(2), \ldots, F(n)\}$.

Decidability: A number theoretical formula $F(x)$ is decidable under an interpretation (and should by intent be defined in $P$) if, and only if, there is a deterministic algorithm $AL_{F}$ that can provide objective evidence for deciding the value of each formula in the denumerable sequence $\{F(1), F(2), \ldots\}$.

In other words, for me ‘decidability’ should imply the existence of a deterministic algorithm that can decide the truth/falsity of each proposition in a well-defined denumerable sequence of propositions; whereas ‘verifiability’ need not imply the existence of a deterministic algorithm that can decide the truth/falsity of each proposition in a well-defined denumerable sequence of propositions.

For reasons and in ways that I cannot quite grasp as yet, it seems to me that standard definitions of the two classes $P$ and $NP$ only muddy the issue by associating the two concepts with terms such as ‘quickly’, ‘polynomial-time’ and ‘non-deterministic’; and by requiring introduction of some corresponding measure/s of computational complexity.

In other words, standard definitions of the two classes assert that:

Verifiability (standard): A number-theoretical formula $F(x)$ is verifiable under an interpretation (and is defined in $NP$) if, and only if, for any given natural number $n$, there is a deterministic polynomial-time algorithm $AL_{(F,\ n)}$ which can provide objective evidence for deciding the value of each formula in the finite sequence $\{F(1), F(2), \ldots, F(n)\}$.

Decidability (standard): A number theoretical formula $F(x)$ is decidable under an interpretation (and is defined in $P$) if, and only if, there is a deterministic polynomial-time algorithm $AL_{F}$ that can provide objective evidence for deciding the value of each formula in the denumerable sequence $\{F(1), F(2), \ldots\}.$

The following argument attempts to view the consequence for the $PvNP$ problem if we separate the two classes $P$ and $NP$ essentially as intended in the first case above.

The justification for this perspective is the formal distinction between the two concepts of ‘algorithmic verifiability’ and ‘algorithmic computability’ introduced in the Birmingham paper.

The significance that such a distinction may have for the first-order Peano Arithmetic $PA$ in particular—and for the foundations of mathematics, logic and computability in general—has already been suggested in this post.

Abstract

In this investigation we now consider the consequences of separating the classes $P$ and $NP$ logically from a similar—finitary arithmetical rather than computational—perspective.

This perspective too is based on explicitly highlighting that the assignment of satisfaction and truth values to number-theoretic formulas under an interpretation can be constructively defined in two distinctly different ways:

(a) in terms of algorithmic verifiability, and

(b) in terms of algorithmic computability.

From this perspective it can be seen that standard definitions of the classes $P$ and $NP$ implicitly assume without proof that:

Cook’s Thesis: If a propositional formula is algorithmically verifiable in polynomial time, then it is algorithmically computable.

This imples that the differentiation between the two classes is only quantitative, and can therefore be adequately expressed in terms of computational complexity.

However, we argue that there are classically defined arithmetic formulas which are algorithmically verifiable but not algorithmically computable; and so the differentiation between the classes $P$ and $NP$ can also be defined qualitatively, and need not be expressed only in terms of computational complexity.

Specifically, we show how Gödel’s $\beta$-function uniquely corresponds some real numbers to algorithmically verifiable arithmetical formulas that are not algorithmically computable.[**]

Introduction

“The computability precursors of the classes $P$ and $NP$ are the classes of decidable and c.e. (computably enumerable) languages, respectively. We say that a language $L$ is c.e. i.e. (or semi-decidable) iff $L = L(M)$ for some Turing machine $M$. We say that $L$ is decidable iff $L = L(M)$ for some Turing machine $M$ which satisfies the condition that $M$ halts on all input strings $w$. …

Thus the problem Satisfiability is: Given a propositional formula $F$, determine whether $F$ is satisfiable. To show that this is in $NP$ we define the polynomial-time checking relation $R(x, y)$, which holds iff $x$ codes a propositional formula $F$ and $y$ codes a truth assignment to the variables of $F$ which makes $F$ true.”

… Stephen Cook, The P versus NP Problem, 2000, Clay Mathematical Institute, Providence, USA.

In this investigation we shall argue that standard interpretations—such as the above[1]—of the formal definitions of the classes $P$ and $NP$ leave room for ambiguity.

Specifically, such interpretations fail to explicitly highlight that the assignment of satisfaction and truth values to number-theoretic formulas under an interpretation can be constructively defined in two distinctly different ways[1a]:

(a) in terms of algorithmic verifiability (Definition 1 below);

It immediately follows from this definition that a number-theoretical formula $F$ is algorithmically verifiable under an interpretation (and should therefore be defined in $NP$) if, and only if, we can define a checking relation $R(x, y)$[2]—where $x$ codes a propositional formula $F$ and $y$ codes a truth assignment to the variables of $F$—such that, for any given natural number values $(m, n)$, there is a deterministic algorithm which will finitarily decide whether or not $R(m, n)$ holds over the domain $\mathbb{N}$ of the natural numbers.

(b) in terms of algorithmic computability (Definition 2 below).

It immediately follows from this definition that a number-theoretical formula $F$ is algorithmically computable under an interpretation (and should therefore be defined in $P$) if, and only if, we can define a checking relation $R(x, y)$[3]—where $x$ codes a propositional formula $F$ and $y$ codes a truth assignment to the variables of $F$—such that there is a deterministic algorithm which, for any given natural number values $(m, n)$, will finitarily decide whether or not $R(m, n)$ holds over the domain $\mathbb{N}$ of the natural numbers.

In other words, standard interpretations of the classes $P$ and $NP$ implicitly assume without proof that:

Cook’s Thesis: If a propositional formula is algorithmically verifiable in polynomial-time, then it is algorithmically computable.

It would follow from such a perspective that the differentiation between the classes $P$ and $NP$ is only quantitative, and can therefore be adequately expressed in terms of computational complexity.

However, we shall argue that—since the two concepts are well-defined[3a]—there are classically defined arithmetic formulas which are algorithmically verifiable but not algorithmically computable; and so the differentiation between the classes $P$ and $NP$ is also qualitative, and cannot be adequately expressed in terms of only computational complexity.

The $PvNP$ Separation Problem

Accordingly, in this investigation we shall ignore both Cook’s Thesis and polynomial-time computations, and address instead the following non-standard (NS) formulation of the $PvNP$ Separation Problem in arithmetic:

Non-standard $PvNP\ (NS)$: Is there an arithmetical formula $F$ that is algorithmically verifiable but not algorithmically computable?

We shall first show how Gödel’s $\beta$-function uniquely corresponds each classically defined real number to an algorithmically verifiable arithmetical formula.

Since classical theory admits the existence of real numbers that are not algorithmically computable[4], we shall conclude that classical theory must also admit the existence of arithmetical formulas that are algorithmically verifiable but not algorithmically computable.

Algorithmically verifiable and algorithmically computable formulas

Definition 1: A number-theoretical formula $F(x)$ is algorithmically verifiable under an interpretation if, and only if, for any given natural number $n$, there is a deterministic algorithm $AL_{(F,\ n)}$ which can provide objective evidence[5] for deciding the value of each formula in the finite sequence $\{F(1), F(2), \ldots, F(n)\}$.

The concept is well-defined in the sense that, first, every atomic number-theoretical formula is algorithmically verifiable as above[6]; further, by Tarski’s definitions[7], the algorithmic verifiability of the formulas of a formal language which contain logical constants can be inductively defined under an interpretation in terms of the algorithmic verifiability of the interpretations of the atomic formulas of the language.

In particular[8], the formulas of the first order Peano Arithmetic PA are constructively decidable under the standard interpretation of PA over the domain $\mathbb{N}$ of the natural numbers if, and only if, they are algorithmically verifiable under the interpretation.[9]

Definition 2: A number theoretical formula $F(x)$ is algorithmically computable under an interpretation if, and only if, there is a deterministic algorithm $AL_{F}$ that can provide objective evidence for deciding the value of each formula in the denumerable sequence $\{F(1), F(2), \ldots\}$.

This concept too is well-defined in the sense that, first, every atomic number-theoretical formula is algorithmically computable as above[10]; further, by Tarski’s definitions, the algorithmic computability of the formulas of a formal language which contain logical constants can also be inductively defined under an interpretation in terms of the algorithmic computability of the interpretations of the atomic formulas of the language.

In particular[11], the PA-formulas are constructively decidable under an algorithmic interpretation of PA over $\mathbb{N}$ if, and only if, they are algorithmically computable under the interpretation.[12]

We note that:

Lemma 1: There are algorithmically verifiable number theoretical formulas which are not algorithmically computable.

Proof: Let $r(n)$ denote the $n^{th}$ digit in the decimal expression $\sum_{i=1}^{\infty}r(i).10^{-i}$ of a putatively given real number $\mathbb{R}$ in the interval $0 < \mathbb{R} \leq 1$.

By the definition of the real number $\mathbb{R}$ as the limit of the Cauchy sequence of rationals $\{\sum_{i=1}^{k}r(i).10^{-i}: k = 1, 2, \ldots\}$, it follows that $r(n)$ is an algorithmically verifiable number-theoretic function.

Since the set of algorithmically computable reals is countable[13], Cantor’s diagonal argument[14] shows that there are real numbers that are not algorithmically computable.

The Lemma follows. $\Box$

We note that algorithmic computability implies the existence of a deterministic algorithm that can decide the truth/falsity of each proposition in a well-defined denumerable sequence of propositions, whereas algorithmic verifiability does not imply the existence of a deterministic algorithm that can decide the truth/falsity of each proposition in a well-defined denumerable sequence of propositions.[15]

Gödel’s $\beta$-function

We note next that Gödel’s $\beta$-function is the primitive recursive number-theoretic function defined by[16]:

Definition 3: $\beta (x_{1}, x_{2}, x_{3}) = rm(1+(x_{3}+ 1) \star x_{2}, x_{1})$, where $rm(x_{1}, x_{2})$ denotes the remainder obtained on dividing $x_{2}$ by $x_{1}$.

We also note that:

Lemma 2: For any non-terminating sequence of values $f(0), f(1), \ldots$, we can construct natural numbers $b_{k},\ c_{k}$ such that:

(i) $j_{k} = max(k, f(0), f(1), \ldots, f(k))$;

(ii) $c_{k} = j_{k}$!;

(iii) $\beta(b_{k}, c_{k}, i) = f(i)$ for $0 \leq i \leq k$.

Proof: This is a standard result[17]. $\Box$

Now we have the standard definition[18]:

Definition 4: A number-theoretic function $f(x_{1}, \ldots, x_{n})$ is said to be representable in the first order Peano Arithmetic PA if, and only if, there is a PA formula $[F(x_{1}, \dots, x_{n+1})]$[19] with the free variables $[x_{1}, \ldots, x_{n+1}]$, such that, for any given natural numbers $k_{1}, \ldots, k_{n+1}$:

(i) if $f(k_{1}, \ldots, k_{n}) = k_{n+1}$ then PA proves: $[F(k_{1}, \ldots, k_{n}, k_{n+1})]$;

(ii) PA proves: $[(\exists_{1} x_{n+1})F(k_{1}, \ldots, k_{n}, x_{n+1})]$.

The function $f(x_{1}, \ldots, x_{n})$ is said to be strongly representable in PA if we further have that:

(iii) PA proves: $[(\exists_{1} x_{n+1})F(x_{1}, \ldots, x_{n}, x_{n+1})]$

We also have that:

Lemma 3: $\beta(x_{1}, x_{2}, x_{3})$ is strongly represented in PA by $[Bt(x_{1}, x_{2}, x_{3}, x_{4})]$, which is defined as follows:

$[(\exists w)(x_{1} = ((1 + (x_{3} + 1)\star x_{2}) \star w + x_{4}) \wedge (x_{4} < 1 + (x_{3} + 1) \star x_{2}))]$.

Proof: This is a standard result[20]. $\Box$

An arithmetical perspective on the $PvNP$ Separation Problem

We finally argue that:

Theorem 1: There is an arithmetical formula that is algorithmically verifiable but not algorithmically computable under any sound interpretation of PA.

Proof: Let $\{r(n)\}$ be the denumerable sequence defined by the denumerable sequence of digits in the decimal expansion $\sum_{i=1}^{\infty}r(i).10^{-i}$ of a putatively given real number $\mathbb{R}$ in the interval $0 < \mathbb{R} \leq 1$.

By Lemma 2, for any given natural number $k$, there are natural numbers $b_{k}, c_{k}$ such that, for any $1 \leq n \leq k$:

$\beta(b_{k}, c_{k}, n) = r(n)$.

By Lemma 3, $\beta(x_{1}, x_{2}, x_{3})$ is strongly represented in PA by $[Bt(x_{1}, x_{2}, x_{3}, x_{4})]$ such that, for any $1 \leq n \leq k$:

If $\beta(b_{k}, c_{k}, n) = r(n)$ then PA proves $[Bt(b_{k}, c_{k}, n, r(n))]$.

We now define the arithmetical formula $[R(b_{k}, c_{k}, n)]$ for any $1 \leq n \leq k$ by:

$[R(b_{k}, c_{k}, n) = r(n)]$ if, and only if, PA proves $[Bt(b_{k}, c_{k}, n, r(n))]$.

Hence every putatively given real number $\mathbb{R}$ in the interval $0 < \mathbb{R} \leq 1$ uniquely corresponds to an algorithmically verifiable arithmetical formula $[R(x)]$ since:

For any $k$, the primitive recursivity of $\beta(b_{k}, c_{k}, n)$ yields a deterministic algorithm AL$_{(\beta, \mathbb{R}, k)}$ that can provide objective evidence for deciding the unique value of each formula in the finite sequence $\{[R(1), R(2), \ldots, R(k)]\}$ by evidencing the truth under a sound interpretation of PA for:

$[R(1) = R(b_{k}, c_{k}, 1)]$
$[R(b_{k}, c_{k}, 1) = r(1)]$

$[R(2) = R(b_{k}, c_{k}, 2)]$
$[R(b_{k}, c_{k}, 2) = r(2)]$

$[R(k) = R(b_{k}, c_{k}, k)]$
$[R(b_{k}, c_{k}, k) = r(k)]$.

The correspondence is unique because, if $\mathbb{R}$ and $\mathbb{S}$ are two different putatively given reals in the interval $0 < \mathbb{R},\ \mathbb{S} \leq 1$, then there is always some $m$ for which:

$r(m) \neq s(m)$.

Hence the corresponding arithmetical formulas $[R(n)]$ and $[S(n)]$ are such that:

$[R(n) = r(n)]$ for all $1 \leq n \leq m$.

$[S(n) = s(n)]$ for all $1 \leq n \leq m$.

$[R(m) \neq S(m)]$.

By Lemma 1, there is an algorithmically uncomputable real number $\mathbb{R}$ such that the corresponding PA formula $[(\exists y)(R(x) = y)]$ is also algorithmically uncomputable, but algorithmically verifiable, under a sound interpretation of PA.

The theorem follows. $\Box$

An arithmetical perspective on the $PvNP$ problem

We conclude that if we were to unambiguously define the classes $P\ (NS)$ and $NP\ (NS)$ as in Section 1(a) and Section 1(b) respectively, then it would follow that:

Corollary 1: $NP \neq P\ (NS).$

References

Kl52 Stephen Cole Kleene. 1952. Introduction to Metamathematics. North Holland Publishing Company, Amsterdam.

Me64 Elliott Mendelson. 1964. Introduction to Mathematical Logic. Van Norstrand. pp.145-146.

Mo12 Cristopher Moore. 2012. P vs. NP, Phase Transitions, and Incomputability in the Wild. Presentation given on 18th June 2012 at the Turing Centenary Workshop on The Incomputable at the Kavli Royal Society International Center at Chicheley Hall, Chichely, Buckinghamshire, UK.

Mu91 Chetan R. Murthy. 1991. An Evaluation Semantics for Classical Proofs. Proceedings of Sixth IEEE Symposium on Logic in Computer Science, pp. 96-109, (also Cornell TR 91-1213), 1991.

Ta33 Alfred Tarski. 1933. The concept of truth in the languages of the deductive sciences. In Logic, Semantics, Metamathematics, papers from 1923 to 1938. (p152-378). ed. John Corcoran. 1983. Hackett Publishing Company, Indianapolis.

Tu36 Alan Turing. 1936. On computable numbers, with an application to the Entscheidungsproblem. In M. Davis (ed.). 1965. The Undecidable. Raven Press, New York. Reprinted from the Proceedings of the London Mathematical Society, ser. 2. vol. 42 (1936-7), pp.230-365; corrections, Ibid, vol 43 (1937) pp. 544-546.

An12 Bhupinder Singh Anand. 2012. Evidence-Based Interpretations of PA. In Proceedings of the Symposium on Computational Philosophy at the AISB/IACAP World Congress 2012-Alan Turing 2012, 2-6 July 2012, University of Birmingham, Birmingham, UK.

An13 … 2013. A suggested mathematical perspective for the $EPR$ argument. Presented on 7’th April at the workshop on Logical Quantum Structures‘ at UNILOG’2013, 4’th World Congress and School on Universal Logic, 29’th March 2013 – 7’th April 2013, Rio de Janeiro, Brazil.\

Notes

Return to *: I am not alone! See for instance this blogpost of Timothy Gower’s representing one extreme; and this plaintive appeal representing the other.

Return to **: For a broader perspective on the relation of Gödel’s $\beta$-function to this distinction, see this post.

Return to 1a: The distinction is explicitly introduced—and its significance in establishing a finitary proof of consistency for the first order Peano Arithmetic PA highlighted—in An12.

Return to 2: If $F$ is a formula of the first order Peano Arithmetic PA, the existence of such a checking relation is assured by An12, Theorem 2.

Return to 3: If $F$ is a PA formula, the existence of such a checking relation is assured by An12, Theorem 3.

Return to 3a: See here. We further note informally here how the distinction between the two concepts may have far-reaching and significant consequences not only for the foundations of mathematics, logic and computability, but also for our perspective on the underlying structure of the laws of nature.

Return to 5: “It is by now folklore … that one can view the values of a simple functional language as specifying evidence for propositions in a constructive logic …”; Mu91.

Return to 7: On the inductive assignment of satisfaction and truth values to the formulas of a formal language under an interpretation; Ta33.

Return to 9: We note that the Axiom Schema of Finite Induction can be finitarily verified as true under the standard interpretation of PA with respect to ‘truth’ as defined by the algorithmically verifiable formulas of PA.

Return to 12: We note that the Axiom Schema of Finite Induction can be finitarily verified as true under the standard interpretation of PA with respect to ‘truth’ as defined by the algorithmically computable formulas of PA.

Return to 15: From the point of view of a finitary mathematical philosophy, the significant difference between the two concepts could be expressed (An13) by saying that we may treat the decimal representation of a real number as corresponding to a physically measurable limit—and not only to a mathematically definable limit—if and only if such representation is definable by an algorithmically computable function.

Return to 19: We use square brackets simply as a convenience in informal argumentation to differentiate between a formal expression and its interpretation over some domain when there is a possibility of confusion between the two.

There is indeed cause for disquiet

Jan Pedersen introduces hmself in his LinkedIn profile as a software developer and an artificial intelligence thinker with a passion for philosophy.

So, from a lay person’s perspective, I can empathise with the sense of professional disquietitude that perhaps motivated him recently to invite the following discussion (alive and kicking as of this moment) in the LinkedIn group History and Philosophy of Science’:

“Does mathematics need a new foundation?

Reading George Lakoff’s & Rafael Nunez excellent book Where Mathematics comes from’ leaves me with that impression.

The view that mathematics deals with Platonic like objects in some higher realm is too naïve and does not go well along with several paradoxes and meta-mathematical theories.”

Jan is not alone in his desire to ground his lifes work upon a firmer mathematical, logical and philosophical foundation.

Melvyn B. Nathanson

For instance, the point was forcibly made some time back by Melvyn B. Nathanson that:

“ … many great and important theorems don’t actually have proofs. They have sketches of proofs, outlines of arguments, hints and intuitions that were obvious to the author (at least, at the time of writing) and that, hopefully, are understood and believed by some part of the mathematical community.

But the community itself is tiny. In most fields of mathematics there are few experts. Indeed, there are very few active research mathematicians in the world, and many important problems, so the ratio of the number of mathematicians to the number of problems is small. In every field, there are “bosses” who proclaim the correctness or incorrectness of a new result, and its importance or unimportance.

Sometimes they disagree, like gang leaders fighting over turf. In any case, there is a web of semi-proved theorems throughout mathematics. Our knowledge of the truth of a theorem depends on the correctness of its proof and on the correctness of all of the theorems used in its proof. It is a shaky foundation.”

… “Desperately Seeking Mathematical Truth,“, Opinion piece in the August 2008 Notices of the American Mathematical Society, Vol. 55, Issue 7.

Elliott Mendelson

A similar concern was reflected earlier in another context by Elliott Mendelson:

“Here is the main conclusion I wish to draw: it is completely unwarranted to say that CT is unprovable just because it states an equivalence between a vague, imprecise notion (effectively computable function) and a precise mathematical notion (partial-recursive function).

… The concepts and assumptions that support the notion of partial-recursive function are, in an essential way, no less vague and imprecise than the notion of effectively computable function; the former are just more familiar and are part of a respectable theory with connections to other parts of logic and mathematics. (The notion of effectively computable function could have been incorporated into an axiomatic presentation of classical mathematics, but the acceptance of CT made this unnecessary.) … Functions are defined in terms of sets, but the concept of set is no clearer than that of function and a foundation of mathematics can be based on a theory using function as primitive notion instead of set. Tarski’s definition of truth is formulated in set-theoretic terms, but the notion of set is no clearer, than that of truth. The model-theoretic definition of logical validity is based ultimately on set theory, the foundations of which are no clearer than our intuitive understanding of logical validity.

… The notion of Turing-computable function is no clearer than, nor more mathematically useful (foundationally speaking) than, the notion of an effectively computable function …”

… Second Thoughts About Church’s Thesis and Mathematical Proofs. 1990. Journal of Philosophy 87.5.

Albert G. Dragalin

Another perspective towards the inadequacy of current foundational assumptions is that of Albert G. Dragalin, for whom the central question is:

“… what is the correspondence between real facts and these counterparts in mathematics? This is very deep and difficult philosophical problem, we are very far from solving it completely …

We note three sorts of such difficulties:

1) The impredicativity, i.e. the circular character of definitions for our objects of investigation. This impredicativity is characteristic for the set theoretic theories, it closely concerns using the abstraction of alienation, when a person formulates some thoughts and then uses the thoughts as the subject of investigation, as a separate thing to be considered. In the extreme form this abstraction leads to paradoxes like the famous Liar’s paradox. But even in the more modest fortm of the type theory comprehension axiom we get somje unsurmountable difficulties.

Strictly speaking, even the notion of natural number contains an impredicativity (in the form of an unrestricted arithmetical induction principle) and there were some attempts to construct a predicative arithmetic, but most of mathematicians adopt the thesis that the natural numbers can be considered as given for granted entities (the so-called Kroneker’s thesis).

2) The lack of constructivity. It means that usual theories use the classical logic and, hence, some non-constructive proofs. In combination with the set theory it leads to complicated abstract constructs which have no computational or even no nominalistic ontological sense.

3) The lack of feasibility. It means that even in our constructive proofs we usually do not distinct feasible and not feasible calculations. So our (even ‘practically looking’) results are often principally not feasible, and so they are beyond human ability.”

Geoffrey Hellman and John L. Bell

From a slightly different perspective, Geoffrey Hellman and John L. Bell note that:

“Contrary to the popular (mis)conception of mathematics as a cut-and dried body of universally agreed upon truths and methods, as soon as one examines the foundations of mathematics, one encounters divergences of viewpoint and failures of communication that can easily remind one of religious, schismatic controversy. While there is indeed universal agreement on a substantial body of mathematical results, and while classical methods overwhelmingly dominate actual practice, as soon as one asks questions concerning fundamentals, such as “What is mathematics about?”, “What makes mathematical truths true?”, “What axioms can we accept as unproblematic?”, and notoriously, even “What are the acceptable logical rules by which mathematical proofs can proceed?”, we ﬁnd we have entered a mine-ﬁeld of contentiousness.”

Pluralism and the Foundations of Mathematics. In Itekellersetal:Sp (2006).

William P. Thurston

A similar disquiet is echoed by William P. Thurston:

On the most fundamental level, the foundations of mathematics are much shakier than the mathematics that we do. Most mathematicians adhere to foundational principles that are known to be polite ﬁctions. For example, it is a theorem that there does not exist any way to ever actually construct or even deﬁne a well-ordering of the real numbers. There is considerable evidence (but no proof) that we can get away with these polite ﬁctions without being caught out, but that doesn’t make them right. Set theorists construct many alternate and mutually contradictory “mathematical universes” such that if one is consistent, the others are too. This leaves very little conﬁdence that one or the other is the right choice or the natural choice.

On Proof And Progress In Mathematics. In the Bulletin of the American Mathematical Society. Volume 30, Number 2, April 1994, Pages 161-177.

W. T. Gowers

Whilst introducing this blog I noted two troubling philosophical issues in the foundations of mathematics that seemed to need addressing if mathematicians, logicians and computationalists were to build upon their fundamental assumptions with a reasonably comfortable sense of security.

These were the ones identified and highlighted by W. T. Gowers:

“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?”

… “Does mathematics need a philosophy?“, presented before the Cambridge University Society for the Philosophy of Mathematics and Mathematical Sciences, 2002.

Gila Sher

In a recent thought-provoking survey of the foundational problem of logic, Gila Sher obliquely refers to the problem of satisfactorily defining both mathematical and logical ‘truth’, whilst concluding that the issue is essentially one of inadequate methodology:

“It is an interesting fact that, with a small number of exceptions, a systematic philosophical foundation for logic, a foundation for logic rather than for mathematics or language, has rarely been attempted. …

By a philosophical foundation for logic I mean in this paper a substantive philosophical theory that critically examines and explains the basic features of logic, the tasks logic performs in our theoretical and practical life, the veridicality of logic—including the source of the truth and falsehood of both logical and meta-logical claims, the grounds on which logical theories should be accepted (rejected, or revised), the ways logical theories are constrained and enabled by the mind and the world, the relations between logic and related theories (e.g., mathematics), the source of the normativity of logic, and so on. The list is in principle open-ended since new interests and concerns may be raised by different persons and communities at present and in the future. In addition, the investigation itself is likely to raise new questions (whether logic is similar to other disciplines in requiring a grounding in reality, what the distinctive characteristics of logical operators are, etc.).

A foundational theory of this kind … should provide us with tools for criticizing, justifying, evaluating, constructing, and improving specific theories. These elements—critical examination, veridical justification, epistemic evaluation, and so on, as well as creating theoretical tools for these tasks—are the main elements of what I call “grounding” in this paper. …

Logic, however, is a very broad discipline, and the present investigation does not purport to apply to all its branches. Instead, it focuses on that branch which in our time is often referred to as “mathematical logic” and in earlier times took the forms of syllogistic logic, Fregean logic, and type-theoretic logic. And even here it is largely concerned with finitistic versions of this branch. These and other self-imposed restrictions will enable us to be more specific on the questions we address in this paper and will give us the space to discuss several issues of interest to mathematical as well as philosophical logicians. These include, for example, Feferman’s criticism of what he called the Tarski–Sher thesis (Feferman [1999], [2010]), the relation between logic and mathematics, the possibility of extending structuralism from mathematics to logic, and topics of relevance to model-theoretic logic.

I have said that systematic attempts to construct a philosophical foundation for logic have been rare. But was not the period between the late 19th-century and the early 20th-century a period of “foundational studies in logic and mathematics”, indeed a period of extraordinary growth and remarkable breakthroughs in this area? The answer is “Yes” with a caveat.

Yes, there were foundational investigations and groundbreaking developments, but for the most part they aimed at a foundation for mathematics, with logic playing a mostly instrumental, if crucial, role. Frege, for example, developed a logical system that would provide a foundation for mathematics, but aside from a few hints, did not attempt to provide a systematic philosophical foundation for logic itself. Russell improved and further developed Frege’s logicism, but although he appreciated the need to provide a systematic philosophical explanation of logic itself—one that would answer such questions as: “In virtue of what are logical propositions true?” he despaired of accomplishing this task. Thus he says:

The fundamental characteristic of logic, obviously, is that which is indicated when we say that logical propositions are true in virtue of their form. . . . I confess, however, that I am unable to give any clear account of what is meant by saying that a proposition is “true in virtue of its form”.

… Bertrand Russell, The Principles of Mathematics, In his introduction to the second edition, 1938, p.xii, Norton, New York.

Indeed, many of the momentous discoveries in meta-logic (by Hilbert, Gödel, Turing, and others) are commonly designated as contributions to “meta-mathematics”. These epochal achievements, however, are not irrelevant to the foundational problemof logic. On the contrary, by giving rise to a sophisticated logical framework and establishing its mathematical properties they created a fertile ground for a theoretical foundation for logic. It is all the more surprising, therefore, that few 20th- and 21st-century philosophers have taken up the challenge. Many have believed that a substantive, theoretical foundation for logic is impossible, some have considered it superfluous, quite a few have been content to simply say that logic is obvious, others have viewed logic as conventional, hence not in need of a foundation, and so on.

This tendency to avoid a philosophical engagement with the foundational problem of logic is not limited to the recent past. We can see it in the great philosophical systems of the 17th and 18th century. Take Kant, for example. Without purporting to offer scholarly exegesis of Kant’s philosophy of logic, we may note that Kant’s approach to logic is quite different from his approach to other disciplines. While Kant set out to provide a foundation for human knowledge in its entirety, he took formal logic largely as given. Logic, Kant emphasizes, has not required a major revision since Aristotle, and although there is room for clarifications and adjustments, there is no need for establishing the “certainty” of logic:

That logic has already, from the earliest times, proceeded upon this sure path is evidenced by the fact that since Aristotle it has not required to retrace a single step, unless, indeed, we care to count as improvements the removal of certain needless subtleties or the clearer exposition of its recognised teaching, features which concern the elegance rather than the certainty of the science.

… Immanuel Kant, Critique of Pure Reason,, 1781/7, Bviii, Macmillan, London, translated by N. Kemp Smith, 1929.

The scarcity of attempts to provide a theoretical foundation for logic is especially notable in light of epistemologists’ recognition that logic has a special standing in knowledge. Compare logic and physics, for example. It is quite common to say that physics is bound by the laws of logic but logic is not bound by the laws of physics, that a serious error in logic might undermine our physical theory, but a serious error in physics would not undermine our logical theory. And it stands to reason that the more general, basic and normative a given field of knowledge is, the more important it is to provide it with a foundation. Nevertheless a theoretical foundation for logic, and in particular a non-trivializing foundation, has rarely been attempted. Why?

Clearly, the failure to attempt such a foundation is not due to neglect, oversight, or intellectual limitations. The extraordinary advances in logic and meta-logic on the one hand, and the wealth of attempts to construct a philosophical foundation for mathematics and science on the other, suggest that neither neglect nor intellectual handicaps are the problem. In my view, the source of the problem is methodological. Certain features of the customary foundational methodology make it very problematic to construct a philosophical foundation for logic, and the first step in confronting the foundational problem of logic is, therefore, dealing with the methodological difficulty.”

… “The Foundational Problem of Logic“, Submitted draft of the paper in The Bulletin of Symbolic Logic, Volume 19, Issue 2 (2013), pp.145-198.

What mathematics does need is a greater awareness of the nature of its foundations

So where do we go from here?

In the following pages we shall argue that what mathematics needs is not a new foundation, but a greater awareness of the nature of its existing foundations.

Author’s working archives & abstracts of investigations

(The following arguments summarise the main points sought to be made in this paper)

Why has Lucas’ and Penrose’s faith in their Gödelian arguments remained unshaken despite unassailable critiques?

Most reasoned critiques [1] of John. R. Lucas’ and Roger Penrose’s philosophical Gödelian arguments [2] against computationalism have been unassailable when viewed from their mathematical and logical perspectives.

However, as John R. Lucas’ latest tour de force, Reason and Reality’, appears to suggest, they have failed to satisfactorily explain why Lucas and Penrose—reasonable men both—seemingly remain convinced of the essential soundness of their philosophical argumentations.

One reason could be that Lucas’ and Penrose’s philosophical arguments place unquestioning faith in, and uncritically follow, standard logical and mathematical expositions of classical theory in overlooking what Gödel has implicitly proven in Theorem VI of his seminal 1931 paper on undecidable’ arithmetical propositions [3]; another, that their arguments place similar faith in and, as uncritically, accept Gödel’s own, informal, interpretation [4] of the implications of this Theorem as definitive.

If so, neither the arguments nor their authors should be taken to task on either count for their faith; it is the standard mathematical and logical expositions of Gödel’s reasoning that are ambiguously silent on both issues.

Specifically, we shall first argue that—contrary to the conventional wisdom that Lucas and Penrose may have reasonably accepted in good faith—the Tarskian satisfaction and Tarskian truth [5] of the formulas of an Arithmetic under an interpretation, and the soundness of the Arithmetic itself, can indeed be formally defined in an effectively verifiable manner within the Arithmetic.

We shall then suggest that although this appears to demolish the main reasons offered in support of Lucas’ original Gödelian argument, it yet leaves open the question for consideration in a future post of whether human intelligence and machine intelligence are qualitatively different.

Lucas’ Reason and Reality

The question arises: Why has the possibility of such definitions continued to elude critical philosophical enquiry by Lucas (and perhaps Penrose)?

Part of the answer may lie in Lucas’ panoramic 2006 overview of how the elements of reason and reality have been perceived—and sought to be put in some coherent perspective—by philosophers down the ages, where Lucas reveals candidly what lies at the heart of the philosophy underpinning his Gödelian argument.

It is apparently the belief—presumably based on standard mathematical and logical expositions of Gödel’s reasoning—that the truth of an arithmetical statement—in the context of his argument—is essentially intuitive, and beyond formal verification:

“Gödel’s theorem is difficult to understand, easy to misunderstand. The formal proof shows only that if the system is consistent, then the Gödelian formula is unprovable in the system. Some philosophers have suggested that the system itself is inconsistent. But that is a counsel of despair; and if elementary number theory were inconsistent, deduction would cease to be a paradigm of valid argument. Other philosophers stick their feet in and refuse to recognise the Gödelian proposition as true. And of course if a man refuses to concede as true anything except what can be proved in a formal system, he can avoid any further embarrassment, beyond that of having to be remarkably obdurate to cogent mathematical reasoning. Essentially what he is doing is to deny any application of the word true’. He can understand what the word provable’ means, and can be forced to acknowledge that in a consistent formalisation of elementary number theory there must be formulas which can be neither proved nor disproved in the formalised system. But he refuses to understand what the word true’ means, and see that the proposition expressed by the Gödelian formula must in fact be true.

But we do understand what true’ means, and we learn from Gödel’s theorem that truth outruns provability. That has always been believed by some thinkers, though denied by others, who have shied away from any concept of truth that could not be established against the sceptic by some copper-bottomed proof. But once the concept of proof has been made explicit, and the criteria for being provable clearly laid down, Gödel’s theorem shows that there are truths which go beyond that concept of provable.

We are led, therefore, to reject certain minimalising views of truth and reason. It is possible for propositions to be true, even though we cannot verify them. It make sense to claim truth, to wonder about truth, to seek truth, beyond the limits of assured knowledge.”

… J. R. Lucas, Reason and Reality, Chapter 2 pp.36-37.

How the Gödelian argument appeals to Tarski’s Undefinability Theorem, and why it shouldn’t!

A not inconsiderable factor in the formation of such a philosophical perspective on the nature of arithmetical—and perhaps even mathematical—truth must surely be that standard mathematical and logical expositions of Gödel’s and Tarski’s reasoning hold Tarski’s Theorem [6] as informally implying that the Tarskian truth of the formulas of Peano Arithmetic under its standard interpretation is of necessity subjectively semantic, and cannot be formalised objectively within the Arithmetic.

Tarski’s Undefinability Theorem: The set of Gödel-numbers of the formulas of any first-order Peano Arithmetic which are true in the standard model of the Arithmetic is not arithmetical.

Now, what this Theorem asserts formally is that there is no PA formula $[F(x)]$ such that, if $[p]$ is the numeral corresponding to the Gödel number of the PA formula $[P]$, then $[F(p)]$ is true under the standard interpretation of PA if, and only if, $P^{*}$ is true (where $P^{*}$ is the interpretation of $[P]$ under the standard interpretation of PA).

However, what it is taken to informally imply in standard mathematical and logical expositions of current theory is reflected in the following representative remarks:

“This result can be paraphrased by saying that the notion of arithmetical truth is not arithmetically definable.”

Mendelson.[7]

“… arithmetical truth cannot be defined in arithmetic.”

So, perhaps Lucas and Penrose have—not unreasonably—relied unquestioningly on such informal—but unarguably authoritatively postulated—implication in the formation of philosophical perspectives for their Gödelian arguments.

We shall now argue that the implication does not withstand scrutiny from a finitary perspective.

In what sense should Tarski’s definitions of satisfiability and truth be decidable unequivocally?

We note first that, in order to avoid ambiguity, it is implicitly accepted as self-evident in standard mathematical and logical expositions of current theory that Tarski’s standard definitions of the satisfiability, and truth, of the formulas of a formal language L under a well-defined interpretation M must be capable of being interpreted unequivocally.

For instance, under Tarski’s definitions a formula $[R(x)]$ of L is defined as satisfied under M if, and only if, its corresponding interpretation, say $R^{*}(x)$, holds in M for any assignment of a value $s$ that lies within the range of the variable $x$ in M.

From a finitary perspective however (such as the one detailed here), Tarski’s definitions can be considered mathematically significant only if we assume that, given any $s$ in M, we can unequivocally decide whether, or not, $R(s)$ holds, or must hold, in M.

The formula $[(\forall x)R(x)]$ of L could also, then, be unequivocally defined as true under the interpretation M if, and only if, $[R(x)]$ were satisfied under M.

Moreover, the formula $[\neg(\forall x)R(x)]$ of L would, further, be definable as true under the interpretation M if, and only if, $[(\forall x)R(x)]$ were false under M.

In other words, from a finitary perspective, definitions of mathematical satisfaction and truth under an interpretation can be considered significant only if they can be defined relative to an unequivocal decidability under the interpretation.

What gives an illusory legitimacy to Lucas’ and Penrose’s Gödelian arguments?

Lucas’ and Penrose’s arguments gain an illusory appearance of legitimacy only because standard mathematical and logical expositions of current theory either do not highlight, or are unaware of, both the significance of, and the ambiguity implicit in, a failure to meet such a requirement of unequivocal decidability [8].

For instance, taking L as PA, we have on the one hand the Church-Turing Thesis which suggests that such decidability ought to be algorithmic.

On the other hand, however (as we show here), the decidability of mathematical satisfaction and truth under the standard interpretation of PA is not only left implicit, but invites an ambiguity that is compounded further by weakening the decidability to effective instantiational, rather than algorithmic, decidability.

Moreover, the intuitive perception underlying such implicit weakening is justifible since, by the principle of Occam’s razor, the former decidability is the minimum requirement of Tarski’s definitions.

Both Lucas and Penrose, quite reasonably therefore, attempt to draw philosophical conclusions—from standard mathematical and logical expositions of the content and meaning of Gödel’s meta-logical argument—that cannot but reflect the absence of an explicit definition of formal decidability for the formulas of Peano Arithmetic under its standard interpretation.

Clearly, they should not be held accountable for the validity of the mathematical and logical premises on which they base their philosophical conclusions, since the onus of making the foregoing decidability explicit can only rest upon standard mathematical and logical expositions of classical theory.

Can we explicitly define satisfaction and truth verifiably?

That we can explicitly define the satisfaction and truth of the formulas of a language L under an interpretation M in a verifiable manner becomes evident if we take M to be an interpretation of L in L itself.

We then have the formalisation of the verifiable concepts of formal satisfaction, and formal truth, of the formulas $[R(x)]$ and $[(\forall x)R(x)]$ of L, respectively, in L, as:

The formula $[R(x)]$ of L is defined as formally satisfied under L if, and only if $[R(s)]$ is provable in L for any term $[s]$ that can be substituted for the variable $[x]$ in $[R(x)]$.

The formula $[(\forall x)R(x)]$ of L is formally true in L if, and only if, $[R(x)]$ is formally satisfied in L.

Can we define formal soundness verifiably?

If we, further, define formal soundness as the property that the axioms of a theory are satisfied in the theory itself, and that the rules of inference preserve formal truth, then, it follows that the theorems of any formally sound theory must be formally true in the theory.

(Question: Is the first-order Peano Arithmetic formally sound?)

Gödelian propositions are formally true but formally unprovable

Now, even if the formula $[(\forall x)R(x)]$ is not provable in L, it would be formally true in L if, and only if, the formula $[R(s)]$ were provable in L for any well-defined term $[s]$ of L that could be substituted for $[x]$ in $[R(x)]$.

The constructive existence of such a Gödelian proposition is precisely what Gödel proves by his Theorem VI [9] for any simply consistent Peano Arithmetic such as PA.

He constructs a formula, $[(\forall x)R(x)]$, of PA that is, itself, unprovable in a simply consistent PA even though, for any given numeral $[n]$, the formula $[R(n)]$ is provable in the PA.

So, Gödel has constructed a formally unprovable Arithmetical formula that is not only implicitly true in the standard interpretation of the Arithmetic, but which is also formally true in the Arithmetic in a verifiable, and intuitionistically unobjectionable, manner that leaves no room for dispute as to its truth’ status vis-á-vis the PA axioms!

Moreover, if the Arithmetic can be shown to be formally sound—again in a verifiable, and intuitionistically unobjectionable, manner—then we no longer need appeal to the arguable assumption that the Arithmetic is implicitly sound under the standard interpretation.

We note that PA is said to be sound for a class $S$ of sentences if, whenever PA proves $[\phi]$ with $[\phi]$ in S, then $\phi^{*}$ is true in the structure $\mathbb{N}$ of the natural numbers.

Replacing the philosophically debatable concept of implicit decidability with constructively verifiable definitions of formal decidability under the standard interpretation of PA should, thus, place Lucas’ and Penrose’s Gödelian arguments in better perspective.

Can we define arithmetic truth verifiably within PA?

The significance of the above remarks is highlighted by the following.

Let $[F(x_{1}, \ldots, x_{n})]$ be a PA-formula whose Gödel number in Gödel’s notation [10] is $f$, and let $F^{*}(x_{1}, \ldots, x_{n})$ be its standard interpretation over the structure $\mathbb{N}$ of the natural numbers under which:

(a) the set of non-negative integers is the domain,

(b) the integer $0$ is the interpretation of the numeral $[0]$,

(c) the successor operation (addition of $1$) is the interpretation of the $S$ function (i.e., of $[f_{1}^{1}]$,

(d) ordinary addition and multiplication are the interpretations of $[+]$ and $[\star]$,

(e) the interpretation of the predicate letter $[=]$ is the identity relation.

… Mendelson. [11]

(We note that, by the above definition, the structure of the real numbers is isomorphic to the structure of the PA numerals, and any decidability of the satisfaction and truth of PA formulas under the standard interpretation over $\mathbb{N}$ must therefore reflect a corresponding decidability of the satisfaction and truth of PA formulas under a formal interpretation over the PA numerals. Curiously, standard texts do not highlight this point.)

Now, following Gödel [12], we can define the concept $f$ is a PROVABLE FORMULA of PA’ as:

Bew$_{PA} (f) \equiv (\exists y)y \hspace{+.5ex}B_{PA}\hspace{+.5ex}f$

However, we can also define the concept $f$ is a TRUE FORMULA of PA’ in the above notation as (where $p_{n}$ denotes the $n^{th}$ prime number):

Tr$_{PA} (f) \equiv (\forall u_{1}) \ldots (\forall u_{n})(\exists y)y \hspace{+.5ex}B\hspace{+.5ex} \{ Sb_{PA}(f \begin{array}{c} 17 \\ Z(u_{1}) \end{array} \ldots \begin{array}{c} p_{n+6} \\ Z(u_{n}) \end{array})\}$

In other words, Tr$_{PA} (f)$ holds if, and only if, for any given sequence $[a_{1}, \ldots, a_{n}]$ of numerals, the PA-formula $[F(a_{1}, \ldots, a_{n})]$ is PA-provable.

Hence, if Tr$_{PA} (f)$ holds then $[F(x_{1}, \ldots, x_{n})]$ interprets as instantiationally true under any sound interpretation of PA.

Now Gödel has also shown that there are arithmetical relations $R(y)$ and $S(y, u_{1}, \ldots, u_{n})$ such that:

(i) for any natural number $a$:

$a \hspace{+.5ex}B_{PA}\hspace{+.5ex}f \equiv R(a)$

(ii) for any natural number sequence $a, b_{1}, \ldots, b_{n}$:

$a \hspace{+.5ex}B\hspace{+.5ex} \{ Sb_{PA}(f \begin{array}{c} 17 \\ Z(b_{1}) \end{array} \ldots \begin{array}{c} p_{n+6} \\ Z(b_{n}) \end{array})\} \equiv \ S(a, b_{1}, \ldots, b_{n})$

Hence, contrary to the current interpretations of Tarski’s and Gödel’s formal reasoning, both PA-provability and PA-truth (under any sound interpretation of PA) are arithmetical’, in the sense that both can be defined unequivocally within the language of PA itself!

Although lying beyond the scope of the immediate issue addressed in this post, we shall show in a future post that the TRUE and PROVABLE formulas defined above are, in fact, the Algorithmically verifiable and Algorithmically computable formulas of PA respectively as defined in the paper Evidence-based Interpretations of PA‘ (presented at the Symposium on Computational Philosophy at the AISB/IACAP World Congress 2012-Alan Turing 2012, 2-6 July 2012, University of Birmingham, Birmingham, UK).

The argument of the paper is that the former define the standard non-finitary interpretation of PA (which does not yield a finitary proof of consistency for PA), whilst the latter define a sound finitary algorithmic interpretation of PA (which does establish the consistency of PA finitarily).

We further showed in this paper that, if the standard interpretation of PA is assumed to be sound, then PA is $\omega$-consistent, and so Aristotle’s particularisation must hold in the underlying logic.

Since Aristotle’s particularisation is a non-constructive postulation, the Gödelian argument against computationalism could be restated as asserting that whereas human intelligences can para-consistently’ derive consequences from a first-order logic that admits Aristotle’s particularisation, a machine intelligence cannot.

Another way of stating this is that the standard interpretation of PA characterises the way in which human intelligences reason, whereas the algorithmic interpretation of PA characterises the way in which mechanical intelligences reason, and that the two are not identical.

References

BBJ03 George S. Boolos, John P. Burgess, Richard C. Jeffrey. 2003. Computability and Logic. (4th ed). Cambridge University Press, Cambridge.

EC89 Richard L. Epstein, Walter A. Carnielli. 1989. Computability: Computable Functions, Logic, and the Foundations of Mathematics. Wadsworth & Brooks, California.

Go31 Kurt Gödel. 1931. On formally undecidable propositions of Principia Mathematica and related systems I. Translated by Elliott Mendelson. In M. Davis (ed.). 1965. The Undecidable. Raven Press, New York. pp.5-38.

Lu61 John Randolph Lucas. 1961. Minds, Machines and Gödel. In Philosophy. Vol. 36, No. 137 (Apr. – Jul., 1961), pp. 112-127, Cambridge University Press.

Lu03 John Randolph Lucas. 2003. The Gödelian Argument: Turn Over the Page. In Etica & Politica / Ethics & Politics, 2003, 1.

Lu06 John Randolph Lucas. 2006. Reason and Reality. Edited by Charles Tandy. Ria University Press, Palo Alto, California.

Me64 Elliott Mendelson. 1964. Introduction to Mathematical Logic. Van Norstrand. pp.145-146.

Pe90 Roger Penrose. 1990. The Emperor’s New Mind: Concerning Computers, Minds and the Laws of Physics. 1990, Vintage edition. Oxford University Press.

Pe94 Roger Penrose. 1994. Shadows of the Mind: A Search for the Missing Science of Consciousness. Oxford University Press.

Sc67 Joseph R. Schoenfield. 1967. Mathematical Logic. Reprinted 2001. A. K. Peters Ltd., Massachusetts.

Ta33 Alfred Tarski. 1933. The concept of truth in the languages of the deductive sciences. In Logic, Semantics, Metamathematics, papers from 1923 to 1938. (p152-278). ed. John Corcoran. 1983. Hackett Publishing Company, Indianapolis.

Wa63 Hao Wang. 1963. A survey of Mathematical Logic. North Holland Publishing Company, Amsterdam.

An07a Bhupinder Singh Anand. 2007. The Mechanist’s challenge. In The Reasoner, Vol(1)5 p5-6.

An12 … 2012. Evidence-Based Interpretations of PA. In Proceedings of the Symposium on Computational Philosophy at the AISB/IACAP World Congress 2012-Alan Turing 2012, 2-6 July 2012, University of Birmingham, Birmingham, UK.

Notes

Return to 1: See for instance: PSYCHE, 1996, 2(23); Journal of Experimental and Theoretical Artificial Intelligence, 2000, 12: 307-329; Behavioral and Brain Sciences, 1993, 16, 611-612).

Return to 5: For purposes of this investigation we take Mendelson’s exposition (in Me64, pp.49-53) of Tarski’s definitions (cf. Ta36) as definitive.

Return to 8: We highlight in An12 the far reaching consequences of the failure to insist upon unequivocal decidability for the satisfaction and truth of the formulas of PA under an interpretation.

The Gödelian argument afresh!

In a talk given on 25/5/96 at a BSPS conference in Oxford, J. R. Lucas [1] articulated his original Gödelian argument [2] afresh as follows:

“The Mechanist claims to have a model of the mind. We take the Mechanist seriously only if he will warrant that his purported model of the mind is consistent. In that case it passes the First Public Examination, but comes down at the Second, because knowing that it is consistent, we know that its Gödelian formula is true, which it cannot itself produce as true.

More succinctly, we can, if a Mechanist presents us with a system that he claims is a model of the mind, ask him simply whether or not it can prove its Gödelian formula (according to some system of Gödel numbering).

If he says it can, we know that it is inconsistent, and would be equally able to prove that 2 and 2 make 5, or that 0=1, and we waste little time on examining it.

If, however, he acknowledges that the system cannot prove its Gödelian formula, then we know it is consistent, since it cannot prove every well-formed formula, and knowing that it is consistent, know also that its Gödelian formula is true.

In this formulation we have, essentially, a dialogue between the Mechanist and the Mentalist, as we may call him, with the Mechanist claiming to be able to produce a mechanist model of the Mentalist’s mind, and the Mentalist being able to refute each particular instance offered.”

Do we really hope to get away with this argument?

Actually, if we were to ask Lucas’ hypothetical Mechanist whether, or not, his model can prove its Gödelian formula, he would, most likely, retort:

Before I commit my resources to something that may be impossible, can you assure me that it is provable?’

Of course we cannot, since we, too, cannot give a finitary proof of the formula that we are asking of the Mechanist’s finitary model.

If we, nevertheless, attempt to assert our superiority over the Mechanist by claiming, somewhat superciliously, that we do know, however, that the formula in question is true, but that it is one which the Mechanist’s model “cannot itself produce as true”, we would cut an even sorrier figure.

A prompt—seemingly astonished but subtly cunning—reply could be:

Whatever gave you that idea! My model can even prove that it’s true.’

The Mechanist’s Challenge

If, unwittingly, we were to express incredulity, we would face the humiliating challenge:

`The Gödelian formula—which Gödel [3] refers to by its Gödel number—$17Gen r$, is of the form $[(\forall x)R(x)]$.

Neither of us can prove it from the agreed set of premises by the specified rules of inference of the Arithmetic in question [4].

However, for a large enough numeral $[n]$, my model can always produce a proof sequence for $[R(1) \& R(2) \& \ldots \& R(n)]$ from the premises faster than you.’

The reason we would have to sheepishly concede defeat, without even addressing the challenge, is that Gödel has constructed [5] a primitive recursive relation, $xBy$, which ensures that the Mechanist can show that the Gödelian sentence is true, in the Tarskian sense, by providing a Turing machine that can “compute” $[R(n)]$ as TRUE for any given numeral $[n]$ [6] as input.

Specifically, Gödel defines $xBy$ (primitive) recursively [7]—over the structure $\mathbb{N}$ of the natural numbers—so that it holds for natural numbers $x, y$, if, and only if, $x$ is the Gödel number of a proof sequence—in any Arithmetic of the natural numbers—for the formula of the Arithmetic whose Gödel number is $y$.

Since our definition of the truth of a formula under an interpretation in $\mathbb{N}$ is also based on Tarski’s specification that it hold exhaustively, i.e., every instantiation of it must hold in the interpretation, our argument for our intellectual superiority over the Mechanist’s model fails miserably in this particular instance.

End of story?

Not quite.

There’s more

We could perhaps try to find solace—and console ourselves—with the thought that our brains are not designed ideally to tackle problems that can only be tackled by brute force; but they are, surely, superior to the Mechanist’s model when it comes to proofs that require ingenuity.

However, we will, then, face even greater discomfiture.

Gödel has given [8] another primitive recursive predicate, $Bw(x)$, that the Mechanist can program on a UTM to—given sufficient time—create a set of theorems that will contain, and continue to be larger than, the set of all the arithmetical theorems that we have ever proven—and verified—collectively using only pencil, paper, and our “superior” intellects!

Gödel [9] defines $Bw(x)$ (primitive) recursively so that it holds for any natural number $x$ if, and only if, $x$ is the Gödel number of a proof sequence in the Arithmetic.

Moreover, the set would contain theorems that we could not even conceptualise, since we would be unable to grasp even the statement, leave alone the proof, of these theorems!

So, what is really wrong with the Gödelian argument?

Well, ironically—and perhaps paradoxically—it’s simply another instance of human insecurity applying very common, and very human, double standards!

Namely, matching our selective interpretation of Tarski’s ambiguously defined concept of intuitive truth (we highlight this ambiguity here[10]) against the Mechanist’s unambiguously defined concept of provability to subtly load the dice in our favour semantically when faced with formal arguments that threaten to expose the continuing reluctance of the human ego to come to terms adequately with, and tap constructively into, the awesome conceptual power, diversity, and potential of any Intelligence, human or otherwise.

References

Go31 Kurt Gödel. 1931. On formally undecidable propositions of Principia Mathematica and related systems I. Translated by Elliott Mendelson. In M. Davis (ed.). 1965. The Undecidable. Raven Press, New York. pp.5-38.

Lu61 J. R. Lucas. 1961. Minds, Machines and Gödel. Philosophy, XXXVI, 1961, pp.112-127; reprinted in The Modeling of Mind. Kenneth M. Sayre and Frederick J. Crosson, eds., Notre Dame Press, 1963, pp.269-270; and Minds and Machines, ed. Alan Ross Anderson, Prentice-Hall, 1954, pp.43-59.

Lu03 John R. Lucas. 2003. The Gödelian Argument: Turn Over the Page. In Etica & Politica / Ethics & Politics, 2003, 1.

An07 Bhupinder Singh Anand. 2007. The Mechanist’s challenge. in The Reasoner, Vol(1)5 p5-6.

An12 Bhupinder Singh Anand. 2012. Evidence-Based Interpretations of PA. In Proceedings of the Symposium on Computational Philosophy at the AISB/IACAP World Congress 2012-Alan Turing 2012, 2-6 July 2012, University of Birmingham, Birmingham, UK.

Notes

Return to 4: ibid., p.25(1), “$17Gen r$ is not $\kappa$-provable”.

### Start here

Join 84 other followers

LobeLog

Critical Perspectives on U.S. Foreign Policy

What's new

Updates on my research and expository papers, discussion of open problems, and other maths-related topics. By Terence Tao

Quanta Magazine

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

The Brains Blog

Since 2005, a leading forum for work in the philosophy and science of mind

Logic Matters

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

A Neighborhood of Infinity

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

Combinatorics and more

Gil Kalai's blog

Mathematics and Computation

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

Foundations of Mathematics, Logic & Computability

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

John D. Cook

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

Shtetl-Optimized

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

Nanoexplanations

the blog of Aaron Sterling

Eric Cavalcanti

Quantum physicist

East Asia Forum

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

Tanya Khovanova's Math Blog

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

The polymath blog

Massively collaborative mathematical projects

Gowers's Weblog

Mathematics related discussions