The significance of evidence-based reasoning for Computational Complexity

Why primality is polynomial time, but factorisation is not

Differentiating between the signature of a number and its value

A brief review: The significance of evidence-based reasoning

In a paper: `The truth assignments that differentiate human reasoning from mechanistic reasoning: The evidence-based argument for Lucas’ Gödelian thesis’, which appeared in the December 2016 issue of Cognitive Systems Research [An16], I briefly addressed the philosophical challenge that arises when an intelligence—whether human or mechanistic—accepts arithmetical propositions as true under an interpretation—either axiomatically or on the basis of subjective self-evidence—without any specified methodology for objectively evidencing such acceptance in the sense of Chetan Murthy and Martin Löb:

“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 …” … Chetan. R. Murthy: [Mu91], \S 1 Introduction.

“Intuitively we require that for each event-describing sentence, say (i.e. the concrete object denoted by exhibits the property expressed by ), there shall be an algorithm (depending on I, i.e. ) to decide the truth or falsity of that sentence.” … Martin H Löb: [Lob59], p.165.

Definition 1 (Evidence-based reasoning in Arithmetic): Evidence-based reasoning accepts arithmetical propositions as true under an interpretation if, and only if, there is some specified methodology for objectively evidencing such acceptance.

The significance of introducing evidence-based reasoning for assigning truth values to the formulas of a first-order Peano Arithmetic, such as PA, under a well-defined interpretation (see Section 3 in [An16]), is that it admits the distinction:

(1) algorithmically verifiable `truth’ (Definition 2}); and

(2) algorithmically computable `truth’ (Definition 3).

Definition 2 (Deterministic algorithm): A deterministic algorithm computes a mathematical function which has a unique value for any input in its domain, and the algorithm is a process that produces this particular value as output.

Note that a deterministic algorithm can be suitably defined as a `realizer‘ in the sense of the Brouwer-Heyting-Kolmogorov rules (see [Ba16], p.5).

For instance, under evidence-based reasoning the formula of the first-order Peano Arithmetic PA must always be interpreted weakly under the classical, standard, interpretation of PA (see [An16], Theorem 5.6) in terms of algorithmic verifiability (see [An16], Definition 1); where, if the PA-formula interprets as an arithmetical relation over :

Definition 2 (Algorithmic verifiability): The number-theoretical relation is algorithmically verifiable if, and only if, for any natural number , there is a deterministic algorithm which can provide evidence for deciding the truth/falsity of each proposition in the finite sequence .

Whereas must always be interpreted strongly under the finitary interpretation of PA (see [An16], Theorem 6.7) in terms of algorithmic computability ([An16], Definition 2), where:

Definition 3 (Algorithmic computability): The number theoretical relation is algorithmically computable if, and only if, there is a deterministic algorithm that can provide evidence for deciding the truth/falsity of each proposition in the denumerable sequence .

The significance of the distinction between algorithmically computable reasoning based on algorithmically computable truth, and algorithmically verifiable reasoning based on algorithmically verifiable truth, is that it admits the following, hitherto unsuspected, consequences:

(i) PA has two well-defined interpretations over the domain of the natural numbers (including ):

(a) the weak non-finitary standard interpretation ([An16], Theorem 5.6),

and

(b) a strong finitary interpretation ([An16], Theorem 6.7);

(ii) PA is non-finitarily consistent under ([An16], Theorem 5.7);

(iii) PA is finitarily consistent under ([An16], Theorem 6.8).

The significance of evidence-based reasoning for Computational Complexity

In this investigation I now show the relevance of evidence-based reasoning, and of distinguishing between algorithmically verifiable and algorithmically computable number-theoretic functions (as defined above), for Computational Complexity is that it assures us a formal foundation for placing in perspective, and complementing, an uncomfortably counter-intuitive entailment in number theory—Theorem 2 below—which has been treated by conventional wisdom as sufficient for concluding that the prime divisors of an integer cannot be proven to be mutually independent.

However, I show there that such informally perceived barriers are, in this instance, illusory; and that admitting the above distinction illustrates:

(a) Why the prime divisors of an integer are mutually independent Theorem 2;

(b) Why determining whether the signature (Definition 3 below) of a given integer —coded as the key in a modified Bazeries-cylinder (see Definition 7 of this paper) based combination lock—is that of a prime, or not, can be done in polynomial time (Corollary 4 of this paper); as compared to the time given by Agrawal et al in [AKS04], and improved to by Lenstra and Pomerance in [LP11], for determining whether the value of a given integer is that of a prime or not.

(c) Why it can be cogently argued that determining a factor of a given integer cannot be polynomial time.

Definition 4 (Signature of a number): The signature of a given integer is the sequence where for all primes .

Unique since, if and have the same signature, then ; whence since for by appeal to Bertrand’s Postulate ; and the uniqueness is easily verified for .

Definition 5 (Value of a number): The value of a given integer is any well-defined interpretation—over the domain of the natural numbers—of the (unique) numeral that represents in the first-order Peano Arithmetic PA.

We note that Theorem 2 establishes a lower limit for [AKS04] and [LP11], because determining the signature of a given integer does not require knowledge of the value of the integer as defined by the Fundamental Theorem of Arithmetic.

Theorem 1: (Fundamental Theorem of Arithmetic): Every positive integer can be represented in exactly one way as a product of prime powers:

