You are currently browsing the tag archive for the ‘natural number’ tag.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

F'(a) holds for some element a

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

E: Consider these two statements of yours …

Consider these two statements of yours:

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

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

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

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

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

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

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

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

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

I would interpret:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. It also means that:

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

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

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

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

4. Which raises the question:

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

Author’s working archives & abstracts of investigations

Bhupinder Singh Anand

Advertisements

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

Ferguson’s and Priest’s thesis

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

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

Ferguson and Priest conclude their review by remarking that:

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

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

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

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

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

A struggle reflected so eloquently in this nineteenth century quote:

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

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

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

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

Making sense of mathematical propositions about infinite processes

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

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

The Liar paradox

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

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

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

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

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

Gödel’s influence on Turing’s reasoning

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

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

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

What is logic: using Ockham’s razor

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

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

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

where I introduced the definition:

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

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

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

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

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

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

\bullet Interpret such representations unambiguously; and

\bullet Conclude further:

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

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

Author’s working archives & abstracts of investigations

Bhupinder Singh Anand

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

A Economist: The return of the machinery question

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

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

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

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

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

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

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

C Justifying irrationality

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

D Differentiating between Human reasoning and Mechanistic reasoning

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

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

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

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

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

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

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

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

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

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

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

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

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

Author’s working archives & abstracts of investigations

Bhupinder Singh Anand

