You are currently browsing the tag archive for the ‘EPR paradox’ tag.

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

Ferguson’s and Priest’s thesis

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

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

Ferguson and Priest conclude their review by remarking that:

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

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

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

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

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

A struggle reflected so eloquently in this nineteenth century quote:

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

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

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

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

Making sense of mathematical propositions about infinite processes

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

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

The Liar paradox

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

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

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

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

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

Gödel’s influence on Turing’s reasoning

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

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

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

What is logic: using Ockham’s razor

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

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

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

where I introduced the definition:

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

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

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

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

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

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

\bullet Interpret such representations unambiguously; and

\bullet Conclude further:

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

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

Author’s working archives & abstracts of investigations

Bhupinder Singh Anand

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

We investigate whether the probabilistic distribution of prime numbers can be treated as a heuristic model of quantum behaviour, since it too can be treated as a quantum phenomena, with a well-defined binomial probability function that is algorithmically computable, where the conjectured values of \pi(n) differ from actual values with a binomial standard deviation, and where we define a phenomena as a quantum phenomena if, and only if, it obeys laws that can only be represented mathematically by functions that are algorithmically verifiable, but not algorithmically computable.

1. Thesis: The concept of ‘mathematical truth’ must be accountable

The thesis of this investigation is that a major philosophical challenge—which has so far inhibited a deeper understanding of the quantum behaviour reflected in the mathematical representation of some laws of nature (see, for instance, this paper by Eamonn Healey)—lies in holding to account the uncritical acceptance of propositions of a mathematical language as true under an interpretation—either axiomatically or on the basis of subjective self-evidence—without any specified methodology of accountability for objectively evidencing such acceptance.

2. The concept of ‘set-theoretical truth’ is not accountable

Since current folk lore is that all scientific truths can be expressed adequately, and communicated unambiguously, in the first order Set Theory ZF, and since the Axiom of Infinity of ZF cannot—even in principle—be objectively evidenced as true under any putative interpretation of ZF (as we argue in this post), an undesirable consequence of such an uncritical acceptance is that the distinction between the truths of mathematical propositions under interpretation which can be objectively evidenced, and those which cannot, is not evident.

3. The significance of such accountability for mathematics

The significance of such a distinction for mathematics is highlighted in this paper due to appear in the December 2016 issue of Cognitive Systems Research, where we address this challenge by considering the two finitarily accountable concepts of algorithmic verifiability and algorithmic computability (first introduced in this paper at the Symposium on Computational Philosophy at the AISB/IACAP World Congress 2012-Alan Turing 2012, Birmingham, UK).

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

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

(iii) 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, 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—and not only to a mathematically definable limit—if and only if such representation is definable by an algorithmically computable function (Thesis 1 on p.9 of this paper that was presented on 26th June at the workshop on Emergent Computational Logics at UNILOG’2015, 5th World Congress and School on Universal Logic, Istanbul, Turkey).

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

We show in the CSR paper how such accountability helps define finitary truth assignments that differentiate human reasoning from mechanistic reasoning in arithmetic by identifying two, hitherto unsuspected, Tarskian interpretations of the first order Peano Arithmetic PA, under both of which the PA axioms interpret as finitarily true over the domain N of the natural numbers, and the PA rules of inference preserve such truth finitarily over N.

4. The ambit of human reasoning vis à vis the ambit of mechanistic reasoning

One corresponds to the classical, non-finitary, putative standard interpretation of PA over N, and can be treated as circumscribing the ambit of human reasoning about ‘true’ arithmetical propositions.

The other corresponds to a finitary interpretation of PA over N that circumscibes the ambit of mechanistic reasoning about ‘true’ arithmetical propositions, and establishes the long-sought for consistency of PA (see this post); which establishes PA as a mathematical language of unambiguous communication for the mathematical representation of physical phenomena.

5. The significance of such accountability for the mathematical representation of physical phenomena

The significance of such a distinction for the mathematical representation of physical phenomena is highlighted in this paper that was presented on 26th June at the workshop on Emergent Computational Logics at UNILOG’2015, 5th World Congress and School on Universal Logic, Istanbul, Turkey, where we showed how some of the seemingly paradoxical elements of quantum mechanics may resolve if we define:

Quantum phenomena: A phenomena is a quantum phenomena if, and only if, it obeys laws that can only be represented mathematically by functions that are algorithmically verifiable but not algorithmically computable.

