You are currently browsing the tag archive for the ‘Gödel’s Beta-function’ tag.

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

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

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

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

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

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

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

The Brains blog

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

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

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

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

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

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

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

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

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

III: The Unexplained Intellect: The importance of computability

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

IV: The Unexplained Intellect: Consequences of imperfection

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

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

V: The Unexplained Intellect: The importance of rapport

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

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

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

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

A: Simplifying Mole’s perspective

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

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

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

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

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

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

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

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

B. Support for Mole’s thesis

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

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

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

The Truth Assignments That Differentiate Human Reasoning From Mechanistic Reasoning: The Evidence-Based Argument for Lucas’ Goedelian Thesis

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

C. Algorithmic computability

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

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

D. Algorithmic verifiability

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

H. The importance of Mole’s ‘rapport’

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

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

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

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

Why Hilbert’s and Brouwer’s interpretations of quantification are complementary and not contradictory.’

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

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

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

Author’s working archives & abstracts of investigations

Bhupinder Singh Anand

Advertisements

Preamble

I find a frustrating equivocity[*] in standard literature between the intent behind the definitions of the classes P and NP as explained informally in terms of ‘verifiability’ and ‘decidability’, and the formal definitions of these two classes.

I call it the PvNP Separation Problem.

My understanding of the intent commonly expressed in standard literature is that:

Verifiability: A number-theoretical formula F(x) is verifiable under an interpretation (and should by intent be defined in NP) if, and only if, for any given natural number n, there is a deterministic 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)\}.

Decidability: A number theoretical formula F(x) is decidable under an interpretation (and should by intent be defined in P) if, and only if, there is a deterministic algorithm AL_{F} that can provide objective evidence for deciding the value of each formula in the denumerable sequence \{F(1), F(2), \ldots\}.

In other words, for me ‘decidability’ should imply the existence of a deterministic algorithm that can decide the truth/falsity of each proposition in a well-defined denumerable sequence of propositions; whereas ‘verifiability’ need not imply the existence of a deterministic algorithm that can decide the truth/falsity of each proposition in a well-defined denumerable sequence of propositions.

For reasons and in ways that I cannot quite grasp as yet, it seems to me that standard definitions of the two classes P and NP only muddy the issue by associating the two concepts with terms such as ‘quickly’, ‘polynomial-time’ and ‘non-deterministic’; and by requiring introduction of some corresponding measure/s of computational complexity.

In other words, standard definitions of the two classes assert that:

Verifiability (standard): A number-theoretical formula F(x) is verifiable under an interpretation (and is defined in NP) if, and only if, for any given natural number n, there is a deterministic polynomial-time 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)\}.

Decidability (standard): A number theoretical formula F(x) is decidable under an interpretation (and is defined in P) if, and only if, there is a deterministic polynomial-time algorithm AL_{F} that can provide objective evidence for deciding the value of each formula in the denumerable sequence \{F(1), F(2), \ldots\}.

The following argument attempts to view the consequence for the PvNP problem if we separate the two classes P and NP essentially as intended in the first case above.

The justification for this perspective is the formal distinction between the two concepts of ‘algorithmic verifiability’ and ‘algorithmic computability’ introduced in the Birmingham paper.

The significance that such a distinction may have for the first-order Peano Arithmetic PA in particular—and for the foundations of mathematics, logic and computability in general—has already been suggested in this post.

Abstract

In this investigation we now consider the consequences of separating the classes P and NP logically from a similar—finitary arithmetical rather than computational—perspective.

This perspective too is based on explicitly highlighting that the assignment of satisfaction and truth values to number-theoretic formulas under an interpretation can be constructively defined in two distinctly different ways:

(a) in terms of algorithmic verifiability, and

(b) in terms of algorithmic computability.

From this perspective it can be seen that standard definitions of the classes P and NP implicitly assume without proof that:

Cook’s Thesis: If a propositional formula is algorithmically verifiable in polynomial time, then it is algorithmically computable.

This imples that the differentiation between the two classes is only quantitative, and can therefore be adequately expressed in terms of computational complexity.

However, we argue that there are classically defined arithmetic formulas which are algorithmically verifiable but not algorithmically computable; and so the differentiation between the classes P and NP can also be defined qualitatively, and need not be expressed only in terms of computational complexity.

