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

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

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

The question arises:

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

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

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

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

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

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

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

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

(i) is finitarily consistent; but

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

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

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

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

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

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

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

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

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

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

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

Reason:

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

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

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

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

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

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

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

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

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

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

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

Author’s working archives & abstracts of investigations

The Riemann Hypothesis (see also this paper) reflects the fact that all currently known approximations of the number $\pi(n)$ of primes $\leq n$ are heuristic

All known approximations of the number $\pi(n)$ of primes $\leq n$ are currently derived from real-valued functions that are asymptotic to $\pi(x)$, such as $\frac{x}{log_{e}x}$, $Li(x)$ and Riemann’s function $R(x) = \sum_{n=1}^{\infty}\frac{\mu(n)}{(n)}li(x^{1/n})$, where the degree of approximation for finite values of $n$ is determined only heuristically by conjecturing upon an error term in the asymptotic relation that can be seen’, but not yet proven, to yield good’ approximations of $\pi(n)$ (as described, for instance, by Barry Mazur and William Stein on p.36 of their absorbingly written, but without sacrificing rigour, entry-level book Prime Numbers and the Riemann Hypothesis).

The above graph compares the actual number $\pi(x)$ (red) of primes $\leq x$ with the distribution of primes as estimated variously by the functions $Li(x)$ (blue), $R(x)$ (black), and $\frac{x}{log_{e}x}$ (green), where $R(x)$ is Riemann’s function $\sum_{n=1}^{\infty}\frac{\mu(n)}{(n)}li(x^{1/n})$.

Two non-heuristic approximations of the number $\pi(n)$ of primes $\leq n$

The following introduces, and compares, two non-heuristic prime counting functions (investigated more fully here) that, prima facie, should apparently yield square-root accurate approximations of $\pi(n)$:

(i) $\pi_{_{H}}(n) = \sum_{j=1}^{n}\prod_{i=1}^{\sqrt{n}}(1-\frac{1}{p_{_{i}}}) = n.\prod_{i=1}^{\sqrt{n}}(1-\frac{1}{p_{_{i}}})$ (green); and

(ii) $\pi_{_{L}}(n) = \sum_{j=1}^{n}\prod_{i=1}^{\sqrt{j}}(1-\frac{1}{p_{_{i}}})$ (red);

Based on manual and spreadsheet calculations, Figs.1 and 2 compare the values of the two non-heuristically estimated prime counting functions (both of which have binomial standard deviations) with the actual values of $\pi(n)$ (blue) for $4 \leq n \leq 1500$ and $4 \leq n \leq 3000$.

Fig.1: The above graph compares the non-heuristically estimated values of $\pi_{_{H}}(n) = \sum_{j=1}^{n}\prod_{i=1}^{\sqrt{n}}(1-\frac{1}{p_{_{i}}}) = n.\prod_{i=1}^{\sqrt{n}}(1-\frac{1}{p_{_{i}}})$ (green) and $\pi_{_{L}}(n) = \sum_{j=1}^{n}\prod_{i=1}^{\sqrt{j}}(1-\frac{1}{p_{_{i}}})$ (red) vs the actual values of $\pi(n)$ (blue) for $4 \leq n \leq 1500$.

Fig.2: The above graph compares the non-heuristically estimated values of $\pi_{_{H}}(n) = \sum_{j=1}^{n}\prod_{i=1}^{\sqrt{n}}(1-\frac{1}{p_{_{i}}}) = n.\prod_{i=1}^{\sqrt{n}}(1-\frac{1}{p_{_{i}}})$ (green) and $\pi_{_{L}}(n) = \sum_{j=1}^{n}\prod_{i=1}^{\sqrt{j}}(1-\frac{1}{p_{_{i}}})$ (red) vs the actual values of $\pi(n)$ (blue) for $4 \leq n \leq 3000$. Note that the gradient of both $y = \pi_{_{H}}(x)$ and of $y = \pi_{_{L}}(x)$ in the interval $(p_{_{n}}^{2},\ p_{_{n+1}}^{2})$ is $\prod_{i = 1}^{n}(1 - \frac{1}{p_{_{i}}}) \rightarrow 0$.

Three intriguing queries

Since $\pi(n) \sim \frac{n}{log_{e}(n)}$ (by the Prime Number Theorem), whilst $\pi_{_{H}}(n) \sim 2e^{-\gamma}\frac{n}{log_{_{e}}n}$ (by Mertens’ Theorem, where $\gamma$ is the Euler-Mascheroni constant and $2.e^{-\gamma} \approx 1.12292 \ldots$), and it can be shown (see Corollary 3.2 here)  that $\pi_{_{L}}(n) \sim ae^{-\lambda}\frac{n}{log_{_{e}}n}$ for some $a \geq 2$, this raises the interesting queries (see also $\S$2 of this initial investigation):

Fig.3. The overlapping rectangles $A, B, C, D, \ldots$ represent $\pi_{_{H}}(p_{_{j+1}}^{2}) = p_{_{j+1}}^{2}.\prod_{i = 1}^{j}(1 - \frac{1}{p_{_{i}}})$ for $j \geq 1$. Figures within each rectangle are the primes and estimated primes corresponding to the functions $\pi(n)$ and $\pi_{_{H}}(n)$, respectively, within the interval $(1,\ p_{_{j+1}}^{2})$ for $j \geq 2$.

Fig.4: Graph of $y = \prod_{i = 1}^{\pi(\sqrt{x})}(1 - \frac{1}{p_{_{i}}})$. The rectangles represent $(p_{_{j+1}}^{2} - p_{_{j}}^{2})\prod_{i = 1}^{j}(1 - \frac{1}{p_{_{i}}})$ for $j \geq 1$. Figures within each rectangle are the primes corresponding to the functions $\pi(n)$ and $\pi_{_{L}}(n)$ within the interval $(p_{_{j}}^{2},\ p_{_{j+1}}^{2})$ for $j \geq 2$. The area under the curve is $\pi_{_{L}}(x) = (x - p_{_{n}}^{2})\prod_{i = 1}^{n}(1 - \frac{1}{p_{_{i}}}) + \sum_{j = 1}^{n-1}(p_{_{j+1}}^{2} - p_{_{j}}^{2})\prod_{i = 1}^{j}(1 - \frac{1}{p_{_{i}}}) + 2$.

(a) Which is the least $n$, if any, such that $\pi_{_{H}}(n) > \pi(n)$?

(b) Which is the largest $n$, if any, such that $\pi(n) > \pi_{_{H}}(n)$?

(c) Is $\pi(n) / \frac{n}{log_{_{e}}n}$ an algorithmically verifiable, but not algorithmically computable (see Definitions 1 and 2 here), oscillating function which is discontinuous in the limit $n \rightarrow \infty$ (in the sense of Zeno’s paradox in 2-dimensions considered in Case 4 here)?

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

It is, indeed, gratifying that, after over 50 years of pursuing a path which challenged the accepted textbook wisdom that mathematical truth (which is the basis for asserting that any scientific proposition may be treated as true) is not definable objectively, my contrary contention has been accepted by the editors of the journal ‘Cognitive Systems Research‘ for publication in the December 2016 issue of the Journal. In a sense, this gives closure to the most challenging part of a journey which I have been privileged to afford and endure so far only because of the blessings, indulgence, and support provided by a generation of late elders (my teachers C. B. Nix James and Professor Manohar S. Huzurbazar, parents and mentors), contemporaries, and countless others who gave me the encouragement and strength to continue on such a nebulous path at crucial moments of my life. Defending the thesis promises to be as challenging—albeit far shorter—a journey!

In a paper The Truth Assignments That Differentiate Human Reasoning From Mechanistic Reasoning: The Evidence-Based Argument for Lucas’ Gödelian Thesis, due to appear in the December 2016 issue of Cognitive Systems Research, we briefly consider (Anand [1]) a 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 evidencing such acceptance (for a brief, relatively recent, review of such challenges, see Feferman [2], Feferman [3]).

The ambiguity in the standard interpretation of the Peano Arithmetic PA

For instance conventional wisdom, whilst accepting Tarski’s classical definitions of the satisfiability and truth of the formulas of a formal language under an interpretation (Anand [1], p.44), postulates that under the classical standard interpretation $\mathcal{I}_{PA(\mathbb{N},\ Standard,\ Classical)}$ (we shall refer to this henceforth as $\mathcal{I}_{PA(\mathbb{N},\ S)}$) of the first-order Peano Arithmetic PA (we take this to be the first-order theory defined in any standard text corresponding to the theory S in Mendelson [4], p.102) over the domain $\mathbb{N}$ of the natural numbers:

(i) The satisfiability/truth of the atomic formulas of PA can be assumed as uniquely decidable under $\mathcal{I}_{PA(\mathbb{N},\ S)}$;

(ii) The PA axioms can be assumed to uniquely interpret as satisfied/true under $\mathcal{I}_{PA(\mathbb{N},\ S)}$;

(iii) The PA rules of inference—Generalisation and Modus Ponens—can be assumed to uniquely preserve such satisfaction/truth under $\mathcal{I}_{PA(\mathbb{N},\ S)}$;

(iv) Aristotle’s particularisation can be assumed to hold under $\mathcal{I}_{PA(\mathbb{N},\ S)}$.

We define Aristotle’s particularisation as the non-finitary assumption that an assertion such as, There exists an $x$ such that $F(x)$ holds’—usually denoted symbolically by $(\exists x)F(x)$‘—can always be validly inferred in the classical logic of predicates from the assertion, It is not the case that: for any given $x$, $F(x)$ does not hold’—usually denoted symbolically by $\neg(\forall x)\neg F(x)$‘ (see also Hilbert & Ackermann [5], pp.58-59).

We argue that the seemingly innocent and self-evident assumptions of uniqueness in (i) to (iii)—as also the seemingly innocent assumption in (iv) which, despite being obviously non-finitary, is unquestioningly accepted in classical literature as equally self-evident under any logically unexceptionable interpretation of the classical first-order logic FOL—conceal an ambiguity with far-reaching consequences.

The two, hitherto unsuspected and essentially different, interpretations of PA

The ambiguity is revealed if we note that Tarski’s classic definitions permit both human and mechanistic intelligences to admit finitary evidence-based definitions of the satisfaction and truth of the atomic formulas of PA over the domain $\mathbb{N}$ of the natural numbers in two, hitherto unsuspected and essentially different, ways:

(1a) In terms of classical algorithmic verifiabilty; and

(1b) In terms of finitary algorithmic computability.

By ‘finitary’ we mean that (for a brief review of ‘finitism’ and ‘constructivity’ in the context of this paper see Feferman [3]):

“… there should be an algorithm for deciding the truth or falsity of any mathematical statement”

We show that:

(2a) The two definitions correspond to two distinctly different assignments of satisfaction and truth to the compound formulas of PA over $\mathbb{N}$—say $\mathcal{I}_{PA(\mathbb{N},\ Standard,\ Verifiable)}$ and $\mathcal{I}_{PA(\mathbb{N},\ Standard,\ Computable)}$ (we shall refer to these henceforth as $\mathcal{I}_{PA(\mathbb{N},\ SV)}$ and $\mathcal{I}_{PA(\mathbb{N},\ SC)}$ respectively); where