where are primes and the are positive integers (including ).

Are the prime divisors of an integer mutually independent?

In this paper I address the query:

Query 1: Are the prime divisors of an integer mutually independent?

Definition 6 (Independent events): Two events are independent if the occurrence of one event does not influence (and is not influenced by) the occurrence of the other.

Intuitively, the prime divisors of an integer seem to be mutually independent by virtue of the Fundamental Theorem of Arithmetic

Moreover, the prime divisors of can also be seen to be mutually independent in the usual, linearly displayed, Sieve of Eratosthenes, where whether an integer is crossed out as a multiple of a prime is obviously independent of whether it is also crossed out as a multiple of a prime :

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 …

Despite such compelling evidence, conventional wisdom appears to accept as definitive the counter-intuitive conclusion that although we can see it as true, we cannot mathematically prove the following proposition as true:

Proposition 1: Whether or not a prime divides an integer is independent of whether or not a prime divides the integer .

We note that such an unprovable-but-intuitively-true conclusion makes a stronger assumption than that in Gödel’s similar claim for his arithmetical formula —whose Gödel-number is —in [Go31], p.26(2). Stronger, since Gödel does not assume his proposition to be intuitively true, but shows that though the arithmetical formula with Gödel-number is not provable in his Peano Arithmetic yet, for any -numeral , the formula whose Gödel-number is is -provable, and therefore meta-mathematically true under any well-defined Tarskian interpretation of (cf., [An16], Section 3.).

Expressed in computational terms (see [An16], Corollary 8.3), under any well-defined interpretation of , Gödel’s formula translates as an arithmetical relation, say , such that is algorithmically verifiable, but not algorithmically computable, as always true over , since is -provable ([An16], Corollary 8.2).

We thus argue that a perspective which denies Proposition 1 is based on perceived barriers that reflect, and are peculiar to, only the argument that:

Theorem 2: There is no deterministic algorithm that, for any given , and any given prime , will evidence that the probability that divides is , and the probability that does not divide is .