Specifically, we show how Gödel’s \beta-function uniquely corresponds some real numbers to algorithmically verifiable arithmetical formulas that are not algorithmically computable.[**]

Introduction

“The computability precursors of the classes P and NP are the classes of decidable and c.e. (computably enumerable) languages, respectively. We say that a language L is c.e. i.e. (or semi-decidable) iff L = L(M) for some Turing machine M. We say that L is decidable iff L = L(M) for some Turing machine M which satisfies the condition that M halts on all input strings w. …

Thus the problem Satisfiability is: Given a propositional formula F, determine whether F is satisfiable. To show that this is in NP we define the polynomial-time checking relation R(x, y), which holds iff x codes a propositional formula F and y codes a truth assignment to the variables of F which makes F true.”

… Stephen Cook, The P versus NP Problem, 2000, Clay Mathematical Institute, Providence, USA.

In this investigation we shall argue that standard interpretations—such as the above[1]—of the formal definitions of the classes P and NP leave room for ambiguity.

Specifically, such interpretations fail to explicitly highlight that the assignment of satisfaction and truth values to number-theoretic formulas under an interpretation can be constructively defined in two distinctly different ways[1a]:

(a) in terms of algorithmic verifiability (Definition 1 below);

It immediately follows from this definition that a number-theoretical formula F is algorithmically verifiable under an interpretation (and should therefore be defined in NP) if, and only if, we can define a checking relation R(x, y)[2]—where x codes a propositional formula F and y codes a truth assignment to the variables of F—such that, for any given natural number values (m, n), there is a deterministic algorithm which will finitarily decide whether or not R(m, n) holds over the domain \mathbb{N} of the natural numbers.

(b) in terms of algorithmic computability (Definition 2 below).

It immediately follows from this definition that a number-theoretical formula F is algorithmically computable under an interpretation (and should therefore be defined in P) if, and only if, we can define a checking relation R(x, y)[3]—where x codes a propositional formula F and y codes a truth assignment to the variables of F—such that there is a deterministic algorithm which, for any given natural number values (m, n), will finitarily decide whether or not R(m, n) holds over the domain \mathbb{N} of the natural numbers.

In other words, standard interpretations of the classes P and NP implicitly assume without proof that:

Cook’s Thesis: If a propositional formula is algorithmically verifiable in polynomial-time, then it is algorithmically computable.

It would follow from such a perspective that the differentiation between the classes P and NP is only quantitative, and can therefore be adequately expressed in terms of computational complexity.

However, we shall argue that—since the two concepts are well-defined[3a]—there are classically defined arithmetic formulas which are algorithmically verifiable but not algorithmically computable; and so the differentiation between the classes P and NP is also qualitative, and cannot be adequately expressed in terms of only computational complexity.

The PvNP Separation Problem

Accordingly, in this investigation we shall ignore both Cook’s Thesis and polynomial-time computations, and address instead the following non-standard (NS) formulation of the PvNP Separation Problem in arithmetic:

Non-standard PvNP\ (NS): Is there an arithmetical formula F that is algorithmically verifiable but not algorithmically computable?

We shall first show how Gödel’s \beta-function uniquely corresponds each classically defined real number to an algorithmically verifiable arithmetical formula.

Since classical theory admits the existence of real numbers that are not algorithmically computable[4], we shall conclude that classical theory must also admit the existence of arithmetical formulas that are algorithmically verifiable but not algorithmically computable.

Algorithmically verifiable and algorithmically computable formulas

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

The concept is well-defined in the sense that, first, every atomic number-theoretical formula is algorithmically verifiable as above[6]; further, by Tarski’s definitions[7], 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.

In particular[8], the formulas of the first order Peano Arithmetic PA are constructively decidable under the standard interpretation of PA over the domain \mathbb{N} of the natural numbers if, and only if, they are algorithmically verifiable under the interpretation.[9]

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

This concept too is well-defined in the sense that, first, every atomic number-theoretical formula is algorithmically computable as above[10]; further, by Tarski’s definitions, 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.

In particular[11], the PA-formulas are constructively decidable under an algorithmic interpretation of PA over \mathbb{N} if, and only if, they are algorithmically computable under the interpretation.[12]

