You are currently browsing the category archive for the ‘Foundations of mathematics’ category.

Why primality is polynomial time, but factorisation is not

Differentiating between the signature of a number and its value

A brief review: The significance of evidence-based reasoning

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

“It is by now folklore … that one can view the values of a simple functional language as specifying evidence for propositions in a constructive logic …” … Chetan. R. Murthy: [Mu91], \S 1 Introduction.

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

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

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

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

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

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

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

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

Definition 2 (Algorithmic verifiability): The number-theoretical relation $F^{*}(x)$ is algorithmically verifiable if, and only if, for any natural number $n$, there is a deterministic algorithm $AL_{(F,\ n)}$ which can provide evidence for deciding the truth/falsity of each proposition in the finite sequence $\{F^{*}(1), F^{*}(2), \ldots, F^{*}(n)\}$.

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

Definition 3 (Algorithmic computability): The number theoretical relation $F^{*}(x)$ is algorithmically computable if, and only if, there is a deterministic algorithm $AL_{F}$ that can provide evidence for deciding the truth/falsity of each proposition in the denumerable sequence $\{F^{*}(1), F^{*}(2), \ldots\}$.

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

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

(a) the weak non-finitary standard interpretation $I_{PA(N, SV)}$ ([An16], Theorem 5.6),

and

(b) a strong finitary interpretation $I_{PA(N, SC)}$ ([An16], Theorem 6.7);

(ii) PA is non-finitarily consistent under $I_{PA(N, SV)}$ ([An16], Theorem 5.7);

(iii) PA is finitarily consistent under $I_{PA(N, SC)}$ ([An16], Theorem 6.8).

The significance of evidence-based reasoning for Computational Complexity

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

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

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

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

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

Definition 4 (Signature of a number): The signature of a given integer $n$ is the sequence $a_{_{n,i}}$ where $n + a_{_{n,i}} \equiv 0\ mod\ (p_{_{i}})$ for all primes $p_{_{i}}\ such\ that\ 1\leq i \leq \pi(\sqrt{n})$.

Unique since, if $p_{_{\pi(\sqrt{m})+1}}^{2} > m \geq p_{_{\pi(\sqrt{m})}}^{2}$ and $p_{_{\pi(\sqrt{n})+1}}^{2} > n \geq p_{_{\pi(\sqrt{n})}}^{2}$ have the same signature, then $|m - n| = c_{_{1}}.\prod_{i=1}^{\pi(\sqrt{m})}p_{_{i}} = c_{_{2}}.\prod_{i=1}^{\pi(\sqrt{n})}p_{_{i}}$; whence $c_{_{1}} = c_{_{2}} = 0$ since $\prod_{i=1}^{k}p_{_{i}} > (\prod_{i=2}^{k-2}p_{_{i}}).p_{_{k}}^{^{2}} > p_{_{k+1}}^{2}$ for $k > 4$ by appeal to Bertrand’s Postulate $2.p_{_{k}} > p_{_{k+1}}$; and the uniqueness is easily verified for $k \leq 4$.

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

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

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

$n=p_{1}^{n_{1}}p_{2}^{n_{2}}\cdots p_{k}^{n_{k}}=\prod _{i=1}^{k}p_{i}^{n_{i}}$

where $p_{1} < p_{2} < \ldots < p_{k}$ are primes and the $n_{i}$ are positive integers (including $0$).

Are the prime divisors of an integer mutually independent?

In this paper I address the query:

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

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

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

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

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

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

Proposition 1: Whether or not a prime $p$ divides an integer $n$ is independent of whether or not a prime $q \neq p$ divides the integer $n$.

We note that such an unprovable-but-intuitively-true conclusion makes a stronger assumption than that in Gödel’s similar claim for his arithmetical formula $[(\forall x)R(x)]$—whose Gödel-number is $17Gen\ r$—in [Go31], p.26(2). Stronger, since Gödel does not assume his proposition to be intuitively true, but shows that though the arithmetical formula with Gödel-number $17Gen\ r$ is not provable in his Peano Arithmetic $P$ yet, for any $P$-numeral $[n]$, the formula $[R(n)]$ whose Gödel-number is $Sb \left(r \begin{array}{c}17 \\ Z(n)\end{array}\right)$ is $P$-provable, and therefore meta-mathematically true under any well-defined Tarskian interpretation of $P$ (cf., [An16], Section 3.).

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

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