6. The mathematical representation of quantum phenomena that is determinate but not predictable

By considering the properties of Gödel’s \beta function (see \S4.1 on p.8 of this preprint)—which allows us to strongly represent any non-terminating sequence of natural numbers by an arithmetical function—it would follow that, since any projection of the future values of a quantum-phenomena-associated, algorithmically verifiable, function is consistent with an infinity of algorithmically computable functions, all of whose past values are identical to the algorithmically verifiable past values of the function, the phenomena itself would be essentially unpredicatable if it cannot be represented by an algorithmically computable function.

However, since the algorithmic verifiability of any quantum phenomena shows that it is mathematically determinate, it follows that the physical phenomena itself must observe determinate laws.

7. Such representation does not need to admit multiverses

Hence (contrary to any interpretation that admits unverifiable multiverses) only one algorithmically computable extension of the function is consistent with the law determining the behaviour of the phenomena, and each possible extension must therefore be associated with a probability that the next observation of the phenomena is described by that particular extension.

8. Is the probability of the future behaviour of quantum phenomena definable by an algorithmically computable function?

The question arises: Although we cannot represent quantum phenomena explicitly by an algorithmically computable function, does the phenomena lend itself to an algorithmically computable probability of its future behaviour in the above sense?

9. Can primes yield a heuristic model of quantum behaviour?

We now show that the distribution of prime numbers denoted by the arithmetical prime counting function \pi(n) is a quantum phenomena in the above sense, with a well-defined probability function that is algorithmically computable.

10. Two prime probabilities

We consider the two probabilities:

(i) The probability P(a) of selecting a number that has the property of being prime from a given set S of numbers;

Example 1: I have a bag containing 100 numbers in which there are twice as many composites as primes. What is the probability that the first number you blindly pick from it is a prime. This is the basis for setting odds in games such as roulette.

(ii) The probability P(b) of determining a proper factor of a given number n.

Example 2: I give you a 5-digit combination lock along with a 10-digit number n. The lock only opens if you set the combination to a proper factor of n which is greater than 1. What is the probability that the first combination you try will open the lock. This is the basis for RSA encryption, which provides the cryptosystem used by many banks for securing their communications.

11. The probability of a randomly chosen number from the set of natural numbers is not definable

Clearly the probability P(a) of selecting a number that has the property of being prime from a given set S of numbers is definable if the precise proportion of primes to non-primes in S is definable.

However if S is the set N of all integers, and we cannot define a precise ratio of primes to composites in N, but only an order of magnitude such as O(\frac{1}{log_{_{e}}n}), then equally obviously P(a) = P(n\ is\ a\ prime) cannot be defined in N (see Chapter 2, p.9, Theorem 2.1, here).

12. The prime divisors of a natural number are independent

Now, the following paper proves P(b) = \frac{1}{\pi(\sqrt{n})}, since it shows that whether or not a prime p divides a given integer n is independent of whether or not a prime q \neq p divides n:

Why Integer Factorising cannot be polynomial time

We thus have that \pi(n) \approx n.\prod_{_{i = 1}}^{^{\pi(\sqrt{n})}}(1-\frac{1}{p_{_{i}}}), with a binomial standard deviation.

Hence, even though we cannot define the probability P(n\ is\ a\ prime) of selecting a number from the set N of all natural numbers that has the property of being prime, \prod_{_{i = 1}}^{^{\pi(\sqrt{n})}}(1-\frac{1}{p_{_{i}}}) can be treated as the putative non-heuristic probability that a given n is a prime.

13. The distribution of primes is a quantum phenomena

The distribution of primes is thus determinate but unpredictable, since it is representable by the algorithmically verifiable but not algorithmically computable arithmetical number-theoretic function Pr(n) = p_{_{n}}, where p_{_{n}} is the n‘th prime.

The Prime Number Generating Theorem and the Trim and Compact algorithms detailed in this 1964 investigation illustrate why the arithmetical number-theoretic function Pr(n) is algorithmically verifiable but not algorithmically computable (see also this Wikipedia proof that no non-constant polynomial function Pr(n) with integer coefficients exists that evaluates to a prime number for all integers n.).