We note that:

Lemma 1: There are algorithmically verifiable number theoretical formulas which are not algorithmically computable.

Proof: Let r(n) denote the n^{th} digit in the decimal expression \sum_{i=1}^{\infty}r(i).10^{-i} of a putatively given real number \mathbb{R} in the interval 0 < \mathbb{R} \leq 1.

By the definition of the real number \mathbb{R} as the limit of the Cauchy sequence of rationals \{\sum_{i=1}^{k}r(i).10^{-i}: k = 1, 2, \ldots\}, it follows that r(n) is an algorithmically verifiable number-theoretic function.

Since the set of algorithmically computable reals is countable[13], Cantor’s diagonal argument[14] shows that there are real numbers that are not algorithmically computable.

The Lemma follows. \Box

We note that algorithmic computability implies the existence of a deterministic 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 a deterministic algorithm that can decide the truth/falsity of each proposition in a well-defined denumerable sequence of propositions.[15]

Gödel’s \beta-function

We note next that Gödel’s \beta-function is the primitive recursive number-theoretic function defined by[16]:

Definition 3: \beta (x_{1}, x_{2}, x_{3}) = rm(1+(x_{3}+ 1) \star x_{2}, x_{1}), where rm(x_{1}, x_{2}) denotes the remainder obtained on dividing x_{2} by x_{1}.

We also note that:

Lemma 2: For any non-terminating sequence of values f(0), f(1), \ldots, we can construct natural numbers b_{k},\ c_{k} such that:

(i) j_{k} = max(k, f(0), f(1), \ldots, f(k));

(ii) c_{k} = j_{k}!;

(iii) \beta(b_{k}, c_{k}, i) = f(i) for 0 \leq i \leq k.

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

Now we have the standard definition[18]:

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

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

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

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

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

We also have that:

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

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

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

An arithmetical perspective on the PvNP Separation Problem

We finally argue that:

Theorem 1: There is an arithmetical formula that is algorithmically verifiable but not algorithmically computable under any sound interpretation of PA.

Proof: Let \{r(n)\} be the denumerable sequence defined by the denumerable sequence of digits in the decimal expansion \sum_{i=1}^{\infty}r(i).10^{-i} of a putatively given real number \mathbb{R} in the interval 0 < \mathbb{R} \leq 1.

By Lemma 2, for any given natural number k, there are natural numbers b_{k}, c_{k} such that, for any 1 \leq n \leq k:

\beta(b_{k}, c_{k}, n) = r(n).

By Lemma 3, \beta(x_{1}, x_{2}, x_{3}) is strongly represented in PA by [Bt(x_{1}, x_{2}, x_{3}, x_{4})] such that, for any 1 \leq n \leq k:

If \beta(b_{k}, c_{k}, n) = r(n) then PA proves [Bt(b_{k}, c_{k}, n, r(n))].

We now define the arithmetical formula [R(b_{k}, c_{k}, n)] for any 1 \leq n \leq k by:

[R(b_{k}, c_{k}, n) = r(n)] if, and only if, PA proves [Bt(b_{k}, c_{k}, n, r(n))].

Hence every putatively given real number \mathbb{R} in the interval 0 < \mathbb{R} \leq 1 uniquely corresponds to an algorithmically verifiable arithmetical formula [R(x)] since:

For any k, the primitive recursivity of \beta(b_{k}, c_{k}, n) yields a deterministic algorithm AL_{(\beta, \mathbb{R}, k)} that can provide objective evidence for deciding the unique value of each formula in the finite sequence \{[R(1), R(2), \ldots, R(k)]\} by evidencing the truth under a sound interpretation of PA for:

[R(1) = R(b_{k}, c_{k}, 1)]
[R(b_{k}, c_{k}, 1) = r(1)]

[R(2) = R(b_{k}, c_{k}, 2)]
[R(b_{k}, c_{k}, 2) = r(2)]

[R(k) = R(b_{k}, c_{k}, k)]
[R(b_{k}, c_{k}, k) = r(k)].

The correspondence is unique because, if \mathbb{R} and \mathbb{S} are two different putatively given reals in the interval 0 < \mathbb{R},\ \mathbb{S} \leq 1, then there is always some m for which:

r(m) \neq s(m).