Theorem 2: There is no deterministic algorithm that, for any given $n$, and any given prime $p \geq 2$, will evidence that the probability $\mathbb{P}(p\ |\ n)$ that $p$ divides $n$ is $\frac{1}{p}$, and the probability $\mathbb{P}(p\not|\ n)$ that $p$ does not divide $n$ is $1 - \frac{1}{p}$.

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

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

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

Theorem 3: For any given $n$, there is a deterministic algorithm that, given any prime $p \geq 2$, will evidence that the probability $\mathbb{P}(p\ |\ n)$ that $p$ divides $n$ is $\frac{1}{p}$, and the probability $\mathbb{P}(p\not|\ n)$ that $p$ does not divide $n$ is $1 - \frac{1}{p}$.

Author’s working archives & abstracts of investigations

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

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

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

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

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

(i) Gödel’s semantic definition of ‘$[R(n) : n]$‘, and therefore of ‘$\neg Bew[R(n) : n]$‘, is not only:

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

but that:

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

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

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

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

$n \in K \equiv \neg Bew[R(n) : n]$

lends legitimacy to $\neg Bew[R(n) : n]$ as a PM formula.

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

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

We cannot, though, conclude from this that:

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

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

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

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

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

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

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

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

by:

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

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

and:

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

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

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

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

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

from:

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

Moreover, we note that:

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

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

#46. $Bew(x) \equiv (\exists y)yBx$.

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

$x$ is the Gödel-number of some provable formula $[F]$ of Gödel’s Peano Arithmetic P’.

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

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

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

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

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

(a) If $Bew(m)$ is true under interpretation in N, then [Bew$_{_{PA}}(m)]$ is provable in P;

(b) If $\neg Bew(m)$ is true under interpretation in N, then $\neg$[Bew$_{_{PA}}(m)]$ is provable in P.

Author’s working archives & abstracts of investigations

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

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

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

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

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

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

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

The Brains blog

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

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

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

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

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

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

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

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

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

III: The Unexplained Intellect: The importance of computability

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

IV: The Unexplained Intellect: Consequences of imperfection

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

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

V: The Unexplained Intellect: The importance of rapport

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

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

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

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

A: Simplifying Mole’s perspective

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

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

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

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

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

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

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

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

B. Support for Mole’s thesis

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

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

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

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

C. Algorithmic computability

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

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

D. Algorithmic verifiability

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

H. The importance of Mole’s ‘rapport’

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

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

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

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

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

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

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

Author’s working archives & abstracts of investigations

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

A new proof?

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

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

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

More concretely:

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

The proof appeals to properties of transfinite ordinals

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

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

Why we cannot ignore Skolem’s cautionary remarks

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

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

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

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

A remarkable exposition of Ramsey’s Theorem

The Yokoyama-Patey proof invites other reservations too.

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

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

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

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

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

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

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

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

Implicit assumptions in Yokoyama-Patey’s argument

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

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

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

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

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

Now in ZF (as in any first-order theory that appeals to the standard first-order logic FOL) the formula $(\exists x)F(x)$ is merely an abbreviation for the formula $\neg(\forall x)\neg(F(x)$.

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

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

(a) Is the $(\forall x)F(x)]$ to be interpreted constructively as:

For any natural number $n$, there is an algorithm $T_n$ (say, a deterministic Turing machine) which evidences that $\{F(1), F(2), \ldots, F(n)\}$ are all true; or,

(b) is the formula $(\forall x)F(x)$ to be interpreted finitarily as:

There is a single algorithm $T$ (say, a deterministic Turing machine) which evidences that, for any natural number $n, F(n)$ is true, i.e., each of $\{F(1), F(2), \ldots\}$ is true?

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

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

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

Author’s working archives & abstracts of investigations

(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

(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}}})$.

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 (see Fig.15 of the investigation) 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

Finitarily consistent mechanist reasoning and non-finitarily consistent human reasoning: Mutually inconsistent yet complementary!