Moreover, although the distribution of primes is a quantum phenomena with probabilty \prod_{_{i = 1}}^{^{\pi(\sqrt{n})}}(1-\frac{1}{p_{_{i}}}), it is easily seen (see Figs. 7-11 on pp.23-26 of this preprint) that the generation of the primes is algorithmically computable.

14. Why the universe may be algorithmically computable

By analogy, this suggests that although the measurable values of some individual properties of particles in the universe over time may represent a quantum phenomena, the universe itself may be algorithmically computable if the laws governing the generation of all the particles in the universe over time are algorithmically computable.

Author’s working archives & abstracts of investigations

Bhupinder Singh Anand

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

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

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 \omegainconsistent, 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 \omegainconsistent (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)”.

Bhupinder Singh Anand

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;

(c) the symbol [S] interprets as the successor operation (addition of 1);

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

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. pp.5-38.

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?.

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

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?

Bhupinder Singh Anand

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

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.

(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

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)\}.

“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

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\}.

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.

Bhupinder Singh Anand

(Paper Presented on 7th April at the workshop on `Logical Quantum Structures‘ at UNILOG’2013, 4th World Congress and School on Universal Logic, 29th March 2013 – 7th April 2013, Rio de Janeiro, Brazil. See also the paper Algorithmically Verifiable Logic vis a vis Algorithmically Computable Logic: Could resolving EPR need two complementary Logics? and presentation on 26th 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.)

Some disturbing features of the standard Copenhagen interpretation of Quantum Theory

Amongst the philosophically disturbing features of the standard Copenhagen interpretation of Quantum Theory[1] are its:

\bullet Essential indeterminateness [2];

\bullet Essential separation of the world into `system’ and `observer’ [3].

\bullet In 1935 Albert Einstein, Boris Podolsky and Nathan Rosen noted [4] that accepting Quantum Theory, but denying these features of the Copenhagen interpretation, logically entails accepting either that the world is non-local [5] (thus contradicting Special Relativity), or that there are hidden variables [6] that would eliminate the need for accepting these features as necesary to any sound interpretation of Quantum Theory.

\bullet In 1952 David Bohm proposed [7] an alternative mathematical development of the existing Quantum Theory (essentially equivalent to it, but based on Louis de Broglie’s pilot wave theory) whose interpretation appealed to hidden variables [8] (presumably hidden natural laws that were implicitly assumed by Bohm to be representable by well-defined classically computable mathematical functions [9]) that eliminated the need for indeterminism and the separation of the world into `system’ and `observer’.

\bullet In 1964 John Stewart Bell showed [10] that any interpretation of Quantum Theory which appeals to (presumably classically computable) hidden variables in the above sense is necessarily non-local.

However, our foundational investigations into an apparently unrelated area [11] suggest that if the above presumption—concerning an appeal by Bohm and Bell to functions that are implicitly assumed to be classically computable—is correct, then the hidden variables in the Bohm-de Broglie interpretation of Quantum Theory could as well be presumed to involve natural laws that are mathematically representable only by functions that are algorithmically verifiable but not algorithmically computable [12] —in which case the interpretation might avoid being held as appealing to `non-locality’.

The underlying perspective of this thesis

The underlying perspective of this thesis is that:

(1) Classical physics assumes that all the observable laws of nature can be mathematically represented in terms of well-defined functions that are algorithmically computable (as defined in the next section).

Since the functions are well-defined, their values are pre-existing and pre-determined as mappings that are capable of being known in their infinite totalities to an omniscient intelligence, such as Laplace’s intellect [13].

(2) However, the overwhelming experimental verification of the mathematical predictions of Quantum Theory suggests that the actual behavior of the real world cannot be assumed as pre-existing and pre-determined in this sense.

In other words, the consequences of some experimental interactions are theoretically incapable of being completely known in advance even to an omniscient intelligence, such as Laplace’s intellect.

So all the observable laws of nature cannot be represented mathematically in terms of functions that are algorithmically computable (as defined in the next section).

(3) Hence, either there is no way of representing all the observable laws of nature mathematically in a deterministic model, or all the observable laws of nature can be represented mathematically in a deterministic model—but in terms of functions that are `computable’ in a non-predictable sense (we define these in the next section as algorithmically verifiable functions).

(4) The Copenhagen interpretation appears to opt for the first option in (3) above, and hold that there is no way of representing all the observable laws of nature mathematically in a deterministic model.

Hence the interpretation is not overly concerned with the seemingly essential non-locality of Quantum Theory, and its conflict with the deterministic mathematical representation of the laws of Special Relativity.

(5) The Bohm-de Broglie interpretation appears to reject the first option in (3) above, and to propose a way of representing all the observable laws of nature mathematically in terms of functions that are presumably taken implicitly to be algorithmically computable.

However, the Bohm-de Broglie interpretation has not so far been viewed as being capable of mathematically representing the seemingly essential non-local feature of Quantum Theory.

Let us therefore, for the moment, consider the second option in (3) above from the perspective suggested by the Birmingham paper; i.e., that the apparently non-local feature of Quantum Theory may actually be indicative of a non-constructive and `counter intuitive-to-human-intelligence’ phenomena in nature that can, however, be mathematically represented by functions that are algorithmically verifiable, but not algorithmically computable.

Algorithmic verifiabilty and algorithmic computability

We define the two concepts [14]:

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 [15] for deciding the truth/falsity of each proposition in the finite sequence \{F(1), F(2), \ldots, F(n)\}.

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\}.

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 [16], 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 [17]—and not only to a mathematically definable limit—if and only if such representation is definable by an algorithmically computable function.

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

