You are currently browsing the tag archive for the ‘Mendelson’ 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 -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 -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 -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 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 , in a first-order theory (see Mendelson 1964, p.74, I(iv)); ‘invalidly’ since Rule C does not qualify that must be algorithmically computable from the alphabet of —which is necessary if 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 , that is to be viewed syntactically merely as a first-order string of —i.e, one which is finitarily constructed from the alphabet of the language of —without any reference to its meaning under any interpretation of .

Essentially, Rule C mirrors in the intuitionistically objectionable postulation that the formula of can always be interpreted as:

holds for some element

in the domain of the interpretation of under which the formula interprets as the relation .

*The Epsilon 2015 paper* shows that this is not a valid interpretation of the formula under any finitary, evidence-based, interpretation of .

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

**Provability Theorem for PA**: A PA formula is provable if, and only if, interprets as an arithmetical relation that is algorithmically computable as always true (see Definition 3, p.7, of *the Epsilon 2015 paper*) over the structure 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 —which Gödel refers to by its Gödel number —which is not provable in PA, even though 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 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 -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 -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 -incompleteness of PA is a verifiable logical meta-theorem that none of them would dispute.

**D: Isn’t Gödel’s undecidable formula —which Gödel refers to by its Gödel number —self-referential?**

*Isn’t Gödel’s undecidable formula —which Gödel refers to by its Gödel number —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 -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 -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 is not an undecidable formula of PA. It is merely unprovable in PA.

3. Moreover, Gödel’s PA-formula is provable in PA, which is why the PA formula is not an undecidable formula of PA.

4. Gödel’s PA-formula 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 asserts its own unprovability in PA.

*Reason*: We have for Gödel’s primitive recursive relation that:

is true if, and only if, the PA formula is provable in PA.

However, in order to conclude that the PA formula asserts its own unprovability in PA, Gödel’s argument must further imply—which it does not—that:

is true (and so, by Gödel’s definition of , the PA formula is not provable in PA) if, and only if, the PA formula is provable in PA.

In other words, for the PA formula to assert its own unprovability in PA, Gödel must show—which his own argument shows is impossible, since the PA formula is not provable in PA—that:

The primitive recursive relation is algorithmically computable as always true if, and only if, the arithmetical relation is algorithmically computable as always true (where is the arithmetical interpretation of the PA formula over the structure of the natural numbers).

6. Hence, Gödel’s PA-formula is not covertly paradoxical.

7. **IF** Wittgenstein believed that the PA formula 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) ‘ is not -provable’ is a valid meta-theorem if PA is consistent, which means that:

‘If PA is consistent and we assume that the PA formula is provable in PA, then the PA formula must also be provable in PA; from which we may conclude that the PA formula is not provable in PA’

(ii) ‘ is not -provable’ is a valid meta-theorem ONLY if PA is -consistent, which means that:

‘If PA is -consistent and we assume that the PA formula is provable in PA, then the PA formula must also be provable in PA; from which we may conclude that the PA formula is not provable in PA’.

8. In fact the PA formula has the following TWO meaningful interpretations (the first of which is a true arithmetical meta-statement—since the PA formula is provable in PA for any PA-numeral —but the second is not—since the PA formula is not provable in PA):

(i) For any given natural number , there is an algorithm which will verify that each of the arithmetical meta-statements ‘ is true’, ‘ is true’, …, ‘ is true’ holds under the standard, algorithmically verifiable, interpretation 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 , the arithmetical statement ‘ is true’ holds under the finitary, algorithmically computable, interpretation of PA (see \S 6, p.13 of *the Epsilon 2015 paper*).

9. **IF** Wittgenstein believed that the PA formula is not a well-defined PA formula, then he was wrong.

Gödel’s definition of the PA formula 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): is the Gödel-number of the formula of PA” and*

*“D(4): Gödel’s PA-formula is not self-referential.”*

*If ‘‘ is the Gödel-number of the open formula in para (iv), and the second argument of the closed formula in para D(4) is ‘‘, then the second formula is obtained by instantiating the variable ‘‘ 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., , is the Gödel-number of the PA formula , and not that of “the entire formula (in 4)”, i.e., of the formula itself (whose Gödel number is ).

Putting it crudely, is neither self-referential—nor circularly defined—because it is not defined in terms of , but in terms of .

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

I would interpret:

Gödel’s PA-formula is self-referential

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

asserts its own unprovability in PA.

Now, if we were to accept the claim that 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:

is true—and so, by Gödel’s definition of —the PA formula is not provable in PA—if, and only if, the PA formula 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 is algorithmically computable as always true if, and only if, the arithmetical interpretation of the PA formula is algorithmically computable as always true over the structure 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 of the PA formula is algorithmically verifiable as always true over the structure of the natural numbers.

Ergo—contrary to Gödel’s claim— Gödel’s PA-formula 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 -inconsistent without remedy?**

*Is the PA system -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 , we cannot have that both and 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 is an interpretation of PA over a structure , and is an interpretation of PA over a structure , then and are identical and denote the structure 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 -consistent (Corollary 8.4, p.16, of *the Epsilon 2015 paper*);

(ii) The Gödel formula 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 of PA (see Section 5, p.11, of *the Epsilon 2015 paper*) over the structure of the natural numbers;

(iii) The Gödel formula 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 of PA (see Section 6, p.13, of *the Epsilon 2015 paper*) over the structure of the natural numbers;

(iv) The Gödel formula is provable in PA; and it is therefore also algorithmically verifiable as true under the algorithmically verifiable standard interpretation of PA over the structure 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 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 of PA over the structure 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 “-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”?