(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 \S1.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 \S4.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

Bhupinder Singh Anand

(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 (\S6.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

Bhupinder Singh Anand

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 1: HW60, p.49.

Return to 2: HW60, p.52, Theorem 59.

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.

Return to 4: By HW60, p.351, Theorem 429, Mertens’ Theorem.

Return to 5: By the argument in Ti51, p.59, eqn.(3.15.2).

Return to 6: HW60, p.9, Theorem 7.

Author’s working archives & abstracts of investigations

Bhupinder Singh Anand

Follow me on Academia.edu

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 1: HW60, p.49.

Return to 2: Ko56, Chapter I, Section 1, Axiom III, p.2; see also GS97, Chapter 1, Section 1.2, Definition 1.2, p.19.

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.

Return to 4: HW60, p.52, Theorem 59.

Author’s working archives & abstracts of investigations

Bhupinder Singh Anand

It is a misconception that an arithmetical statement—such as the one constructed by Kurt Gödel (1931. On formally undecidable propositions of Principia Mathematica and related systems I. In M. Davis. 1965. The Undecidable. p25)—can be intuitively true, and yet not follow formally from the axioms and rules of inference of a first-order Peano Arithmetic, PA.

The misconception arises because PA actually admits two logical entailments, only one of which—Gödelian provability—has, so far, been formally acknowledged.

However, the other—familiar only in its avatar as the intuitive truth of a proposition under PA‘s standard interpretation—does, also, follow formally from the axioms and rules of inference of PA.

Even when this issue is sought to be addressed, the argument is indirect, and this point remains implicit.

For instance, in a critical review of Roger Penrose’s Gödelian argument, Martin Davis (1990. Is Mathematical Insight Algorithmic? Behavioural and Brain Sciences, vol. 13 (1990), pp. 659–660) argues that:

“… There is an algorithm which, given any consistent set of axioms, will output a polynomial equation P = 0 which in fact has no integer solutions, but such that this fact can not be deduced from the given axioms. Here then is the true but unprovable Gödel sentence on which Penrose relies and in a particularly simple form at that. Note that the sentence is provided by an algorithm. If insight is involved, it must be in convincing oneself that the given axioms are indeed consistent, since otherwise we will have no reason to believe that the Gödel sentence is true”.

Note that the first part of Gödel’s argument in Theorem VI of his 1931 paper is that, if PA is consistent, then we can mechanically construct a PA formula—which, syntactically, is of the form [(\forall x)R(x)]—such that:

(i) The formula [(\forall x)R(x)], when viewed as a string of ‘meaningless’ symbols, does not follow mechanically from the axioms of PA as the last of any finite sequence of PA-formulas, each of which is either a PA-axiom, or a consequence of one or more of the formulas preceding it in the sequence, by the mechanical application of the rules of inference of PA;

(ii) For any given numeral [n]—which ‘represents’ the natural number n in PA—the formula [R(n)], when viewed as a string of ‘meaningless’ symbols, does follow mechanically from the axioms of PA as the last of some finite sequence of PA-formulas, each of which is either a PA-axiom, or a consequence of one or more of the formulas preceding it in the sequence, by the mechanical application of the rules of inference of PA.

Now, (i) is the standard definition (due to Gödel) of the meta-assertion:

(iii) The PA-formula [(\forall x)R(x)] is formally unprovable in PA.

However, under standard interpretations of Alfred Tarski’s definitions of the satisfiability and truth of the formulas of a language L under an interpretation M, the L-formula [(\forall x)R(x)] is true in the interpretation M if, and only if, the interpreted relation R^{\prime}(x) is instantiationally satisfied in M (i. e. for any given element of M the interpreted relation can be ‘seen’ to hold in the interpretation).

If we take both L and M as PA (as detailed in ‘Evidence-Based Interpretations of PA‘), and take satisfiability in PA to mean instantiational provability in PA, we arrive at the formal definition of the truth of the PA-formula [(\forall x)R(x)] in PA as:

The PA-formula [(\forall x)R(x)] is formally true in PA if, and only if, the formula [R(x)] is provable in PA whenever we substitute a numeral [n] for the variable [x] in [R(x)].

Hence (ii) is the standard definition (due to Tarski) of the meta-assertion:

(iv) The PA-formula [(\forall x)R(x)] is formally true in PA.

So, by definition, the appropriate interpretation of Gödel’s reasoning (i) and (ii) ought to be:

(v) The PA-formula [(\forall x)R(x)] is formally unprovable in PA, but formally true in PA.

This interpretation also meets Ludwig Wittgenstein’s (Remarks on the Foundations of Mathematics. 1978 edition. MIT Press) requirement that the concept of ‘truth’ in a language must be formally definable, and effectively verifiable, within the language.

As noted by Reuben L. Goodstein (1972. Wittgenstein’s Philosophy of Mathematics. In Ambrose, Alice, and Morris Lazerowitz (eds.), Ludwig Wittgenstein: Philosophy and Language. George Allen and Unwin. pp. 271–86):

“In the realist-formalist controversy in the philosophy of mathematics Wittgenstein’s Remarks offers a solution that is crystal clear and satisfyingly uncompromising. The true propositions of mathematics are true because they are provable in a calculus; they are deductions from axioms by formal rules and are true in virtue of valid applications of the rules of inference and owe nothing to the world outside mathematics.”

However, standard expositions of Gödel’s formal reasoning assert only that:

(vi) The PA-formula [(\forall x)R(x)] is formally unprovable in PA, but intuitively true in the standard interpretation of PA.

They fail to highlight that, actually, (i) and (ii) are both logically entailed by the axioms and rules of inference of PA, and that, classically, the meta-assertion:

(vii) The PA-formula [(\forall x)R(x)] is intuitively true in the standard interpretation of PA.

is both ambiguous and stronger than the meta-assertion:

(viii) The PA-formula [R(x)] is formally true in PA.

The ambiguity surfaces in the presence of the Church-Turing Thesis, for (vii), then, implicitly implies that the arithmetical relation R(x) is algorithmically decidable as always true in the standard interpretation of PA, whereas (viii) does not.

Author’s working archives & abstracts of investigations

Bhupinder Singh Anand

Readability

Try reading in +125 magnification

Start here

Enter your email address to follow this blog and receive notifications of new posts by email.

Join 84 other followers

Recent posts

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

Tanya Khovanova's Math Blog

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

The polymath blog

Massively collaborative mathematical projects