Theorem 1: There are mathematical functions that are algorithmically verifiable but not algorithmically computable.

Proof: (a) Since any real number is mathematically definable as the limit of a Cauchy sequence of rational numbers:

Let R(n) denote the n^{th} digit in the decimal expression of the real number R in binary notation.

Then, for any given natural number n, there is an algorithm AL_{(R,\ n)} that can decide the truth/falsity of each proposition in the finite sequence:

\{R(1)=0, R(2)=0, \ldots, R(n)=0\}.

Hence, for any real number R, the relation R(x)=0 is algorithmically verifiable trivially.

(b) Since it follows from Alan Turing’s Halting argument [18] that there are algorithmically uncomputable real numbers:

Let [R(n)] denote the n^{th} digit in the decimal expression of an algorithmically uncomputable real number R in binary notation.

By (a), the relation [R(x)=0] is algorithmically verifiable trivially.

However, by definition there is no algorithm AL_{R} that can decide the truth/falsity of each proposition in the denumerable sequence:

\{[R(1)=0], [R(2)=0], \ldots\}.

Hence the relation [R(x)=0] is algorithmically verifiable but not algorithmically computable. \Box

Some mathematical constants are definable only by algorithmically verifiable but not algorithmically computable functions

We note that:

(i) All the mathematically defined functions known to, and used by, science are algorithmically computable, including those that define transcendental numbers such as \pi,\ e, etc.

They can be computed algorithmically as they are all definable as the limit of some well-defined infinite series of rationals.

(ii) The existence of mathematical constants that are defined by functions which are algorithmically verifiable but not algorithmically computable—suggested most famously by Georg Cantor’s diagonal argument—has been a philosophically debatable deduction.

Such existential deductions have been viewed with both suspicion and scepticism by scientists such as Henri Poincaré, L. E. J. Brouwer, etc., and disputed most vociferously on philosophical grounds by Ludwig Wittgenstein [19].

(iii) A constructive definition of an arithmetical Boolean function [R(x)] that is true (hence algorithmically verifiable [20]) but not provable in Peano Arithmetic (hence algorithmically not computable [21]) was given by Kurt Gödel in his 1931 paper on formally undecidable arithmetical propositions [22].

It was also disputed vociferously by Wittgenstein [23].

(iv) The definition of a number-theoretic function that is algorithmically verifiable but not algorithmically computable was also given by Alan Turing in his 1936 paper on computable numbers [24].

He defined a halting function, say H(n), that is 0 if, and only if, the Turing machine with code number n halts on input n. Such a function is mathematically well-defined, but assuming that it defines an algorithmically computable real number leads to a contradiction.

Turing thereupon concluded the mathematical existence of algorithmically uncomputable real numbers.

(v) A definition of a number-theoretic function that is algorithmically verifiable but not algorithmically computable was given by Gregory Chaitin [25].

He defined a class of constants—denoted by \Omega—which is such that if C(n) is the n^{th} digit in the decimal expression of an \Omega constant, then the function C(x) is algorithmically verifiable but not algorithmically computable.

Some physical constants may be representable by real numbers that are definable only by algorithmically verifiable but not algorithmically computable functions

Now, we note that:

“… the numerical values of dimensionless physical constants are independent of the units used. These constants cannot be eliminated by any choice of a system of units. Such constants include:

\bullet\ \alpha, the fine structure constant, the coupling constant for the electromagnetic interaction (\approx 1/137.036). Also the square of the electron charge, expressed in Planck units. This defines the scale of charge of elementary particles with charge.

\bullet\ \mu or \beta, the proton-to-electron mass ratio, the rest mass of the proton divided by that of the electron (\approx 1836.15). More generally, the rest masses of all elementary particles relative to that of the electron.

\bullet\ \alpha_{s}, the coupling constant for the strong force (\approx 1)

\bullet\ \alpha{G}, the gravitational coupling constant (\approx 10^{-38}) which is the square of the electron mass, expressed in Planck units. This defines the scale of the mass of elementary particles.

At the present time, the values of the dimensionless physical constants cannot be calculated; they are determined only by physical measurement. This is one of the unsolved problems of physics. …

The list of fundamental dimensionless constants decreases when advances in physics show how some previously known constant can be computed in terms of others. A long-sought goal of theoretical physics is to find first principles from which all of the fundamental dimensionless constants can be calculated and compared to the measured values. A successful `Theory of Everything’ would allow such a calculation, but so far, this goal has remained elusive.”

Dimensionless physical constant – Wikipedia.

This suggests that:

Thesis 1: Some of the dimensionless physical constants are only representable in a mathematical language as real numbers that are defined by functions which are algorithmically verifiable, but not algorithmically computable.

In other words, we cannot treat such constants as denoting—even in principle—a measurable limit, as we could a constant that is representable mathematically by a real number that is definable by algorithmically computable functions.

From the point of view of mathematical philosophy, this distinction would be expressed by saying that the sequence of digits in the decimal representation of an `unmeasurable’ physical constant cannot be treated in a mathematical language as a `completed’ infinite sequence, whilst the corresponding sequence in the decimal representation of a `measurable’ physical constant can be treated as a `completed’ infinite sequence.

Zeno’s argument: The dichotomy between a continuous physical reality and its discretely representable mathematical theory

Zeno’s paradoxical arguments highlight the philosophical and theological dichotomy between our essentially `continuous’ perception of the physical reality that we seek to capture with our measurements, and the essential `discreteness’ of any mathematical language of Arithmetic in which we seek to express such measurements.

The distinction between algorithmic verifiability and algorithmic computability of Arithmetical functions can be seen as reflecting the dichotomy mathematically.

Classical laws of nature

For instance, the distinction suggests that classical mechanics can be held as complete with respect to the algorithmically computable representation of the physical world, in the sense that:

Thesis 2: Classical laws of nature determine the nature and behaviour of all those properties of the physical world which are mathematically describable completely at any moment of time t(n) by algorithmically computable functions from a given initial state at time t(0).

Neo-classical laws of nature

On the other hand, the distinction also suggests that:

Thesis 3: Neo-classical laws of nature determine the nature and behaviour of those properties of the physical world which are describable completely at any moment of time t(n) by algorithmically verifiable functions; however such properties are not completely describable by algorithmically computable functions from any given initial state at time t(0).

Since such behaviour [26] follows fixed laws and is determinate (even if not algorithmically predictable by classical laws), Albert Einstein could have been justified in his belief that:

“… God doesn’t play dice with the world”

and in holding that:

“I like to think that the moon is there even if I am not looking at it”.

Incompleteness: Arithmetical analogy

The distinction also suggests that neither classical mechanics nor neo-classical quantum mechanics can be described as `mathematically complete’ with respect to the algorithmically verifiable behaviour of the physical world.

The analogy here is that Gödel showed in 1931 [27] that any formal arithmetic is not mathematically complete with respect to the algorithmically verifiable nature and behaviour of the natural numbers [28].

However it can be argued that the first-order Peano Arithmetic PA is complete [29] with respect to the algorithmically computable nature and behaviour of the natural numbers.

In this sense, the EPR paper may not be entirely wrong in holding that:

“We are thus forced to conclude that the quantum-mechanical description of physical reality given by wave functions is not complete.”

Conjugate properties

The above also suggests that:

Thesis 4: The nature and behaviour of two conjugate properties F_{1} and F_{2} of a particle P that are determined by neo-classical laws are described mathematically at any time t(n) by two algorithmically verifiable, but not algorithmically computable, functions f_{1} and f_{2}.