(*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 be understood from a broadly computational perspective”;

(iii) “ 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”.

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.

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**

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 is algorithmically computable if, and only if, there is an algorithm that can provide objective evidence (cf. ibid Murthy 91) for deciding the truth/falsity of each proposition in the denumerable sequence .

(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 is algorithmically verifiable if, and only if, for any given natural number , there is an algorithm which can provide objective evidence for deciding the truth/falsity of each proposition in the finite sequence .

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:

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

**A foundational argument for defining Effective Computability formally, and weakening the Church and Turing Theses – II**

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

** The Logical Issue**

In the previous posts we addressed first the computational issue, and second the philosophical issue—concerning the informal concept of `effective computability’—that seemed implicit in Selmer Bringsjord’s narrational case against Church’s Thesis ^{[1]}.

We now address the logical issue that leads to a formal definability of this concept which—arguably—captures our intuitive notion of the concept more fully.

We note that in this paper on undecidable arithmetical propositions we have shown how it follows from Theorem VII of Gödel’s seminal 1931 paper that every recursive function is representable in the first-order Peano Arithmetic PA by a formula which is algorithmically verifiable, but not algorithmically computable, *if* we assume (*Aristotle’s particularisation*) that the negation of a universally quantified formula of the first-order predicate calculus is always indicative of the existence of a counter-example under the standard interpretation of PA.

In this earlier post on the Birmingham paper, we have also shown that:

(i) The concept of algorithmic verifiability is well-defined under the standard interpretation of PA over the structure of the natural numbers; and

(ii) The concept of algorithmic computability too is well-defined under the algorithmic interpretation of PA over the structure of the natural numbers; and

We shall argue in this post that the standard postulation of the Church-Turing Thesis—which postulates that the intuitive concept of `effective computability’ is completely captured by the formal notion of `algorithmic computability’—does not hold if we formally define a number-theoretic formula as effectively computable if, and only if, it is algorithmically verifiable; and it therefore needs to be replaced by a weaker postulation of the Thesis as an instantiational equivalence.

** Weakening the Church and Turing Theses**

We begin by noting that the following theses are classically equivalent ^{[1]}:

**Standard Church’s Thesis:** ^{[2]} A number-theoretic function (or relation, treated as a Boolean function) is effectively computable if, and only if, it is recursive ^{[3]}.

**Standard Turing’s Thesis:** ^{[4]} A number-theoretic function (or relation, treated as a Boolean function) is effectively computable if, and only if, it is Turing-computable ^{[5]}.

In this paper we shall argue that, from a foundational perspective, the principle of Occam’s razor suggests the Theses should be postulated minimally as the following equivalences:

**Weak Church’s Thesis:** A number-theoretic function (or relation, treated as a Boolean function) is effectively computable if, and only if, it is instantiationally equivalent to a recursive function (or relation, treated as a Boolean function).

**Weak Turing’s Thesis:** A number-theoretic function (or relation, treated as a Boolean function) is effectively computable if, and only if, it is instantiationally equivalent to a Turing-computable function (or relation, treated as a Boolean function).

** The need for explicitly distinguishing between `instantiational’ and `uniform’ methods**

**Why Church’s Thesis?**

It is significant that both Kurt Gödel (initially) and Alonzo Church (subsequently—possibly under the influence of Gödel’s disquietitude) enunciated Church’s formulation of `effective computability’ as a Thesis because Gödel was instinctively uncomfortable with accepting it as a definition that *minimally* captures the essence of `*intuitive* effective computability’ ^{[6]}.

**Kurt Gödel’s reservations**

Gödel’s reservations seem vindicated if we accept that a number-theoretic function can be effectively computable instantiationally (in the sense of being algorithmically *verifiable* as defined in the Birmingham paper, reproduced in this post), but not by a uniform method (in the sense of being algorithmically *computable* as defined in the Birmingham paper, reproduced in this post).

The significance of the fact (considered in the Birmingham paper, reproduced in this post) that `truth’ too can be effectively decidable *both* instantiationally *and* by a uniform method under the standard interpretation of PA is reflected in Gödel’s famous 1951 Gibbs lecture^{[7]}, where he remarks:

“I wish to point out that one may conjecture the truth of a universal proposition (for example, that I shall be able to verify a certain property for any integer given to me) and at the same time conjecture that no general proof for this fact exists. It is easy to imagine situations in which both these conjectures would be very well founded. For the first half of it, this would, for example, be the case if the proposition in question were some equation of two number-theoretical functions which could be verified up to very great numbers .” ^{[8]}

**Alan Turing’s perspective**

Such a possibility is also implicit in Turing’s remarks ^{[9]}:

“The computable numbers do not include all (in the ordinary sense) definable numbers. Let P be a sequence whose *n*-th figure is 1 or 0 according as *n* is or is not satisfactory. It is an immediate consequence of the theorem of that P is not computable. It is (so far as we know at present) possible that any assigned number of figures of P can be calculated, but not by a uniform process. When sufficiently many figures of P have been calculated, an essentially new method is necessary in order to obtain more figures.”

**Boolos, Burgess and Jeffrey’s query**

The need for placing such a distinction on a formal basis has also been expressed explicitly on occasion ^{[10]}.

Thus, Boolos, Burgess and Jeffrey ^{[11]} define a diagonal *halting function*, , any value of which can be decided effectively, although there is no single algorithm that can effectively compute .

Now, the straightforward way of expressing this phenomenon should be to say that there are well-defined number-theoretic functions that are effectively computable instantiationally but not uniformly. Yet, following Church and Turing, such functions are labeled as uncomputable ^{[12]}!

However, as Boolos, Burgess and Jeffrey note quizically:

“According to Turing’s Thesis, since is not Turing-computable, cannot be effectively computable. Why not? After all, although no Turing machine computes the function , we were able to compute at least its first few values, For since, as we have noted, the empty function we have . And it may seem that we can actually compute for any positive integer —if we don’t run out of time.” ^{[13]}

**Why should Chaitin’s constant be labelled `uncomputable’?**

The reluctance to treat a function such as —or the function that computes the digit in the decimal expression of a Chaitin constant ^{[14]}—as computable, on the grounds that the `time’ needed to compute it increases monotonically with , is curious ^{[15]}; the same applies to any total Turing-computable function !^{[16]}

Moreover, such a reluctance to treat instantiationally computable functions such as as not `effectively computable’ is difficult to reconcile with a conventional wisdom that holds the standard interpretation of the first order Peano Arithmetic PA as defining an intuitively sound model of PA.

*Reason:* We have shown in the Birmingham paper (reproduced in this post) that ‘satisfaction’ and ‘truth’ under the standard interpretation of PA is definable constructively in terms of algorithmic verifiability (*instantiational computability*).

** Distinguishing between algorithmic verifiability and algorithmic computability**

We now show in Theorem 1 that if Aristotle’s particularisation is presumed valid over the structure of the natural numbers—as is the case under the standard interpretation of the first-order Peano Arithmetic PA—then it follows from the instantiational nature of the (constructively defined ^{[17]}) Gödel -function that a primitive recursive relation can be instantiationally equivalent to an arithmetical relation, where the former is algorithmically computable over , whilst the latter is algorithmically verifiable (i.e., instantiationally computable) but not algorithmically computable over .^{[18]}

** Significance of Gödel’s -function**

We note first that in Theorem VII of his seminal 1931 paper on formally undecidable arithmetical propositions Gödel showed that, given a total number-theoretic function and any natural number , we can construct a primitive recursive function and natural numbers such that for all .

In this paper we shall essentially answer the following question affirmatively:

**Query 3:** Does Gödel’s Theorem VII admit construction of an arithmetical function such that:

(a) for any given natural number , there is an algorithm that can verify for all (hence may be said to be algorithmically verifiable if is recursive);

(b) there is no algorithm that can verify for all (so may be said to be algorithmically uncomputable)?

** Defining effective computability**

Now, in the Birmingham paper (reproduced in this post), we have formally defined what it means for a formula of an arithmetical language to be:

(i) Algorithmically verifiable;

(ii) Algorithmically computable.

under an interpretation.

We shall thus propose the definition:

**Effective computability:** A number-theoretic formula is effectively computable if, and only if, it is algorithmically verifiable.

**Intuitionistically unobjectionable:** We note first that since every finite set of integers is recursive, every well-defined number-theoretical formula is algorithmically verifiable, and so the above definition is intuitionistically unobjectionable; and second that the existence of an arithmetic formula that is algorithmically verifiable but not algorithmically computable (Theorem 1) supports Gödel’s reservations on Alonzo Church’s original intention to label his Thesis as a definition ^{[19]}.

The concept is well-defined, since we have shown in the Birmingham paper (reproduced in this post) that the algorithmically verifiable and the algorithmically computable PA formulas are well-defined under the standard interpretation of PA and that:

(a) The PA-formulas are decidable as satisfied / unsatisfied or true / false under the standard interpretation of PA if, and only if, they are algorithmically verifiable;

(b) The algorithmically computable PA-formulas are a proper subset of the algorithmically verifiable PA-formulas;

(c) The PA-axioms are algorithmically computable as satisfied / true under the standard interpretation of PA;

(d) Generalisation and Modus Ponens preserve algorithmically computable truth under the standard interpretation of PA;

(e) The provable PA-formulas are precisely the ones that are algorithmically computable as satisfied / true under the standard interpretation of PA.

** Gödel’s Theorem VII and algorithmically verifiable, but not algorithmically computable, arithmetical propositions**

In his seminal 1931 paper on formally undecidable arithmetical propositions, Gödel defined a curious primitive recursive function—Gödel’s -function—as ^{[20]}:

**Definition 1:**

where denotes the remainder obtained on dividing by .

Gödel showed that the above function has the remarkable property that:

**Lemma 1:** For any given denumerable sequence of natural numbers, say , and any given natural number , we can construct natural numbers such that:

(i) ;

(ii) !;

(iii) for .

**Proof:** This is a standard result ^{[21]}.

Now we have the standard definition ^{[22]}:

**Definition 2:** A number-theoretic function is said to be representable in PA if, and only if, there is a PA formula with the free variables , such that, for any given natural numbers :

(i) if then PA proves: ;

(ii) PA proves: .

The function is said to be strongly representable in PA if we further have that:

(iii) PA proves:

**Interpretation of `‘:** The symbol `‘ denotes `uniqueness’ under an interpretation which assumes that Aristotle’s particularisation holds in the domain of the interpretation.

Formally, however, the PA formula:

is merely a short-hand notation for the PA formula:

.

We then have:

**Lemma 2** is strongly represented in PA by , which is defined as follows:

.

**Proof:** This is a standard result ^{[23]}.

Gödel further showed (also under the tacit, but critical, presumption of Aristotle’s particularisation ^{[24]} that:

**Lemma 3:** If is a recursive function defined by:

(i)

(ii)

where and are recursive functions of lower rank ^{[25]} that are represented in PA by well-formed formulas and ,

then is represented in PA by the following well-formed formula, denoted by :

**Proof:** This is a standard result ^{[26]}.

** What does “ is provable” assert under the standard interpretation of PA?**

Now, if the PA formula represents in PA the recursive function denoted by then by definition, for any given numerals , the formula is provable in PA; and true under the standard interpretation of PA.

We thus have that:

**Lemma 4:** “ is true under the standard interpretation of PA” is the assertion that:

Given any natural numbers , we can construct natural numbers —all functions of —such that:

(a) ;

(b) for all , ;

(c) ;

where , and are any recursive functions that are formally represented in PA by and respectively such that:

(i)

(ii) for all

(iii) and are recursive functions that are assumed to be of lower rank than .

**Proof:** For any given natural numbers and , if interprets as a well-defined arithmetical relation under the standard interpretation of PA, then we can define a deterministic Turing machine that can `construct’ the sequences:

and:

and give evidence to verify the assertion. ^{[27]}

We now see that:

**Theorem 1:** Under the standard interpretation of PA is algorithmically verifiable, but not algorithmically computable, as always true over .

**Proof:** It follows from Lemma 4 that:

(1) is PA-provable for any given numerals . Hence is true under the standard interpretation of PA. It then follows from the definition of in Lemma 3 that, for any given natural numbers , we can construct some pair of natural numbers —where are functions of the given natural numbers and —such that:

(a) for ;

(b) holds in .

Since is primitive recursive, defines a deterministic Turing machine that can `construct’ the denumerable sequence for any given natural numbers and such that:

(c) for .

We can thus define a deterministic Turing machine that will give evidence that the PA formula is true under the standard interpretation of PA.

Hence is algorithmically verifiable over under the standard interpretation of PA.

(2) Now, the pair of natural numbers are defined such that:

(a) for ;

(b) holds in ;

where is defined in Lemma 3 as !, and:

(c) ;

(d) is the `number’ of terms in the sequence .

Since is not definable for a denumerable sequence we cannot define a denumerable sequence such that:

(e) for all .

We cannot thus define a deterministic Turing machine that will give evidence that the PA formula interprets as true under the standard interpretation of PA for any given sequence of numerals .

Hence is not algorithmically computable over under the standard interpretation of PA.

The theorem follows.

**Corollary 1:** If the standard interpretation of PA is sound, then the classical Church and Turing theses are false.

The above theorem now suggests the following definition:

**Definition 2:** (*Effective computability*) A number-theoretic function is effectively computable if, and only if, it is algorithmically verifiable.

Such a definition of effective computability now allows the classical Church and Turing theses to be expressed as the weak equivalences in —rather than as identities—without any apparent loss of generality.

**References**

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

** Bri93** Selmer Bringsjord. 1993. *The Narrational Case Against Church’s Thesis.* Easter APA meetings, Atlanta.

**Ch36** Alonzo Church. 1936. *An unsolvable problem of elementary number theory.* In M. Davis (ed.). 1965. *The Undecidable* Raven Press, New York. Reprinted from the Am. J. Math., Vol. 58, pp.345-363.

**Ct75** Gregory J. Chaitin. 1975. *A Theory of Program Size Formally Identical to Information Theory.* J. Assoc. Comput. Mach. 22 (1975), pp. 329-340.

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

**Go51** Kurt Gödel. 1951. *Some basic theorems on the foundations of mathematics and their implications.* Gibbs lecture. In Kurt Gödel, Collected Works III, pp.304-323.\ 1995. *Unpublished Essays and Lectures.* Solomon Feferman et al (ed.). Oxford University Press, New York.

**Ka59** Laszlo Kalmár. 1959. *An Argument Against the Plausibility of Church’s Thesis.* In Heyting, A. (ed.) *Constructivity in Mathematics.* North-Holland, Amsterdam.

**Kl36** Stephen Cole Kleene. 1936. *General Recursive Functions of Natural Numbers.* Math. Annalen vol. 112 (1936) pp.727-766.

**Me64** Elliott Mendelson. 1964. *Introduction to Mathematical Logic.* Van Norstrand, Princeton.

**Me90** Elliott Mendelson. 1990. *Second Thoughts About Church’s Thesis and Mathematical Proofs.* Journal of Philosophy 87.5.

**Pa71** Rohit Parikh. 1971. *Existence and Feasibility in Arithmetic.* The Journal of Symbolic Logic, Vol.36, No. 3 (Sep., 1971), pp. 494-508.

**Si97** Wilfried Sieg. 1997. *Step by recursive step: Church’s analysis of effective calculability* Bulletin of Symbolic Logic, Volume 3, Number 2.

**Sm07** Peter Smith. 2007. *Church’s Thesis after 70 Years.* A commentary and critical review of *Church’s Thesis After 70 Years.* In Meinong Studies Vol 1 (Ontos Mathematical Logic 1), 2006 (2013), Eds. Adam Olszewski, Jan Wolenski, Robert Janusz. Ontos Verlag (Walter de Gruyter), Frankfurt, Germany.

**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-265; corrections, Ibid, vol 43 (1937) pp. 544-546.

**An07** Bhupinder Singh Anand. 2007. *Why we shouldn’t fault Lucas and Penrose for continuing to believe in the Gödelian argument against computationalism – II.* In *The Reasoner*, Vol(1)7 p2-3.

**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: cf. Me64, p.237.

Return to 2: *Church’s (original) Thesis:* The effectively computable number-theoretic functions are the algorithmically computable number-theoretic functions Ch36.

Return to 11: cf. Me64, p.227.

Return to 4: After describing what he meant by “computable” numbers in the opening sentence of his 1936 paper on Computable Numbers Tu36, Turing immediately expressed this thesis—albeit informally—as: “… the computable numbers include all numbers which could naturally be regarded as computable”.

Return to 5: cf. BBJ03, p.33.

Return to 6: See Si97.

Return to 7: Go51.

Return to 8: Parikh’s paper Pa71 can also be viewed as an attempt to investigate the consequences of expressing the essence of Gödel’s remarks formally.

Return to 9: Tu36, , p.139.

Return to 10: Parikh’s distinction between `decidability’ and `feasibility’ in Pa71 also appears to echo the need for such a distinction.

Return to 11: BBJ03, p. 37.

Return to 12: The issue here seems to be that, when using language to express the abstract objects of our individual, and common, mental `concept spaces’, we use the word `exists’ loosely in three senses, without making explicit distinctions between them (see An07).

Return to 13: BBJ03, p.37.

Return to 14: Chaitin’s Halting Probability is given by , where the summation is over all self-delimiting programs that halt, and is the size in bits of the halting program ; see Ct75.

Return to 15: The incongruity of this is addressed by Parikh in Pa71.

Return to 16: The only difference being that, in the latter case, we know there is a common `program’ of constant length that will compute for any given natural number ; in the former, we know we may need distinctly different programs for computing for different values of , where the length of the program will, sometime, reference .

Return to 17: By Kurt Gödel; see Go31, Theorem VII.

Return to 18: **Analagous distinctions in analysis:** The distinction between algorithmically computable, and algorithmically verifiable but not algorithmically computable, number-theoretic functions seeks to reflect in arithmetic the essence of *uniform* methods (formally detailed in the Birmingham paper (reproduced in this post) and in its main consequence—the Provability Theorem for PA—as detailed in this post), classically characterised by the distinctions in analysis between: (a) uniformly continuous, and point-wise continuous but not uniformly continuous, functions over an interval; (b) uniformly convergent, and point-wise convergent but not uniformly convergent, series.

**A limitation of set theory and a possible barrier to computation:** We note, further, that the above distinction cannot be reflected within a language—such as the set theory ZF—which identifies `equality’ with `equivalence’. Since functions are defined extensionally as mappings, such a language cannot recognise that a set which represents a primitive recursive function may be equivalent to, but computationally different from, a set that represents an arithmetical function; where the former function is algorithmically computable over , whilst the latter is algorithmically verifiable but not algorithmically computable over .

Return to 19: See the Provability Theorem for PA in this post.

Return to 20: cf. Go31, p.31, Lemma 1; Me64, p.131, Proposition 3.21.

Return to 21: cf. Go31, p.31, Lemma 1; Me64, p.131, Proposition 3.22.

Return to 22: Me64, p.118.

Return to 23: cf. Me64, p.131, proposition 3.21.

Return to 24: The implicit assumption being that the negation of a universally quantified formula of the first-order predicate calculus is indicative of “the existence of a counter-example”—Go31, p.32.

Return to 25: cf. Me64, p.132; Go31, p.30(2).

Return to 26: cf. Go31, p.31(2); Me64}, p.132.

Return to 27: A critical philosophical issue that we do not address here is whether the PA formula can be considered to interpret under a sound interpretation of PA as a well-defined predicate, since the denumerable sequences and is not equal to if is not equal to —are represented by denumerable, distinctly different, functions respectively. There are thus denumerable pairs for which yields the sequence .

**A foundational argument for defining Effective Computability formally, and weakening the Church and Turing Theses – I**

** The Philosophical Issue**

In a previous post we have argued that standard interpretations of classical theory may inadvertently be weakening a desirable perception—of mathematics as the lingua franca of scientific expression—by ignoring the possibility that since mathematics is, indeed, indisputably accepted as the language that most effectively expresses and communicates intuitive truth, the chasm between formal truth and provability must, of necessity, be bridgeable.

We further queried whether the roots of such interpretations may lie in removable ambiguities that currently persist in the classical definitions of foundational elements; ambiguities that allow the introduction of non-constructive—hence non-verifiable, non-computational, ambiguous and essentially Platonic—elements into the standard interpretations of classical mathematics.

**Query 1:** Are formal classical theories essentially unable to adequately express the extent and range of human cognition, or does the problem lie in the way formal theories are classically interpreted at the moment?

We noted that the former addressed the question of whether there are absolute limits on our capacity to express human cognition unambiguously; the latter, whether there are only temporal limits—not necessarily absolute—to the capacity of classical interpretations to communicate unambiguously that which we intended to capture within our formal expression.

We argued that, prima facie, applied science continues, perforce, to interpret mathematical concepts Platonically, whilst waiting for mathematics to provide suitable, and hopefully reliable, answers as to how best it may faithfully express its observations verifiably.

** Are axiomatic computational concepts really unambiguous?**

This now raises the corresponding philosophical question that is implicit in Selmer Bringsjord’s narrational case against Church’s Thesis ^{[1]}:

**Query 2** Is there a duality in the classical acceptance of non-constructive, foundational, concepts as axiomatic?

We now argue that beyond the question raised in an earlier post of whether—as computer scientist Lance Fortnow believes—Turing machines can `capture everything we can compute’, or whether—as computer scientists Peter Wegner and Dina Goldin suggest—they are `inappropriate as a universal foundation for computational problem solving’, we also need to address the philosophical question—implicit in Bringsjord’s paper—of whether, or not, the concept of `effective computability’ is capable of a constructive, and intuitionistically unobjectionable, definition; and the relation of such definition to that of formal provability and to the standard perceptions of the Church and Turing Theses as reviewed here by at heart Trinity mathmo and by profession Philosopher Peter Smith.

We therefore consider the case for introduction of such a definition from a philosophical point of view, and consider some consequences.

** Mendelson’s thesis**

We note that Elliott Mendelson ^{[2]} is quoted by Bringsjord in his paper as saying (*italicised parenthetical qualifications added*):

(i) “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)”.

(ii) “The concepts and assumptions that support the notion of partial-recursive function are, in an essential way, no less vague and imprecise (*non-constructive, and intuitionistically objectionable*) 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 (*not more non-constructive, and intuitionistically objectionable*) 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 (*not more non-constructive, and intuitionistically objectionable*), than that of truth.

The model-theoretic definition of logical validity is based ultimately on set theory, the foundations of which are no clearer (*not more non-constructive, and intuitionistically objectionable*) than our intuitive (*non-constructive, and intuitionistically objectionable*) understanding of logical validity”.

(iii) “The notion of Turing-computable function is no clearer (*not more non-constructive, and intuitionistically objectionable*) than, nor more mathematically useful (foundationally speaking) than, the notion of an effectively computable function …”

where:

(a) The Church-Turing Thesis, CT, is formulated as:

“A function is effectively computable if and only if it is Turing-computable”.

(b) An effectively computable function is defined to be the computing of the function by an algorithm.

(c) The classical notion of an algorithm is expressed by Mendelson as:

“… an effective and completely specified procedure for solving a whole class of problems. …

An algorithm does not require ingenuity; its application is prescribed in advance and does not depend upon any empirical or random factors”.

and, where Bringsjord paraphrases (iii) as:

(iv) “The notion of a formally defined program for guiding the operation of a TM is no clearer than, nor more mathematically useful (foundationally speaking) than, the notion of an algorithm”.

adding that:

(v) “This proposition, it would then seem, is the very heart of the matter.

If (iv) is true then Mendelson has made his case; if this proposition is false, then his case is doomed, since we can chain back by modus tollens and negate (iii)”.

** The concept of `constructive, and intuitionistically unobjectionable’**

Now, prima facie, any formalisation of a `vague and imprecise’, `intuitive’ concept—say C—would normally be intended to capture the concept C both faithfully and completely within a constructive, and intuitionistically unobjectionable ^{[3]}, language L.

Clearly, we could disprove the thesis—that C and its formalisation L are interchangeable, hence equivalent—by showing that there is a constructive aspect of C that is formalisable in a constructive language L’, but that such formalisation cannot be assumed expressible in L without introducing inconsistency.

However, equally clearly, there can be no way of proving the equivalence as this would contradict the premise that the concept is `vague and imprecise’, hence essentially open-ended in a non-definable way, and so non-formalisable.

Obviously, Mendelson’s assertion that there is no justification for claiming Church’s Thesis as unprovable must, therefore, rely on an interpretation that differs significantly from the above; for instance, his concept of provability may appeal to the axiomatic acceptability of `vague and imprecise’ concepts—as suggested by his remarks.

Now, we note that all the examples cited by Mendelson involve the decidability (computability) of an infinitude of meta-mathematical instances, where the distinction between the constructive meta-assertion that any given instance is individually decidable (instantiationally computable), and the non-constructive meta-assertion that all the instances are jointly decidable (uniformly computable), is not addressed explicitly.

However, , and appear to suggest that Mendelson’s remarks relate implicitly to non-constructive meta-assertions.

Perhaps the real issue, then, is the one that emerges if we replace Mendelson’s use of implicitly open-ended concepts such as `vague and imprecise’ and `intuitive’ by the more meta-mathematically meaningful concept of `non-constructive, and intuitionistically objectionable’, as italicised and indicated parenthetically.

The essence of Mendelson’s meta-assertion then appears to be that, if the classically accepted definitions of foundational concepts such as `partial recursive function’, `function’, `Tarskian truth’ etc. are also non-constructive, and intuitionistically objectionable, then replacing one non-constructive concept by another may be psychologically unappealing, but it should be meta-mathematically valid and acceptable.

** The duality**

Clearly, meta-assertion would stand refuted by a `non-algorithmic’ effective method that is constructive.

However, if it is explicitly—and, as suggested by the nature of the arguments in Bringsjord’s paper, widely—accepted at the outset that any effective method is necessarily algorithmic (i.e. uniform as stated in above), then any counter-argument to CT can, prima facie, only offer non-algorithmic methods that may, paradoxically, be `effective’ intuitively but in a non-constructive, and intuitionistically objectionable, way only!

Recognition of this dilemma is implicit in the admission that the various arguments, as presented by Bringsjord in the case against Church’s Thesis—including his narrational case—are open to reasonable, but inconclusive, refutations.

Nevertheless, if we accept Mendelson’s thesis that the inter-changeability of non-constructive concepts is valid in the foundations of mathematics, then Bringsjord’s case against Church’s Thesis, since it is based similarly on non-constructive concepts, should also be considered conclusive classically (even though it cannot, prima facie, be considered constructively conclusive in an intuitionistically unobjectionable way).

There is, thus, an apparent duality in the—seemingly extra-logical—decision as to whether an argument based on non-constructive concepts may be accepted as classically conclusive or not.

That this duality may originate in the very issues raised in Mendelson’s remarks—concerning the non-constructive roots of foundational concepts that are classically accepted as mathematically sound—is seen if we note that these issues may be more significant than is, prima facie, apparent.

** Definition of a formal mathematical object, and consequences**

Thus, if we define a formal mathematical object as any symbol for an individual letter, function letter or a predicate letter that can be introduced through definition into a formal theory without inviting inconsistency, then it can be argued that unrestricted, non-constructive, definitions of non-constructive, foundational, set-theoretic concepts—such as `mapping’, `function’, `recursively enumerable set’, etc.—in terms of constructive number-theoretic concepts—such as recursive number-theoretic functions and relations—may not always correspond to formal mathematical objects.

In other words, the assumption that every definition corresponds to a formal mathematical object may introduce a formal inconsistency into standard Peano Arithmetic and, ipso facto, into any Axiomatic Set Theory that models standard PA (an inconsistency which, loosely speaking, may be viewed as a constructive arithmetical parallel to Russell’s non-constructive impredicative set).

Since it can also be argued that the non-constructive element in Tarski’s definitions of `satisfiability’ and `truth’, and in Church’s Thesis, originate in a common, but removable, ambiguity in the interpretation of an effective method, perhaps it is worth considering whether Bringsjord’s acceptance of the assumption—that every constructive effective method is necessarily algorithmic, in the sense of being a uniform procedure as in above—is mathematically necessary, or even whether it is at all intuitively tenable.

(*Uniform procedure: A property usually taken to be a necessary condition for a procedure to qualify as effective.*)

Thus, we may argue that we can explicitly and constructively define a `non-algorithmic’ effective method as one that, in any given instance, is instantiationally computable if, and only if, it terminates finitely with a conclusive result; and an `algorithmic’ effective method as one that is uniformly computable if, and only if, it terminates finitely, with a conclusive result, in any given instance. ^{[4]}

** Bringsjord’s case against CT**

Apropos the specific arguments against CT it would seem, prima facie, that a non-algorithmic effective—even if not obviously constructive—method could be implicit in the following argument considered by Bringsjord:

“Assume for the sake of argument that all human cognition consists in the execution of effective processes (in brains, perhaps). It would then follow by CT that such processes are Turing-computable, i.e., that computationalism is true. However, if computationalism is false, while there remains incontrovertible evidence that human cognition consists in the execution of effective processes, CT is overthrown”.

Assuming computationalism is false, the issue in this argument would, then, be whether there is a constructive, and adequate, expression of human cognition in terms of individually effective methods.

An appeal to such a non-algorithmic effective method may, in fact, be implicit in Bringsjord’s consideration of the predicate H, defined by:

iff

where the predicate holds if, and only if, TM M, running program P on input , halts in exactly steps ( halt).

**Bringsjord’s Total Computability**

Bringsjord defines S as totally (*and, implicitly, uniformly*) computable in the sense that, given some triple , there is some (*uniform*) program P* which, running on some TM M*, can infallibly give us a verdict, Y (`yes’) or N (`no’), for whether or not S is true of this triple.

He then notes that, since the ability to (*uniformly*) determine, for a pair , whether or not H is true of it, is equivalent to solving the full halting problem, H is not totally computable.

**Bringsjord’s Partial Computability**

However, he also notes that there is a program (*implicitly non-uniform, and so, possibly, effective individually*) which, when asked whether or not some TM M run by P on halts, will produce Y iff halt. For this reason H is declared partially (*implicitly, individually*) computable.

More explicitly, Bringsjord remarks that Laszlo Kalmár’s refutation of CT ^{[5]} is classically inconclusive mainly because it does not admit any uniform effective method, but appeals to the existence of an infinitude of individually effective methods.

**Kalmár’s Perspective of CT**

Considering that it always seeks to calculate (defined below) constructively even in the absence of a uniform procedure—not necessarily within a fixed postulate system—we shall show that Kalmár’s finitary argument (^{[6]}as reproduced below from Bringsjord’s paper) makes a pertinent observation:

“First, he draws our attention to a function that isn’t Turing-computable, given that is ^{[7]}:

= {the least such that if exists; and if there is no such }

Kalmár proceeds to point out that for any in for which a natural number with exists,

`an obvious method for the calculation of the least such … can be given,’

namely, calculate in succession the values (which, by hypothesis, is something a computist or TM can do) until we hit a natural number such that , and set .

On the other hand, for any natural number for which we can prove, not in the frame of some fixed postulate system but by means of arbitrary—of course, correct—arguments that no natural number with exists, we have also a method to calculate the value in a finite number of steps.

Kalmár goes on to argue as follows. The definition of itself implies the tertium non datur, and from it and CT we can infer the existence of a natural number which is such that

(*) there is no natural number such that ; and

(**) this cannot be proved by any correct means.

Kalmár claims that (*) and (**) are very strange, and that therefore CT is at the very least implausible.”

**Distinguishing between individually effective computability and uniformly effective computability**

Now, the significant point that emerges from Bringsjord’s and Kalmár’s philosophical arguments is the need to distinguish formally between non-algorithmic (i.e., instantiational) computability (or, more precisely, algorithmic verifiability as defined here) and algorithmic (i.e., uniform) computability (or, more precisely, algorithmic computability as defined here) as highlighted in the Birmingham paper.

In the next post we note that this point has also been raised from a more formal, logical, perspective; and consider what is arguably an intuitively-more-adequate formal definability of `effective computability’ in terms of ‘algorithmic verifiability’ under which the classical Church and Turing Theses do not hold, but weakened Church and Turing Theses do!

**References**

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

** Bri93** Selmer Bringsjord. 1993. *The Narrational Case Against Church’s Thesis.* Easter APA meetings, Atlanta.

**Ch36** Alonzo Church. 1936. *An unsolvable problem of elementary number theory.* In M. Davis (ed.). 1965. *The Undecidable* Raven Press, New York. Reprinted from the Am. J. Math., Vol. 58, pp.345-363.

**Ct75** Gregory J. Chaitin. 1975. *A Theory of Program Size Formally Identical to Information Theory.* J. Assoc. Comput. Mach. 22 (1975), pp. 329-340.

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

**Go51** Kurt Gödel. 1951. *Some basic theorems on the foundations of mathematics and their implications.* Gibbs lecture. In Kurt Gödel, Collected Works III, pp.304-323.\ 1995. *Unpublished Essays and Lectures.* Solomon Feferman et al (ed.). Oxford University Press, New York.

**Ka59** Laszlo Kalmár. 1959. *An Argument Against the Plausibility of Church’s Thesis.* In Heyting, A. (ed.) *Constructivity in Mathematics.* North-Holland, Amsterdam.

**Kl36** Stephen Cole Kleene. 1936. *General Recursive Functions of Natural Numbers.* Math. Annalen vol. 112 (1936) pp.727-766.

**Me64** Elliott Mendelson. 1964. *Introduction to Mathematical Logic.* Van Norstrand, Princeton.

**Me90** Elliott Mendelson. 1990. *Second Thoughts About Church’s Thesis and Mathematical Proofs.* Journal of Philosophy 87.5.

**Pa71** Rohit Parikh. 1971. *Existence and Feasibility in Arithmetic.* The Journal of Symbolic Logic, Vol.36, No. 3 (Sep., 1971), pp. 494-508.

**Si97** Wilfried Sieg. 1997. *Step by recursive step: Church’s analysis of effective calculability* Bulletin of Symbolic Logic, Volume 3, Number 2.

**Sm07** Peter Smith. 2007. *Church’s Thesis after 70 Years.* A commentary and critical review of *Church’s Thesis After 70 Years.** In Meinong Studies Vol 1 (Ontos Mathematical Logic 1), 2006 (2013), Eds. Adam Olszewski, Jan Wolenski, Robert Janusz. Ontos Verlag (Walter de Gruyter), Frankfurt, Germany.*

**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-265; corrections, Ibid, vol 43 (1937) pp. 544-546.

**An07** Bhupinder Singh Anand. 2007. *Why we shouldn’t fault Lucas and Penrose for continuing to believe in the Gödelian argument against computationalism – II.* In *The Reasoner*, Vol(1)7 p2-3.

**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 2: Me90.

Return to 3: The terms `constructive’ and `constructive, and intuitionistically unobjectionable’ are used synonymously both in their familiar linguistic sense, and in a mathematically precise sense. Mathematically, we term a concept as `constructive, and intuitionistically unobjectionable’ if, and only if, it can be defined in terms of pre-existing concepts without inviting inconsistency. Otherwise, we understand it to mean unambiguously verifiable, by some `effective method’, within some finite, well-defined, language or meta-language. It may also be taken to correspond, broadly, to the concept of `constructive, and intuitionistically unobjectionable’ in the sense apparently intended by Gödel in his seminal 1931 paper Go31, p.26.

Return to 4: We note that the possibility of a distinction between the interpreted number-theoretic meta-assertions, `For any given natural number , is true’ and ` is true for all natural numbers ‘, is not evident unless these are expressed symbolically as, ` is true)’ and ` is true’, respectively. The issue, then, is whether the distinction can be given any mathematical significance. For instance, under a constructive formulation of Tarski’s definitions, we may qualify the latter by saying that it can be meaningfully asserted as a totality only if `‘ is a well-defined mathematical object.

Return to 5: Ka59.

Return to 6: Ka59.

Return to 7: Bringsjord notes that the original proof can be found on page 741 of Kleene Kl36.

Return to 8: We detail a formal proof of this Thesis in this post.

*
***So where exactly does the buck stop?**

Another reason why Lucas and Penrose should not be faulted for continuing to believe in their well-known Gödelian arguments against computationalism lies in the lack of an adequate consensus on the concept of `effective computability’.

For instance, Boolos, Burgess and Jeffrey (2003: Computability and Logic, 4th ed.~CUP, p37) define a diagonal *halting* function, , any value of which can be computed effectively, although there is no single algorithm that can effectively compute .

“According to Turing’s Thesis, since is not Turing-computable, cannot be effectively computable. Why not? After all, although no Turing machine computes the function , we were able to compute at least its first few values, For since, as we have noted, the empty function we have . And it may seem that we can actually compute for any positive integer —if we don’t run out of time.”

… ibid. 2003. p37.

Now, the straightforward way of expressing this phenomenon should be to say that there are well-defined real numbers that are instantiationally computable, but not algorithmically computable.

Yet, following Church and Turing, such functions are labeled as effectively uncomputable!

The issue here seems to be that, when using language to express the abstract objects of our individual, and common, mental `concept spaces’, we use the word `exists’ loosely in three senses, without making explicit distinctions between them.

First, we may mean that an individually conceivable object exists, within a language , if it lies within the range of the variables of . The existence of such objects is necessarily derived from the grammar, and rules of construction, of the appropriate constant terms of the language—generally finitary in recursively defined languages—and can be termed as constructive in by definition.

Second, we may mean that an individually conceivable object exists, under a formal interpretation of in another formal language, say **′**, if it lies within the range of a variable of under the interpretation.

Again, the existence of such an object in **′** is necessarily derivable from the grammar, and rules of construction, of the appropriate constant terms of **′**, and can be termed as constructive in **′** by definition.

Third, we may mean that an individually conceivable object exists, in an interpretation of , if it lies within the range of an interpreted variable of , where is a Platonic interpretation of in an individual’s subjective mental conception (in Brouwer’s sense).

Clearly, the debatable issue is the third case.

So the question is whether we can—and, if so, how we may—correspond the Platonically conceivable objects of various individual interpretations of , say , **′**, **′****′**, …, unambiguously to the mathematical objects that are definable as the constant terms of .

If we can achieve this, we can then attempt to relate to a common external world and try to communicate effectively about our individual mental concepts of the world that we accept as lying, by consensus, in a common, Platonic, `concept-space’.

For mathematical languages, such a common `concept-space’ is implicitly accepted as the collection of individual intuitive, Platonically conceivable, perceptions—, **′**, **′****′**, …,—of the standard intuitive interpretation, say , of Dedekind’s axiomatic formulation of the Peano Postulates.

Reasonably, if we intend a language or a set of languages to be adequate, first, for the expression of the abstract concepts of collective individual consciousnesses, and, second, for the unambiguous and effective communication of those of such concepts that we can accept as lying within our common concept-space, then we need to give effective guidelines for determining the Platonically conceivable mathematical objects of an individual perception of that we can agree upon, by common consensus, as corresponding to the constants (mathematical objects) definable within the language.

Now, in the case of mathematical languages in standard expositions of classical theory, this role is sought to be filled by the Church-Turing Thesis (CT). Its standard formulation postulates that every number-theoretic function (or relation, treated as a Boolean function) of , which can intuitively be termed as effectively computable, is partial recursive / Turing-computable.

However, CT does not succeed in its objective completely.

Thus, even if we accept CT, we still cannot conclude that we have specified explicitly that the domain of consists of only constructive mathematical objects that can be represented in the most basic of our formal mathematical languages, namely, first-order Peano Arithmetic (PA) and Recursive Arithmetic (RA).

The reason seems to be that CT is postulated as a strong identity, which, prima facie, goes beyond the minimum requirements for the correspondence between the Platonically conceivable mathematical objects of and those of PA and RA.

“We now define the notion, already discussed, of an effectively calculable function of positive integers by identifying it with the notion of a recursive function of positive integers.”

… Church 1936: An unsolvable problem of elementary number theory, Am.~J.~Math., Vol.~58, pp.~345–363.

“The theorem that all effectively calculable sequences are computable and its converse are proved below in outline.

… Turing 1936: On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, ser.~2.~vol.~42 (1936–7), pp.~230–265.

This violation of the principle of Occam’s Razor is highlighted if we note (e.g., Gödel 1931: On undecidable propositions of Principia Mathematica and related systems I, Theorem VII) that, pedantically, every recursive function (or relation) is not shown as identical to a unique arithmetical function (or relation), but (*see the comment following Lemma 9 of this paper*) only as instantiationally equivalent to an infinity of arithmetical functions (or relations).

Now, the standard form of CT only postulates algorithmically computable number-theoretic functions of as effectively computable.

It overlooks the possibility that there may be number-theoretic functions and relations which are effectively computable / decidable instantiationally in a Tarskian sense, but not algorithmically.

**References**

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

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

**An07b** … 2007. *Why we shouldn’t fault Lucas and Penrose for continuing to believe in the Gödelian argument against computationalism – I.* In *The Reasoner,* Vol(1)6 p3-4.

**An07c** … 2007. *Why we shouldn’t fault Lucas and Penrose for continuing to believe in the Gödelian argument against computationalism – II.* In *The Reasoner*, Vol(1)7 p2-3.

**An08** … 2008. *Can we really falsify truth by dictat?.* In *The Reasoner*, Vol(2)1 p7-8.

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

**A finitary arithmetical perspective on the forcing of non-standard models onto PA**

In the previous post we formally argued that the first order Peano Arithmetic PA is categorical from a finitary perspective (, Corollary 1).

We now argue that conventional wisdom which holds PA as essentially incomplete—and thus precludes categoricity—may appeal to finitarily fragile arguments (*as mentioned in this earlier post and in this preprint, now reproduced below*) for the existence of non-standard models of the first-order Peano Arithmetic PA.

Such wisdom ought, therefore, to be treated foundationally as equally fragile from a post-computationalist arithmetical perspective within classical logic, rather than accepted as foundationally sound relative to an ante-computationalist perspective of set theory.

**Post-computationalist doctrine**

“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 …” (cf. Mu91).

** Introduction**

Once we accept as logically sound the set-theoretically based meta-argument ^{[1]} that the first-order Peano Arithmetic PA ^{[2]} can be forced—by an ante-computat- ionalist interpretation of the Compactness Theorem—into admitting non-standard models which contain an `infinite’ integer, then the set-theoretical properties ^{[3]} of the algebraic and arithmetical structures of such putative models should perhaps follow without serious foundational reservation.

**Compactness Theorem:** If every finite subset of a set of sentences has a model, then the whole set has a model (BBJ03. p.147).

However we shall argue that, from an arithmetical perspective, we can only conclude by the Compactness Theorem that if is the -theory of the standard model (interpretation) (Ka91, p.10-11), then we may consistently add to it the following as an additional—not necessarily independent—axiom:

.

Moreover, we shall argue that even though is algorithmically computable (Definition 2) as always true in the standard model (whence all of its instances are in ) we cannot conclude by the Compactness Theorem that:

is consistent and has a model which contains an `infinite’ integer ^{[4]}.

*Reason:* We shall argue that the condition in the above definition of requires, first of all, that we must be able to extend by the addition of a `relativised’ axiom (cf. Fe92; Me64, p.192) such as:

,

from which we may conclude the existence of some such that:

for all .

However, we shall further show that even this would not yield a model for since, by Theorem 1, we cannot introduce a `completed’ infinity such as into either or any model of !

** A post-computationalist doctrine**

More generally we shall argue that—if our interest is in the arithmetical properties of models of PA—then we first need to make explicit any appeal to non-constructive considerations such as Aristotle’s particularisation (Definition 3).

We shall then argue that, even from a classical perspective, there are serious foundational, post-computationalist, reservations to accepting that a consistent PA can be forced by the Compactness Theorem into admitting non-standard models which contain elements other than the natural numbers.

*Reason:* Any arithmetical application of the Compactness Theorem to PA can neither ignore currently accepted post-computationalist doctrines of objectivity—nor contradict the constructive assignments of satisfaction and truth to the atomic formulas of PA (therefore to the compound formulas under Tarski’s inductive definitions) in terms of either algorithmical verifiability or algorithmic computability (An12, ).

The significance of this doctrine ^{[5]} is that it helps highlight how the algorithmically verifiable (Definition 1) formulas of PA define the classical non-finitary standard interpretation of PA ^{[6]} (to which standard arguments for the existence of non-standard models of PA critically appeal).

Accordingly, we shall show that standard arguments which appeal to the ante-computationalist interpretation of the Compactness Theorem—for forcing non-standard models of PA ^{[7]} which contain an `infinite’ integer—cannot admit constructive assignments of satisfaction and truth ^{[8]} (in terms of algorithmical verifiability) to the atomic formulas of their putative extension of PA.

We shall conclude that such arguments therefore questionably postulate by axiomatic fiat that which they seek to `prove’!

** Standard arguments for non-standard models of PA**

In this limited investigation we shall consider only the following three standard arguments for the existence of non-standard models of the first-order Peano Arithmetic PA:

(*i*) If PA is consistent, then we obtain a non-standard model for PA which contains an `infinite’ integer by applying the Compactness Theorem to the union of the set of formulas that are satisfied or true in the classical `standard’ model of PA ^{[9]} and the countable set of all PA-formulas of the form .

(*ii*) If PA is consistent, then we obtain a non-standard model for PA which contains an `infinite’ integer by adding a constant to the language of PA and applying the Compactness Theorem to the theory **P**.

(*iii*) If PA is consistent, then we obtain a non-standard model for PA which contains an `infinite’ integer by adding the PA formula as an axiom to PA, where is a Gödelian formula ^{[10]} that is unprovable in PA, even though ] is provable in PA for any given PA numeral (Go31, p.25(1)).

We shall first argue that (*i*) and (*ii*)—which appeal to Thoralf Skolem’s ante-computationalist reasoning (in Sk34) for the existence of a non-standard model of PA—should be treated as foundationally fragile from a finitary, post-computationalist perspective within classical logic ^{[11]}.

We shall then argue that although (*iii*)—which appeals to Kurt Gödel’s (also ante-computationalist) reasoning (Go31) for the existence of a non-standard model of PA—does yield a model other than the classical `standard’ model of PA, we cannot conclude by even classical (albeit post-computationalist) reasoning that the domain is other than the domain of the natural numbers unless we make the non-constructive—and logically fragile—extraneous assumption that a consistent PA is necessarily -consistent.

(*-consistency*): A formal system S is -consistent if, and only if, there is no S-formula for which, first, is S-provable and, second, is S-provable for any given S-term .

** Algorithmically verifiable formulas and algorithmically computable formulas**

We begin by distinguishing between:

**Definition 1:** An atomic formula ^{[12]} of PA is algorithmically verifiable under an interpretation if, and only if, for any given numeral , there is an algorithm which can provide objective evidence (Mu91) for deciding the truth value of each formula in the finite sequence of PA formulas under the interpretation.

The concept is well-defined in the sense that 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 (An12).

We note further that the formulas of the first order Peano Arithmetic PA are decidable under the standard interpretation of PA over the domain of the natural numbers if, and only if, they are algorithmically verifiable under the interpretation ^{[13]}.

**Definition 2:** An atomic formula of PA is algorithmically computable under an interpretation if, and only if, there is an algorithm that can provide objective evidence for deciding the truth value of each formula in the denumerable sequence of PA formulas under the interpretation.

This concept too is well-defined in the sense that 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 (An12).

We note further that the PA-formulas are decidable under an algorithmic interpretation of PA over if, and only if, they are algorithmically computable under the interpretation ^{[14]}.

Although we shall not appeal to the following in this paper, we note in passing that the foundational significance ^{[15]} of the distinction lies in the argument that:

**Lemma 1:** There are algorithmically verifiable number theoretical functions which are not algorithmically computable. ^{[16]}

**Proof:** Let denote the digit in the decimal expansion of a putatively given real number in the interval . By the definition of a real number as the limit of a Cauchy sequence of rationals, it follows that is an algorithmically verifiable number-theoretic function. Since every algorithmically computable real is countable (Tu36), Cantor’s diagonal argument (Kl52, pp.6-8) shows that there are real numbers that are not algorithmically computable. The Lemma follows.

** Making non-finitary assumptions explicit**

We next make explicit—and briefly review—a tacitly held fundamental tenet of classical logic which is unrestrictedly adopted as intuitively obvious by standard literature ^{[17]} that seeks to build upon the formal first-order predicate calculus FOL:

**Definition 3:** (*Aristotle’s particularisation*) This holds that from an assertion such as:

`It is not the case that: For any given , does not hold’,

usually denoted symbolically by `‘, we may always validly infer in the classical, Aristotlean, logic of predicates (HA28, pp.58-59) that:

`There exists an unspecified such that holds’,

usually denoted symbolically by `‘.

** The significance of Aristotle’s particularisation for the first-order predicate calculus**

Now we note that in a formal language the formula `‘ is an abbreviation for the formula `‘; and that the commonly accepted interpretation of this formula tacitly appeals to Aristotlean particularisation.

However, as L. E. J. Brouwer had noted in his seminal 1908 paper on the unreliability of logical principles (Br08), the commonly accepted interpretation of this formula is ambiguous if interpretation is intended over an infinite domain.

Brouwer essentially argued that, even supposing the formula `‘ of a formal Arithmetical language interprets as an arithmetical relation denoted by `‘, and the formula `‘ as the arithmetical proposition denoted by `‘, the formula `‘ need not interpret as the arithmetical proposition denoted by the usual abbreviation `‘; and that such postulation is invalid as a general logical principle in the absence of a means for constructing some putative object for which the proposition holds in the domain of the interpretation.

Hence we shall follow the convention that the assumption that `‘ is the intended interpretation of the formula `‘—which is essentially the assumption that Aristotle’s particularisation holds over the domain of the interpretation—must always be explicit.

** The significance of Aristotle’s particularisation for PA**

In order to avoid intuitionistic objections to his reasoning, Kurt Gödel introduced the syntactic property of -consistency ^{[18]} as an explicit assumption in his formal reasoning in his seminal 1931 paper on formally undecidable arithmetical propositions (Go31, p.23 and p.28).

Gödel explained at some length ^{[19]} that his reasons for introducing -consistency explicitly was to avoid appealing to the semantic concept of classical arithmetical truth in Aristotle’s logic of predicates (which presumes Aristotle’s particularisation).

The two concepts are meta-mathematically equivalent in the sense that, if PA is consistent, then PA is -consistent if, and only if, Aristotle’s particularisation holds under the standard interpretation of PA ^{[20]}.

** The ambiguity in admitting an `infinite’ constant**

We begin our consideration of standard arguments for the existence of non-standard models of PA which contain an `infinite’ integer by first highlighting and eliminating an ambiguity in the argument as it is usually found in standard texts ^{[21]}:

“**Corollary.** There is a non-standard model of **P** with domain the natural numbers in which the denotation of every nonlogical symbol is an arithmetical relation or function.

*Proof.* As in the proof of the existence of nonstandard models of arithmetic, add a constant to the language of arithmetic and apply the Compactness Theorem to the theory

**P** n:

to conclude that it has a model (necessarily infinite, since all models of **P** are). The denotations of in any such model will be a non-standard element, guaranteeing that the model is non-standard. Then apply the arithmetical Löwenheim-Skolem theorem to conclude that the model may be taken to have domain the natural numbers, and the denotations of all nonlogical symbols arithmetical.”

… BBJ03, p.306, Corollary 25.3.

** We cannot force PA to admit a transfinite ordinal**

The ambiguity lies in a possible interpretation of the symbol as a `completed’ infinity (such as Cantor’s first transfinite ordinal ) in the context of non-standard models of PA. To eliminate this possibility we establish trivially that, and briefly examine why:

**Theorem 1:** No model of PA can admit a transfinite ordinal under the standard interpretation of the classical logic FOL^{[22]}.

**Proof:** Let [] denote the PA-formula:

Since Aristotle’s particularisation is tacitly assumed under the standard interpretation of FOL, this translates in every model of PA, as:

If denotes an element in the domain of a model of PA, then either is 0, or is a `successor’.

Further, in every model of PA, if denotes the interpretation of []:

(a) is true;

(b) If is true, then is true.

Hence, by Gödel’s completeness theorem:

(c) PA proves ;

(d) PA proves .

*Gödel’s Completeness Theorem:* In any first-order predicate calculus, the theorems are precisely the logically valid well-formed formulas (*i. e. those that are true in every model of the calculus*).

Further, by Generalisation:

(e) PA proves ;

*Generalisation in PA:* [] follows from [].

Hence, by Induction:

(f) is provable in PA.

*Induction Axiom Schema of PA:* For any formula [] of PA:

[]

In other words, except 0, every element in the domain of any model of PA is a `successor’. Further, the standard PA axioms ensure that can only be a `successor’ of a unique element in any model of PA.

Since Cantor’s first limit ordinal is not the `successor’ of any ordinal in the sense required by the PA axioms, and since there are no infinitely descending sequences of ordinals (cf. Me64, p.261) in a model—if any—of a first order set theory such as ZF, the theorem follows.

** Why we cannot force PA to admit a transfinite ordinal**

Theorem 1 reflects the fact that we can define the usual order relation `‘ in PA so that every instance of the PA Axiom Schema of Finite Induction, such as, say:

(*i*) []

yields the weaker PA theorem:

(*ii*) []

Now, if we interpret PA without relativisation in ZF ^{[23]}— i.e., numerals as finite ordinals, [] as [], etc.— then (*ii*) always translates in ZF as a theorem:

(*iii*) []

However, (*i*) does not always translate similarly as a ZF-theorem, since the following is not necessarily provable in ZF:

(*iv*) []

*Example:* Define [] as `[]’.

We conclude that, whereas the language of ZF admits as a constant the first limit ordinal which would interpret in any putative model of ZF as the (`completed’ infinite) set of all finite ordinals:

**Corollary 1:** The language of PA admits of no constant that interprets in any model of PA as the set of all natural numbers.

We note that it is the non-logical Axiom Schema of Finite Induction of PA which does not allow us to introduce—contrary to what is suggested by standard texts ^{[24]}—an `actual’ (*or `completed’*) infinity disguised as an arbitrary constant (usually denoted by or ) into either the language, or a putative model, of PA ^{[25]}.

** Forcing PA to admit denumerable descending dense sequences**

The significance of Theorem 1 is seen in the next two arguments, which attempt to implicitly bypass the Theorem’s constraint by appeal to the Compactness Theorem for forcing a non-standard model onto PA ^{[26]}.

However, we argue in both cases that applying the Compactness Theorem constructively—even from a classical perspective—does not logically yield a non-standard model for PA with an `infinite’ integer as claimed ^{[27]}.

** An argument for a non-standard model of PA**

The first is the argument (Ln08, p.7) that we can define a non-standard model of PA with an infinite descending chain of successors, where the only non-successor is the null element :

1. Let (*the set of natural numbers*); (*equality*); (*the successor function*); (*the addition function*); (*the product function*); (*the null element*) be the structure that serves to define a model of PA, say .

2. Let T[] be the set of PA-formulas that are satisfied or true in .

3. The PA-provable formulas form a subset of T[].

4. Let be the countable set of all PA-formulas of the form , where the index is a natural number.

5. Let T be the union of and T[].

6. T[] plus any finite set of members of has a model, e.g., itself, since is a model of any finite descending chain of successors.

7. Consequently, by Compactness, T has a model; call it .

8. has an infinite descending sequence with respect to because it is a model of .

9. Since PA is a subset of T, is a non-standard model of PA.

** Why the argument in is logically fragile**

However if—as claimed in above— is a model of T[] plus any finite set of members of , and the PA term is well-defined for any given natural number , then:

All PA-formulas of the form are PA-provable,

is a proper sub-set of the PA-provable formulas, and

T is identically T[].

*Reason:* The argument cannot be that some PA-formula of the form is true in , but not PA-provable, as this would imply that if PA is consistent then PA+ has a model other than ; in other words, it would presume that which is sought to be proved, namely that PA has a non-standard model ^{[28]}!

Consequently, the postulated model of T in by `Compactness’ is the model that defines T[]. However, has no infinite descending sequence with respect to , even though it is a model of .

Hence the argument does not establish the existence of a non-standard model of PA with an infinite descending sequence with respect to the successor function .

** A formal argument for a non-standard model of PA**

The second is the more formal argument ^{[29]}:

“Let denote the complete -theory of the standard model, i.e. is the collection of all true -sentences. For each we let be the closed term of ; is just the constant symbol . We now expand our language by adding to it a new constant symbol , obtaining the new language , and consider the following -theory with axioms

(for each )

and

(for each )

This theory is consistent, for each finite fragment of it is contained in

for some , and clearly the -structure with domain and interpreted naturally, and interpreted by the integer , satisfies . Thus by the compactness theore is consistent and has a model . The first thing to note about is that

for all , and hence it contains an `infinite’ integer.”

** Why the argument in too is logically fragile**

We note again that, from an arithmetical perspective, any application of the Compactness Theorem to PA cannot ignore currently accepted computationalist doctrines of objectivity (cf. Mu91) and contradict the constructive assignment of satisfaction and truth to the atomic formulas of PA (therefore to the compound formulas under Tarski’s inductive definitions) in terms of either algorithmical verifiability or algorithmic computability (An12, ).

Accordingly, from an arithmetical perspective we can only conclude by the Compactness Theorem that if is the -theory of the standard model (interpretation), then we may consistently add to it the following as an additional—not necessarily independent—axiom:

.

Moreover, even though is algorithmically computable as always true in the standard model—whence all instances of it are also therefore in —we cannot conclude by the Compactness Theorem that is consistent and has a model which contains an `infinite’ integer.

*Reason:* The condition `‘ in requires, first of all, that we must be able to extend by the addition of a `relativised’ axiom (cf. Fe92; Me64, p.192) such as:

,

from which we may conclude the existence of some such that:

for all .

However, even this would not yield a model for since, by Theorem 1, we cannot introduce a `completed’ infinity such as into any model of !

As the argument stands, it seeks to violate finitarity by adding a new constant to the language of PA that is not definable in and, ipso facto, adding an atomic formula to PA whose satisfaction under any interpretation of PA is not algorithmically verifiable!

Since the atomic formulas of PA are algorithmically verifiable under the standard interpretation (An12, Corollary 2), the above conclusion too postulates that which it seeks to prove!

Moreover, the postulation would be false if were categorical.

Since must have a non-standard model if it is not categorical, we consider next whether we may conclude from Gödel’s incompleteness argument (in Go31) that any such model can have an `infinite’ integer.

** Gödel’s argument for a non-standard model of PA**

We begin by considering the Gödelian formula ^{[30]} which is unprovable in PA if PA is consistent, even though the formula is provable in a consistent PA for any given PA numeral .

Now, it follows from Gödel’s reasoning ^{[31]} that:

**Theorem 2:** If PA is consistent, then we may add the PA formula as an axiom to PA without inviting inconsistency.

**Theorem 3:** If PA is -consistent, then we may add the PA formula as an axiom to PA without inviting inconsistency.

Gödel concluded from this that:

**Corollary 2:** If PA is -consistent, then there are at least two distinctly different models of PA.

If we assume that a consistent PA is necessarily -consistent, then it follows that one of the two putative models postulated by Corollary 2 must contain elements other than the natural numbers.

We conclude that Gödel’s justification for the assumption that non-standard models of PA containing elements other than the natural numbers are logically feasible lies in his non-constructive—and logically fragile—assumption that a consistent PA is necessarily -consistent.

** Why Gödel’s assumption is logically fragile**

Now, whereas Gödel’s proof of Corollary 2 appeals to the non-constructive Aristotle’s particularisation, a constructive proof of the Corollary follows trivially from evidence-based interpretations of PA (An12).

*Reason:* Tarski’s inductive definitions allow us to provide *finitary* satisfaction and truth certificates to all atomic (and ipso facto to all compound) formulas of PA over the domain of the natural numbers in *two* essentially different ways:

(1) In terms of algorithmic verifiabilty (An12, ); and

(2) In terms of algorithmic computability (An12, ).

That there can be even one, let alone two, logically sound and finitary assignments of satisfaction and truth certificates to both the atomic and compound formulas of PA was hitherto unsuspected!

Moreover, neither the putative `algorithmically verifiable’ model, nor the `algorithmically computable’ model, of PA defined by these finitary satisfaction and truth assignments contains elements other than the natural numbers.

**(a) Any algorithmically verifiable model of PA is necessarily over **

For instance if, in the first case, we assume that the algorithmically verifiable atomic formulas of PA determine an algorithmically verifiable model of PA over the domain of the PA numerals, then such a putative model would be isomorphic to the standard model of PA over the domain of the natural numbers (An12, & , Corollary 2).

However, such a putative model of PA over would not be finitary since, if the formula were to interpret as true in it, then we could only conclude that, for any numeral , there is an algorithm which will finitarily certify the formula as true under an algorithmically verifiable interpretation in .

We could not conclude that there is a single algorithm which, for any numeral , will finitarily certify the formula as true under the algorithmically verifiable interpretation in .

Consequently, the PA Axiom Schema of Finite Induction would not interpret as true finitarily under the algorithmically verifiable interpretation of PA over the domain of the PA numerals.

Thus the algorithmically verifiable interpretation of PA would not define a finitary model of PA.

However, if we were to assume that the algorithmically verifiable interpretation of PA defines a non-finitary model of PA, then it would follow that:

PA is necessarily -consistent;

Aristotle’s particularisation holds over ; and

The `standard’ interpretation of PA also defines a non-finitary model of PA over .

**(b) The algorithmically computable interpretation of PA is over **

The second case is where the algorithmically computable atomic formulas of PA determine an algorithmically computable model of PA over the domain of the natural numbers (An12, & ).

The algorithmically computable model of PA is finitary since we can show that, if the formula interprets as true under it, then we may always conclude that there is a single algorithm which, for any numeral , will finitarily certify the formula as true in under the algorithmically computable interpretation.

Consequently we can show that all the PA axioms—including the Axiom Schema of Finite Induction—interpret finitarily as true in under the algorithmically computable interpretation of PA, and the PA Rules of Inference preserve such truth finitarily (An12, Theorem 4).

Thus the algorithmically computable interpretation of PA defines a finitary model of PA from which we may conclude that:

PA is consistent (An12, , Theorem 6).

** Why we cannot conclude that PA is necessarily -consistent**

By the way the above finitary interpretation (b) is defined under Tarski’s inductive definitions (An12, ), if a PA-formula interprets as true in the corresponding finitary model of PA, then there is an algorithm that provides a certificate for such truth for in ; whilst if interprets as false in the above finitary model of PA, then there is no algorithm that can provide such a truth certificate for in (An12, ).

Now, if there is no algorithm that can provide such a truth certificate for the Gödelian formula in , then we would have by definition first that the PA formula is true in the model, and second by Gödel’s reasoning that the formula is true in the model for any given numeral . Hence Aristotle’s particularisation would not hold in the model.

However, by definition if PA were -consistent then Aristotle’s particularisation must necessarily hold in every model of PA.

It follows that unless we can establish that there is some algorithm which can provide such a truth certificate for the Gödelian formula in , we cannot make the unqualified assumption—as Gödel appears to do—that a consistent PA is necessarily -consistent.

**Conclusion**

We have argued that standard arguments for the existence of non-standard models of the first-order Peano Arithmetic PA with domains other than the domain of the natural numbers should be treated as logically fragile even from within classical logic. In particular we have argued that although Gödel’s argument for the existence of a non-standard model of PA does yield a model of PA other than the classical non-finitary `standard’ model, we cannot conclude from it that the domain is other than the domain of the natural numbers unless we make the non-constructive—and logically fragile—assumption that a consistent PA is necessarily -consistent.

**References**

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

**Be59** Evert W. Beth. 1959. *The Foundations of Mathematics.* In *Studies in Logic and the Foundations of Mathematics.* Edited by L. E. J. Brouwer, E. W. Beth, A. Heyting. 1959. North Holland Publishing Company, Amsterdam.

**BF58** Paul Bernays and Abraham A. Fraenkel. 1958. *Axiomatic Set Theory* In *Studies in Logic and the Foundations of Mathematics.* Edited by L. E. J. Brouwer, E. W. Beth, A. Heyting. 1959. North Holland Publishing Company, Amsterdam.

**Bo00** Andrey I. Bovykin. 2000. *On order-types of models of arithmetic.* Thesis submitted to the University of Birmingham for the degree of Ph.D. in the Faculty of Science, School of Mathematics and Statistics, The University of Birmingham, Edgbaston, Birmingham, B15 2TT, United Kingdom, 13 April 2000.

**Br08** L. E. J. Brouwer. 1908. *The Unreliability of the Logical Principles.* English translation in A. Heyting, Ed. *L. E. J. Brouwer: Collected Works 1: Philosophy and Foundations of Mathematics.* Amsterdam: North Holland / New York: American Elsevier (1975): pp.107-111.

**Co66** Paul J. Cohen. 1966. *Set Theory and the Continuum Hypothesis.* (Lecture notes given at Harvard University, Spring 1965) W. A. Benjamin, Inc., New York.

**Da82** Martin Davis. 1958. *Computability and Unsolvability.* 1982 ed. Dover Publications, Inc., New York.

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

**Fe92** Solomon Feferman. 1992. *What rests on what: The proof-theoretic analysis of mathematics* Invited lecture, 15th International Wittgenstein Symposium: *Philosophy of Mathematics*, held in Kirchberg/Wechsel, Austria, 16-23 August 1992.

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

**HA28** David Hilbert & Wilhelm Ackermann. 1928. *Principles of Mathematical Logic.* Translation of the second edition of the *Grundzüge Der Theoretischen Logik.* 1928. Springer, Berlin. 1950. Chelsea Publishing Company, New York.

**Hi25** David Hilbert. 1925. *On the Infinite.* Text of an address delivered in Münster on 4th June 1925 at a meeting of the Westphalian Mathematical Society. In Jean van Heijenoort. 1967.Ed. *From Frege to Gödel: A source book in Mathematical Logic, 1878 – 1931.* Harvard University Press, Cambridge, Massachusetts.

**HP98** Petr Hájek and Pavel Pudlák. 1998. *Metamathematics of First-Order Arithmetic.* Volume 3 of *Perspectives in Mathematical Logic* Series, ISSN 0172-6641. Springer-Verlag, Berlin, 1998.

**Ka91** Richard Kaye. 1991. *Models of Peano Arithmetic.* Oxford Logic Guides, 15. Oxford Science Publications. The Clarendon Press, Oxford University Press, New York, 1991.

**Ka11** Richard Kaye. 2011. *Tennenbaum’s theorem for models of arithmetic.* In *Set Theory, Arithmetic, and Foundations of Mathematics.* Eds. Juliette Kennedy & Roman Kossak. Lecture Notes in Logic (No. 36). pp.66-79. Cambridge University Press, 2011. Cambridge Books Online. http://dx.doi.org/10.1017/CBO9780511910616.005.

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

**Kn63** G. T. Kneebone. 1963. *Mathematical Logic and the Foundations of Mathematics: An Introductory Survey.* D. Van Norstrand Company Limited, London.

**Ko06** Roman Kossak and James H. Schmerl. 2006. *The structure of models of Peano arithmetic.* Oxford Logic Guides, 50. Oxford Science Publications. The Clarendon Press, Oxford University Press, Oxford, 2006.

**Li64** A. H. Lightstone. 1964. *The Axiomatic Method.* Prentice Hall, NJ.

**Ln08** Laureano Luna. 2008. *On non-standard models of Peano Arithmetic.* In *The Reasoner,* Vol(2)2 p7.

**Me64** Elliott Mendelson. 1964. *Introduction to Mathematical Logic.* Van Norstrand, Princeton.

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

**Nv64** P. S. Novikov. 1964. *Elements of Mathematical Logic.* Oliver & Boyd, Edinburgh and London.

**Qu63** Willard Van Orman Quine. 1963. *Set Theory and its Logic.* Harvard University Press, Cambridge, Massachusette.

**Rg87** Hartley Rogers Jr. 1987. *Theory of Recursive Functions and Effective Computability.* MIT Press, Cambridge, Massachusetts.

**Ro53** J. Barkley Rosser. 1953. *Logic for Mathematicians.* McGraw Hill, New York.

**Sh67** Joseph R. Shoenfield. 1967. *Mathematical Logic.* Reprinted 2001. A. K. Peters Ltd., Massachusetts.

**Sk28** Thoralf A. Skolem. 1928. *On Mathematical Logic.* Text of a lecture delivered on 22nd October 1928 before the Norwegian Mathematical Association. In Jean van Heijenoort. 1967. Ed. *From Frege to Gödel: A source book in Mathematical Logic, 1878 – 1931* Harvard University Press, Cambridge, Massachusetts.

**Sk34** Thoralf A. Skolem. 1934. *\”{U}ber die Nicht-charakterisierbarkeit der Zahlenreihe mittels endlich oder abz\”{a}hlbar unendlich vieler Aussagen mit ausschliesslich Zahlenvariablen.* Fundamenta Mathematicae, 23, 150-161. English version: *Peano’s axioms and models of arithmetic.* In *Mathematical interpretations of formal systems.* North Holland, Amsterdam, 1955, pp.1-14.

**Sm92** Raymond M. Smullyan. 1992. *Gödel’s Incompleteness Theorems.* Oxford University Press, Inc., New York.

**Su60** Patrick Suppes. 1960. *Axiomatic Set Theory.* Van Norstrand, Princeton.

**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-265; corrections, Ibid, vol 43 (1937) pp. 544-546.

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

**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 argument.* Presented on 7’th April at the workshop on `*Logical Quantum Structures*‘ at UNILOG’2013, World Congress and School on Universal Logic, March 2013 – April 2013, Rio de Janeiro, Brazil.

**Notes**

Return to 1: By which we mean arguments such as in Ka91 (see pg.1), where the meta-theory is taken to be a set-theory such as ZF or ZFC, and the logical consistency of the meta-theory is not considered relevant to the argumentation.

Return to 2: For purposes of this investigation we may take this to be a first order theory such as the theory S defined in Me64, pp.102-103.

Return to 3: eg. Ka91; Bo00; BBJ03,\ ch.25,\ p.302; Ko06; Ka11.

Return to 4: As argued in Ka91, p.10-11.

Return to 5: Some of the—hitherto unsuspected—consequences of this doctrine are detailed in An12.

Return to 6: An12, Corollary 2; `non-finitary’ because the Axiom Schema of Finite Induction *cannot* 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 7: eg., BBJ03, p.155, Lemma 13.3 (Model existence lemma).

Return to 8: cf. The standard non-constructive set-theoretical assignment-by-postulation **(S5)** of the satisfaction properties **(S1)** to **(S8)** in BBJ03, p.153, Lemma 13.1 (Satisfaction properties lemma), which appeals critically to Aristotle’s particularisation.

Return to 9: For purposes of this investigation we may take this to be an interpretation of PA as defined in Me64, p.107.

Return to 10: In his seminal 1931 paper Go31, Kurt Gödel defines, and refers to, the formula corresponding to only by its `Gödel’ number (op. cit., p.25, Eqn.(12)), and to the formula corresponding to only by its `Gödel’ number .

Return to 11: By `classical logic’ we mean the standard first-order predicate calculus FOL where we neither deny the Law of the Excludeds Middle, nor assume that the FOL is -consistent (i.e., we do not assume that Aristotle’s particularisation must hold under any interpretation of the logic).

Return to 12: *Notation*: For the sake of convenience, we shall use square brackets to indicate that the expression enclosed by them is to be treated as denoting a formula of a formal theory, and not as denoting an interpretation.

Return to 13: However, as noted earlier, the Axiom Schema of Finite Induction *cannot* 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 14: In this case however, 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 (An12, Theorem 4).

Return to 15: The far reaching—hitherto unsuspected—consequences of this distinction for PA are detailed in An12.

Return to 16: 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, 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 17: See Hi25, p.382; HA28, p.48; Sk28, p.515; Go31, p.32.; Kl52, p.169; Ro53, p.90; BF58, p.46; Be59, pp.178 & 218; Su60, p.3; Wa63, p.314-315; Qu63, pp.12-13; Kn63, p.60; Co66, p.4; Me64, pp.45, 47, 52(ii), 214(fn); Nv64, p.92; Li64, p.33; Sh67, p.13; Da82, p.xxv; Rg87, p.xvii; EC89, p.174; Mu91; Sm92, p.18, Ex.3; BBJ03, p.102.

Return to 18: The significance of -consistency for the formal system PA is highlighted inAn12.

Return to 19: In his introduction on p.9 of Go31.

Return to 20: For details see An12.

Return to 21: cf. HP98, p.13, ; Me64, p.112, Ex. 2.

Return to 22: For purposes of this investigation we may take this to be the first order predicate calculus as defined in Me64, p.57.

Return to 23: In the sense indicated by Feferman Fe92.

Return to 24: eg. HP98, p.13, ; Ka91, p.11 & p.12, fig.1; BBJ03. p.306, Corollary 25.3; Me64, p.112, Ex. 2.

Return to 25: A possible reason why the Axiom Schema of Finite Induction does not admit non-finitary reasoning into either PA, or into any model of PA, is suggested in below.

Return to 26: eg. Ln08, p.7; Ka91, pp.10-11, p.74 & p.75, Theorem 6.4.

Return to 27: And as suggested also by standard texts in such cases; eg. BBJ03. p.306, Corollary 25.3; Me64, p.112, Ex. 2.

Return to 28: To place this distinction in perspective, Adrien-Marie Legendre and Carl Friedrich Gauss independently conjectured in 1796 that, if denotes the number of primes less than , then is asymptotically equivalent to /In. Between 1848/1850, Pafnuty Lvovich Chebyshev confirmed that if /(/In) has a limit, then it must be 1. However, the crucial question of whether /(/In) has a limit at all was answered in the affirmative using analytic methods independently by Jacques Hadamard and Charles Jean de la Vallée Poussin only in 1896, and using only elementary methods by Atle Selberg and Paul Erdös in 1949.

Return to 29: Ka91, pp.10-11; attributed as essentially Skolem’s argument in Sk34.

Return to 30: In his seminal 1931 paper Go31, Kurt Gödel defines, and refers to, the formula corresponding to only by its `Gödel’ number (op. cit., p.25, Eqn.(12)), and to the formula corresponding to only by its `Gödel’ number .

Return to 31: Go31, p.25(1) & p.25(2).

** The Holy Grail of Arithmetic: Bridging Provability and Computability**

*See also this update.*

**Peter Wegner and Dina Goldin**

In a short opinion paper, `Computation Beyond Turing Machines‘, Computer Scientists Peter Wegner and Dina Goldin (Wg03) advanced the thesis that:

`A paradigm shift is necessary in our notion of computational problem solving, so it can provide a complete model for the services of today’s computing systems and software agents.’

We note that Wegner and Goldin’s arguments, in support of their thesis, seem to reflect an extraordinarily eclectic view of mathematics, combining both an implicit acceptance of, and implicit frustration at, the standard interpretations and dogmas of classical mathematical theory:

(i) `… Turing machines are inappropriate as a universal foundation for computational problem solving, and … computer science is a fundamentally non-mathematical discipline.’

(ii) `(Turing’s) 1936 paper … proved that mathematics could not be completely modeled by computers.’

(iii) `… the Church-Turing Thesis … equated logic, lambda calculus, Turing machines, and algorithmic computing as equivalent mechanisms of problem solving.’

(iv) `Turing implied in his 1936 paper that Turing machines … could not provide a model for all forms of mathematics.’

(v) `… Gödel had shown in 1931 that logic cannot model mathematics … and Turing showed that neither logic nor algorithms can completely model computing and human thought.’

These remarks vividly illustrate the dilemma with which not only Theoretical Computer Sciences, but all applied sciences that depend on mathematics—for providing a verifiable language to express their observations precisely—are faced:

**Query:** Are formal classical theories essentially unable to adequately express the extent and range of human cognition, or does the problem lie in the way formal theories are classically interpreted at the moment?

The former addresses the question of whether there are absolute limits on our capacity to express human cognition unambiguously; the latter, whether there are only temporal limits—not necessarily absolute—to the capacity of classical interpretations to communicate unambiguously that which we intended to capture within our formal expression.

Prima facie, applied science continues, perforce, to interpret mathematical concepts Platonically, whilst waiting for mathematics to provide suitable, and hopefully reliable, answers as to how best it may faithfully express its observations verifiably.

**Lance Fortnow**

This dilemma is also reflected in Computer Scientist Lance Fortnow’s on-line rebuttal of Wegner and Goldin’s thesis, and of their reasoning.

Thus Fortnow divides his faith between the standard interpretations of classical mathematics (and, possibly, the standard set-theoretical models of formal systems such as standard Peano Arithmetic), and the classical computational theory of Turing machines.

He relies on the former to provide all the proofs that matter:

`Not every mathematical statement has a logical proof, but logic does capture everything we can prove in mathematics, which is really what matters’;

and, on the latter to take care of all essential, non-provable, truth:

`… what we can compute is what computer science is all about’.

**Can faith alone suffice?**

However, as we shall argue in a subsequent post, Fortnow’s faith in a classical Church-Turing Thesis that ensures:

`… Turing machines capture everything we can compute’,

may be as misplaced as his faith in the infallibility of standard interpretations of classical mathematics.

*The reason:* There are, prima facie, reasonably strong arguments for a Kuhnian (Ku62) paradigm shift; not, as Wegner and Goldin believe, in the notion of computational problem solving, but in the standard interpretations of classical mathematical concepts.

However, Wegner and Goldin could be right in arguing that the direction of such a shift must be towards the incorporation of non-algorithmic effective methods into classical mathematical theory (as detailed in the Birmingham paper); presuming, from the following remarks, that this is, indeed, what `external interactions’ are assumed to provide beyond classical Turing-computability:

(vi) `… that Turing machine models could completely describe all forms of computation … contradicted Turing’s assertion that Turing machines could only formalize algorithmic problem solving … and became a dogmatic principle of the theory of computation’.

(vii) `… interaction between the program and the world (environment) that takes place during the computation plays a key role that cannot be replaced by any set of inputs determined prior to the computation’.

(viii) `… a theory of concurrency and interaction requires a new conceptual framework, not just a refinement of what we find natural for sequential [algorithmic] computing’.

(ix) `… the assumption that all of computation can be algorithmically specified is still widely accepted’.

A widespread notion of particular interest, which seems to be recurrently implicit in Wegner and Goldin’s assertions too, is that mathematics is a dispensable tool of science, rather than its indispensable mother tongue.

**Elliott Mendelson**

However, the roots of such beliefs may also lie in ambiguities, in the classical definitions of foundational elements, that allow the introduction of non-constructive—hence non-verifiable, non-computational, ambiguous, and essentially Platonic—elements into the standard interpretations of classical mathematics.

For instance, in a 1990 philosophical reflection, Elliott Mendelson’s following remarks (in Me90; reproduced from Selmer Bringsjord (Br93)), implicitly imply that classical definitions of various foundational elements can be argued as being either ambiguous, or non-constructive, or both:

`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.’

Consequently, standard interpretations of classical theory may, inadvertently, be weakening a desirable perception—of mathematics as the lingua franca of scientific expression—by ignoring the possibility that, since mathematics is, indeed, indisputably accepted as the language that most effectively expresses and communicates intuitive truth, the chasm between formal truth and provability must, of necessity, be bridgeable.

**Cristian Calude, Elena Calude and Solomon Marcus**

The belief in the existence of such a bridge is occasionally implicit in interpretations of computational theory.

For instance, in an arXived paper *Passages of Proof*, Computer Scientists Cristian Calude, Elena Calude and Solomon Marcus remark that:

“Classically, there are two equivalent ways to look at the mathematical notion of proof: logical, as a finite sequence of sentences strictly obeying some axioms and inference rules, and computational, as a specific type of computation. Indeed, from a proof given as a sequence of sentences one can easily construct a Turing machine producing that sequence as the result of some finite computation and, conversely, given a machine computing a proof we can just print all sentences produced during the computation and arrange them into a sequence.”

In other words, the authors seem to hold that Turing-computability of a `proof’, in the case of an arithmetical proposition, is equivalent to provability of its representation in PA.

**Wilfrid Sieg**

We now attempt to build such a bridge formally, which is essentially one between the arithmetical ‘Decidability and Calculability’ described by Philosopher Wilfrid Sieg in his in-depth and wide-ranging survey ‘On Comptability‘, in which he addresses Gödel’s lifelong belief that an iff bridge between the two concepts is ‘impossible’ for ‘the whole calculus of predicates’ (Wi08, p.602).

** Bridging provability and computability: The foundations**

In the paper titled “Evidence-Based Interpretations of ” that was presented to the Symposium on Computational Philosophy at the AISB/IACAP World Congress 2012-Alan Turing 2012, held from to July 2012 at the University of Birmingham, UK (reproduced in this post) we have defined what it means for a number-theoretic function to be:

(i) Algorithmically verifiable;

(ii) Algorithmically computable.

We have shown there that:

(i) The standard interpretation of the first order Peano Arithmetic PA is finitarily sound if, and only if, Aristotle’s particularisation holds over ; and the latter is the case if, and only if, PA is -consistent.

(ii) We can define a finitarily sound algorithmic interpretation of PA over the domain where, if is an atomic formula of PA, then the sequence of natural numbers satisfies if, and only if is algorithmically computable under , but we do not presume that Aristotle’s particularisation is valid over .

(iii) The axioms of PA are always true under the finitary interpretation , and the rules of inference of PA preserve the properties of satisfaction/truth under .

We concluded that:

**Theorem 1:** The interpretation of PA is finitarily sound.

**Theorem 2:** PA is consistent.

** Extending Buss’ Bounded Arithmetic**

One of the more significant consequences of the Birmingham paper is that we can extend the iff bridge between the domain of provability and that of computability envisaged under Buss’ Bounded Arithmetic by showing that an arithmetical formula is PA-provable if, and only if, interprets as true under an algorithmic interpretation of PA.

** A Provability Theorem for PA**

We first show that PA can have no non-standard model (for a distinctly different proof of this convention-challenging thesis see this post and this paper), since it is `algorithmically’ complete in the sense that:

**Theorem 3:** (*Provability Theorem for PA*) A PA formula is PA-provable if, and only if, is algorithmically computable as always true in .

**Proof:** We have by definition that interprets as true under the interpretation if, and only if, is algorithmically computable as always true in .

Since is finitarily sound, it defines a finitary model of PA over —say —such that:

If is PA-provable, then is algorithmically computable as always true in ;

If is PA-provable, then it is not the case that is algorithmically computable as always true in .

Now, we cannot have that both and are PA-unprovable for some PA formula , as this would yield the contradiction:

(i) There is a finitary model—say —of PA+ in which is algorithmically computable as always true in .

(ii) There is a finitary model—say —of PA+ in which it is not the case that is algorithmically computable as always true in

The lemma follows.

** The holy grail of arithmetic**

We thus have that:

**Corollary 1:** PA is categorical finitarily.

Now we note that:

**Lemma 2:** If PA has a sound interpretation over , then there is a PA formula which is algorithmically verifiable as always true over under even though is not PA-provable.

**Proof** In his seminal 1931 paper on formally undecidable arithmetical propositions, Kurt Gödel has shown how to construct an arithmetical formula with a single variable—say ^{[1]}—such that is not PA-provable ^{[2]}, but is instantiationally PA-provable for any given PA numeral . Hence, for any given numeral , the PA formula must hold for some . The lemma follows.

By the argument in Theorem 3 it follows that:

**Corollary 2:** The PA formula defined in Lemma 2 is PA-provable.

**Corollary 3:** Under any sound interpretation of PA, Gödel’s interprets as an algorithmically verifiable, but not algorithmically computable, tautology over .

**Proof** Gödel has shown that ^{[3]} interprets as an algorithmically verifiable tautology ^{[4]}. By Corollary 2 is not algorithmically computable as always true in .

**Corollary 4:** PA is *not* -consistent. ^{[5]}

**Proof** Gödel has shown that if PA is consistent, then is PA-provable for any given PA numeral ^{[6]}. By Corollary 2 and the definition of -consistency, if PA is consistent then it is *not* -consistent.

**Corollary 5:** The standard interpretation of PA is not finitarily sound, and does not yield a finitary model of PA ^{[7]}.

**Proof** If PA is consistent but not -consistent, then Aristotle’s particularisation does not hold over . Since the `standard’, interpretation of PA appeals to Aristotle’s particularisation, the lemma follows.

Since formal quantification is currently interpreted in classical logic ^{[8]} so as to admit Aristotle’s particularisation over as axiomatic ^{[9]}, the above suggests that we may need to review number-theoretic arguments ^{[10]} that appeal unrestrictedly to classical Aristotlean logic.

** The Provability Theorem for PA and Bounded Arithmetic**

In a 1997 paper ^{[11]}, Samuel R. Buss considered Bounded Arithmetics obtained by:

(a) limiting the applicability of the Induction Axiom Schema in PA only to functions with quantifiers bounded by an unspecified natural number bound ;

(b) `weakening’ the statement of the axiom with the aim of differentiating between effective computability over the sequence of natural numbers, and feasible `polynomial-time’ computability over a bounded sequence of the natural numbers ^{[12]}.

Presumably Buss’ intent—as expressed below—is to build an iff bridge between provability in a Bounded Arithmetic and Computability so that a formula, say , is provable in the Bounded Arithmetic if, and only if, there is an algorithm that, for any given numeral , decides the formula as `true’:

If is provable, then there should be an algorithm to find as a function of ^{[13]}.

Since we have proven such a Provability Theorem for PA in the previous section, the first question arises:

** Does the introduction of bounded quantifiers yield any computational advantage?**

Now, one difference ^{[14]} between a Bounded Arithmetic and PA is that we can presume in the Bounded Arithmetic that, from a proof of , we may always conclude that there is some numeral such that is provable in the arithmetic; however, this is not a finitarily sound conclusion in PA.

*Reason:* Since is simply a shorthand for , such a presumption implies that Aristotle’s particularisation holds over the natural numbers under any finitarily sound interpretation of PA.

To see that (as Brouwer steadfastly held) this may not always be the case, interpret as ^{[15]}:

There is an algorithm that decides as `true’ for any given numeral .

In such case, if is provable in PA, then we can only conclude that:

There is an algorithm that, for any given numeral , decides that it is not the case that there is an algorithm that, for any given numeral , decides as `true’.

We cannot, however, conclude—as we can in a Bounded Arithmetic—that:

There is an algorithm that, for any given numeral , decides that there is an algorithm that, for some numeral , decides as `true’.

*Reason:* may be a Halting-type formula for some numeral .

This could be the case if were PA-*un*provable, but PA-provable for any given numeral .

Presumably it is the belief that any finitarily sound interpretation of PA requires Aristotle’s particularisation to hold in , and the recognition that the latter does not admit linking provability to computability in PA, which has led to considering the effect of bounding quantification in PA.

However, as we have seen in the preceding sections, we are able to link provability to computability through the Provability Theorem for PA by recognising precisely that, to the contrary, any interpretation of PA which requires Aristotle’s particularisation to hold in cannot be finitarily sound!

The postulation of an unspecified bound in a Bounded Arithmetic in order to arrive at a provability-computability link thus appears dispensible.

The question then arises:

** Does `weakening’ the PA Induction Axiom Schema yield any computational advantage?**

Now, Buss considers a bounded arithmetic which is, essentially, PA with the following `weakened’ Induction Axiom Schema, PIND ^{[16]}:

However, PIND can be expressed in first-order Peano Arithmetic PA as follows:

.

Moreover, the above is a particular case of PIND():

.

Now we have the PA theorem:

It follows that the following is also a PA theorem:

In other words, for any numeral , PIND() is equivalent in PA to the standard Induction Axiom of PA!

Thus, the Provability Theorem for PA suggests that all arguments and conclusions of a Bounded Arithmetic can be reflected in PA without any loss of generality.

**References**

**Br93** Selmer Bringsjord 1993. *The Narrational Case Against Church’s Thesis.* Easter APA meetings, Atlanta.

**Br08** L. E. J. Brouwer. 1908. *The Unreliability of the Logical Principles.* English translation in A. Heyting, Ed. *L. E. J. Brouwer: Collected Works 1: Philosophy and Foundations of Mathematics.* Amsterdam: North Holland / New York: American Elsevier (1975): pp.107-111.

**Bu97** Samuel R. Buss. 1997. *Bounded Arithmetic and Propositional Proof Complexity.* In *Logic of Computation.* pp.67-122. Ed. H. Schwichtenberg. Springer-Verlag, Berlin.

**CCS01** Cristian S. Calude, Elena Calude and Solomon Marcus. 2001. *Passages of Proof.* Workshop, Annual Conference of the Australasian Association of Philosophy (New Zealand Division), Auckland. Archived at: http://arxiv.org/pdf/math/0305213.pdf. Also in EATCS Bulletin, Number 84, October 2004, viii+258 pp.

**Da82** Martin Davis. 1958. *Computability and Unsolvability.* 1982 ed. Dover Publications, Inc., New York.

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

**HA28** David Hilbert & Wilhelm Ackermann. 1928. *Principles of Mathematical Logic.* Translation of the second edition of the *Grundzüge Der Theoretischen Logik.* 1928. Springer, Berlin. 1950. Chelsea Publishing Company, New York.

**He04** Catherine Christer-Hennix. 2004. *Some remarks on Finitistic Model Theory, Ultra-Intuitionism and the main problem of the Foundation of Mathematics.* ILLC Seminar, 2nd April 2004, Amsterdam.

**Hi25** David Hilbert. 1925. *On the Infinite.* Text of an address delivered in Münster on 4th June 1925 at a meeting of the Westphalian Mathematical Society. In Jean van Heijenoort. 1967.Ed. *From Frege to Gödel: A source book in Mathematical Logic, 1878 – 1931.* Harvard University Press, Cambridge, Massachusetts.

**Ku62** Thomas S. Kuhn. 1962. *The structure of Scientific Revolutions.* 2nd Ed. 1970. University of Chicago Press, Chicago.

**Me90** Elliott Mendelson. 1990. *Second Thoughts About Church’s Thesis and Mathematical Proofs.* In *Journal of Philosophy* 87.5.

**Pa71** Rohit Parikh. 1971. *Existence and Feasibility in Arithmetic.* In *The Journal of Symbolic Logic,>i> Vol.36, No. 3 (Sep., 1971), pp. 494-508.*

**Rg87** Hartley Rogers Jr. 1987. *Theory of Recursive Functions and Effective Computability.* MIT Press, Cambridge, Massachusetts.

**Ro36** J. Barkley Rosser. 1936. *Extensions of some Theorems of Gödel and Church.* In M. Davis (ed.). 1965. *The Undecidable.* Raven Press, New York. Reprinted from *The Journal of Symbolic Logic.* Vol.1. pp.87-91.

**Si08** Wilfrid Sieg. 2008. *On Computability* in *Handbook of the Philosophy of Science. Philosophy of Mathematics.* pp.525-621. Volume Editor: Andrew Irvine. General Editors: Dov M. Gabbay, Paul Thagard and John Woods. Elsevier BV. 2008.

**WG03** Peter Wegner and Dina Goldin. 2003. *Computation Beyond Turing Machines.* Communications of the ACM, 46 (4) 2003.

**Notes**

Return to 1: Gödel refers to this formula only by its Gödel number (Go31, p.25(12)).

Return to 2: Gödel’s immediate aim in Go31 was to show that is not P-provable; by Generalisation it follows, however, that is also not P-provable.

Return to 3: Gödel refers to this formula only by its Gödel number (Go31, p.25, eqn.12).

Return to 4: Go31, p.26(2): “ holds”.

Return to 5: This conclusion is contrary to accepted dogma. See, for instance, Davis’ remarks in Da82, p.129(iii) that:

“… there is no equivocation. Either an adequate arithmetical logic is -inconsistent (in which case it is possible to prove false statements within it) or it has an unsolvable decision problem and is subject to the limitations of Gödel’s incompleteness theorem”.

Return to 6: Go31, p.26(2).

Return to 7: I note that finitists of all hues—ranging from Brouwer Br08 to Alexander Yessenin-Volpin He04—have persistently questioned the finitary soundness of the `standard’ interpretation .

Return to 8: See Hi25, p.382; HA28, p.48; Be59, pp.178 \& 218.

Return to 9: In the sense of being intuitively obvious. See, for instance, Da82, p.xxiv; Rg87, p.308 (1)-(4); EC89, p.174 (4); BBJ03, p.102.

Return to 10: For instance Rosser’s construction of an undecidable arithmetical proposition in PA (see Ro36)—which does not explicitly assume that PA is -consistent—implicitly presumes that Aristotle’s particularisation holds over .

Return to 11: Bu97.

Return to 12: See also Pa71.

Return to 13: See Bu97.

Return to 14: We suspect the only one.

Return to 15: We have seen in the earlier sections that such an interpretation is finitarily sound.

Return to 16: Where denotes the largest natural number lower bound of the rational .

(*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 such that, if is the numeral corresponding to the Gödel number of the PA formula , then is true under the standard interpretation of PA if, and only if, is true (where is the interpretation of 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 of L is defined as satisfied under M if, and only if, its corresponding interpretation, say , holds in M for any assignment of a value that lies within the range of the variable 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 in M, *we can unequivocally decide* whether, or not, holds, or must hold, in M.

The formula of L could also, then, be unequivocally defined as true under the interpretation M if, and only if, were satisfied under M.

Moreover, the formula of L would, further, be definable as true under the interpretation M if, and only if, 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 and of L, respectively, in L, as:

The formula of L is defined as formally satisfied under L if, and only if is provable in L for any term that can be substituted for the variable in .

The formula of L is formally true in L if, and only if, 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 is not provable in L, it would be formally true in L if, and only if, the formula were provable in L for any well-defined term of L that could be substituted for in .

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, , of PA that is, itself, unprovable in a simply consistent PA even though, for any given numeral , the formula 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 of sentences if, whenever PA proves with in S, then is true in the structure 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 be a PA-formula whose Gödel number in Gödel’s notation ^{[10]} is , and let be its standard interpretation over the structure of the natural numbers under which:

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

(b) the integer is the interpretation of the numeral ,

(c) the successor operation (addition of ) is the interpretation of the function (i.e., of ,

(d) ordinary addition and multiplication are the interpretations of and ,

(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 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 ` is a PROVABLE FORMULA of PA’ as:

Bew

However, we can also define the concept ` is a TRUE FORMULA of PA’ in the above notation as (where denotes the prime number):

Tr

In other words, Tr holds if, and only if, for any given sequence of numerals, the PA-formula is PA-provable.

Hence, if Tr holds then interprets as *instantiationally* true under any sound interpretation of PA.

Now Gödel has also shown that there are arithmetical relations and such that:

(i) for any natural number :

(ii) for any natural number sequence :

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!

**The road ahead for the Gödelian argument**

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

**An07b** … 2007. *Why we shouldn’t fault Lucas and Penrose for continuing to believe in the Gödelian argument against computationalism – I.* In *The Reasoner,* Vol(1)6 p3-4.

**An07c** … 2007. *The Reasoner*, Vol(1)7 p2-3.

**An08** … 2008. *Can we really falsify truth by dictat?.* In *The Reasoner*, Vol(2)1 p7-8.

**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 2: See Lu61, Lu03, Lu06 and Pe90, Pe94.

Return to 3: See Theorem VI on p.24 of Go31.

Return to 4: On p.27 of Go31.

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 6: Me64, p.151, Corollary 3.38.

Return to 7: Me64, p.151.

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.

Return to 9: Go31, p.24, Theorem VI.

Return to 10: Go31, p.13.

Return to 11: This definition is excerpted from Me64, p.107.

Return to 12: Go31, p.22 (Dfn.46).

**The significance of Aristotle’s particularisation**

The logic underlying our current interpretations of all first-order formal languages—which are incidentally also intended to provide a firm finitary formal foundation for all computing languages—is Aristotle’s logic of predicates, a fundamental tenet of which is:

**Aristotlean particularisation**: This holds that an assertion such as:

`There exists an such that holds’

—usually denoted symbolically by `‘—can be validly inferred in the classical Aristotlean logic of predicates ^{[1]} from the assertion:

`It is not the case that: for any given , does not hold’

—usually denoted symbolically by `‘.

In this post we shall review various claims that Gödel’s reasoning—concerning the formal undecidability of some arithmetical propositions— can be recast using Rosser’s argument to arrive at Gödel’s intended conclusion without Gödel’s seemingly contrived assumption of -consistency.

We shall then argue that such claims do not stand up to logical scrutiny, since we show that Rosser’s argument appeals to Aristotlean particularisation, which implicitly implies -consistency.

**Gödel and formally undecidable arithmetical propositions**

Now, in his seminal 1931 paper, Kurt Gödel showed that ^{[1]}:

**Lemma** If a Peano Arithmetic P is -consistent, then there is a constructively definable P-formula ^{[3]} such that neither nor are P-provable.

Of course, since every -consistent system is necessarily simply consistent, Gödel’s conclusion is significant only if there is an -consistent language that seeks to formally express all our true propositions about the natural numbers.

The issue of whether there actually *is* an -consistent system of Arithmetic at all appears to have been treated as inconsequential ^{[4]} following J. Barkley Rosser’s 1936 paper ^{[5]}, in which he claimed that Gödel’s reasoning can be recast to arrive at Gödel’s intended result (i.e., construction of a formally undecidable arithmetical proposition in P) by assuming only that P is simply consistent (i.e., without assuming that P is -consistent).

In this paper, we shall analyse various authoritative expositions of Rosser’s argument (including that in Rosser’s original paper), and show first that they all implicitly appeal to Aristotle’s particularisation; and second that such appeal is valid only if P is -consistent.

**The significance of -consistency**

Now classically, under Tarski’s definitions of the satisfaction and truth of the formulas of a first-order language under an interpretation ^{[6]}, the formally defined logical constant `‘ in an occurrence such as `‘—which is formally defined in terms of the primitive (undefined) logical constant `‘ as `‘—may be assumed to *always* appeal to an interpretation such as `There is some such that …’ in any sound interpretation of *any* formal first-order mathematical language without inviting inconsistency ^{[7]}.

In other words:

**Lemma** If the first-order predicate calculus of a first-order mathematical language admits quantification, then any putative classical model of the language may—without inviting inconsistency— interpret existential quantification as Aristotle’s particularisation under Tarski’s definitions of the satisfaction, and truth, of the formulas of a first-order language under an interpretation.

We thus have:

**Lemma** If Aristotle’s particularisation is logically valid, then the standard interpretation of PA is sound (under Tarski’s definitions).

**Lemma** If is sound, then PA is -consistent.

**Expositions of Rosser’s argument are generally sketchy**

Although both Gödel’s proof and Rosser’s argument are complex, and not easy to unravel, the former has been extensively analysed, and its various steps formally validated ^{[8]}, in a number of expositions of Gödel’s number-theoretic reasoning ^{[9]}.

In sharp contrast, Rosser’s widely cited ^{[10]} argument does not appear to have received the same critical scrutiny, and its number-theoretic expositions generally remain either implicit or sketchy ^{[11]}.

**Wang’s outline of Rosser’s argument**

Wang, for instance, states that ^{[12]} from the formal provability of:

(i)

in his formal system of first-order Peano Arithmetic Z, we may infer the formal provability of:

(ii)

However, the inference (ii) from (i) appears to assume that the following deduction is valid for some :

Thus, Wang’s conclusion appears to implicitly assume that Aristotle’s particularisation holds under any sound interpretation of his Peano Arithmetic Z; and, ipso facto, that Z is therefore -consistent.

Although Wang does not explicitly define the interpretation of the formal Z-formula `‘ as `There is some such that ‘, this interpretation appears implicit in his discussion and definition of `‘ in terms of Hilbert’s -function ^{[13]} as a property of the underlying logic of Wang’s Peano Arithmetic Z, and is obvious in the above argument.

In other words Wang implicitly implies that the interpretation of existential quantification cannot be specific to any particular interpretation of a formal mathematical language, but must necessarily be determined by the predicate calculus that is to be applied uniformly to all the mathematical languages in question.

**Beth’s outline of Rosser’s argument**

Similarly, in his outline of a formalisation of Rosser’s argument, Beth implicitly concludes ^{[14]} that from the formal provability of:

(i)

in his formal system of first-order Peano Arithmetic P, we may infer the formal provability of:

(ii)

However, again, the inference (ii) from (i) appears to assume that the following deduction is valid for some :

Thus, Beth’s conclusion, too, appears to implicitly assume that Aristotle’s particularisation is valid under any sound interpretation of his Peano Arithmetic P; and, ipso facto, that P is therefore -consistent.

In this case however, Beth explicitly defines the interpretation of the formal P-formula `‘ as `There is a value of such that …’ ^{[15]}.

Thus Beth, too, implies that the interpretation of existential quantification in formalised axiomatics cannot be specific to any particular interpretation of a formal mathematical language, but must necessarily be determined by the predicate calculus that is to be applied uniformly to all the mathematical languages in question.

**Where Rosser’s argument presumes -consistency**

Now, Rosser’s claim in his `extension’ ^{[16]} of Gödel’s 1931 argument ^{[17]} is that, whereas Gödel’s argument assumes -consistency, Rosser’s assumes only simple consistency.

However, we argue that Rosser’s original argument (also a sketch) implicitly appears to also presume that the system of Peano Arithmetic in question is -consistent.

For instance, the concluding deduction in Rosser’s reasoning ^{[18]} presumes that if, for any given natural number , the formula in Gödel’s Peano Arithmetic P whose Gödel-number is:

is P-provable ^{[19]} under the given premises, we may conclude that, if P is simply consistent, then the P-formula whose Gödel-number is:

is also P-provable.

Rosser essentially seems to reason here that since the P-formula —where is a specific P-numeral—is P-provable for any given P-numeral , we may conclude in this case that—unlike Gödel’s argument concerning a similar conclusion for his `undecidable’ proposition—the P-formula is P-provable.

It is difficult to see how Rosser can make this inference without implicitly presuming either Aristotle’s particularisation or that P is -consistent.

**Mendelson’s formal espression of Rosser’s argument**

I consider next Mendelson’s more rigorous proof ^{[20]} of Rosser’s argument and highlight where it too implicitly presumes that P is -consistent.

Now, Gödel ^{[21]} defines a primitive recursive relation that holds if, and only if, is the Gödel-number of a well-formed P-formula ^{[22]}, say , which has a single free variable and where is the Gödel-number of a P-proof of .

So, for any natural numbers :

(a) holds if, and only if, is the Gödel-number of a P-proof of .

Rosser’s argument defines an additional primitive recursive relation, , which holds if, and only if, is the Gödel-number of , and is the Gödel-number of a P-proof of .

Hence, for any natural numbers :

(b) holds if, and only if, is the Gödel-number of a P-proof of .

Further, it follows from Gödel’s Theorems V ^{[23]} and VII ^{[24]} that the primitive recursive relations and are instantiationally equivalent to some arithmetical relations, and , such that, for any natural numbers :

(c) If holds, then is P-provable;

(d) If holds, then is P-provable;

(e) If holds, then is P-provable;

(f) If holds, then is P-provable;

Now, whilst Gödel defines as , Rosser’s argument defines as .

Further, whereas Gödel considers the P-provability of the Gödelian proposition, , Rosser’s argument considers the P-provability of the proposition .

(We note that it is the occurence of the existential quantifier in Rosser’s formula that distinguishes it from Gödel’s. Consequently whereas Gödel’s argument can be expressed entirely within a formal arithmetic that can be presumed -consistent—without appeal to any particular interpretation of quantification—Rosser’s argument must of necessity appeal either to some non-constructive syntactic meta-rule such as Mendelson’s Rule C ^{[25]}, or to the non-constructive semantic Aristotle’s particularisation, for deriving logical consequences from an existentially quantified formula.)

We also note that, by definition:

(i) holds if, and only if, is the Gödel-number of a P-proof of:

;

(ii) holds if, and only if, is the Gödel-number of a P-proof of:

.

**Mendelson’s formal proof of Rosser’s argument**

(a) We assume, first, that is the Gödel-number of some proof sequence in P for the proposition .

Hence is true, and is P-provable.

However, we then have that is P-provable.

Further, by Modus Ponens, we have that is P-provable.

Now, if P is simply consistent, then is not P-provable.

Hence, does not hold for any natural number , and so holds for every natural number .

It follows that is P-provable for every P-numeral .

Hence, is also P-provable—a contradiction.

Hence, is not P-provable if P is simply consistent.

(b) We assume next that is the Gödel-number of some proof-sequence in P for the proposition .

Hence holds, and is P-provable.

However, if P is simply consistent, is not P-provable.

Hence, holds for every natural number , and is P-provable for all P-numerals .

(i) The foregoing implies is P-provable, and we consider the following deduction ^{[26]}:

(1) … *Hypothesis*

(2) … *By 3(b)*

(3) … *From (1), (2)*

(4) … *From (3)*

(ii) From (1)-(4), by the Deduction Theorem, we have that is provable in P for any P-numeral ;

(iii) Now, is P-provable for any P-numeral ;

(iv) Also, is P-provable for any P-numeral .

(v) Hence is P-provable for any P-numeral .

(vi) Hence is P-provable for any P-numeral .

(vii) Hence is P-provable for any P-numeral .

(viii) Now, (vii) contradicts our assumption that is P-provable.

(ix) Hence is not P-provable if P is simply consistent.

However, the claimed contradiction in (viii) *only* follows if we assume that P is -consistent, and *not* if we assume only that P is simply consistent!

**References**

**Be59** Evert W. Beth. 1959. *The Foundations of Mathematics.* Studies in Logic and the Foundations of Mathematics. Edited by L. E. J. Brouwer, E. W. Beth, A. Heyting. 1959. North Holland Publishing Company, Amsterdam.

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

**Br08** L. E. J. Brouwer. 1908. *The Unreliability of the Logical Principles.* English translation in A. Heyting, Ed. L. E. J. Brouwer: Collected Works 1: *Philosophy and Foundations of Mathematics.* Amsterdam: North Holland / New York: American Elsevier (1975): pp. 107-111.

**Ca62** Rudolf Carnap. 1962. *On the use of Hilbert’s -operator in scientific theories.* In *Essays on the Foundations of Mathematics.* Edited by Y. Bar-Hillel, E. I. J. Posnanski, M. O. Rabin, and A. Robinson for The Hebrew University of Jerusalem. 1962. North Holland Publishing Company, Amsterdam: pp.156-164.

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

**HA28** David Hilbert & Wilhelm Ackermann. 1928. *Principles of Mathematical Logic.* Translation of the second edition of the *Grundzüge Der Theoretischen Logik.* 1928. Springer, Berlin. 1950. Chelsea Publishing Company, New York.

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

**Rg87** Hartley Rogers Jr. 1987. *Theory of Recursive Functions and Effective Computability.* MIT Press, Cambridge, Massachusetts.

**Ro36** J. Barkley Rosser. 1936. *Extensions of some Theorems of Gödel and Church.* In M. Davis (ed.). 1965. *The Undecidable.* Raven Press, New York. Reprinted from The Journal of Symbolic Logic. Vol.1. pp.87-91.

**Sh67** Joseph R.\ Shoenfield. 1967. *Mathematical Logic.* Reprinted 2001. A. K. Peters Ltd., Massachusetts.

**Sm92** Raymond M. Smullyan. 1992. *Gödel’s Incompleteness Theorems.* Oxford University Press, Inc., New York.

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

**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 1: HA28, pp.58-59.

Return to 2: Go31, Theorem VI, p.24, p.25(1) & p.26(2).

Return to 3: In his argument, Gödel refers to this formula only by its `Gödel’ number `‘; Go31, p.25, Eqn.(12).

Return to 4: See, for instance, Be59, p.595; Wa63, p.19 (Theorem 3) & p.25; Me64, p.144; Sh67, p.132 (Incompleteness Theorem); EC89, p.215; BBJ03, p.224 (Gödel’s first incompleteness theorem).

Return to 5: Ro36.

Return to 6: Ta33.

Return to 7: See, for instance, Me64, p.52(ii).

Return to 8: Possibly because Gödel’s remarkably self-contained 1931 paper—it neither contained, nor needed, any formal citations—remains unsurpassed in mathematical literature for thoroughness, clarity, transparency and soundness of exposition.

Return to 9: For instance Me64, p.143; EC89, p.210-211.

Return to 10: Be59, pp.393-395 (which focuses on Rosser’s argument, and treats Gödel’s proof of his Theorem VI (Go31, p.24) as a secondary, weaker result); Wa63, p.337; Me64, pp.144-147; Sh67, p.232 (interestingly, this introductory text contains *no* reference to Gödel or to his 1931 paper!); EC89, p.215; Sm92, p.81; BBJ03, p.226 (this introductory text, too, focuses on Rosser’s argument, and treats Gödel’s argument as more of a historical curiosity!).

Return to 11: See Be59, p.593-595; Wa63, p.337; Sh67, p.232; Rg87, p.98; EC89, p.217, Ex.2; Sm92, p.81; BBJ03, p.226.

Return to 12: Wa63, p.337.

Return to 13: Wa63, p.315(2.31); see also p.10 & pp.443-445.

Return to 14: Be59, p.594 (ij).

Return to 15: Be59, p.178.

Return to 16: Ro36.

Return to 17: Go31.

Return to 18: Ro36, p.234.

Return to 19: Notation (due to Gödel): By `P-provable’ we mean provable from the axioms of P and an arbitrary class, , of P-formulas—including the case where is empty—by the rules of deduction of P.

Return to 20: Me64, p.145, Proposition 3.32.

Return to 21: Go31, p.24, 8.1.

Return to 22: Of his formally defined Peano Arithmetic P.

Return to 23: Go31, p.22.

Return to 24: Go31, p.29.

Return to 25: Me64, p.73, §7.

Return to 26: cf. Me64, p.146.

## Recent comments