You are currently browsing the tag archive for the ‘partial-recursive’ tag.

# Tag Archive

## Does mathematics need a new foundation?

August 31, 2013 in Foundations of mathematics, logic and computation, Philosophy | Tags: ambiguity, arithmetic, Church Turing Thesis, constructivity, effective computability, Elliott Mendelson, feasibility, function, Geoffrey Hellman, George Lakoff, impredicativity, John L. Bell, logic, logical validity, mathematical objects, mathematical truth, melvyn b nathanson, meta-mathematical, paradoxes, partial-recursive, philosophy, Platonic, proofs, Rafael Nunez, set-theoretic, Tarski, theorems, W. T. Gowers | Leave a comment

**There is indeed cause for disquiet**

Jan Pedersen introduces hmself in his LinkedIn profile as a software developer and an artificial intelligence thinker with a passion for philosophy.

So, from a lay person’s perspective, I can empathise with the sense of professional disquietitude that perhaps motivated him recently to invite the following discussion (alive and kicking as of this moment) in the LinkedIn group `History and Philosophy of Science’:

“Does mathematics need a new foundation?

Reading George Lakoff’s & Rafael Nunez excellent book `Where Mathematics comes from’ leaves me with that impression.

The view that mathematics deals with Platonic like objects in some higher realm is too naïve and does not go well along with several paradoxes and meta-mathematical theories.”

Jan is not alone in his desire to ground his lifes work upon a firmer mathematical, logical and philosophical foundation.

**Melvyn B. Nathanson**

For instance, the point was forcibly made some time back by Melvyn B. Nathanson that:

“ … many great and important theorems don’t actually have proofs. They have sketches of proofs, outlines of arguments, hints and intuitions that were obvious to the author (at least, at the time of writing) and that, hopefully, are understood and believed by some part of the mathematical community.

But the community itself is tiny. In most fields of mathematics there are few experts. Indeed, there are very few active research mathematicians in the world, and many important problems, so the ratio of the number of mathematicians to the number of problems is small. In every field, there are “bosses” who proclaim the correctness or incorrectness of a new result, and its importance or unimportance.

Sometimes they disagree, like gang leaders fighting over turf. In any case, there is a web of semi-proved theorems throughout mathematics. Our knowledge of the truth of a theorem depends on the correctness of its proof and on the correctness of all of the theorems used in its proof. It is a shaky foundation.”

… “*Desperately Seeking Mathematical Truth,*“, Opinion piece in the August 2008 Notices of the American Mathematical Society, Vol. 55, Issue 7.

**Elliott Mendelson**

A similar concern was reflected earlier in another context by Elliott Mendelson:

“Here is the main conclusion I wish to draw: it is completely unwarranted to say that CT is unprovable just because it states an equivalence between a vague, imprecise notion (effectively computable function) and a precise mathematical notion (partial-recursive function).

… The concepts and assumptions that support the notion of partial-recursive function are, in an essential way, no less vague and imprecise than the notion of effectively computable function; the former are just more familiar and are part of a respectable theory with connections to other parts of logic and mathematics. (The notion of effectively computable function could have been incorporated into an axiomatic presentation of classical mathematics, but the acceptance of CT made this unnecessary.) … Functions are defined in terms of sets, but the concept of set is no clearer than that of function and a foundation of mathematics can be based on a theory using function as primitive notion instead of set. Tarski’s definition of truth is formulated in set-theoretic terms, but the notion of set is no clearer, than that of truth. The model-theoretic definition of logical validity is based ultimately on set theory, the foundations of which are no clearer than our intuitive understanding of logical validity.

… The notion of Turing-computable function is no clearer than, nor more mathematically useful (foundationally speaking) than, the notion of an effectively computable function …”

… Second Thoughts About Church’s Thesis and Mathematical Proofs. 1990. Journal of Philosophy 87.5.

**Albert G. Dragalin**

Another perspective towards the inadequacy of current foundational assumptions is that of Albert G. Dragalin, for whom the central question is:

“… what is the correspondence between real facts and these counterparts in mathematics? This is very deep and difficult philosophical problem, we are very far from solving it completely …

We note three sorts of such difficulties:

1) *The impredicativity,* i.e. the circular character of definitions for our objects of investigation. This impredicativity is characteristic for the set theoretic theories, it closely concerns using the *abstraction of alienation,* when a person formulates some thoughts and then *uses* the thoughts as the subject of investigation, as a separate thing to be considered. In the extreme form this abstraction leads to paradoxes like the famous Liar’s paradox. But even in the more modest fortm of the type theory comprehension axiom we get somje unsurmountable difficulties.

Strictly speaking, even the notion of natural number contains an impredicativity (in the form of an unrestricted arithmetical induction principle) and there were some attempts to construct a *predicative arithmetic,* but most of mathematicians adopt the thesis that the natural numbers can be considered as given for granted entities (the so-called *Kroneker’s thesis*).