In other words, it is the very essence of the neo-classical laws determining the nature and behaviour of the particle that—at any time t(n)—we can only determine either f_{1}(n) or f_{2}(n), but not both.

Hence measuring either one makes the other indeterminate as we cannot go back in time.

However, this does not contradict the assumption that any property of an object must obey some deterministic natural law for any possible measurement that is made at any time.

Entangled particles

The above similarly suggests that:

Thesis 5: The nature and behaviour of an entangled property of two particles P and Q is determined by neo-classical laws and are describable mathematically at any time t(n) by two algorithmically verifiable—but not algorithmically computable—functions f_{1} and g_{1}.

In other words, it is the very essence of the neo-classical laws determining the nature and behaviour of the entangled properties of two particles that—at any time t(n)—determining one immediately gives the state of the other without measurement since the properties are entangled.

Again, this does not contradict the assumption that any property of an object must obey some deterministic natural law for any possible measurement that is made at any time.

Nor does it require any information to travel from one particle to another consequent to a measurement.[29a]

Schrödinger’s cat

If [F(x)] is an algorithmically verifiable but not algorithmically computable Boolean function, we can take the query:

Is F(n)=0 for all natural numbers?

as corresponding mathematically to the Schrödinger question:

Is the cat dead or alive at any given time t?

We can then argue that there is no mathematical paradox involved in Schrödinger‘s assertion that the cat is both dead and alive, if we take this to mean that:

I may either assume the cat to be alive until a given time t (in the future), or assume the cat to be dead until the time t, without arriving at any logical contradiction in my existing Quantum description of nature.

In other words:

Once we accept Quantum Theory as a valid description of nature, then there is no paradox in stating that the theory essentially cannot predict the state of the cat at any moment of future time (so the inability to predict does not arise out of a lack of sufficient information about the laws of the system that Quantum theory is describing, but stems from the very nature of these laws).

The mathematical analogy for the above would be:

Once we accept that Peano Arithmetic is consistent [30] and categorical [31] then we cannot deduce from the axioms of PA whether F(n)=0 for all natural numbers, or whether F(n)=1 for some natural number.

Conclusion
To sum up, we suggest that the paradoxical element in the EPR argument may disappear if we could argue that:

(i) All properties of physical reality can be deterministic—in the sense that any physical property can have one, and only one, value at any time t(n)—where the value is completely determined by some natural law which need not, however, be algorithmic.

(ii) There are elements of such a physical reality whose properties at any time t(n) are determined completely in terms of their putative properties at some earlier time t(0).

Such properties are predictable mathematically since they are representable mathematically by algorithmically computable functions.

The Laws of Classical Mechanics describe the nature and behaviour of such physical reality only.

(iii) There can be elements of such a physical reality whose properties at any time t(n) cannot be theoretically determined completely from their putative properties at some earlier time t(0).

Such properties are unpredictable mathematically since they are only representable mathematically by algorithmically verifiable, but not algorithmically computable, functions.

The Laws of Quantum Mechanics describe the nature and behaviour of such physical reality.

The need for constructive mathematical foundations

The following perspective [32] emphasises the need for a universally common, constructive, foundation for the mathematical representation of elements of reality such as those considered above:

“Our investigations lead us to consider the possibilities for `reuniting the antipodes’. The antipodes being classical mathematics (CLASS) and intuitionism (INT).

… It therefore seems worthwhile to explore the `formal’ common ground of classical and intuitionistic mathematics. If systematically developed, many intuitionistic results would be seen to hold classically as well, and thus offer a way to develop a strong constructive theory which is still consistent with the rest of classical mathematics.

Such a constructive theory can form a conceptual framework for applied mathematics and information technology.

These sciences now use an ad-hoc approach to reality since the classical framework is inadequate. … and can easily use the richness of ideas already present in classical mathematics, if classical mathematics were to be systematically developed along the common grounds before the unconstructive elements are brought in.”

Frank Waaldijk [33]

“… we propose that Laplacian determinism be seen in the light of constructive mathematics and Church’s Thesis.