Hence the corresponding arithmetical formulas [R(n)] and [S(n)] are such that:

[R(n) = r(n)] for all 1 \leq n \leq m.

[S(n) = s(n)] for all 1 \leq n \leq m.

[R(m) \neq S(m)].

By Lemma 1, there is an algorithmically uncomputable real number \mathbb{R} such that the corresponding PA formula [(\exists y)(R(x) = y)] is also algorithmically uncomputable, but algorithmically verifiable, under a sound interpretation of PA.

The theorem follows. \Box

An arithmetical perspective on the PvNP problem

We conclude that if we were to unambiguously define the classes P\ (NS) and NP\ (NS) as in Section 1(a) and Section 1(b) respectively, then it would follow that:

Corollary 1: NP \neq P\ (NS).

References

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

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

Mo12 Cristopher Moore. 2012. P vs. NP, Phase Transitions, and Incomputability in the Wild. Presentation given on 18th June 2012 at the Turing Centenary Workshop on The Incomputable at the Kavli Royal Society International Center at Chicheley Hall, Chichely, Buckinghamshire, UK.

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.

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

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

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 *: I am not alone! See for instance this blogpost of Timothy Gower’s representing one extreme; and this plaintive appeal representing the other.

Return to **: For a broader perspective on the relation of Gödel’s \beta-function to this distinction, see this post.

Return to 1: See also Mo12.

Return to 1a: The distinction is explicitly introduced—and its significance in establishing a finitary proof of consistency for the first order Peano Arithmetic PA highlighted—in An12.

Return to 2: If F is a formula of the first order Peano Arithmetic PA, the existence of such a checking relation is assured by An12, Theorem 2.

Return to 3: If F is a PA formula, the existence of such a checking relation is assured by An12, Theorem 3.

Return to 3a: See here. We further note informally here how the distinction between the two concepts may have far-reaching and significant consequences not only for the foundations of mathematics, logic and computability, but also for our perspective on the underlying structure of the laws of nature.

Return to 4: Tu36.

Return to 5: “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 …”; Mu91.

Return to 6: Tu36.

Return to 7: On the inductive assignment of satisfaction and truth values to the formulas of a formal language under an interpretation; Ta33.

Return to 8: An12, Theorem 2, Corollary 2.

Return to 9: We note that the Axiom Schema of Finite Induction can be finitarily verified as true under the standard interpretation of PA with respect to ‘truth’ as defined by the algorithmically verifiable formulas of PA.

Return to 10: Tu36.

Return to 11: An12, Theorem 5.

Return to 12: We note that the Axiom Schema of Finite Induction can be finitarily verified as true under the standard interpretation of PA with respect to ‘truth’ as defined by the algorithmically computable formulas of PA.

Return to 13: Tu36.

Return to 14: Kl52, pp.6-8.

Return to 15: From the point of view of a finitary mathematical philosophy, the significant difference between the two concepts could be expressed (An13) 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.

Return to 16: Me64, p.131, Proposition 3.21.

Return to 17: Me64, p.131, Proposition 3.22.

Return to 18: Me64, p.118.

Return to 19: We use square brackets simply as a convenience in informal argumentation to differentiate between a formal expression and its interpretation over some domain when there is a possibility of confusion between the two.

Return to 20: cf., Me64, p.131, proposition 3.21.

Bhupinder Singh Anand

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 Definite 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 indefinite (“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 indefinite.

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 sufficiently clear to fix the truth-value of CH have a position which is at present difficult 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 first 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

Bhupinder Singh Anand

Readability

Try reading in +125 magnification

Start here

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

Join 84 other followers

Recent posts

George Lakoff

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

LobeLog

Critical Perspectives on U.S. Foreign Policy

What's new

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

Quanta Magazine

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

The Brains Blog

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

Logic Matters

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

A Neighborhood of Infinity

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

Combinatorics and more

Gil Kalai's blog

Mathematics and Computation

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

Foundations of Mathematics, Logic & Computability

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

John D. Cook

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

Shtetl-Optimized

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

Nanoexplanations

the blog of Aaron Sterling

Eric Cavalcanti

Quantum physicist

East Asia Forum

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

Tanya Khovanova's Math Blog

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

The polymath blog

Massively collaborative mathematical projects