You are currently browsing the tag archive for the ‘algorithm’ 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.
A: Doesn’t simple consistency suffice for defining Rosser’s undecidable arithmetical proposition?
“You claim that the PA system is -inconsistent, and that Gödel’s first theorem holds vacuously. But by Rosser’s result, simple consistency suffices.“
Well, it does seem surprising that Rosser’s claim—that his ‘undecidable’ proposition only assumes simple consistency—has not been addressed more extensively in the literature. Number-theoretic expositions of Rosser’s proof have generally remained either implicit or sketchy (see, for instance, this post).
Note that Rosser’s proposition and reasoning involve interpretation of an existential quantifier, whilst Gödel’s proposition and reasoning only involve interpretation of a universal quantifier.
The reason why Rosser’s claim is untenable is that—in order to interpret the existential quantifier as per Hilbert’s -calculus—Rosser’s argument needs to assume his Rule C (see Elliott Mendelson, Introduction to Mathematical Logic, 1964 ed., p.73), which implicitly implies that Gödel’s arithmetic P—in which Rosser’s argumentation is grounded—is -consistent .
See, for instance, this analysis of (a) Wang’s outline of Rosser’s argument on p.5, (b) Beth’s outline of Rosser’s argument on p.6, and (c) Mendelson’s exposition of Rosser’s argument in Section 4.2 on p.8.
Moreover, the assumption is foundationally fragile, because Rule C invalidly assumes that we can introduce an ‘unspecified’ formula denoting an ‘unspecified’ numeral into PA even if the formula has not been demonstrated to be algorithmically definable in terms of the alphabet of PA.
See Theorem 8.5 and following remarks in Section 8, pp.7-8 of this paper that was presented in June 2015 at the workshop on Hilbert’s Epsilon and Tau in Logic, Informatics and Linguistics, University of Montpellier, France.
B: As I see it, rule C is only a shortcut.
“As I see it, rule C is only a shortcut; it is totally eliminable. Moreover, it is part of predicate logic, not of the Peano’s arithmetic.“
Assuming that Rule C is a short cut which can always be eliminated is illusory, and is tantamount to invalidly (see Corollary 8.6, p.17 of the Epsilon 2015 paper) claiming that Hilbert’s calculus is a conservative extension of the first-order predicate calculus.
Reason: Application of Rule C invalidly (see Theorem 8.5 and following remarks in Section 8, pp.7-8 of the Epsilon 2015 paper) involves introduction of a new individual constant, say , in a first-order theory (see Mendelson 1964, p.74, I(iv)); ‘invalidly’ since Rule C does not qualify that must be algorithmically computable from the alphabet of —which is necessary if is first-order.
Notation: We use square brackets to indicate that the expression within the brackets denotes a well-formed formula of a formal system, say , that is to be viewed syntactically merely as a first-order string of —i.e, one which is finitarily constructed from the alphabet of the language of —without any reference to its meaning under any interpretation of .
Essentially, Rule C mirrors in the intuitionistically objectionable postulation that the formula of can always be interpreted as:
holds for some element
in the domain of the interpretation of under which the formula interprets as the relation .
The Epsilon 2015 paper shows that this is not a valid interpretation of the formula under any finitary, evidence-based, interpretation of .
That, incidentally, is a consequence of the proof that PA is not -consistent; which itself is a consequence of (Theorem 7.1, p.15, of the Epsilon 2015 paper):
Provability Theorem for PA: A PA formula is provable if, and only if, interprets as an arithmetical relation that is algorithmically computable as always true (see Definition 3, p.7, of the Epsilon 2015 paper) over the structure of the natural numbers.
Compare with what Gödel has essentially shown in his famous 1931 paper on formally undecidable arithmetical propositions, which is that (Lemma 8.1, p.16, of the Epsilon 2015 paper):
Gödel: There is a PA formula —which Gödel refers to by its Gödel number —which is not provable in PA, even though interprets as an arithmetical relation that is algorithmically verifiable as always true (see Definition 4, p.7, of the Epsilon 2015 paper) over the structure of the natural numbers.
C: If you by-pass the intuitionist objections, would all logicist and post-formalist theories hold?
“If I have understood correctly, you claim that the PA system is -inconsistent from an intuitionistic point of view? If you by-pass the intuitionist objections, would all logicist and post-formalist theories hold?“
There is nothing to bypass—the first-order Peano Arithmetic PA is a formal axiomatic system which is -inconsistent as much for an intuitionist, as it is for a realist, a finitist, a formalist, a logicist or a nominalist.
Philosophers may differ about beliefs that are essentially unverifiable; but the -incompleteness of PA is a verifiable logical meta-theorem that none of them would dispute.
D: Isn’t Gödel’s undecidable formula —which Gödel refers to by its Gödel number —self-referential?
Isn’t Gödel’s undecidable formula —which Gödel refers to by its Gödel number —self-referential and covertly paradoxical?
According to Wittgenstein it interprets in any model as a sentence that is devoid of sense, or even meaning. I think a good reason for this is that the formula is simply syntactically wrongly formed: the provability of provability is not defined and can not be consistently defined.
What you propose may be correct, but for automation systems of deduction wouldn’t -inconsistency be much more problematic than undecidability?
How would you feel if a syntax rule is proposed, that formulas containing numerals are instantiations of open formulas that may not be part of the canonical language? Too daring, may be?
Let me briefly respond to the interesting points that you have raised.
1. The -inconsistency of PA is a meta-theorem; it is a Corollary of the Provability Theorem of PA (Theorem 7.1, p.15, of the Epsilon 2015 paper).
2. Gödel’s PA-formula is not an undecidable formula of PA. It is merely unprovable in PA.
3. Moreover, Gödel’s PA-formula is provable in PA, which is why the PA formula is not an undecidable formula of PA.
4. Gödel’s PA-formula is not self-referential.
5. Wittgenstein correctly believed—albeit purely on the basis of philosophical considerations unrelated to whether or not Gödel’s formal reasoning was correct—that Gödel was wrong in stating that the PA formula asserts its own unprovability in PA.
Reason: We have for Gödel’s primitive recursive relation that:
is true if, and only if, the PA formula is provable in PA.
However, in order to conclude that the PA formula asserts its own unprovability in PA, Gödel’s argument must further imply—which it does not—that:
is true (and so, by Gödel’s definition of , the PA formula is not provable in PA) if, and only if, the PA formula is provable in PA.
In other words, for the PA formula to assert its own unprovability in PA, Gödel must show—which his own argument shows is impossible, since the PA formula is not provable in PA—that:
The primitive recursive relation is algorithmically computable as always true if, and only if, the arithmetical relation is algorithmically computable as always true (where is the arithmetical interpretation of the PA formula over the structure of the natural numbers).
6. Hence, Gödel’s PA-formula is not covertly paradoxical.
7. IF Wittgenstein believed that the PA formula is empty of meaning and has no valid interpretation, then he was wrong, and—as Gödel justifiably believed—he could not have properly grasped Gödel’s formal reasoning that:
(i) ‘ is not -provable’ is a valid meta-theorem if PA is consistent, which means that:
‘If PA is consistent and we assume that the PA formula is provable in PA, then the PA formula must also be provable in PA; from which we may conclude that the PA formula is not provable in PA’
(ii) ‘ is not -provable’ is a valid meta-theorem ONLY if PA is -consistent, which means that:
‘If PA is -consistent and we assume that the PA formula is provable in PA, then the PA formula must also be provable in PA; from which we may conclude that the PA formula is not provable in PA’.
8. In fact the PA formula has the following TWO meaningful interpretations (the first of which is a true arithmetical meta-statement—since the PA formula is provable in PA for any PA-numeral —but the second is not—since the PA formula is not provable in PA):
(i) For any given natural number , there is an algorithm which will verify that each of the arithmetical meta-statements ‘ is true’, ‘ is true’, …, ‘ is true’ holds under the standard, algorithmically verifiable, interpretation of PA (see \S 5, p.11 of the Epsilon 2015 paper);
(ii) There is an algorithm which will verify that, for any given natural number , the arithmetical statement ‘ is true’ holds under the finitary, algorithmically computable, interpretation of PA (see \S 6, p.13 of the Epsilon 2015 paper).
9. IF Wittgenstein believed that the PA formula is not a well-defined PA formula, then he was wrong.
Gödel’s definition of the PA formula yields a well-formed formula in PA, and cannot be treated as ‘syntactically wrongly formed’.
10. The Provability Theorem for PA shows that both ‘proving something in PA’ and ‘proving that something is provable in PA’ are finitarily well-defined meta-mathematical concepts.
11. The Provability Theorem for PA implies that PA is complete with respect to the concepts of satisfaction, truth and provability definable in automated deduction systems, which can only define algorithmically computable truth.
12. The Provability Theorem for PA implies that PA is categorical, so you can introduce your proposed syntax rule ONLY if it leads to a conservative extension of PA.
13. Whether ‘daring’ or not, why would you want to introduce such a rule?
E: Consider these two statements of yours …
Consider these two statements of yours:
“(iv): is the Gödel-number of the formula of PA” and
“D(4): Gödel’s PA-formula is not self-referential.”
If ‘‘ is the Gödel-number of the open formula in para (iv), and the second argument of the closed formula in para D(4) is ‘‘, then the second formula is obtained by instantiating the variable ‘‘ in the first with its own Gödel-number.
So how would you call, in one word, the relation between the entire formula (in D(4)) and its second argument?
Para D(4) is an attempt to clarify precisely this point.
1. Apropos the first statement ‘(iv)’ cited by you:
From a pedantic perspective, the “relation between the entire formula (in D(4)) and its second argument” cannot be termed self-referential because the “second argument”, i.e., , is the Gödel-number of the PA formula , and not that of “the entire formula (in 4)”, i.e., of the formula itself (whose Gödel number is ).
Putting it crudely, is neither self-referential—nor circularly defined—because it is not defined in terms of , but in terms of .
2. Apropos the second statement ‘D(4)’ cited by you:
I would interpret:
Gödel’s PA-formula is self-referential
to mean, in this particular context, that—as Gödel wrongly claimed:
asserts its own unprovability in PA.
Now, if we were to accept the claim that is self-referential in the above sense, then (as various critics of Gödel’s reasoning have pointed out) we would have to conclude further that Gödel’s argument leads to the contradiction:
is true—and so, by Gödel’s definition of —the PA formula is not provable in PA—if, and only if, the PA formula is provable in PA.
However, in view of the Provability Theorem of PA (Theorem 7.1, p.15, of the Epsilon 2015 paper), this contradiction would only follow if Gödel’s argument were to establish (which it does not) that:
The primitive recursive relation is algorithmically computable as always true if, and only if, the arithmetical interpretation of the PA formula is algorithmically computable as always true over the structure of the natural numbers.
The reason Gödel cannot claim to have established the above is that his argument only proves the much weaker meta-statement:
The arithmetical interpretation of the PA formula is algorithmically verifiable as always true over the structure of the natural numbers.
Ergo—contrary to Gödel’s claim— Gödel’s PA-formula is not self-referential (and so, even though Gödel’s claimed interpretation of what his own reasoning proves is wrong, there is no paradox in Gödel’s reasoning per se)!
F: Is the PA system -inconsistent without remedy?
Is the PA system -inconsistent without remedy? Is it possible to introduce a new axiom or new rule which by-passes the problematic unprovable statements of the Gödel-Rosser Theorems?
1. Please note that the first-order Peano Arithmetic PA is:
(i) consistent (Theorem 7.3, p.15, of the Epsilon 2015 paper); which means that for any PA-formula , we cannot have that both and are Theorems of PA;
(ii) complete (Theorem 7.1, p.15, of the Epsilon 2015 paper); which means that we cannot add an axiom to PA which is not a Theorem of PA without inviting inconsistency;
(iii) categorical (Theorem 7.2, p.15, of the Epsilon 2015 paper); which means that if is an interpretation of PA over a structure , and is an interpretation of PA over a structure , then and are identical and denote the structure of the natural numbers defined by Dedekind’s axioms; and so PA has no model which contains an element that is not a natural number (see Footnote 54, p.16, of the Epsilon 2015 paper).
2. What this means with respect to Gödel’s reasoning is that:
(i) PA has no undecidable propositions, which is why it is not -consistent (Corollary 8.4, p.16, of the Epsilon 2015 paper);
(ii) The Gödel formula is not provable in PA; but it is algorithmically verifiable as true (Corollary 8.3, p.16, of the Epsilon 2015 paper) under the algorithmically verifiable standard interpretation of PA (see Section 5, p.11, of the Epsilon 2015 paper) over the structure of the natural numbers;
(iii) The Gödel formula is not provable in PA; and it is algorithmically computable as false (Corollary 8.3, p.16, of the Epsilon 2015 paper) under the algorithmically computable finitary interpretation of PA (see Section 6, p.13, of the Epsilon 2015 paper) over the structure of the natural numbers;
(iv) The Gödel formula is provable in PA; and it is therefore also algorithmically verifiable as true under the algorithmically verifiable standard interpretation of PA over the structure of the natural numbers—which means that the logic by which the standard interpretation of PA assigns values of ‘satisfaction’ and ‘truth’ to the formulas of PA (under Tarski’s definitions) may be paraconsistent (see http://plato.stanford.edu/entries/logic-paraconsistent) since PA is consistent;
(v) The Gödel formula is provable in PA; and it is therefore algorithmically computable as true (Corollary 8.2, p.16, of the Epsilon 2015 paper) under the algorithmically computable finitary interpretation of PA over the structure of the natural numbers.
3. It also means that:
(a) The “Gödel-Rosser Theorem” is not a Theorem of PA;
(b) The “unprovable Gödel sentence” is not a “problematic statement”;
(c) The “PA system” does not require a “remedy” just because it is “-inconsistent”;
(d) No “new axiom or new rule” can “by-pass the unprovable sentence”.
4. Which raises the question:
Why do you see the “unprovable Gödel sentence” as a “problematic statement” that requires a “remedy” which must “by-pass the unprovable sentence”?
(Notations, non-standard concepts, and definitions used commonly in these investigations are detailed in this post.)
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‘:
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:
where I introduced the definition:
A finite set of rules is a Logic of a formal mathematical language if, and only if, constructively assigns unique truth-values:
(a) Of provability/unprovability to the formulas of ; and
(b) Of truth/falsity to the sentences of the Theory which is defined semantically by the -interpretation of over a structure .
I showed there that such a definitional rule-based approach to ‘logic’ and ‘truth’ allows us to:
Equate the provable formulas of the first order Peano Arithmetic PA with the PA formulas that can be evidenced as `true’ under an algorithmically computable interpretation of PA over the structure of the natural numbers;
Adequately represent some of the philosophically troubling abstractions of the physical sciences mathematically;
Interpret such representations unambiguously; and
First that the concept of infinity is an emergent feature of any mechanical intelligence whose true arithmetical propositions are provable in the first-order Peano Arithmetic; and
Second that discovery and formulation of the laws of quantum physics lies within the algorithmically computable logic and reasoning of a mechanical intelligence whose logic is circumscribed by the first-order Peano Arithmetic.
Notations, non-standard concepts, and definitions used commonly in these investigations are detailed in this post.)
1. Since, by the Prime Number Theorem, the number of primes is , it would follow that determining a factor of requires at least one logical operation for each prime , and therefore cannot be done in polynomial time—whence —IF whether or not a prime divides an integer were independent of whether or not a prime divides the integer .
2. Currently, conventional approaches to determining the computational complexity of Integer Factorising apparently appeal critically to the belief that:
(i) either—explicitly (see here)—that whether or not a prime divides an integer is not independent of whether or not a prime divides the integer ;
(ii) or—implicitly (since the problem is yet open)—that a proof to the contrary must imply that if is the probability that is a prime, then .
3. If so, then conventional approaches seem to conflate the two probabilities:
(i) The probability of selecting a number that has the property of being prime from a given set of numbers;
Example 1: I have a bag containing numbers in which there are twice as many composites as primes. What is the probability that the first number you blindly pick from it is a prime. This is the basis for setting odds in games such as roulette.
(ii) The probability of determining that a given integer is prime.
Example 2: I give you a -digit combination lock along with a -digit number . The lock only opens if you set the combination to a proper factor of which is greater than . What is the probability that the first combination you try will open the lock. This is the basis for RSA encryption, which provides the cryptosystem used by many banks for securing their communications.
4. In case 3(i), if the precise proportion of primes to non-primes in is definable, then clearly too is definable.
However if is the set of all integers, and we cannot define a precise ratio of primes to composites in , but only an order of magnitude such as , then equally obviously cannot be defined in (see Chapter 2, p.9, Theorem 2.1, here).
5. In case 3(ii) the following paper proves , since it shows that whether or not a prime divides a given integer is independent of whether or not a prime divides :
Not only does it immediately follow that (see here), but we further have that , with a binomial standard deviation. Hence, even though we cannot define the probability of selecting a number from the set of all natural numbers that has the property of being prime, can be treated as the de facto probability that a given is prime, with all its attended consequences for various prime-counting functions and the Riemann Zeta function (see here).
Abstract We define the residues for all and all such that if, and only if, is a divisor of . We then show that the joint probability of two unequal primes dividing any integer is the product . We conclude that the prime divisors of any integer are independent; and that the probability of being a prime is . The number of primes less than or equal to is thus given by . We further show that , and conclude that does not oscillate.
We begin by defining the residues for all and all as below:
Definition 1: where .
Since each residue cycles over the values , these values are all incongruent and form a complete system of residues  .
It immediately follows that:
Lemma 1: if, and only if, is a divisor of .
By the standard definition of the probability of an event , we conclude that:
Lemma 2: For any and any given integer , the probability that is , and the probability that is .
We note the standard definition:
Definition 2: Two events and are mutually independent for if, and only if, .
The prime divisors of any integer are mutually independent
We then have that:
Lemma 3: If and are two primes where then, for any , we have:
where and .
Proof: The numbers , where and , are all incongruent and form a complete system of residues  . Hence:
By Lemma 2:
The lemma follows.
If and in Lemma 3, so that both and are prime divisors of , we conclude by Definition 2 that:
Corollary 1: .
Corollary 2: .
Theorem 1: The prime divisors of any integer are mutually independent. 
The probability that is a prime
Since is a prime if, and only if, it is not divisible by any prime , it follows immediately from Lemma 2 and Lemma 3 that:
Lemma 4: For any , the probability of an integer being a prime is the probability that for any if .
Lemma 5: .
The Prime Number Theorem
The number of primes less than or equal to is thus given by:
Lemma 6: .
This now yields the Prime Number Theorem:
Theorem 2: .
Proof: From Lemma 6 and Mertens’ Theorem that
it follows that:
The behaviour of as is then seen by differentiating the right hand side, where we note that :
Hence does not oscillate as .
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.
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.
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 ; from which we conclude that integer factorising cannot be in the class 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.