This means amongst other things that infinite sequences (of natural numbers; a real number is then given by such an infinite sequence) are never `finished’, instead we see them developing in the course of time.

Now a very consequent, therefore elegant interpretation of Laplacian determinism runs as follows.

Suppose that there is in the real world a developing-infinite sequence of natural numbers, say \alpha. Then how to interpret the statement that this sequence is `uniquely determined’ by the state of the world at time zero?

At time zero we can have at most finite information since, according to our constructive viewpoint, infinity is never attained. So this finite information about \alpha supposedly enables us to `uniquely determine’ \alpha in its course of time.

It is now hard to see another interpretation of this last statement, than the one given by Church’s Thesis, namely that this finite information must be a (Turing-)algorithm that we can use to compute \alpha (n) for any n \in \mathbb(N).

With classical logic and omniscience, the previous can be stated thus:

`for every (potentially infinite) sequence of numbers (a_{n})_{n \in \mathbb{N}} taken from reality there is a recursive algorithm \alpha such that \alpha (n) = a_{n} for each n \in \mathbb{N}. This statement is sometimes denoted as `CT_{phys}‘,

… this classical omniscient interpretation is easily seen to fail in real life.

Therefore we adopt the constructive viewpoint.

The statement `the real world is deterministic’ can then best be interpreted as:

`a (potentially infinite) sequence of numbers (a_{n})_{n \in \mathbb{N}} taken from reality cannot be apart from every recursive algorithm \alpha (in symbols: \neg \forall \alpha \in \sigma_{\omega REC} \exists n \in \mathbb{N}\ [\alpha(n) \neq a_{n}])’.”

Frank Waaldijk [34]

References

Be64 John Stewart Bell. 1964. On the Einstein Podolsky Rosen Paradox Physics Vol 1, No. 3, pp.195-200, 1964. Reprinted in J. S. Bell, Speakable and unspeakable in quantum mechanics, Cambridge, 2004, p. 14-21.

Bo52 David Bohm. 1952. A Suggested Interpretation of the Quantum Theory in Terms of `Hidden Variables’, I. Physical Review 85 n.2, pp.166-179 (1952) and A Suggested Interpretation of the Quantum Theory in Terms of `Hidden Variables’, II. Physical Review 85 n.2, pp.180-193 (1952).

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

Ch82 Gregory J. Chaitin. 1982. Gödel’s Theorem and Information. International Journal of Theoretical Physics 22 (1982), pp. 941-954.

EPR35 Albert Einstein, Boris Yakovlevich Podolsky, Nathan Rosen. 1935. Can Quantum-Mechanical Description of Physical Reality be Considered Complete? InPhysical Review PHYS REV X – vol. 47, no. 10, pp.777-780. Bibcode 1935PhRv\ldots 47…777E. doi:10.1103/PhysRev.47.777.

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. pp.5-38.

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

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.

Sc35 Erwin Schrödinger. Die gegenwärtige Situation in der Quantenmechanik, Naturwissenschaftern. 23: pp. 807-812; 823-823, 844-849. (1935). English translation: John D. Trimmer, The present situation in Quantum Mechanics, Proceedings of the American Philosophical Society 124, pp. 323-38 (1980), reprinted in Quantum Theory and Measurement, p. 152 (1983).

Sh11 Sheldon Goldstein et al. 2011. Bell’s Theorem, Scholarpedia, 6(10):8378, doi:10.4249/scholarpedia.8378.

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.

Wa03 Frank Waaldijk. 2003. On the foundations of constructive mathematics. Web paper.

Wi78 Ludwig Wittgenstein. 1937. Remarks on the Foundations of Mathematics. 1978 ed., MIT Press, Cambridge.

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.

An12a Bhupinder Singh Anand. 2012. Some consequences of interpreting the associated logic of the first-order Peano Arithmetic PA finitarily. Draft.

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

Notes

Return to 1: “Because it consists of the views developed by a number of scientists and philosophers during the second quarter of the 20th Century, there is no definitive statement of the Copenhagen interpretation”, Wikipedia; cf., Copenhagen Interpretation of Quantum Mechanics, Stanford Encyclopedia of Philosophy; also The Copenhagen Interpretation of Quantum Mechanics by Ben Best.

Return to 2: “It is a general principle of orthodox formulations of quantum theory that measurements of physical quantities do not simply reveal pre-existing or pre-determined values, the way they do in classical theories. Instead, the particular outcome of the measurement somehow “emerges” from the dynamical interaction of the system being measured with the measuring device, so that even someone who was omniscient about the states of the system and device prior to the interaction couldn’t have predicted in advance which outcome would be realized.” … Sh11.

Return to 2: Highlighted famously by Erwin Schrödinger’s caustic observation on the dubious condition of his Platonic pet:

“One can even set up quite ridiculous cases. A cat is penned up in a steel chamber, along with the following device (which must be secured against direct interference by the cat): in a Geiger counter there is a tiny bit of radioactive substance, so small, that perhaps in the course of the hour one of the atoms decays, but also, with equal probability, perhaps none; if it happens, the counter tube discharges and through a relay releases a hammer which shatters a small flask of hydrocyanic acid. If one has left this entire system to itself for an hour, one would say that the cat still lives if meanwhile no atom has decayed. The \psi-function of the entire system would express this by having in it the living and dead cat (pardon the expression) mixed or smeared out in equal parts.” … Sc35, §5.

Return to 3: cf. Sh11.

Return to 4: EPR35.

Return to 5: “`Non-local’ … means that there exist interactions between events that are too far apart in space and too close together in time for the events to be connected even by signals moving at the speed of light.” … Sh11.