We now consider the following (tentatively expressed) conclusions suggested by our previous post, which we shall aim to investigate from various perspectives in these pages.

Structures

The Birmingham paper suggests that we may need to distinguish much more sharply than we do at present between:

$\bullet$ Mathematical structures that are built upon only finitary reasoning, and

$\bullet$ Mathematical structures that admit non-finitary reasoning.

Interpretations

For instance the Birmingham paper provides:

$\bullet$ An example of a mathematical structure based on finitary reasoning, namely the finitarily sound algorithmic interpretation $\mathcal{I}_{PA(N,\ Algorithmic)}$ of the first order Peano Arithmetic PA.

$\bullet$ An example of a mathematical structure based on non-finitary reasoning, namely the non-finitarily sound standard interpretation $\mathcal{I}_{PA(N,\ Standard)}$ of the first order Peano Arithmetic PA.

Aristotle’s particularisation

The Birmingham paper suggests that the roots of the distinction between these two structures lies in the fact that:

$\bullet$ Finitary reasoning does not assume that Aristotle’s particularisation is always true over infinite domains.

$\bullet$ Non-finitary reasoning assumes that Aristotle’s particularisation is always true over infinite domains.

Consistency of Arithmetic

In the Birmingham paper we also show that:

$\bullet$ Finitary reasoning proves that PA is consistent finitarily (as demanded by the second of Hilbert’s celebrated twenty three problems).

$\bullet$ Non-finitary reasoning proves that PA is consistent non-finitarily (a consequence of Gentzen’s non-finitary proof of consistency for PA).

FOL is consistent; FOL+AP is $\omega$-consistent

This suggests that:

$\bullet$ Finitary reasoning as formalised in first order logic (FOL) is consistent.

$\bullet$ Non-finitary reasoning as formalised in Hilbert’s $\epsilon$-calculus (FOL+AP) is $\omega$-consistent.

$\omega$-consistency

Since the Birmingham paper shows that Aristotle’s particularisation holds over the structure of the natural numbers if, and only if, PA is $\omega$-consistent, it suggests that:

$\bullet$ Finitary reasoning does not admit that PA can be $\omega$-consistent (see Corollary 4 of this post).

$\bullet$ Non-finitary reasoning admits that PA can be $\omega$-consistent.

Arithmetical undecidability

Since proofs of arithmetical undecidability implicitly assume Aristotle’s particularisation, this further suggests that:

$\bullet$ Finitary reasoning does not admit undecidable arithmetical propositions (see Corollary 3 of this post).

$\bullet$ Non-finitary reasoning admits undecidable arithmetical propositions.

Completed Infinity

A significant consequence is that:

$\bullet$ Finitary reasoning does not admit an axiom of infinity.

$\bullet$ Non-finitary reasoning admits an axiom of infinity.

Non-standard models of PA

A further consequence of this is that:

$\bullet$ Finitary reasoning does not admit non-standard models of PA.

$\bullet$ Non-finitary reasoning too does not admit non-standard models of PA.

Algorithmically computable truth and algorithmically verifiable truth

The Birmingham paper also suggests that:

$\bullet$ The truths of finitary reasoning are algorithmically computable.

$\bullet$ The truths of non-finitary reasoning are algorithmically verifiable, but not necessarily algorithmically computable.

Categoricity and incompleteness of Arithmetic

We show in Corollary 1 of this post that it also follows from the Birmingham paper that:

$\bullet$ Finitary reasoning proves that PA is categorical with respect to algorithmically computable truth.

$\bullet$ Non-finitary reasoning proves that PA is incomplete with respect to algorithmically verifiable truth (a consequence of Gödel’s proof of of the undecidability of some arithmetical propositions in any $\omega$-consistent system of arithmetic).

How intelligences reason

This suggests that:

$\bullet$ Finitary reasoning is a shared characteristic of all intelligences, human or non-human.

$\bullet$ Non-finitary reasoning is a characteristic of human intelligence that may not be shared by any other intelligence.

Communication between intelligences: SETI

It further suggests that the search for extra-terrestrial intelligence may benefit from the argument that:

$\bullet$ Finitary reasoning admits effective and unambiguous communication between two intelligences with respect to its (algorithmically computable) arithmetical truths.