2) *The lack of constructivity.* It means that usual theories use the classical logic and, hence, some non-constructive proofs. In combination with the set theory it leads to complicated abstract constructs which have no computational or even no nominalistic ontological sense.

3) *The lack of feasibility.* It means that even in our constructive proofs we usually do not distinct feasible and not feasible calculations. So our (even ‘practically looking’) results are often principally not feasible, and so they are beyond human ability.”

… *On Foundations of Mathematics: Some modern problems and achievements*

**Geoffrey Hellman and John L. Bell**

From a slightly different perspective, Geoffrey Hellman and John L. Bell note that:

“Contrary to the popular (mis)conception of mathematics as a cut-and dried body of universally agreed upon truths and methods, as soon as one examines the foundations of mathematics, one encounters divergences of viewpoint and failures of communication that can easily remind one of religious, schismatic controversy. While there is indeed universal agreement on a substantial body of mathematical results, and while classical methods overwhelmingly dominate actual practice, as soon as one asks questions concerning fundamentals, such as “What is mathematics about?”, “What makes mathematical truths true?”, “What axioms can we accept as unproblematic?”, and notoriously, even “What are the acceptable logical rules by which mathematical proofs can proceed?”, we ﬁnd we have entered a mine-ﬁeld of contentiousness.”

… *Pluralism and the Foundations of Mathematics.* In *Itekellersetal:Sp* (2006).

**William P. Thurston**

A similar disquiet is echoed by William P. Thurston:

On the most fundamental level, the foundations of mathematics are much shakier than the mathematics that we do. Most mathematicians adhere to foundational principles that are known to be polite ﬁctions. For example, it is a theorem that there does not exist any way to ever actually construct or even deﬁne a well-ordering of the real numbers. There is considerable evidence (but no proof) that we can get away with these polite ﬁctions without being caught out, but that doesn’t make them right. Set theorists construct many alternate and mutually contradictory “mathematical universes” such that if one is consistent, the others are too. This leaves very little conﬁdence that one or the other is the right choice or the natural choice.

… *On Proof And Progress In Mathematics.* In the *Bulletin of the American Mathematical Society.* Volume 30, Number 2, April 1994, Pages 161-177.

**W. T. Gowers**

Whilst introducing this blog I noted two troubling philosophical issues in the foundations of mathematics that seemed to need addressing if mathematicians, logicians and computationalists were to build upon their fundamental assumptions with a reasonably comfortable sense of security.

These were the ones identified and highlighted by W. T. Gowers:

“If you ask a philosopher what the main problems are in the philosophy of mathematics, then the following two are likely to come up: what is the status of mathematical truth, and what is the nature of mathematical objects? That is, what gives mathematical statements their aura of infallibility, and what on earth are these statements about?”

… “*Does mathematics need a philosophy?*“, presented before the Cambridge University Society for the Philosophy of Mathematics and Mathematical Sciences, 2002.

**Gila Sher**

In a recent thought-provoking survey of the foundational problem of logic, Gila Sher obliquely refers to the problem of satisfactorily defining both mathematical and logical ‘truth’, whilst concluding that the issue is essentially one of inadequate methodology:

“It is an interesting fact that, with a small number of exceptions, a systematic philosophical foundation for logic, a foundation for logic rather than for mathematics or language, has rarely been attempted. …

By a philosophical foundation for logic I mean in this paper a substantive philosophical theory that critically examines and explains the basic features of logic, the tasks logic performs in our theoretical and practical life, the veridicality of logic—including the source of the truth and falsehood of both logical and meta-logical claims, the grounds on which logical theories should be accepted (rejected, or revised), the ways logical theories are constrained and enabled by the mind and the world, the relations between logic and related theories (e.g., mathematics), the source of the normativity of logic, and so on. The list is in principle open-ended since new interests and concerns may be raised by different persons and communities at present and in the future. In addition, the investigation itself is likely to raise new questions (whether logic is similar to other disciplines in requiring a grounding in reality, what the distinctive characteristics of logical operators are, etc.).

A foundational theory of this kind … should provide us with tools for criticizing, justifying, evaluating, constructing, and improving specific theories. These elements—critical examination, veridical justification, epistemic evaluation, and so on, as well as creating theoretical tools for these tasks—are the main elements of what I call “grounding” in this paper. …