Return to 6: “Traditionally, the phrase `hidden variables’ is used to characterize any elements supplementing the wave function of orthodox quantum theory.” … Sh11.

Return to 7: Bo52.

Return to 8: “This terminology is, however, particularly unfortunate in the case of the de Broglie-Bohm theory, where it is in the supplementary variables—definite particle positions—that one finds an image of the manifest world of ordinary experience.” … Sh11.

Return to 9: Which could be considered as having pre-existing or pre-determined mathematical values over the domain over which the functions are well-defined.

Return to 10: Be64.

Return to 11: Concerning evidence-based and finitary interpretations of the first order Peano Arithmetic PA, in An12.

Return to 12: As defined below—hence mathematically determinate but unpredictable.

Return to 13: “We may regard the present state of the universe as the effect of its past and the cause of its future. An intellect which at any given moment knew all the forces that animate Nature and the mutual positions of the beings that comprise it, if this intellect were vast enough to submit its data to analysis, could condense into a single formula the movement of the greatest bodies of the universe and that of the lightest atom: for such an intellect nothing could be uncertain; and the future just like the past would be present before its eyes.” … Pierre Simon Laplace, A Philosophical Essay on Probabilities.

Return to 14: See An12.

Return to 15: `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 16: 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 17: In the sense of a physically `completable’ infinite sequence (as needed to resolve Zeno’s paradox).

Return to 18: Tu36, p.132, §8.

Return to 19: Wi78.

Return to 20: An12a, Corollary 8, p.27.

Return to 21: An12a, Corollary 8, p.27.

Return to 22: Go31.

Return to 23: Wi78.

Return to 24: Tu36.

Return to 25: Ch82.

Return to 26: A putative model for such behaviour is given in Wa03, §1.5, p.5:

“The second way to model our real world is to assume that it is deterministic. …

It would be worthwhile to explore the consequences of a deterministic world with incomplete information (since under the assumption of determinancy in the author’s eyes this comes closest to real life).

That is a world in which each infinite sequence is given by an algorithm, which in most cases is completely unknown.

We can model such a world by introducing two players, where player I picks algorithms and hands out the computed values of these algorithms to player II, one at a time.

Sometimes player I discloses (partial) information about the algorithms themselves.

Player II can of course construct her or his own algorithms, but still is confronted with recursive elements of player I about which she/he has incomplete information.”

Return to 27: Go31.

Return to 28: Which—as shown in An12—is the behaviour sought to be captured by the Standard interpretation of the first order Peano Arithmetic PA.

Return to 29: And categorical, as argued in An12a.

Return to 29a: For a model of widely separated outputs that are correlated but don’t allow communication, which demonstrates that non-locality doesn’t imply communication, see this paper Wim van Dam: Implausible Consequences of Superstrong Nonlocality and this explanatory blog A Neighborhood of Infinity: Distributed computing with alien technology.

Return to 30: An12 establishes the `consistency’.

Return to 31: An12a establishes the `categoricity’—which means that any two models of the Arithmetic are isomorphic.

Return to 32: Wa03.

Return to 33: ibid., §1.6, p.5.

Return to 34: ibid., §7.2, p.24.

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

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

Gowers's Weblog

Mathematics related discussions