Tag Archive

You are currently browsing the tag archive for the ‘extra-terrestrial’ tag.

The significance of evidence-based reasoning for Computational Complexity

December 20, 2018 in computational complexity, Foundations of mathematics, Foundations of mathematics, logic and computation, logic and computation, Philosophy, Theory of Numbers | Tags: algorithmically computable, algorithmically verifiable, Aristotle's particularisation, arithmetic, Church Turing Thesis, completed infinity, computationalism, consistency, constructive, determinism, EPR paradox, extra-terrestrial, finitary, first order, FOL, formal, formal language, foundations, Gödel, Gödelian argument, Goodstein, Hilbert, human, human intelligence, logic, Lucas, mathematical truth, mathematics, mechanical intelligence, mechanist, natural numbers, omega-consistency, para-consistency, Peano Arithmetic PA, philosophy, reasoning, Rosser, Rule C, science, semantic, SETI, simple functional language, standard interpretation, syntactic, Tarski, Turing, undecidable, unpredictability | Leave a comment

Why primality is polynomial time, but factorisation is not

Differentiating between the signature of a number and its value

A brief review: The significance of evidence-based reasoning

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

and

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

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

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

The significance of evidence-based reasoning for Computational Complexity

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

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

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

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

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

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

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

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

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

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

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

Are the prime divisors of an integer mutually independent?

In this paper I address the query:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Author’s working archives & abstracts of investigations

Can Gödel be held guilty of implicit obfuscation?

December 6, 2018 in Foundations of mathematics, Foundations of mathematics, logic and computation, logic and computation, Philosophy | Tags: algorithmically computable, algorithmically verifiable, Aristotle's particularisation, arithmetic, Church Turing Thesis, completed infinity, computationalism, consistency, constructive, determinism, EPR paradox, extra-terrestrial, finitary, first order, FOL, formal, formal language, foundations, Gödel, Gödelian argument, Goodstein, Hilbert, human, human intelligence, logic, Lucas, mathematical truth, mathematics, mechanical intelligence, mechanist, natural numbers, omega-consistency, para-consistency, Peano Arithmetic PA, philosophy, reasoning, Rosser, Rule C, science, semantic, SETI, simple functional language, standard interpretation, syntactic, Tarski, Turing, undecidable, unpredictability | 3 comments

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

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

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

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

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

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

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

but that:

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

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

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

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

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

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

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

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

We cannot, though, conclude from this that:

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

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

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

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

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

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

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

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

by:

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

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

and:

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

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

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

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

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

from:

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

Moreover, we note that:

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

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

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

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

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

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

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

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

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

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

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

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

Author’s working archives & abstracts of investigations

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

December 1, 2018 in Foundations of mathematics, logic and computation, logic and computation, Philosophy | Tags: algorithmically computable, algorithmically verifiable, Aristotle's particularisation, arithmetic, Church Turing Thesis, completed infinity, computationalism, consistency, constructive, determinism, EPR paradox, extra-terrestrial, finitary, first order, FOL, formal, formal language, foundations, Gödel, Gödelian argument, Goodstein, Hilbert, human, human intelligence, logic, Lucas, mathematical truth, mathematics, mechanical intelligence, mechanist, natural numbers, omega-consistency, para-consistency, Peano Arithmetic PA, philosophy, reasoning, Rosser, Rule C, science, semantic, SETI, simple functional language, standard interpretation, syntactic, Tarski, Turing, undecidable, unpredictability | 2 comments

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

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

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

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

and

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

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

We begin by noting that:

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

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

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

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

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

(6) Gödel then defines a primitive recursive relation, say $Q(x,y) \equiv xBSUBy$ , such that, for any $m,n$ :

$mBSUBn$ is true if, and only if, $m$ happens to be a GN that can be decomposed into a proof sequence whose last member is some PA formula $[F(n)]$ , and $n$ happens to be a GN that decomposes into the PA-formula $[F(u)]$ with only one variable $[u]$ .

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

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

C: Gödel’s reasoning in Peano Arithmetic

(8) Now, by Gödel’s Theorem VII (a standard representation theorem of arithmetic), $xBSUBy$ can be expressed in PA by some (formally well-defined) formula $[\neg R(x,y)]$ such that, for any $m,n$ :

(a) If $mBSUBn$ is true, then $[\neg R(m,n)]$ is PA-provable;

(b) If $\neg mBSUBn$ is true, then $[R(m,n)]$ is PA-provable.

(9) Further, by (6) and (8), for any $m,n$ , if $n$ is the GN of $F(x)$ then:

(a) If $mBSUBn$ is true, then $[R(m,n)]$ is PA-provable; and $m$ is a PA-proof of $[F(n)]$ ;

(b) If $\neg mBSUBn$ is true, then $[\neg R(m,n)]$ is PA-provable; and $m$ is not a PA-proof of $[F(n)]$ .

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

(a) Let $q$ be the GN of the formula $[R(x,y)]$ defined in (8).

(b) Let $p$ be the GN of $[(\forall x)R(x,y)]$ .

(d) Let $17Gen\ r$ be the GN of $[(\forall x)R(x,p)]$ .

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

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

(12) If we now substitute $p$ for $n$ , and $[(\forall x)R(x,p)]$ for $[F(n)]$ , in (9) we have (since $p$ is the GN of $[(\forall x)R(x,y)]$ ) that:

(i) If $mBSUBp$ is true, then $[R(\neg m,p)]$ is PA-provable; whence $m$ is a PA-proof of $[(\forall x)R(x,p)]$ ;

(ii) If $\neg mBSUBp$ is true, then $[R(m,p)]$ is PA-provable; whence $m$ is not a PA-proof of $[(\forall x)R(x,p)]$ .

Hence $n = p$ answers Query 1 affirmatively.

D: Gödel’s conclusions

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

By (12)(i), if $mSUBp$ is true for some $m$ , then both $[R(\neg m,p)]$ and $[(\forall x)R(x,p)]$ are PA-provable—a contradiction since, by Generalisation in PA, the latter implies that $[R(m,p)]$ is provable in PA.

Hence $[(\forall x)R(x,p)]$ , whose GN is $17Gen\ r$ , is not provable in PA if PA is consistent.

(14) Moreover, if PA is assumed to also be $\omega$ -consistent (which means that we cannot have a PA-provable formula $[\neg (\forall x)F(x)]$ such that $[F(m)]$ is also provable in PA for any given numeral $[m]$ ) then:

By (13), $m$ is not a PA-proof of $[(\forall x)R(x,p)]$ for any given $m$ ; whence $[R(m,p)]$ is PA-provable for any given $m$ by (12)(ii).

Hence $[\neg (\forall x)R(x,p)]$ , whose GN is $Neg(17Gen r)$ , is not provable in PA.

E: Gödel’s $[(\forall x)R(x,p)]$ does not refer to itself

We note that Gödel’s formula $[(\forall x)R(x,p)]$ —whose GN is $17Gen\ r$ — does not refer to itself since it is defined in terms of the natural number $p$ , and not in terms of the natural number $17Gen\ r$ .

F: Somewhere, far beyond Gödel

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

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

$\bullet$ There can be no interpretation of Gödel’s definition of his formally undecidable arithmetical proposition $[(\forall x)R(x),p]$ over the domain of the natural numbers—whether expressed mathematically or in any language of common discourse—that could lead to a contradiction;

$\bullet$ Gödel’s $[(\forall x)R(x,p)]$ is not a formally undecidable arithmetical proposition, since $[\neg (\forall x)R(x,p)]$ is PA-provable (see Corollary 8.2 of this paper).

Author’s working archives & abstracts of investigations

Does AI pose an existential threat to mankind?

July 10, 2016 in Education, Foundations of mathematics, logic and computation, logic and computation, Philosophy | Tags: algorithmically computable, algorithmically decidable, algorithmically verifiable, ambiguity, arithmetic, Cantor, completed infinity, computation, computationalism, consistency, constructive, determinism, extra-terrestrial, finitary, first order, FOL, formal, formal language, foundations, Gödel, Gödelian argument, Hilbert, human intelligence, interpretation, languages of adequate expression, languages of effective communication, logic, logical paradoxes, mathematical truth, mathematics, mechanical intelligence, natural number, natural numbers, non-locality, Peano Arithmetic PA, peano axioms, philosophy, reasoning, science, set theory, SETI, simple functional language, standard interpretation, Tarski, truth, Turing, Turing machine, uncomputable, undecidable | Leave a comment