(2b) The PA axioms are true over $\mathbb{N}$, and the PA rules of inference preserve truth over $\mathbb{N}$, under both $\mathcal{I}_{PA(\mathbb{N},\ SV)}$ and $\mathcal{I}_{PA(\mathbb{N},\ SC)}$.

A finitary proof of consistency for Arithmetic: The solution to Hilbert’s Second Millenium Problem

We then show that:

(3a) If we assume the satisfaction and truth of the compound formulas of PA are always non-finitarily decidable under the assignment $\mathcal{I}_{PA(\mathbb{N},\ SV)}$, then this assignment defines a non-finitary interpretation of PA in which Aristotle’s particularisation always holds over $\mathbb{N}$; and which corresponds to the classical non-finitary standard interpretation $\mathcal{I}_{PA(\mathbb{N},\ S)}$ of PA over the domain $\mathbb{N}$—from which only a human intelligence may non-finitarily conclude (as Gentzen’s argument does) that PA is consistent; whilst

(3b) The satisfaction and truth of the compound formulas of PA are always finitarily decidable under the assignment $\mathcal{I}_{PA(\mathbb{N},\ SC)}$, which thus defines a finitary interpretation of PA—from which both intelligences may finitarily conclude that PA is consistent (as sought by David Hilbert for the second of the twenty three problems that he highlighted at the International Congress of Mathematicians in Paris in 1900; see Hilbert [6]).

PA is categorical and has no non-standard models

We show further that both intelligences would logically conclude that:

(4a) The assignment $\mathcal{I}_{PA(\mathbb{N},\ SC)}$ defines a subset of PA formulas that are algorithmically computable as true under the standard interpretation $\mathcal{I}_{PA(\mathbb{N},\ S)}$ if, and only if, the formulas are PA provable;

(4b) PA is categorical (and so has no non-standard model, as argued in Anand [7]);

We note that the standard argument to the contrary—as detailed, for instance, in Kaye [8] (pp.10-11)—violates finitarity by adding a new constant $c$ to the language $\mathcal{L}_{A}$ of PA that is not definable in $\mathcal{L}_{A}$ and, ipso facto, by adding an atomic formula $[c=x]$ to PA whose satisfaction under any interpretation of PA is not algorithmically verifiable.

However, since the atomic formulas of PA are algorithmically verifiable under the standard interpretation (Theorem 5.1, p. 38, in Anand [1]), the above argument invalidly postulates precisely that which it seeks to prove (as also do arguments in: Boolos, Burgess & Jeffrey [9], p.306, Corollary 25.3; Luna [10], p.7)!

There are no ‘undecidable’ arithmetical propositions: Gödel’s Theorems hold vacuously

Both intelligences would also logically conclude that:

(4c) PA is not $\omega$-consistent.

(5a) Since PA is not $\omega$-consistent, Gödel’s argument in Gödel [11] (p.28(2))—that “$Neg(17Gen r)$ is not $\kappa$-PROVABLE”—does not yield a formally undecidable proposition’ in PA;

The reason we prefer to consider Gödel’s original argument (rather than any of its subsequent avatars) is that, for a purist, Gödel’s remarkably self-contained 1931 paper—it neither contained, nor needed, any formal citations—remains unsurpassed in mathematical literature for thoroughness, clarity, transparency and soundness of exposition—from first principles (thus avoiding any implicit mathematical or philosophical assumptions)—of his notion of arithmetical undecidability’ as based on his Theorems VI and XI and their logical consequences.

We also note that if PA is not $\omega$-consistent, then Aristotle’s particularisation does not hold in any finitary interpretation of PA over $\mathbb{N}$.

Now, J. Barkeley Rosser’s ‘undecidable’ arithmetical proposition in Rosser [12] is of the form $[(\forall y)(Q(h, y) \rightarrow (\exists z)(z \leq y \wedge S(h, z)))]$.

Thus his ‘extension’ of Gödel’s proof of undecidability too does not yield a ‘formally undecidable proposition’ in PA, since it implicitly presumes that Aristotle’s particularisation holds when interpreting $[(\forall y)(Q(h, y) \rightarrow (\exists z)(z \leq y \wedge S(h, z)))]$ under a finitary interpretation over $\mathbb{N}$ (Rosser [12], Theorem II, pp.233-234; Kleene [13], Theorem 29, pp.208-209; Mendelson [4], Proposition 3.32, pp.145-146).

(5b) The appropriate conclusion to be drawn from Gödel’s argument (in Gödel [11], p.27(1))—that “$17Gen r$ is not $\kappa$-PROVABLE”—is thus not that there is a ‘formally undecidable arithmetical proposition’ (see also Feferman [4] for an interesting perspective on how he—as well as, reportedly, both Gödel and Hilbert—informally viewed the concept of ‘formally undecidable arithmetical propositions’) but that any such putatively ‘undecidable arithmetical proposition’ is an instantiation of the argument (corresponding to Cantor’s diagonal argument and Turing’s halting argument) that we can define number-theoretic formulas which are algorithmically verifiable as always true, but not algorithmically computable as always true.

The argument for Lucas’ Gödelian Thesis

We conclude from this that Lucas’ Gödelian argument can validly claim:

Thesis: There can be no mechanist model of human reasoning if the assignment $\mathcal{I}_{PA(\mathbb{N},\ SV)}$ can be treated as circumscribing the ambit of human reasoning about ‘true’ arithmetical propositions, and the assignment $\mathcal{I}_{PA(\mathbb{N},\ SC)}$ can be treated as circumscribing the ambit of mechanistic reasoning about ‘true’ arithmetical propositions.

Although Lucas’ original 1961 thesis (Lucas [14]):

“… we cannot hope ever to produce a machine that will be able to do all that a mind can do: we can never not even in principle, have a mechanical model of the mind.”

deserves consideration that lies beyond the immediate scope of this investigation, we draw attention to his informal 1996 defence of it from a philosophical perspective in Lucas [15], where he concludes with the argument that:

“Thus, though the Gödelian formula is not a very interesting formula to enunciate, the Gödelian argument argues strongly for creativity, first in ruling out any reductionist account of the mind that would show us to be, au fond, necessarily unoriginal automata, and secondly by proving that the conceptual space exists in which it is intelligible to speak of someone’s being creative, without having to hold that he must be either acting at random or else in accordance with an antecedently specifiable rule”.

Argument: Gödel has shown how to construct an arithmetical formula with a single variable—say $[R(x)]$ (Gödel refers to this formula only by its Gödel number $r$ (Gödel [11], p.25(12)))—such that $[R(x)]$ is not PA-provable, but $[R(n)]$ is instantiationally PA-provable for any given PA numeral $[n]$.

Hence, for any given numeral $[n]$, Gödel’s primitive recursive relation $xB \lceil [R(n)] \rceil$ must hold for some natural number $m$ (where $xBy$ denotes Gödel’s primitive recursive relation ‘$x$ is the Gödel-number of a proof sequence in PA whose last term is the PA formula with Gödel-number $y$‘ (Gödel [11], p.22(45)); and $\lceil [R(n)] \rceil$ denotes the Gödel-number of the PA formula $[R(n)]$).

If we assume that any mechanical witness can only reason finitarily then although, for any given numeral $[n]$, a mechanical witness can give evidence under the assignment $\mathcal{I}_{PA(\mathbb{N},\ SC)}$ that the PA formula $[R(n)]$ holds in $\mathbb{N}$, no mechanical witness can conclude finitarily under the assignment $\mathcal{I}_{PA(\mathbb{N},\ SC)}$ that, for any given numeral $[n]$, the PA formula $[R(n)]$ holds in $\mathbb{N}$.

However, if we assume that a human witness can also reason non-finitarily, then a human witness can conclude under the assignment $\mathcal{I}_{PA(\mathbb{N},\ SV)}$ that, for any given numeral $[n]$, the PA formula $[R(n)]$ holds in $\mathbb{N}$.

Bibliography

[1] Bhupinder Singh Anand. 2016. The Truth Assignments That Differentiate Human Reasoning From Mechanistic Reasoning: The Evidence-Based Argument for Lucas’ Gödelian Thesis. To appear in Cognitive Systems Research. Volume 40, December 2016, Pages 35-45, doi:10.1016/j.cogsys.2016.02.004.

[2] Solomon Feferman. 2006. Are There Absolutely Unsolvable Problems? Gödel’s Dichotomy. In Philosophia Mathematica (2006) 14 (2): 134-152.

[3] Solomon Feferman. 2008. Lieber Herr Bernays!, Lieber Herr Gödel! Gödel on finitism, constructivity and Hilbert’s program. In the Special Issue: Gödel’s dialectica Interpretation of Dialectica, Volume 62, Issue 2, June 2008, pp. 245-290.

[4] Elliott Mendelson. 1964. Introduction to Mathematical Logic. Van Norstrand, Princeton.

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

[6] David Hilbert. 1900. Mathematical Problems. An address delivered before the International Congress of Mathematicians at Paris in 1900. Dr. Maby Winton Newson translated this address into English with the author’s permission for the Bulletin of the American Mathematical Society, 8 (1902), 437-479. An HTML version is accessible at http://aleph0.clarku.edu/~djoyce/hilbert/problems.html.

[7] Bhupinder Singh Anand. 2008. Can we really falsify truth by dictat?. In The Reasoner, Vol(2)1 pp. 7-8.

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

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

[10] Laureano Luna. 2008. On non-standard models of Peano Arithmetic. In The Reasoner, Vol(2)2 p. 7.

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

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

[13] Stephen Cole Kleene. 1952. Introduction to Metamathematics. North Holland Publishing Company, Amsterdam.

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

[15] J. R. Lucas. 1996. The Gödelian Argument: Turn Over the Page. A paper read at a BSPS conference in Oxford. Reproduced in 2003 as Series/Report no.: Etica & Politica / Ethics & Politics V (2003) 1, EUT Edizioni Università di Trieste, URI: http://hdl.handle.net/10077/5477.

Author’s working archives & abstracts of investigations

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

$\S 1$ Are there still unsolved problems about the numbers $1, 2, 3, 4, \ldots ?$

In a 2005 Clay Math Institute invited large lecture to a popular audience at MIT ‘Are there still unsolved problems about the numbers $1, 2, 3, 4, \ldots ?$’, co-author with William Stein of Prime Numbers and the Riemann Hypothesis, and Gerhard Gade Harvard University Professor, Barry Mazur remarked that (p.6):

“If I give you a number $N$, say $N$ = one million, and ask you for the first number after $N$ that is prime, is there a method that answers that question without, in some form or other, running through each of the successive numbers after $N$ rejecting the nonprimes until the first prime is encountered? Answer: unknown.”

Although this may represent conventional wisdom, it is not, however, strictly true!

Reason: The following 1964 Theorem yields two algorithms (Trim/Compact), each of which affirmatively answers the questions:

(i) Do we necessarily discover the primes in a Platonic domain of the natural numbers, as is suggested by the sieve of Eratosthenes, or can we also generate them sequentially in a finitarily definable domain that builds into them the property of primality?

(ii) In other words, given the first $k$ primes, can we generate the prime $p(k+1)$ algorithmically, without testing any number larger than $p(k)$ for primality?