Logic, however, is a very broad discipline, and the present investigation does not purport to apply to all its branches. Instead, it focuses on that branch which in our time is often referred to as “mathematical logic” and in earlier times took the forms of syllogistic logic, Fregean logic, and type-theoretic logic. And even here it is largely concerned with finitistic versions of this branch. These and other self-imposed restrictions will enable us to be more specific on the questions we address in this paper and will give us the space to discuss several issues of interest to mathematical as well as philosophical logicians. These include, for example, Feferman’s criticism of what he called the Tarski–Sher thesis (Feferman [1999], [2010]), the relation between logic and mathematics, the possibility of extending structuralism from mathematics to logic, and topics of relevance to model-theoretic logic.

I have said that systematic attempts to construct a philosophical foundation for logic have been rare. But was not the period between the late 19th-century and the early 20th-century a period of “foundational studies in logic and mathematics”, indeed a period of extraordinary growth and remarkable breakthroughs in this area? The answer is “Yes” with a caveat.

Yes, there were foundational investigations and groundbreaking developments, but for the most part they aimed at a foundation for mathematics, with logic playing a mostly instrumental, if crucial, role. Frege, for example, developed a logical system that would provide a foundation for mathematics, but aside from a few hints, did not attempt to provide a systematic philosophical foundation for logic itself. Russell improved and further developed Frege’s logicism, but although he appreciated the need to provide a systematic philosophical explanation of logic itself—one that would answer such questions as: “In virtue of what are logical propositions true?” he despaired of accomplishing this task. Thus he says:

*The fundamental characteristic of logic, obviously, is that which is indicated when we say that logical propositions are true in virtue of their form. . . . I confess, however, that I am unable to give any clear account of what is meant by saying that a proposition is “true in virtue of its form”.*

… Bertrand Russell, *The Principles of Mathematics,* In his introduction to the second edition, 1938, p.xii, Norton, New York.

Indeed, many of the momentous discoveries in meta-logic (by Hilbert, Gödel, Turing, and others) are commonly designated as contributions to “meta-mathematics”. These epochal achievements, however, are not irrelevant to the foundational problemof logic. On the contrary, by giving rise to a sophisticated logical framework and establishing its mathematical properties they created a fertile ground for a theoretical foundation for logic. It is all the more surprising, therefore, that few 20th- and 21st-century philosophers have taken up the challenge. Many have believed that a substantive, theoretical foundation for logic is impossible, some have considered it superfluous, quite a few have been content to simply say that logic is obvious, others have viewed logic as conventional, hence not in need of a foundation, and so on.

This tendency to avoid a philosophical engagement with the foundational problem of logic is not limited to the recent past. We can see it in the great philosophical systems of the 17th and 18th century. Take Kant, for example. Without purporting to offer scholarly exegesis of Kant’s philosophy of logic, we may note that Kant’s approach to logic is quite different from his approach to other disciplines. While Kant set out to provide a foundation for human knowledge in its entirety, he took formal logic largely as given. Logic, Kant emphasizes, has not required a major revision since Aristotle, and although there is room for clarifications and adjustments, there is no need for establishing the “certainty” of logic:

*That logic has already, from the earliest times, proceeded upon this sure path is evidenced by the fact that since Aristotle it has not required to retrace a single step, unless, indeed, we care to count as improvements the removal of certain needless subtleties or the clearer exposition of its recognised teaching, features which concern the elegance rather than the certainty of the science.*

… Immanuel Kant, *Critique of Pure Reason,*, 1781/7, Bviii, Macmillan, London, translated by N. Kemp Smith, 1929.

The scarcity of attempts to provide a theoretical foundation for logic is especially notable in light of epistemologists’ recognition that logic has a special standing in knowledge. Compare logic and physics, for example. It is quite common to say that physics is bound by the laws of logic but logic is not bound by the laws of physics, that a serious error in logic might undermine our physical theory, but a serious error in physics would not undermine our logical theory. And it stands to reason that the more general, basic and normative a given field of knowledge is, the more important it is to provide it with a foundation. Nevertheless a theoretical foundation for logic, and in particular a non-trivializing foundation, has rarely been attempted. Why?

Clearly, the failure to attempt such a foundation is not due to neglect, oversight, or intellectual limitations. The extraordinary advances in logic and meta-logic on the one hand, and the wealth of attempts to construct a philosophical foundation for mathematics and science on the other, suggest that neither neglect nor intellectual handicaps are the problem. In my view, the source of the problem is methodological. Certain features of the customary foundational methodology make it very problematic to construct a philosophical foundation for logic, and the first step in confronting the foundational problem of logic is, therefore, dealing with the methodological difficulty.”

… “*The Foundational Problem of Logic*“, Submitted draft of the paper in *The Bulletin of Symbolic Logic,* Volume 19, Issue 2 (2013), pp.145-198.

**What mathematics does need is a greater awareness of the nature of its foundations**

So where do we go from here?

In the following pages we shall argue that what mathematics needs is not a new foundation, but a greater awareness of the *nature* of its existing foundations.

**Author’s working archives & abstracts of investigations**

## Recent comments