(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

Misunderstanding Gödel: The significance of Feynman’s cover-up factor

November 8, 2013 in Foundations of mathematics, logic and computation, Philosophy | Tags: algorithmically computable, algorithmically verifiable, Aristotle's particularisation, arithmetic, Church Turing Thesis, completed infinity, computationalism, consistency, constructive, determinism, EPR paradox, extra-terrestrial, finitary, first order, FOL, formal, formal language, foundations, Gödel, Gödelian argument, Goodstein, Hilbert, human, human intelligence, logic, Lucas, mathematical truth, mathematics, mechanical intelligence, mechanist, natural numbers, omega-consistency, para-consistency, Peano Arithmetic PA, philosophy, reasoning, Rosser, Rule C, science, semantic, SETI, simple functional language, standard interpretation, syntactic, Tarski, Turing, undecidable, unpredictability | Leave a comment

See also (i) this later publication by Sebastian Grève, where he concludes that “… while Gödel indeed showed some significant understanding of Wittgenstein here, ultimately, Wittgenstein perhaps understood Gödel better than Gödel understood himself”; and (ii) this note on Rosser’s Rule C and Wittgenstein’s objections on purely philosophical considerations to Gödel’s reasoning and conclusions, where we show that, although not at all obvious (perhaps due to Gödel’s overpoweringly plausible presentation of his interpretation of his own formal reasoning over the years) what Gödel claimed to have proven is not—as suspected and held by Wittgenstein—supported by Gödel’s formal argumentation.

A: Misunderstanding Gödel’s Theorems VI and XI: Incompleteness and Undecidability

In an informal essay, “Misunderstanding Gödel’s Theorems VI and XI: Incompleteness and Undecidability“, DPhil candidate Sebastian Grève at The Queen’s College, Oxford, attempts to come to terms with what he subjectively considers:

“… has not been properly addressed as such by philosophers hitherto as of great philosophical importance in our understanding of Gödel’s Incompleteness Theorems.”

Grève’s is an unusual iconoclastic perspective:

“This essay is an open enquiry towards a better understanding of the philosophical significance of Gödel’s two most famous theorems. I proceed by a discussion of several common misunderstandings, led by the following four questions:

1) Is the Gödel sentence true?

2) Is the Gödel sentence undecidable?

3) Is the Gödel sentence a statement?

4) Is the Gödel sentence a sentence?

Asking these questions in this order means to trace back the steps of Gödel’s basic philosophical interpretation of his formal results. What I call the basic philosophical interpretation is usually just taken for granted by philosopher’s writing about Gödel’s theorems.”

In a footnote Grève acknowledges Wittgenstein’s influence by suggesting that:

“This essay can be read as something like a free-floating interpretation of the theme of Wittgenstein’s remarks on Gödel’s Incompleteness Theorems in Wittgenstein: 1978[RFM], I-(III), partly following Floyd: 1995 but especially Kienzler: 2008, and constituting a reply to inter alia Rodych: 2003”.

B: Why we may see the trees, but not the forest

We note that Grève’s four points are both overdue and well-made:

1. Is the Gödel sentence true?

Grève’s objection that standard interpretations are obscure when they hold the Gödel sentence as being intuitively true deserves consideration (see this post).

The ‘truth’ of the sentence should and does—as Wittgenstein stressed and suggested—follow objectively from the axioms and rules of inference of arithmetic.

2. Is the Gödel sentence undecidable?

Grève’s observation that the ‘undecidability’ of the Gödel sentence conceals a philosophically questionable assumption is well-founded.

The undecidability in question follows only on the assumption of ‘ $\omega$ -consistency’ made explicitly by Gödel.

This assumption is actually logically equivalent to the philosophically questionable assertion that from the provability of $[\neg(\forall x)R(x)]$ we may conclude the existence of some numeral $[n]$ for which $[R(n)]$ is provable.

Since Rosser’s proof implicitly makes this assumption by means of his logically questionable Rule C, his claim of avoiding omega-consistency for arithmetic is illusory.

3. Is the Gödel sentence a statement?

Grève rightly holds that the Gödel sentence should be treated as a valid statement within the formal arithmetic S, since it is structurally defined as a well-formed formula of S.

4. Is the Gödel sentence a sentence?

Grève’s concern about whether the Gödel sentence of S is a valid arithmetical proposition under interpretation also seems to need serious philosophical consideration.

It can be argued (see the comment following the proof of Lemma 9 of this preprint) that the way the sentence is formally defined as the universal quantification of an instantiationally (but not algorithmically) defined arithmetical predicate does not yield an unequivocally defined arithmetical proposition in the usual sense under interpretation.

In this post ^[*] we shall not only echo Grève’s disquietitude, but argue further that Gödel’s interpretation and assessment of his own formal reasoning in his seminal 1931 paper on formally undecidable arithmetical propositions is, essentially, a post-facto imposition that continues to influence standard expositions of Gödel’s reasoning misleadingly.

Feynman’s cover-up factor

Our thesis is influenced by physicist Richard P. Feynman, who started his 1965 Nobel Lecture with a penetrating observation:

We have a habit in writing articles published in scientific journals to make the work as finished as possible, to cover up all the tracks, to not worry about the blind alleys or describe how you had the wrong idea first, and so on. So there isn’t any place to publish, in a dignified manner, what you actually did in order to get to do the work.