$\bullet$ Non-finitary reasoning does not admit effective and unambiguous communication between two intelligences with respect to its (algorithmically verifiable) arithmetical truths.

Determinism, Unpredictability and the EPR paradox

An unexpected consequence of the arguments of the Birmingham paper is that our perspectives on the relation between determinism and predictability may benefit from the paradigm shift demanded by the argument that:

$\bullet$ Finitary reasoning admits the EPR paradox.

$\bullet$ Non-finitary reasoning does not admit the EPR paradox.

The Gödelian argument

The arguments of the Birmingham paper also suggest a fresh perspective on the issue of computationalism since:

$\bullet$ Finitary reasoning does not admit Lucas’ Gödelian argument.

$\bullet$ Non-finitary reasoning admits Lucas’ Gödelian argument.

Effective computability

It further suggests that the nature and status of ‘effective computability’ may also need to be assessed afresh since:

$\bullet$ Finitary reasoning naturally equates algorithmic computability with effective computability.

$\bullet$ Non-finitary reasoning naturally equates algorithmic verifiability with effective computability.

Church Turing Thesis

As also the nature of CT, since:

$\bullet$ Finitary reasoning admits the Church-Turing Thesis.

$\bullet$ Non-finitary reasoning does not admit the Church-Turing Thesis.

Goodstein’s Theorem

Broadly speaking, the two conflicting-but-complementary structures defined in the Birmingham paper suggest that we should be more explicit—in our argumentation—of the structure to which a particular assertion about the natural numbers pertains, since:

$\bullet$ Both finitary and non-finitary reasoning do not admit the proof of Goodstein’s Theorem as neither admits a completed infinity.

$\bullet$ Set-theoretical reasoning admits the proof of Goodstein’s Theorem as it admits a completed infinity.

There’s more …

In the next post we shall consider some further intriguing consequences suggested by the Birmingham paper.

What do you think?

Does Goodstein’s sequence over the natural numbers always terminate or not?

Author’s working archives & abstracts of investigations

### Start here

Join 85 other followers

Diagonal Argument

Math, science, their history, and assorted trivia and quadrivia.

math - update

blogging & searching for true math ...

George Lakoff

George Lakoff has retired as Distinguished Professor of Cognitive Science and Linguistics at the University of California at Berkeley. He is now Director of the Center for the Neural Mind & Society (cnms.berkeley.edu).

LobeLog

Critical Perspectives on U.S. Foreign Policy

What's new

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

Quanta Magazine

Reviewing classical interpretations of Cantor's, Gödel's, Tarski's, and Turing's reasoning and addressing some grey areas in the foundations of mathematics, logic and computability

The Brains Blog

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

Logic Matters

Reviewing classical interpretations of Cantor's, Gödel's, Tarski's, and Turing's reasoning and addressing some grey areas in the foundations of mathematics, logic and computability

A Neighborhood of Infinity

Reviewing classical interpretations of Cantor's, Gödel's, Tarski's, and Turing's reasoning and addressing some grey areas in the foundations of mathematics, logic and computability

Combinatorics and more

Gil Kalai's blog

Mathematics and Computation

Reviewing classical interpretations of Cantor's, Gödel's, Tarski's, and Turing's reasoning and addressing some grey areas in the foundations of mathematics, logic and computability

Foundations of Mathematics, Logic & Computability

Reviewing classical interpretations of Cantor's, Gödel's, Tarski's, and Turing's reasoning and addressing some grey areas in the foundations of mathematics, logic and computability

John D. Cook

Reviewing classical interpretations of Cantor's, Gödel's, Tarski's, and Turing's reasoning and addressing some grey areas in the foundations of mathematics, logic and computability

Shtetl-Optimized

Reviewing classical interpretations of Cantor's, Gödel's, Tarski's, and Turing's reasoning and addressing some grey areas in the foundations of mathematics, logic and computability

Nanoexplanations

the blog of Aaron Sterling

Eric Cavalcanti

Quantum physicist

East Asia Forum

Reviewing classical interpretations of Cantor's, Gödel's, Tarski's, and Turing's reasoning and addressing some grey areas in the foundations of mathematics, logic and computability