I: A PRIME NUMBER GENERATING THEOREM

Theorem: For all $i < k$, let $p(i)$ denote the $i$'th prime, and define $a(i)$ such that:

$a(i) < p(i)$,

and:

$p(k) + a(i) \equiv 0\ (mod\ p(i))$.

Let $d(k)$ be such that, for all $d < d(k)$, there is some $i$ such that:

$d \equiv a(i)\ (mod\ p(i))$.

Then:

$p(k+1) = p(k) + d(k)$.

Proof: For all $d < d(k)$, there is some $i$ such that:

$p(k) + d \equiv 0\ (mod\ p(i))$.

Since $p(k+1) < 2p(k)$:

$d(k) < p(k)$.

Hence:

$p(k) + d(k) < p(k)^{2}$,

and so it is the prime $p(k+1)$.

II: TRIM NUMBERS

The significance of the Prime Number Generating Theorem is seen in the following algorithm.

We define Trim numbers recursively by $t(1) = 2$, and $t(n+1) = t(n) + d(n)$, where $p(i)$ is the $i$‘th prime and:

(1) $d(1) = 1$, and $a(2, 1) = 1$ is the only element in the $2$nd array;

(2) $d(n)$ is the smallest even integer that does not occur in the $n$‘th array $\{a(n, 1), \ldots, a(n, n-1)\}$;

(3) $j$ is selected so that:

$0 \leq a(n+1, i) = (a(n, i) - d(n) + j*p(i) < p(i)$ for all $0 < i \leq (n-1)$.

It follows that the Trim number $t(n+1)$ is, thus, a prime unless all its prime divisors are less than $d(n)$.

The Trim Number Algorithm

$\line(1,0){285}$

n    $t(n)$

1    2           2      3      5      7       11     13      17     19      23      27       29     31   37

$\line(1,0){285}$

2    3            1      $\textit{2}$      5

3    5            1      1      $\textit{2}$      7

4    7            1      2      3      $\textit{4}$       11

5    11           1      1      4      3       $\textit{2}$      13

6    13           1      2      2      1       9      $\textit{4}$       17

7    17           1      1      3      4       5      9       $\textit{2}$      19

8    19           1      2      1      2       3      7       15      $\textit{4}$      23

9    23           1      1      2      5      10      3       11     15      $\textit{4}$       27

10   27          1      0      3      1       6      12       7      11      19       $\textit{2}$        29

11   29           1      1      1      6       4      10       5       9      17                  $\textit{2}$      31

$\ldots$

n    $t(n)$            $r_{_{1}}$     $r_{_{2}}$     $r_{_{3}}$     $r_{_{4}}$      $r_{_{5}}$     $r_{_{6}}$       $r_{_{7}}$     $r_{_{8}}$      $r_{_{9}}$     $r_{_{10}}$       $r_{_{11}}$    …    $\textit{\ldots}$

$\line(1,0){285}$

NOTE: The first $50$ Trim Numbers upto $t(50) = 199$ consist of the first $46$ primes and the $4$ composites:

(i) Trim composite $t(10)$: $27 = 3.3.3$

(ii) Trim composite $t(32)$: $125 = 5.5.5$

(iii) Trim composite $t(37)$: $147 = 3.7.7$

(iv) Trim composite $t(46)$: $189 = 3.3.3.7$

Theorem: For all $n > 1, t(n) < n^{^{2}}$

II A: $k$-TRIM NUMBERS

For any given natural number $k>2$, we define $k$-Trim numbers recursively by $t_k(1) = 2$, and $t_k(n+1) = t_k(n) + d(n)$, where $p(i)$ is the $i$‘th prime and:

(1) $d(1) = 1$, and $a(2, 1) = 1$ is the only element in the $2$nd array;

(2) $d(n)$ is the smallest even integer that does not occur in the $n$‘th array $\{a(n, 1), \ldots, a(n, k-1)\}$;

(3) $j$ is selected so that:

$0 \leq a(n+1, i) = (a(n, i) - d(n) + j*p(i) < p(i)$ for all $0 < i \leq (k-1)$.

It follows that the $k$-Trim number $t_k(n+1)$ is, thus, not divisible by any prime $\leq p(k)$ unless the prime is smaller than $d(n)$.

III: COMPACT NUMBERS

Compact numbers are defined recursively by $c(1) = 2$, and $c(n+1) = c(n) + d(n)$, where $p(i)$ is the $i$‘th prime and:

(1) $d(1) = 1$, and $a(2, 1) = 1$ is the only element in the $2$nd array;

(2) $d(n)$ is the smallest even integer that does not occur in the nth array $\{a(n, 1), \ldots, a(n, k)\}$;

(3) $j$ is selected so that:

$0 \leq a(n+1, i) = (a(n, i) - d(n) + j*p(i) < p(i)$ for all $0 < i \leq k$;

(4) $k$ is selected so that:

$p(k)*p(k) < c(n) \leq p(k+1)*p(k+1)$;

(5) $a(n, k+1) = 0$ if $c(n) = p(k+1)*p(k+1)$.

It follows that the compact number $c(n+1)$ is either a prime, or a prime square, unless all, except a maximum of $1$, prime divisors of the number are less than $d(n)$.

The Compact Number Algorithm

$\line(1,0){285}$

n    $c(n)$

1    2           2      3      5      7       11     13      17     19      23      29       31     37   41

$\line(1,0){285}$

2    3            1      $\textit{2}$      5

3    5            1      $\textit{2}$      7

4    7            1      $\textit{2}$      9

5    9            1      0      $\textit{2}$     11

6    11           1      1      $\textit{2}$    13

7    13           1      2      $\textit{4}$    17

8    17           1      1      $\textit{2}$    19

9    19           1      2      $\textit{4}$     23

10  23           1      1      $\textit{2}$     25

11   25           1      2      0      $\textit{4}$     29

12   29           1      1      1      $\textit{2}$     31

13   31           1      2      4      $\textit{6}$     37

14   37           1      2      3      $\textit{4}$     41

15   41           1      1      4      $\textit{2}$     43

16   43           1      2      2      $\textit{4}$     47

17   47           1      1      3      $\textit{2}$     49

18   49           1      2      1      0      $\textit{4}$      53

19   53           1      1      2      3      $\textit{4}$      57

20   57           1      0      3      6      $\textit{2}$      59

21   59           1      1      1      4      $\textit{2}$      61

22   61           1      2      4      2      $\textit{6}$      67

23   67           1      2      3      3      $\textit{4}$       71

24   71           1      1      4      6      $\textit{2}$       73

25   73           1      2      2      4      $\textit{6}$       79

26   79           1      2      1      5      $\textit{4}$       83

27   83           1      1      2      1      $\textit{4}$       87

28   87           1      0      3      4      $\textit{2}$       89

29   89           1      1      1      2      $\textit{4}$       93

30   93           1      0      2      5      $\textit{4}$       97

31   97           1      2      3      1      $\textit{4}$       101

32   101          1      1      4      4      $\textit{2}$      103

33   103          1      2      2      2      $\textit{4}$      107

34   107          1      1      3      5      $\textit{2}$      109

35   109          1      2      1      3      $\textit{4}$      113

36   113          1      1      2      6      $\textit{4}$       117

37   117          1      0      3      2      $\textit{4}$       121

38   121          1      2      4      5      0       $\textit{6}$       127

39   127          1      2      3      6      5       $\textit{4}$       131

40   131          1      1      4      2      1       $\textit{6}$       137

41   137          1      1      3      3      6       $\textit{2}$       139

42   139          1      2      1      1      4       $\textit{6}$       145

43   145          1      2      0      2      9       $\textit{4}$       149

44   149          1      1      1      5      5       $\textit{2}$       151

45   151          1      2      4      5      0       $\textit{6}$       157

46   157          1      2      3      4      8       $\textit{6}$       163

47   163          1      2      2      5      2       $\textit{4}$       167

48   167          1      1      3      1      9       $\textit{2}$       169

49   169          1      2      1      6      7       0       $\textit{4}$       173

50   173          1      1      2      2      3       9       $\textit{4}$       177

51   177          1      0      3      5      10     5       $\textit{2}$       179

52   179          1      1      1      3      8       3       $\textit{2}$       181

53   181          1      2      4      1      6       1       $\textit{8}$       189

54   189          1      0      1      0      9       6       $\textit{2}$       191

55   191          1      1      4      5      7       4       $\textit{2}$       193

56   193          1      2      2      3      5       2       $\textit{4}$       197

57   197          1      1      3      6      1       11      $\textit{2}$       199

58   199          1      2      1      4      10      9       $\textit{6}$       205

59   205          1      2      0      5      4       3        $\textit{6}$       211

60   211          1      2      4      6      9       10      $\textit{8}$       219

61   219          1      0      1      5      1       2        $\textit{4}$       223

62   223          1      2      2      1      8       11       $\textit{4}$       227

63   227          1      1      3      4      4       7        $\textit{2}$       229

64   229          1      2      1      2      2       5        $\textit{4}$       233

65   233          1      1      2      5      9       14      $\textit{4}$       237

66   237          1      0      3      1      5       10      $\textit{2}$       239

67   239          1      1      1      6      3       8        $\textit{2}$       241

68   241          1      2      4      4      1       6        $\textit{8}$       249

69   249          1      0      1      3      4       11      $\textit{2}$       251

70   251          1      1      4      1      2       9        $\textit{6}$       257

71   257          1      1      3      2      7       3        $\textit{4}$       261

72   261          1      0      4      5      3       12      $\textit{2}$       263

73   263          1      1      2      3      1       10      $\textit{4}$       267

74   267          1      0      3      6      8       6        $\textit{2}$       269

75   269          1      1      1      4      6       4        $\textit{2}$       271

76   271          1      2      4      2      4       2        $\textit{6}$       277

77   277          1      2      3      3      9       9        $\textit{4}$       281

78   281          1      1      4      6      5       5        $\textit{2}$       283

79   283          1      2      2      4      3       3        $\textit{6}$       289

$\ldots$

n     $c(n)$            $r_{_{1}}$     $r_{_{2}}$     $r_{_{3}}$     $r_{_{4}}$      $r_{_{5}}$     $r_{_{6}}$       $r_{_{7}}$     $r_{_{8}}$       $r_{_{9}}$     $r_{_{10}}$       $r_{_{11}}$    …

$\line(1,0){285}$

NOTE: The first $79$ Compact Numbers upto $c(79) = 283$ consist of the first $61$ primes, $5$ prime squares, and $13$ composites.

Theorem 1: There is always a Compact Number $c(m)$ such that $n^{^{2}} < c(m) \leq (n+1)^{^{2}}$.

Theorem 2: For sufficiently large $n,\ d(n) < constant.\frac{\sqrt{c(n)}}{log_{_{e}}c(n)}$.

$\S 2$ A 2-dimensional Eratosthenes sieve

A later investigation (see also this post) shows why the usual, linearly displayed, Eratosthenes sieve argument reveals the structure of divisibility (and, ipso facto, of primality) more transparently when displayed as the 1964, $2$-dimensional matrix, representation of the residues $r_{i}(n)$, defined for all $n \geq 2$ and all $i \geq 2$ by:

$n + r_{i}(n) \equiv 0\ (mod\ i)$, where $i > r_{i}(n) \geq 0$.

Density‘: For instance, the residues $r_{_{i}}(n)$ can be defined for all $n \geq 1$ as the values of the non-terminating sequences $Ri (n) = \{i-1, i-2, \ldots, 0, i-1, i-2, \ldots, 0, \ldots\}$, defined for all $i \geq 1$ (as illustrated below in Fig.1).

Fig.1

$\line(1,0){285}$

Sequence    $R_{_{1}}$    $R_{_{2}}$    $R_{_{3}}$    $R_{_{4}}$    $R_{_{5}}$    $R_{_{6}}$    $R_{_{7}}$    $R_{_{8}}$    $R_{_{9}}$    $R_{_{10}}$    $R_{_{11}}$     …    $R_{_{n}}$

$\line(1,0){285}$

n=1                $\textbf{0}$      1      2      3       4      5       6      7      8       9       10      …    n-1

n=2                0      $\textbf{0}$      1      2       3      4       5      6      7       8        9       …    n-2

n=3                0      1      $\textbf{0}$      1       2      3       4      5      6       7        8       …    n-3

n=4                0      0      2      $\textbf{0}$       1      2       3      4      5       6        7       …    n-4

n=5                0      1      1      3       $\textbf{0}$      1       2      3      4       5        6       …    n-5

n=6                0      0      0      2       4      $\textbf{0}$       1      2      3       4        5       …    n-6

n=7                0      1      2      1       3      5       $\textbf{0}$      1      2       3        4       …    n-7

n=8                0      0      1      0       2      4       6      $\textbf{0}$      1       2        3       …    n-8

n=9                0      1      0      3       1      3       5      7      $\textbf{0}$       1        2       …    n-9

n=10               0      0      2      2       0      2       4      6      8       $\textbf{0}$        1       …    n-10

n=11               0      1      1      1       4      1       3      5      7       9        $\textbf{0}$       …    n-11

$\ldots$

n                     $r_{_{1}}$     $r_{_{2}}$    $r_{_{3}}$     $r_{_{4}}$      $r_{_{5}}$     $r_{_{6}}$     $r_{_{7}}$     $r_{_{8}}$     $r_{_{9}}$    $r_{_{10}}$      $r_{_{11}}$     …    $\textbf{0}$

$\line(1,0){285}$

We note that:

$\bullet$ For any $i \geq 2$, the non-terminating sequence $R_{_{i}}(n)$ cycles through the values $(i-1, i-2, \ldots 0)$ with period $i$;

$\bullet$ For any $i \geq 2$ the ‘density’—over the set of natural numbers—of the set $\{n\}$ of integers that are divisible by $i$ is $\frac{1}{i}$; and the ‘density’ of integers that are not divisible by $i$ is $\frac{i-1}{i}$.

Primality: The residues $r_{_{i}}(n)$ can be alternatively defined for all $i \geq 1$ as values of the non-terminating sequences, $E(n) = \{r_{_{i}}(n) : i \geq 1\}$, defined for all $n \geq 1$ (as illustrated below in Fig.2).

Fig.2

$\line(1,0){285}$

Sequence    $R_{_{1}}$    $R_{_{2}}$    $R_{_{3}}$    $R_{_{4}}$    $R_{_{5}}$    $R_{_{6}}$    $R_{_{7}}$    $R_{_{8}}$    $R_{_{9}}$    $R_{_{10}}$    $R_{_{11}}$     …    $R_{_{n}}$

$\line(1,0){285}$

$E(1)$             $\textbf{0}$      1      2      3       4      5       6      7      8       9       10      …    n-1

$\textbf{E(2)}$             0      $\textbf{0}$      1      2       3      4       5      6      7       8        9       …    n-2

$\textbf{E(3)}$             0      1      $\textbf{0}$      1       2      3       4      5      6       7        8       …    n-3

$\textit{E(4)}$              0      0      2      $\textbf{0}$       1      2       3      4      5       6        7       …    n-4

$\textbf{E(5)}$             0      1      1      3       $\textbf{0}$      1       2      3      4       5        6       …    n-5

$\textit{E(6)}$              0      0      0      2       4      $\textbf{0}$       1      2      3       4        5       …    n-6

$\textbf{E(7)}$             0      1      2      1       3      5       $\textbf{0}$      1      2       3        4       …    n-7

$\textit{E(8)}$              0      0      1      0       2      4       6      $\textbf{0}$      1       2        3       …    n-8

$\textit{E(9)}$              0      1      0      3       1      3       5      7      $\textbf{0}$       1        2       …    n-9

$\textit{E(10)}$             0      0      2      2       0      2       4      6      8       $\textbf{0}$        1       …    n-10

$\textbf{E(11)}$            0      1      1      1       4      1       3      5      7       9        $\textbf{0}$       …    n-11

$\ldots$

$E(n)$               $r_{_{1}}$     $r_{_{2}}$    $r_{_{3}}$     $r_{_{4}}$      $r_{_{5}}$     $r_{_{6}}$     $r_{_{7}}$     $r_{_{8}}$     $r_{_{9}}$    $r_{_{10}}$      $r_{_{11}}$     …    $\textbf{0}$

$\line(1,0){285}$

We note that:

$\bullet$ The non-terminating sequences $\textbf{E(n)}$ highlighted in bold correspond to a prime $p$ (since $r_{_{i}}(p) \neq 0$ for any $1 < i < p$) in the usual, linearly displayed, Eratosthenes sieve:

$E(1), \textbf{E(2)}, \textbf{E(3)}, \textit{E(4)}, \textbf{E(5)}, \textit{E(6)}, \textbf{E(7)}, \textit{E(8)}, \textit{E(9)}, \textit{E(10)}, \textbf{E(11)}, \ldots$

$\bullet$ The non-terminating sequences $\textit{E(n)}$ highlighted in italics identify a crossed out composite $n$ (since $r_{_{i}}(n) = 0$ for some $1 < i < n$) in the usual, linearly displayed, Eratosthenes sieve.

The significance of expressing Eratosthenes sieve as a $2$-dimensional matrix

Fig.1 illustrates that although the probability $P(a)$ of selecting a number that has the property of being prime from a given set $S$ of numbers is definable if the precise proportion of primes to non-primes in $S$ is definable, if $S$ is the set $N$ of all integers, and we cannot define a precise ratio of primes to composites in $N$, but only an order of magnitude such as $O(\frac{1}{log_{_{e}}n})$, then equally obviously $P(a) = P(n\ is\ a\ prime)$ cannot be defined in $N$ (see Chapter 2, p.9, Theorem 2.1, here).

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

Fig.2 illustrates, however, that the probability $P(b)$ of determining a proper factor of a given number $n$ is $\frac{1}{\pi(\sqrt{n})}$, since this paper shows that whether or not a prime $p$ divides a given integer $n$ is independent of whether or not a prime $q \neq p$ divides $n$.

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

The putative non-heuristic probability that a given $n$ is a prime

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

$\S 3$ “What sort of Hypothesis is the Riemann Hypothesis?”

The significance of the above perspective is that (see this investigation) it admits non-heuristic approximations of prime counting functions with what appear to be (see Fig.15 of the investigation) square root accurate errors, where:

“It has long been known that that for any real number $X$ the number of prime numbers less than $X$ (denoted $\pi(X))$ is approximately $X/ log X$ in the sense that the ratio $\frac{\pi(X)}{X/ log X}$ tends to $1$ as $X$ goes to infinity. The Riemann Hypothesis would give us a much more accurate “count” for $\pi(X)$ in that it will offer a specific smooth function $R(X)$ (hardly any more difficult to describe than $X/ log X$) and then conjecture that $R(X)$ is an essentially square root accurate approximation to $\pi(X)$; i.e., for any given exponent greater than $1/2$ (you choose it: $0.501,\ 0.5001,\ 0.50001$, for example) and for large enough $X$ where the phrase “large enough” depends on your choice of exponent the error term i.e., the difference between $R(X)$ and the number of primes less than $X$ in absolute value is less than $X$ raised to that exponent (e.g. $< X^{0.501}, < X^{0.5001}$, etc.)"

This argument laid the foundation for this investigation. See also this arXiv preprint, and this broader update.

Abstract We define the residues $r_{i}(n)$ for all $n \geq 2$ and all $i \geq 2$ such that $r_{i}(n) = 0$ if, and only if, $i$ is a divisor of $n$. We then show that the joint probability $\mathbb{P}(p_{i} | n\ \cap\ p_{j} | n)$ of two unequal primes $p_{i},\ p_{j}$ dividing any integer $n$ is the product $\mathbb{P}(p_{i} | n).\mathbb{P}(p_{j} | n)$. We conclude that the prime divisors of any integer $n$ are independent; and that the probability $\mathbb{P}(n \in \{p\})$ of $n$ being a prime $p$ is $\prod_{i = 1}^{\sqrt{n}}(1 - 1/p_{i}) \sim 2e^{-\gamma}/log_{e}\ n$. The number of primes less than or equal to $n$ is thus given by $\pi(n) \approx \sum_{j = 1}^{n}\prod_{i = 1}^{\pi(\sqrt{j})}(1 - 1/p_{i})$. We further show that $((\pi(x).log_{e}\ x)/x)' = o(1/x)$, and conclude that $(\pi(x).log_{e}\ x)/x$ does not oscillate.

$\S 1$ The residues $r_{i}(n)$

We begin by defining the residues $r_{i}(n)$ for all $n \geq 2$ and all $i \geq 2$ as below:

Definition 1: $n + r_{i}(n) \equiv 0\ (mod\ i)$ where $i > r_{i}(n) \geq 0$.

Since each residue $r_{i}(n)$ cycles over the $i$ values $(i-1, i-2, \ldots, 0)$, these values are all incongruent and form a complete system of residues [1] $mod\ i$.

It immediately follows that:

Lemma 1: $r_{i}(n) = 0$ if, and only if, $i$ is a divisor of $n$.

$\S 2$ The probability $\mathbb{P}(e)$

By the standard definition of the probability $\mathbb{P}(e)$ of an event $e$, we conclude that:

Lemma 2: For any $n \geq 2,\ i \geq 2$ and any given integer $i > u \geq 0$, the probability $\mathbb{P}(r_{i}(n) = u)$ that $r_{i}(n) = u$ is $1/i$, and the probability $\mathbb{P}(r_{i}(n) \neq u)$ that $r_{i}(n) \neq u$ is $1 - 1/i$.

We note the standard definition:

Definition 2: Two events $e_{i}$ and $e_{j}$ are mutually independent for $i \neq j$ if, and only if, $\mathbb{P}(e_{i}\ \cap\ e_{j}) = \mathbb{P}(e_{i}).\mathbb{P}(e_{j})$.

$\S 3$ The prime divisors of any integer $n$ are mutually independent

We then have that:

Lemma 3: If $p_{i}$ and $p_{j}$ are two primes where $i \neq j$ then, for any $n \geq 2$, we have:

$\mathbb{P}((r_{p_{_{i}}}(n) = u) \cap (r_{p_{_{j}}}(n) = v)) = \mathbb{P}(r_{p_{_{i}}}(n) = u).\mathbb{P}(r_{p_{_{j}}}(n) = v)$

where $p_{i} > u \geq 0$ and $p_{j} > v \geq 0$.

Proof: The $p_{i}.p_{j}$ numbers $v.p_{i} + u.p_{j}$, where $p_{i} > u \geq 0$ and $p_{j} > v \geq 0$, are all incongruent and form a complete system of residues [2] $mod\ (p_{i}.p_{j})$. Hence:

$\mathbb{P}((r_{p_{_{i}}}(n) = u) \cap (r_{p_{_{j}}}(n) = v)) = 1/p_{i}.p_{j}$.

By Lemma 2:

$\mathbb{P}(r_{p_{_{i}}}(n) = u).\mathbb{P}(r_{p_{_{j}}}(n) = v) = (1/p_{i})(1/p_{j})$.

The lemma follows. $\Box$

If $u = 0$ and $v = 0$ in Lemma 3, so that both $p_{i}$ and $p_{j}$ are prime divisors of $n$, we conclude by Definition 2 that:

Corollary 1: $\mathbb{P}((r_{p_{_{i}}}(n) = 0) \cap (r_{p_{_{j}}}(n) = 0)) = \mathbb{P}(r_{p_{_{i}}}(n) = 0).\mathbb{P}(r_{p_{_{j}}}(n) = 0)$.

Corollary 2: $\mathbb{P}(p_{i} | n\ \cap\ p_{j} | n) = \mathbb{P}(p_{i} | n).\mathbb{P}(p_{j} | n)$.

Theorem 1: The prime divisors of any integer $n$ are mutually independent. [3]

$\S 4$ The probability that $n$ is a prime

Since $n$ is a prime if, and only if, it is not divisible by any prime $p \leq \sqrt{n}$, it follows immediately from Lemma 2 and Lemma 3 that:

Lemma 4: For any $n \geq 2$, the probability $\mathbb{P}(n \in \{p\})$ of an integer $n$ being a prime $p$ is the probability that $r_{p_{_{i}}}(n) \neq 0$ for any $1 \leq i \leq k$ if $p_{k}^{2} \leq n < p_{k+1}^{2}$. $\Box$

Lemma 5: $\mathbb{P}(n \in \{p\}) = \prod_{i = 1}^{\pi(\sqrt{n})}(1 - 1/p_{i}) \sim 2e^{-\gamma}/log_{e}\ n$ [4]. $\Box$

$\S 5$ The Prime Number Theorem

The number of primes less than or equal to $n$ is thus given by:

Lemma 6: $\pi(n) \approx \sum_{j = 1}^{n}\prod_{i = 1}^{\pi(\sqrt{j})}(1 - 1/p_{i})$. $\Box$

This now yields the Prime Number Theorem:

Theorem 2: $\pi(x) \sim x/log_{e}\ x$.

Proof: From Lemma 6 and Mertens’ Theorem that
[5]:

$\prod_{p \leq x}(1 - 1/p_{i}) = e^{o(1)}.e^{-\gamma}/log_{e}\ x$

it follows that:

$(\pi(n).log_{e}\ n)/n \approx (log_{e}\ n/n)\sum_{j = 1}^{n}\prod_{i = 1}^{\pi(\sqrt{j})}(1 - 1/p_{i})$

$(\pi(n).log_{e}\ n)/n \approx (log_{e}\ n/n)\sum_{j = 1}^{n}(2.e^{o(1)}.e^{-\gamma})/log_{e}\ n$

$(\pi(x).log_{e}\ x)/x \sim c.(log_{e}\ x/x)\int_{2}^{x}(1/log_{e}\ t).dt$

$(\pi(x).log_{e}\ x)/x \sim c.(log_{e}\ x/x)[log_{e}.log_{e}\ t + log_{e}\ t + \sum_{2}^{\infty}(log_{e}\ t)^{k}/(k. k!)]_{2}^{^{x}}$

$(\pi(x).log_{e}\ x)/x \sim c.(log_{e}\ x/x)[log_{e}.log_{e}\ x + log_{e}\ x + \sum_{2}^{\infty}(log_{e}\ x)^{k}/(k. k!)]$

$(\pi(x).log_{e}\ x)/x \sim c.(log_{e}\ x/x).f(log_{e}\ x)$

The behaviour of $(\pi(x).log_{e}\ x)/x$ as $x \rightarrow \infty$ is then seen by differentiating the right hand side, where we note that $f(log_{e}\ x)' = 1/log_{e}\ x$:

$(c.(log_{e}\ x/x).f(log_{e}\ x))' = c/x + c.f(log_{e}\ x).(1/x^{2} - log_{e}\ x/x^{2})$

$(c.(log_{e}\ x/x).f(log_{e}\ x))' = c/x + (c.f(log_{e}\ x).(1 - log_{e}\ x))/x^{2}$

$(c.(log_{e}\ x/x).f(log_{e}\ x))' = o(1/x)$

Hence $(\pi(x).log_{e}\ x)/x$ does not oscillate as $x \rightarrow \infty$. $\Box$

Acknowledgements

I am indebted to my erstwhile classmate, Professor Chetan Mehta, for his unqualified encouragement and support for my scholarly pursuits over the past fifty years; most pertinently for his patiently critical insight into the required rigour without which the argument of this 1964 investigation would have remained in the informal universe of seemingly self-evident truths.

References

HW60 G. H. Hardy and E. M. Wright. 1960. An Introduction to the Theory of Numbers 4th edition. Clarendon Press, Oxford.

Ti51 E. C. Titchmarsh. 1951. The Theory of the Riemann Zeta-Function. Clarendon Press, Oxford.

Notes

Return to 3: In the previous post we have shown how it immediately follows from Theorem 1 that integer factorising is necessarily of order $O(n/log_{e}\ n)$; from which we conclude that integer factorising cannot be in the class $P$ of polynomial-time algorithms.

Author’s working archives & abstracts of investigations

This argument laid the foundation for this later post and this investigation.

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

Abstract: We show the joint probability $\mathbb{P}(p_{i} | n\ \cap\ p_{j} | n)$ that two unequal primes $p_{i},\ p_{j}$ divide any integer $n$ is the product $\mathbb{P}(p_{i} | n).\mathbb{P}(p_{j} | n)$. We conclude that the prime divisors of any integer $n$ are independent; and that Integer Factorising is necessarily of the order $O(n/log_{e}\ n)$.

$\S 1$ The residues $r_{i}(n)$

We define the residues $r_{i}(n)$ for all $n \geq 2$ and all $i \geq 2$ as below:

Definition 1: $n + r_{i}(n) \equiv 0\ (mod\ i)$ where $i > r_{i}(n) \geq 0$.

Since each residue $r_{i}(n)$ cycles over the $i$ values $(i-1, i-2, \ldots, 0)$, these values are all incongruent and form a complete system of residues [1] $mod\ i$.

We note that:

Lemma 1: $r_{i}(n) = 0$ if, and only if, $i$ is a divisor of $n$.

$\S 2$ The probability $\mathbb{P}(e)$

By the standard definition of the probability [2] $\mathbb{P}(e)$ of an event $e$, we then have that:

Lemma 2: For any $n \geq 2,\ i \geq 2$ and any given integer $i > u \geq 0$, the probability $\mathbb{P}(r_{i}(n) = u)$ that $r_{i}(n) = u$ is $1/i$, and the probability $\mathbb{P}(r_{i}(n) \neq u)$ that $r_{i}(n) \neq u$ is $1 - 1/i$.

We note the standard definition [3]:

Definition 2: Two events $e_{i}$ and $e_{j}$ are mutually independent for $i \neq j$ if, and only if, $\mathbb{P}(e_{i}\ \cap\ e_{j}) = \mathbb{P}(e_{i}).\mathbb{P}(e_{j})$.

$\S 3$ The prime divisors of any integer $n$ are mutually independent

We then have that:

Lemma 3: If $p_{i}$ and $p_{j}$ are two primes where $i \neq j$ then, for any $n \geq 2$, we have:

$\mathbb{P}((r_{p_{_{i}}}(n) = u) \cap (r_{p_{_{j}}}(n) = v)) = \mathbb{P}(r_{p_{_{i}}}(n) = u).\mathbb{P}(r_{p_{_{j}}}(n) = v)$

where $p_{i} > u \geq 0$ and $p_{j} > v \geq 0$.

Proof: The $p_{i}.p_{j}$ numbers $v.p_{i} + u.p_{j}$, where $p_{i} > u \geq 0$ and $p_{j} > v \geq 0$, are all incongruent and form a complete system of residues [4] $mod\ (p_{i}.p_{j})$. Hence:

$\mathbb{P}((r_{p_{_{i}}}(n) = u) \cap (r_{p_{_{j}}}(n) = v)) = 1/p_{i}.p_{j}$.

By Lemma 2:

$\mathbb{P}(r_{p_{_{i}}}(n) = u).\mathbb{P}(r_{p_{_{j}}}(n) = v) = (1/p_{i})(1/p_{j})$.

The lemma follows. $\Box$

If $u = 0$ and $v = 0$ in Lemma 3, so that both $p_{i}$ and $p_{j}$ are prime divisors of $n$, we conclude by Definition 2 that:

Corollary 1: $\mathbb{P}((r_{p_{_{i}}}(n) = 0) \cap (r_{p_{_{j}}}(n) = 0)) = \mathbb{P}(r_{p_{_{i}}}(n) = 0).\mathbb{P}(r_{p_{_{j}}}(n) = 0)$.

Corollary 2: $\mathbb{P}(p_{i} | n\ \cap\ p_{j} | n) = \mathbb{P}(p_{i} | n).\mathbb{P}(p_{j} | n)$.

Theorem 1: The prime divisors of any integer $n$ are mutually independent.

Since $n$ is a prime if, and only if, it is not divisible by any prime $p \leq \sqrt{n}$ we may, without any loss of generality, take integer factorising to mean determining at least one prime factor $p \leq \sqrt{n}$ of any given $n \geq 2$.

$\S 4$ Integer Factorising is not in $P$

It then immediately follows from Theorem 1 that:

Corollary 3: Integer Factorising is not in $P$.

Proof: We note that any computational process to identify a prime divisor of $n \geq 2$ must necessarily appeal to a logical operation for identifying such a factor.

Since $n$ may be the square of a prime, it follows from Theorem 1 that we necessarily require at least one logical operation for each prime $p \leq \sqrt{n}$ in order to logically identify a prime divisor of $n$.

Moreover, since the number of such primes is of the order $O(n/log_{e}\ n)$, any deterministic algorithm that always computes a prime factor of $n$ cannot be polynomial-time—i.e. of order $O((log_{e}\ n)^{c})$ for any $c$—in the length of the input $n$.

The corollary follows if $P$ is the set of such polynomial-time algorithms. $\Box$

Acknowledgements

I am indebted to my erstwhile classmate, Professor Chetan Mehta, for his unqualified encouragement and support for my scholarly pursuits over the past fifty years; most pertinently for his patiently critical insight into the required rigour without which the argument of this 1964 investigation would have remained in the informal universe of seemingly self-evident truths.

References

GS97 Charles M. Grinstead and J. Laurie Snell. 1997. Introduction to Probability. Second Revised Edition, 1997, American Mathematical Society, Rhode Island, USA.

HW60 G. H. Hardy and E. M. Wright. 1960. An Introduction to the Theory of Numbers 4th edition. Clarendon Press, Oxford.

Ko56 A. N. Kolmogorov. 1933. Foundations of the Theory of Probability. Second English Edition. Translation edited by Nathan Morrison. 1956. Chelsea Publishing Company, New Yourk.

An05 Bhupinder Singh Anand. 2005. Three Theorems on Modular Sieves that suggest the Prime Difference is $O(\pi(p(n)^{1/2}))$. Private investigation.

Notes

Return to 3: Ko56, Chapter VI, Section 1, Definition 1, pg.57 and Section 2, pg.58; see also GS97, Chapter 4, Section 4.1, Theorem 4.1, pg.140.

Author’s working archives & abstracts of investigations

In this post we shall beg indulgence for wilfully ignoring Wittgenstein’s dictum: “Whereof one cannot speak, thereof one must be silent.”

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

$\S 1$ The Background

In his comments on this earlier post (on the need for a better consensus on the definition of effective computability‘) socio-proctologist Vivek Iyer—who apparently prefers to be known here only through this blogpage, and whose sustained interest has almost compelled a more responsible response in the form of this blogpage—raised an interesting query (albeit obliquely) on whether commonly accepted Social Welfare Functions—such as those based on Muth rationality—could possibly be algorithmically verifiable, but not algorithmically computable:

“We know the mathematical properties of market solutions but assume we can know the Social Welfare Function which brought it about. We have the instantiation and know it is computable but we don’t know the underlying function.”

He later situated the query against the perspective of:

“… the work of Robert Axtell http://scholar.google.com/citations?user=K822uYQAAAAJ&hl=en- who has derived results for the computational complexity class of market (Walrasian) eqbm. This is deterministically computable as a solution for fixed points in exponential time, though easily or instantaneously verifiable (we just check that the market clears by seeing if there is anyone who still wants to sell or buy at the given price). Axtell shows that bilateral trades are complexity class P and this is true of the Subjective probabilities.”

Now, the key para of Robert Axtell’s paper seemed to be:

“The second welfare theorem states that any Pareto optimal allocation is a Walrasian equilibrium from some endowments, and is usually taken to mean that a social planner/society can select the allocation it wishes to achieve and then use tax and related regulatory policy to alter endowments such that subsequent market processes achieve the allocation in question. We have demonstrated above that the job of such a social planner would be very hard indeed, and here we ask whether there might exist a computationally more credible version of the second welfare theorem”…Axtell p.9

Axtell’s aim here seemed to be to maximise in polynomial time the Lyapunov function $V(x(t))$ (given on Axtell p.7; which is a well-defined number-theoretic formula over the real numbers) to within a specific range of its limiting value over a given set of possible endowment allocations.

Distribution of Resources

Prima facie Axtell’s problem seemed to lie within a general class of problems concerning the distribution of finite resources amongst a finite population.

For instance, the total number of ways, say $P(n, k)$ in which any budgeted measure of $n$ discrete endowments can be allocated over $k$ agents is given by the partition function $P(n, k)$ (which I wrongly commented upon as being the factorisation function $F(n, k)$ generated by $\eta_{k}(s)$):

$\prod_{i=1}^{\infty}\frac{1}{(1-ax^{i})} = \sum_{n=1}^{\infty}\sum_{k=1}^{\infty}P(n, k)a^{k}x^{n}$

We noted that if we take one of the allocations $E$ as the equilibrium (ideal/desired destination) distribution, then a general problem of arriving at an ideal Distribution of Resources from a given starting distribution could ask whether there is always a path that is polynomial in $P(n, k)$ and such that, starting from any arbitrary distribution, there is a minimum cost for passing (in the worst case) through all the possible distributions irreversibly (where we assume that it is not feasible under any series of individual rational exchanges for a particular resource distribution over the population to repeat itself with time).

We assumed there that, for any given set of distributions $S_{i}=\{A_{1},\ A_{2},\ \ldots,\ A_{i}\}$ and any $A_{j}$, there is a minimum measure $m_{S_{i}S_{j}}$ which determines the cost of progressing from the set of distributions $A_{i}=\{A_{1},\ A_{2},\ \ldots,\ A_{i}\}$ to the set of distributions $S_{j}=\{A_{1},\ A_{2},\ \ldots,\ A_{j}\}$, where $A_{j}$ is not in $S_{i}=\{A_{1},\ A_{2},\ \ldots,\ A_{i}\}$.

We noted that mathematically the above can be viewed as a variation of the Travelling Salesman problem where the goal is to minimise the total cost of progressing from a starting distribution $A_{1}$ to the ideal distribution $E$, under the influence of free market forces based on individual rational exchanges that are only regulated to ensure—through appropriate taxation and/or other economic tools—that the cost of repeating a distribution is not feasible.

We further noted that, since the Travelling Salesman Problem is in the complexity class $NP$, it would be interesting to identify where exactly Axtell’s problem reduces to the computability complexity class $P$ (and where we ignore, for the moment, the $PvNP$ separation problem raised in this earlier post).

$\S 2$ Defining Market Equilibrium in a Simplified Stock Exchange

In order to get a better perspective on the issue of an equilibrium, we shall now speculate on whether we can reasonably define a market equilibrium in a simplified terminating market situation (i.e., a situation which always ends when there is no possible further profitable activity for any participant), where our definition of an equilibrium is any terminal state of minimum total cost and maximum total gain.

For instance, we could treat the population in question as a simplified on-line Stock Exchange with $k$ speculators $B_{1},\ B_{2},\ \ldots, B_{k}$ and $n$ scrips, where both $k$ and $n$ are fixed.

Now we can represent a distribution $A_{(t)}$ at time $t$ by one of the ways, say $P(n,\ k)$, in which $n$ can be partitioned into $k$ parts as $n = a_{i} + a_{2} + \ldots + a_{k}$, where $a_{i}$ is the number of scrips (mandatorily $\geq 1$) held by speculator $B{i}$ at time $t$ (which can fluctuate freely based on market forces of supply and demand).

We note that the generating function for $P(n,\ k)$ is given by the partition function:

$\prod_{i=1}^{\infty}\frac{1}{(1-ax^{i})} = \sum_{n=1}^{\infty}\sum_{k=1}^{\infty}P(n, k)a^{k}x^{n}$

One could then conceive of a Transaction Corpus Tax ($TCT$) as a cess on each transaction levied by the Regulator (such as India’s SEBI) on the Exchange:

$\bullet$ Where $TCT$ is directly recovered by the Exchange from individual speculators along with an appropriate Transaction Processing Fee ($TPF$) and a periodic Exchange Maintenance Cost ($EMC$); and

$\bullet$ Where, unless the market is in a terminating situation, the maintenance charge $EMC$ is uniformly leviable periodically, even if no transaction has taken place, to ensure that trading activity never halts voluntarily.

Now, given an initial distribution, say $A_{0}$, of the scrips amongst the population $k$, we can assume that any transaction by say speculator $B_{i}$ at time $t_{j}$ would incur a $TCT$ cost $f_{t_{j}}(A_{j},\ A_{j+1})$, plus a $TPF$ and a (possibly discounted) $EMC$.

Obviously the gain to $B_{i}$ must exceed $TCT+TPF+EMC$ for the trade to be a rational one.

However, what is important to note here (which obviously need not apply in dissimilar cases such as Axtell’s) is that apparently none of the following factors:

(a) the price of the scrip being traded at any transaction;

(b) the quantum of the gain (which need not even be quantifiable in any particular transaction);

(c) the quantum of $TPF$ or $EMC$;

seem to play any role in reaching the Equilibrium Distribution $E_{(n,\ k)}$ for the particular set of $k$ speculators $\{B_{1},\ B_{2},\ \ldots,\ B_{k}\}$ and $n$ scrips.

Moreover, the only restriction is on $TCT$, to the effect that:

$f_{t_{i}}(A_{i},\ A_{j}) = \infty$ for any $i$ if $j < i$

In other words, no transaction can take place that requires a distribution to be repeated.

One way of justifying such a Regulatory restriction would be that if a distribution were allowed to repeat itself, a cabal could prevent market equilibrium by artificially fuelling speculation aimed at merely inflating the valuations of the $n$ scrips over a selected distribution.

By definition, starting with any distribution $A_{0}$, it would seem that the above activity must come to a mandatory halt after having passed necessarily through all the possible $P(k,\ n)$ distributions.

If so, this would reduce the above to a Travelling Salesman Problem TSP if we define the Equilibrium Distribution $E_{(n,\ k)}$ as the (not necessarily unique) distribution which minimises the Total Transaction Corpus Tax to speculators in reaching the Equilibrium through all possible distributions.

In other words, the Equilibrium Distribution is—by definition—the one for which $\sum_{i=0}^{P(n,\ k)} f_{t_{i}}(A_{i},\ A_{i+1})$ is a minimum; and is one that can be shown to always exist.

$\S 3$ What do you think (an afterthought)?

Assuming all the speculators $B_{1},\ B_{2},\ \ldots, B_{k}$ agree that their individual profitability can only be assured over a terminating distribution cycle if, and only if, the Total Transaction Corpus Tax $\sum_{i=0}^{P(n,\ k)} f_{t_{i}}(A_{i},\ A_{i+1})$ is minimised (not an unreasonable agreement to seek in a country like India that once had punitive 98% rates of Income Tax), can $E_{(n,\ k)}$ be interpreted as a Nash equilibrium?

In other words, in the worst case where the quantum of Transaction Corpus Tax can be arbitrarily revised and levied with retrospective effect at any transaction, is there a Nash strategy that can guide the set $B_{1},\ B_{2},\ \ldots, B_{k}$ of speculators into ensuring that they eventually arrive at an Equilibrium Distribution $E_{(n,\ k)}$?

References

Ax03 Robert Axtell. 2003. The Complexity of Exchange. In Econometrica, Vol. 29, No. 3 (July 1961).

Mu61 John F. Muth. 1961. Rational Expectations and the Theory of Price Movements. In Econometrica, Vol. 29, No. 3 (July 1961).

Three Dogmas of FOL: Hibertian Theism, Brouwerian Atheism, and Finitary Agnosticism (work in progress as on 10/07/2017)

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

What essentially differentiate our approach of finitary agnosticism to mathematical reasoning in this investigation from both the classical Hilbertian, and the intuitionistic Brouwerian, perspectives is how we address two significant dogmas of the classical first order logic FOL.

Hilbertian Theism

In a 1925 address[1] Hilbert had shown that the axiomatisation $\mathcal{L}_{\varepsilon}$ of classical Aristotlean predicate logic proposed by him as a formal first-order $\varepsilon$-predicate calculus[2] in which he used a primitive choice-function[3] symbol, $\varepsilon$‘, for defining the quantifiers $\forall$‘ and $\exists$‘ would adequately express—and yield, under a suitable interpretation—Aristotle’s logic of predicates if the $\varepsilon$-function was interpreted to yield Aristotlean particularisation[4].

Classical approaches to mathematics—essentially following Hilbert—can be labelled theistic’ in that they implicitly assume—without providing adequate objective criteria—[5] both that:

$\bullet$ The standard first order logic FOL is consistent;

and that:

$\bullet$ The standard interpretation of FOL is finitarily sound (which implies Aristotle’s particularisation).

The significance of the label theistic’ is that conventional wisdom tacitly believes that Aristotle’s particularisation remains valid—without qualification—even over infinite domains; a belief that is not unequivocally self-evident, but must be appealed to as an article of faith.

Although intended to highlight an entirely different distinction, that the choice of such a label may not be totally inappropriate is suggested by Tarski’s point of view[6] to the effect:

“… that Hilbert’s alleged hope that meta-mathematics would usher in a feeling of absolute security’ was a kind of theology’ that lay far beyond the reach of any normal human science’ …”.

Brouwerian Atheism

We note second that, in sharp contrast, constructive approaches to mathematics—such as Intuitionism[6a]—can be labelled atheistic’ since they deny both that:

$\bullet$ FOL is consistent (since they deny the Law of The Excluded Middle[7];

and that:

$\bullet$ The standard interpretation of FOL is sound (since they deny Aristotle’s particularisation).

The significance of the label atheistic’ is that whereas constructive approaches to mathematics deny the faith-based belief in the unqualified validity of Aristotle’s particularisation over infinite domains, their denial of the Law of the Excluded Middle is itself a belief—in the inconsistency of FOL—that is also not unequivocally self-evident, and must also be appealed to as an article of faith since it does not take into consideration the objective criteria for the consistency of FOL that follows from the Birmingham paper.

Although Brouwer’s explicitly stated objection appeared to be to the Law of the Excluded Middle as expressed and interpreted at the time[8], some of Kleene’s remarks[9], some of Hilbert’s remarks[10] and, more particularly, Kolmogorov’s remarks[11] suggest that the intent of Brouwer’s fundamental objection (see this post) can also be viewed today as being limited only to the yet prevailing belief—as an article of faith—that the validity of Aristotle’s particularisation can be extended without qualification to infinite domains.

Finitary Agnosticism

In our investigations, however, we adopt what may be labelled a finitarily agnostic’ perspective[12] by noting that although, if Aristotle’s particularisation holds in an interpretation then the Law of the Excluded Middle must also hold in the interpretation, the converse is not true.

We thus follow a middle path by explicitly assuming on the basis of the Birmingham paper (reproduced in this post) that:

$\bullet$ FOL is finitarily consistent;

and by explicitly stating when an argument appeals to the postulation that:

$\bullet$ The standard interpretation of FOL is sound.

The significance of the label agnostic’ is that we neither hold FOL to be inconsistent, nor hold that Aristotle’s particularisation can be applied—without qualification—over infinite domains.

The two seemingly contradictory but perhaps complementary perspectives

It follows from the above that the Brouwerian Atheistic perspective is merely a restricted perspective within the Finitary Agnostic perspective, whilst the Hilbertian Theistic perspective contradicts the Finitary Agnostic perspective.

Curiously, a case can be made (as is attempted in this post, and in this paper that I presented on 10th June 2015 at the Epsilon 2015 workshop on Hilberts Epsilon and Tau in Logic, Informatics and Linguistics, University of Montpellier, France, June 10-11-12) that the Hilbertian perspective formalises the concept of algorithmically verifiable truth’ in the non-finitary—hence essentially subjective—reasoning that circumscribes human intelligences (which, by the Anthropic principle, can be taken to reflect the ‘truths’ of natural laws), whilst the Finitary perspective formalises the concept of ‘algorithmically computable truth’ in the finitary—hence essentially objective—reasoning that circumscribes mechanical intelligences; and that the two are complementary, not contradictory, perspectives on the nature and scope of quantification.

References

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

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

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

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

Br13 L. E. J. Brouwer. 1913. Intuitionism and Formalism. Inaugural address at the University of Amsterdam, October 14, 1912. Translated by Professor Arnold Dresden for the Bulletin of the American Mathematical Society, Volume 20 (1913), pp.81-96. 1999. Electronically published in Bulletin (New Series) of the American Mathematical Society, Volume 37, Number 1, pp.55-64.

Br23 L. E. J. Brouwer. 1923. On the significance of the principle of the excluded middle in mathematics, especially in function theory. Address delivered on 21 September 1923 at the annual convention of the Deutsche Mathematiker-Vereinigung in Marburg an der Lahn. In Jean van Heijenoort. 1967. Ed. From Frege to G&oumldel: A source book in Mathematical Logic, 1878 – 1931. Harvard University Press, Cambridge, Massachusetts.

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

Cr05 John N. Crossley. 2005. What is Mathematical Logic? A Survey. Address at the First Indian Conference on Logic and its Relationship with Other Disciplines held at the Indian Institute of Technology, Powai, Mumbai from January 8 to 12. Reprinted in Logic at the Crossroads: An Interdisciplinary View – Volume I (pp.3-18). ed. Amitabha Gupta, Rohit Parikh and Johan van Bentham. 2007. Allied Publishers Private Limited, Mumbai.

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

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

Fr09 Curtis Franks. 2009. The Autonomy of Mathematical Knowledge: Hilbert’s Program Revisited}. Cambridge University Press, New York.

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

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

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

Hi27 David Hilbert. 1927. The Foundations of Mathematics. Text of an address delivered in July 1927 at the Hamburg Mathematical Seminar. In Jean van Heijenoort. 1967.Ed. From Frege to Gödel: A source book in Mathematical Logic, 1878 – 1931. Harvard University Press, Cambridge, Massachusetts.

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

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

Ko25 Andrei Nikolaevich Kolmogorov. 1925. On the principle of excluded middle. In Jean van Heijenoort. 1967. Ed. From Frege to Gödel: A source book in Mathematical Logic, 1878 – 1931. Harvard University Press, Cambridge, Massachusetts.

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

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

Ma09 Maria Emilia Maietti. 2009. A minimalist two-level foundation for constructive mathematics. Dipartimento di Matematica Pura ed Applicata, University of Padova.

MS05 Maria Emilia Maietti and Giovanni Sambin. 2005. Toward a minimalist foundation for constructive mathematics. Clarendon Press, Oxford.

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

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

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

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

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

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

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

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

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

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

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

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

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

Notes

Return to 5: See for instance: Hi25, p.382; HA28, p.48; Sk28, p.515; Go31, p.32.; Kl52, p.169; Ro53, p.90; BF58, p.46; Be59, pp.178 & 218; Su60, p.3; Wa63, p.314-315; Qu63, pp.12-13; Kn63, p.60; Co66, p.4; Me64, p.52(ii); Nv64, p.92; Li64, p.33; Sh67, p.13; Da82, p.xxv; Rg87, p.xvii; EC89, p.174; Mu91; Sm92, p.18, Ex.3; BBJ03, p.102; Cr05, p.6.

Return to 7: “The formula $\forall x(A(x)\vee \neg A(x))$ is classically provable, and hence under classical interpretation true. But it is unrealizable. So if realizability is accepted as a necessary condition for intuitionistic truth, it is untrue intuitionistically, and therefore unprovable not only in the present intuitionistic formal system, but by any intuitionistic methods whatsoever”. Kl52, p.513.

Author’s working archives & abstracts of investigations

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

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

$\S 1$ The Logical Issue

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

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

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

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

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

$\S 2$ Weakening the Church and Turing Theses

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

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

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

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

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

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

$\S 2.1$ The need for explicitly distinguishing between instantiational’ and uniform’ methods

Why Church’s Thesis?

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

Kurt Gödel’s reservations

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

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

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

Alan Turing’s perspective

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

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

Boolos, Burgess and Jeffrey’s query

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

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

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

However, as Boolos, Burgess and Jeffrey note quizically:

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

Why should Chaitin’s constant $\Omega$ be labelled uncomputable’?

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

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

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

$\S 2.2$ Distinguishing between algorithmic verifiability and algorithmic computability

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

$\S 2.2.1$ Significance of Gödel’s $\beta$-function

We note first that in Theorem VII of his seminal 1931 paper on formally undecidable arithmetical propositions Gödel showed that, given a total number-theoretic function $f(x)$ and any natural number $n$, we can construct a primitive recursive function $\beta(z, y, x)$ and natural numbers $b_{n}, c_{n}$ such that $\beta(b_{n}, c_{n}, i)$ $= f(i)$ for all $0 \leq i \leq n$.

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

Query 3: Does Gödel’s Theorem VII admit construction of an arithmetical function $A(x)$ such that:

(a) for any given natural number $n$, there is an algorithm that can verify $A(i) = f(i)$ for all $0 \leq i \leq n$ (hence $A(x)$ may be said to be algorithmically verifiable if $f(x)$ is recursive);

(b) there is no algorithm that can verify $A(i) = f(i)$ for all $0 \leq i$ (so $A(x)$ may be said to be algorithmically uncomputable)?

$\S 2.2.2$ Defining effective computability

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

(i) Algorithmically verifiable;

(ii) Algorithmically computable.

under an interpretation.

We shall thus propose the definition:

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

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

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

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

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

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

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

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

$\S 3$ Gödel’s Theorem VII and algorithmically verifiable, but not algorithmically computable, arithmetical propositions

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

Definition 1: $\beta (x_{1}, x_{2}, x_{3}) = rm(1+(x_{3}+ 1) \star x_{2}, x_{1})$

where $rm(x_{1}, x_{2})$ denotes the remainder obtained on dividing $x_{2}$ by $x_{1}$.

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

Lemma 1: For any given denumerable sequence of natural numbers, say $f(k, 0),\ f(k, 1),\ \ldots$, and any given natural number $n$, we can construct natural numbers $b, c, j$ such that:

(i) $j = max(n, f(k, 0), f(k, 1), \ldots, f(k, n))$;

(ii) $c = j$!;

(iii) $\beta(b, c, i) = f(k, i)$ for $0 \leq i \leq n$.

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

Now we have the standard definition [22]:

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

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

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

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

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

Interpretation of $[\exists_{1}]$‘: The symbol $[\exists_{1}]$‘ denotes uniqueness’ under an interpretation which assumes that Aristotle’s particularisation holds in the domain of the interpretation.

Formally, however, the PA formula:

$[(\exists_{1} x_{3})F(x_{1}, x_{2}, x_{3})]$

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

$[\neg(\forall x_{3})\neg F(x_{1}, x_{2}, x_{3}) \wedge (\forall y)(\forall z)(F(x_{1}, x_{2}, y) \wedge F(x_{1}, x_{2}, z) \rightarrow y=z)]$.

We then have:

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

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

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

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

Lemma 3: If $f(x_{1}, x_{2})$ is a recursive function defined by:

(i) $f(x_{1}, 0) = g(x_{1})$

(ii) $f(x_{1}, (x_{2}+1)) = h(x_{1}, x_{2}, f(x_{1}, x_{2}))$

where $g(x_{1})$ and $h(x_{1}, x_{2}, x_{3})$ are recursive functions of lower rank [25] that are represented in PA by well-formed formulas $[G(x_{1}, x_{2})]$ and $[H(x_{1}, x_{2}, x_{3}, x_{4})]$,

then $f(x_{1}, x_{2})$ is represented in PA by the following well-formed formula, denoted by $[F(x_{1}, x_{2}, x_{3})]$:

$[(\exists u)(\exists v)(((\exists w)(Bt(u, v, 0, w) \wedge G(x_{1}, w))) \wedge Bt(u, v, x_{2}, x_{3}) \wedge (\forall w)(w < x_{2} \rightarrow (\exists y)(\exists z)(Bt(u, v, w, y) \wedge Bt(u, v, (w+1), z) \wedge H(x_{1}, w, y, z)))].$

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

$\S 4.1$ What does “$[(\exists_{1} x_{3})F(k, m, x_{3})]$ is provable” assert under the standard interpretation of PA?

Now, if the PA formula $[F(x_{1}, x_{2}, x_{3})]$ represents in PA the recursive function denoted by $f(x_{1}, x_{2})$ then by definition, for any given numerals $[k], [m]$, the formula $[(\exists_{1} x_{3})F(k, m, x_{3})]$ is provable in PA; and true under the standard interpretation of PA.

We thus have that:

Lemma 4:$[(\exists_{1} x_{3})F(k, m, x_{3})]$ is true under the standard interpretation of PA” is the assertion that:

Given any natural numbers $k, m$, we can construct natural numbers $t_{(k, m)}, u_{(k, m)}, v_{(k, m)}$—all functions of $k, m$—such that:

(a) $\beta(u_{(k, m)}, v_{(k, m)}, 0) = g(k)$;

(b) for all $i, $\beta(u_{(k, m)}, v_{(k, m)}, i) = h(k, i, f(k, i))$;

(c) $\beta(u_{(k, m)}, v_{(k, m)}, m) = t_{(k, m)}$;

where $f(x_{1}, x_{2})$, $g(x_{1})$ and $h(x_{1}, x_{2}, x_{3})$ are any recursive functions that are formally represented in PA by $F(x_{1}, x_{2}, x_{3}), G(x_{1}, x_{2})$ and $H(x_{1}, x_{2}, x_{3}, x_{4})$ respectively such that:

(i) $f(k, 0) = g(k)$

(ii) $f(k, (y+1)) = h(k, y, f(k, y))$ for all $y

(iii) $g(x_{1})$ and $h(x_{1}, x_{2}, x_{3})$ are recursive functions that are assumed to be of lower rank than $f(x_{1}, x_{2})$.

Proof: For any given natural numbers $k$ and $m$, if $[F(x_{1}, x_{2}, x_{3})]$ interprets as a well-defined arithmetical relation under the standard interpretation of PA, then we can define a deterministic Turing machine $TM$ that can construct’ the sequences:

$f(k, 0), f(k, 1), \ldots, f(k, m)$

and:

$\beta(u_{(k, m)}, v_{(k, m)}, 0), \beta(u_{(k, m)}, v_{(k, m)}, 1), \ldots, \beta(u_{(k, m)}, v_{(k, m)}, m)$

and give evidence to verify the assertion. $\Box$[27]

We now see that:

Theorem 1: Under the standard interpretation of PA $[(\exists_{1} x_{3})F(x_{1}, x_{2}, x_{3})]$ is algorithmically verifiable, but not algorithmically computable, as always true over $\mathbb{N}$.

Proof: It follows from Lemma 4 that:

(1) $[(\exists_{1} x_{3})F(k, m, x_{3})]$ is PA-provable for any given numerals $[k, m]$. Hence $[(\exists_{1} x_{3})F(k, m, x_{3})]$ is true under the standard interpretation of PA. It then follows from the definition of $[F(x_{1}, x_{2}, x_{3})]$ in Lemma 3 that, for any given natural numbers $k, m$, we can construct some pair of natural numbers $u_{(k, m)}, v_{(k, m)}$—where $u_{(k, m)}, v_{(k, m)}$ are functions of the given natural numbers $k$ and $m$—such that:

(a) $\beta(u_{(k, m)}, v_{(k, m)}, i) = f(k, i)$ for $0 \leq i \leq m$;

(b) $F^{*}(k, m, f(k, m))$ holds in $\mathbb{N}$.

Since $\beta(x_{1}, x_{2}, x_{3})$ is primitive recursive, $\beta(u_{(k, m)}, v_{(k, m)}, i)$ defines a deterministic Turing machine $TM$ that can construct’ the denumerable sequence $f'(k, 0), f'(k, 1), \ldots$ for any given natural numbers $k$ and $m$ such that:

(c) $f(k, i) = f'(k, i)$ for $0 \leq i \leq m$.

We can thus define a deterministic Turing machine $TM$ that will give evidence that the PA formula $[(\exists_{1} x_{3})F(k, m, x_{3})]$ is true under the standard interpretation of PA.

Hence $[(\exists_{1} x_{3})F(x_{1}, x_{2}, x_{3})]$ is algorithmically verifiable over $\mathbb{N}$ under the standard interpretation of PA.

(2) Now, the pair of natural numbers $u_{(x_{1}, x_{2})}, v_{(x_{1}, x_{2})}$ are defined such that:

(a) $\beta(u_{(x_{1}, x_{2})}, v_{(x_{1}, x_{2})}, i) = f(x_{1}, i)$ for $0 \leq i \leq x_{2}$;

(b) $F^{*}(x_{1}, x_{2}, f(x_{1}, x_{2}))$ holds in $\mathbb{N}$;

where $v_{(x_{1}, x_{2})}$ is defined in Lemma 3 as $j$!, and:

(c) $j = max(n, f(x_{1}, 0), f(x_{1}, 1), \ldots, f(x_{1}, x_{2}))$;

(d) $n$ is the number’ of terms in the sequence $f(x_{1}, 0), f(x_{1}, 1), \ldots, f(x_{1}, x_{2})$.

Since $j$ is not definable for a denumerable sequence $\beta(u_{(x_{1}, x_{2})}, v_{(x_{1}, x_{2})}, i)$ we cannot define a denumerable sequence $f'(x_{1}, 0), f'(x_{1}, 1), \ldots$ such that:

(e) $f(k, i) = f'(k, i)$ for all $i \geq 0$.

We cannot thus define a deterministic Turing machine $TM$ that will give evidence that the PA formula $[(\exists_{1} x_{3})F(x_{1}, x_{2}, x_{3})]$ interprets as true under the standard interpretation of PA for any given sequence of numerals $[(a_{1}, a_{2})]$.

Hence $[(\exists_{1} x_{3})F(x_{1}, x_{2}, x_{3})]$ is not algorithmically computable over $\mathbb{N}$ under the standard interpretation of PA.

The theorem follows. $\Box$

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

The above theorem now suggests the following definition:

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

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

References

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Notes

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

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

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

Return to 9: Tu36, $\S9(II)$, p.139.

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

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

Return to 14: Chaitin’s Halting Probability is given by $0 < \Omega = \sum2^{-|p|} < 1$, where the summation is over all self-delimiting programs $p$ that halt, and $|p|$ is the size in bits of the halting program $p$; see Ct75.

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

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

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

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

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

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

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

Return to 27: A critical philosophical issue that we do not address here is whether the PA formula $[F(x_{1}, x_{2}, x_{3}]$ can be considered to interpret under a sound interpretation of PA as a well-defined predicate, since the denumerable sequences $\{f(k, 0), f(k, 1), \ldots, f(k, m), m_{p}: p>0$ and $m_{p}$ is not equal to $m_{q}$ if $p$ is not equal to $q\}$—are represented by denumerable, distinctly different, functions $\beta(u_{p_{1}}, v_{p_{2}}, i)$ respectively. There are thus denumerable pairs $(u_{p_{1}}, v_{p_{2}})$ for which $\beta(u_{p_{1}}, v_{p_{2}}, i)$ yields the sequence $f(k, 0), f(k, 1), \ldots, f(k, m)$.

Author’s working archives & abstracts of investigations

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

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

$\S 1.1$ The Philosophical Issue

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

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

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

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

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

$\S 1.2$ Are axiomatic computational concepts really unambiguous?

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

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

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

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

$\S 1.2.1$ Mendelson’s thesis

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

(i) “Here is the main conclusion I wish to draw:

it is completely unwarranted to say that CT is unprovable just because it states an equivalence between a vague, imprecise notion (effectively computable function) and a precise mathematical notion (partial-recursive function)”.

(ii) “The concepts and assumptions that support the notion of partial-recursive function are, in an essential way, no less vague and imprecise (non-constructive, and intuitionistically objectionable) than the notion of effectively computable function; the former are just more familiar and are part of a respectable theory with connections to other parts of logic and mathematics.

(The notion of effectively computable function could have been incorporated into an axiomatic presentation of classical mathematics, but the acceptance of CT made this unnecessary.) …

Functions are defined in terms of sets, but the concept of set is no clearer (not more non-constructive, and intuitionistically objectionable) than that of function and a foundation of mathematics can be based on a theory using function as primitive notion instead of set.

Tarski’s definition of truth is formulated in set-theoretic terms, but the notion of set is no clearer (not more non-constructive, and intuitionistically objectionable), than that of truth.

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

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

where:

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

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

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

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

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

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

and, where Bringsjord paraphrases (iii) as:

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

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

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

$\S 1.2.2$ The concept of constructive, and intuitionistically unobjectionable’

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

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

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

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

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

However, $\S 1.2.1(a)$, $\S 1.2.1(b)$ and $\S 1.2.1(c)$ appear to suggest that Mendelson’s remarks relate implicitly to non-constructive meta-assertions.

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

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

$\S 1.2.3$ The duality

Clearly, meta-assertion $\S 1.2.1(iii)$ would stand refuted by a non-algorithmic’ effective method that is constructive.

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

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

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

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

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

$\S 1.2.4$ Definition of a formal mathematical object, and consequences

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

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

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

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

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

$\S 1.2.5$ Bringsjord’s case against CT

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

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

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

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

$H(P, i)$ iff $(\exists n)S(P, i, n)$

where the predicate $S(P, u, n)$ holds if, and only if, TM M, running program P on input $u$, halts in exactly $n$ steps ($= MP : u =>n$ halt).

Bringsjord’s Total Computability

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

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

Bringsjord’s Partial Computability

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

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

Kalmár’s Perspective of CT

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

“First, he draws our attention to a function $g$ that isn’t Turing-computable, given that $f$ is [7]:

$g(x) = \mu y(f(x, y) = 0)$ = {the least $y$ such that $f(x, y) = 0$ if $y$ exists; and $0$ if there is no such $y$}

Kalmár proceeds to point out that for any $n$ in $N$ for which a natural number $y$ with $f(n, y) = 0$ exists,

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

namely, calculate in succession the values $f(n, 0), f(n, 1), f(n, 2), \ldots$ (which, by hypothesis, is something a computist or TM can do) until we hit a natural number $m$ such that $f(n, m) = 0$, and set $y = m$.

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

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

(*) there is no natural number $y$ such that $f(p, y)= 0$; and

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

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

Distinguishing between individually effective computability and uniformly effective computability

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

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

References

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Notes

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

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

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

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

Author’s working archives & abstracts of investigations