That such `cover up’ may have unintended—and severely limiting—consequences on a discipline is suggested by Gödel’s interpretation, and assessment, of his own formal reasoning in his seminal 1931 paper on formally undecidable arithmetical propositions (Go31).

Thus, in his informal preamble to the result that he intended to prove formally, Gödel wrote (cf. Go31, p.9):

The analogy of this result with Richard’s antinomy is immediately evident; there is also a close relationship with the Liar Paradox … Thus we have a proposition before us which asserts its own unprovability.

Further, interpreting the significance of his formal reasoning as having established the existence of a formally undecidable arithmetical proposition that is, however, decidable by meta-mathematical arguments, Gödel noted that:

The precise analysis of this remarkable circumstance leads to surprising results concerning consistency proofs of formal systems … (Go31, p.9)

The true reason for the incompleteness which attaches to all formal systems of mathematics lies, as will be shown in Part II of this paper, in the fact that the formation of higher and higher types can be continued into the transfinite (c.f., D. Hilbert, `Über das Unendliche’, Math. Ann. 95, p. 184), while, in every formal system, only countable many are available. Namely, one can show that the undecidable sentences which have been constructed here always become decidable through adjunction of suitable high types (e.g. of the type $\omega$ to the system $P$ . A similar result also holds for the axiom systems of set theory. (Go31, p.28, footnote 48a)

The explicit thesis of this foundational paper is that the above interpretation is an instance of a `cover up’—in Feynman’s sense—which appears to be a post-facto imposition that, first, continues to echo in and misleadingly ^[1] influence standard expositions of Gödel’s reasoning when applied to a first-order Peano Arithmetic, PA, and, second, that it obscures the larger significance of the genesis of Gödel’s reasoning.

As Gödel’s various remarks in Go31 suggest, this possibly lay in efforts made at the dawn of the twentieth century—largely as a result of Brouwer’s objections (Br08)—to define unambiguously the role that the universal and existential quantifiers played in formal mathematical reasoning.

That this issue is critical to Gödel’s reasoning in Go31, but remains unresolved in it, is obscured by his powerful presentation and interpretation.

So, to grasp the underlying mathematical significance of Gödel’s reasoning, and of what he has actually achieved, one may need to avoid focusing (as detailed in the previous posts on A foundational perspective on the semantic and logical paradoxes; in this post on undecidable Gödelian propositions, and in this preprint on undecidable Gödelian propositions):

$\bullet$ on the analogy of the so-called `Liar paradox’;

$\bullet$ on Gödel’s interpretation of his arithmetical proposition as asserting its own formal unprovability in his formal Peano Arithmetic P (Go31, pp.9-13);

$\bullet$ on his interpretation of the reasons for the `incompleteness’ of P; and

$\bullet$ on his assessment and interpretation of the formal consequences of such `incompleteness’.

We show in this paper that, when applied to PA ^[2], all of these obscure the deeper significance of what Gödel actually achieved in Go31.

C: Hilbert: If the $\omega$ -Rule is true, can P be completed?

Instead, Gödel’s reasoning may need to be located specifically in the context of Hilbert’s Program (cf. Hi30, pp.485-494) in which he proposed an $\omega$ -rule as a finitary means of extending a Peano Arithmetic—such as his formal system P in Go31—to a possible completion (i.e. to logically showing that, given any arithmetical proposition, either the proposition, or its negation, is formally provable from the axioms and rules of inference of the extended Arithmetic).

Hilbert’s $\omega$ -Rule: If it is proved that the P-formula [ $F(x)$ ] interprets as a true numerical formula for each given P-numeral [ $x$ ], then the P-formula $[(\forall x)F(x)]$ may be admitted as an initial formula (axiom) in P.

It is likely that Gödel’s 1931 paper evolved out of attempts to prove Hilbert’s $\omega$ -rule in the limited—and more precise—sense that if a formula [ $F(n)$ ] is provable in P for each given numeral [ $n$ ], then the formula [ $(\forall x)F(x)$ ] must be provable in P.

Now, if we meta-assume Hilbert’s $\omega$ -rule for P, then it follows that, if P is consistent, then there is no P-formula [ $F(x)$ ] for which, first, [ $\neg(\forall x)F(x)$ ] is P-provable and, second, [ $F(n)$ ] is P-provable for any given P-numeral [ $n$ ].

Gödel defined a consistent Peano Arithmetic with the above property as additionally $\omega$ -consistent (Go31, pp.23-24).

D: The significance of $\omega$ -consistency

To place the significance of $\omega$ -consistency in a current perspective, we note that the standard model of the first order Peano Arithmetic PA (cf. Me64, p.107; Sc67, p.23, p.209; BBJ03, p.104) presumes ^[3] that the standard interpretation M of PA (under which the PA-formula [ $(\exists x)R(x)$ ], which is merely an abbreviation for $[\neg(\forall x)\neg R(x)]$ , interprets as true if, and only if, $R(n)$ holds for some natural number $n$ under M) is sound (cf. BBJ03, p.174).

Clearly, if such an interpretation of the existential quantifier is sound, it immediately implies that PA is necessarily $\omega$ -consistent ^[4].

Since Brouwer’s main objection was to Hilbert’s presumption that such an interpretation of the existential quantifier is sound, Gödel explicitly avoided this assumption in his seminal 1931 paper (Go31, p.9) in order to ensure that his reasoning was acceptable as “constructive” and “intuitionistically unobjectionable” (Go31, p.26).

He chose, instead, to present the formal undecidability of his arithmetical proposition—and the consequences arising from it—as explicitly conditional on the assumption of the formal property of $\omega$ -consistency for his Peano Arithmetic P under the unqualified—and, as we show below, mistaken—belief that:

PA is $\omega$ -consistent (Go31, p.28, footnote 48a).

E: Gödel: If the $\omega$ -Rule is true, P cannot be completed

Now, Gödel’s significant achievement in Go31 was the discovery that, if P is consistent, then it was possible to construct a P-formula, [ $R(x)$ ] ^[5], such that $[R(n)]$ is P-provable for any given P-numeral [ $n$ ] (Go31, p.25(2)), but [ $(\forall x)R(x)$ ] is P-unprovable (Go31, p.25(1)).

However, it becomes apparent from his remarks in Go31 that Gödel considered his more significant achievement the further argument that, if P is assumed $\omega$ -consistent, then both [ $(\forall x)R(x)$ ] and [ $\neg (\forall x)R(x)$ ] ^[6] are P-unprovable, and so P is incomplete!

This is the substance of Gödel’s Theorem VI (Go31, p.24).

Although this Theorem neither validated nor invalidated Hilbert’s $\omega$ -rule, it did imply that assuming the rule led not to the completion of a Peano Arithmetic as desired by Hilbert, but to its essential incompletability!

F: The $\omega$ -Rule is inconsistent with PA

Now, apparently, the possibility neither considered by Gödel in 1931, nor seriously since, is that a formal sytem of Peano Arithmetic—such as PA—may be consistent and $\omega$ –inconsistent.

If so, one would ascribe this omission to the `cover up’ factor mentioned by Feynman, since a significant consequence of Gödel’s reasoning—in the first half of his proof of his Theorem VI—is that it actually establishes PA as $\omega$ –inconsistent (as detailed in Corollary 9 of this preprint and Corollary 4 of this post).

In other words, we can logically show for Gödel’s formula [ $R(x)$ ] that [ $\neg(\forall x)$ $R(x)$ ] is PA-provable, and that [ $R(n)$ ] is PA-provable for any given PA-numeral [ $n$ ].

Consequently, Gödel’s Theorem VI is vacuously true for PA, and it also follows that Hilbert’s $\omega$ -Rule is inconsistent with PA!

G: Need: A paradigm shift in interpreting the quantifiers

Thus Gödel’s unqualified belief that:

“PA is $\omega$ -consistent“

was misplaced, and Brouwer’s objection to Hilbert’s presumption—that the above interpretation of the existential quantifier is sound—was justified; since, if PA is consistent, then it is provably $\omega$ –inconsistent, from which it follows that the standard interpretation M of PA is not sound.

Hence we can no longer interpret `[ $\neg(\forall x)F(x)$ ] is true’ maximally under the standard interpretation of PA as:

(i) The arithmetical relation $F(n)$ is not always ^[7] true.

However, since the theorems of PA—when treated as Boolean functions—are Turing-computable as always true under a sound finitary interpretation $\beta$ of PA, we can interpret `[ $\neg(\forall x)F(x)$ ] is true’ minimally as:

(ii) The arithmetical relation $F(n)$ is not Turing-computable as always true.

This interpretation allows us to conclude from Gödel’s meta-mathematical argument that we can construct a PA-formula [ $(\forall x)R(x)$ ] that is unprovable in PA, but which is true under a sound interpretation of PA ^[8] although we may now no longer conclude from Gödel’s reasoning that there is an undecidable arithmetical PA-proposition.

Moreover, the interpretation admits an affirmative answer to Hilbert’s query: Is PA complete or completeable?

H: PA is algorithmically complete

In outline, the basis from which this conclusion follows formally is that:

(i) Gödel’s proof of the essential incompleteness of any formal system of Peano Arithmetic (Go31, Theorem VI, p.24) explicitly assumes that the arithmetic is $\omega$ -consistent;

(ii) Rosser’s extension of Gödel’s proof of the essential incompleteness of any formal system of Peano Arithmetic (cf. Ro36, Theorem II, p.233) implicitly presumes that the Arithmetic is $\omega$ -consistent (as detailed in this post);

(iii) PA is $\omega$ –inconsistent (as detailed in Corollary 9 of this preprint);

(iv) The classical `standard’ interpretation of PA (cf. Me64, section \S 2, pp.49-53; p107) over the structure [ $N$ ]—defined as { $N$ (the set of natural numbers); $=$ (equality); $'$ (the successor function); $+$ (the addition function); $\ast$ (the product function); $0$ (the null element)}— does not define a finitary model of PA (as detailed in the paper titled Evidence-Based Interpretations of PA presented at IACAP/AISB Turing 2012, Birmingham, UK in July 2012);

(v) We can define a sound interpretation $\beta$ of PA—in terms of Turing-computability—which yields a finitary model of PA, but which does not admit a non-standard model for PA (as detailed in this paper);

(vi) PA is algorithmically complete in the sense that an arithmetical proposition $F$ defines a Turing-machine TM $_{F}$ which computes $F$ as true under $\beta$ if, and only if, the corresponding PA-formula [ $F$ ] is PA-provable (as detailed in Section 8 of this preprint).

I: Gödel’s proof of his Theorem XI does not withstand scrutiny

Since Gödel’s proof of his Theorem XI (Go31, p.36)—in which he claims to show that the consistency of his formal system of Peano Arithmetic P can be expressed as a P-formula which is not provable in P—appeals critically to his Theorem VI, it follows that this proof cannot be applied to PA.

However, we show below that there are other, significant, reasons why Gödel’s reasoning in this proof must be treated as classically objectionable per se.

J: Why Gödel’s interpretation of the significance of his Theorem XI is classically objectionable

Now, in his Theorem XI, Gödel constructs a formula [ $W$ ] ^[9] in P and assumes that [ $W$ ] translates—under a sound interpretation of P—as an arithmetical proposition that is true if, and only if, a specified formula of P is unprovable in P.

Now, if there were such a P-formula, then, since an inconsistent system necessarily proves every well-formed formula of the system, it would follow that a proof sequence within P proves that P is consistent.

However, Gödel shows that his formula [ $W$ ] is not P-provable (Go31, p.37).

He concludes that the consistency of any formal system of Peano Arithmetic is not provable within the Arithmetic. ^[10]

K: Defining meta-propositions of P arithmetically

Specifically, Gödel first shows how 46 meta-propositions of P can be defined by means of primitive recursive functions and relations (Go31, pp.17-22).

These include:

( $\#23$ ) A primitive recursive relation, Form( $x$ ), which is true if, and only if, $x$ is the Gödel-number of a formula of P;

( $\#45$ ) A primitive recursive relation, $xBy$ , which is true if, and only if, $x$ is the Gödel-number of a proof sequence of P whose last formula has the Gödel-number $y$ .

Gödel assures the constructive nature of the first 45 definitions by specifying (cf. Go31, p.17, footnote 34):

Everywhere in the following definitions where one of the expressions ` $\forall x$ ‘, ` $\exists x$ ‘, ` $\epsilon x$ (There is a unique $x$ )’ occurs it is followed by a bound for $x$ . This bound serves only to assure the recursive nature of the defined concept.

Gödel then defines a meta-mathematical proposition that is not recursive:

( $\#46$ ) A proposition, $Bew(x)$ , which is true if, and only if, $(\exists y)yBx$ is true.

Thus $Bew(x)$ is true if, and only if, $x$ is the Gödel-number of a provable formula of P.

L: Expressing arithmetical functions and relations in P

Now, by Gödel’s Theorem VII (Go31, p.29), any recursive relation, say $Q(x)$ , can be represented in P by some, corresponding, arithmetical formula, say [ $R(x)$ ], such that, for any natural number $n$ :

If $Q(n)$ is true, then [ $R(n)$ ] is P-provable;

If $Q(n)$ is false, then [ $\neg R(n)$ ] is P-provable.

However, Gödel’s reasoning in the first half of his Theorem VI (Go31, p.25(1)) establishes that the above representation does not extend to the closure of a recursive relation, in the sense that we cannot assume:

If $(\forall x)Q(x)$ is true (i.e, $Q(n)$ is true for any given natural number), then $[(\forall x)R(x)]$ is P-provable.

In other words, we cannot assume that, even though the recursive relation $Q(x)$ is instantiationally equivalent to a sound interpretation of the P-formula [ $R(x)$ ], the number-theoretic proposition $(\forall x)Q(x)$ must, necessarily, be logically equivalent to the—correspondingly sound—interpretation of the P-formula [ $(\forall x)R(x)$ ].

The reason: In recursive arithmetic, the expression ` $(\exists x)F(x)$ ‘ is an abbreviation for the assertion:

(*) There is some (at least one) natural number $n$ such that $F(n)$ holds.

In a formal Peano Arithmetic, however, the formula `[ $(\exists x)F(x)$ ]’ is simply an abbreviation for `[ $\neg (\forall x)\neg F(x)$ ]’, which, under a sound finitary interpretation of the Arithmetic can have the verifiable translation:

(**) The relation $\neg F(x)$ is not Turing-computable as always true.

Moreover, Gödel’s Theorem VI establishes that we cannot conclude (*) from (**) without risking inconsistency.

Consequently, although a primitive recursive relation may be instantiationally equivalent to a sound interpretation of a P-formula, we cannot assume that the existential closure of the relation must have the same meaning as the interpretation of the existential closure of the corresponding P-formula.

However this, precisely, is the presumption made by Gödel in the proof of Theorem XI, from which he concludes that the consistency of P can be expressed in P, but is not P-provable.

M: Ambiguity in the interpreted `meaning’ of formal mathematical expressions

The ambiguity in the `meaning’ of formal mathematical expressions containing unrestricted universal and existential closure under an interpretation was emphasised by Wittgenstein (Wi56):

Do I understand the proposition “There is . . .” when I have no possibility of finding where it exists? And in so far as what I can do with the proposition is the criterion of understanding it … it is not clear in advance whether and to what extent I understand it.

N: Expressing “P is consistent” arithmetically

Specifically, Gödel defines the notion of “P is consistent” classically as follows:

P is consistent if, and only if, Wid(P) is true

where Wid(P) is defined as:

$( \exists x) (Form(x) \wedge \neg Bew(x))$

This translates as:

There is a natural number $n$ which is the Gödel-number of a formula of P, and this formula is not P-provable.

Thus, Wid(P) is true if, and only if, P is consistent.

O: Gödel: “P is consistent” is always expressible in P

However, Gödel, then, presumes that:

(i) Wid(P) can be represented by some formula [ $W$ ] of P such that “[ $W$ ] is true” and “Wid(P) is true” are logically equivalent (i.e., have the same meaning) under a sound interpretation of P;

(ii) if the recursive relation, $Q(x, p)$ (1931, p24(8.1)), is represented by the P-formula [ $R(x, p)$ ], then the proposition “[ $(\forall x)R(x, p)$ ] is true” is logically equivalent to (i.e., has the same meaning as) “ $(\forall x)Q(x, p)$ is true” under a sound interpretation of P.

P: The loophole in Gödel’s presumption

Although, (ii), for instance, does follow if “[ $(\forall x)R(x, p)$ ] is true” translates as “ $R(x, p)$ is Turing-computable as always true”, it does not if “[ $(\forall x)R(x, p)$ ] is true” translates as “ $R(x, p)$ is constructively computable as true for any given natural number $n$ , but it is not Turing-computable as true for any given natural number $n$ “.

So, if [ $W$ ], too, interprets as an arithmetical proposition that is constructively computable as true, but not Turing-computable as true, then the consistency of P may be provable instantiationally in P ^[11].

Hence, at best, Gödel’s reasoning can only be taken to establish that the consistency of P is not provable algorithmically in P.

Gödel’s broader conclusion only follows if P purports to prove its own consistency algorithmically.

However, Gödel’s particular argument, based on his definition of Wid(P), does not support this claim.

Bibliography

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

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

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

Hi27 David Hilbert. 1927. The Foundations of Mathematics. In The Emergence of Logical Empiricism. 1996. Garland Publishing Inc.

Hi30 David Hilbert. 1930. Die Grundlegung der elementaren Zahlenlehre. Mathematische Annalen. Vol. 104 (1930), pp. 485-494.

Me64 Elliott Mendelson. 1964. Introduction to Mathematical Logic. Van Norstrand. pp.145-146.

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

Sc67 Joseph R. Schoenfield. 1967. Mathematical Logic. Reprinted 2001. A. K. Peters Ltd., Massachusetts.

Tu36 Alan Turing. 1936. On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, ser. 2. vol. 42 (1936-7), pp.230-265; corrections, Ibid, vol 43 (1937) pp. 544-546.

Wi56 Ludwig Wittgenstein. 1956. Remarks on the Foundations of Mathematics. Edited by G. H. von Wright and R. Rhees. Translated by G. E. M. Anscombe. Basil Blackwell, Oxford.

Notes

Return to *: Edited and transcribed from this 2010 preprint. Some of its pedantic conclusions regarding the `soundness’ of the standard interpretation of PA (and consequences thereof) should, however, be treated as qualified by the broader philosophical perspective that treats the standard and algorithmic interpretations of PA as complementary—rather than contradictory—interpretations (as detailed in this post).

Return to 1: We show in this paper that, from a finitary perspective (such as that of this preprint) the proofs of both of Gödel’s celebrated theorems in Go31—his Theorem VI postulating the existence of an undecidable proposition in his formal Peano Arithmetic, P, and his Theorem XI postulating that the consistency of P can be expressed, but not proven, within P—hold vacuously for first order Peano Arithmetic, PA.

Return to 2: Although we have restricted ourselves in this paper to considering only PA, the arguments would—prima facie—apply equally to any first-order theory that contains sufficient Peano Arithmetic in Gödel’s sense (cf. Go31, p.28(2)), by which we mean that every primitive recursive relation is definable within the theory in the sense of Gödel’s Theorems V (Go31, p.22) and VII (Go31, p.29).

Return to 3: Following Hilbert.

Return to 4: Since we cannot, then, have that $[\neg(\forall x)\neg R(x)]$ is PA-provable and that $[\neg R(n)]$ is also PA-provable for any given numeral $[n]$ .

Return to 5: This corresponds to the P-formula of his paper that Gödel defines, and refers to, only by its Gödel-number $r$ (cf. Go31, p.25, eqn.(12)).

Return to 6: Gödel refers to these P-formulas only by their Gödel-numbers $17Gen \hspace{+.5ex} r$ and $Neg(17Gen \hspace{+.5ex} r)$ respectively (cf. Go31, p.25, eqn.13).

Return to 7: i.e., for any given natural number $n$ .

Return to 8: Because the arithmetical relation $R(x)$ is a Halting-type of relation (cf.Tu36, $\S 8$ ) that is constructively computable as true for any given natural number $n$ , although it is not Turing-computable as true for any given natural number $n$ (as detailed in this post).

Return to 9: Gödel refers to it only by its Gödel-number $w$ (Go31, p.37).

Return to 10: Gödel’s broader conclusion—unchallenged so far but questionable—was that his reasoning could be validly “… carried over, word for word, to the axiom systems of set theory M and of classical mathematics A”.

Return to 11: That Gödel was open to such a possibility in 1931 is evidenced by his remark (Go31, p37) that “… it is conceivable that there might be finitary proofs which cannot be represented in P (or in M or A)”.

Author’s working archives & abstracts of investigations

Notation, non-standard concepts and definitions used in these investigations

September 7, 2013 in Foundations of mathematics, logic and computation, Philosophy | Tags: algorithmically computable, algorithmically verifiable, Aristotle's particularisation, arithmetic, Church Turing Thesis, completed infinity, computationalism, consistency, constructive, determinism, EPR paradox, extra-terrestrial, finitary, first order, FOL, formal, formal language, foundations, Gödel, Gödelian argument, Goodstein, Hilbert, human, human intelligence, logic, Lucas, mathematical truth, mathematics, mechanical intelligence, mechanist, natural numbers, omega-consistency, para-consistency, Peano Arithmetic PA, philosophy, reasoning, Rosser, Rule C, science, semantic, SETI, simple functional language, standard interpretation, syntactic, Tarski, Turing, undecidable, unpredictability | Leave a comment

Use of square brackets

Unless otherwise obvious from the context, we use square brackets to indicate that the contents represent a symbol or a formula—of a formal theory—generally assumed to be well-formed unless otherwise indicated by the context.

In other words, expressions inside the square brackets are to be only viewed syntactically as juxtaposition of symbols that are to be formed and manipulated upon strictly in accordance with specific rules for such formation and manipulation—in the manner of a mechanical or electronic device—without any regards to what the symbolism might represent semantically under an interpretation that gives them meaning.

Use of an asterisk

Unless otherwise obvious from the context, we use an asterisk to indicate that the associated expression is to be interpreted semantically with respect to some well-defined interpretation.

Explanatory comments

We have taken some liberty in emphasising standard definitions selectively, and interspersing our arguments liberally with comments and references, generally of a foundational nature.

These are intended to reflect our underlying thesis that essentially arithmetical problems appear more natural when expressed—and viewed—within an arithmetical perspective of an interpretation of PA that appeals to the evidence provided by a deterministic algorithm.

Since a deterministic algorithm has only one possible move from a given configuration such a perspective, by its very nature, cannot appeal implicitly to transfinite concepts.

Evidence

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

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

Aristotle’s particularisation

This holds that from an assertion such as:

‘It is not the case that: For any given $x,\ P^{*}(x)$ does not hold’

usually denoted symbolically by ‘ $\neg(\forall x)\neg P^{*}(x)$ ‘, we may always validly infer in the classical, Aristotlean, logic of predicates ^[1] that:

‘There exists an unspecified $x$ such that $P^{*}(x)$ holds’

usually denoted symbolically by ‘ $(\exists x)P^{*}(x)$ ‘.

Aristotle’s particularisation (AP) is essentially the semantic postulation that from the negation of a universal we may always deduce the existence of a contrafactual. It is necessarily true over finite domains.

Expressed more formally:

Aristotle’s particularisation under an interpretation

If the formula $[\neg (\forall x) \neg F(x)]$ of a first order language $S$ interprets as true under a sound interpretation of $S$ , then we may always conclude that there must be some object $s$ in the domain $D$ of the interpretation such that, if the formula $[F(x)]$ interprets as the unary relation $F^{*}(x)$ in $D$ , then the proposition $F^{*}(s)$ is true under the interpretation.

The significance of Aristotle’s particularisation for the first-order predicate calculus

We note that in a formal language the formula ‘ $[(\exists x)P(x)]$ ‘ is an abbreviation for the formula ‘ $[\neg(\forall x)\neg P(x)]$ ‘.

The commonly accepted interpretation of this formula—and a fundamental tenet of classical logic unrestrictedly adopted as intuitively obvious by standard literature ^[2] that seeks to build upon the formal first-order predicate calculus—tacitly appeals to Aristotlean particularisation.

However, L. E. J. Brouwer had noted in his seminal 1908 paper on the unreliability of logical principles ^[3] that the commonly accepted interpretation of this formula is ambiguous if interpretation is intended over an infinite domain.

Brouwer essentially argued that, even supposing the formula ‘ $[P(x)]$ ‘ of a formal Arithmetical language interprets as an arithmetical relation denoted by ‘ $P^{*}(x)$ ‘, and the formula ‘ $[\neg(\forall x)\neg P(x)]$ ‘ as the arithmetical proposition denoted by ‘ $\neg(\forall x)\neg P^{*}(x)$ ‘, the formula ‘ $[(\exists x)P(x)]$ ‘ need not interpret as the arithmetical proposition denoted by the usual abbreviation ‘ $(\exists x)P^{*}(x)$ ‘; and that such postulation is invalid as a general logical principle in the absence of a means for constructing some putative object $a$ for which the proposition $P^{*}(a)$ holds in the domain of the interpretation.

Hence we shall follow the convention that the assumption that ‘ $(\exists x)P^{*}(x)$ ‘ is the intended interpretation of the formula ‘ $[(\exists x)P(x)]$ ‘—which is essentially the assumption that Aristotle’s particularisation holds over the domain of the interpretation—must always be explicit.

The significance of Aristotle’s particularisation for PA

In order to avoid intuitionistic objections to his reasoning, Kurt Gödel introduced the syntactic property of $\omega$ -consistency ^[4] as an explicit assumption in his formal reasoning in his seminal 1931 paper on formally undecidable arithmetical propositions ^[5].

Gödel explained at some length ^[6] that his reasons for introducing $\omega$ -consistency explicitly was to avoid appealing to the semantic concept of classical arithmetical truth in Aristotle’s logic of predicates (which presumes Aristotle’s particularisation).

The two concepts are meta-mathematically equivalent in the sense that, if PA is consistent, then PA is $\omega$ -consistent if, and only if, Aristotle’s particularisation holds under the standard interpretation of PA ^[7].

We note that Aristotle’s particularisation is a non-constructive—and logically fragile—semantic deduction rule. It is reflected in classical first order deduction either by some similarly non-constructive syntactic rule of natural deduction—such as Rosser’s Rule C ^[7.1]—or by the assumption that FOL is $\omega$ -consistent.

The structure $\mathbb{N}$

The structure of the natural numbers—namely:

$N$ (the set of natural numbers);

$=$ (equality);

$S$ (the successor function);

$+$ (the addition function);

$\ast$ (the product function);

$0$ (the null element).

The axioms of the first-order Peano Arithmetic PA

$PA_{1}$ : $[(x_{1} = x_{2}) \rightarrow ((x_{1} = x_{3}) \rightarrow (x_{2} = x_{3}))]$ ;

$PA_{2}$ : $[(x_{1} = x_{2}) \rightarrow (x_{1}^{\prime} = x_{2}^{\prime})]$ ;

$PA_{3}$ : $[0 \neq x_{1}^{\prime}]$ ;

$PA_{4}$ : $[(x_{1}^{\prime} = x_{2}^{\prime}) \rightarrow (x_{1} = x_{2})]$ ;

$PA_{5}$ : $[( x_{1} + 0) = x_{1}]$ ;

$PA_{6}$ : $[(x_{1} + x_{2}^{\prime}) = (x_{1} + x_{2})^{\prime}]$ ;

$PA_{7}$ : $[( x_{1} \star 0) = 0]$ ;

$PA_{8}$ : $[( x_{1} \star x_{2}^{\prime}) = ((x_{1} \star x_{2}) + x_{1})]$ ;

$PA_{9}$ : For any well-formed formula $[F(x)]$ of PA:

$[F(0) \rightarrow (((\forall x)(F(x) \rightarrow F(x^{\prime}))) \rightarrow (\forall x)F(x))]$ .

Generalisation in PA

If $[A]$ is PA-provable, then so is $[(\forall x)A]$ .

Modus Ponens in PA

If $[A]$ and $[A \rightarrow B]$ are PA-provable, then so is $[B]$ .

The standard interpretation of PA

The standard interpretation $\mathcal{I}_{PA(\mathbb{N},\ Standard)}$ of PA over the structure $\mathbb{N}$ is the one in which the logical constants have their ‘usual’ interpretations ^[8] in Aristotle’s logic of predicates (which subsumes Aristotle’s particularisation), and ^[9]:

(a) the set of non-negative integers is the domain;

(b) the symbol $[0]$ interprets as the integer $0$ ;

(d) the symbols $[+]$ and $[*]$ interpret as ordinary addition and multiplication;

(e) the symbol $[=]$ interprets as the identity relation.

Simple consistency

A formal system S is simply consistent if, and only if, there is no S-formula $[F(x)]$ for which both $[(\forall x)F(x)]$ and $[\neg(\forall x)F(x)]$ are S-provable.

$\omega$ -consistency

A formal system S is $\omega$ -consistent if, and only if, there is no S-formula $[F(x)]$ for which first $[\neg(\forall x)F(x)]$ is S-provable, and second $[F(a)]$ is S-provable for any given S-term $[a]$ .

Soundness (formal system – non-standard)

A formal system S is sound under an interpretation $\mathcal{I}_{S}$ with respect to a domain $\mathbb{D}$ if, and only if, every theorem $[T]$ of S translates as ‘ $[T]$ is true under $\mathcal{I}_{S}$ in $\mathbb{D}$ ‘.

Soundness (interpretation – non-standard)

An interpretation $\mathcal{I}_{S}$ of a formal system S is sound with respect to a domain $\mathbb{D}$ if, and only if, S is sound under the interpretation $\mathcal{I}_{S}$ over the domain $\mathbb{D}$ .

Soundness in classical logic

In classical logic, a formal system $S$ is sometimes defined as ‘sound’ if, and only if, it has an interpretation; and an interpretation is defined as the assignment of meanings to the symbols, and truth-values to the sentences, of the formal system. Moreover, any such interpretation is defined as a model ^[10] of the formal system.

This definition suffers, however, from an implicit circularity: the formal logic $L$ underlying any interpretation of $S$ is implicitly assumed to be ‘sound’.

The above definitions seek to avoid this implicit circularity by delinking the defined ‘soundness’ of a formal system under an interpretation from the implicit ‘soundness’ of the formal logic underlying the interpretation.

This admits the case where, even if $L_{1}$ and $L_{2}$ are implicitly assumed to be sound, $S+L_{1}$ is sound, but $S+L_{2}$ is not.

Moreover, an interpretation of $S$ is now a model for $S$ if, and only if, it is sound.

Algorithmic verifiability

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

Tarskian interpretation of an arithmetical language verifiably in terms of the computations of a simple functional language

We show in the Birmingham paper that the ‘algorithmic verifiability’ of the formulas of a formal language which contain logical constants can be inductively defined under an interpretation in terms of the ‘algorithmic verifiability’ of the interpretations of the atomic formulas of the language; further, that the PA-formulas are decidable under the standard interpretation of PA over $\mathbb{N}$ if, and only if, they are algorithmically verifiable under the interpretation. ^[11]

Algorithmic computability

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

Tarskian interpretation of an arithmetical language algorithmically in terms of the computations of a simple functional language

We show in the Birmingham paper that the ‘algorithmic computability’ of the formulas of a formal language which contain logical constants can also be inductively defined under an interpretation in terms of the ‘algorithmic computability’ of the interpretations of the atomic formulas of the language; further, that the PA-formulas are decidable under an algorithmic interpretation of PA over $\mathbb{N}$ if, and only if, they are algorithmically computable under the interpretation. ^[12]

Algorithmic verifiability vis à vis algorithmic computability

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

From the point of view of a finitary mathematical philosophy—which is the constraint within which an applied science ought to ideally operate—the significant difference between the two concepts could be expressed by saying that we may treat the decimal representation of a real number as corresponding to a physically measurable limit ^[14]—and not only to a mathematically definable limit—if and only if such representation is definable by an algorithmically computable function. ^[15]

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

References

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

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

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

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

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

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

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

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

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

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

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

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

Me64 Elliott Mendelson. 1964. Introduction to Mathematical Logic. Van Norstrand. pp.145-146.

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

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

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

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

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

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

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

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

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

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

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

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

An13 … 2013. A suggested mathematical perspective for the $EPR$ argument. Presented on 7’th April at the workshop on `Logical Quantum Structures‘ at UNILOG’2013, 4’th World Congress and School on Universal Logic, 29’th March 2013 – 7’th April 2013, Rio de Janeiro, Brazil.\

Notes

Return to 1: HA28, pp.58-59.

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

Return to 3: Br08.

Return to 4: The significance of $\omega$ -consistency for the formal system PA is highlighted in An12.

Return to 5: Go31, p.23 and p.28.

Return to 6: In his introduction on p.9 of Go31.

Return to 7: For details see An12.

Return to 7.1: See Ro53, pp.127-136.

Return to 8: See Me64, p.49.

Return to 9: See Me64, p.107.

Return to 10: We follow the definition in Me64, p.51.

Return to 11: We show in An12 that the concept of Algorithmic verifiability is also well-defined under the standard interpretation of PA over $\mathbb{N}$ .

Return to 12: We show in An12 that the concepts of Algorithmic verifiability and Algorithmic computability are both well-defined under the standard interpretation of PA over $\mathbb{N}$ ; moreover they identify distinctly different subsets of the well-defined PA formulas.

Return to 13: We note that the concept of ‘algorithmic computability’ is essentially an expression of the more rigorously defined concept of ‘realizability’ in Kl52, p.503.

Return to 14: In the sense of a physically ‘completable’ infinite sequence (as needed to resolve Zeno’s paradox).

Return to 15: This point is addressed in more detail in An13.

Return to 16: See Appendix B of this preprint Is Gödel’s undecidable proposition an ‘ad hoc’ anomaly?.

Author’s working archives & abstracts of investigations

The reals are denumerable: The finitary solution that Hilbert probably would not have foreseen for the First of his Twenty Three problems!

September 5, 2013 in Foundations of mathematics, logic and computation, Philosophy | Tags: algorithmically computable, algorithmically verifiable, Aristotle's particularisation, arithmetic, cardinality, Church Turing Thesis, completed infinity, computationalism, consistency, constructive, continuum hypothesis, determinism, EPR paradox, extra-terrestrial, finitary, first order, FOL, formal, formal language, foundations, Gödel, Gödel’s Beta-function, Gödelian argument, Goodstein, Hilbert, human, human intelligence, logic, Lucas, mathematical truth, mathematics, mechanical intelligence, mechanist, natural numbers, omega-consistency, para-consistency, Peano Arithmetic PA, philosophy, real number, reasoning, Rosser, Rule C, science, semantic, SETI, simple functional language, standard interpretation, syntactic, Tarski, Turing, undecidable, unpredictability | Leave a comment

Two perspectives on Hilbert’s First and Second Problems

In the Birmingham paper ‘Evidence-Based Interpretations of PA’, we introduced the distinction between algorithmic verifiability and algorithmic computability.

We showed how the distinction naturally helped distinguish between a finitary algorithmic interpretation $\mathcal{I}_{PA(N,\ Algorithmic)}$ of PA, and the non-finitary standard interpretation $\mathcal{I}_{PA(N,\ Standard)}$ of PA.

We then showed how the former yielded a finitary proof of consistency for PA, as demanded by the second of Hilbert’s celebrated 23 problems.

In the previous post, we also highlighted why the the non-finitary standard interpretation $\mathcal{I}_{PA(N,\ Standard)}$ of PA does not yield a finitary proof of consistency for PA.

Cantor’s Continuum Hypothesis

We now show that the difference between the conclusions suggested by finitary reasoning and those suggested by non-finitary reasoning in the previous pages (as in the case of Goodstein’s argument) is reflected further in the differing status of the Continuum Hypothesis (the first of Hilbert’s 23 problems) when viewed from finitary and non-finitary perspectives as detailed below.

The non-finitary set-theoretical perspective

The non-finitary set-theoretical perspective on the Continuum Hypothesis is well-known, and described succintly by Topologist Peter Nyikos in a short expository lecture given at the University of Auckland in May, 2000:

“In 1900, David Hilbert gave a seminal lecture in which he spoke about a list of unsolved problems in mathematics that he deemed to be of outstanding importance. The first of these was Cantor’s continuum problem, which has to do with infinite numbers with which Cantor revolutionised set theory. The smallest infinite number, $\aleph_{0}$ , `aleph-nought,’ gives the number of positive whole numbers. A set is of this cardinality if it is possible to list its members in an arrangement such that each one is encountered after a finite number (however large) of steps. Cantor’s revolutionary discovery was that the points on a line cannot be so listed, and so the number of points on a line is a strictly higher infinite number ( $c$ , `the cardinality of the continuum’) than $\aleph_{0}$ . Hilbert’s First Problem asks whether any infinite subset of the real line is of one of these two cardinalities. The axiom that this is indeed the case is known as the Continuum Hypothesis (CH). …

Gödel [1940] also gave a partial solution to Hilbert’s First Problem by showing that the Continuum Hypothesis (CH) is consistent if the usual Zermelo-Fraenkel (ZF) axioms for set theory are consistent. He produced a model, known as the Constructible Universe, of the ZF axioms in which both the Axiom of Choice (AC) and the CH hold. Then Cohen showed in 1963 that the negations of these axioms are also consistent with ZF; in particular, CH can fail while AC holds in a model of ZF.”

… Hilbert’s First and Second Problems and the foundations of mathematics, Topology Atlas Document # taic-52, Topology Atlas Invited Contributions vol. 9, no. 3 (2004) 6 pp.

Is CH a Deﬁnite Mathematical Problem?

Well, the non-finitary set-theoretical formulation of the Continuum Hypothesis isn’t, according to Solomon Feferman who, in a presentation at the inaugural Paul Bernays Lectures, ETH, Zurich, Sept. 12, 2012, restated in his presentation that:

$\bullet$ My view: No; in fact it is essentially indeﬁnite (“inherently vague”).

$\bullet$ That is, the concepts of arbitrary set and function as used in its formulation even at the level of P(N) are essentially indeﬁnite.

… Why isn’t the Continuum Problem on the Millennium ($1,000,000) Prize List? CSLI Workshop on Logic, Rationality and Intelligent Interaction, Stanford, June 1, 2013.

Feferman sought to place in perspective the anti-Platonistic basis for his belief by quoting:

“Those who argue that the concept of set is not sufﬁciently clear to ﬁx the truth-value of CH have a position which is at present difﬁcult to assail. As long as no new axiom is found which decides CH, their case will continue to grow stronger, and our assertion that the meaning of CH is clear will sound more and more empty.”

… D. A. Martin, Hilbert’s ﬁrst problem: The Continuum Hypothesis, in Mathematical Developments arising from Hilbert Problems, Felix E. Browder, Rutgers University, Editor – American Mathematical Society, 1976, 628 pp.

A finitary arithmetical perspective

However a possible candidate for a finitary arithmetical perspective (as proposed in the previous pages of these investigations) is reflected in the following:

Theorem: There is no set whose cardinality is strictly between the cardinality $\aleph_{0}$ of the integers and the cardinality $2^{\aleph_{0}}$ of the real numbers.

Proof: By means of Gödel’s $\beta$ -function $\beta(b,\ c,\ i)$ , we can show that if $r(n)$ denotes the $n^{th}$ digit in the decimal expansion $\sum_{n=1}^{\infty}r(n).10^{-n}$ of a putatively given real number R in the interval $[0,\ 1]$ then, for any given natural number $k$ , we can define an arithmetical function $R(k,\ n)$ such that:

$r(n) = R(k,\ n)$ for all $1 \leq n \leq k$ .

Since Gödel’s $\beta$ -function is primitive recursive, it follows that every putatively given real number R can be uniquely corresponded to an algorithmically verifiable arithmetical function $R(x)$ within the first order Peano Arithmetic PA, where we define $R(x)$ by:

$R(n) = R(k,\ n)$ for all $1 \leq n \leq k$ ,

and $k$ is selected such that:

$R(k,\ n) = r(n)$ for all $1 \leq n \leq k$ .

(For the purist, the above conclusion can be justified by the argument in this preprint.)

Definition: Algorithmically verifiable function

A number-theoretical function $F(x)$ is algorithmically verifiable if, and only if, for any given natural number $n$ , there is an algorithm $AL_{(F,\ n)}$ which can provide objective evidence for deciding the value of each formula in the finite sequence $\{F(1), F(2), \ldots, F(n)\}$ .

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

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

Definition: Algorithmically computable function

A number theoretical function $F(x)$ is algorithmically computable if, and only if, there is an algorithm $AL_{F}$ that can provide objective evidence for deciding the value of each formula in the denumerable sequence $\{F(1), F(2), \ldots\}$ .

Cantor’s diagonal argument

From a finitary arithmetical perspective, Cantor’s diagonal argument simply shows that there are algorithmically verifiable functions which are not algorithmically computable.

The correspondence is unique because, if R and S are two different putatively given reals in the interval $[0,\ 1]$ , then there is always some $m$ for which $r(m) \neq s(m)$ . Hence we can always find corresponding arithmetical functions $R(m,\ n)$ and $S(m,\ n)$ such that:

$r(n) = R(m,\ n)$ for all $1 \leq n \leq m$ .

$s(n) = S(m,\ n)$ for all $1 \leq n \leq m$ .

$R(m,\ m) \neq S(m,\ m)$ .

Since PA is first order, the cardinality of the reals in the interval $[0,\ 1]$ cannot, therefore, exceed that of the integers. The theorem follows. $\hfill \Box$

In other words, the Continuum Hypothesis is trivially true from a finitary perspective because of the seemingly heretical conclusion that: $\aleph_{0} = 2^{\aleph_{0}}$ , an answer that Hilbert would probably never have envisaged for the first of the celebrated twenty three problems that he bequethed to posterity!

Skolem’s (apparent) paradox

It is an answer that should, however, give comfort to the shades of Thoralf Skolem. In his 1922 address delivered in Helsinki before the Fifth Congress of Scandinavian Mathematicians, Skolem improved upon both the argument and statement of Löwenheim’s 1915 theorem—subsequently labelled as the:

(Downwards) Löwenheim-Skolem Theorem

If a first-order proposition is satisfied in any domain at all, then it is already satisfied in a denumerably infinite domain.

Skolem then cautioned about unrestrictedly (and meta-mathematically) corresponding putative mathematical entities across domains of different axiom systems, and drew attention to a:

“… peculiar and apparently paradoxical state of affairs. By virtue of the axioms we can prove the existence of higher cardinalities, of higher number classes, and so forth. How can it be, then, that the entire domain $B$ can already be enumerated by means of the finite positive integers? The explanation is not difficult to find. In the axiomatization, ‘set’ does not mean an arbitrarily defined collection; the sets are nothing but objects that are connected with one another through certain relations expressed by the axioms. Hence there is no contradiction at all if a set $M$ of the domain $B$ is non-denumerable in the sense of the axiomatization; for this means merely that within $B$ there occurs no one-to-one mapping $\Phi$ of $M$ onto $Z_{o}$ (Zermelo’s number sequence). Nevertheless there exists the possibility of numbering all objects in $B$ , and therefore also the elements of $M$ , by means of the positive integers; of course such an enumeration too is a collection of certain pairs, but this collection is not a ‘set’ (that is, it does not occur in the domain $B$ ).”

… 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, p.295.

What do you think? Does the above argument apply to the finite ordinals? If so, is ZF inconsistent, or is it $\omega$ -consistent?

Author’s working archives & abstracts of investigations

How mechanical intelligences and human intelligences can reason in contradictory, yet complementary, ways!

September 4, 2013 in Foundations of mathematics, logic and computation, Philosophy | Tags: algorithmically computable, algorithmically verifiable, Aristotle's particularisation, arithmetic, Church Turing Thesis, completed infinity, computationalism, consistency, constructive, determinism, EPR paradox, extra-terrestrial, finitary, first order, FOL, formal, formal language, foundations, Gödel, Gödelian argument, Goodstein, Hilbert, human, human intelligence, logic, Lucas, mathematical truth, mathematics, mechanical intelligence, mechanist, natural numbers, omega-consistency, para-consistency, Peano Arithmetic PA, philosophy, reasoning, Rosser, Rule C, science, semantic, SETI, simple functional language, standard interpretation, syntactic, Tarski, Turing, undecidable, unpredictability | Leave a comment

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

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

Structures

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

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

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

Interpretations

For instance the Birmingham paper provides:

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

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

Aristotle’s particularisation

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

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

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

Consistency of Arithmetic

In the Birmingham paper we also show that:

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

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

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

This suggests that:

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

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

$\omega$ -consistency

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

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

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

Arithmetical undecidability

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

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

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

Completed Infinity

A significant consequence is that:

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

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

Non-standard models of PA

A further consequence of this is that:

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

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

Algorithmically computable truth and algorithmically verifiable truth

The Birmingham paper also suggests that:

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

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

Categoricity and incompleteness of Arithmetic

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

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

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

How intelligences reason

This suggests that:

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

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

Communication between intelligences: SETI

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

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

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

Determinism, Unpredictability and the EPR paradox

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

$\bullet$ Finitary reasoning admits the EPR paradox.

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

The Gödelian argument

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

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

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

Effective computability

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

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

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

Church Turing Thesis

As also the nature of CT, since:

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

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

Goodstein’s Theorem

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

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

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

There’s more …

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

What do you think?

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

Author’s working archives & abstracts of investigations

Mathematics does not need a new foundation; it only needs to make its implicit assumptions explicit!

September 1, 2013 in Foundations of mathematics, logic and computation, Philosophy | Tags: algorithmically computable, algorithmically verifiable, Aristotle's particularisation, arithmetic, Church Turing Thesis, completed infinity, computationalism, consistency, constructive, determinism, EPR paradox, extra-terrestrial, finitary, first order, FOL, formal, formal language, foundations, Gödel, Gödelian argument, Goodstein, Hilbert, human, human intelligence, logic, Lucas, mathematical truth, mathematics, mechanical intelligence, mechanist, natural numbers, omega-consistency, para-consistency, Peano Arithmetic PA, philosophy, reasoning, Rosser, Rule C, science, semantic, SETI, simple functional language, standard interpretation, syntactic, Tarski, Turing, undecidable, unpredictability | Leave a comment

Aristotle’s particularisation: A grey area in our accepted foundational concepts

We shall now argue that what mathematics needs is not a new foundation, but a greater awareness of the nature of its existing foundations.

In particular, it is the thesis of these investigations that almost all of the unresolved philosophical issues in the foundations of mathematics reflect the fact that the nature and role of Aristotle’s particularisation is left implicit when it is postulated over infinite domains.

Perhaps that is the unintended consequence of ignoring Hilbert’s efforts to integrate the concept formally into first order logic by formally defining universal and existential quantification through the introduction of his $\epsilon$ -operator.

Semantic postulation of Aristotle’s particularisation

Aristotle’s particularisation (AP) is the postulation that from the negation of a universal we may always deduce the existence of a contrafactual.

(It is necessarily true over finite domains.)

More formally:

Aristotle’s particularisation under an interpretation

(We note that Aristotle’s particularisation is a non-constructive—and logically fragile—semantic deduction rule. It is reflected in classical first order deduction either by some similarly non-constructive syntactic rule of natural deduction—such as Rosser’s Rule C—or by the assumption that FOL is $\omega$ -consistent.)

Is the price of Aristotle’s particularisation too high?

If so, we shall argue that the price being asked for assuming AP implicitly—instead of explicitly as Hilbert had proposed—may be too high!

Partially because the assumption seems to effectively obscure the far-reaching consequences of the non-finitary nature of AP from immediate view in natural and formal deductive chains.

(And therefore of the first order logic FOL under the implicit assumption of Aristotle’s particularisation.)

For instance, as Carnap’s deduction of the Axiom of Choice in ZF $_{\epsilon}$ illustrates, the non-finitary consequences of assuming AP over infinite domains becomes apparent when the underlying logic is taken as Hilbert’s $\epsilon$ -calculus instead of the classical first order logic FOL.

However, formal deductions apparently prefer to substitute—seemingly arbitrarily—the implicit assumption of AP in the underlying logic by the introduction of `contrived’ formal assumptions such as Gödel’s $\omega$ -consistency or Rosser’s Rule C.

$\omega$ -consistency

A formal system S is $\omega$ -consistent if, and only if, there is no S-formula $[F(x)]$ for which, first, $[\neg(\forall x)F(x)]$ is S-provable and, second, $[F(a)]$ is S-provable for any given S-term $[a]$ .

Rosser’s Rule C

“Since the rule ‘If $(\exists x)F(x)$ , then $F(y)$ ‘ corresponds to a hypothetical act of choice, we shall call it the rule of choice, or more briefly, Rule C.”

… J. Barkley Rosser. Logic for Mathematicians. 1953. McGraw Hill Book Company Inc., New York.

Similarly natural deduction chains apparently prefer to substitute—again seemingly arbitrarily—the implicit assumption of AP in the underlying logic by admitting a Rule of Infinite Induction (transfinite induction).

More importantly, the price may be too high because the implicit assumption of Aristotle’s particularisation in the underlying logic has masked the fact that, without such assumption, FOL is finitarily consistent; and—as we note below—that mathematically significant finitary structures can be built upon it without assuming AP.

Evidence-Based Interpretations of PA

Some consequences of making the assumption of Aristotle’s particularisation explicit are highlighted in `Evidence-Based Interpretations of PA’ that was presented at the AISB/IACAP Turing 2012 conference in Birmingham last year.

We showed there that Tarski’s inductive definitions admit evidence-based interpretations of the first-order Peano Arithmetic PA which allow us to define the satisfaction and truth of the quantified formulas of PA constructively over the domain $N$ of the natural numbers in two essentially different ways:

$\bullet$ In terms of algorithmic verifiabilty; and

$\bullet$ In terms of algorithmic computability.

That there can be even one, let alone two, logically sound (one finitary and one non-finitary) assignments of satisfaction and truth certificates to both the atomic and compound formulas of PA had hitherto been unsuspected!

Definition: Algorithmically verifiable arithmetical truth

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

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

We show in the Birmingham paper (as we shall refer to it hereafter) that the `algorithmic verifiability’ of the formulas of a formal language which contain logical constants can be inductively defined under an interpretation in terms of the `algorithmic verifiability’ of the interpretations of the atomic formulas of the language; further, that the PA-formulas are decidable under the standard interpretation of PA over $N$ if, and only if, they are algorithmically verifiable under the interpretation.

Definition: Algorithmically computable arithmetical truth

We show in the Birmingham paper that the `algorithmic computability’ of the formulas of a formal language which contain logical constants can also be inductively defined under an interpretation in terms of the `algorithmic computability’ of the interpretations of the atomic formulas of the language; further, that the PA-formulas are decidable under an algorithmic interpretation of PA over $N$ if, and only if, they are algorithmically computable under the interpretation.

Algorithmic verifiability vis à vis algorithmic computability

We show in the Birmingham paper that the concepts of Algorithmic verifiability and Algorithmic computability are both well-defined under the standard interpretation of PA over $N$ ; moreover they identify distinctly different subsets of the well-defined PA formulas.

We show in this paper that although every algorithmically computable relation is algorithmically verifiable, the converse is not true.

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

From the point of view of a finitary mathematical philosophy—which is the constraint within which an applied science ought to ideally operate—the significant difference between the two concepts could be expressed (as addressed in more detail in this paper) by saying that we may treat the decimal representation of a real number as corresponding to a physically measurable limit—and not only to a mathematically definable limit—if and only if such representation is definable by an algorithmically computable function.

The finitarily sound algorithmic interpretation $\mathcal{I}_{PA(N,\ Algorithmic)}$ of PA over $N$

We argued from the above distinction that the algorithmically computable PA-formulas can provide a finitarily sound algorithmic interpretation $\mathcal{I}_{PA(N,\ Algorithmic)}$ of PA over the domain $N$ of the natural numbers.

We showed, moreover, that this yields a finitary proof of consistency for PA—as demanded by the Second of Hilbert’s celebrated Twenty Three Problems.

The non-finitarily sound standard interpretation $\mathcal{I}_{PA(N,\ Standard)}$ of PA over $N$

On the other hand, the distinction also suggests that Gerhard Gentzen’s transfinite proof of consistency for PA corresponds to the argument that the algorithmically verifiable PA-formulas of PA provide a non-finitarily sound standard interpretation $\mathcal{I}_{PA(N,\ Standard)}$ of PA over $N$ .

Moreover—as has been generally suspected (perhaps for the reason noted towards the end of this post)—the distinction also suggests why the standard interpretation cannot yield the finitary proof of consistency for PA as demanded by Hilbert.

The distinction between finitary and non-finitary arithmetical reasoning introduced in the Birmingham paper has far reaching consequences

In these pages we shall argue that the power of this simple distinction actually goes far beyond the immediate conclusions drawn in the Birmingham paper.

Reason: We can further constructively define an unambiguous distinction between finitary and non-finitary reasoning, at the level of first order logic itself, which shows that the two are both mutually inconsistent yet complementary!

As can be expected, such a distinction could have far-reaching consequences for the foundations of mathematics, logic and computabiity (which form the focus of the investigations in these pages).

We shall consider some of these in the next post.

Author’s working archives & abstracts of investigations

	Abel Peralta on Can Gödel be held guilty of im…
	Bhupinder Singh Anan… on Can Gödel be held guilty of im…
	Abel Peralta on Can Gödel be held guilty of im…
	Bhupinder Singh Anan… on Why Gödel’s Theorem…
	Abel Peralta on Why Gödel’s Theorem…

Tag Archive

The significance of evidence-based reasoning for Computational Complexity

Can Gödel be held guilty of implicit obfuscation?

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

Does AI pose an existential threat to mankind?

Misunderstanding Gödel: The significance of Feynman’s cover-up factor

Notation, non-standard concepts and definitions used in these investigations

The reals are denumerable: The finitary solution that Hilbert probably would not have foreseen for the First of his Twenty Three problems!

How mechanical intelligences and human intelligences can reason in contradictory, yet complementary, ways!

Mathematics does not need a new foundation; it only needs to make its implicit assumptions explicit!

Readability

Start here

Follow Blog via Email

Search

Recent posts

Blogs I Follow

Recent comments