Proof By a standard result in the Theory of Numbers ([Ste02], Chapter 2, p.9, Theorem 2.1, we cannot define a probability function for the probability that a random is prime over the probability space .

(Compare with the informal argument in [HL23], pp.36-37.)

In other words, treating Theorem 2 as an absolute barrier does not admit the possibility—which has consequences for the resolution of outstanding problems in both the theory of numbers and computational complexity—that Proposition 1 is algorithmically verifiable, but not algorithmically computable, as true, since:

Theorem 3: For any given , there is a deterministic algorithm that, given any prime , will evidence that the probability that divides is , and the probability that does not divide is .

Author’s working archives & abstracts of investigations

Can Gödel be held guilty of implicit obfuscation?

Can Gödel be held responsible for not clearly distinguishing—in his seminal 1931 paper on formally undecidable propositions (pp.596-616, ‘From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931‘, Jean van Heijenoort, Harvard University Press, 1976 printing)—between the implicit circularity that is masked by the non-constructive nature of his proof of undecidability in PM, and the lack of any circularity in his finitary proof of undecidability in Peano Arithmetic?

“The analogy of this argument with the Richard antinomy leaps to the eye. It is closely related to the “Liar” too;[Fn.14] for the undecidable proposition states that belongs to , that is, by (1), that is not provable. We therefore have before us a proposition that says about itself that it is not provable [in PM].[Fn.15] …

[Fn.14] Any epistemological antinomycould be used for a similar proof of the existence of undecidable propositions.”

[Fn.15] Contrary to appearances, such a proposition involves no faulty circularity, for initially it [only] asserts that a certain well-defined formula (namely, the one obtained from the th formula in the lexicographic order by a certain substitution) is unprovable. Only subsequently (and so to speak by chance) does it turn out that this formula is precisely the one by which the proposition itself was expressed.”

It is a question worth asking, if we heed Abel-Luis Peralta, who is a Graduate in Scientific Calculus and Computer Science in the Faculty of Exact Sciences at the National University of La Plata in Buenos Aires, Argentina; and who has been contending in a number of posts on his Academia web-page that:

(i) Gödel’s semantic definition of ‘‘, and therefore of ‘‘, is not only:

(a) self-referential under interpretation—in the sense of the above quote (pp.597-598, van Heijenoort) from Gödel’s Introduction in his 1931 paper ‘On Formally Undecidable Propositions of Principia Mathematica and Related Systems I’ (pp.596-616, van Heijenoort);

but that:

(b) neither of the definitions can be verified by a deterministic Turing machine as yielding a valid formula of PM.

Peralta is, of course, absolutely right in his contentions.

However, such non-constructiveness is a characteristic of any set-theoretical system in which PM is interpretable; and in which, by Gödel’s self-confessed Platonism (apparent in his footnote #15 in the quote above), we do not need to establish that his definitions of ‘‘ and ‘‘ need to be verifiable by a deterministic Turing machine in order to be treated as valid formulas of PM.

Reason: By the usual axiom of separation of any formal set theory such as ZFC in which PM is interpreted, Gödel’s set-theoretical definition (p.598, Heijenoort):

lends legitimacy to as a PM formula.

Thus Gödel can formally assume—without further proof, by appeal simply to the axiom of choice of ZFC—that the PM formulas with exactly one variable—of the type of natural numbers—can be well-ordered in a sequence in some way such as, for example (Fn.11, p.598, Heijenoort):

“… by increasing the sum of the finite sequences of integers that is the ‘class sign’;, and lexicographically for equal sums.”

We cannot, though, conclude from this that:

(ii) Gödel’s formally undecidable P-formula, say —whose Gödel-number is defined as in Gödel’s proof of his Theorem VI (on pp.607-609 of van Heijenoort)—also cannot be verified by a deterministic Turing machine to be a valid formula of Gödel’s Peano Arithmetic P.

Reason: The axioms of set-theoretical systems such as PM, ZF, etc. would all admit—under a well-defined interpretation, if any—infinite elements, in the putative domain of any such interpretation, which are not Turing-definable.

Nevertheless, to be fair to two generations of scholars who—apart from those who are able to comfortably wear the logician’s hat—have laboured in attempts to place the philosophical underpinnings of Gödel’s reasoning (in his 1931 paper) in a coherent perspective (see this post; also this and this), I think Gödel must, to some extent, be held responsible—but in no way accountable—for the lack of a clear-cut distinction between the non-constructivity implicit in his semantic proof in (i), and the finitarity that he explicitly ensures for his syntactic proof in (ii).

Reason: Neither in his title, nor elsewhere in his paper, does Gödel categorically state that his goal was:

(iii) not only to demonstrate the existence of formally undecidable propositions in PM, a system which admits non-finitary elements under any putative interpretation;

(iv) but also to prevent the admittance of non-finitary elements—precisely those which would admit conclusions such as (ii)—when demonstrating the existence of formally undecidable propositions in ‘related’ systems such as his Peano Arithmetic P.

He merely hints at this by stating (see quote below from pp.587-589 of van Heijenoort) that his demonstration of (iii) is a ‘sketch’ that lacked the precision which he intended to achieve in (iv):

“Before going into details, we shall first sketch the main idea of the proof, of course without any claim to complete precision. The formulas of a formal system (we restrict ourselves here to the system PM) in outward appearance are finite sequences of primitive signs (variables, logical constants, and parentheses or punctuation dots), and it is easy to state with complete precision which sequences of primitive signs are meaningful formulas and which are not….

by:

(v) weakening the implicit assumption—of the decidability of the semantic truth of PM-propositions under any well-defined interpretation of PM—which underlies his proof of the existence of formally undecidable set-theoretical propositions in PM;

The method of proof just explained can clearly be applied to any formal system that, first, when interpreted as representing a system of notions and propositions, has at its disposal sufficient means of expression to define the notions occurring in the argument above (in particular, the notion “provable formula”) and in which, second, every provable formula is true in the interpretation considered. The purpose of carrying out the above proof with full precision in what follows is, among other things, to replace the second of the assumptions just mentioned by a purely formal and much weaker one.”

and:

(vi) insisting—in his proof of the existence of formally undecidable arithmetical propositions in his Peano Arithmetic P—upon the introduction of a methodology for constructively assigning unique truth values to only those (primitive recursive) quantified number-theoretic assertions (#1 to #45 on pp.603-606 of van Heijenoort) that are bounded when interpreted over the domain N of the natural numbers (footnote #34 on p.603 of van Heijenoort):

“Wherever one of the signs , , or occurs in the definitions below, it is followed by a bound on . This bound serves merely to ensure that the notion defined is recursive (see Theorem IV). But in most cases the extension of the notion defined would not change if this bound were omitted.”

From today’s perspective, one could reasonably hold that—as Peralta implicitly contends—Gödel is misleadingly suggesting (in the initial quote above from pp.587-589 of van Heijenoort) that his definitions of ‘‘ and ‘‘ may be treated as yielding ‘meaningful’ formulas of PM which are well-definable constructively (in the sense of being definable by a deterministic Turing machine).

In my previous post I detailed precisely why such an assumption would be fragile, by showing how the introduction of the boundedness Gödel insisted upon in (vi) distinguishes:

(vii) Gödel’s semantic proof of the existence of formally undecidable set-theoretical propositions in PM (pp.598-599 of van Heijenoort), which admits Peralta’s contention (1);

from:

(viii) Gödel’s syntactic proof of the existence of formally undecidable arithmetical propositions in the language of his Peano Arithmetic P (pp.607-609 of van Heijenoort), which does not admit the corresponding contention (ii).

Moreover, we note that:

(1) Whereas Gödel can—albeit non-constructively—claim that his definition of ‘‘ yields a formula in PM, we cannot claim, correspondingly, that his primitive recursive formula is a formula in his Peano Arithmetic P.

(2) The latter is a number-theoretic relation defined by Gödel in terms of his primitive recursive relation #45, ‘‘, as:

#46. .

(3) In Gödel’s terminology, ‘‘ translates under interpretation over the domain N of the natural numbers as:

‘ is the Gödel-number of some provable formula of Gödel’s Peano Arithmetic P’.

(4) However, unlike Gödel’s primitive recursive functions and relations #1 to #45, both ‘‘ and ‘‘ are number-theoretic relations which are not primitive recursive—which means that they are not effectively decidable by a Turing machine under interpretation in N.

(5) Reason: Unlike in Gödel’s definitions #1 to #45 (see footnote #34 on p.603 of van Heijenoort, quoted above), there is no bound on the quantifier ‘‘ in the definition of .

Hence, by Turing’s Halting Theorem, we cannot claim—in the absence of specific proof to the contrary—that there must be some deterministic Turing machine which will determine whether or not, for any given natural number , the assertion is true under interpretation in N.

This is the crucial difference between Gödel’s semantic proof of the existence of formally undecidable set-theoretical propositions in PM (which admits Peralta’s contention (i)), and Gödel’s syntactic proof of the existence of formally undecidable arithmetical propositions in the language of his Peano Arithmetic P (which does not admit his contention (i)).

(6) We cannot, therefore—in the absence of specific proof to the contrary—claim by Gödel’s Theorems V or VII that there must be some P-formula, say [Bew (corresponding to the PM-formula ), such that, for any given natural number :

(a) If is true under interpretation in N, then [Bew is provable in P;

(b) If is true under interpretation in N, then [Bew is provable in P.

Author’s working archives & abstracts of investigations

Why Gödel’s Theorem VI of his 1931 paper on formally undecidable sentences does not yield a contradiction in any formal mathematical language, or when interpreted in any language of common discourse

A: Is Gödel’s reasoning really kosher?

Many scholars yet harbour a lingering suspicion that Gödel’s definition of his formally undecidable arithmetical proposition involves a latent contradiction—arising from a putative, implicit, circular self-reference—that is masked by unverifiable, even if not patently invalid, mathematical reasoning.

The following proof of Gödel’s Theorem VI of his 1931 paper is intended to:

strip away the usual mathematical jargon that shrouds proofs of Gödel’s argument which makes his—admittedly arcane—reasoning difficult for a non-logician to unravel;

and

show that, and why—unlike in the case of the paradoxical ‘Liar’ sentence: ‘This sentence is a lie’—Gödel’s proposition does not involve any circular self-reference that could yield a Liar-like contradiction, either in a formal mathematical language, or when interpreted in any language of common discourse.

B: Gödel’s 45 primitive recursive arithmetic functions and relations

We begin by noting that:

(1) In his 1931 paper on formally ‘undecidable’ arithmetical propositions, Gödel shows that, given a well-defined system of Gödel-numbering, every formula of a first-order Peano Arithmetic such as PA can be Gödel-numbered by Gödel’s primitive recursive relation #23, , which is true if, and only if, is the Gödel-number (GN) of a formula of PA.

(2) So, given any natural number , (1) allows us to decompose and effectively determine whether, or not, is the GN of some PA formula.

(3) Gödel also defines a primitive recursive relation #44, , which is true if, and only if, is the GN of a finite sequence of formulas in PA, each of which is either an axiom, or an immediate consequence of two preceding formulas in the sequence.

(4) So, given any natural number , (3) allows us to effectively determine whether, or not, the natural number is the GN of a proof sequence in PA.

(5) Further, Gödel defines a primitive recursive relation #45, , which is true if, and only if, is the GN of a proof sequence in PA whose last formula has the GN .

(6) Gödel then defines a primitive recursive relation, say , such that, for any :

is true if, and only if, happens to be a GN that can be decomposed into a proof sequence whose last member is some PA formula , and happens to be a GN that decomposes into the PA-formula with only one variable .

(7) The essence of Gödel’s Theorem VI lies in answering the question:

Query 1: Is there any natural number for which is true?

C: Gödel’s reasoning in Peano Arithmetic

(8) Now, by Gödel’s Theorem VII (a standard representation theorem of arithmetic), can be expressed in PA by some (formally well-defined) formula such that, for any :

(a) If is true, then is PA-provable;

(b) If is true, then is PA-provable.

(9) Further, by (6) and (8), for any , if is the GN of then:

(a) If is true, then is PA-provable; and is a PA-proof of ;

(b) If is true, then is PA-provable; and is not a PA-proof of .

(10) In his Theorem VI, Gödel then argues as follows:

(a) Let be the GN of the formula defined in (8).

(b) Let be the GN of .

(c) Let be the GN of .

(d) Let be the GN of .

(11) We note that all the above primitive recursive relations are formally well-defined within the standard primitive recursive arithmetic PRA; and all the PA-formulas—as well as their corresponding Gödel-numbers—are well-defined in the first-order Peano Arithmetic PA.

In other words, as Gödel emphasised in his paper, the 46—i.e., —PRA functions and relations that he defines are all bounded, and therefore effectively decidable as true or false over the domain of the natural numbers; whilst the PA-formulas that he defines do not involve any reference—or self-reference—to either the meaning or the truth/falsity of any PA-formulas under an interpretation in , but only to their PA-provability which, he shows, is effectively decidable by his system of Gödel-numbering and his definition of the primitive recursive relation .

(12) If we now substitute for , and for , in (9) we have (since is the GN of ) that:

(i) If is true, then is PA-provable; whence is a PA-proof of ;

(ii) If is true, then is PA-provable; whence is not a PA-proof of .

Hence answers Query 1 affirmatively.

D: Gödel’s conclusions

(13) Gödel then concludes that, if PA is consistent then:

By (12)(i), if is true for some , then both and are PA-provable—a contradiction since, by Generalisation in PA, the latter implies that is provable in PA.

Hence , whose GN is , is not provable in PA if PA is consistent.

(14) Moreover, if PA is assumed to also be -consistent (which means that we cannot have a PA-provable formula such that is also provable in PA for any given numeral ) then:

By (13), is not a PA-proof of for any given ; whence is PA-provable for any given by (12)(ii).

Hence , whose GN is , is not provable in PA.

E: Gödel’s does not refer to itself

We note that Gödel’s formula —whose GN is — does not refer to itself since it is defined in terms of the natural number , and not in terms of the natural number .

F: Somewhere, far beyond Gödel

The consequences of Gödel’s path-breaking answer to Query 1 are far-reaching (as detailed in this thesis).

For instance, taken together with the proof that PA is categorical with respect to algorithmic computability (Corollary 7.2 of this paper), and that PA is not -consistent (Corollary 8.4 of this paper), the above entails that:

There can be no interpretation of Gödel’s definition of his formally undecidable arithmetical proposition over the domain of the natural numbers—whether expressed mathematically or in any language of common discourse—that could lead to a contradiction;

Gödel’s is not a formally undecidable arithmetical proposition, since is PA-provable (see Corollary 8.2 of this paper).

Author’s working archives & abstracts of investigations

Why Gödel’s ‘undecidable’ formula does not assert its own unprovability

(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‘:

‘The Truth Assignments That Differentiate Human Reasoning From Mechanistic Reasoning: The evidence-based argument for Lucas’ Gödelian thesis‘.

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

Author’s working archives & abstracts of investigations

The enduring evolution of logic

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

Ferguson’s and Priest’s thesis

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

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

Ferguson and Priest conclude their review by remarking that:

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

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

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

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

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

A struggle reflected so eloquently in this nineteenth century quote:

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

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

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

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

Making sense of mathematical propositions about infinite processes

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

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

The Liar paradox

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

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

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

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

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

Gödel’s influence on Turing’s reasoning

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

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

‘The Truth Assignments That Differentiate Human Reasoning From Mechanistic Reasoning: The evidence-based argument for Lucas’ Gödelian thesis‘.

What is logic: using Ockham’s razor

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

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

‘Algorithmically Verifiable Logic vis à vis Algorithmically Computable Logic: Could resolving EPR need two complementary Logics?‘

where I introduced the definition:

A finite set of rules is a Logic of a formal mathematical language if, and only if, constructively assigns unique truth-values:

(a) Of provability/unprovability to the formulas of ; and

(b) Of truth/falsity to the sentences of the Theory which is defined semantically by the -interpretation of over a structure .

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

Equate the provable formulas of the first order Peano Arithmetic PA with the PA formulas that can be evidenced as `true’ under an algorithmically computable interpretation of PA over the structure of the natural numbers;

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

Interpret such representations unambiguously; and

Conclude further:

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

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

Author’s working archives & abstracts of investigations

Does AI pose an existential threat to mankind?

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

A Economist: The return of the machinery question

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

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

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

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

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

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

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

C Justifying irrationality

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

D Differentiating between Human reasoning and Mechanistic reasoning

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

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

‘The Truth Assignments That Differentiate Human Reasoning From Mechanistic Reasoning‘.

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

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

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

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

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

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

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

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

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

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

Author’s working archives & abstracts of investigations

Can Primes yield a heuristic model of quantum behaviour?

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

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

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

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

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

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

3. The significance of such accountability for mathematics

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

(i) Algorithmic verifiability

A number-theoretical relation 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 .

(ii) Algorithmic computability

A number theoretical relation is algorithmically computable if, and only if, there is an algorithm that can provide objective evidence for deciding the truth/falsity of each proposition in the denumerable sequence .

(iii) Algorithmic verifiability vis à vis algorithmic computability

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

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

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

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

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

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

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

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

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

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

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

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

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

7. Such representation does not need to admit multiverses

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

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

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

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

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

10. Two prime probabilities

We consider the two probabilities:

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

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

(ii) The probability of determining a proper factor of a given number .

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

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

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

However if is the set of all integers, and we cannot define a precise ratio of primes to composites in , but only an order of magnitude such as , then equally obviously cannot be defined in (see Chapter 2, p.9, Theorem 2.1, here).

12. The prime divisors of a natural number are independent

Now, the following paper proves , since it shows that whether or not a prime divides a given integer is independent of whether or not a prime divides :

Why Integer Factorising cannot be polynomial time

We thus have that , with a binomial standard deviation.

Hence, even though we cannot define the probability of selecting a number from the set of all natural numbers that has the property of being prime, can be treated as the putative non-heuristic probability that a given is a prime.

13. The distribution of primes is a quantum phenomena

The distribution of primes is thus determinate but unpredictable, since it is representable by the algorithmically verifiable but not algorithmically computable arithmetical number-theoretic function , where is the ‘th prime.

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

Moreover, although the distribution of primes is a quantum phenomena with probabilty , it is easily seen (see Figs. 7-11 on pp.23-26 of this preprint) that the generation of the primes is algorithmically computable.

14. Why the universe may be algorithmically computable

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

Author’s working archives & abstracts of investigations

Can we think about the infinite in a consistent way, and would such a concept be helpful?

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

A. A mathematical physicist’s conception of thinking about infinity in consistent ways

John Baez is a mathematical physicist, currently working at the math department at U. C. Riverside in California, and also at the Centre for Quantum Technologies in Singapore.

Baez is not only academically active in the areas of network theory and information theory, but also socially active in promoting and supporting the Azimuth Project, which is a platform for scientists, engineers and mathematicians to collaboratively do something about the global ecological crisis.

In a recent post—Large Countable Ordinals (Part 1)—on the Azimuth Blog, Baez confesses to a passionate urge to write a series of blogs—that might even eventually yield a book—about the infinite, reflecting both his fascination with, and frustration at, the challenges involved in formally denoting and talking meaningfully about different sizes of infinity:

“I love the infinite. … It may not exist in the physical world, but we can set up rules to think about it in consistent ways, and then it’s a helpful concept. … Cantor’s realization that there are different sizes of infinity is … part of the everyday bread and butter of mathematics.”

B. Why thinking about infinity in a consistent way must be constrained by an objective, evidence-based, perspective

I would cautiously submit however that (as I briefly argue in this blogpost), before committing to any such venture, whether we can think about the “different sizes of infinity” in “consistent ways“, and to what extent such a concept is “helpful“, are issues that may need to be addressed from an objective, evidence-based, computational perspective in addition to the conventional self-evident, intuition-based, classical perspective towards formal axiomatic theories.

C. Why we cannot conflate the behaviour of Goodstein’s sequence in Arithmetic with its behaviour in Set Theory

Let me suggest why by briefly reviewing—albeit unusually—the usual argument of Goodstein’s Theorem (see here) that every Goodstein sequence over the natural numbers must terminate finitely.

1. The Goodstein sequence over the natural numbers

First, let , be the terms of the Goodstein sequence for over the domain of the natural numbers, where is the base in which the hereditary representation of the ‘th term of the sequence is expressed.

Some properties of Goodstein’s sequence over the natural numbers

We note that, for any natural number , R. L. Goodstein uses the properties of the hereditary representation of to construct a sequence of natural numbers by an unusual, but valid, algorithm.

Hereditary representation: The representation of a number as a sum of powers of a base , followed by expression of each of the exponents as a sum of powers of , etc., until the process stops. For example, we may express the hereditary representations of in base and base as follows:

We shall ignore the peculiar manner of constructing the individual members of the Goodstein sequence, since these are not germane to understanding the essence of Goodstein’s argument. We need simply accept for now that is well-defined over the structure of the natural numbers, and has, for instance, the following properties:

If we replace the base in each term of the sequence by , we arrive at a corresponding sequence of, say, Goodstein’s functions for over the domain of the natural numbers.

Where, for instance:

It is fairly straightforward (see here) to show that, for all :

Either , or .

Clearly terminates in if, and only if, there is a natural number such that, for any , we have either that or that .

However, since we cannot, equally clearly, immediately conclude from the axioms of the first-order Peano Arithmetic PA that such a must exist merely from the definition of the sequence in , we cannot immediately conclude from the above argument that must terminate finitely in .

2. The Goodstein sequence over the finite ordinal numbers

Second, let , be the terms of the Goodstein sequence over the domain of the finite ordinal numbers , where is Cantor’s least transfinite ordinal.

If we replace the base in each term of the sequence by , where ranges over all ordinals upto , it is again fairly straightforward to show that:

Either , or .

Clearly, in this case too, terminates in if, and only if, there is an ordinal such that, for all finite , we have either that , or that .

3. Goodstein’s argument over the transfinite ordinal numbers

If we, however, let then—since the ZF axioms do not admit an infinite descending set of ordinals—it now immediately follows that we cannot have:

for all .

Hence must terminate finitely in , since we must have that for some finite .

4. The intuitive justification for Goodstein’s Theorem

The intuitive justification—which must implicitly underlie any formal argument—for Goodstein’s Theorem then is that, since the finite ordinals can be meta-mathematically seen to be in a correspondence with the natural numbers, we can conclude from (2) above that every Goodstein sequence over the natural numbers must also terminate finitely.

5. The fallacy in Goodstein’s argument

The fallacy in this conclusion is exposed if we note that, by (2), must terminate finitely in even if did not terminate in !

6. Why we need to heed Skolem’s cautionary remarks

Clearly, if we heed Skolem’s cautionary remarks (reproduced here) about unrestrictedly corresponding conclusions concerning elements of different formal systems, then we can validly only conclude that the relationship of ‘terminating finitely’ with respect to the ordinal inequality ‘‘ over an infinite set of finite ordinals in any putative interpretation of a first order Ordinal Arithmetic cannot be obviously corresponded to the relationship of ‘terminating finitely’ with respect to the natural number inequality ‘‘ over an infinite set of natural numbers in any interpretation of PA.

7. The significance of Skolem’s qualification

The significance of Skolem’s qualification is highlighted if we note that we cannot force PA to admit a constant denoting a ‘completed infinity’, such as Cantor’s least ordinal , into either PA or into any interpretation of PA without inviting inconsistency.

(The proof is detailed in Theorem 4.1 on p.7 of this preprint. See also this blogpage).

8. PA is finitarily consistent

Moreover, the following paper, due to appear in the December 2016 issue of Cognitive Systems Research, gives a finitary proof of consistency for the first-order Peano Arithmetic PA:

The truth assignments that differentiate human reasoning from mechanistic reasoning: The evidence-based argument for Lucas’ Gödelian thesis.

9. Why ZF cannot have an evidence-based interpretation

It also follows from the above-cited CSR paper that ZF axiomatically postulates the existence of an infinite set which cannot be evidenced as true even under any putative interpretation of ZF.

10. The appropriate conclusion of Goodstein’s argument

So, if a ‘completed infinity’ cannot be introduced as a constant into PA, or as an element into the domain of any interpretation of PA, without inviting inconsistency, it would follow in Russell’s colourful phraseology that the appropriate conclusion to be drawn from Goodstein’s argument is that:

(i) 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;

(ii) 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 notional interest.

Which raises the issue not only of whether we can think about the different sizes of infinity in a consistent way, but also to what extent we may need to justify that such a concept is helpful to an emerging student of mathematics.

Author’s working archives & abstracts of investigations

The Unexplained Intellect

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

The Brains blog

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

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

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

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

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

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

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

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

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 Truth Assignments That Differentiate Human Reasoning From Mechanistic Reasoning: The Evidence-Based Argument for Lucas’ Goedelian Thesis’

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:

‘Algorithmically Verifiable Logic vis `a vis Algorithmically Computable Logic: Could resolving EPR need two complementary Logics?‘

(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):

‘Why Hilbert’s and Brouwer’s interpretations of quantification are complementary and not contradictory.’

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

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

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

Author’s working archives & abstracts of investigations

Bridging the Finite-Infinite Divide?

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

A new proof?

An interesting review by Natalie Wolchover on May 24, 2016, in the on-line magazine Quanta, reports that:

“With a surprising new proof, two young mathematicians have found a bridge across the finite-infinite divide, helping at the same time to map this strange boundary.

The boundary does not pass between some huge finite number and the next, infinitely large one. Rather, it separates two kinds of mathematical statements: ‘finitistic’ ones, which can be proved without invoking the concept of infinity, and ‘infinitistic’ ones, which rest on the assumption — not evident in nature — that infinite objects exist.”

More concretely:

“In the new proof, Keita Yokoyama, 34, a mathematician at the Japan Advanced Institute of Science and Technology, and Ludovic Patey, 27, a computer scientist from Paris Diderot University, pin down the logical strength of — but not at a level most people expected. The theorem is ostensibly a statement about infinite objects. And yet, Yokoyama and Patey found that it is ‘finitistically reducible’: It’s equivalent in strength to a system of logic that does not invoke infinity. This result means that the infinite apparatus in can be wielded to prove new facts in finitistic mathematics, forming a surprising bridge between the finite and the infinite.”

The proof appeals to properties of transfinite ordinals

My immediate reservation—after a brief glance at the formal definitions in 1.6 on p.6 of the Yokoyama-Patey paper—was that the domain of the structure in which the formal result is proved necessarily contains at least Cantor’s smallest transfinite ordinal , whereas the result is apparently sought to be ‘finitistically reducible’ (as considered by Stephen G. Simpson in an absorbing survey of Partial Realizations of Hilbert’s Program), in the sense of being not only finitarily provable, but interpretable in, and applicable to, finite structures (such as that of the natural numbers) whose domains may not contain (nor, in some cases, even admit—see Theorem 1 in 4.1 of this post) an infinite ‘number’.

Prima facie, the implicit assumption here (see also this post) seems to reflect, for instance, the conventional wisdom that every proposition which is formally provable about the finite, set-theoretically defined ordinals (necessarily assumed consistent with an axiom of infinity), must necessarily interpret as a true proposition about the natural numbers.

Why we cannot ignore Skolem’s cautionary remarks

In this conventional wisdom—by terming it as Skolem’s Paradox—both accepts and implicitly justifies ignoring Thoraf Skolem’s cautionary remarks about unrestrictedly corresponding putative mathematical relations and entities across domains of different axiom systems.

(Thoralf Skolem. 1922. Some remarks on axiomatized set theory. Text of an address delivered in Helsinki before the Fifth Congress of Scandinavian Mathematicians, 4-7 August 1922. In Jean van Heijenoort. 1967. Ed. From Frege to Gödel: A source book in Mathematical Logic, 1878 – 1931. Harvard University Press, Cambridge, Massachusetts.)

However, that the assumption is fragile is seen since, without such an assumption, we can only conclude from, say, Goodstein’s argument that a Goodstein sequence defined over the finite ZF ordinals must terminate finitely even if the corresponding Goodstein sequence over the natural numbers does not terminate (see Theorem 2 of this unpublished investigation)!

(R. L. Goodstein. 1944. On the Restricted Ordinal Theorem. In the Journal of Symbolic Logic 9, 33-41.)

A remarkable exposition of Ramsey’s Theorem

The Yokoyama-Patey proof invites other reservations too.

In a comment—remarkable for its clarity of exposition—academically minded ‘Peter’ illustrates Ramsey’s Theorem as follows:

Something that might help to understand what’s going on here is to start one level lower: Ramsey’s theorem for singletons () says that however you colour the integers with two colours (say red and blue), you are guaranteed to find an infinite monochromatic subset. To see this is true, simply go along the integers starting from and put them into the red or the blue bag according to their colour. Since in each step you increase the size of one or the other bag, without removing anything, you end up with an infinite set. This is a finitistic proof: it never really uses infinity, but it tells you how to construct the first part of the ‘infinite set’.

Now let’s try the standard proof for , pairs. This time we will go along the integers twice, and we will throw away a lot as we go.

The first time, we start at . Because there are infinitely many numbers bigger than , each of which makes a pair with and each of which pairs is coloured either red or blue, there are either infinitely many red pairs with or infinitely many blue pairs (note: this is really using ). I write down under ‘red’ or ‘blue’ depending on which it turned out to be (in case both sets of pairs are infinite, I’ll write red just to break a tie), then I cross out all the numbers bigger than which make the ‘wrong colour’ pair with .

Now I move on to the next number, say , I didn’t cross out, and I look at all the pairs it makes with the un-crossed-out numbers bigger than it. There are still infinitely many, so either the red pairs or the blue pairs form an infinite set (or both). I write down red or blue below as before, and again cross out all the number bigger than which make a wrong colour pair with . And I keep going like this; because everything stays infinite I never get stuck.

After an infinitely long time, I can go back and look at all the numbers which I did not cross out – there is an infinite list of them. Under each is written either ‘red’ or ‘blue’, and if under (say) number the word ‘red’ is written, then forms red pairs with all the un-crossed-out numbers bigger than . Now (using again) either the word ‘red’ or the word ‘blue’ was written infinitely often, so I can pick an infinite set of numbers under which I wrote either always ‘red’ or always ‘blue’. Suppose it was always ‘red’; then if and are any two numbers in the collection I picked, the pair will be red – this is because one of and , say , is smaller, and by construction all the pairs from to bigger un-crossed-out numbers, including , are red. If it were always blue, by the same argument I get an infinite set where all pairs are blue.

What is different here to the first case? The difference is that in order to say whether I should write ‘red’ or ‘blue’ under (or any other number) in the first step, I have to ‘see’ the whole infinite set. I could look at a lot of these numbers and make a guess – but if the guess turns out to be wrong then it means I made a mistake at all the later steps of the process too; everything falls apart. This is not a finitistic proof – according to some logicians, you should be worried that it might somehow be wrong. Most mathematicians will say it is perfectly fine though.

Moving up to , the usual proof is an argument that looks quite a lot like the argument, except that instead of using in the ‘first pass’ it uses . All fine; we believe , so no problem. But now, when you want to write down ‘red’ or ‘blue under in this ‘first pass’ you have to know something more complicated about all the triples using ; you want to know if you can find an infinite set such that any pair in forms a red triple with . If not, tells you that you can find an infinite set such that any pair in forms a _blue_ triple with . Then you would cross off everything not in , and keep going as with . The proof doesn’t really get any harder for the general case (or indeed changing the number of colours to something bigger than ). If you’re happy with infinity, there’s nothing new to see here. If not – well, these proofs have you recursively using more and infinitely more appeals to something infinite as you increase k, which is not a happy place to be in if you don’t like infinity.

Implicit assumptions in Yokoyama-Patey’s argument

Peter’s clarity of exposition makes it easier to see that, in order to support the conclusion that their proof of Ramsey’s Theorem for pairs is ‘finitistically reducible’, Yokoyama-Patey must assume:

(i) that ZFC is consistent, and therefore has a Tarskian interpretation in which the ‘truth’ of a ZFC formula can be evidenced;

(ii) that their result must be capable of an evidence-based Tarskian interpretation over the ‘finitist’ structure of the natural numbers.

As to (i), Peter has already pointed out in his final sentence that there are (serious?) reservations to accepting that the ZF axiom of infinity can have any evidence-based interpretation.

As to (ii), Ramsey’s Theorem is an existensial ZFC formula of the form (whose proof must appeal to an axiom of choice).

Now in ZF (as in any first-order theory that appeals to the standard first-order logic FOL) the formula is merely an abbreviation for the formula .

So, under any consistent ‘finitistically reducible’ interpretation of such a formula, there must be a unique, unequivocal, evidence-based Tarskian interpretation of over the domain of the natural numbers.

Now, if we are to avoid intuitionistic objections to the admitting of ‘unspecified’ natural numbers in the definition of quantification under any evidence-based Tarskian interpretation of a formal system of arithmetic, we are faced with the ambiguity where the questions arise:

(a) Is the to be interpreted constructively as:

For any natural number , there is an algorithm (say, a deterministic Turing machine) which evidences that are all true; or,

(b) is the formula to be interpreted finitarily as:

There is a single algorithm (say, a deterministic Turing machine) which evidences that, for any natural number is true, i.e., each of is true?

As Peter has pointed out in his analysis of Ramsey’s Theorem for pairs, the proof of the Theorem necessitates that:

“I have to ‘see’ the whole infinite set. I could look at a lot of these numbers and make a guess – but if the guess turns out to be wrong then it means I made a mistake at all the later steps of the process too; everything falls apart. This is not a finitistic proof – according to some logicians, you should be worried that it might somehow be wrong.”

In other words, Yokoyama-Patey’s conclusion (that their new proof is ‘finitistically reducible’) would only hold if they have established (b) somewhere in their proof; but a cursory reading of their paper does not suggest this to be the case.

Author’s working archives & abstracts of investigations